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_MCS_H 28309260Scognet#define CK_SPINLOCK_MCS_H 29309260Scognet 30309260Scognet#include <ck_cc.h> 31309260Scognet#include <ck_pr.h> 32309260Scognet#include <ck_stdbool.h> 33309260Scognet#include <ck_stddef.h> 34309260Scognet 35309260Scognet#ifndef CK_F_SPINLOCK_MCS 36309260Scognet#define CK_F_SPINLOCK_MCS 37309260Scognet 38309260Scognetstruct ck_spinlock_mcs { 39309260Scognet unsigned int locked; 40309260Scognet struct ck_spinlock_mcs *next; 41309260Scognet}; 42309260Scognettypedef struct ck_spinlock_mcs * ck_spinlock_mcs_t; 43309260Scognettypedef struct ck_spinlock_mcs ck_spinlock_mcs_context_t; 44309260Scognet 45309260Scognet#define CK_SPINLOCK_MCS_INITIALIZER (NULL) 46309260Scognet 47309260ScognetCK_CC_INLINE static void 48309260Scognetck_spinlock_mcs_init(struct ck_spinlock_mcs **queue) 49309260Scognet{ 50309260Scognet 51309260Scognet *queue = NULL; 52309260Scognet ck_pr_barrier(); 53309260Scognet return; 54309260Scognet} 55309260Scognet 56309260ScognetCK_CC_INLINE static bool 57309260Scognetck_spinlock_mcs_trylock(struct ck_spinlock_mcs **queue, 58309260Scognet struct ck_spinlock_mcs *node) 59309260Scognet{ 60309260Scognet bool r; 61309260Scognet 62309260Scognet node->locked = true; 63309260Scognet node->next = NULL; 64309260Scognet ck_pr_fence_store_atomic(); 65309260Scognet 66309260Scognet r = ck_pr_cas_ptr(queue, NULL, node); 67309260Scognet ck_pr_fence_lock(); 68309260Scognet return r; 69309260Scognet} 70309260Scognet 71309260ScognetCK_CC_INLINE static bool 72309260Scognetck_spinlock_mcs_locked(struct ck_spinlock_mcs **queue) 73309260Scognet{ 74309260Scognet bool r; 75309260Scognet 76309260Scognet r = ck_pr_load_ptr(queue) != NULL; 77309260Scognet ck_pr_fence_acquire(); 78309260Scognet return r; 79309260Scognet} 80309260Scognet 81309260ScognetCK_CC_INLINE static void 82309260Scognetck_spinlock_mcs_lock(struct ck_spinlock_mcs **queue, 83309260Scognet struct ck_spinlock_mcs *node) 84309260Scognet{ 85309260Scognet struct ck_spinlock_mcs *previous; 86309260Scognet 87309260Scognet /* 88309260Scognet * In the case that there is a successor, let them know they must 89309260Scognet * wait for us to unlock. 90309260Scognet */ 91309260Scognet node->locked = true; 92309260Scognet node->next = NULL; 93309260Scognet ck_pr_fence_store_atomic(); 94309260Scognet 95309260Scognet /* 96309260Scognet * Swap current tail with current lock request. If the swap operation 97309260Scognet * returns NULL, it means the queue was empty. If the queue was empty, 98309260Scognet * then the operation is complete. 99309260Scognet */ 100309260Scognet previous = ck_pr_fas_ptr(queue, node); 101309260Scognet if (previous != NULL) { 102309260Scognet /* 103309260Scognet * Let the previous lock holder know that we are waiting on 104309260Scognet * them. 105309260Scognet */ 106309260Scognet ck_pr_store_ptr(&previous->next, node); 107309260Scognet while (ck_pr_load_uint(&node->locked) == true) 108309260Scognet ck_pr_stall(); 109309260Scognet } 110309260Scognet 111309260Scognet ck_pr_fence_lock(); 112309260Scognet return; 113309260Scognet} 114309260Scognet 115309260ScognetCK_CC_INLINE static void 116309260Scognetck_spinlock_mcs_unlock(struct ck_spinlock_mcs **queue, 117309260Scognet struct ck_spinlock_mcs *node) 118309260Scognet{ 119309260Scognet struct ck_spinlock_mcs *next; 120309260Scognet 121309260Scognet ck_pr_fence_unlock(); 122309260Scognet 123309260Scognet next = ck_pr_load_ptr(&node->next); 124309260Scognet if (next == NULL) { 125309260Scognet /* 126309260Scognet * If there is no request following us then it is a possibilty 127309260Scognet * that we are the current tail. In this case, we may just 128309260Scognet * mark the spinlock queue as empty. 129309260Scognet */ 130309260Scognet if (ck_pr_load_ptr(queue) == node && 131309260Scognet ck_pr_cas_ptr(queue, node, NULL) == true) { 132309260Scognet return; 133309260Scognet } 134309260Scognet 135309260Scognet /* 136309260Scognet * If the node is not the current tail then a lock operation 137309260Scognet * is in-progress. In this case, busy-wait until the queue is 138309260Scognet * in a consistent state to wake up the incoming lock 139309260Scognet * request. 140309260Scognet */ 141309260Scognet for (;;) { 142309260Scognet next = ck_pr_load_ptr(&node->next); 143309260Scognet if (next != NULL) 144309260Scognet break; 145309260Scognet 146309260Scognet ck_pr_stall(); 147309260Scognet } 148309260Scognet } 149309260Scognet 150309260Scognet /* Allow the next lock operation to complete. */ 151309260Scognet ck_pr_store_uint(&next->locked, false); 152309260Scognet return; 153309260Scognet} 154309260Scognet#endif /* CK_F_SPINLOCK_MCS */ 155309260Scognet#endif /* CK_SPINLOCK_MCS_H */ 156