overview

Welcome to liblfds, a portable, license-free, lock-free data structure library written in C.

Lock-free data structures are process, thread and interrupt safe (i.e. the same data structure instance can be safely used concurrently and simultaneously across cores, processes, threads and both inside and outside of interrupt handlers), never sleep (and so are safe for kernel use when sleeping is not permitted), operate without context switches, cannot fail (no need to handle error cases, as there are none), perform and scale literally orders of magnitude better than locking data structures, and liblfds itself (as of release 7.0.0) is implemented such that it performs no allocations (and so works with NUMA, stack, heap and shared memory) and compiles not just on a freestanding C89 implementation, but on a bare C89 implementation.

The library is completely documented (every API, function, macro, struct, define, typedef and enum) and ships with a complete test suite and a partial benchmark suite.

Current users include AT&T, Red Hat and Xen.

resources

Home Blog Forum Mailing Lists Documentation Local Git GitHub Contact

license

You are free to use this library in any way. Go forth and create wealth!

If for legal reasons a custom licence is required, the license of your choice will be granted, and license is hereby granted up front for a range of popular licenses : the MIT license, the BSD license, the Apache license, the GPL and LPGL (all versions thereof) and the Creative Commons licenses (all of them). Additionally, everything is also placed in the public domain.

data structures, processors and out-of-the-box toolchain support

The following matrix details out-of-the-box support, i.e. toolchains for which build files ship with the library and for those toolchains, which processors have been ported to. For other processors, the porting abstraction layer provides an easy-to-implement mechanism for adding support. For other toolchains you will need to provide your own build files.

Release 7.1.1
GCC and gnumake GCC, gnumake and kbuild1 Microsoft C compiler and gnumake WDK 7.12
Alpha, IA64, MIPS64,
POWERPC32/64,
SPARC32/64
MIPS32 ARM64 x86 ARM32, x64 Alpha, IA64, MIPS32/64,
POWERPC32/64,
SPARC32/64
ARM64 ARM32, x86 x64 x64 x86 IA64 x64, x86
Binary Tree (add-only, unbalanced)
Freelist
Hash (add-only)
List (add-only, singly-linked, ordered)
List (add-only, singly-linked, unordered)
PRNG
Queue (bounded, many producer, many consumer)
Queue (bounded, single producer, single consumer)
Queue (unbounded, many producer, many consumer)
Ringbuffer
Stack

1. This is the Linux kernel toolchain
2. This is a Windows kernel toolchain

Key
supported, compiled and tested
supported and compiled but not tested (test ought to pass, but it hasn't been run, so it won't)
supported but not compiled or tested (so it ought to compile, but it hasn't been done, so it won't)
not (yet) supported (never compiled, and expected not to compile successfully)
cannot be implemented on this platform
GCC GCC >= 4.1.2 and GNUmake >= 3.8.1
Microsoft C compiler Development uses Microsoft Windows SDK 7.1, but MSVC 2008 or later should be fine, and GNUmake 3.8.1
WDK 7.1 Windows Driver Kit 7.1.0

benchmarking

btree (add-only, unbalanced)
ARM32 MIPS32 x64 Penny Arcade
Raspberry Pi 2 Model B Ci20 AWS dedicated VM Core i5 Bar

freelist
ARM32 x64
Raspberry Pi 2 Model B AWS dedicated VM Core i5

queue (unbounded, many producer, many consumer)
ARM32 x64
Raspberry Pi 2 Model B AWS dedicated VM Core i5

downloads

date release source md5sum release note comment
25 Sep 09 1 zip
tar.bz2
726a344141ed486260e73d2e4cd2f822
e6573df1e2b4cb8818de826f4440858b
here Deprecated.
05 Oct 09 2 zip
tar.bz2
7afc44da5e1d9fba45d34e2063cadb76
5afc460fb47ae206415c127bb72cd4c1
here Deprecated.
25 Oct 09 3 zip
tar.bz2
c5452a275e1c359b3e97bc281e3c3d8d
e1cfbea18a28949ee17d5c1b84ed34d0
here Deprecated.
07 Dec 09 4 zip
tar.bz2
7be3eec9834be7f6603f0bb03490546a
b11527ebaa25096dbccb380ab4d39004
here Deprecated.
19 Dec 09 5 zip
tar.bz2
5329a3348abd8d7b8d7cb44f796de393
dd1df6553b54ad3e342e545ce7b6f306
here Deprecated.
29 Dec 09 6 zip
tar.bz2
1bbb808f56082c7206efe2c9f3a36e47
cc9e07e8a7b972eb9fe4bbeb5db6eb7b
here Deprecated.
18 Dec 12 6.0.0 zip
tar.bz2
github
6eef0b2c8b56579d428a5d0d6d1d3bf5
a782de14d10a1d61c0423086f09107d9
here Wholly identical to 6, except all public entities are prefixed with "lfds600_".
This release is a stepping-stone from 6 into per-version 'namespaces'.
31 Dec 12 6.1.0 zip
tar.bz2
github
983d9eef3b0d2b123e0d27a7af4c90ad
5dc9ba7547b987bbbc3191224c301a16
here Maintenance release.
2 Jan 13 6.0.1 zip
tar.bz2
github
fd9668a28d568156fb6a2b482f8d1856
bd331c6cb53f66ca8959dfceec840eed
here Bugfix release.
2 Jan 13 6.1.1 zip
tar.bz2
github
ec167c570cc0c5bc9a2b0d7c3424e4a3
ff3c5f1cb7805ab5b2d63c49d5e589e3
here Bugfix release.
29 Dec 15 7.0.0 zip
tar.bz2
github
a320eb3bd77bbffabe02b665479006e3
552b613d454fc3e2aa6c54a4f86fca75
here Finally.
31 May 16 7.1.0 zip
tar.bz2
github
e797b13362eadf9eb43cfab84bc8b2ff
bad98e370d9a6035919f421b929ae22e
here New queue, PRNG, benchmark app, plus general performance improvements.
20 Feb 17 7.1.1 zip
tar.bz2
github
0bf8b2141062fc375c502dd5c85e828c
2a4cb6d64d8d9333b050059e4a1b7782
here Bugfix release.

user provided downloads

date release source md5sum release note comment
17 Aug 14 6.1.1 patch file 85353a6719ac6fc498aa904d0c329b47 n/a OSX patch kindly provided by Karl Yerkes
4 Aug 15 6.1.1 patch file e9df09f41257d3c791988427c169c967 n/a OSX patch kindly provided by Ben Jolitz