Intrusieve gelinkte lijsten - Datastructuren in de praktijk

Wat zijn intrusieve gelinkte lijsten?

Intrusieve gelinkte lijsten zijn een variatie op gelinkte lijsten waarbij de koppelingen (links) zijn ingebed in de structuur die gekoppeld wordt.

In een typische implementatie van een gelinkte lijst bevat een lijstknooppunt (list node) een datapointer naar de gekoppelde gegevens en een next-pointer naar het volgende knooppunt in de lijst.

In een intrusieve implementatie bevat het lijstknooppunt wel een next-pointer naar het volgende knooppunt, maar geen datapointer. Dit komt omdat de lijst direct is ingebed in het object zelf.

Een structuur voor een intrusieve enkelvoudig gelinkte lijst bevat een enkele next-pointer naar een ander lijstknooppunt:

typedef struct list {
    struct list *next;
} list;

Deze lijststructuur wordt vervolgens ingebed in de structuur die gekoppeld moet worden. Bijvoorbeeld, een item-structuur met een val-lid:

typedef struct item {
    int val;
    list items;
} item;

Om een nieuw item i2 toe te voegen aan de lijst van i1, stelt u de items.next-pointer van i1 in op het adres van i2.items:

item* i1 = create_item(16);
item* i2 = create_item(18);
i1->items.next = &i2->items;

U kunt het object dat een lijstknooppunt bevat benaderen door eerst het adres van het lijstobject op te halen (bijv. de waarde van i1.items.next). Vervolgens trekt u de offset van het lijstlid af van het adres van het lijstobject.

De offset is het aantal bytes dat een lid vanaf het begin van het omvattende object is gepositioneerd.

Stel dat een lijstobject in object i2 zich bevindt op geheugenadres 0x18. Het lijstlid heeft een offset van 8 bytes vanaf het begin van de item-datastructuur. Daarom is het beginadres van het i2-object: 0x18 - 8 = 0x10.

In C-code die met GCC is gecompileerd, kunt u bytes van een pointer aftrekken door de pointervariabele te casten naar een void-pointer (die bij GCC een grootte van 1 byte heeft). U kunt dan bytes aftrekken van de pointerwaarde zonder dat het getal wordt geschaald naar num * sizeof(structuur):

item* _i2 = (void *)(i1->items.next) - 8;

Let op: Pointer-aritmetiek op een void-pointer is illegaal in standaard C, maar wordt ondersteund door GCC. Linux wordt gecompileerd met GCC en kan daarom pointer-aritmetiek op void-pointers uitvoeren.

Het aftrekken van een absolute waarde is niet portabel, omdat datatypes verschillende groottes kunnen hebben afhankelijk van de CPU-architectuur. Een betere methode is het gebruik van de offsetof-macro. Deze retourneert de offset van een lid ten opzichte van de omvattende structuur (in bytes):

item* _s2 = (void *)(i1->items.next) - (offsetof(item, items));

Samenvattend:

• Het lijstknooppunt is ingebed in een omvattend object.
• Het lijstknooppunt wijst naar een ander lijstknooppunt dat is ingebed in het gekoppelde object.
• Het basisadres van het gekoppelde object wordt berekend door de offset van het lijstlid af te trekken van het geheugenadres van het gelinkte lijstobject.

Waarom intrusieve gelinkte lijsten gebruiken?

Er zijn twee belangrijke redenen om voor intrusieve lijsten te kiezen boven niet-intrusieve gelinkte lijsten:

1. Minder geheugenallocaties: Bij niet-intrusieve lijsten vereist het maken van een nieuw object en het toevoegen ervan aan een lijst twee allocaties: één voor het object en één voor het lijstknooppunt. Bij intrusieve lijsten hoeft u slechts één object te alloceren, aangezien het knooppunt is ingebed. Dit vermindert het aantal fouten, omdat er minder situaties zijn waarin een geheugenallocatie kan mislukken.
2. Minder cache thrashing: Het itereren door een niet-intrusieve lijst vereist het derefereren van een lijstknooppunt en daarna het derefereren van de lijstgegevens. Intrusieve lijsten vereisen alleen het derefereren van het volgende lijstknooppunt.

Dubbel gelinkte en circulaire lijsten

Dubbel gelinkte en circulaire lijsten zijn variaties op enkelvoudig gelinkte lijsten. Linux maakt gebruik van circulaire dubbel gelinkte lijsten.

Dubbel gelinkte lijsten

Een dubbel gelinkte lijst houdt pointers bij naar zowel het volgende (next) als het vorige (prev) knooppunt.

De lijststructuur bevat dus een extra prev-pointer:

typedef struct dlist {
    struct dlist *next;
    struct dlist *prev;
} dlist;

Dubbel gelinkte lijsten maken het verwijderen en invoegen eenvoudiger, omdat u slechts een referentie naar één enkel knooppunt nodig heeft om deze acties uit te voeren.

