Lock-free algorithm library

Question

Is there a library that implements lock-free algorithms(queue, linked list and others) written in C (not in C++)? I've taken a look at some libraries like Intel's, but I would like to use generic libraries, at least more generic than Intel's one.

Unexpected

Queue, linked list and others are not algorithms. They are data structures – Width

But the methods for manipulating them in a lock-free manner are algorithms, and such algorithms are even an active area of research, if I'm not mistaken. (Albeit probably a misguided one...) – Mac

Note linked lists are a step above queues. A queue can be written without SMR. A linked list almost cannot (I think it can be done - I came up with a theoretical design - but it's awkward and of course since it's not SMR, it's using a free-list behind the scenes for store). – Underact

Answer 1

See Practical lock-free data structures from the University of Cambridge

Stomatitis

sounds really cool. has someone got experience with this library? – Mousey

Well, it implements Multiple-Word-CAS and Software Transactional Memory, both of which are software constructs, and somewhat less that practical (read: slow). Then those are used to implement Binary Search Trees, Red-Black-Trees and Skip-Lists. It is understandable that this was done for the trees, as there is no known single-word-CAS lock-free balanced tree data-structure. The Skip-List does also have a single-CAS implementation. There are no queue, stack, or normal linked-lists, or hash-tables. – Radiolarian

If the skip-list is single CAS, how do they handle ABA? – Underact

I found the code for this library impenetrable. There's also no documentation. It's not production-use ready. It's barely readable-ready :-) – Underact

At a quick glance, it seems they have a full gargabe collector that handles memory reclamation for the CAS skip list at least, coupled with some marking here and there (I just quickly flew over the code). Of course a full GC solves memory reclamation, and once that is solved, ABA disappears (any complete solution to the memory reclamation problem, such as SMR, RCU, whatever, also solves ABA, iirc there's a proof of that somewhere, but it's trivial to reason out yourself). – Radiolarian

Answer 2

I've written my own, Rig, currently queue, stack and list are there, hash-table will soon follow. While I'm still working on it, it is intended for public consumption, and the API is mostly stable, just use the SVN trunk. :)

The only other such library in C that I know of is liblfds, though I've never used it.

Radiolarian

How do you handle unlinking from the list? are you using a delete bit? if so, how are you handling SMR? (also, what license are you using?) – Underact

Yeah, the list uses a delete bit, and memory is then recycled using Michael Maged's SMR algorithm. The code is BSD licensed, I just used the most open/permissive license I could find. :) – Radiolarian

Mmm - the delete bit - I emailed Tim, he did that work at Sun, I suspect it's patented and the patent is owned by Sun (now Oracle). Maged's SMR - that's hazard pointers, isn't it? that IS patented. I'm afraid the BSD license you've chosen can't apply to these techniques. If it helps, RCU is available under LGPL (I've taken this route). – Underact

A few points: 1) the license under which I release my own code, or of other libraries, has nothing at all to do with possible patents upon techniques implemented by said code 2) Fun, US software patents, relevance to me and to the world: ~ zero ;) 3) I'm not even sure those patents exists, and if they do, if they have any relevance: using the unused bits of a ptr to store information is a widely used technique in many contexts, and there sure is prior-art than Harris' 2001 paper. SMR is also a kinda specialized GC (the paper itself says so), and IBM is behind it, they're open-source friendly. – Radiolarian

I may be wrong, but I think you are incorrect. If someone holds a patent on a technique, no one else can with permission use that technique. It is not meaningful to license a use of a patented technique when permission has not been granted; the patent holder can block use. – Underact

Those patents may have been taken out in the EU, at least, since the holding companies are large multi-nationals (IBM, Sun, Oracle). There is a patent for hazard pointers - a quick search on Google will find it. I don't know if there is a patent for the delete bit - I've not looked; but it is common for companies to patent the techniques in white papers prior to publishing those papers. – Underact

