Stack

From liblfds.org
Revision as of 02:04, 30 December 2015 by Admin (talk | contribs) (→‎Example)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Source Files

└───liblfds700
    ├───inc
    │   └───liblfds700
    │           lfds700_stack.h
    └───src
        └───lfds700_stack
                lfds700_stack_cleanup.c
                lfds700_stack_init.c
                lfds700_stack_internal.h
                lfds700_stack_pop.c
                lfds700_stack_push.c
                lfds700_stack_query.c

Enums

enum lfds700_stack_query
{
  LFDS700_STACK_QUERY_SINGLETHREADED_GET_COUNT,
  LFDS700_STACK_QUERY_SINGLETHREADED_VALIDATE
};

Opaque Structures

struct lfds700_misc_prng_state;
struct lfds700_stack_element;
struct lfds700_stack_state;

Macros

#define LFDS700_STACK_GET_KEY_FROM_ELEMENT( stack_element )
#define LFDS700_STACK_SET_KEY_IN_ELEMENT( stack_element, new_key )

#define LFDS700_STACK_GET_VALUE_FROM_ELEMENT( stack_element )
#define LFDS700_STACK_SET_VALUE_IN_ELEMENT( stack_element, new_value )

#define LFDS700_STACK_GET_USER_STATE_FROM_STATE( stack_state )

Prototypes

void lfds700_stack_init_valid_on_current_logical_core( struct lfds700_stack_state *ss, void *user_state );

void lfds700_stack_cleanup( struct lfds700_stack_state *ss,
                            void (*element_cleanup_callback)(struct lfds700_stack_state *ss, struct lfds700_stack_element *se) );

void lfds700_stack_push( struct lfds700_stack_state *ss,
                         struct lfds700_stack_element *se,
                         struct lfds700_misc_prng_state *ps );

int lfds700_stack_pop( struct lfds700_stack_state *ss,
                       struct lfds700_stack_element **se,
                       struct lfds700_misc_prng_state *ps );

void lfds700_stack_query( struct lfds700_stack_state *ss,
                          enum lfds700_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 lfds700_stack_init_valid_on_current_logical_core to initialize a struct lfds700_stack_state, and then calls lfds700_stack_push and lfds700_stack_pop to push and pop struct lfds700_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 LFDS700_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 lfds700_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 lfds700_stack_element, and this is used when calling lfds700_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, lfds700_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 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 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 lfds700_stack_cleanup has returned. Typical usage is to return popped stack elements to a freelist.

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 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.

Example

#include <stdio.h>
#include "liblfds700.h"

struct test_data
{
  struct lfds700_stack_element
    se;

  int long long unsigned
    user_id;
};

int main()
{
  int long long unsigned
    loop;

  struct lfds700_misc_prng_state
    ps;

  struct lfds700_stack_element
    *se;

  struct lfds700_stack_state
    ss;

  struct test_data
    *td,
    *temp_td;

  lfds700_misc_library_init_valid_on_current_logical_core();

  lfds700_misc_prng_init( &ps );

  lfds700_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;

    LFDS700_STACK_SET_VALUE_IN_ELEMENT( td[loop].se, &td[loop] );
    lfds700_stack_push( &ss, &td[loop].se, &ps );
  }  

  for( loop = 0 ; loop < 10 ; loop++ )
  {
    lfds700_stack_pop( &ss, &se );
    temp_td = LFDS700_STACK_GET_VALUE_FROM_ELEMENT( se );

    print( "user_id = %llu\n", temp_td->user_id );
  }

  lfds700_stack_cleanup( &ss, NULL );

  free( td );

  lfds700_misc_library_cleanup();

  return( EXIT_SUCCESS );
}

See Also