1/*-
2 * Copyright (c) 2001, 2003 Daniel Eischen <deischen@freebsd.org>.
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 AUTHORS 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 * $FreeBSD$
27 */
28
29#include <sys/types.h>
30#include <machine/atomic.h>
31#include <assert.h>
32#include <stdlib.h>
33
34#include "atomic_ops.h"
35#include "lock.h"
36
37#ifdef _LOCK_DEBUG
38#define	LCK_ASSERT(e)	assert(e)
39#else
40#define LCK_ASSERT(e)
41#endif
42
43#define	MAX_SPINS	500
44
45void
46_lock_destroy(struct lock *lck)
47{
48	if ((lck != NULL) && (lck->l_head != NULL)) {
49		free(lck->l_head);
50		lck->l_head = NULL;
51		lck->l_tail = NULL;
52	}
53}
54
55int
56_lock_init(struct lock *lck, enum lock_type ltype,
57    lock_handler_t *waitfunc, lock_handler_t *wakeupfunc,
58    void *(calloc_cb)(size_t, size_t))
59{
60	if (lck == NULL)
61		return (-1);
62	else if ((lck->l_head = calloc_cb(1, sizeof(struct lockreq))) == NULL)
63		return (-1);
64	else {
65		lck->l_type = ltype;
66		lck->l_wait = waitfunc;
67		lck->l_wakeup = wakeupfunc;
68		lck->l_head->lr_locked = 0;
69		lck->l_head->lr_watcher = NULL;
70		lck->l_head->lr_owner = NULL;
71		lck->l_head->lr_active = 1;
72		lck->l_tail = lck->l_head;
73	}
74	return (0);
75}
76
77int
78_lock_reinit(struct lock *lck, enum lock_type ltype,
79    lock_handler_t *waitfunc, lock_handler_t *wakeupfunc)
80{
81	if (lck == NULL)
82		return (-1);
83	else if (lck->l_head == NULL)
84		return (_lock_init(lck, ltype, waitfunc, wakeupfunc, calloc));
85	else {
86		lck->l_head->lr_locked = 0;
87		lck->l_head->lr_watcher = NULL;
88		lck->l_head->lr_owner = NULL;
89		lck->l_head->lr_active = 1;
90		lck->l_tail = lck->l_head;
91	}
92	return (0);
93}
94
95int
96_lockuser_init(struct lockuser *lu, void *priv)
97{
98	if (lu == NULL)
99		return (-1);
100	else if ((lu->lu_myreq == NULL) &&
101	    ((lu->lu_myreq = malloc(sizeof(struct lockreq))) == NULL))
102		return (-1);
103	else {
104		lu->lu_myreq->lr_locked = 1;
105		lu->lu_myreq->lr_watcher = NULL;
106		lu->lu_myreq->lr_owner = lu;
107		lu->lu_myreq->lr_active = 0;
108		lu->lu_watchreq = NULL;
109		lu->lu_priority = 0;
110		lu->lu_private = priv;
111		lu->lu_private2 = NULL;
112	}
113	return (0);
114}
115
116int
117_lockuser_reinit(struct lockuser *lu, void *priv)
118{
119	if (lu == NULL)
120		return (-1);
121	if (lu->lu_watchreq != NULL) {
122		/*
123		 * In this case the lock is active.  All lockusers
124		 * keep their watch request and drop their own
125		 * (lu_myreq) request.  Their own request is either
126		 * some other lockuser's watch request or is the
127		 * head of the lock.
128		 */
129		lu->lu_myreq = lu->lu_watchreq;
130		lu->lu_watchreq = NULL;
131	}
132	if (lu->lu_myreq == NULL)
133		/*
134		 * Oops, something isn't quite right.  Try to
135		 * allocate one.
136		 */
137		return (_lockuser_init(lu, priv));
138	else {
139		lu->lu_myreq->lr_locked = 1;
140		lu->lu_myreq->lr_watcher = NULL;
141		lu->lu_myreq->lr_owner = lu;
142		lu->lu_myreq->lr_active = 0;
143		lu->lu_watchreq = NULL;
144		lu->lu_priority = 0;
145		lu->lu_private = priv;
146		lu->lu_private2 = NULL;
147	}
148	return (0);
149}
150
151void
152_lockuser_destroy(struct lockuser *lu)
153{
154	if ((lu != NULL) && (lu->lu_myreq != NULL))
155		free(lu->lu_myreq);
156}
157
158/*
159 * Acquire a lock waiting (spin or sleep) for it to become available.
160 */
161void
162_lock_acquire(struct lock *lck, struct lockuser *lu, int prio)
163{
164	int i;
165	int lval;
166
167	/**
168	 * XXX - We probably want to remove these checks to optimize
169	 *       performance.  It is also a bug if any one of the
170	 *       checks fail, so it's probably better to just let it
171	 *       SEGV and fix it.
172	 */
173#if 0
174	if (lck == NULL || lu == NULL || lck->l_head == NULL)
175		return;
176#endif
177	if ((lck->l_type & LCK_PRIORITY) != 0) {
178		LCK_ASSERT(lu->lu_myreq->lr_locked == 1);
179		LCK_ASSERT(lu->lu_myreq->lr_watcher == NULL);
180		LCK_ASSERT(lu->lu_myreq->lr_owner == lu);
181		LCK_ASSERT(lu->lu_watchreq == NULL);
182
183		lu->lu_priority = prio;
184	}
185	/*
186	 * Atomically swap the head of the lock request with
187	 * this request.
188	 */
189	atomic_swap_ptr((void *)&lck->l_head, lu->lu_myreq,
190	    (void *)&lu->lu_watchreq);
191
192	if (lu->lu_watchreq->lr_locked != 0) {
193		atomic_store_rel_ptr
194		    ((volatile uintptr_t *)(void *)&lu->lu_watchreq->lr_watcher,
195		    (uintptr_t)lu);
196		if ((lck->l_wait == NULL) ||
197		    ((lck->l_type & LCK_ADAPTIVE) == 0)) {
198			while (lu->lu_watchreq->lr_locked != 0)
199				;	/* spin, then yield? */
200		} else {
201			/*
202			 * Spin for a bit before invoking the wait function.
203			 *
204			 * We should be a little smarter here.  If we're
205			 * running on a single processor, then the lock
206			 * owner got preempted and spinning will accomplish
207			 * nothing but waste time.  If we're running on
208			 * multiple processors, the owner could be running
209			 * on another CPU and we might acquire the lock if
210			 * we spin for a bit.
211			 *
212			 * The other thing to keep in mind is that threads
213			 * acquiring these locks are considered to be in
214			 * critical regions; they will not be preempted by
215			 * the _UTS_ until they release the lock.  It is
216			 * therefore safe to assume that if a lock can't
217			 * be acquired, it is currently held by a thread
218			 * running in another KSE.
219			 */
220			for (i = 0; i < MAX_SPINS; i++) {
221				if (lu->lu_watchreq->lr_locked == 0)
222					return;
223				if (lu->lu_watchreq->lr_active == 0)
224					break;
225			}
226			atomic_swap_int(&lu->lu_watchreq->lr_locked,
227			    2, &lval);
228			if (lval == 0)
229				lu->lu_watchreq->lr_locked = 0;
230			else
231				lck->l_wait(lck, lu);
232
233		}
234	}
235	lu->lu_myreq->lr_active = 1;
236}
237
238/*
239 * Release a lock.
240 */
241void
242_lock_release(struct lock *lck, struct lockuser *lu)
243{
244	struct lockuser *lu_tmp, *lu_h;
245	struct lockreq *myreq;
246	int prio_h;
247	int lval;
248
249	/**
250	 * XXX - We probably want to remove these checks to optimize
251	 *       performance.  It is also a bug if any one of the
252	 *       checks fail, so it's probably better to just let it
253	 *       SEGV and fix it.
254	 */
255#if 0
256	if ((lck == NULL) || (lu == NULL))
257		return;
258#endif
259	if ((lck->l_type & LCK_PRIORITY) != 0) {
260		prio_h = 0;
261		lu_h = NULL;
262
263		/* Update tail if our request is last. */
264		if (lu->lu_watchreq->lr_owner == NULL) {
265			atomic_store_rel_ptr((volatile uintptr_t *)
266			    (void *)&lck->l_tail,
267			    (uintptr_t)lu->lu_myreq);
268			atomic_store_rel_ptr((volatile uintptr_t *)
269			    (void *)&lu->lu_myreq->lr_owner,
270			    (uintptr_t)NULL);
271		} else {
272			/* Remove ourselves from the list. */
273			atomic_store_rel_ptr((volatile uintptr_t *)
274			    (void *)&lu->lu_myreq->lr_owner,
275			    (uintptr_t)lu->lu_watchreq->lr_owner);
276			atomic_store_rel_ptr((volatile uintptr_t *)
277			    (void *)&lu->lu_watchreq->lr_owner->lu_myreq,
278			    (uintptr_t)lu->lu_myreq);
279		}
280		/*
281		 * The watch request now becomes our own because we've
282		 * traded away our previous request.  Save our previous
283		 * request so that we can grant the lock.
284		 */
285		myreq = lu->lu_myreq;
286		lu->lu_myreq = lu->lu_watchreq;
287		lu->lu_watchreq = NULL;
288		lu->lu_myreq->lr_locked = 1;
289		lu->lu_myreq->lr_owner = lu;
290		lu->lu_myreq->lr_watcher = NULL;
291		/*
292		 * Traverse the list of lock requests in reverse order
293		 * looking for the user with the highest priority.
294		 */
295		for (lu_tmp = lck->l_tail->lr_watcher; lu_tmp != NULL;
296		     lu_tmp = lu_tmp->lu_myreq->lr_watcher) {
297			if (lu_tmp->lu_priority > prio_h) {
298				lu_h = lu_tmp;
299				prio_h = lu_tmp->lu_priority;
300			}
301		}
302		if (lu_h != NULL) {
303			/* Give the lock to the highest priority user. */
304			if (lck->l_wakeup != NULL) {
305				atomic_swap_int(
306				    &lu_h->lu_watchreq->lr_locked,
307				    0, &lval);
308				if (lval == 2)
309					/* Notify the sleeper */
310					lck->l_wakeup(lck,
311					    lu_h->lu_myreq->lr_watcher);
312			}
313			else
314				atomic_store_rel_int(
315				    &lu_h->lu_watchreq->lr_locked, 0);
316		} else {
317			if (lck->l_wakeup != NULL) {
318				atomic_swap_int(&myreq->lr_locked,
319				    0, &lval);
320				if (lval == 2)
321					/* Notify the sleeper */
322					lck->l_wakeup(lck, myreq->lr_watcher);
323			}
324			else
325				/* Give the lock to the previous request. */
326				atomic_store_rel_int(&myreq->lr_locked, 0);
327		}
328	} else {
329		/*
330		 * The watch request now becomes our own because we've
331		 * traded away our previous request.  Save our previous
332		 * request so that we can grant the lock.
333		 */
334		myreq = lu->lu_myreq;
335		lu->lu_myreq = lu->lu_watchreq;
336		lu->lu_watchreq = NULL;
337		lu->lu_myreq->lr_locked = 1;
338		if (lck->l_wakeup) {
339			atomic_swap_int(&myreq->lr_locked, 0, &lval);
340			if (lval == 2)
341				/* Notify the sleeper */
342				lck->l_wakeup(lck, myreq->lr_watcher);
343		}
344		else
345			/* Give the lock to the previous request. */
346			atomic_store_rel_int(&myreq->lr_locked, 0);
347	}
348	lu->lu_myreq->lr_active = 0;
349}
350
351void
352_lock_grant(struct lock *lck __unused /* unused */, struct lockuser *lu)
353{
354	atomic_store_rel_int(&lu->lu_watchreq->lr_locked, 3);
355}
356
357void
358_lockuser_setactive(struct lockuser *lu, int active)
359{
360	lu->lu_myreq->lr_active = active;
361}
362
363