r6.0.1:Porting Guide
Library
Introduction
There are four issues to deal with when it comes to porting liblfds;
- The lock-free algorithms implemented in liblfds depend on atomic instructions and the API for these instructions varies by platform.
- Atomic instructions always need to work on aligned memory (e.g. memory allocated on pointer length boundaries) and as such liblfds needs for heap allocations access to platform specific aligned malloc and aligned free functions and for stack allocations access to the compiler specific keyword which controls the memory alignment of variables declared on the stack.
- The atomic instructions always correspond to a single underlying CPU instruction and it is important that the abstraction layer functions are inlined by the compiler, otherwise we have the overhead of a function call every time we use one of these instructions and one of the points of using lock-free is performance; as such, liblfds needs access to the compiler specific keyword which controls function inlining.
- The word length of the underlying hardware can vary. In today's world, this means 32 bit CPUs and 64 bit CPUs and liblfds needs to know an integer type which has the word length of the underlying CPU.
In response to these issues, liblfds implements an abstraction layer. The abstraction layer provides to the liblfds a standard API to mask these platform dependent issues. Porting consists of implementing the abstraction layer API on your platform.
Detailed Platform Requirements
To port liblfds, the target platform must provide;
- atomic single-word increment
- atomic single-word compare-and-swap
- atomic contigious double-word compare-and-swap
- aligned malloc
- aligned free
- compiler keyword for alignment of variables declared on the stack
A word here means a type equal in length to the platform pointer size.
Also, the target plaform may provide;
- compiler keyword for function inlining
It is desirable but not essential to have a compiler keyword for function inlining. If the abstraction layer define for this keyword is left empty, then inlining will not occur; everything will still work, it'll just be slower.
Currently, liblfds has been ported only to platforms which provide a contigious double-word compare-and-swap (x86, x64 and ARM). It is entirely possible to port to a platform which instead provides load-link/conditional-store where non-load-linked loads can be performed inside the LL/SC pair (this is how ABA is solved using single word LL/SC) but this has not yet been done and it is not reasonable to ask a third party to undertake such a port until I've done it and documented it. Please see lfds601_abstraction_dcas for more details should you wish to try this anyway.
Note that the SPARC and IA64 architectures provides neither contigious double-word compare-and-swap nor load-link/conditional-store and as such, liblfds cannot be ported to those architectures.
The Abstraction Layer
At this point in the guide, you should briefly open the abstraction layer API page, lfds601_abstraction (liblfds), to get an overview of the API function prototypes, defines and typedefs.
Each function, define and typedef has a wiki page and those pages contain detailed information and examples specifically written with implementation in mind.
Implementing the Abstraction Layer
Implementing the abstraction layer requires;
- implementing the five abstraction layer functions;
- aligned malloc
- aligned free
- atomic single-word compare-and-swap function, compiler instrinic or instruction
- atomic contigious double-word compare-and-swap function, compiler instrinic or instruction
- atomic increment function, compiler instrinic or instruction
- providing the necessary set of typedefs and defines in liblfds.h;
- a type for lfds601_atom_t
- the compiler inline directive for LFDS601_INLINE
- the compiler stack variable alignment directive for LFDS601_ALIGN
- the correct sizes for LFDS601_ALIGN_SINGLE_POINTER and LFDS601_ALIGN_DOUBLE_POINTER
- #including any header files needed for your platform
The location of the functions, typedef and defines in the source files is as follows;
| File | Function |
| /liblfds601/src/lfds601_abstraction/lfds601_abstraction_aligned_free.c | lfds601_abstraction_aligned_free |
| /liblfds601/src/lfds601_abstraction/lfds601_abstraction_aligned_malloc.c | lfds601_abstraction_aligned_malloc |
| /liblfds601/src/lfds601_abstraction/lfds601_abstraction_cas.c | lfds601_abstraction_cas |
| /liblfds601/src/lfds601_abstraction/lfds601_abstraction_dcas.c | lfds601_abstraction_dcas |
| /liblfds601/src/lfds601_abstraction/lfds601_abstraction_increment.c | lfds601_abstraction_increment |
| /liblfds601/inc/liblfds601.h | typedef, defines and includes |
When you come to implement, you will be adding your code alongside other existing implementations for other platforms. You must guard each function by an #if, such that it is only seen by platforms which can use that implementation. The set of the typedef and defines in liblfds601.h is similarly guarded by an identical #if.
So for example, lfds601_abstraction_aligned_free in lfds601_abstraction_aligned_free.c, on Windows looks like this;
#if (defined _WIN32 && defined _MSC_VER)
/* TRD : any Windows on any CPU with the Microsoft C compiler
_WIN32 indicates 64-bit or 32-bit Windows
_MSC_VER indicates Microsoft C compiler
*/
void lfds601_abstraction_aligned_free( void *memory )
{
_aligned_free( memory );
return;
}
#endif
And the typedef and defines in liblfds.h on 64-bit Windows looks like this;
#if (defined _WIN64 && defined _MSC_VER) // TRD : 64-bit Windows with the Microsoft C compiler, any CPU #include <assert.h> #include <stdlib.h> #include <stdio.h> #include <windows.h> typedef unsigned __int64 lfds601_atom_t; #define LFDS601_INLINE extern __forceinline #define LFDS601_ALIGN(alignment) __declspec( align(alignment) ) #define LFDS601_ALIGN_SINGLE_POINTER 8 #define LFDS601_ALIGN_DOUBLE_POINTER 16 #endif
Existing Implementations Matrix
When an abstraction layer function is implemented, the protective #if exactly defines the platform requirements necessary for that implementation. As such, many functions although implemented for a specific port are in fact useable on a wide range of platforms. For example, there is an implementation of lfds601_abstraction_increment which only requires GCC 4.1.0 or later and so this implementation works on any operating system and any CPU.
Using this table can be a bit of a mind twister. The best way is to look at the function you're interested in and then go from left to right; you can then see what implementations exist for that function and if your platform matches any of them. Do that for each function and then you'll know what work you have to do to port. Generally speaking, on a Linux platform with GCC, the only work that is required is implementing double-word compare-and-swap, since this is not supported by GCC in its built-in atomic operations.
Notes; (u) denotes user-mode, (k) denotes kernel-mode, x86 means i486 or better, ARM means architecture 6K or better.
| Standard OS CPU Compiler |
N/A Windows (u) Any Microsoft C |
N/A Windows (k) Any Microsoft C |
POSIX >= 6.0 Any Any Any |
N/A Any Any GCC >= 4.1.0 |
N/A Any x86, x64, ARM GCC |
| lfds601_abstraction_aligned_free | y | y | y | ||
| lfds601_abstraction_aligned_malloc | y | y | y | ||
| lfds601_abstraction_cas | y | y | y | ||
| lfds601_abstraction_dcas | y | y | y | ||
| lfds601_abstraction_increment | y | y | y |
Test Program
Introduction
There are three issues when it comes to porting the test program;
- The test program needs to run multiple concurrent threads and the API for thread management varies by platform.
- The number of threads issued is a multiple of the number of CPUs and the API for determining the number of CPUs varies by platform.
- The prototype for a thread function varies by platform.
In response to these issues, the test program implements an abstraction layer. The abstraction layer provides to the test program a standard API for these platform dependent functions. Porting consists of implementing these functions on your platform.
Detailed Platform Requirements
To port the test program, the target platform must provide;
- a function to start a thread
- a function to wait for a thread to terminate
- the type of the value returned by the thread function prototype
- the type used for thread state
The Abstraction Layer
At this point in the guide, you should briefly open the abstraction layer API page, abstraction (test), to get an overview of the API function prototypes, defines and typedefs.
Each function, define and typedef has a wiki page and those pages contain detailed information and examples specifically written with implementation in mind.
Implementing the Abstraction Layer
Implementing the abstraction layer requires;
- implementing the three abstraction layer functions;
- a function for finding the number of CPUs
- a function for starting a thread
- a function for waiting for a thread to terminate
- providing the necessary set of typedefs and defines in lfds601_abstraction.h;
- a type for lfds601_thread_state_t
- a type for lfds601_thread_return_t
- #including any header files needed for your platform
The location of the functions and typedefs in the source files is as follows;
| File | Function |
| /test/src/lfds601_abstraction_cpu_count.c | lfds601_abstraction_cpu_count |
| /test/src/lfds601_abstraction_thread_start.c | lfds601_abstraction_thread_start |
| /test/src/lfds601_abstraction_thread_wait.c | lfds601_abstraction_thread_wait |
| /test/src/lfds601_abstraction.h | the typedefs and includes |
When you come to implement, you will be adding your code alongside other existing implementations for other platforms. You must guard each function by an #if, such that it is only seen by platforms which can use that implementation. The typedefs in abstraction.h are similarly guarded by an identical #if.
So for example, lfds601_abstraction_cpu_count in lfds601_abstraction_cpu_count.c, on Windows looks like this;
#if (defined _WIN32 && defined _MSC_VER)
/* TRD : any Windows on any CPU with the Microsoft C compiler
_WIN32 indicates 64-bit or 32-bit Windows
_MSC_VER indicates Microsoft C compiler
*/
unsigned int lfds601_abstraction_cpu_count()
{
SYSTEM_INFO
si;
GetSystemInfo( &si );
return( (unsigned int) si.dwNumberOfProcessors );
}
#endif
And the typedefs in lfds601_abstraction.h on Windows look like this;
#if (defined _WIN32 && defined _MSC_VER)
/* TRD : any Windows on any CPU with the Microsoft C compiler
_WIN32 indicates 64-bit or 32-bit Windows
_MSC_VER indicates Microsoft C compiler
*/
#include <windows.h>
typedef HANDLE lfds601_thread_state_t;
typedef DWORD lfds601_thread_return_t;
#endif
The abstraction layer API root document page is abstraction (test).
Each abstraction layer function and typedef has a wiki page. Those pages contain detailed information and examples specifically written with implementation in mind. Refer to those pages for the information you need when you come to implement.
Existing Implementations Matrix
When an abstraction layer function is implemented, the protective #if exactly defines the platform requirements necessary for that implementation. As such, many functions although implemented for a specific port are in fact useable on a wide range of platforms. For example, there is an implementation of lfds601_abstraction_increment which only requires GCC 4.1.0 or later and so this implementation works on any operating system and any CPU.
| Standard OS CPU Compiler |
N/A Any Windows Any Microsoft C |
pthreads UNIX Any Any |
Linux Any Any GCC |
| lfds601_abstraction_cpu_count | y | y | |
| lfds601_abstraction_thread_start | y | y | |
| lfds601_abstraction_thread_end | y | y |
Note that pthreads is not in fact restricted to UNIX. Implementations exist for Windows. However, Windows has it's platform-native threads, which are preferable, so the use of pthreads is for now with UNIXes.