Introduction

Introduction

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 across 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 can be used with the stack, heap or shared memory) and compiles not just on a freestanding C89 implementation, but on a bare C89 implementation.

Currently liblfds is composed of two separate components; liblfds which is the library itself and test, which is a command-line based test programme.

Both liblfds and test provide a porting abstraction layer, which acts to mask platform differences.

Out-of-the-Box Supported Data Structures and Platforms

A platform is a combination of toolchain (GCC, MSVC, etc) and processor type.

Not all processors support all data structures, due to atomic operation support varying by processor.

Out-of-the-box support basically amounts to which toolchain build files are provided by liblfds (for porting abstraction layers have been provided for the systems for which build files are provided).

The table below looks complicated but what it comes down to is this; the add-only data structures and the bounded single-consumer, single-producer queue work on everything, and all the other stuff works only on ARM32, x86 and x64. Only user-mode Linux (ARM32, MIPS32, x86 and x64) and user-mode Windows (x86 and x64) have actually had the test suite run on them - and you know how it is with software, if you've not actually run it and seen it work, then it doesn't work - so there are no guarantees at all that anything else actually works. There's no support yet for ARM64.

Release 7.0.0
	GCC and gnumake					GCC, kbuild and gnumake1				SDK for Windows 7		VS Pro 2012		VS Pro 2012 and WDK 8.02	VS Pro 2013 and WDK 8.12	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	x64	x86	x64, x86	ARM32, x64, x86	IA64	x64, x86
Binary Tree (add-only, unbalanced)
Freelist
Hash (add-only)
List (add-only, ordered, singly-linked)
List (add-only, singly-linked, unordered)
Queue
Queue (BSCSP)3
Ringbuffer
Stack

1. This is the Linux kernel toolchain
2. This is a Windows kernel toolchain
3. Bounded (fixed maximum number of elements, specified at instantiation time), single consumer, single producer

Key
	supported, compiled and tested
	supported and compiled but not tested (test ought to pass, but it hasn't been run, so it might not)
	supported but not compiled or tested (so it ought to compile, but it hasn't been done, so it might not)
	not (yet) supported (never compiled, and expected not to compile successfully)
	cannot be implemented on this platform
GCC	GCC >= 4.1.21 and GNUmake >= 3.8.1
SDK 7 for Windows	Microsoft Windows SDK 7.1 and GNUmake 3.8.1
VS Pro 2012	Microsoft Visual Studio 2012 Professional Edition
VS Pro 2013	Microsoft Visual Studio 2013 Professional Edition
WDK 7.1	Windows Driver Kit 7.1.0
WDK 8.0	Windows Driver Kit 8.0 (there seems to be no page for WDK 8.0, only a download link)
WDK 8.1	Windows Driver Kit 8.1

1. If GCC >= 4.7.3 is used, the new atomic intrinsics introduced with that version are used

License

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

If for legal reasons a specific, well-known 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.

Porting

The liblfds library and test binary each provide a porting abstraction layer which acts to mask platform differences. Porting is the act of implementing on your platform the defines, typesdefs and functions which make up a porting abstraction layer.

The liblfds porting abstraction layer is intentionally minimal and in particular is entirely independent of the Standard Library, and so supports hosted, freestanding and entirely independent environments. A corollary of this is that the library performs no memory allocation and so is suitable for environments where run-time memory allocation is unavailable.

The liblfds porting abstraction layer is arranged as three header files, one each for the compiler, operating system and processor, where each file provided such parts of the porting abstraction layer as come from each source, with each file using the pre-processor #if directive with compiler defined macros to restrict each implementation to the correct platform.

As such, it's not possible to succinctly state exactly what ports are supported out-of-the-box, as an implementation can span many potential platforms - e.g. the compiler implementation which matches GCC provides the compiler part of the porting abstraction layer for GCC for all operating systems and all processors.

The test porting abstraction layer essentially consists of thread support. Out-of-the-box ports are provided for Windows (XP and greater) user-mode and Linux user-mode. There are no kernel ports as test is a command line programme; there is yet no version which can run in kernel mode.

For documentation, see the Porting Guide (liblfds) and the Porting Guide (test).

Building

There are two top-level directories, liblfds700 and test. Each separate component (liblfds700 and test) has a directory called build, which in turns has one directory per supported platform, where that directory contains the build files (makefiles, MSVC solutions, etc) for that platform.

├───liblfds700
│   ├───bin
│   ├───build
|   │   ├───gcc_and_gnumake
|   │   ├───gcc_kbuild_and_gnumae
|   │   ├───sdk_for_windows_7_and_gnumake
|   │   ├───visual_studio_express_2012
|   │   ├───visual_studio_professional_2012_and_wdk_8.0
|   │   └───wdk_7.1
│   ├───inc
│   ├───obj
│   └───src
└───test
    ├───bin
    ├───build
    │   ├───gcc_and_gnumake
    │   ├───visual_studio_express_2012
    │   └───sdk_for_windows_7_and_gnumake
    ├───obj
    └───src

The liblfds library compiles to either a static or shared library, to the pathname liblfds700/bin/liblfds700.[nnn], where the suffix of the library file varies by platform and by the type of library (static or dynamic).

The test programme compiles to a command line binary, to the pathname test/bin/test[nnn], where the suffix of the executable file varies by platform (and may be absent, as is the case under Linux).

For documentation, see the Building Guide (liblfds) and the Building Guide (test).

Usage

The liblfds library has a set of header files, one per data structure, found in liblfds700/inc/, but you only include liblfds700/inc/liblfds700.h. Include the header file as you would normally, link to the library as you would normally. Voilà!

The test programme is a command line binary and is run by hand from the command line, no arguments or "-h" will display help text.

For documentation, see the Usage Guide (liblfds) and the Usage Guide (test).

See Also

• Release 7.0.0 Documentation