Hacker News new | past | comments | ask | show | jobs | submit login

I'm not sure how to build a lock-less doubly-linked list in C, honestly, and it may not be possible. I've authored several lock-less data structures in C, but I've not thought about this one... A singly-linked list is easy-peasy for addition at the head or tail (just atomic reads and atomic compare-and-swap), though deletion is tricky (because the obvious CAS thing to do is racy if you'd free the deleted element, and you do want to free it eventually...).

A good pattern for thread-safety is to use immutable data structures. jq's jv API [0] is a great example of how to make it easy to deal with immutable data structures. Of course, you don't get to have cycles this way and so you don't get to have doubly-linked lists. Also, for root state you kinda need something like a thread-safe variable (of which there are a number of flavors in Clojure, Haskell, and others) where when you read it you're guaranteed to have a stable reference to the value, but also guaranteed that garbage will be collected -- this is great when the values are immutable data structures.

You could have cycles in immutable data structures if you install the cycle before ever sharing with other threads and can make sure you don't fall into a loop when releasing the immutable value. But this is the sort of thing that requires "unsafe mode" unless the compiler/runtime can figure out that a) you haven't shared the thing yet, b) it won't be mutated once shared. I don't know how to figure that out statically, but that might be a good avenue for research.

[0] https://github.com/stedolan/jq/wiki/C-API:-jv




Some CPUs have a 128-bit compare-and-swap (lock cmpxchg16b on x64). You can build a lockless doubly-linked list with that. See for example https://gist.github.com/glampert/c40f2584d2fbc72316e1c8a6ef1...

As to the doubly-linked list in Rust: I think one could add the notions of “allocated block that must have n references to it” and accompanying “one of n references to an allocated block”. That could lead, for example, to code

   let p1, p2 = heap::allocate2(elem_size, align);
to allocate such a block with two references. The borrow tracker could then ensure that both p1 and p2 get stored once somewhere before the function allocating the memory returns or get returned from the function, or that both get passed to a function freeing the memory, and never used afterwards.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: