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

Ian Wienand                                       June 2, 2005                                LIBATOMIC-STACK(3)