1309260Scognet/* 2309260Scognet * Copyright 2010-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_SPINLOCK_ANDERSON_H 28309260Scognet#define CK_SPINLOCK_ANDERSON_H 29309260Scognet 30309260Scognet#include <ck_cc.h> 31309260Scognet#include <ck_limits.h> 32309260Scognet#include <ck_md.h> 33309260Scognet#include <ck_pr.h> 34309260Scognet#include <ck_stdbool.h> 35309260Scognet 36309260Scognet#ifndef CK_F_SPINLOCK_ANDERSON 37309260Scognet#define CK_F_SPINLOCK_ANDERSON 38309260Scognet/* 39309260Scognet * This is an implementation of Anderson's array-based queuing lock. 40309260Scognet */ 41309260Scognetstruct ck_spinlock_anderson_thread { 42309260Scognet unsigned int locked; 43309260Scognet unsigned int position; 44309260Scognet}; 45309260Scognettypedef struct ck_spinlock_anderson_thread ck_spinlock_anderson_thread_t; 46309260Scognet 47309260Scognetstruct ck_spinlock_anderson { 48309260Scognet struct ck_spinlock_anderson_thread *slots; 49309260Scognet unsigned int count; 50309260Scognet unsigned int wrap; 51309260Scognet unsigned int mask; 52309260Scognet char pad[CK_MD_CACHELINE - sizeof(unsigned int) * 3 - sizeof(void *)]; 53309260Scognet unsigned int next; 54309260Scognet}; 55309260Scognettypedef struct ck_spinlock_anderson ck_spinlock_anderson_t; 56309260Scognet 57309260ScognetCK_CC_INLINE static void 58309260Scognetck_spinlock_anderson_init(struct ck_spinlock_anderson *lock, 59309260Scognet struct ck_spinlock_anderson_thread *slots, 60309260Scognet unsigned int count) 61309260Scognet{ 62309260Scognet unsigned int i; 63309260Scognet 64309260Scognet slots[0].locked = false; 65309260Scognet slots[0].position = 0; 66309260Scognet for (i = 1; i < count; i++) { 67309260Scognet slots[i].locked = true; 68309260Scognet slots[i].position = i; 69309260Scognet } 70309260Scognet 71309260Scognet lock->slots = slots; 72309260Scognet lock->count = count; 73309260Scognet lock->mask = count - 1; 74309260Scognet lock->next = 0; 75309260Scognet 76309260Scognet /* 77309260Scognet * If the number of threads is not a power of two then compute 78309260Scognet * appropriate wrap-around value in the case of next slot counter 79309260Scognet * overflow. 80309260Scognet */ 81309260Scognet if (count & (count - 1)) 82309260Scognet lock->wrap = (UINT_MAX % count) + 1; 83309260Scognet else 84309260Scognet lock->wrap = 0; 85309260Scognet 86309260Scognet ck_pr_barrier(); 87309260Scognet return; 88309260Scognet} 89309260Scognet 90309260ScognetCK_CC_INLINE static bool 91309260Scognetck_spinlock_anderson_locked(struct ck_spinlock_anderson *lock) 92309260Scognet{ 93309260Scognet unsigned int position; 94309260Scognet bool r; 95309260Scognet 96309260Scognet position = ck_pr_load_uint(&lock->next) & lock->mask; 97309260Scognet r = ck_pr_load_uint(&lock->slots[position].locked); 98309260Scognet ck_pr_fence_acquire(); 99309260Scognet return r; 100309260Scognet} 101309260Scognet 102309260ScognetCK_CC_INLINE static void 103309260Scognetck_spinlock_anderson_lock(struct ck_spinlock_anderson *lock, 104309260Scognet struct ck_spinlock_anderson_thread **slot) 105309260Scognet{ 106309260Scognet unsigned int position, next; 107309260Scognet unsigned int count = lock->count; 108309260Scognet 109309260Scognet /* 110309260Scognet * If count is not a power of 2, then it is possible for an overflow 111309260Scognet * to reallocate beginning slots to more than one thread. To avoid this 112309260Scognet * use a compare-and-swap. 113309260Scognet */ 114309260Scognet if (lock->wrap != 0) { 115309260Scognet position = ck_pr_load_uint(&lock->next); 116309260Scognet 117309260Scognet do { 118309260Scognet if (position == UINT_MAX) 119309260Scognet next = lock->wrap; 120309260Scognet else 121309260Scognet next = position + 1; 122309260Scognet } while (ck_pr_cas_uint_value(&lock->next, position, 123309260Scognet next, &position) == false); 124309260Scognet 125309260Scognet position %= count; 126309260Scognet } else { 127309260Scognet position = ck_pr_faa_uint(&lock->next, 1); 128309260Scognet position &= lock->mask; 129309260Scognet } 130309260Scognet 131309260Scognet /* Serialize with respect to previous thread's store. */ 132309260Scognet ck_pr_fence_load(); 133309260Scognet 134309260Scognet /* 135309260Scognet * Spin until slot is marked as unlocked. First slot is initialized to 136309260Scognet * false. 137309260Scognet */ 138309260Scognet while (ck_pr_load_uint(&lock->slots[position].locked) == true) 139309260Scognet ck_pr_stall(); 140309260Scognet 141309260Scognet /* Prepare slot for potential re-use by another thread. */ 142309260Scognet ck_pr_store_uint(&lock->slots[position].locked, true); 143309260Scognet ck_pr_fence_lock(); 144309260Scognet 145309260Scognet *slot = lock->slots + position; 146309260Scognet return; 147309260Scognet} 148309260Scognet 149309260ScognetCK_CC_INLINE static void 150309260Scognetck_spinlock_anderson_unlock(struct ck_spinlock_anderson *lock, 151309260Scognet struct ck_spinlock_anderson_thread *slot) 152309260Scognet{ 153309260Scognet unsigned int position; 154309260Scognet 155309260Scognet ck_pr_fence_unlock(); 156309260Scognet 157309260Scognet /* Mark next slot as available. */ 158309260Scognet if (lock->wrap == 0) 159309260Scognet position = (slot->position + 1) & lock->mask; 160309260Scognet else 161309260Scognet position = (slot->position + 1) % lock->count; 162309260Scognet 163309260Scognet ck_pr_store_uint(&lock->slots[position].locked, false); 164309260Scognet return; 165309260Scognet} 166309260Scognet#endif /* CK_F_SPINLOCK_ANDERSON */ 167309260Scognet#endif /* CK_SPINLOCK_ANDERSON_H */ 168