1309260Scognet/* 2309260Scognet * Copyright 2009-2015 Samy Al Bahra. 3309260Scognet * All rights reserved. 4309260Scognet * 5309260Scognet * Redistribution and use in source and binary forms, with or without 6309260Scognet * modification, are permitted provided that the following conditions 7309260Scognet * are met: 8309260Scognet * 1. Redistributions of source code must retain the above copyright 9309260Scognet * notice, this list of conditions and the following disclaimer. 10309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 11309260Scognet * notice, this list of conditions and the following disclaimer in the 12309260Scognet * documentation and/or other materials provided with the distribution. 13309260Scognet * 14309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24309260Scognet * SUCH DAMAGE. 25309260Scognet */ 26309260Scognet 27309260Scognet#ifndef CK_STACK_H 28309260Scognet#define CK_STACK_H 29309260Scognet 30309260Scognet#include <ck_cc.h> 31309260Scognet#include <ck_pr.h> 32309260Scognet#include <ck_stdbool.h> 33309260Scognet#include <ck_stddef.h> 34309260Scognet 35309260Scognetstruct ck_stack_entry { 36309260Scognet struct ck_stack_entry *next; 37309260Scognet}; 38309260Scognettypedef struct ck_stack_entry ck_stack_entry_t; 39309260Scognet 40309260Scognetstruct ck_stack { 41309260Scognet struct ck_stack_entry *head; 42309260Scognet char *generation CK_CC_PACKED; 43309260Scognet} CK_CC_ALIASED; 44309260Scognettypedef struct ck_stack ck_stack_t; 45309260Scognet 46309260Scognet#define CK_STACK_INITIALIZER { NULL, NULL } 47309260Scognet 48309260Scognet#ifndef CK_F_STACK_PUSH_UPMC 49309260Scognet#define CK_F_STACK_PUSH_UPMC 50309260Scognet/* 51309260Scognet * Stack producer operation safe for multiple unique producers and multiple consumers. 52309260Scognet */ 53309260ScognetCK_CC_INLINE static void 54309260Scognetck_stack_push_upmc(struct ck_stack *target, struct ck_stack_entry *entry) 55309260Scognet{ 56309260Scognet struct ck_stack_entry *stack; 57309260Scognet 58309260Scognet stack = ck_pr_load_ptr(&target->head); 59309260Scognet entry->next = stack; 60309260Scognet ck_pr_fence_store(); 61309260Scognet 62309260Scognet while (ck_pr_cas_ptr_value(&target->head, stack, entry, &stack) == false) { 63309260Scognet entry->next = stack; 64309260Scognet ck_pr_fence_store(); 65309260Scognet } 66309260Scognet 67309260Scognet return; 68309260Scognet} 69309260Scognet#endif /* CK_F_STACK_PUSH_UPMC */ 70309260Scognet 71309260Scognet#ifndef CK_F_STACK_TRYPUSH_UPMC 72309260Scognet#define CK_F_STACK_TRYPUSH_UPMC 73309260Scognet/* 74309260Scognet * Stack producer operation for multiple unique producers and multiple consumers. 75309260Scognet * Returns true on success and false on failure. 76309260Scognet */ 77309260ScognetCK_CC_INLINE static bool 78309260Scognetck_stack_trypush_upmc(struct ck_stack *target, struct ck_stack_entry *entry) 79309260Scognet{ 80309260Scognet struct ck_stack_entry *stack; 81309260Scognet 82309260Scognet stack = ck_pr_load_ptr(&target->head); 83309260Scognet entry->next = stack; 84309260Scognet ck_pr_fence_store(); 85309260Scognet 86309260Scognet return ck_pr_cas_ptr(&target->head, stack, entry); 87309260Scognet} 88309260Scognet#endif /* CK_F_STACK_TRYPUSH_UPMC */ 89309260Scognet 90309260Scognet#ifndef CK_F_STACK_POP_UPMC 91309260Scognet#define CK_F_STACK_POP_UPMC 92309260Scognet/* 93309260Scognet * Stack consumer operation safe for multiple unique producers and multiple consumers. 94309260Scognet */ 95309260ScognetCK_CC_INLINE static struct ck_stack_entry * 96309260Scognetck_stack_pop_upmc(struct ck_stack *target) 97309260Scognet{ 98309260Scognet struct ck_stack_entry *entry, *next; 99309260Scognet 100309260Scognet entry = ck_pr_load_ptr(&target->head); 101309260Scognet if (entry == NULL) 102309260Scognet return NULL; 103309260Scognet 104309260Scognet ck_pr_fence_load(); 105309260Scognet next = entry->next; 106309260Scognet while (ck_pr_cas_ptr_value(&target->head, entry, next, &entry) == false) { 107309260Scognet if (entry == NULL) 108309260Scognet break; 109309260Scognet 110309260Scognet ck_pr_fence_load(); 111309260Scognet next = entry->next; 112309260Scognet } 113309260Scognet 114309260Scognet return entry; 115309260Scognet} 116309260Scognet#endif 117309260Scognet 118309260Scognet#ifndef CK_F_STACK_TRYPOP_UPMC 119309260Scognet#define CK_F_STACK_TRYPOP_UPMC 120309260Scognet/* 121309260Scognet * Stack production operation for multiple unique producers and multiple consumers. 122309260Scognet * Returns true on success and false on failure. The value pointed to by the second 123309260Scognet * argument is set to a valid ck_stack_entry_t reference if true is returned. If 124309260Scognet * false is returned, then the value pointed to by the second argument is undefined. 125309260Scognet */ 126309260ScognetCK_CC_INLINE static bool 127309260Scognetck_stack_trypop_upmc(struct ck_stack *target, struct ck_stack_entry **r) 128309260Scognet{ 129309260Scognet struct ck_stack_entry *entry; 130309260Scognet 131309260Scognet entry = ck_pr_load_ptr(&target->head); 132309260Scognet if (entry == NULL) 133309260Scognet return false; 134309260Scognet 135309260Scognet ck_pr_fence_load(); 136309260Scognet if (ck_pr_cas_ptr(&target->head, entry, entry->next) == true) { 137309260Scognet *r = entry; 138309260Scognet return true; 139309260Scognet } 140309260Scognet 141309260Scognet return false; 142309260Scognet} 143309260Scognet#endif /* CK_F_STACK_TRYPOP_UPMC */ 144309260Scognet 145309260Scognet#ifndef CK_F_STACK_BATCH_POP_UPMC 146309260Scognet#define CK_F_STACK_BATCH_POP_UPMC 147309260Scognet/* 148309260Scognet * Pop all items off the stack. 149309260Scognet */ 150309260ScognetCK_CC_INLINE static struct ck_stack_entry * 151309260Scognetck_stack_batch_pop_upmc(struct ck_stack *target) 152309260Scognet{ 153309260Scognet struct ck_stack_entry *entry; 154309260Scognet 155309260Scognet entry = ck_pr_fas_ptr(&target->head, NULL); 156309260Scognet ck_pr_fence_load(); 157309260Scognet return entry; 158309260Scognet} 159309260Scognet#endif /* CK_F_STACK_BATCH_POP_UPMC */ 160309260Scognet 161309260Scognet#ifndef CK_F_STACK_PUSH_MPMC 162309260Scognet#define CK_F_STACK_PUSH_MPMC 163309260Scognet/* 164309260Scognet * Stack producer operation safe for multiple producers and multiple consumers. 165309260Scognet */ 166309260ScognetCK_CC_INLINE static void 167309260Scognetck_stack_push_mpmc(struct ck_stack *target, struct ck_stack_entry *entry) 168309260Scognet{ 169309260Scognet 170309260Scognet ck_stack_push_upmc(target, entry); 171309260Scognet return; 172309260Scognet} 173309260Scognet#endif /* CK_F_STACK_PUSH_MPMC */ 174309260Scognet 175309260Scognet#ifndef CK_F_STACK_TRYPUSH_MPMC 176309260Scognet#define CK_F_STACK_TRYPUSH_MPMC 177309260Scognet/* 178309260Scognet * Stack producer operation safe for multiple producers and multiple consumers. 179309260Scognet */ 180309260ScognetCK_CC_INLINE static bool 181309260Scognetck_stack_trypush_mpmc(struct ck_stack *target, struct ck_stack_entry *entry) 182309260Scognet{ 183309260Scognet 184309260Scognet return ck_stack_trypush_upmc(target, entry); 185309260Scognet} 186309260Scognet#endif /* CK_F_STACK_TRYPUSH_MPMC */ 187309260Scognet 188309260Scognet#ifdef CK_F_PR_CAS_PTR_2_VALUE 189309260Scognet#ifndef CK_F_STACK_POP_MPMC 190309260Scognet#define CK_F_STACK_POP_MPMC 191309260Scognet/* 192309260Scognet * Stack consumer operation safe for multiple producers and multiple consumers. 193309260Scognet */ 194309260ScognetCK_CC_INLINE static struct ck_stack_entry * 195309260Scognetck_stack_pop_mpmc(struct ck_stack *target) 196309260Scognet{ 197309260Scognet struct ck_stack original, update; 198309260Scognet 199309260Scognet original.generation = ck_pr_load_ptr(&target->generation); 200309260Scognet ck_pr_fence_load(); 201309260Scognet original.head = ck_pr_load_ptr(&target->head); 202309260Scognet if (original.head == NULL) 203309260Scognet return NULL; 204309260Scognet 205309260Scognet /* Order with respect to next pointer. */ 206309260Scognet ck_pr_fence_load(); 207309260Scognet 208309260Scognet update.generation = original.generation + 1; 209309260Scognet update.head = original.head->next; 210309260Scognet 211309260Scognet while (ck_pr_cas_ptr_2_value(target, &original, &update, &original) == false) { 212309260Scognet if (original.head == NULL) 213309260Scognet return NULL; 214309260Scognet 215309260Scognet update.generation = original.generation + 1; 216309260Scognet 217309260Scognet /* Order with respect to next pointer. */ 218309260Scognet ck_pr_fence_load(); 219309260Scognet update.head = original.head->next; 220309260Scognet } 221309260Scognet 222309260Scognet return original.head; 223309260Scognet} 224309260Scognet#endif /* CK_F_STACK_POP_MPMC */ 225309260Scognet 226309260Scognet#ifndef CK_F_STACK_TRYPOP_MPMC 227309260Scognet#define CK_F_STACK_TRYPOP_MPMC 228309260ScognetCK_CC_INLINE static bool 229309260Scognetck_stack_trypop_mpmc(struct ck_stack *target, struct ck_stack_entry **r) 230309260Scognet{ 231309260Scognet struct ck_stack original, update; 232309260Scognet 233309260Scognet original.generation = ck_pr_load_ptr(&target->generation); 234309260Scognet ck_pr_fence_load(); 235309260Scognet original.head = ck_pr_load_ptr(&target->head); 236309260Scognet if (original.head == NULL) 237309260Scognet return false; 238309260Scognet 239309260Scognet update.generation = original.generation + 1; 240309260Scognet ck_pr_fence_load(); 241309260Scognet update.head = original.head->next; 242309260Scognet 243309260Scognet if (ck_pr_cas_ptr_2_value(target, &original, &update, &original) == true) { 244309260Scognet *r = original.head; 245309260Scognet return true; 246309260Scognet } 247309260Scognet 248309260Scognet return false; 249309260Scognet} 250309260Scognet#endif /* CK_F_STACK_TRYPOP_MPMC */ 251309260Scognet#endif /* CK_F_PR_CAS_PTR_2_VALUE */ 252309260Scognet 253309260Scognet#ifndef CK_F_STACK_BATCH_POP_MPMC 254309260Scognet#define CK_F_STACK_BATCH_POP_MPMC 255309260Scognet/* 256309260Scognet * This is equivalent to the UP/MC version as NULL does not need a 257309260Scognet * a generation count. 258309260Scognet */ 259309260ScognetCK_CC_INLINE static struct ck_stack_entry * 260309260Scognetck_stack_batch_pop_mpmc(struct ck_stack *target) 261309260Scognet{ 262309260Scognet 263309260Scognet return ck_stack_batch_pop_upmc(target); 264309260Scognet} 265309260Scognet#endif /* CK_F_STACK_BATCH_POP_MPMC */ 266309260Scognet 267309260Scognet#ifndef CK_F_STACK_PUSH_MPNC 268309260Scognet#define CK_F_STACK_PUSH_MPNC 269309260Scognet/* 270309260Scognet * Stack producer operation safe with no concurrent consumers. 271309260Scognet */ 272309260ScognetCK_CC_INLINE static void 273309260Scognetck_stack_push_mpnc(struct ck_stack *target, struct ck_stack_entry *entry) 274309260Scognet{ 275309260Scognet struct ck_stack_entry *stack; 276309260Scognet 277309260Scognet entry->next = NULL; 278309260Scognet ck_pr_fence_store_atomic(); 279309260Scognet stack = ck_pr_fas_ptr(&target->head, entry); 280309260Scognet ck_pr_store_ptr(&entry->next, stack); 281309260Scognet ck_pr_fence_store(); 282309260Scognet 283309260Scognet return; 284309260Scognet} 285309260Scognet#endif /* CK_F_STACK_PUSH_MPNC */ 286309260Scognet 287309260Scognet/* 288309260Scognet * Stack producer operation for single producer and no concurrent consumers. 289309260Scognet */ 290309260ScognetCK_CC_INLINE static void 291309260Scognetck_stack_push_spnc(struct ck_stack *target, struct ck_stack_entry *entry) 292309260Scognet{ 293309260Scognet 294309260Scognet entry->next = target->head; 295309260Scognet target->head = entry; 296309260Scognet return; 297309260Scognet} 298309260Scognet 299309260Scognet/* 300309260Scognet * Stack consumer operation for no concurrent producers and single consumer. 301309260Scognet */ 302309260ScognetCK_CC_INLINE static struct ck_stack_entry * 303309260Scognetck_stack_pop_npsc(struct ck_stack *target) 304309260Scognet{ 305309260Scognet struct ck_stack_entry *n; 306309260Scognet 307309260Scognet if (target->head == NULL) 308309260Scognet return NULL; 309309260Scognet 310309260Scognet n = target->head; 311309260Scognet target->head = n->next; 312309260Scognet 313309260Scognet return n; 314309260Scognet} 315309260Scognet 316309260Scognet/* 317309260Scognet * Pop all items off a stack. 318309260Scognet */ 319309260ScognetCK_CC_INLINE static struct ck_stack_entry * 320309260Scognetck_stack_batch_pop_npsc(struct ck_stack *target) 321309260Scognet{ 322309260Scognet struct ck_stack_entry *n; 323309260Scognet 324309260Scognet n = target->head; 325309260Scognet target->head = NULL; 326309260Scognet 327309260Scognet return n; 328309260Scognet} 329309260Scognet 330309260Scognet/* 331309260Scognet * Stack initialization function. Guarantees initialization across processors. 332309260Scognet */ 333309260ScognetCK_CC_INLINE static void 334309260Scognetck_stack_init(struct ck_stack *stack) 335309260Scognet{ 336309260Scognet 337309260Scognet stack->head = NULL; 338309260Scognet stack->generation = NULL; 339309260Scognet return; 340309260Scognet} 341309260Scognet 342309260Scognet/* Defines a container_of functions for */ 343309260Scognet#define CK_STACK_CONTAINER(T, M, N) CK_CC_CONTAINER(ck_stack_entry_t, T, M, N) 344309260Scognet 345309260Scognet#define CK_STACK_ISEMPTY(m) ((m)->head == NULL) 346309260Scognet#define CK_STACK_FIRST(s) ((s)->head) 347309260Scognet#define CK_STACK_NEXT(m) ((m)->next) 348309260Scognet#define CK_STACK_FOREACH(stack, entry) \ 349309260Scognet for ((entry) = CK_STACK_FIRST(stack); \ 350309260Scognet (entry) != NULL; \ 351309260Scognet (entry) = CK_STACK_NEXT(entry)) 352309260Scognet#define CK_STACK_FOREACH_SAFE(stack, entry, T) \ 353309260Scognet for ((entry) = CK_STACK_FIRST(stack); \ 354309260Scognet (entry) != NULL && ((T) = (entry)->next, 1); \ 355309260Scognet (entry) = (T)) 356309260Scognet 357309260Scognet#endif /* CK_STACK_H */ 358