linux-kernel - lock-free data structure library ported to Linux kernel

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <574D5441.6060709@liblfds.org>
Date:	Tue, 31 May 2016 12:07:13 +0300
From:	admin <admin@...lfds.org>
To:	linux-kernel <linux-kernel@...r.kernel.org>
Subject: lock-free data structure library ported to Linux kernel

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