lock-free data structure library ported to Linux kernel

From: admin
Date: Tue May 31 2016 - 05:13:59 EST

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.


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;


Release 7.1.0 was published about thirty minutes ago :-)