r6.1.0:lfds610_freelist

Source Files

/liblfds610/src/lfds610_freelist/lfds610_freelist_delete.c
/liblfds610/src/lfds610_freelist/lfds610_freelist_get_and_set.c
/liblfds610/src/lfds610_freelist/lfds610_freelist_new.c
/liblfds610/src/lfds610_freelist/lfds610_freelist_pop_push.c
/liblfds610/src/lfds610_freelist/lfds610_freelist_query.c
/liblfds610/src/lfds610_freelist/lfds610_freelist_internal.h
/liblfds610/inc/liblfds610.h

Incomplete Types

struct lfds610_freelist_state;
struct lfds610_freelist_element;

Enums

enum lfds610_freelist_query_type
{
  LFDS610_FREELIST_QUERY_ELEMENT_COUNT,
  LFDS610_FREELIST_QUERY_VALIDATE
};

Prototypes

int lfds610_freelist_new( struct lfds610_freelist_state **fs, lfds610_atom_t number_elements,
                          int (*user_data_init_function)(void **user_data, void *user_state),
                          void *user_state );
void lfds610_freelist_use( struct lfds610_freelist_state *fs );
void lfds610_freelist_delete( struct lfds610_freelist_state **fs,
                              void (*user_data_delete_function)(void *user_data, void *user_state),
                              void *user_state );

lfds610_atom_t lfds610_freelist_new_elements( struct lfds610_freelist_state *fs, lfds610_atom_t number_elements );

struct lfds610_freelist_element *lfds610_freelist_pop( void *lfds610_freelist_state, struct lfds610_freelist_element **fe );
struct lfds610_freelist_element *lfds610_freelist_guaranteed_pop( struct lfds610_freelist_state *fs, struct lfds610_freelist_element **fe );
void lfds610_freelist_push( struct lfds610_freelist_state *fs, struct lfds610_freelist_element *fe );

void *lfds610_freelist_get_user_data_from_element( struct lfds610_freelist_element *fe, void **user_data );
void lfds610_freelist_set_user_data_in_element( struct lfds610_freelist_element *fe, void *user_data );

void lfds610_freelist_query( struct lfds610_freelist_state *fs, enum lfds610_freelist_query_type query_type, void *query_input, void *query_output );

Overview

This API implements a freelist. A new freelist is instantiated by the lfds610_freelist_new function, where the argument number_elements is the maximum number of elements which can be popped from the freelist at any one time. The caller then uses the freelist by pushing and popping, via the lfds610_freelist_push and lfds610_freelist_pop functions, respectively. A push or pop operation will push or pop a single freelist element. A freelist element contains a single void pointer of user data, which is read and written using the functions lfds610_freelist_get_user_data_from_element and lfds610_freelist_set_user_data_in_element, respectively. These void pointers are expected to point to user allocated state although of course they can be used directly to store a single value. Finally, the freelist is deleted using lfds610_freelist_delete.

The function lfds610_freelist_pop only fails when there are no elements available in the freelist. In this case, the function lfds610_freelist_guaranteed_pop can be called. This allocates a single new element and then provides that element. This permanently increases the maximum number of elements in the freelist by one. This function only fails when malloc fails.

Lock-free Specific Behaviour

The maximum number of elements in the freelist must be specified when the freelist is created and these elements are allocated in full when the freelist is created. It is possible after the freelist is created to increase the number of elements in the freelist, by using the function lfds610_freelist_guaranteed_pop, but it is never possible to decrease the number of elements in the freelist; the freelist can only grow. This is why there are only functions for adding elements to an existing freelist and no functions for deleting elements which have been removed from the freelist.

Note that the function for adding new elements to a freelist (lfds610_freelist_new_elements) is (as would be expected in a lock-free data structure) thread-safe. Multiple threads can concurrently be calling this function as well as other threads engaging in the normal push and pop operations.

Algorithm

This freelist implements Treiber's stack algorithm (a freelist is a pre-filled stack). As such it does not truly scale; contention for entry and exit to and from the stack ultimately reduces performance as the CPU count increases. Indeed, with enough CPUs, performance becomes less than with fewer CPUs, for there are so many threads, they almost always fail in their attempt to enter or leave the stack and so are prevented from doing other work.

There is a far more scalable stack, based on the work done by Hendler, Shavit and Yerushalmi, which I understand (I've not looked at in depth) is basically the Treiber stack but with a layer in front of the stack where any threads which at the same time wish to push and pop can exchange their respective operations (the pusher giving his element to the popper) and so avoid having to touch the freelist. I intend to implement this in the future.