2 * Copyright 2013-2015 Samy Al Bahra.
3 * Copyright 2013 Brendon Scheinman.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * This is an implementation of lock cohorts as described in:
33 * Dice, D.; Marathe, V.; and Shavit, N. 2012.
34 * Lock Cohorting: A General Technique for Designing NUMA Locks
39 #include <ck_stddef.h>
41 enum ck_cohort_state {
42 CK_COHORT_STATE_GLOBAL = 0,
43 CK_COHORT_STATE_LOCAL = 1
46 #define CK_COHORT_DEFAULT_LOCAL_PASS_LIMIT 10
48 #define CK_COHORT_NAME(N) ck_cohort_##N
49 #define CK_COHORT_INSTANCE(N) struct CK_COHORT_NAME(N)
50 #define CK_COHORT_INIT(N, C, GL, LL, P) ck_cohort_##N##_init(C, GL, LL, P)
51 #define CK_COHORT_LOCK(N, C, GC, LC) ck_cohort_##N##_lock(C, GC, LC)
52 #define CK_COHORT_UNLOCK(N, C, GC, LC) ck_cohort_##N##_unlock(C, GC, LC)
53 #define CK_COHORT_TRYLOCK(N, C, GLC, LLC, LUC) ck_cohort_##N##_trylock(C, GLC, LLC, LUC)
54 #define CK_COHORT_LOCKED(N, C, GC, LC) ck_cohort_##N##_locked(C, GC, LC)
56 #define CK_COHORT_PROTOTYPE(N, GL, GU, GI, LL, LU, LI) \
57 CK_COHORT_INSTANCE(N) { \
60 enum ck_cohort_state release_state; \
61 unsigned int waiting_threads; \
62 unsigned int acquire_count; \
63 unsigned int local_pass_limit; \
66 CK_CC_INLINE static void \
67 ck_cohort_##N##_init(struct ck_cohort_##N *cohort, \
68 void *global_lock, void *local_lock, unsigned int pass_limit) \
70 cohort->global_lock = global_lock; \
71 cohort->local_lock = local_lock; \
72 cohort->release_state = CK_COHORT_STATE_GLOBAL; \
73 cohort->waiting_threads = 0; \
74 cohort->acquire_count = 0; \
75 cohort->local_pass_limit = pass_limit; \
80 CK_CC_INLINE static void \
81 ck_cohort_##N##_lock(CK_COHORT_INSTANCE(N) *cohort, \
82 void *global_context, void *local_context) \
85 ck_pr_inc_uint(&cohort->waiting_threads); \
86 LL(cohort->local_lock, local_context); \
87 ck_pr_dec_uint(&cohort->waiting_threads); \
89 if (cohort->release_state == CK_COHORT_STATE_GLOBAL) { \
90 GL(cohort->global_lock, global_context); \
93 ++cohort->acquire_count; \
97 CK_CC_INLINE static void \
98 ck_cohort_##N##_unlock(CK_COHORT_INSTANCE(N) *cohort, \
99 void *global_context, void *local_context) \
102 if (ck_pr_load_uint(&cohort->waiting_threads) > 0 \
103 && cohort->acquire_count < cohort->local_pass_limit) { \
104 cohort->release_state = CK_COHORT_STATE_LOCAL; \
106 GU(cohort->global_lock, global_context); \
107 cohort->release_state = CK_COHORT_STATE_GLOBAL; \
108 cohort->acquire_count = 0; \
111 ck_pr_fence_release(); \
112 LU(cohort->local_lock, local_context); \
117 CK_CC_INLINE static bool \
118 ck_cohort_##N##_locked(CK_COHORT_INSTANCE(N) *cohort, \
119 void *global_context, void *local_context) \
121 return GI(cohort->local_lock, local_context) || \
122 LI(cohort->global_lock, global_context); \
125 #define CK_COHORT_TRYLOCK_PROTOTYPE(N, GL, GU, GI, GTL, LL, LU, LI, LTL) \
126 CK_COHORT_PROTOTYPE(N, GL, GU, GI, LL, LU, LI) \
127 CK_CC_INLINE static bool \
128 ck_cohort_##N##_trylock(CK_COHORT_INSTANCE(N) *cohort, \
129 void *global_context, void *local_context, \
130 void *local_unlock_context) \
133 bool trylock_result; \
135 ck_pr_inc_uint(&cohort->waiting_threads); \
136 trylock_result = LTL(cohort->local_lock, local_context); \
137 ck_pr_dec_uint(&cohort->waiting_threads); \
138 if (trylock_result == false) { \
142 if (cohort->release_state == CK_COHORT_STATE_GLOBAL && \
143 GTL(cohort->global_lock, global_context) == false) { \
144 LU(cohort->local_lock, local_unlock_context); \
148 ++cohort->acquire_count; \
152 #define CK_COHORT_INITIALIZER { \
153 .global_lock = NULL, \
154 .local_lock = NULL, \
155 .release_state = CK_COHORT_STATE_GLOBAL, \
156 .waiting_threads = 0, \
157 .acquire_count = 0, \
158 .local_pass_limit = CK_COHORT_DEFAULT_LOCAL_PASS_LIMIT \
161 #endif /* CK_COHORT_H */