diff options
Diffstat (limited to 'include/spinlock/ticket.h')
| -rw-r--r-- | include/spinlock/ticket.h | 296 |
1 files changed, 296 insertions, 0 deletions
diff --git a/include/spinlock/ticket.h b/include/spinlock/ticket.h new file mode 100644 index 0000000..3358547 --- /dev/null +++ b/include/spinlock/ticket.h @@ -0,0 +1,296 @@ +/* + * Copyright 2010-2015 Samy Al Bahra. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef CK_SPINLOCK_TICKET_H +#define CK_SPINLOCK_TICKET_H + +#include <ck_backoff.h> +#include <ck_cc.h> +#include <ck_elide.h> +#include <ck_md.h> +#include <ck_pr.h> +#include <ck_stdbool.h> + +#ifndef CK_F_SPINLOCK_TICKET +#define CK_F_SPINLOCK_TICKET +/* + * If 16-bit or 32-bit increment is supported, implement support for + * trylock functionality on availability of 32-bit or 64-bit fetch-and-add + * and compare-and-swap. This code path is only applied to x86*. + */ +#if defined(CK_MD_TSO) && (defined(__x86__) || defined(__x86_64__)) +#if defined(CK_F_PR_FAA_32) && defined(CK_F_PR_INC_16) && defined(CK_F_PR_CAS_32) +#define CK_SPINLOCK_TICKET_TYPE uint32_t +#define CK_SPINLOCK_TICKET_TYPE_BASE uint16_t +#define CK_SPINLOCK_TICKET_INC(x) ck_pr_inc_16(x) +#define CK_SPINLOCK_TICKET_CAS(x, y, z) ck_pr_cas_32(x, y, z) +#define CK_SPINLOCK_TICKET_FAA(x, y) ck_pr_faa_32(x, y) +#define CK_SPINLOCK_TICKET_LOAD(x) ck_pr_load_32(x) +#define CK_SPINLOCK_TICKET_INCREMENT (0x00010000UL) +#define CK_SPINLOCK_TICKET_MASK (0xFFFFUL) +#define CK_SPINLOCK_TICKET_SHIFT (16) +#elif defined(CK_F_PR_FAA_64) && defined(CK_F_PR_INC_32) && defined(CK_F_PR_CAS_64) +#define CK_SPINLOCK_TICKET_TYPE uint64_t +#define CK_SPINLOCK_TICKET_TYPE_BASE uint32_t +#define CK_SPINLOCK_TICKET_INC(x) ck_pr_inc_32(x) +#define CK_SPINLOCK_TICKET_CAS(x, y, z) ck_pr_cas_64(x, y, z) +#define CK_SPINLOCK_TICKET_FAA(x, y) ck_pr_faa_64(x, y) +#define CK_SPINLOCK_TICKET_LOAD(x) ck_pr_load_64(x) +#define CK_SPINLOCK_TICKET_INCREMENT (0x0000000100000000ULL) +#define CK_SPINLOCK_TICKET_MASK (0xFFFFFFFFULL) +#define CK_SPINLOCK_TICKET_SHIFT (32) +#endif +#endif /* CK_MD_TSO */ + +#if defined(CK_SPINLOCK_TICKET_TYPE) +#define CK_F_SPINLOCK_TICKET_TRYLOCK + +struct ck_spinlock_ticket { + CK_SPINLOCK_TICKET_TYPE value; +}; +typedef struct ck_spinlock_ticket ck_spinlock_ticket_t; +#define CK_SPINLOCK_TICKET_INITIALIZER { .value = 0 } + +CK_CC_INLINE static void +ck_spinlock_ticket_init(struct ck_spinlock_ticket *ticket) +{ + + ticket->value = 0; + ck_pr_barrier(); + return; +} + +CK_CC_INLINE static bool +ck_spinlock_ticket_locked(struct ck_spinlock_ticket *ticket) +{ + CK_SPINLOCK_TICKET_TYPE request, position; + + request = CK_SPINLOCK_TICKET_LOAD(&ticket->value); + position = request & CK_SPINLOCK_TICKET_MASK; + request >>= CK_SPINLOCK_TICKET_SHIFT; + + ck_pr_fence_acquire(); + return request != position; +} + +CK_CC_INLINE static void +ck_spinlock_ticket_lock(struct ck_spinlock_ticket *ticket) +{ + CK_SPINLOCK_TICKET_TYPE request, position; + + /* Get our ticket number and set next ticket number. */ + request = CK_SPINLOCK_TICKET_FAA(&ticket->value, + CK_SPINLOCK_TICKET_INCREMENT); + + position = request & CK_SPINLOCK_TICKET_MASK; + request >>= CK_SPINLOCK_TICKET_SHIFT; + + while (request != position) { + ck_pr_stall(); + position = CK_SPINLOCK_TICKET_LOAD(&ticket->value) & + CK_SPINLOCK_TICKET_MASK; + } + + ck_pr_fence_lock(); + return; +} + +CK_CC_INLINE static void +ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket *ticket, unsigned int c) +{ + CK_SPINLOCK_TICKET_TYPE request, position; + ck_backoff_t backoff; + + /* Get our ticket number and set next ticket number. */ + request = CK_SPINLOCK_TICKET_FAA(&ticket->value, + CK_SPINLOCK_TICKET_INCREMENT); + + position = request & CK_SPINLOCK_TICKET_MASK; + request >>= CK_SPINLOCK_TICKET_SHIFT; + + while (request != position) { + ck_pr_stall(); + position = CK_SPINLOCK_TICKET_LOAD(&ticket->value) & + CK_SPINLOCK_TICKET_MASK; + + backoff = (request - position) & CK_SPINLOCK_TICKET_MASK; + backoff <<= c; + ck_backoff_eb(&backoff); + } + + ck_pr_fence_lock(); + return; +} + +CK_CC_INLINE static bool +ck_spinlock_ticket_trylock(struct ck_spinlock_ticket *ticket) +{ + CK_SPINLOCK_TICKET_TYPE snapshot, request, position; + + snapshot = CK_SPINLOCK_TICKET_LOAD(&ticket->value); + position = snapshot & CK_SPINLOCK_TICKET_MASK; + request = snapshot >> CK_SPINLOCK_TICKET_SHIFT; + + if (position != request) + return false; + + if (CK_SPINLOCK_TICKET_CAS(&ticket->value, + snapshot, snapshot + CK_SPINLOCK_TICKET_INCREMENT) == false) { + return false; + } + + ck_pr_fence_lock(); + return true; +} + +CK_CC_INLINE static void +ck_spinlock_ticket_unlock(struct ck_spinlock_ticket *ticket) +{ + + ck_pr_fence_unlock(); + CK_SPINLOCK_TICKET_INC((CK_SPINLOCK_TICKET_TYPE_BASE *)(void *)&ticket->value); + return; +} + +#undef CK_SPINLOCK_TICKET_TYPE +#undef CK_SPINLOCK_TICKET_TYPE_BASE +#undef CK_SPINLOCK_TICKET_INC +#undef CK_SPINLOCK_TICKET_FAA +#undef CK_SPINLOCK_TICKET_LOAD +#undef CK_SPINLOCK_TICKET_INCREMENT +#undef CK_SPINLOCK_TICKET_MASK +#undef CK_SPINLOCK_TICKET_SHIFT +#else +/* + * MESI benefits from cacheline padding between next and current. This avoids + * invalidation of current from the cache due to incoming lock requests. + */ +struct ck_spinlock_ticket { + unsigned int next; + unsigned int position; +}; +typedef struct ck_spinlock_ticket ck_spinlock_ticket_t; + +#define CK_SPINLOCK_TICKET_INITIALIZER {.next = 0, .position = 0} + +CK_CC_INLINE static void +ck_spinlock_ticket_init(struct ck_spinlock_ticket *ticket) +{ + + ticket->next = 0; + ticket->position = 0; + ck_pr_barrier(); + + return; +} + +CK_CC_INLINE static bool +ck_spinlock_ticket_locked(struct ck_spinlock_ticket *ticket) +{ + bool r; + + r = ck_pr_load_uint(&ticket->position) != + ck_pr_load_uint(&ticket->next); + ck_pr_fence_acquire(); + return r; +} + +CK_CC_INLINE static void +ck_spinlock_ticket_lock(struct ck_spinlock_ticket *ticket) +{ + unsigned int request; + + /* Get our ticket number and set next ticket number. */ + request = ck_pr_faa_uint(&ticket->next, 1); + + /* + * Busy-wait until our ticket number is current. + * We can get away without a fence here assuming + * our position counter does not overflow. + */ + while (ck_pr_load_uint(&ticket->position) != request) + ck_pr_stall(); + + ck_pr_fence_lock(); + return; +} + +CK_CC_INLINE static void +ck_spinlock_ticket_lock_pb(struct ck_spinlock_ticket *ticket, unsigned int c) +{ + ck_backoff_t backoff; + unsigned int request, position; + + request = ck_pr_faa_uint(&ticket->next, 1); + + for (;;) { + position = ck_pr_load_uint(&ticket->position); + if (position == request) + break; + + backoff = request - position; + backoff <<= c; + + /* + * Ideally, back-off from generating cache traffic for at least + * the amount of time necessary for the number of pending lock + * acquisition and relinquish operations (assuming an empty + * critical section). + */ + ck_backoff_eb(&backoff); + } + + ck_pr_fence_lock(); + return; +} + +CK_CC_INLINE static void +ck_spinlock_ticket_unlock(struct ck_spinlock_ticket *ticket) +{ + unsigned int update; + + ck_pr_fence_unlock(); + + /* + * Update current ticket value so next lock request can proceed. + * Overflow behavior is assumed to be roll-over, in which case, + * it is only an issue if there are 2^32 pending lock requests. + */ + update = ck_pr_load_uint(&ticket->position); + ck_pr_store_uint(&ticket->position, update + 1); + return; +} +#endif /* !CK_F_SPINLOCK_TICKET_TRYLOCK */ + +CK_ELIDE_PROTOTYPE(ck_spinlock_ticket, ck_spinlock_ticket_t, + ck_spinlock_ticket_locked, ck_spinlock_ticket_lock, + ck_spinlock_ticket_locked, ck_spinlock_ticket_unlock) + +CK_ELIDE_TRYLOCK_PROTOTYPE(ck_spinlock_ticket, ck_spinlock_ticket_t, + ck_spinlock_ticket_locked, ck_spinlock_ticket_trylock) + +#endif /* CK_F_SPINLOCK_TICKET */ +#endif /* CK_SPINLOCK_TICKET_H */ |