Circulaire gelinkte lijsten

Een circulaire gelinkte lijst wijst nooit naar een null-waarde. In plaats daarvan wijst het laatste knooppunt terug naar het eerste knooppunt. In een circulaire dubbel gelinkte lijst wijst het eerste knooppunt ook naar het laatste knooppunt.

Een circulaire lijst maakt het eenvoudig om vanuit elk willekeurig knooppunt door de gehele lijst te itereren, zonder dat er een referentie naar een specifieke lijstkop (list head) bewaard hoeft te worden:

void list_print_each(list* node) {
    list* start = node;
    do {
        printf("%d,", node->val);
        node = node->next;
    } while (node != start);
}

De meest gebruikte gelinkte lijsten in Linux zijn circulaire dubbel gelinkte lijsten.

Gelinkte lijsten in Linux

Linux maakt uitgebreid gebruik van gelinkte lijsten voor allerlei taken, van het bijhouden van vrije geheugen-slabs tot het itereren door elk actief proces. Een zoekopdracht naar de structuur struct list_head levert in Linux 5.2 meer dan 10.000 resultaten op.

In Linux worden lijstknooppunten veel vaker toegevoegd en verwijderd dan dat ze worden doorlopen. Een analyse van Linux tijdens normaal gebruik wees uit dat traversals (het doorlopen van de lijst) slechts 6% van de totale bewerkingen aan gelinkte lijsten uitmaakten. Van die traversals vonden 28% plaats op lege lijsten of bezochten ze slechts één knooppunt.

Linux gebruikt gelinkte lijsten dus hoofdzakelijk voor objecten waarbij het doorlopen van de lijst zelden voorkomt, of waarbij de lijst klein is. De meest populaire structuur hiervoor is de intrusieve circulaire dubbel gelinkte lijst.

Implementatie van intrusieve gelinkte lijsten in Linux

De Linux circulaire dubbel gelinkte lijst is gedefinieerd in include/linux/list.h. De structuur heet list_head en bevat een next- en prev-pointer:

struct list_head {
    struct list_head *next, *prev;
};

U maakt een gelinkte lijst van objecten door list_head in te bedden als lid van de structuur die in een lijst moet worden geplaatst:

struct atmel_sha_drv {
    struct list_head head;
    // ..
};

Een nieuwe lijst kan statisch of dynamisch worden geïnitialiseerd. Een statisch geïnitialiseerde lijst kan de LISTHEADINIT-macro gebruiken:

static struct atmel_sha_drv atmel_sha = {
    .dev_list = LIST_HEAD_INIT(atmel_sha.dev_list),
    // ..
};

LISTHEADINIT zorgt ervoor dat de next- en prev-pointers van het lijstknooppunt naar zichzelf wijzen: #define LISTHEADINIT(name) { &(name), &(name) }

Om een lijst dynamisch te initiëren, kan de INITLISTHEAD-macro worden gebruikt. Vaak wordt een apart list_head bewaard als hoofdknooppunt:

static struct list_head hole_cache;
INIT_LIST_HEAD(&hole_cache);

INITLISTHEAD wordt aangeroepen met een pointer naar een lijstknooppunt, waarbij de pointers wederom naar zichzelf worden gezet:

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    WRITE_ONCE(list->next, list);
    list->prev = list;
}

Opmerking: de WRITE_ONCE-macro voorkomt ongewenste compiler-optimalisaties bij het toewijzen van een waarde.

Nieuwe items kunnen worden toegevoegd met list_add:

struct hole {
    // ..
    struct list_head list;
};

static struct hole initholes[64];
// ..
for(i = 0; i < 64; i++)
    list_add(&(initholes[i].list), &hole_cache);

list_add accepteert een pointer naar een hoofdknooppunt en een pointer naar het knooppunt dat moet worden ingevoegd. Het roept vervolgens __list_add aan om het nieuwe knooppunt tussen het hoofdknooppunt en head->next te plaatsen:

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
    // ..
    next->prev = new;
    new->next = next;
    new->prev = prev;
    WRITE_ONCE(prev->next, new);
}

Linux biedt de list_entry-macro om de omvattende datastructuur van een lijstknooppunt te benaderen:

struct hole *ret;
ret = list_entry(hole_cache.next, struct hole, list);

Dit maakt gebruik van de eerder genoemde offset-techniek. listentry expandeert naar een containerof-macro:

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

De containerof-macro berekent het adres van het omvattende object door de offset van het lijstknooppunt af te trekken van het adres van het listhead-object:

#define container_of(ptr, type, member) ({				\
    void *__mptr = (void *)(ptr);					\
    ((type *)(__mptr - offsetof(type, member))); })

Processen volgen

In POSIX is een proces een uitvoerende instantie van een programma. Een van de kerntaken van de kernel is het creëren van processen en het inplannen (scheduling) ervan, zodat elk proces een passende hoeveelheid tijd krijgt.

