LIBATOMIC-STACK(3) LIBATOMIC-STACK(3)
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 ac-
cessed 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 ac-
cessing the data structure at once. This latter condition can be en-
sured 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 com-
pare-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 be-
tween 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 ob-
ject, 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 other-
wise 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)
Generated by dwww version 1.15 on Tue Jun 25 08:19:15 CEST 2024.