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
38struct ck_spinlock_mcs {
39	unsigned int locked;
40	struct ck_spinlock_mcs *next;
41};
42typedef struct ck_spinlock_mcs * ck_spinlock_mcs_t;
43typedef struct ck_spinlock_mcs ck_spinlock_mcs_context_t;
44
45#define CK_SPINLOCK_MCS_INITIALIZER	    (NULL)
46
47CK_CC_INLINE static void
48ck_spinlock_mcs_init(struct ck_spinlock_mcs **queue)
49{
50
51	*queue = NULL;
52	ck_pr_barrier();
53	return;
54}
55
56CK_CC_INLINE static bool
57ck_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
71CK_CC_INLINE static bool
72ck_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
81CK_CC_INLINE static void
82ck_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
115CK_CC_INLINE static void
116ck_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