Stack
Source Files
└───liblfds710
├───inc
│ └───liblfds710
│ lfds710_stack.h
└───src
└───lfds710_stack
lfds710_stack_cleanup.c
lfds710_stack_init.c
lfds710_stack_internal.h
lfds710_stack_pop.c
lfds710_stack_push.c
lfds710_stack_query.c
Enums
enum lfds710_stack_query;
Opaque Structures
struct lfds710_stack_element; struct lfds710_stack_state;
Macros
#define LFDS710_STACK_GET_KEY_FROM_ELEMENT( stack_element ) #define LFDS710_STACK_SET_KEY_IN_ELEMENT( stack_element, new_key ) #define LFDS710_STACK_GET_VALUE_FROM_ELEMENT( stack_element ) #define LFDS710_STACK_SET_VALUE_IN_ELEMENT( stack_element, new_value ) #define LFDS710_STACK_GET_USER_STATE_FROM_STATE( stack_state )
Prototypes
void lfds710_stack_init_valid_on_current_logical_core( struct lfds710_stack_state *ss, void *user_state ); void lfds710_stack_cleanup( struct lfds710_stack_state *ss, void (*element_cleanup_callback)(struct lfds710_stack_state *ss, struct lfds710_stack_element *se) ); void lfds710_stack_push( struct lfds710_stack_state *ss, struct lfds710_stack_element *se ); int lfds710_stack_pop( struct lfds710_stack_state *ss, struct lfds710_stack_element **se ); void lfds710_stack_query( struct lfds710_stack_state *ss, enum lfds710_stack_query query_type, void *query_input, void *query_output );
Overview
This data structure implements a stack. 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 stack (see Hendler, Shavit, Yerushalmi - A Scalable Lock-Free Stack Algorithm), 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 lfds710_stack_init_valid_on_current_logical_core to initialize a struct lfds710_stack_state, and then calls lfds710_stack_push and lfds710_stack_pop to push and pop struct lfds710_stack_elements. A stack 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 stack (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 LFDS710_STACK_SET_VALUE_IN_ELEMENT. The SET macros can only be used when an element is outside of the stack. (Things may seem to work even if they are used on elements which are in the stack, 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 lfds710_stack.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 stacks contain within themselves a struct lfds710_stack_element, and this is used when calling lfds710_stack_push, and the value set in the stack element is a pointer to the user structure entering the stack. This approach permits zero run-time allocation of store and also ensures the stack element is normally in the same memory page as the user data it refers to.
Lock-free Specific Behaviour
The state initialization function, lfds710_stack_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 LFDS710_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 stack 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 lfds710_stack_cleanup has returned. Typical usage is to return popped stack elements to a freelist.
The SET macros (for setting key and value, in stack elements) can only be correctly used on elements which are outside of a stack, 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 stack element which has been pushed to the stack 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 stack should be regarded as a safe communication channel between threads. Any stack element which has a key and/or value set, and then is pushed to a stack, 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.
License
Unclear. However, no patent is known and the design is massively used throughout the industry.
Example
#include <stdio.h>
#include <stdlib.h>
#include "liblfds710.h"
struct test_data
{
struct lfds710_stack_element
se;
int long long unsigned
user_id;
};
int main()
{
int long long unsigned
loop;
struct lfds710_stack_element
*se;
struct lfds710_stack_state
ss;
struct test_data
*td,
*temp_td;
lfds710_stack_init_valid_on_current_logical_core( &ss, NULL );
td = malloc( sizeof(struct test_data) * 10 );
for( loop = 0 ; loop < 10 ; loop++ )
{
td[loop].user_id = loop;
LFDS710_STACK_SET_VALUE_IN_ELEMENT( td[loop].se, &td[loop] );
lfds710_stack_push( &ss, &td[loop].se );
}
for( loop = 0 ; loop < 10 ; loop++ )
{
lfds710_stack_pop( &ss, &se );
temp_td = LFDS710_STACK_GET_VALUE_FROM_ELEMENT( *se );
print( "user_id = %llu\n", temp_td->user_id );
}
lfds710_stack_cleanup( &ss, NULL );
free( td );
return( EXIT_SUCCESS );
}