c - Synchronizing access to a doubly-linked list -

i'm trying implement (special kind of) doubly-linked list in c, in pthreads environment using c-wrapped synchronization instructions atomic cas, etc. rather pthread primitives. (the elements of list fixed-size chunks of memory , surely cannot fit pthread_mutex_t etc. inside them.) don't need full arbitrary doubly-linked list methods, only:

• insertion @ end of list
• deletion beginning of list
• deletion @ arbitrary points in list based on pointer member removed, obtained source other traversing list.

so perhaps better way describe data structure queue/fifo possibility of removing items mid-queue.

is there standard approach synchronizing this? i'm getting stuck on possible deadlock issues, of inherent algorithms involved , others of might stem fact i'm trying work in confined space other constraints on can do.

edit: in particular, i'm stuck on if adjacent objects removed simultaneously. presumably when removing object, need obtain locks on both previous , next objects in list , update next/prev pointers point 1 another. if either neighbor locked, result in deadlock. i've tried work out way any/all of removals taking place walk locked part of list , determine maximal sublist that's in process of removal, lock nodes adjacent sublist whole sublist gets removed whole, head starting hurt.. :-p

conclusion(?): follow up, have code want working, i'm interested in theoretical problem. everyone's answers have been quite helpful, , combined details of constraints outside expressed here (you really don't want know pointer-to-element-to-be-removed came , synchronization involved there!) i've decided abandon local-lock code , focus on:

• using larger number of smaller lists each have individual locks.
• minimizing number of instructions on locks held , poking @ memory (in safe way) prior acquiring lock reduce possibility of page faults , cache misses while lock held.
• measuring contention under artificially-high load , evaluating whether approach satisfactory.

thanks again gave answers. if experiment doesn't go might come approaches outlined (especially vlad's) , try again.

why not apply coarse-grained lock? lock whole queue.

a more elaborate (however not more efficient, depends on usage pattern) solution using read-wrote lock, reading , writing, respectively.

---

using lock-free operations seem me not idea case. imagine thread traversing queue, , @ same moment "current" item deleted. doesn't matter how many additional links traverse algorithm holds, items may deleted, code have no chance finish traversal.

---

another issue compare-and-swap pointers never know whether points same old structure, or old structure has been freed , new structure allocated @ same address. may or may not issue algorithms.

---

for case of "local" locking (i.e., possibility lock each list item separately), idea make locks ordered. ordering locks ensures impossibility of deadlock. operations that:

delete pointer p previous item:

1. lock p, check (using perhaps special flag in item) item still in list
2. lock p->next, check it's not 0 , in list; way ensure p->next->next won't removed in meantime
3. lock p->next->next
4. set flag in p->next indicating it's not in list
5. (p->next->next->prev, p->next->prev) = (p, null); (p->next, p->next->next) = (p->next->next, null)
6. release locks

insert beginning:

1. lock head
2. set flag in new item indicating it's in list
3. lock new item
4. lock head->next
5. (head->next->prev, new->prev) = (new, head); (new->next, head) = (head, new)
6. release locks

this seems correct, didn't try idea.

essentially, makes double-linked list work if single-linked list.

---

if don't have pointer previous list element (which of course case, it's virtually impossible keep such pointer in consistent state), can following:

delete pointer c item deleted:

1. lock c, check if still part of list (this has flag in list item), if not, operation fails
2. obtain pointer p = c->prev
3. unlock c (now, c may moved or deleted other thread, p may moved or deleted list well) [in order avoid deallocation of c, need have shared pointer or @ least kind of refcounting list items here]
4. lock p
5. check if p part of list (it deleted after step 3); if not, unlock p , restart beginning
6. check if p->next equals c, if not, unlock p , restart beginning [here can maybe optimize out restart, not sure atm]
7. lock p->next; here can sure p->next==c , not deleted, because deletion of c have required locking of p
8. lock p->next->next; locks taken, can proceed
9. set flag c not part of list
10. perform customary (p->next, c->next, c->prev, c->next->prev) = (c->next, null, null, p)
11. release locks

note having pointer list item cannot ensure item not deallocated, you'll need have kind of refcounting, item not destroyed @ moment try lock it.

---

note in last algorithm number of retries bounded. indeed, new items cannot appear on left of c (insertion @ rightmost position). if our step 5 fails , need retry, can caused having p removed list in meanwhile. such removal can occur not more n-1 times, n initial position of c in list. of course, worst case rather unlikely happen.