← Back to branch summary

~ubuntu-branches/ubuntu/quantal/libgc/quantal

« back to all changes in this revision

Viewing changes to libatomic_ops-1.2/doc/README_stack.txt

  • Committer: Bazaar Package Importer
  • Author(s): Christoph Egger
  • Date: 2011-03-02 13:43:18 UTC
  • mfrom: (1.2.5 upstream) (3.1.6 sid)
  • Revision ID: james.westby@ubuntu.com-20110302134318-82ful0us5ce82qe8
Tags: 1:7.1-7
http://bugs.debian.org/615469
http://bugs.debian.org/614744
* Add ppc64 symbol file (Closes: #615469)
* Add sh4 symbol file (Closes: #614744)
* Add armhf symbol file
* Add powerpcspe symbol file
* Handle sparc64 the same as sparc
* Clear non-arch symbol file to support building on not yet captured
  architectures
* add -pthread to fix build with --no-add-needed

Show diffs side-by-side

added added

removed removed

Lines of Context:
libatomic_ops-1.2/doc/README_stack.txt
 
1
Note that the AO_stack implementation is licensed under the GPL,
 
2
unlike the lower level routines.
 
3
 
 
4
The header file atomic_ops_stack.h defines a linked stack abstraction.
 
5
Stacks may be accessed by multiple concurrent threads.  The implementation
 
6
is 1-lock-free, i.e. it will continue to make progress if at most one
 
7
thread becomes inactive while operating on the data structure.
 
8
 
 
9
(The implementation can be built to be N-lock-free for any given N.  But that
 
10
seems to rarely be useful, especially since larger N involve some slowdown.)
 
11
 
 
12
This makes it safe to access these data structures from non-reentrant
 
13
signal handlers, provided at most one non-signal-handler thread is
 
14
accessing the data structure at once.  This latter condition can be
 
15
ensured by acquiring an ordinary lock around the non-hndler accesses
 
16
to the data structure.
 
17
 
 
18
For details see:
 
19
 
 
20
Hans-J. Boehm, "An Almost Non-Blocking Stack", PODC 2004,
 
21
http://portal.acm.org/citation.cfm?doid=1011767.1011774, or
 
22
http://www.hpl.hp.com/techreports/2004/HPL-2004-105.html
 
23
(This is not exactly the implementation described there, since the
 
24
interface was cleaned up in the interim.  But it should perform
 
25
very similarly.)
 
26
 
 
27
We use a fully lock-free implementation when the underlying hardware
 
28
makes that less expensive, i.e. when we have a double-wide compare-and-swap
 
29
operation available.  (The fully lock-free implementation uses an AO_t-
 
30
sized version count, and assumes it does not wrap during the time any
 
31
given operation is active.  This seems reasonably safe on 32-bit hardware,
 
32
and very safe on 64-bit hardware.) If a fully lock-free implementation
 
33
is used, the macro AO_STACK_IS_LOCK_FREE will be defined.
 
34
 
 
35
The implementation is interesting only because it allows reuse of
 
36
existing nodes.  This is necessary, for example, to implement a memory
 
37
allocator.
 
38
 
 
39
Since we want to leave the precise stack node type up to the client,
 
40
we insist only that each stack node contains a link field of type AO_t.
 
41
When a new node is pushed on the stack, the push operation expects to be
 
42
passed the pointer to this link field, which will then be overwritten by
 
43
this link field.  Similarly, the pop operation returns a pointer to the
 
44
link field of the object that previously was on the top of the stack.
 
45
 
 
46
The cleanest way to use these routines is probably to define the stack node
 
47
type with an initial AO_t link field, so that the conversion between the
 
48
link-field pointer and the stack element pointer is just a compile-time
 
49
cast.  But other possibilities exist.  (This would be cleaner in C++ with
 
50
templates.)
 
51
 
 
52
A stack is represented by an AO_stack_t structure.  (This is normally
 
53
2 or 3 times the size of a pointer.)  It may be statically initialized
 
54
by setting it to AO_STACK_INITIALIZER, or dynamically initialized to
 
55
an empty stack with AO_stack_init.  There are only three operations for
 
56
accessing stacks:
 
57
 
 
58
void AO_stack_init(AO_stack_t *list);
 
59
void AO_stack_push_release(AO_stack_t *list, AO_t *new_element);
 
60
AO_t * AO_stack_pop_acquire(volatile AO_stack_t *list);
 
61
 
 
62
We require that the objects pushed as list elements remain addressable
 
63
as long as any push or pop operation are in progress.  (It is OK for an object
 
64
to be "pop"ped off a stack and "deallocated" with a concurrent "pop" on
 
65
the same stack still in progress, but only if "deallocation" leaves the
 
66
object addressable.  The second "pop" may still read the object, but
 
67
the value it reads will not matter.)
 
68
 
 
69
We require that the headers (AO_stack objects) remain allocated and
 
70
valid as long as any operations on them are still in-flight.
 
71
 
 
72
We also provide macros AO_REAL_HEAD_PTR that converts an AO_stack_t
 
73
to a pointer to the link field in the next element, and AO_REAL_NEXT_PTR
 
74
that converts a link field to a real, dereferencable, pointer to the link field
 
75
in the next element.  This is intended only for debugging, or to traverse
 
76
the list after modification has ceased.  There is otherwise no guarantee that
 
77
walking a stack using this macro will produce any kind of consistent
 
78
picture of the data structure.