Stack
Source Files
└───liblfds711
├───inc
│ └───liblfds711
│ lfds711_stack.h
└───src
└───lfds711_stack
lfds711_stack_cleanup.c
lfds711_stack_init.c
lfds711_stack_internal.h
lfds711_stack_pop.c
lfds711_stack_push.c
lfds711_stack_query.c
Enums
enum lfds711_stack_query;
Opaque Structures
struct lfds711_stack_element; struct lfds711_stack_state;
Macros
#define LFDS711_STACK_GET_KEY_FROM_ELEMENT( stack_element ) #define LFDS711_STACK_SET_KEY_IN_ELEMENT( stack_element, new_key ) #define LFDS711_STACK_GET_VALUE_FROM_ELEMENT( stack_element ) #define LFDS711_STACK_SET_VALUE_IN_ELEMENT( stack_element, new_value ) #define LFDS711_STACK_GET_USER_STATE_FROM_STATE( stack_state )
Prototypes
void lfds711_stack_init_valid_on_current_logical_core( struct lfds711_stack_state *ss, void *user_state ); void lfds711_stack_cleanup( struct lfds711_stack_state *ss, void (*element_cleanup_callback)(struct lfds711_stack_state *ss, struct lfds711_stack_element *se) ); void lfds711_stack_push( struct lfds711_stack_state *ss, struct lfds711_stack_element *se ); int lfds711_stack_pop( struct lfds711_stack_state *ss, struct lfds711_stack_element **se ); void lfds711_stack_query( struct lfds711_stack_state *ss, enum lfds711_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 lfds711_stack_init_valid_on_current_logical_core to initialize a struct lfds711_stack_state, and then calls lfds711_stack_push and lfds711_stack_pop to push and pop struct lfds711_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 LFDS711_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 lfds711_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 lfds711_stack_element, and this is used when calling lfds711_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, lfds711_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 LFDS711_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 lfds711_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 "liblfds711.h"
struct test_data
{
struct lfds711_stack_element
se;
int long long unsigned
user_id;
};
int main()
{
int long long unsigned
loop;
struct lfds711_stack_element
*se;
struct lfds711_stack_state
ss;
struct test_data
*td,
*temp_td;
lfds711_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;
LFDS711_STACK_SET_VALUE_IN_ELEMENT( td[loop].se, &td[loop] );
lfds711_stack_push( &ss, &td[loop].se );
}
for( loop = 0 ; loop < 10 ; loop++ )
{
lfds711_stack_pop( &ss, &se );
temp_td = LFDS711_STACK_GET_VALUE_FROM_ELEMENT( *se );
print( "user_id = %llu\n", temp_td->user_id );
}
lfds711_stack_cleanup( &ss, NULL );
free( td );
return( EXIT_SUCCESS );
}