summaryrefslogtreecommitdiffstats
path: root/include/spinlock/ticket.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/spinlock/ticket.h')
-rw-r--r--include/spinlock/ticket.h296
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 */