2 * The implementation of the routines described here is covered by the GPL.
3 * This header file is covered by the following license:
7 * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
9 * Permission is hereby granted, free of charge, to any person obtaining a copy
10 * of this software and associated documentation files (the "Software"), to deal
11 * in the Software without restriction, including without limitation the rights
12 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 * copies of the Software, and to permit persons to whom the Software is
14 * furnished to do so, subject to the following conditions:
16 * The above copyright notice and this permission notice shall be included in
17 * all copies or substantial portions of the Software.
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28 /* Almost lock-free LIFO linked lists (linked stacks). */
32 #include "atomic_ops.h"
34 #if !defined(AO_HAVE_compare_double_and_swap_double) \
35 && !defined(AO_HAVE_compare_double_and_swap) \
36 && defined(AO_HAVE_compare_and_swap)
37 # define AO_USE_ALMOST_LOCK_FREE
39 /* If we have no compare-and-swap operation defined, we assume */
40 /* that we will actually be using CAS emulation. If we do that, */
41 /* it's cheaper to use the version-based implementation. */
42 # define AO_STACK_IS_LOCK_FREE
46 * These are not guaranteed to be completely lock-free.
47 * List insertion may spin under extremely unlikely conditions.
48 * It cannot deadlock due to recursive reentry unless AO_list_remove
49 * is called while at least AO_BL_SIZE activations of
50 * AO_list_remove are currently active in the same thread, i.e.
51 * we must have at least AO_BL_SIZE recursive signal handler
54 * All operations take an AO_list_aux argument. It is safe to
55 * share a single AO_list_aux structure among all lists, but that
56 * may increase contention. Any given list must always be accessed
57 * with the same AO_list_aux structure.
59 * We make some machine-dependent assumptions:
60 * - We have a compare-and-swap operation.
61 * - At least _AO_N_BITS low order bits in pointers are
62 * zero and normally unused.
63 * - size_t and pointers have the same size.
65 * We do use a fully lock-free implementation if double-width
66 * compare-and-swap operations are available.
69 #ifdef AO_USE_ALMOST_LOCK_FREE
70 /* The number of low order pointer bits we can use for a small */
72 # if defined(__LP64__) || defined(_LP64) || defined(_WIN64)
73 /* WIN64 isn't really supported yet. */
79 # define AO_BIT_MASK ((1 << AO_N_BITS) - 1)
81 * AO_stack_aux should be treated as opaque.
82 * It is fully defined here, so it can be allocated, and to facilitate
89 #if AO_BL_SIZE > (1 << AO_N_BITS)
90 # error AO_BL_SIZE too big
93 typedef struct AO__stack_aux {
94 volatile AO_t AO_stack_bl[AO_BL_SIZE];
97 /* The stack implementation knows only about the lecation of */
98 /* link fields in nodes, and nothing about the rest of the */
99 /* stack elements. Link fields hold an AO_t, which is not */
100 /* necessarily a real pointer. This converts the AO_t to a */
101 /* real (AO_t *) which is either o, or points at the link */
102 /* field in the next node. */
103 #define AO_REAL_NEXT_PTR(x) (AO_t *)((x) & ~AO_BIT_MASK)
105 /* The following two routines should not normally be used directly. */
106 /* We make them visible here for the rare cases in which it makes sense */
107 /* to share the an AO_stack_aux between stacks. */
109 AO_stack_push_explicit_aux_release(volatile AO_t *list, AO_t *x,
113 AO_stack_pop_explicit_aux_acquire(volatile AO_t *list, AO_stack_aux *);
115 /* And now AO_stack_t for the real interface: */
117 typedef struct AO__stack {
118 volatile AO_t AO_ptr;
122 #define AO_STACK_INITIALIZER {0}
124 AO_INLINE void AO_stack_init(AO_stack_t *list)
127 list -> AO_aux.AO_stack_bl[0] = 0;
128 list -> AO_aux.AO_stack_bl[1] = 0;
131 for (i = 0; i < AO_BL_SIZE; ++i)
132 list -> AO_aux.AO_stack_bl[i] = 0;
137 /* Convert an AO_stack_t to a pointer to the link field in */
138 /* the first element. */
139 #define AO_REAL_HEAD_PTR(x) AO_REAL_NEXT_PTR((x).AO_ptr)
141 #define AO_stack_push_release(l, e) \
142 AO_stack_push_explicit_aux_release(&((l)->AO_ptr), e, &((l)->AO_aux))
143 #define AO_HAVE_stack_push_release
145 #define AO_stack_pop_acquire(l) \
146 AO_stack_pop_explicit_aux_acquire(&((l)->AO_ptr), &((l)->AO_aux))
147 #define AO_HAVE_stack_pop_acquire
149 # else /* Use fully non-blocking data structure, wide CAS */
151 #ifndef AO_HAVE_double_t
152 /* Can happen if we're using CAS emulation, since we don't want to */
153 /* force that here, in case other atomic_ops clients don't want it. */
154 # include "atomic_ops/sysdeps/standard_ao_double_t.h"
157 typedef volatile AO_double_t AO_stack_t;
158 /* AO_val1 is version, AO_val2 is pointer. */
160 #define AO_STACK_INITIALIZER {0}
162 AO_INLINE void AO_stack_init(AO_stack_t *list)
168 #define AO_REAL_HEAD_PTR(x) (AO_t *)((x).AO_val2)
169 #define AO_REAL_NEXT_PTR(x) (AO_t *)(x)
171 void AO_stack_push_release(AO_stack_t *list, AO_t *new_element);
172 #define AO_HAVE_stack_push_release
173 AO_t * AO_stack_pop_acquire(AO_stack_t *list);
174 #define AO_HAVE_stack_pop_acquire
176 #endif /* Wide CAS case */
178 #if defined(AO_HAVE_stack_push_release) && !defined(AO_HAVE_stack_push)
179 # define AO_stack_push(l, e) AO_stack_push_release(l, e)
180 # define AO_HAVE_stack_push
183 #if defined(AO_HAVE_stack_pop_acquire) && !defined(AO_HAVE_stack_pop)
184 # define AO_stack_pop(l) AO_stack_pop_acquire(l)
185 # define AO_HAVE_stack_pop
188 #endif /* !AO_STACK_H */