The problem with all this is not that you are particularly wrong or right, but that you are not informing users of your library. Arguing 'it's not a problem so it doesn't need to be mentioned' given the list of assumptions and caveats here (such as - you can't use this library in the USA) is properly tantamount to deception. As such, users may be mis-leading, or mis-informed, or under-informed, such that they use the library in a project, investing time and effort, but then come to a point where they realise that for legal issues they must undo that work. – Underact

Moreover, I have to say, I find your view that it's fine to ignore US patents unpleasent. You are only implimenting those algorithms because someone else invented them - you are reading their work, their white paper. The investor (rightfully) claims ownership, a claim you dismiss on the basis that you can! if you had independently invented the content, I would have a completely different view, but you did not. – Underact

IANAL, but IMHO a license is specific to the code, and defines its usage and limitations, patents are something slightly different. The EU doesn't recognize software patents to the level the US do, so just because a big company files them, wouldn't mean they get accepted. For SMR I only found a patent application. Personally, you are the first open-source developer I encounter specifically worrying to such extent about this, I absolutely did not want to deceive anyone (and I kinda resent that accusation), simply for me, in my cultural/social environment, we don't care about any of this. – Radiolarian

I also do not dismiss such possible claims just because I can, I did briefly think about it, and came to the conclusion that the delete-bit (using unused ptr bits for information) is clearly invalid by prior-art (see Wikipedia Tagged_pointer and LISP machines, this was done in the 90's already), and I'm not even sure the patent exists at all. For SMR there is a patent application, which is not a patent, and even then, it would not simply stop any usage of it, until properly proven in court to even hold up, see all the Apple, IBM, HTC, ... mud-fights and all the total nonsense patents. – Radiolarian

This is starting to get long, I'll post a summary of this on my blog and we can continue discussion there, I am kinda interested in this, and do like to debate issues like those. :) Still, I'm unsure about any open-source library being able to guarantee patent-freedom, can you prove to me glibc, kde, gnome are fully patent free? Even the big ones aren't sure what they own is really really ok (ie. Google with VP8). – Radiolarian

links are dead. – Feral

Answer 3

liblfds

http://www.liblfds.org

Wiki with full API documentation, forum for questions, blog for reading the author rattle on :-)

Platform independent. Out of the box for Windows, Linux, Intel and ARM.

Release 7 should be out in a month or two. Will add run-time cache line alignment, backoff and SMR. (SMR also gives a ton of the other CPU types - basically, anything GCC compiles on which supports atomic ops, e.g. SPARC, MIPS, IA64, etc).

Also, there's no license - you can use the code however you want. Make money! It's not GPL.

Underact

Answer 4

I'm currently writing a lock-free lib but it's C++. Here's an STL-like Lock-Free Doubly-Linked List.

The memory manager it uses is quite powerful (32-bit CAS without ABA issues) so I'm using it to create a complete set of containers: a lock-free map/set (using skip lists), a lock-free bag (instead of queue/stack), and a lock-free unordered map (hash table using split-ordered lists).

For more info about the doubly-linked list check out my answer to a related question.

Harbard

I had a look at the memory manager. It seems to be using hazard pointers? see previous discussion about this technique being patented. RCU is available under LGPL. – Underact

The memory manager is a modified LFRM, which combines reference counting with hazard pointers. The author released an implementation of LFRM under the GPL several years ago, and I've seen other libraries with straight-up SMR released under liberal licenses despite the hazard patent. – Harbard

True, the patent situation is unclear at best here, Hazard Pointers actually have no patent, just a patent application. I've followed up on all of this on my blog chtekk.longitekk.com/index.php?/archives/… and wrote down my thoughts. Again, licenses and patents are not the same thing, connected, but to what extent and depending on whom is based upon the wording of the license. Fun stuff. ;) – Radiolarian

If approved, the patent won't be valid in my country anyway. I'll take the "I'll cross that bridge when I get there" approach to this one. – Harbard

The problem is, there are catagories of users who cannot use code with such licensing risks. (Although also commerical users are largely eliminated by GPL anyway). – Underact

It's just the author's LFMR (aka. "Beware & Cleanup") implementation in Ada that is GPL. The algorithm as described in his paper is not directly covered under any patent which is what I derived my implementation from, so my implementation is under a license of my own choosing, the Boost license. – Harbard

@Kometes: the author can say whatever he likes about what license he's using. If the algorithm is patented, his license is meaningless because the patent holder can force users to stop using the code. The fact you, the original author, or anyone at all chooses GPL, or Boost or whatever you like makes no difference at all. If the algorithm is patented, it is not yours to license. – Underact

Yes, I was just clarifying that my implementation is not derived from copyrighted GPL'd code. As to risk of litigation on any patent infringement, interested companies distributing to the US can have their patent lawyers make that call. – Harbard