Man Linux: Main Page and Category List


       libatomic-stack - Library providing linked stack abstraction


       #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);


       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 accessing stacks:

              Initalise a stack

              Push new element onto the stack.

              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.


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


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