kern_umtx.c revision 116182 
1/*
2 * Copyright (c) 2002, Jeffrey Roberson <jeff@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 unmodified, this list of conditions, and the following
10 *    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.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <sys/cdefs.h>
28__FBSDID("$FreeBSD: head/sys/kern/kern_umtx.c 116182 2003-06-11 00:56:59Z obrien $");
29
30#include <sys/param.h>
31#include <sys/kernel.h>
32#include <sys/lock.h>
33#include <sys/malloc.h>
34#include <sys/mutex.h>
35#include <sys/proc.h>
36#include <sys/signalvar.h>
37#include <sys/sysent.h>
38#include <sys/systm.h>
39#include <sys/sysproto.h>
40#include <sys/sx.h>
41#include <sys/thr.h>
42#include <sys/umtx.h>
43
44struct umtx_q {
45	LIST_ENTRY(umtx_q)	uq_next;	/* Linked list for the hash. */
46	TAILQ_HEAD(, thread) uq_tdq;	/* List of threads blocked here. */
47	struct umtx	*uq_umtx;	/* Pointer key component. */
48	pid_t		uq_pid;		/* Pid key component. */
49};
50
51#define	UMTX_QUEUES	128
52#define	UMTX_HASH(pid, umtx)						\
53    (((uintptr_t)pid + ((uintptr_t)umtx & ~65535)) % UMTX_QUEUES)
54
55LIST_HEAD(umtx_head, umtx_q);
56static struct umtx_head queues[UMTX_QUEUES];
57static MALLOC_DEFINE(M_UMTX, "umtx", "UMTX queue memory");
58
59static struct mtx umtx_lock;
60MTX_SYSINIT(umtx, &umtx_lock, "umtx", MTX_DEF);
61
62#define	UMTX_LOCK()	mtx_lock(&umtx_lock);
63#define	UMTX_UNLOCK()	mtx_unlock(&umtx_lock);
64
65
66static struct umtx_q *umtx_lookup(struct thread *, struct umtx *umtx);
67static struct umtx_q *umtx_insert(struct thread *, struct umtx *umtx);
68
69static struct umtx_q *
70umtx_lookup(struct thread *td, struct umtx *umtx)
71{
72	struct umtx_head *head;
73	struct umtx_q *uq;
74	pid_t pid;
75
76	pid = td->td_proc->p_pid;
77
78	head = &queues[UMTX_HASH(td->td_proc->p_pid, umtx)];
79
80	LIST_FOREACH(uq, head, uq_next) {
81		if (uq->uq_pid == pid && uq->uq_umtx == umtx)
82			return (uq);
83	}
84
85	return (NULL);
86}
87
88/*
89 * Insert a thread onto the umtx queue.
90 */
91static struct umtx_q *
92umtx_insert(struct thread *td, struct umtx *umtx)
93{
94	struct umtx_head *head;
95	struct umtx_q *uq;
96	pid_t pid;
97
98	pid = td->td_proc->p_pid;
99
100	if ((uq = umtx_lookup(td, umtx)) == NULL) {
101		struct umtx_q *ins;
102
103		UMTX_UNLOCK();
104		ins = malloc(sizeof(*uq), M_UMTX, M_ZERO | M_WAITOK);
105		UMTX_LOCK();
106
107		/*
108		 * Some one else could have succeeded while we were blocked
109		 * waiting on memory.
110		 */
111		if ((uq = umtx_lookup(td, umtx)) == NULL) {
112			head = &queues[UMTX_HASH(pid, umtx)];
113			uq = ins;
114			uq->uq_pid = pid;
115			uq->uq_umtx = umtx;
116			LIST_INSERT_HEAD(head, uq, uq_next);
117			TAILQ_INIT(&uq->uq_tdq);
118		} else
119			free(ins, M_UMTX);
120	}
121
122	/*
123	 * Insert us onto the end of the TAILQ.
124	 */
125	TAILQ_INSERT_TAIL(&uq->uq_tdq, td, td_umtx);
126
127	return (uq);
128}
129
130static void
131umtx_remove(struct umtx_q *uq, struct thread *td)
132{
133	TAILQ_REMOVE(&uq->uq_tdq, td, td_umtx);
134
135	if (TAILQ_EMPTY(&uq->uq_tdq)) {
136		LIST_REMOVE(uq, uq_next);
137		free(uq, M_UMTX);
138	}
139}
140
141int
142_umtx_lock(struct thread *td, struct _umtx_lock_args *uap)
143    /* struct umtx *umtx */
144{
145	struct umtx_q *uq;
146	struct umtx *umtx;
147	intptr_t owner;
148	intptr_t old;
149	int error;
150
151	uq = NULL;
152
153	/*
154	 * Care must be exercised when dealing with this structure.  It
155	 * can fault on any access.
156	 */
157	umtx = uap->umtx;
158
159	for (;;) {
160		/*
161		 * Try the uncontested case.  This should be done in userland.
162		 */
163		owner = casuptr((intptr_t *)&umtx->u_owner,
164		    UMTX_UNOWNED, (intptr_t)td);
165
166		/* The address was invalid. */
167		if (owner == -1)
168			return (EFAULT);
169
170		/* The acquire succeeded. */
171		if (owner == UMTX_UNOWNED)
172			return (0);
173
174		/* If no one owns it but it is contested try to acquire it. */
175		if (owner == UMTX_CONTESTED) {
176			owner = casuptr((intptr_t *)&umtx->u_owner,
177			    UMTX_CONTESTED, ((intptr_t)td | UMTX_CONTESTED));
178
179			/* The address was invalid. */
180			if (owner == -1)
181				return (EFAULT);
182
183			if (owner == MTX_CONTESTED);
184				return (0);
185
186			/* If this failed the lock has changed, restart. */
187			continue;
188		}
189
190
191		UMTX_LOCK();
192		uq = umtx_insert(td, umtx);
193		UMTX_UNLOCK();
194
195		/*
196		 * Set the contested bit so that a release in user space
197		 * knows to use the system call for unlock.  If this fails
198		 * either some one else has acquired the lock or it has been
199		 * released.
200		 */
201		old = casuptr((intptr_t *)&umtx->u_owner, owner,
202		    owner | UMTX_CONTESTED);
203
204		/* The address was invalid. */
205		if (old == -1) {
206			UMTX_LOCK();
207			umtx_remove(uq, td);
208			UMTX_UNLOCK();
209			return (EFAULT);
210		}
211
212		/*
213		 * We set the contested bit, sleep. Otherwise the lock changed
214		 * and we need to retry.
215		 */
216		UMTX_LOCK();
217		if (old == owner)
218			error = msleep(td, &umtx_lock,
219			    td->td_priority | PCATCH, "umtx", 0);
220		else
221			error = 0;
222
223		umtx_remove(uq, td);
224		UMTX_UNLOCK();
225
226		/*
227		 * If we caught a signal we might have to retry or exit
228		 * immediately.
229		 */
230		if (error)
231			return (error);
232	}
233
234	return (0);
235}
236
237int
238_umtx_unlock(struct thread *td, struct _umtx_unlock_args *uap)
239    /* struct umtx *umtx */
240{
241	struct thread *blocked;
242	struct umtx *umtx;
243	struct umtx_q *uq;
244	intptr_t owner;
245	intptr_t old;
246
247	umtx = uap->umtx;
248
249	/*
250	 * Make sure we own this mtx.
251	 *
252	 * XXX Need a {fu,su}ptr this is not correct on arch where
253	 * sizeof(intptr_t) != sizeof(long).
254	 */
255	if ((owner = fuword(&umtx->u_owner)) == -1)
256		return (EFAULT);
257
258	if ((struct thread *)(owner & ~UMTX_CONTESTED) != td)
259		return (EPERM);
260	/*
261	 * If we own it but it isn't contested then we can just release and
262	 * return.
263	 */
264	if ((owner & UMTX_CONTESTED) == 0) {
265		owner = casuptr((intptr_t *)&umtx->u_owner,
266		    (intptr_t)td, UMTX_UNOWNED);
267
268		if (owner == -1)
269			return (EFAULT);
270		/*
271		 * If this failed someone modified the memory without going
272		 * through this api.
273		 */
274		if (owner != (intptr_t)td)
275			return (EINVAL);
276
277		return (0);
278	}
279
280	old = casuptr((intptr_t *)&umtx->u_owner, owner, UMTX_CONTESTED);
281
282	if (old == -1)
283		return (EFAULT);
284
285	/*
286	 * This will only happen if someone modifies the lock without going
287	 * through this api.
288	 */
289	if (old != owner)
290		return (EINVAL);
291
292	/*
293	 * We have to wake up one of the blocked threads.
294	 */
295	UMTX_LOCK();
296	uq = umtx_lookup(td, umtx);
297	if (uq != NULL) {
298		blocked = TAILQ_FIRST(&uq->uq_tdq);
299		wakeup(blocked);
300	}
301
302	UMTX_UNLOCK();
303
304	return (0);
305}
306