1 /*
2 * Copyright 2010-2015 Samy Al Bahra.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27 #ifndef CK_SPINLOCK_MCS_H
28 #define CK_SPINLOCK_MCS_H
29
30 #include <ck_cc.h>
31 #include <ck_pr.h>
32 #include <ck_stdbool.h>
33 #include <ck_stddef.h>
34
35 #ifndef CK_F_SPINLOCK_MCS
36 #define CK_F_SPINLOCK_MCS
37
38 struct ck_spinlock_mcs {
39 unsigned int locked;
40 struct ck_spinlock_mcs *next;
41 };
42 typedef struct ck_spinlock_mcs * ck_spinlock_mcs_t;
43 typedef struct ck_spinlock_mcs ck_spinlock_mcs_context_t;
44
45 #define CK_SPINLOCK_MCS_INITIALIZER (NULL)
46
47 CK_CC_INLINE static void
ck_spinlock_mcs_init(struct ck_spinlock_mcs ** queue)48 ck_spinlock_mcs_init(struct ck_spinlock_mcs **queue)
49 {
50
51 *queue = NULL;
52 ck_pr_barrier();
53 return;
54 }
55
56 CK_CC_INLINE static bool
ck_spinlock_mcs_trylock(struct ck_spinlock_mcs ** queue,struct ck_spinlock_mcs * node)57 ck_spinlock_mcs_trylock(struct ck_spinlock_mcs **queue,
58 struct ck_spinlock_mcs *node)
59 {
60 bool r;
61
62 node->locked = true;
63 node->next = NULL;
64 ck_pr_fence_store_atomic();
65
66 r = ck_pr_cas_ptr(queue, NULL, node);
67 ck_pr_fence_lock();
68 return r;
69 }
70
71 CK_CC_INLINE static bool
ck_spinlock_mcs_locked(struct ck_spinlock_mcs ** queue)72 ck_spinlock_mcs_locked(struct ck_spinlock_mcs **queue)
73 {
74 bool r;
75
76 r = ck_pr_load_ptr(queue) != NULL;
77 ck_pr_fence_acquire();
78 return r;
79 }
80
81 CK_CC_INLINE static void
ck_spinlock_mcs_lock(struct ck_spinlock_mcs ** queue,struct ck_spinlock_mcs * node)82 ck_spinlock_mcs_lock(struct ck_spinlock_mcs **queue,
83 struct ck_spinlock_mcs *node)
84 {
85 struct ck_spinlock_mcs *previous;
86
87 /*
88 * In the case that there is a successor, let them know they must
89 * wait for us to unlock.
90 */
91 node->locked = true;
92 node->next = NULL;
93 ck_pr_fence_store_atomic();
94
95 /*
96 * Swap current tail with current lock request. If the swap operation
97 * returns NULL, it means the queue was empty. If the queue was empty,
98 * then the operation is complete.
99 */
100 previous = ck_pr_fas_ptr(queue, node);
101 if (previous != NULL) {
102 /*
103 * Let the previous lock holder know that we are waiting on
104 * them.
105 */
106 ck_pr_store_ptr(&previous->next, node);
107 while (ck_pr_load_uint(&node->locked) == true)
108 ck_pr_stall();
109 }
110
111 ck_pr_fence_lock();
112 return;
113 }
114
115 CK_CC_INLINE static void
ck_spinlock_mcs_unlock(struct ck_spinlock_mcs ** queue,struct ck_spinlock_mcs * node)116 ck_spinlock_mcs_unlock(struct ck_spinlock_mcs **queue,
117 struct ck_spinlock_mcs *node)
118 {
119 struct ck_spinlock_mcs *next;
120
121 ck_pr_fence_unlock();
122
123 next = ck_pr_load_ptr(&node->next);
124 if (next == NULL) {
125 /*
126 * If there is no request following us then it is a possibilty
127 * that we are the current tail. In this case, we may just
128 * mark the spinlock queue as empty.
129 */
130 if (ck_pr_load_ptr(queue) == node &&
131 ck_pr_cas_ptr(queue, node, NULL) == true) {
132 return;
133 }
134
135 /*
136 * If the node is not the current tail then a lock operation
137 * is in-progress. In this case, busy-wait until the queue is
138 * in a consistent state to wake up the incoming lock
139 * request.
140 */
141 for (;;) {
142 next = ck_pr_load_ptr(&node->next);
143 if (next != NULL)
144 break;
145
146 ck_pr_stall();
147 }
148 }
149
150 /* Allow the next lock operation to complete. */
151 ck_pr_store_uint(&next->locked, false);
152 return;
153 }
154 #endif /* CK_F_SPINLOCK_MCS */
155 #endif /* CK_SPINLOCK_MCS_H */
156