[C] CAS concurrent linked-list

[CurlyMo]

Ik probeer een non-blocking linked list te maken, maar dat lukt niet erg. Veel online bronnen refereren aan het artikel van Timothy L. Harris A Pragmatic Implementation of Non-blocking Linked-Lists Alle pseudo code is geschreven rond C++, maar het lukt me niet om de boel te vertalen naar C voor mijn unordered list.

Invoegen gaat nog, ook aan de hand van de wikipedia uitleg:

C:

typedef struct ll {
    int i;
    struct ll *head;
} ll;

struct ll *list = NULL;

void list_add(int x) {
    struct ll *node = malloc(sizeof(struct ll));
    node->i = x;

    struct ll *cpy = list;
    do {
        cpy = list;
        node->head = cpy;
    } while(!__sync_bool_compare_and_swap(&list, cpy, node));
}

Dat werkt prima.

Voor het verwijderen beschrijft Harris een tweetrapsraket. Eerst verwijder je een node logisch, daarna fysiek.
Voor de logische verwijderingen is het nodig eerst de tail te ontkoppelen van de huidige node en er een nieuwe node tussen te plaatsen.

Waar ik echter al vast loop is hoe je een dubbele linked list maakt om de tail ontkoppeling te faciliteren bij verwijdering.

C:

typedef struct ll {
    int i;
    struct ll *head;
    struct ll *tail;
} ll;

struct ll *list = NULL;

void list_add(int x) {
    struct ll *node = malloc(sizeof(struct ll));
    node->i = x;
    node->tail = NULL;

    struct ll *cpy = list;
    do {
        cpy = list;
        node->head = cpy;
    } while(!__sync_bool_compare_and_swap(&list, cpy, node));
    if(node->head != NULL) {
        node->head->tail = node;
    }
}

Het probleem hier is dat het vullen van de tail van de node volgens mij niet thread-safe is. Op hetzelfde moment als dat de tail gevuld wordt, kan ergens via een logische verwijdering al een ontkoppeling hebben plaatsgevonden, waardoor de head van de tail al niet meer naar node verwijst.

En dan ben ik nog niet eens toegekomen aan de daadwerkelijke verwijderingslogica, maar zit ik nog vast in het begrijpen van dit deel van het concept zoals beschreven door Harris

[SPee]

Wil je double linked list maken?
Dan zit je inderdaad op een unsafe stukje bij het toevoegen/verwijderen van een node.
Dat wordt soms opgelost door een locking mechanisme icm het aanroepen van een methode die de aanpassing doet. Of met een waarschuwing "not thread safe".

Als je denkt dat je een double linked list nodig hebt om een node te verwijderen?
Nee, dat is niet nodig.
Je houdt node1 in een variabele, controleert of node2 verwijderd moet worden, en als dat het geval is, dan werk je node1.head bij met de waarde node2.head. Je kunt dan node2 verwijderen. Is dat niet de gewenste node, laat de variabele dan naar node2 verwijzen en herhaal de stap.

[CurlyMo]

SPee schreef op vrijdag 25 juni 2021 @ 14:49:
Wil je double linked list maken?

Nee, maar ik heb het idee dat dat voorwaardelijk is om dit te laten werken.

Dan zit je inderdaad op een unsafe stukje bij het toevoegen/verwijderen van een node.
Dat wordt soms opgelost door een locking mechanisme icm het aanroepen van een methode die de aanpassing doet. Of met een waarschuwing "not thread safe".

Locking wil ik niet en not thread safe ook niet. Anders had ik net zo goed geen CAS hoeven te gebruiken

Je houdt node1 in een variabele, controleert of node2 verwijderd moet worden, en als dat het geval is, dan werk je node1.head bij met de waarde node2.head. Je kunt dan node2 verwijderen. Is dat niet de gewenste node, laat de variabele dan naar node2 verwijzen en herhaal de stap.

Volgens mij loopt je hier het risico dat node1 op zichzelf alweer veranderd kan zijn op het moment dat je node2 verwijderd. Dat is volgens mij waarom je een double linked list nodig hebt, omdat je in node2 dé referentie wil bewaren naar node1.

[ThomasG]

CurlyMo schreef op vrijdag 25 juni 2021 @ 17:06:
[...]

