NAME

       libatomic-stack - Library providing linked stack abstraction

SYNOPSIS

       #include <atomic_ops_stack.h>

       cc ... -latomic_ops_gpl

       Note  that  the  AO_stack implementation is licensed under the GPL, unlike the lower level
       routines.

       void AO_stack_init(AO_stack_t *list);
       void AO_stack_push_release(AO_stack_t *list, AO_t *new_element);
       AO_t * AO_stack_pop_acquire(volatile AO_stack_t *list);

DESCRIPTION

       libatomic-stack defines a linked stack abstraction.  Stacks may be  accessed  by  multiple
       concurrent  threads.   The  implementation  is  1-lock-free, i.e. it will continue to make
       progress if at most one thread becomes inactive while operating on the data structure.

       This makes it safe to access these data structures  from  non-reentrant  signal  handlers,
       provided  at  most  one non-signal-handler thread is accessing the data structure at once.
       This latter condition can be ensured by acquiring an ordinary lock around  the  non-hndler
       accesses to the data structure.

       We  use  a  fully  lock-free  implementation  when the underlying hardware makes that less
       expensive, i.e. when we have a double-wide  compare-and-swap  operation  available.   (The
       fully  lock-free implementation uses an AO_t- sized version count, and assumes it does not
       wrap during the time any given operation is active.  This seems reasonably safe on  32-bit
       hardware,  and very safe on 64-bit hardware.) If a fully lock-free implementation is used,
       the macro AO_STACK_IS_LOCK_FREE will be defined.

       The cleanest way to use these routines is probably to define the stack node type  with  an
       initial  AO_t  link  field,  so that the conversion between the link-field pointer and the
       stack element pointer is just a compile-time cast.  But other possibilities exist.   (This
       would be cleaner in C++ with templates.)

       A  stack  is  represented  by an AO_stack_t structure.  (This is normally 2 or 3 times the
       size  of  a  pointer.)   It   may   be   statically   initialized   by   setting   it   to
       AO_STACK_INITIALIZER  ,  or dynamically initialized to an empty stack with AO_stack_init .
       There are only three operations for accessing stacks:

       AO_stack_init
              Initalise a stack

       AO_stack_push_release
              Push new element onto the stack.

       AO_stack_pop_acquire
              Pop element off the stack.

       We require that the objects pushed as list elements remain addressable as long as any push
       or  pop operation are in progress.  (It is OK for an object to be "pop"ped off a stack and
       "deallocated" with a concurrent "pop" on the same stack still in  progress,  but  only  if
       "deallocation" leaves the object addressable.  The second "pop" may still read the object,
       but the value it reads will not matter.)

       We require that the headers ( AO_stack objects) remain allocated and valid as long as  any
       operations on them are still in-flight.

       We  also  provide  macros AO_REAL_HEAD_PTR that converts an AO_stack_t to a pointer to the
       link field in the next element, and AO_REAL_NEXT_PTR that converts a link field to a real,
       dereferencable,  pointer to the link field in the next element.  This is intended only for
       debugging, or to traverse the list after modification has ceased.  There is  otherwise  no
       guarantee  that  walking  a  stack  using  this  macro will produce any kind of consistent
       picture of the data structure.

SEE ALSO

       libatomic-ops(3), libatomic-malloc(3)

AUTHOR

       This manual page was written by Ian Wienand <ianw@gelato.unsw.edu.au>, based  on  comments
       in the source code.  It was written for the Debian project (but may be used by others).