Freelist
Source Files
└───liblfds700
├───inc
│ └───liblfds700
│ lfds700_freelist.h
└───src
└───lfds700_freelist
lfds700_freelist_cleanup.c
lfds700_freelist_init.c
lfds700_freelist_internal.h
lfds700_freelist_pop.c
lfds700_freelist_push.c
lfds700_freelist_query.c
Enums
enum lfds700_freelist_query { LFDS700_FREELIST_QUERY_SINGLETHREADED_GET_COUNT, LFDS700_FREELIST_QUERY_SINGLETHREADED_VALIDATE };
Opaque Structures
struct lfds700_freelist_element; struct lfds700_freelist_state; struct lfds700_misc_prng_state;
Macros
#define LFDS700_FREELIST_GET_KEY_FROM_ELEMENT( freelist_element ) #define LFDS700_FREELIST_SET_KEY_IN_ELEMENT( freelist_element, new_key ) #define LFDS700_FREELIST_GET_VALUE_FROM_ELEMENT( freelist_element ) #define LFDS700_FREELIST_SET_VALUE_IN_ELEMENT( freelist_element, new_value ) #define LFDS700_FREELIST_GET_USER_STATE_FROM_STATE( freelist_state )
Prototype
void lfds700_freelist_init_valid_on_current_logical_core( struct lfds700_freelist_state *fs, void *user_state ); void lfds700_freelist_cleanup( struct lfds700_freelist_state *fs, void (*element_cleanup_callback)(struct lfds700_freelist_state *fs, struct lfds700_freelist_element *fe) ); void lfds700_freelist_push( struct lfds700_freelist_state *fs, struct lfds700_freelist_element *fe, struct lfds700_misc_prng_state *ps ); int lfds700_freelist_pop( struct lfds700_freelist_state *fs, struct lfds700_freelist_element **fe, struct lfds700_misc_prng_state *ps ); void lfds700_freelist_query( struct lfds700_freelist_state *fs, enum lfds700_freelist_query query_type, void *query_input, void *query_output );
Overview
This data structure implements a freelist. It supports any number of concurrent users, and internally implements exponential backoff to help deal with high load and so improve scalability. There is however no elimination layer in front of the freelist (see Hendler, Shavit, Yerushalmi - A Scalable Lock-Free Stack Algorithm - the elimination layer for the stack is directly applicable to the freelist), so it does not fully scale.
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.
General usage is that the user calls lfds700_freelist_init_valid_on_current_logical_core to initialize a struct lfds700_freelist_state, and then calls lfds700_freelist_push and lfds700_freelist_pop to push and pop struct lfds700_freelist_elements. A freelist element provides the ability to store a key and a value, both of which are of type void *. The key is not used in any way by the freelist (and of course the value is neither), rather, it is available as a convenience for the user, for situations where data is being transferred between different types of data structures, where some of these data structures do support a meaningful key. The key and value are get and set by macros, such as LFDS700_FREELIST_SET_VALUE_IN_ELEMENT. The SET macros can only be used when an element is outside of the freelist. (Things may seem to work even if they are used on elements which are in the freelist, but it's a matter of pure chance).
(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)
The state and element structures are both public, present in the lfds700_freelist.h header file, so that users can embed them in their own structures (and where necessary pass them to sizeof). Expected use is that user structures which are to enter freelists contain within themselves a struct lfds700_freelist_element, and this is used when calling lfds700_freelist_push, and the value set in the freelist element is a pointer to the user structure entering the freelist. This approach permits zero run-time allocation of store and also ensures the freelist element is normally in the same memory page as the user data it refers to.
Lock-free Specific Behaviour
The state initialization function, lfds700_freelist_init_valid_on_current_logical_core, as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE, which will do that which its name suggests.
Once a freelist element structure has been pushed to the stack, it cannot be deallocated (free, or stack allocation lifetimes ending due to say a thread ending, etc) until lfds700_freelist_cleanup has returned. Typical usage of course with a freelist is as a store for unused elements, so this restriction in fact is in line with normal usage.
The struct lfds700_misc_prng_state argument is the state for a single-threaded, fast, high quality random number generator, required by the exponential backoff code. Each thread should allocate and initialize one of these structures, and then it can be used for all API calls which take this argument.
The SET macros (for setting key and value, in stack elements) can only be correctly used on elements which are outside of a freelist, and the GET macros, if called by a thread on a logical core other than the logical core of the thread which called the SET macros, can only be correctly used on a freelist element which has been pushed to the freelist and then popped.
By correctly is it meant to say that the GET macros will actually read the data written by the SET macros, and not some other data.
The freelist should be regarded as a safe communication channel between threads. Any freelist element which has a key and/or value set, and then is pushed to a freelist, will allow any thread which pops that element to correctly read the key and/or value (and by this is it meant to say not just the void pointer of the key and value, but also whatever they point to). This is the only guarantee. Any reads or writes of key and/or value, or what they point to, which occur outside of this pushing and popping pair are not guaranteed to be correct; the data written may never be seen by other threads.
White Paper
This is an implementation of the classic lock-free data structure, by R. K. Treiber, back from 1986. Treiber published a long pamphlet, "Systems Programming: Coping with Parallelism", which amongst other things described the use of compare-and-swap on some contemporary IBM mainframe hardware to implement a stack (which is conceptually identical to a freelist).
Example
#include <stdio.h>
#include "liblfds700.h"
struct test_data
{
struct lfds700_freelist_element
fe;
int
buffer[1024];
};
int main()
{
int long long unsigned
loop;
struct lfds700_misc_prng_state LFDS700_PAL_ALIGN( LFDS700_PAL_CACHE_LINE_LENGTH_IN_BYTES )
ps;
struct lfds700_freelist_element
*fe;
struct lfds700_freelist_state
fs;
struct test_data
*td,
*temp_td;
lfds700_misc_library_init_valid_on_current_logical_core();
lfds700_misc_prng_init( &ps );
lfds700_freelist_init_valid_on_current_logical_core( &fs, NULL );
td = malloc( sizeof(struct test_data) * 10 );
/* TRD : rather than push one by one, we could use lfds700_freelist_push_array_of_elements()
but this is an introductory example, so keeping it simple and showing how push/pop work
*/
for( loop = 0 ; loop < 10 ; loop++ )
{
LFDS700_FREELIST_SET_VALUE_IN_ELEMENT( td[loop].fe, &td[loop] );
lfds700_freelist_push( &fs, &td[loop].fe, &ps );
}
for( loop = 0 ; loop < 10 ; loop++ )
{
lfds700_freelist_pop( &fs, &fe );
temp_td = LFDS700_FREELIST_GET_VALUE_FROM_ELEMENT( fe );
// TRD : and here now we can use temp_td->buffer
}
lfds700_freelist_cleanup( &s, NULL );
free( td );
lfds700_misc_library_cleanup();
return( EXIT_SUCCESS );
}