lock-free data structure library ported to Linux kernel

lock-free data structure library ported to Linux kernel

[admin]

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 :-)

Re: lock-free data structure library ported to Linux kernel

[Jonathan Corbet]

On Tue, 31 May 2016 12:07:13 +0300
admin <admin@liblfds.org> wrote:

> 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!

So if you want to get people to take a look at this, I would suggest
posting it as a patch set, and, crucially, adding uses within the kernel
and showing how that makes the kernel better.

Thanks,

jon