Nee, maar ik heb het idee dat dat voorwaardelijk is om dit te laten werken.

Ja, en nee. Wat je ziet in Timothy L. Harris A Pragmatic Implementation of Non-blocking Linked-Lists is een double-ended list. Wat ik zie in jouw code voorbeeld een doubly-linked list. Daar ga je dus de fout in.

[CurlyMo]

ThomasG schreef op vrijdag 25 juni 2021 @ 19:12:
[...]
Ja, en nee. Wat je ziet in Timothy L. Harris A Pragmatic Implementation of Non-blocking Linked-Lists is een double-ended list. Wat ik zie in jouw code voorbeeld een doubly-linked list. Daar ga je dus de fout in.

Dat brengt me wel verder van het begrip van zijn oplossing

Hoe lost een double-ended list dat op?

[CurlyMo]

SPee schreef op vrijdag 25 juni 2021 @ 14:49:
Je houdt node1 in een variabele, controleert of node2 verwijderd moet worden, en als dat het geval is, dan werk je node1.head bij met de waarde node2.head. Je kunt dan node2 verwijderen. Is dat niet de gewenste node, laat de variabele dan naar node2 verwijzen en herhaal de stap.

Om even het probleem bij verwijdering te schetsen:

C:

void list_remove(struct ll *node) {
    struct ll *cpy = NULL;
    struct ll *tmp = container;
    while(tmp) {
        if(node == tmp) {
            if(cpy == NULL) {
                container = tmp->head;
            } else {
                cpy->head = tmp->head;
            }
            break;
        }
        cpy = tmp;
        tmp = tmp->head;
    }
}

