1/*
2 * Copyright 2011-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_BRLOCK_H
28#define CK_BRLOCK_H
29
30/*
31 * Big reader spinlocks provide cache-local contention-free read
32 * lock acquisition in the absence of writers. This comes at the
33 * cost of O(n) write lock acquisition. They were first implemented
34 * in the Linux kernel by Ingo Molnar and David S. Miller around the
35 * year 2000.
36 *
37 * This implementation is thread-agnostic which comes at the cost
38 * of larger reader objects due to necessary linkage overhead. In
39 * order to cut down on TLB pressure, it is recommended to allocate
40 * these objects on the same page.
41 */
42
43#include <ck_pr.h>
44#include <ck_stdbool.h>
45#include <ck_stddef.h>
46
47struct ck_brlock_reader {
48	unsigned int n_readers;
49	struct ck_brlock_reader *previous;
50	struct ck_brlock_reader *next;
51};
52typedef struct ck_brlock_reader ck_brlock_reader_t;
53
54#define CK_BRLOCK_READER_INITIALIZER {0}
55
56struct ck_brlock {
57	struct ck_brlock_reader *readers;
58	unsigned int writer;
59};
60typedef struct ck_brlock ck_brlock_t;
61
62#define CK_BRLOCK_INITIALIZER {NULL, false}
63
64CK_CC_INLINE static void
65ck_brlock_init(struct ck_brlock *br)
66{
67
68	br->readers = NULL;
69	br->writer = false;
70	ck_pr_barrier();
71	return;
72}
73
74CK_CC_INLINE static void
75ck_brlock_write_lock(struct ck_brlock *br)
76{
77	struct ck_brlock_reader *cursor;
78
79	/*
80	 * As the frequency of write acquisitions should be low,
81	 * there is no point to more advanced contention avoidance.
82	 */
83	while (ck_pr_fas_uint(&br->writer, true) == true)
84		ck_pr_stall();
85
86	ck_pr_fence_atomic_load();
87
88	/* The reader list is protected under the writer br. */
89	for (cursor = br->readers; cursor != NULL; cursor = cursor->next) {
90		while (ck_pr_load_uint(&cursor->n_readers) != 0)
91			ck_pr_stall();
92	}
93
94	ck_pr_fence_lock();
95	return;
96}
97
98CK_CC_INLINE static void
99ck_brlock_write_unlock(struct ck_brlock *br)
100{
101
102	ck_pr_fence_unlock();
103	ck_pr_store_uint(&br->writer, false);
104	return;
105}
106
107CK_CC_INLINE static bool
108ck_brlock_write_trylock(struct ck_brlock *br, unsigned int factor)
109{
110	struct ck_brlock_reader *cursor;
111	unsigned int steps = 0;
112
113	while (ck_pr_fas_uint(&br->writer, true) == true) {
114		if (++steps >= factor)
115			return false;
116
117		ck_pr_stall();
118	}
119
120	/*
121	 * We do not require a strict fence here as atomic RMW operations
122	 * are serializing.
123	 */
124	ck_pr_fence_atomic_load();
125
126	for (cursor = br->readers; cursor != NULL; cursor = cursor->next) {
127		while (ck_pr_load_uint(&cursor->n_readers) != 0) {
128			if (++steps >= factor) {
129				ck_brlock_write_unlock(br);
130				return false;
131			}
132
133			ck_pr_stall();
134		}
135	}
136
137	ck_pr_fence_lock();
138	return true;
139}
140
141CK_CC_INLINE static void
142ck_brlock_read_register(struct ck_brlock *br, struct ck_brlock_reader *reader)
143{
144
145	reader->n_readers = 0;
146	reader->previous = NULL;
147
148	/* Implicit compiler barrier. */
149	ck_brlock_write_lock(br);
150
151	reader->next = ck_pr_load_ptr(&br->readers);
152	if (reader->next != NULL)
153		reader->next->previous = reader;
154	ck_pr_store_ptr(&br->readers, reader);
155
156	ck_brlock_write_unlock(br);
157	return;
158}
159
160CK_CC_INLINE static void
161ck_brlock_read_unregister(struct ck_brlock *br, struct ck_brlock_reader *reader)
162{
163
164	ck_brlock_write_lock(br);
165
166	if (reader->next != NULL)
167		reader->next->previous = reader->previous;
168
169	if (reader->previous != NULL)
170		reader->previous->next = reader->next;
171	else
172		br->readers = reader->next;
173
174	ck_brlock_write_unlock(br);
175	return;
176}
177
178CK_CC_INLINE static void
179ck_brlock_read_lock(struct ck_brlock *br, struct ck_brlock_reader *reader)
180{
181
182	if (reader->n_readers >= 1) {
183		ck_pr_store_uint(&reader->n_readers, reader->n_readers + 1);
184		return;
185	}
186
187	for (;;) {
188		while (ck_pr_load_uint(&br->writer) == true)
189			ck_pr_stall();
190
191#if defined(__x86__) || defined(__x86_64__)
192		ck_pr_fas_uint(&reader->n_readers, 1);
193
194		/*
195		 * Serialize reader counter update with respect to load of
196		 * writer.
197		 */
198		ck_pr_fence_atomic_load();
199#else
200		ck_pr_store_uint(&reader->n_readers, 1);
201
202		/*
203		 * Serialize reader counter update with respect to load of
204		 * writer.
205		 */
206		ck_pr_fence_store_load();
207#endif
208
209		if (ck_pr_load_uint(&br->writer) == false)
210			break;
211
212		ck_pr_store_uint(&reader->n_readers, 0);
213	}
214
215	ck_pr_fence_lock();
216	return;
217}
218
219CK_CC_INLINE static bool
220ck_brlock_read_trylock(struct ck_brlock *br,
221		       struct ck_brlock_reader *reader,
222		       unsigned int factor)
223{
224	unsigned int steps = 0;
225
226	if (reader->n_readers >= 1) {
227		ck_pr_store_uint(&reader->n_readers, reader->n_readers + 1);
228		return true;
229	}
230
231	for (;;) {
232		while (ck_pr_load_uint(&br->writer) == true) {
233			if (++steps >= factor)
234				return false;
235
236			ck_pr_stall();
237		}
238
239#if defined(__x86__) || defined(__x86_64__)
240		ck_pr_fas_uint(&reader->n_readers, 1);
241
242		/*
243		 * Serialize reader counter update with respect to load of
244		 * writer.
245		 */
246		ck_pr_fence_atomic_load();
247#else
248		ck_pr_store_uint(&reader->n_readers, 1);
249
250		/*
251		 * Serialize reader counter update with respect to load of
252		 * writer.
253		 */
254		ck_pr_fence_store_load();
255#endif
256
257		if (ck_pr_load_uint(&br->writer) == false)
258			break;
259
260		ck_pr_store_uint(&reader->n_readers, 0);
261
262		if (++steps >= factor)
263			return false;
264	}
265
266	ck_pr_fence_lock();
267	return true;
268}
269
270CK_CC_INLINE static void
271ck_brlock_read_unlock(struct ck_brlock_reader *reader)
272{
273
274	ck_pr_fence_unlock();
275	ck_pr_store_uint(&reader->n_readers, reader->n_readers - 1);
276	return;
277}
278
279#endif /* CK_BRLOCK_H */
280