Intern noemt Linux processen "tasks". Wanneer taken worden gemaakt, worden ze toegevoegd aan een takenlijst. Deze lijst wordt gebruikt wanneer Linux over elke enkele taak moet itereren, bijvoorbeeld bij het verzenden van een signaal naar elk proces.

Linux representeert taken als een taskstruct. Een taskstruct bevat een list_head-lid genaamd tasks om de koppeling tussen taken te maken:

struct task_struct {
    // ..
    pid_t pid;
    // ..
    struct list_head tasks;
    // ..
};

De initiële taak is statisch gealloceerd als init_task, en het tasks-veld is geïnitialiseerd met zichzelf als head:

struct task_struct init_task = {
    // ..
    .tasks = LIST_HEAD_INIT(init_task.tasks),
};

Toekomstige taken worden toegevoegd aan deze lijst op het moment dat ze worden gecreëerd via forking. Dit is geïmplementeerd in copyprocess, die een nieuwe taskstruct maakt van het huidige uitvoerende proces (current) door duptaskstruct aan te roepen:

struct task_struct *copy_process(
    // ..
)
{
    struct task_struct *p;
    // ..
    p = dup_task_struct(current, node);
    // ..
}

Na creatie wordt de nieuwe taak toegevoegd aan de takenlijst via listaddtailrcu met het adres van inittask.tasks:

struct task_struct *copy_process(
    // ..
)
{
    // ..
    list_add_tail_rcu(&p->tasks, &init_task.tasks);
}

listaddtailrcu is een variatie op de listadd-functie. Het maakt gebruik van RCU (Read-Copy-Update), een synchronisatiemechanisme dat gelijktijdigheid ondersteunt tussen één schrijver en meerdere lezers. listaddtailrcu voegt het tasks-knooppunt van de nieuwe taak toe aan het einde van de inittask-lijst.

Zoals vermeld wordt de takenlijst vooral gebruikt wanneer de kernel een actie op elke taak moet uitvoeren. Voorbeelden hiervan zijn het bevriezen van taken bij het in hibernate-modus gaan van een computer, het wisselen van taken naar een bijgewerkte kernelversie tijdens een live patch, of het verzenden van een signaal naar elk proces. Omdat deze acties zeldzaam zijn, is de efficiëntie van het itereren door de lijst geen groot probleem.

Een voorbeeld waarbij een signaal naar elk proces wordt gestuurd, is wanneer de SysRq-toets en de e-toets tegelijkertijd worden ingedrukt, wat alle processen beëindigt. (SysRq is een toets uit de jaren '80; Linux voegt hier standaard sneltoetsen aan toe).

De kernel registreert een handler-functie die wordt aangeroepen bij SysRq + e. Deze handler roept sendsigall aan met SIGTERM, wat een SIGTERM-signaal stuurt naar alle processen, behalve naar het init-proces en kernel-taken. Dit gebeurt met de foreachprocess-macro:

static void send_sig_all(int sig)
{
    struct task_struct *p;
    // ..
    for_each_process(p) {
        if (p->flags & PF_KTHREAD)
            continue;
        if (is_global_init(p))
            continue;
        do_send_sig_info(sig, SEND_SIG_PRIV, p, PIDTYPE_MAX);
    }
    // ..
}

De foreachprocess-macro expandeert naar een for-loop die over elk item in de lijst loopt door de waarde van p te wijzigen. Beginnend bij inittask gebruikt het de nexttask-macro om het volgende item te bereiken:

#define for_each_process(p) \
    for (p = &init_task ; (p = next_task(p)) != &init_task ; )

De nexttask-macro expandeert vervolgens naar listentryrcu om de volgende taskstruct van de lijst-head pointer te verkrijgen:

#define next_task(p) \
    list_entry_rcu((p)->tasks.next, struct task_struct, `tasks`)

listentryrcu is op zijn beurt een macro die expandeert naar de container_of-macro, die vervolgens het basisadres van de omvattende structuur bepaalt.

Het is vermeldenswaard dat de tasks-lijst niet de enige manier is waarop Linux referenties naar taken bijhoudt. Er wordt ook een dictionary-datastructuur (een idr) gebruikt die toegang in constante tijd biedt. Dit wordt gebruikt om snel een taakobject op te zoeken aan de hand van een specifiek PID, wat veel efficiënter is dan het doorlopen van de gehele takenlijst.

Conclusie

Intrusieve gelinkte lijsten zijn een interessant alternatief voor niet-intrusieve lijsten, omdat ze cache thrashing en het aantal geheugenallocaties verminderen.

Linux maakt veel gebruik van intrusieve gelinkte lijsten, over het algemeen wanneer de lijsten kort zijn of zelden worden doorlopen. Als u zich wilt verdiepen in kernel-hacking, is het essentieel om bekend te raken met intrusieve gelinkte lijsten.