r6.1.1:Building Guide (lfds)

Introduction

The library builds as a static or dynamic library, with release or debug builds.

A platform is a combination of hardware, operating system and toolchain. The library has out-of-the-box support for certain broad platforms, where broad indicates particular components but where the versions vary, but it is problematic to exactly define which versions are supported due to the very large number of versions combined with lack of hardware, software and information.

Directory Layout

The source archive contains the following directory tree;

/liblfds611/bin/                      - the library binary (static or dynamic) ends up in here
/liblfds611/inc/                      - public header files
/liblfds611/obj/                      - directory for object files for liblfds
/liblfds611/src/lfds611_abstraction/  - abstraction layer sources
/liblfds611/src/lfds611_freelist/     - freelist sources
/liblfds611/src/lfds611_liblfds/      - liblfds internal sources
/liblfds611/src/lfds611_queue/        - queue sources
/liblfds611/src/lfds611_ringbuffer/   - ringbuffer sources
/liblfds611/src/lfds611_slist/        - singly linked list sources
/liblfds611/src/lfds611_stack/        - stack sources

In short; /liblfds611/bin contains the library binary, /liblfds611/inc contains the public header files, /liblfds611/obj is the temporary directory for object files and /liblfds611/src contains one directory per data structure, where each such directory contains the multiple C files for that data structure.

The root contains a considerable number of files required for building on various platforms.

Supported Platforms

Out-of-the-box ports are provided for;

Hardware	Operating System	Toolchain Choices
x64	Windows 64-bit	1. Microsoft Visual Studio 2. Microsoft Windows SDK and GNUmake
x64 x86	Windows 32-bit	1. Microsoft Visual Studio 2. Visual C++ Express Edition 3. Microsoft Windows SDK and GNUmake
x64 x86	Windows Kernel	1. Windows Driver Kit
x64	Linux 64-bit	1. GCC and GNUmake
x64 x86 ARM	Linux 32-bit	1. GCC and GNUmake

All platform components (hardware, OS, toolchain) have version requirements. However, it is problematic to exactly define these requirements, as the necessary hardware and software are not available. Certain constraints are known and are described here; beyond that, try it with your versions and see if the test programme passes (which is not a guarantee, but is a strong positive sign).

Hardware	Versioning
ARM	armv6k or better (for ldrex/strex)
x64	cmpxchg16b is missing from early (~2003) AMD Opterons
x86	i486 or better (for cmpxchg8b)

Operating Systems	Versioning
Linux	No known requirements
Windows	Win98 and NT 4.0 or better (_InterlockedIncrement behaves differently in earlier versions)

Toolchain	Versioning
Microsoft Visual Studio	The solution files are made with the 2008 release and probably cannot be read by earlier versions
Visual C++ Express Edition	The solution files are made with the 2008 release and probably cannot be read by earlier versions
Microsoft Windows SDK and GNUmake	No known requirements
GCC and GNUmake	GCC 4.1.0 introduced atomic intrinsics and these are required; these however have been pretty problematic (e.g. silently not implemented for ARM, or failing with shared objects, etc) up till something like version 4.4.0

Tested Platforms

Every build variant (static/dynamic, debug/release) of liblfds has been built, and the static release and dynamic release variants of test programme run (where possible, so not on Windows kernel) for five iterations, on the following platforms;

Hardware	NN/PC/LC¹	Operating System	Toolchain	Targets
Intel Core i5	1/2/4	Windows 7 build 7600 64-bit	Microsoft SDK for Windows 7 v7.1 and GNUmake 3.8.1	x64 (native) x86
VirtuaBox VM	1/2/2	Windows 7 build 7600 64-bit	Visual C++ 2008 Trial Edition	x64 (native) x86
VirtuaBox VM	1/2/2	Windows 7 build 7600 64-bit	Microsoft Windows Driver Kit v7.1.0²	Windows 7 free build 64-bit (native) Windows 7 free build 32-bit Windows XP free build 32-bit
EC2 VM m1.xlarge	?/?/4	Linux 3.2.34-55.46.amzn1.x86_64	GCC 4.6.2 20111027 and GNUmake 3.8.1	x64 (native)
EC2 VM c1.medium	?/?/2	Linux 3.2.34-55.46.amzn1.i686	GCC 4.6.2 20111027 and GNUmake 3.8.1	x86 (OS native, but 64-bit CPUs)
Cortex A15	1/1/2	Linux 3.4.0 armv71	GCC 4.6.3 and GNUmake 3.8.1	ARM (native)

1. Numa Nodes / Physical Cores / Logical Cores
2. Win kernel build cannot run the test programme; this platform has only been compiled upon

