Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 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. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 46 | struct lockfree_node_contents { |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 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 */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 62 | typedef union lockfree_node { |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 63 | gpr_atm atm; |
| 64 | struct lockfree_node_contents contents; |
| 65 | } lockfree_node; |
| 66 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 67 | #define ENTRY_ALIGNMENT_BITS 3 /* make sure that entries aligned to 8-bytes */ |
Craig Tiller | e0981df | 2015-07-16 08:45:15 -0700 | [diff] [blame] | 68 | #define INVALID_ENTRY_INDEX \ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 69 | ((1 << 16) - 1) /* reserve this entry as invalid \ |
Craig Tiller | 565b18b | 2015-09-23 10:09:42 -0700 | [diff] [blame^] | 70 | */ |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 71 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 72 | struct gpr_stack_lockfree { |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 73 | lockfree_node *entries; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 74 | lockfree_node head; /* An atomic entry describing curr head */ |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 75 | |
| 76 | #ifndef NDEBUG |
| 77 | /* Bitmap of pushed entries to check for double-push or pop */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 78 | gpr_atm pushed[(INVALID_ENTRY_INDEX + 1) / (8 * sizeof(gpr_atm))]; |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 79 | #endif |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 80 | }; |
| 81 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 82 | gpr_stack_lockfree *gpr_stack_lockfree_create(size_t entries) { |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 83 | gpr_stack_lockfree *stack; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 84 | stack = gpr_malloc(sizeof(*stack)); |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 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 */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 88 | GPR_ASSERT(entries < INVALID_ENTRY_INDEX); |
| 89 | stack->entries = gpr_malloc_aligned(entries * sizeof(stack->entries[0]), |
| 90 | ENTRY_ALIGNMENT_BITS); |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 91 | /* Clear out all entries */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 92 | memset(stack->entries, 0, entries * sizeof(stack->entries[0])); |
| 93 | memset(&stack->head, 0, sizeof(stack->head)); |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 94 | #ifndef NDEBUG |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 95 | memset(&stack->pushed, 0, sizeof(stack->pushed)); |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 96 | #endif |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 97 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 98 | GPR_ASSERT(sizeof(stack->entries->atm) == sizeof(stack->entries->contents)); |
Craig Tiller | 42b6c93 | 2015-07-30 09:59:25 -0700 | [diff] [blame] | 99 | |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 100 | /* Point the head at reserved dummy entry */ |
| 101 | stack->head.contents.index = INVALID_ENTRY_INDEX; |
| 102 | return stack; |
| 103 | } |
| 104 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 105 | void gpr_stack_lockfree_destroy(gpr_stack_lockfree *stack) { |
| 106 | gpr_free_aligned(stack->entries); |
| 107 | gpr_free(stack); |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 108 | } |
| 109 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 110 | int gpr_stack_lockfree_push(gpr_stack_lockfree *stack, int entry) { |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 111 | lockfree_node head; |
| 112 | lockfree_node newhead; |
Craig Tiller | 42b6c93 | 2015-07-30 09:59:25 -0700 | [diff] [blame] | 113 | lockfree_node curent; |
| 114 | lockfree_node newent; |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 115 | |
| 116 | /* First fill in the entry's index and aba ctr for new head */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 117 | newhead.contents.index = (gpr_uint16)entry; |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 118 | /* Also post-increment the aba_ctr */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 119 | curent.atm = gpr_atm_no_barrier_load(&stack->entries[entry].atm); |
Craig Tiller | 42b6c93 | 2015-07-30 09:59:25 -0700 | [diff] [blame] | 120 | newhead.contents.aba_ctr = ++curent.contents.aba_ctr; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 121 | gpr_atm_no_barrier_store(&stack->entries[entry].atm, curent.atm); |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 122 | |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 123 | #ifndef NDEBUG |
| 124 | /* Check for double push */ |
| 125 | { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 126 | int pushed_index = entry / (int)(8 * sizeof(gpr_atm)); |
| 127 | int pushed_bit = entry % (int)(8 * sizeof(gpr_atm)); |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 128 | gpr_atm old_val; |
| 129 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 130 | old_val = gpr_atm_no_barrier_fetch_add(&stack->pushed[pushed_index], |
| 131 | (gpr_atm)(1UL << pushed_bit)); |
| 132 | GPR_ASSERT((old_val & (gpr_atm)(1UL << pushed_bit)) == 0); |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 133 | } |
| 134 | #endif |
| 135 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 136 | do { |
| 137 | /* Atomically get the existing head value for use */ |
| 138 | head.atm = gpr_atm_no_barrier_load(&(stack->head.atm)); |
| 139 | /* Point to it */ |
| 140 | newent.atm = gpr_atm_no_barrier_load(&stack->entries[entry].atm); |
| 141 | newent.contents.index = head.contents.index; |
| 142 | gpr_atm_no_barrier_store(&stack->entries[entry].atm, newent.atm); |
| 143 | } while (!gpr_atm_rel_cas(&(stack->head.atm), head.atm, newhead.atm)); |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 144 | /* Use rel_cas above to make sure that entry index is set properly */ |
Craig Tiller | ffe27b9 | 2015-07-13 16:37:15 -0700 | [diff] [blame] | 145 | return head.contents.index == INVALID_ENTRY_INDEX; |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 146 | } |
| 147 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 148 | int gpr_stack_lockfree_pop(gpr_stack_lockfree *stack) { |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 149 | lockfree_node head; |
| 150 | lockfree_node newhead; |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 151 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 152 | do { |
| 153 | head.atm = gpr_atm_acq_load(&(stack->head.atm)); |
| 154 | if (head.contents.index == INVALID_ENTRY_INDEX) { |
| 155 | return -1; |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 156 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 157 | newhead.atm = |
| 158 | gpr_atm_no_barrier_load(&(stack->entries[head.contents.index].atm)); |
| 159 | |
| 160 | } while (!gpr_atm_no_barrier_cas(&(stack->head.atm), head.atm, newhead.atm)); |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 161 | #ifndef NDEBUG |
| 162 | /* Check for valid pop */ |
| 163 | { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 164 | int pushed_index = head.contents.index / (8 * sizeof(gpr_atm)); |
| 165 | int pushed_bit = head.contents.index % (8 * sizeof(gpr_atm)); |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 166 | gpr_atm old_val; |
| 167 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 168 | old_val = gpr_atm_no_barrier_fetch_add(&stack->pushed[pushed_index], |
| 169 | -(gpr_atm)(1UL << pushed_bit)); |
| 170 | GPR_ASSERT((old_val & (gpr_atm)(1UL << pushed_bit)) != 0); |
vjpai | 6c22619 | 2015-07-22 14:34:58 -0700 | [diff] [blame] | 171 | } |
| 172 | #endif |
| 173 | |
Vijay Pai | 887f86b | 2015-07-10 17:12:10 -0700 | [diff] [blame] | 174 | return head.contents.index; |
Vijay Pai | 005e305 | 2015-07-10 15:18:45 -0700 | [diff] [blame] | 175 | } |