Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/support/stack_lockfree.h"
35 :
36 : #include <stdlib.h>
37 : #include <string.h>
38 :
39 : #include <grpc/support/port_platform.h>
40 : #include <grpc/support/alloc.h>
41 : #include <grpc/support/atm.h>
42 : #include <grpc/support/log.h>
43 :
44 : /* The lockfree node structure is a single architecture-level
45 : word that allows for an atomic CAS to set it up. */
46 : struct lockfree_node_contents {
47 : /* next thing to look at. Actual index for head, next index otherwise */
48 : gpr_uint16 index;
49 : #ifdef GPR_ARCH_64
50 : gpr_uint16 pad;
51 : gpr_uint32 aba_ctr;
52 : #else
53 : #ifdef GPR_ARCH_32
54 : gpr_uint16 aba_ctr;
55 : #else
56 : #error Unsupported bit width architecture
57 : #endif
58 : #endif
59 : };
60 :
61 : /* Use a union to make sure that these are in the same bits as an atm word */
62 : typedef union lockfree_node {
63 : gpr_atm atm;
64 : struct lockfree_node_contents contents;
65 : } lockfree_node;
66 :
67 : #define ENTRY_ALIGNMENT_BITS 3 /* make sure that entries aligned to 8-bytes */
68 : #define INVALID_ENTRY_INDEX \
69 : ((1 << 16) - 1) /* reserve this entry as invalid \
70 : */
71 :
72 : struct gpr_stack_lockfree {
73 : lockfree_node *entries;
74 : lockfree_node head; /* An atomic entry describing curr head */
75 :
76 : #ifndef NDEBUG
77 : /* Bitmap of pushed entries to check for double-push or pop */
78 : gpr_atm pushed[(INVALID_ENTRY_INDEX + 1) / (8 * sizeof(gpr_atm))];
79 : #endif
80 : };
81 :
82 8575 : gpr_stack_lockfree *gpr_stack_lockfree_create(size_t entries) {
83 : gpr_stack_lockfree *stack;
84 8575 : stack = gpr_malloc(sizeof(*stack));
85 : /* Since we only allocate 16 bits to represent an entry number,
86 : * make sure that we are within the desired range */
87 : /* Reserve the highest entry number as a dummy */
88 8575 : GPR_ASSERT(entries < INVALID_ENTRY_INDEX);
89 8575 : stack->entries = gpr_malloc_aligned(entries * sizeof(stack->entries[0]),
90 : ENTRY_ALIGNMENT_BITS);
91 : /* Clear out all entries */
92 8575 : memset(stack->entries, 0, entries * sizeof(stack->entries[0]));
93 8575 : memset(&stack->head, 0, sizeof(stack->head));
94 : #ifndef NDEBUG
95 8575 : memset(&stack->pushed, 0, sizeof(stack->pushed));
96 : #endif
97 :
98 : GPR_ASSERT(sizeof(stack->entries->atm) == sizeof(stack->entries->contents));
99 :
100 : /* Point the head at reserved dummy entry */
101 8575 : stack->head.contents.index = INVALID_ENTRY_INDEX;
102 8575 : return stack;
103 : }
104 :
105 8495 : void gpr_stack_lockfree_destroy(gpr_stack_lockfree *stack) {
106 8495 : gpr_free_aligned(stack->entries);
107 8495 : gpr_free(stack);
108 8495 : }
109 :
110 123821270 : int gpr_stack_lockfree_push(gpr_stack_lockfree *stack, int entry) {
111 : lockfree_node head;
112 : lockfree_node newhead;
113 : lockfree_node curent;
114 : lockfree_node newent;
115 :
116 : /* First fill in the entry's index and aba ctr for new head */
117 123821270 : newhead.contents.index = (gpr_uint16)entry;
118 : /* Also post-increment the aba_ctr */
119 123821270 : curent.atm = gpr_atm_no_barrier_load(&stack->entries[entry].atm);
120 123821270 : newhead.contents.aba_ctr = ++curent.contents.aba_ctr;
121 123821270 : gpr_atm_no_barrier_store(&stack->entries[entry].atm, curent.atm);
122 :
123 : #ifndef NDEBUG
124 : /* Check for double push */
125 : {
126 123821270 : int pushed_index = entry / (int)(8 * sizeof(gpr_atm));
127 123821270 : int pushed_bit = entry % (int)(8 * sizeof(gpr_atm));
128 : gpr_atm old_val;
129 :
130 123821270 : old_val = gpr_atm_no_barrier_fetch_add(&stack->pushed[pushed_index],
131 : (gpr_atm)(1UL << pushed_bit));
132 123821270 : GPR_ASSERT((old_val & (gpr_atm)(1UL << pushed_bit)) == 0);
133 : }
134 : #endif
135 :
136 : do {
137 : /* Atomically get the existing head value for use */
138 123824793 : head.atm = gpr_atm_no_barrier_load(&(stack->head.atm));
139 : /* Point to it */
140 123824793 : newent.atm = gpr_atm_no_barrier_load(&stack->entries[entry].atm);
141 123824793 : newent.contents.index = head.contents.index;
142 123824793 : gpr_atm_no_barrier_store(&stack->entries[entry].atm, newent.atm);
143 125168503 : } while (!gpr_atm_rel_cas(&(stack->head.atm), head.atm, newhead.atm));
144 : /* Use rel_cas above to make sure that entry index is set properly */
145 123834552 : return head.contents.index == INVALID_ENTRY_INDEX;
146 : }
147 :
148 8899775 : int gpr_stack_lockfree_pop(gpr_stack_lockfree *stack) {
149 : lockfree_node head;
150 : lockfree_node newhead;
151 :
152 : do {
153 8899775 : head.atm = gpr_atm_acq_load(&(stack->head.atm));
154 8899775 : if (head.contents.index == INVALID_ENTRY_INDEX) {
155 238254 : return -1;
156 : }
157 8661130 : newhead.atm =
158 8661352 : gpr_atm_no_barrier_load(&(stack->entries[head.contents.index].atm));
159 :
160 8661352 : } while (!gpr_atm_no_barrier_cas(&(stack->head.atm), head.atm, newhead.atm));
161 : #ifndef NDEBUG
162 : /* Check for valid pop */
163 : {
164 8655046 : int pushed_index = head.contents.index / (8 * sizeof(gpr_atm));
165 8655046 : int pushed_bit = head.contents.index % (8 * sizeof(gpr_atm));
166 : gpr_atm old_val;
167 :
168 8655046 : old_val = gpr_atm_no_barrier_fetch_add(&stack->pushed[pushed_index],
169 : -(gpr_atm)(1UL << pushed_bit));
170 8655046 : GPR_ASSERT((old_val & (gpr_atm)(1UL << pushed_bit)) != 0);
171 : }
172 : #endif
173 :
174 8655046 : return head.contents.index;
175 : }
|