Toolchain Notes

Microsoft Visual Studio is Microsoft's commerical, fully fledged development GUI. It is expensive and supports all Windows platforms (32 and 64-bit Windows and 32 and 64-bit CPUs).

Visual C++ Express Edition is Microsoft's free development GUI. It only supports x86 but in theory installation of the Microsoft Windows SDK makes the x64 compilers available.

Microsoft Windows SDK is Microsoft's free command line based development environment. It has no GUI, but supports all Windows platforms (32 and 64-bit Windows and 32 and 64-bit CPUs).

The Windows Driver Kit is Microsoft's kernel development environment. It is command line based and supports all Windows platforms (including in release 7.1.0 ARM based platforms which are not yet supported by liblfds).

Building for Linux User-Mode

There is a GNUmake makefile, /makefile.linux, which has the following targets;

arrel (release static)
ardbg (debug static)
sorel (release shared object)
sodbg (debug shared object)
clean

The default build is debug static.

The resulting object files are placed directly in /liblfds611/obj and the resulting binaries are placed directly in /liblfds611/bin. If you wish to change build type, you need to make clean first.

Building for Windows Kernel-Mode

The Windows kernel build environment is primitive and has a number of severe limitations; in particular, all source files must be in one directory and it is not possible to choose the output binary type (static or dynamic library) from the build command line; rather, a string has to be modified in a text file used by the build (!)

To deal with these limitations, it is necessary for a Windows kernel build to run a batch file prior to building. There are two batch files, one for static library builds and the other for dynamic library builds. They are idempotent; you can run them as often as you like and switch between them as often as you want. It's all fine.

Both batch files copy all the sources file into a single directory, /liblfds611/src/single_dir_for_windows_kernel/.

The static library batch file will then copy /liblfds611/sources.static into /liblfds611/src/single_dir_for_windows_kernel/, which will cause a static library to be built.

The dynamic library batch file will then copy /liblfds611/sources.dynamic into /liblfds611/src/single_dir_for_windows_kernel/, which will cause a dynamic library to be built. It will also copy src/driver_entry.c into /liblfds611/src/single_dir_for_windows_kernel/, since the linker requires the DriverEntry function to exist, even though it's not used.

To build, start a build command line as usual, indicating through the command line you select whether you are making a debug or release build. Then run the appropriate liblfds batch file to select a static or dynamic library. Then, finally, run build.exe in the root directory, with whatever arguments you prefer.

Note that due to limitations in the build environment, object files appear in a subdirectory in /liblfds611/src/single_dir_for_windows_kernel/, rather than in the usual /liblfds611/obj/. The final binary output however still appears as usual in /liblfds611/bin/.

Note that the sources file used to compile the library asserts the define WIN_KERNEL_BUILD. This appears to be necessary, due to the lack of a compiler-provided method to differentiate in the code between a user-mode or kernel-mode build.

Building for Windows User-Mode

Microsoft Visual Studio / Visual C++ Express Edition

There is a Visual Studio 2008 project file, /liblfds611/liblfds.sln, which has the following platforms;

Win32 (for 32 bit CPUs)
x64 (for 64 bit CPUs)

and the following configurations;

Debug DLL
Debug Lib
Release DLL
Release Lib

The default build is x64 debug lib. The DLL builds both link to the DLL version of the MS run-time libraries. The static builds link to the static versions of the MS run-time libraries.

With Visual C++ Express Edition, the x64 platform will not be available but in theory installation of the Microsoft Windows SDK makes the x64 compilers available.

As is customary with Visual Studio, each build has it's own object file and output binary directory (/liblfds611/obj/$(Platform)/$(Configuration) and /liblfds611/bin/$(Platform)/$(Configuration), respectively), so it is not necessary to clean between switching configuration or platform types.

Microsoft Windows SDK

There is a GNUmake makefile, /makefile.windows, which has the following targets;

librel (release static)
libdbg (debug static)
dllrel (release DLL)
dlldbg (debug DLL)
clean

To use this makefile, open a command shell and run vcvars*.bat or setenv.bat as appropriate for your target platform.

As with the Linux makefile, the makefile places its output directly in /liblfds611/bin and /liblfds611/obj. A make clean is required when switching between build types.

Usage

There is a single public header file, /liblfds611/inc/liblfds611.h. This contains the APIs for all of the data structures. You need to include this header file in your source code. The library binary, on all platforms and for all build variants, ends up in /bin/liblfds611.*, where the suffix varies by platform and build variant (static or dynamic library). For static builds, you need to link directly to the binary. For dynamic builds, you need to arrange your system such that the loader at run-time can locate the library.