Synchronizing access to a doubly-linked list

Question

I'm trying to implement a (special kind of) doubly-linked list in C, in a pthreads environment but using only C-wrapped synchronization instructions like atomic CAS, etc. rather than pthread primitives. (The elements of the list are fixed-size chunks of memory and almost surely cannot fit pthread_mutex_t etc. inside them.) I don't actually need full arbitrary doubly-linked list methods, only:

• insertion at the end of the list
• deletion from the beginning of the list
• deletion at arbitrary points in the list based on a pointer to the member to be removed, which was obtained from a source other than by traversing the list.

So perhaps a better way to describe this data structure would be a queue/fifo with the possibility of removing items mid-queue.

Is there a standard approach to synchronizing this? I'm getting stuck on possible deadlock issues, some of which are probably inherent to the algorithms involved and others of which might stem from the fact that I'm trying to work in a confined space with other constraints on what I can do.

Edit: In particular, I'm stuck on what to do if adjacent objects are to be removed simultaneously. Presumably when removing an object, you need to obtain locks on both the previous and next objects in the list and update their next/prev pointers to point to one another. But if either neighbor is already locked, this would result in a deadlock. I've tried to work out a way that any/all of the removals taking place could walk the locked part of the list and determine the maximal sublist that's currently in the process of removal, then lock the nodes adjacent to that sublist so that the whole sublist gets removed as a whole, but my head is starting to hurt.. :-P

Conclusion(?): To follow up, I do have some code I want to get working, but I'm also interested in the theoretical problem. Everyone's answers have been quite helpful, and combined with details of the constraints outside what I expressed here (you really don't want to know where the pointer-to-element-to-be-removed came from and the synchronization involved there!) I've decided to abandon the local-lock code for now and focus on:

• using a larger number of smaller lists which each have individual locks.
• minimizing the number of instructions over which locks are held and poking at memory (in a safe way) prior to acquiring a lock to reduce the possibility of page faults and cache misses while a lock is held.
• measuring the contention under artificially-high load and evaluating whether this approach is satisfactory.

Thanks again to everybody who gave answers. If my experiment doesn't go well I might come back to the approaches outlined (especially Vlad's) and try again.

Answer 1

Why not just apply a coarse-grained lock? Just lock the whole queue.

A more elaborate (however not necessarily more efficient, depends on your usage pattern) solution would be using a read-wrote lock, for reading and writing, respectively.

---

Using lock-free operations seem to me not a very good idea for your case. Imagine that some thread is traversing your queue, and at the same moment the "current" item is deleted. Doesn't matter how many additional links your traverse algorithm holds, all that items may be deleted, so your code would have no chance to finish the traversal.

---

Another issue with compare-and-swap is that with pointers you never know whether it really points to the same old structure, or the old structure has been freed and some new structure is allocated at the same address. This may or may not be an issue for your algorithms.

---

For the case of "local" locking (i.e., the possibility to lock each list item separately), An idea would be to make the locks ordered. Ordering the locks ensures the impossibility of a deadlock. So your operations are like that:

Delete by the pointer p to the previous item:

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

Insert into the beginning:

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

This seems to be correct, I didn't however try this idea.

Essentially, this makes the double-linked list work as if it were a single-linked list.

---

If you don't have the pointer to the previous list element (which is of course usually the case, as it's virtually impossible to keep such a pointer in consistent state), you can do the following:

Delete by the pointer c to the item to be deleted:

1. lock c, check if it is still a part of the list (this has to be a flag in the list item), if not, operation fails
2. obtain pointer p = c->prev
3. unlock c (now, c may be moved or deleted by other thread, p may be moved or deleted from the list as well) [in order to avoid the deallocation of c, you need to have something like shared pointer or at least a kind of refcounting for list items here]
4. lock p
5. check if p is a part of the list (it could be deleted after step 3); if not, unlock p and restart from the beginning
6. check if p->next equals c, if not, unlock p and restart from the beginning [here we can maybe optimize out the restart, not sure ATM]
7. lock p->next; here you can be sure that p->next==c and is not deleted, because the deletion of c would have required locking of p
8. lock p->next->next; now all the locks are taken, so we can proceed
9. set the flag that c is not a part of the list
10. perform the customary (p->next, c->next, c->prev, c->next->prev) = (c->next, null, null, p)
11. release all the locks

Note that just having a pointer to some list item cannot ensure that the item is not deallocated, so you'll need to have a kind of refcounting, so that the item is not destroyed at the very moment you try to lock it.

---

Note that in the last algorithm the number of retries is bounded. Indeed, new items cannot appear on the left of c (insertion is at the rightmost position). If our step 5 fails and thus we need a retry, this can be caused only by having p removed from the list in the meanwhile. Such a removal can occur not more than N-1 times, where N is the initial position of c in the list. Of course, this worst case is rather unlikely to happen.