Hi, everyone. This is my first post to the linux-kernel list.
I am the author of a lock-free data structure library, liblfds, which has now my first attempt at a port to the Linux kernel, which is to say, I have a Kbuild file which produces a static library. I'm posting as I thought it might be of some interest. Please forgive me if not! The library performs no memory allocation, has no OS or standard library dependencies, compiles on a bare C89 compiler, where the Linux kernel port is dependent on GCC 4.1.2 or greater, and so supports every processor GCC provides atomic intrinsics for. Documentation is exhaustive (a wiki page per function, enum, struct, etc, etc). The benchmark programme compares liblfds against locking mechanisms for the same benchmarks, and produce eyecand^Hgnuplots. http://liblfds.org/pages/images/liblfds710_btree_au_readn_then_writen_numa_Core%20i5%20%28x64%29.1200x1800.png The set of data structures is quite limited. There's a couple of little add-only data structures (btree, list, hash) and the a freelist/stack, couple of queues and a ringbuffer. It is however surprising how often add-only data structures are still perfectly viable. There's a lock-free, delete supporting red-black tree in the literature, which looms large now in my mind. The library can be found here; http://www.liblfds.org Release 7.1.0 was published about thirty minutes ago :-)