Bij verwijdering zie je dat je moet checken of de te verwijderen node de eerste node uit de linked list is (regel #6). Dat soort condities schieten dus niet op in concurrent situaties.

---

Ow, wacht. Die double-ended list voegt een meta node toe aan het begin en aan het eind van de lijst, die niet bewerkt kunnen worden. Daardoor kom je nooit in bovenstaande situatie terecht dat je moet checken of dit het eerste element betreft. Nice.

[ Voor 12% gewijzigd door CurlyMo op 25-06-2021 22:38 ]

[CurlyMo]

Nieuwe versie die met die sentinal nodes inderdaad goed werkt (nog niet brute force getest):

C:

typedef struct lln {
    int i;
    int rm;
    struct lln *head;
} lln;

typedef struct ll {
    struct lln *head;
    struct lln *tail;
} ll;

struct ll list;

struct lln *list_add(int x) {
    struct lln *node = malloc(sizeof(struct lln));
    node->i = x;
    node->rm = 0;

    struct lln *cpy = list.tail->head;

    cpy = list.head->head;
    do {
        cpy = list.head->head;
        node->head = cpy;
    } while(!__sync_bool_compare_and_swap(&list.head->head, cpy, node));

    return node;
}

void list_remove(struct lln *node) {
    struct lln *cpy = list.tail->head;
    struct lln *tmp = list.head->head;

    while(tmp) {
        if(tmp == list.tail) {
            break;
        }
        if(node == tmp) {
            if(!__sync_bool_compare_and_swap(&cpy->head, tmp, tmp->head)) {
                    cpy = list.tail->head;
                    tmp = list.head->head;
                    continue;
            } else {
                    free(tmp);
                    break;
            }
        }
        cpy = tmp;
        tmp = tmp->head;
    }
}

void list_init(void) {
    list.head = malloc(sizeof(struct lln));
    list.tail = malloc(sizeof(struct lln));
    list.head->head = list.tail;
    list.tail->head = list.head;
}

Wat ik me dan nog afvraag is of de tweetrapsraket wel nodig is in een ongesorteerde linked list. In die situatie weet je namelijk altijd zeker dat je nieuwe node aan het begin van je lijst komt te staan en zit je dus niet te pielen met plaatsen van een nieuwe node tussen twee oude nodes, wat je bij een gesorteerde linked list mogelijk wel hebt.

[CurlyMo]

Ik loop nog steeds vast. Tijdens mijn brute force test komt het nog steeds voor dat een thread tmp probeert te lezen op regel 49 terwijl een andere thread tmp al vrijgegeven heeft op regel 44.

Probleem geschets in onderstaande output:

==6884==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000040898 at pc 0x563851e5fdbc bp 0x7f46ff7fee60 sp 0x7f46ff7fee50
WRITE of size 8 at 0x602000040898 thread T1
    #0 0x563851e5fdbb in list_remove /home/experiments/mempool/test.c:118
    #1 0x563851e6003f in thread1 /home/experiments/mempool/test.c:195
    #2 0x7f47026a87fb in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x77fb)
    #3 0x7f4702de0b5e in clone (/lib/x86_64-linux-gnu/libc.so.6+0x114b5e)

0x602000040898 is located 8 bytes inside of 16-byte region [0x602000040890,0x6020000408a0)
freed by thread T2 here:
    #0 0x7f470318a7b8 in __interceptor_free (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xde7b8)
    #1 0x563851e5fe38 in list_remove /home/experiments/mempool/test.c:123
    #2 0x563851e600b9 in thread2 /home/experiments/mempool/test.c:196
    #3 0x7f47026a87fb in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x77fb)

previously allocated by thread T2 here:
    #0 0x7f470318ab50 in __interceptor_malloc (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdeb50)
    #1 0x563851e5fb6e in list_add /home/experiments/mempool/test.c:95
    #2 0x563851e600a2 in thread2 /home/experiments/mempool/test.c:196
    #3 0x7f47026a87fb in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x77fb)

Thread T1 created by T0 here:
    #0 0x7f47030e3d2f in __interceptor_pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x37d2f)
    #1 0x563851e60389 in main /home/experiments/mempool/test.c:220
    #2 0x7f4702ced1c0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x211c0)

Thread T2 created by T0 here:
    #0 0x7f47030e3d2f in __interceptor_pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x37d2f)
    #1 0x563851e603aa in main /home/experiments/mempool/test.c:221
    #2 0x7f4702ced1c0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x211c0)

Ik tag aanvullend nog even @.oisyn @gomez12 @farlane @SymbolicFrank gezien jullie uitmuntende hulp in eerdere C topics van me

[.oisyn]

Ik snap nog steeds niet waarom je een tail en een head hebt. Voor een singly linked list heb je altijd alleen een head nodig. Daarnaast zit je nog met het ABA probleem. In de tijd nadat thread 1 de head node heeft uitgelezen om een node te verwijderen, kan thread 2 een node meerdere nodes verwijderen en weer toevoegen, op zo'n manier dat de head node pointer hetzelfde is maar de inhoud anders.

De gebruikelijke manier om dat op te lossen is door de CAS breder te maken dan alleen een pointer, en ook een int mee te nemen die je steeds ophoogt bij iedere wijziging. Als je garanties kunt geven over ongebruikte bits in de pointer zou je die evt ook kunnen gebruiken.

.edit: oh wacht je wil ook het verwijderen van een willekeurige node supporten, niet alleen de head. Dat is niet te doen zonder locking, omdat je op zoek moet naar de juiste node terwijl iemand anders misschien nodes loopt te verwijderen.

[ Voor 15% gewijzigd door .oisyn op 29-06-2021 08:55 ]

[CurlyMo]

.oisyn schreef op dinsdag 29 juni 2021 @ 08:46:
Ik snap nog steeds niet waarom je een tail en een head hebt.

De head en de tail zijn hier niet head's en tail's op node niveau, maar op list niveau. Oftewel, de twee sentinal nodes (waarvan ik het bestaan ook pas sinds Harris' artikel ken).

De gebruikelijke manier om dat op te lossen is door de CAS breder te maken dan alleen een pointer, en ook een int mee te nemen die je steeds ophoogt bij iedere wijziging. Als je garanties kunt geven over ongebruikte bits in de pointer zou je die evt ook kunnen gebruiken.

Bedoel je hier een reference counting mechanisme?

.edit: oh wacht je wil ook het verwijderen van een willekeurige node supporten, niet alleen de head. Dat is niet te doen zonder locking, omdat je op zoek moet naar de juiste node terwijl iemand anders misschien nodes loopt te verwijderen.

Volgens het artikel van Harris zou dat wel moeten kunnen Ik krijg het alleen niet werkend in een unordered list.

[.oisyn]

CurlyMo schreef op dinsdag 29 juni 2021 @ 09:34:
[...]

De head en de tail zijn hier niet head's en tail's op node niveau, maar op list niveau. Oftewel, de twee sentinal nodes (waarvan ik het bestaan ook pas sinds Harris' artikel ken).

Ja, en ik snap nog steeds niet waarom die nodig zijn

Bedoel je hier een reference counting mechanisme?

Nee, ik bedoel een manier om extra state mee te geven dan alleen het geheugenadres van een node.

Situatie 1: n1 -> n2 -> n3
Situatie 2: n1 -> n3

Node n2 is verwijderd. De persoon die head (node n1) wil verwijderen pakt de next pointer en maakt dat de nieuwe head, maar alleen als de head nog steeds gelijk is aan n1. De verandering van situatie 1 naar 2 is voor hem niet zichtbaar; hij pakt de next-pointer van n1, wat dan nog n2 is, en wijzigt head in n2 als head nog gelijk is aan n1.

Resultaat: n2 -> n3. Alleen was n2 al verwijderd.

Door een extra int bij te houden, die je steeds ophoogt bij elke mutatie, heb je extra state waar je dit mee voorkomt. De head is dan niet alleen een pointer, maar ook die int. Dus n1|1 in situatie 1, maar bijvoorbeeld n1|3 in situatie 2. De compare-and-swap faalt dan, want hoewel head nog steeds naar n1 wijst, is de int veranderd.

Volgens het artikel van Harris zou dat wel moeten kunnen

Ik zal het artikel eens doorlezen, maar je zit gewoon met een fundamenteel probleem: je bent door de lijst aan het lopen terwijl iemand mogelijk aan het muteren is.

[CurlyMo]

.oisyn schreef op dinsdag 29 juni 2021 @ 09:49:
[...]

Ja, en ik snap nog steeds niet waarom die nodig zijn

Dat kan ik je ondertussen wel uitleggen

C:

void list_remove(struct ll *node) {
    struct ll *cpy = NULL;
    struct ll *tmp = container;
    while(tmp) {
        if(node == tmp) {
            if(cpy == NULL) {
                container = tmp->head;
            } else {
                cpy->head = tmp->head;
            }
            break;
        }
        cpy = tmp;
        tmp = tmp->head;
    }
}

Op regel #6 moet ik checken of de node niet de start van de list is. Zo ja, dan moet ik de globale placeholder variable updaten (regel #7) i.p.v. de verbinding tussen nodes binnen de list (regel #9). Dat maakt een CAS verwijdering van node lastiger. Een sentinal node gaat daarvoor zitten waardoor ook de functionele start van je lijst wordt voorafgegaan door een daadwerkelijke node.

Nee, ik bedoel een manier om extra state mee te geven dan alleen het geheugenadres van een node.
[...]

Precies jouw uitleg hier komt ook terug in het artikel.

The reference contained in the next field of a node may be in one of two states: marked or unmarked. A node is marked if and only if its next field is marked. Marked references are distinct from normal references but still allow there referred-to node to be determined {for example they may be indicated by another wise-unused low-order bit in each reference. Intuitively a marked node is one which should be ignored because some process is deleting it. The function is_marked_reference(r) returns true if and only if r is a marked reference. Similarly get_marked_reference(r) and get_unmarked_reference(r) convert between marked and unmarked references.

Zij stellen dat als volgt voor:

C:

int is_marked_ref(long i) {
  return (int) (i & 0x1L);
}

long unset_mark(long i) {
  i &= ~0x1L;
  return i;
}

long set_mark(long i) {
  i |= 0x1L;
  return i;
}

long get_unmarked_ref(long w) {
  return w & ~0x1L;
}

long get_marked_ref(long w) {
  return w | 0x1L;
}

https://github.com/gpiska...c/linkedlist/linkedlist.c

[.oisyn]

Da's leuk, maar dat voorkomt nog steeds niet het ABA-probleem. Ik vind het tekenend dat dit hele probleem niet eens wordt genoemd in het paper. Als het niet voor kan komen moet je daar toch minstens iets over zeggen

[CurlyMo]

.oisyn schreef op dinsdag 29 juni 2021 @ 10:45:
Da's leuk, maar dat voorkomt nog steeds niet het ABA-probleem. Ik vind het tekenend dat dit hele probleem niet eens wordt genoemd in het paper. Als het niet voor kan komen moet je daar toch minstens iets over zeggen

Ik ken het ABA probleem. En dat is precies waar ik tegenaan loop. Hoe kan je het dan niet kennen

In het licht van jouw idee en wat ik lees in het artikel zou je de next pointer moeten markeren als de opvolgende node verwijderd wordt. Dan voorkom je dat je richting die te verwijderen node itereert. Op het moment dat alle verwijderde nodes zijn afgehandeld, dan komt de CAS langs die de gemarkeerde pointer vervangt door een pointer naar een node die niet verwijderd hoeft te worden en dus weer een valide pointer is.

[ThomasG]

Je bent nog steeds slechts een halve implementatie. Hoewel ze het een non-blocking linked list noemen is het stiekem een concurrent ordered set. De search functie bijvoorbeeld zie ik niet terug in jouw code, maar die heb wel nodig.

Daarnaast bestaat het ABA bestaat niet in het Harris' algoritme. Wanneer een node eenmaal gemarkeerd is als verwijderd, kan het nooit meer ongedaan gemaakt worden. In plaats daarvan wordt een nieuwe code gemaakt. Je ziet denk ik wel aankomen dat de nodes nergens daadwerkelijk verwijderd worden, dus zul je uiteindelijk uit het geheugen lopen. In de meeste implementaties zie je ook geen garbage collector om de gemarkeerde nodes te verwijderen, maar dat is wel nodig.

[CurlyMo]

ThomasG schreef op dinsdag 29 juni 2021 @ 11:00:
Je bent nog steeds slechts een halve implementatie. Hoewel ze het een non-blocking linked list noemen is het stiekem een concurrent ordered set. De search functie bijvoorbeeld zie ik niet terug in jouw code, maar die heb wel nodig.

Omdat de search functie er vanuit gaat dat je de node die hoort bij een value niet kent. Dat is hierbij niet zo. Daarbij heb ik het idee dat die search functie hoofdzakelijk nodig is voor het volgorderijke karakter van de lijst in het artikel van Harris.

[.oisyn]

ThomasG schreef op dinsdag 29 juni 2021 @ 11:00:
Je ziet denk ik wel aankomen dat de nodes nergens daadwerkelijk verwijderd worden, dus zul je uiteindelijk uit het geheugen lopen. In de meeste implementaties zie je ook geen garbage collector om de gemarkeerde nodes te verwijderen, maar dat is wel nodig.

Maar dat is dus wel het punt. Lekker makkelijk om om het ABA-probleem heen te werken door geheugenadressen nooit te hergebruiken

[CurlyMo]

.oisyn schreef op dinsdag 29 juni 2021 @ 11:13:
[...]


Maar dat is dus wel het punt. Lekker makkelijk om om het ABA-probleem heen te werken door geheugenadressen nooit te hergebruiken

Precies, zolang je niet daadwerkelijk vrijgeeft, dan gaat alles prima Ook in mijn implementaties.

[ThomasG]

CurlyMo schreef op dinsdag 29 juni 2021 @ 11:04:
[...]

Omdat de search functie er vanuit gaat dat je de node die hoort bij een value niet kent. Dat is hierbij niet zo. Daarbij heb ik het idee dat die search functie hoofdzakelijk nodig is voor het volgorderijke karakter van de lijst in het artikel van Harris.

Harris implementatie is een ordered set. De head en tail bevatten de laagst en hoogte mogelijke values, en functioneren als markers. Alle inserts gaan op volgorde daartussen, en omdat het een set is heeft het alleen unieke values.

Wat het verwijderen doet is de node markeren als verwijderd, en probeert de node er tussen uit te halen. Het er tussen uit halen kan op dat moment mislukken, bijvoorbeeld als er een andere node in tussentijd wordt tussen de verwijderde en de linker en/of rechter node. Dat wordt niet opgelost door de remove functie, maar door de search functie die dat bij de volgende remove, insert, contains, e.d. call oplost.

Het geheel werkt door het toepassen van trucjes, en alleen als je ze allemaal toepast.

[CurlyMo]

ThomasG schreef op dinsdag 29 juni 2021 @ 12:25:
[...]
Harris implementatie is een ordered set. De head en tail bevatten de laagst en hoogte mogelijke values, en functioneren als markers. Alle inserts gaan op volgorde daartussen, en omdat het een set is heeft het alleen unieke values.

Zoals ik het begrijp maken sentinal nodes van een linked list een soort oneindig grote ringbuffer. De tail node verwijst altijd terug naar de head node. Die hoeven daarbij niet een virtueel geordende max en min waarde te representeren. Dat ze dat doen in een gesorteerde lijst is evident, maar volgens mij niet voorwaardelijk in een ongesorteerde lijst. Je doorbreekt echter de ringbuffer door telkens af te kappen op de tail node.

Wat het verwijderen doet is de node markeren als verwijderd, en probeert de node er tussen uit te halen. Het er tussen uit halen kan op dat moment mislukken, bijvoorbeeld als er een andere node in tussentijd wordt tussen de verwijderde en de linker en/of rechter node. Dat wordt niet opgelost door de remove functie, maar door de search functie die dat bij de volgende remove, insert, contains, e.d. call oplost.

True, met het verschil dat het bij een gesorteerde lijst wel degelijk uitmaakt dat je de juiste node zoekt in je lijst en het ook uitmaakt waar je je nieuwe node plaatst. Bij een ongesorteerde lijst boeit dat niet. Daarom denk ik dat je bij een ongesorteerde lijst prima die logica enkel in je verwijder functie kan zetten. Ook omdat ik de pointer al bezit. Die hoeft niet opnieuw vanuit de waarde gevonden te worden.

Het geheel werkt door het toepassen van trucjes, en alleen als je ze allemaal toepast.

[.oisyn]

CurlyMo schreef op dinsdag 29 juni 2021 @ 13:37:
[...]

Zoals ik het begrijp maken sentinal nodes van een linked list een soort oneindig grote ringbuffer.

Nee, het feit dat tail->next naar head wijst is gewoon een quirk in jouw implementatie . Ik zie nog steeds de noodzaak van een tail node niet. In de code in het artikel wordt de tail effectief ook nooit gedereferenced. Het kan dus net zo goed nullptr of een andere speciale waarde zijn.

[CurlyMo]

.oisyn schreef op dinsdag 29 juni 2021 @ 14:06:
[...]

Nee, het feit dat tail->next naar head wijst is gewoon een quirk in jouw implementatie . Ik zie nog steeds de noodzaak van een tail node niet. In de code in het artikel wordt de tail effectief ook nooit gedereferenced. Het kan dus net zo goed nullptr of een andere speciale waarde zijn.

Effectief maakt het niks uit

Ik denk dat je gelijk hebt, maar ik probeer op delen toch het artikel te volgen.

[.oisyn]

CurlyMo schreef op dinsdag 29 juni 2021 @ 14:08:
Ik denk dat je gelijk hebt, maar ik probeer op delen toch het artikel te volgen.

Dat is op zich prima, maar in het aritkel wijst tail->next ook niet naar head

[ThomasG]

.oisyn schreef op dinsdag 29 juni 2021 @ 14:06:
[...]

Nee, het feit dat tail->next naar head wijst is gewoon een quirk in jouw implementatie . Ik zie nog steeds de noodzaak van een tail node niet. In de code in het artikel wordt de tail effectief ook nooit gedereferenced. Het kan dus net zo goed nullptr of een andere speciale waarde zijn.

Het maakt wel uit. In de paper is het goed te zien, omdat het een template is. Bij implementaties in C waarbij het type van de key een integer is wel. Want dan is de head node een INT_MIN, en de tail node een INT_MAX. Vergeet niet: het is effectief een ordered set, de search en insert sorteren immers en doen niets bij duplicatie keys. Het maakt dan niet uit of de lijst leeg is, of dat je aan het begin of eind een insert of delete doet. Dezelfde logica werkt altijd. En je hebt nooit een node waarbij de next node een null-pointer is, behalve bij de tail node. Maar dat is geen probleem, want tail->next wordt nooit aangeroepen.

Daarbij blijf je het probleem van memory-management houden. Het is in non-managed talen lastig om de verwijderde nodes daadwerkelijk op te ruimen. En in managed talen is het lastig omdat je niet direct bij het geheugen kan komen om de nodes te markeren, en de garbage collector weer een performance bottleneck is. Vrijwel alle implementaties van Timothy L. Harris A Pragmatic Implementation of Non-blocking Linked-Lists zijn zonder memory management, en dat zie je ook terug in veel van de benchmarks. Die lopen totdat het geheugen vol raakt.

[.oisyn]

ThomasG schreef op dinsdag 29 juni 2021 @ 14:27:
[...]
Het maakt wel uit. In de paper is het goed te zien, omdat het een template is. Bij implementaties in C waarbij het type van de key een integer is wel.

Gekke formulering, bedoel je dat het in het paper niet goed te zien is?

Juist in het paper wordt noch de waarde van de head node als van de tail node uitgelezen. De search begint bij head->next, en wordt afgekapt zodra men de tail node tegenkomt.

Ook het gebruik van INT_MIN en INT_MAX zou impliceren dat die waardes ongeldig zijn voor je set.

Het is in non-managed talen lastig om de verwijderde nodes daadwerkelijk op te ruimen

Vooral omdat er nog allerhande threads gebruik van kunnen maken. Ik vind het een enorme cop-out, hoor.

[ Voor 21% gewijzigd door .oisyn op 29-06-2021 14:52 ]

[CurlyMo]

Volgens mij is het inderdaad zo dat de bestaande artikelen allemaal uitgaan van talen met een garbage collector.

Na heel veel meer leeswerk ben ik tot de conclusie gekomen dat een daadwerkelijke lock-free linked list gewoon niet bestaat of mogelijk is.

Dus dan maar de concurrent doubly linked list. Maar die krijg ik ook niet werkend

C:

typedef struct lln {
    int i;
    pthread_mutex_t lock;
    struct lln *next;
    struct lln *prev;
} lln;

struct lln *head = NULL;

struct lln *list_add(int x) {
    struct lln *node = malloc(sizeof(struct lln));

    pthread_mutex_init(&node->lock, NULL);

    node->i = x;
    node->prev = NULL;
    node->next = NULL;

    if(head != NULL) {
        struct lln *cpy = head;
        pthread_mutex_lock(&cpy->lock);
        head->prev = node;
        node->next = head;
        head = node;
        pthread_mutex_unlock(&cpy->lock);
    } else {
        node->next = head;
        head = node;
    }
    return node;
}


void list_remove(struct lln *node) {
    pthread_mutex_lock(&node->lock);
    if(node->prev == NULL && node->next == NULL) {
        head = NULL;
    } else if(node->prev == NULL) {
        pthread_mutex_lock(&node->next->lock);

        head = node->next;

        pthread_mutex_unlock(&node->next->lock);
    } else if(node->next == NULL) {     
        pthread_mutex_lock(&node->prev->lock);

        node->prev->next = NULL;
        
        pthread_mutex_unlock(&node->prev->lock);
    } else {
        pthread_mutex_lock(&node->prev->lock);
        pthread_mutex_lock(&node->next->lock);
        
        node->prev->next = node->next;
        node->next->prev = node->prev;
        
        pthread_mutex_unlock(&node->next->lock);
        pthread_mutex_unlock(&node->prev->lock);
    }
    pthread_mutex_unlock(&node->lock);
    pthread_mutex_destroy(&node->lock);
    free(node);
}

==10803==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000038 (pc 0x55e568347dc9 bp 0x7fc4a92fee90 sp 0x7fc4a92fee70 T1)
==10803==The signal is caused by a WRITE memory access.
==10803==Hint: address points to the zero page.
    #0 0x55e568347dc8 in list_add /home/source/experiments/mempool/test.c:100
    #1 0x55e56834826d in thread1 /home/source/experiments/mempool/test.c:143
    #2 0x7fc4ac9567fb in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x77fb)
    #3 0x7fc4ac683b5e in clone (/lib/x86_64-linux-gnu/libc.so.6+0x114b5e)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /home/source/experiments/mempool/test.c:100 in list_add
Thread T1 created by T0 here:
    #0 0x7fc4acba5d2f in __interceptor_pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x37d2f)
    #1 0x55e5683485c9 in main /home/source/experiments/mempool/test.c:185
    #2 0x7fc4ac5901c0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x211c0)

Regel #100 is in deze post regel #22

[CurlyMo]

Uiteindelijk toch opgelost op deze manier

Toch niet, geef me nog even een momentje.

[ Voor 92% gewijzigd door CurlyMo op 02-07-2021 23:35 ]