Deleted Added
sdiff udiff text old ( 118272 ) new ( 122514 )
full compact
subr_turnstile.c (118272) subr_turnstile.c (122514)
1/*-
2 * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.

--- 16 unchanged lines hidden (view full) ---

25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
29 * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
30 */
31
32/*
1/*-
2 * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.

--- 16 unchanged lines hidden (view full) ---

25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
29 * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
30 */
31
32/*
33 * Machine independent bits of mutex implementation.
33 * Implementation of turnstiles used to hold queue of threads blocked on
34 * non-sleepable locks. Sleepable locks use condition variables to
35 * implement their queues. Turnstiles differ from a sleep queue in that
36 * turnstile queue's are assigned to a lock held by an owning thread. Thus,
37 * when one thread is enqueued onto a turnstile, it can lend its priority
38 * to the owning thread.
39 *
40 * We wish to avoid bloating locks with an embedded turnstile and we do not
41 * want to use back-pointers in the locks for the same reason. Thus, we
42 * use a similar approach to that of Solaris 7 as described in Solaris
43 * Internals by Jim Mauro and Richard McDougall. Turnstiles are looked up
44 * in a hash table based on the address of the lock. Each entry in the
45 * hash table is a linked-lists of turnstiles and is called a turnstile
46 * chain. Each chain contains a spin mutex that protects all of the
47 * turnstiles in the chain.
48 *
49 * Each time a thread is created, a turnstile is malloc'd and attached to
50 * that thread. When a thread blocks on a lock, if it is the first thread
51 * to block, it lends its turnstile to the lock. If the lock already has
52 * a turnstile, then it gives its turnstile to the lock's turnstile's free
53 * list. When a thread is woken up, it takes a thread from the free list
54 * if there are any other waiters. If it is the only thread blocked on the
55 * lock, then it reclaims the turnstile associated with the lock and removes
56 * it from the hash table.
57 *
58 * XXX: We should probably implement some sort of sleep queue that condition
59 * variables and sleepqueue's share. On Solaris condition variables are
60 * implemented using a hash table of sleep queues similar to our current
61 * sleep queues. We might want to investigate doing that ourselves.
34 */
35
36#include <sys/cdefs.h>
62 */
63
64#include <sys/cdefs.h>
37__FBSDID("$FreeBSD: head/sys/kern/subr_turnstile.c 118272 2003-07-31 18:52:18Z jhb $");
65__FBSDID("$FreeBSD: head/sys/kern/subr_turnstile.c 122514 2003-11-11 22:07:29Z jhb $");
38
66
39#include "opt_adaptive_mutexes.h"
40#include "opt_ddb.h"
41
42#include <sys/param.h>
43#include <sys/systm.h>
67#include <sys/param.h>
68#include <sys/systm.h>
44#include <sys/bus.h>
45#include <sys/kernel.h>
46#include <sys/ktr.h>
47#include <sys/lock.h>
48#include <sys/malloc.h>
49#include <sys/mutex.h>
50#include <sys/proc.h>
69#include <sys/kernel.h>
70#include <sys/ktr.h>
71#include <sys/lock.h>
72#include <sys/malloc.h>
73#include <sys/mutex.h>
74#include <sys/proc.h>
75#include <sys/queue.h>
51#include <sys/resourcevar.h>
76#include <sys/resourcevar.h>
77#include <sys/turnstile.h>
52#include <sys/sched.h>
78#include <sys/sched.h>
53#include <sys/sbuf.h>
54#include <sys/sysctl.h>
55#include <sys/vmmeter.h>
56
79
57#include <machine/atomic.h>
58#include <machine/bus.h>
59#include <machine/clock.h>
60#include <machine/cpu.h>
61
62#include <ddb/ddb.h>
63
64#include <vm/vm.h>
65#include <vm/vm_extern.h>
66
67/*
80/*
68 * Internal utility macros.
81 * Constants for the hash table of turnstile chains. TC_SHIFT is a magic
82 * number chosen because the sleep queue's use the same value for the
83 * shift. Basically, we ignore the lower 8 bits of the address.
84 * TC_TABLESIZE must be a power of two for TC_MASK to work properly.
69 */
85 */
70#define mtx_unowned(m) ((m)->mtx_lock == MTX_UNOWNED)
86#define TC_TABLESIZE 128 /* Must be power of 2. */
87#define TC_MASK (TC_TABLESIZE - 1)
88#define TC_SHIFT 8
89#define TC_HASH(lock) (((uintptr_t)(lock) >> TC_SHIFT) & TC_MASK)
90#define TC_LOOKUP(lock) &turnstile_chains[TC_HASH(lock)]
71
91
72#define mtx_owner(m) (mtx_unowned((m)) ? NULL \
73 : (struct thread *)((m)->mtx_lock & MTX_FLAGMASK))
74
75/*
92/*
76 * Lock classes for sleep and spin mutexes.
93 * There are three different lists of turnstiles as follows. The list
94 * connected by ts_link entries is a per-thread list of all the turnstiles
95 * attached to locks that we own. This is used to fixup our priority when
96 * a lock is released. The other two lists use the ts_hash entries. The
97 * first of these two is turnstile chain list that a turnstile is on when
98 * it is attached to a lock. The second list to use ts_hash is the free
99 * list hung off a turnstile that is attached to a lock.
100 *
101 * Each turnstile contains two lists of threads. The ts_blocked list is
102 * a linked list of threads blocked on the turnstile's lock. The
103 * ts_pending list is a linked list of threads previously awoken by
104 * turnstile_signal() or turnstile_wait() that are waiting to be put on
105 * the run queue.
106 *
107 * Locking key:
108 * c - turnstile chain lock
109 * q - td_contested lock
77 */
110 */
78struct lock_class lock_class_mtx_sleep = {
79 "sleep mutex",
80 LC_SLEEPLOCK | LC_RECURSABLE
111struct turnstile {
112 TAILQ_HEAD(, thread) ts_blocked; /* (c + q) Blocked threads. */
113 TAILQ_HEAD(, thread) ts_pending; /* (c) Pending threads. */
114 LIST_ENTRY(turnstile) ts_hash; /* (c) Chain and free list. */
115 LIST_ENTRY(turnstile) ts_link; /* (q) Contested locks. */
116 LIST_HEAD(, turnstile) ts_free; /* (c) Free turnstiles. */
117 struct lock_object *ts_lockobj; /* (c) Lock we reference. */
118 struct thread *ts_owner; /* (q) Who owns the lock. */
81};
119};
82struct lock_class lock_class_mtx_spin = {
83 "spin mutex",
84 LC_SPINLOCK | LC_RECURSABLE
120
121struct turnstile_chain {
122 LIST_HEAD(, turnstile) tc_turnstiles; /* List of turnstiles. */
123 struct mtx tc_lock; /* Spin lock for this chain. */
85};
86
124};
125
87/*
88 * System-wide mutexes
89 */
90struct mtx sched_lock;
91struct mtx Giant;
126static struct mtx td_contested_lock;
127static struct turnstile_chain turnstile_chains[TC_TABLESIZE];
92
128
129MALLOC_DEFINE(M_TURNSTILE, "turnstiles", "turnstiles");
130
93/*
94 * Prototypes for non-exported routines.
95 */
131/*
132 * Prototypes for non-exported routines.
133 */
134static void init_turnstile0(void *dummy);
96static void propagate_priority(struct thread *);
135static void propagate_priority(struct thread *);
136static void turnstile_setowner(struct turnstile *ts, struct thread *owner);
97
137
138/*
139 * Walks the chain of turnstiles and their owners to propagate the priority
140 * of the thread being blocked to all the threads holding locks that have to
141 * release their locks before this thread can run again.
142 */
98static void
99propagate_priority(struct thread *td)
100{
143static void
144propagate_priority(struct thread *td)
145{
101 int pri = td->td_priority;
102 struct mtx *m = td->td_blocked;
146 struct turnstile_chain *tc;
147 struct turnstile *ts;
148 struct thread *td1;
149 int pri;
103
104 mtx_assert(&sched_lock, MA_OWNED);
150
151 mtx_assert(&sched_lock, MA_OWNED);
152 pri = td->td_priority;
153 ts = td->td_blocked;
105 for (;;) {
154 for (;;) {
106 struct thread *td1;
155 td = ts->ts_owner;
107
156
108 td = mtx_owner(m);
109
110 if (td == NULL) {
111 /*
112 * This really isn't quite right. Really
113 * ought to bump priority of thread that
157 if (td == NULL) {
158 /*
159 * This really isn't quite right. Really
160 * ought to bump priority of thread that
114 * next acquires the mutex.
161 * next acquires the lock.
115 */
162 */
116 MPASS(m->mtx_lock == MTX_CONTESTED);
117 return;
118 }
119
120 MPASS(td->td_proc != NULL);
121 MPASS(td->td_proc->p_magic == P_MAGIC);
163 return;
164 }
165
166 MPASS(td->td_proc != NULL);
167 MPASS(td->td_proc->p_magic == P_MAGIC);
122 KASSERT(!TD_IS_SLEEPING(td), (
123 "sleeping thread (pid %d) owns a mutex",
168
169 /*
170 * XXX: The owner of a turnstile can be stale if it is the
171 * first thread to grab a slock of a sx lock. In that case
172 * it is possible for us to be at SSLEEP or some other
173 * weird state. We should probably just return if the state
174 * isn't SRUN or SLOCK.
175 */
176 KASSERT(!TD_IS_SLEEPING(td),
177 ("sleeping thread (pid %d) owns a non-sleepable lock",
124 td->td_proc->p_pid));
178 td->td_proc->p_pid));
125 if (td->td_priority <= pri) /* lower is higher priority */
179
180 /*
181 * If this thread already has higher priority than the
182 * thread that is being blocked, we are finished.
183 */
184 if (td->td_priority <= pri)
126 return;
127
185 return;
186
128
129 /*
130 * If lock holder is actually running, just bump priority.
131 */
132 if (TD_IS_RUNNING(td)) {
133 td->td_priority = pri;
134 return;
135 }
136

--- 10 unchanged lines hidden (view full) ---

147 * XXXKSE this gets a lot more complicated under threads
148 * but try anyhow.
149 */
150 if (TD_ON_RUNQ(td)) {
151 MPASS(td->td_blocked == NULL);
152 sched_prio(td, pri);
153 return;
154 }
187 /*
188 * If lock holder is actually running, just bump priority.
189 */
190 if (TD_IS_RUNNING(td)) {
191 td->td_priority = pri;
192 return;
193 }
194

--- 10 unchanged lines hidden (view full) ---

205 * XXXKSE this gets a lot more complicated under threads
206 * but try anyhow.
207 */
208 if (TD_ON_RUNQ(td)) {
209 MPASS(td->td_blocked == NULL);
210 sched_prio(td, pri);
211 return;
212 }
213
155 /*
214 /*
156 * Adjust for any other cases.
215 * Bump this thread's priority.
157 */
158 td->td_priority = pri;
159
160 /*
216 */
217 td->td_priority = pri;
218
219 /*
161 * If we aren't blocked on a mutex, we should be.
220 * If we aren't blocked on a lock, we should be.
162 */
163 KASSERT(TD_ON_LOCK(td), (
221 */
222 KASSERT(TD_ON_LOCK(td), (
164 "process %d(%s):%d holds %s but isn't blocked on a mutex\n",
223 "process %d(%s):%d holds %s but isn't blocked on a lock\n",
165 td->td_proc->p_pid, td->td_proc->p_comm, td->td_state,
224 td->td_proc->p_pid, td->td_proc->p_comm, td->td_state,
166 m->mtx_object.lo_name));
225 ts->ts_lockobj->lo_name));
167
168 /*
226
227 /*
169 * Pick up the mutex that td is blocked on.
228 * Pick up the lock that td is blocked on.
170 */
229 */
171 m = td->td_blocked;
172 MPASS(m != NULL);
230 ts = td->td_blocked;
231 MPASS(ts != NULL);
232 tc = TC_LOOKUP(ts->ts_lockobj);
233 mtx_lock_spin(&tc->tc_lock);
173
174 /*
175 * Check if the thread needs to be moved up on
234
235 /*
236 * Check if the thread needs to be moved up on
176 * the blocked chain
237 * the blocked chain. It doesn't need to be moved
238 * if it is already at the head of the list or if
239 * the item in front of it still has a higher priority.
177 */
240 */
178 if (td == TAILQ_FIRST(&m->mtx_blocked)) {
241 if (td == TAILQ_FIRST(&ts->ts_blocked)) {
242 mtx_unlock_spin(&tc->tc_lock);
179 continue;
180 }
181
182 td1 = TAILQ_PREV(td, threadqueue, td_lockq);
183 if (td1->td_priority <= pri) {
243 continue;
244 }
245
246 td1 = TAILQ_PREV(td, threadqueue, td_lockq);
247 if (td1->td_priority <= pri) {
248 mtx_unlock_spin(&tc->tc_lock);
184 continue;
185 }
186
187 /*
188 * Remove thread from blocked chain and determine where
189 * it should be moved up to. Since we know that td1 has
190 * a lower priority than td, we know that at least one
191 * thread in the chain has a lower priority and that
192 * td1 will thus not be NULL after the loop.
193 */
249 continue;
250 }
251
252 /*
253 * Remove thread from blocked chain and determine where
254 * it should be moved up to. Since we know that td1 has
255 * a lower priority than td, we know that at least one
256 * thread in the chain has a lower priority and that
257 * td1 will thus not be NULL after the loop.
258 */
194 TAILQ_REMOVE(&m->mtx_blocked, td, td_lockq);
195 TAILQ_FOREACH(td1, &m->mtx_blocked, td_lockq) {
259 mtx_lock_spin(&td_contested_lock);
260 TAILQ_REMOVE(&ts->ts_blocked, td, td_lockq);
261 TAILQ_FOREACH(td1, &ts->ts_blocked, td_lockq) {
196 MPASS(td1->td_proc->p_magic == P_MAGIC);
197 if (td1->td_priority > pri)
198 break;
199 }
200
201 MPASS(td1 != NULL);
202 TAILQ_INSERT_BEFORE(td1, td, td_lockq);
262 MPASS(td1->td_proc->p_magic == P_MAGIC);
263 if (td1->td_priority > pri)
264 break;
265 }
266
267 MPASS(td1 != NULL);
268 TAILQ_INSERT_BEFORE(td1, td, td_lockq);
269 mtx_unlock_spin(&td_contested_lock);
203 CTR4(KTR_LOCK,
270 CTR4(KTR_LOCK,
204 "propagate_priority: p %p moved before %p on [%p] %s",
205 td, td1, m, m->mtx_object.lo_name);
271 "propagate_priority: td %p moved before %p on [%p] %s",
272 td, td1, ts->ts_lockobj, ts->ts_lockobj->lo_name);
273 mtx_unlock_spin(&tc->tc_lock);
206 }
207}
208
274 }
275}
276
209#ifdef MUTEX_PROFILING
210SYSCTL_NODE(_debug, OID_AUTO, mutex, CTLFLAG_RD, NULL, "mutex debugging");
211SYSCTL_NODE(_debug_mutex, OID_AUTO, prof, CTLFLAG_RD, NULL, "mutex profiling");
212static int mutex_prof_enable = 0;
213SYSCTL_INT(_debug_mutex_prof, OID_AUTO, enable, CTLFLAG_RW,
214 &mutex_prof_enable, 0, "Enable tracing of mutex holdtime");
215
216struct mutex_prof {
217 const char *name;
218 const char *file;
219 int line;
220 uintmax_t cnt_max;
221 uintmax_t cnt_tot;
222 uintmax_t cnt_cur;
223 struct mutex_prof *next;
224};
225
226/*
277/*
227 * mprof_buf is a static pool of profiling records to avoid possible
228 * reentrance of the memory allocation functions.
229 *
230 * Note: NUM_MPROF_BUFFERS must be smaller than MPROF_HASH_SIZE.
278 * Early initialization of turnstiles. This is not done via a SYSINIT()
279 * since this needs to be initialized very early when mutexes are first
280 * initialized.
231 */
281 */
232#define NUM_MPROF_BUFFERS 1000
233static struct mutex_prof mprof_buf[NUM_MPROF_BUFFERS];
234static int first_free_mprof_buf;
235#define MPROF_HASH_SIZE 1009
236static struct mutex_prof *mprof_hash[MPROF_HASH_SIZE];
237/* SWAG: sbuf size = avg stat. line size * number of locks */
238#define MPROF_SBUF_SIZE 256 * 400
239
240static int mutex_prof_acquisitions;
241SYSCTL_INT(_debug_mutex_prof, OID_AUTO, acquisitions, CTLFLAG_RD,
242 &mutex_prof_acquisitions, 0, "Number of mutex acquistions recorded");
243static int mutex_prof_records;
244SYSCTL_INT(_debug_mutex_prof, OID_AUTO, records, CTLFLAG_RD,
245 &mutex_prof_records, 0, "Number of profiling records");
246static int mutex_prof_maxrecords = NUM_MPROF_BUFFERS;
247SYSCTL_INT(_debug_mutex_prof, OID_AUTO, maxrecords, CTLFLAG_RD,
248 &mutex_prof_maxrecords, 0, "Maximum number of profiling records");
249static int mutex_prof_rejected;
250SYSCTL_INT(_debug_mutex_prof, OID_AUTO, rejected, CTLFLAG_RD,
251 &mutex_prof_rejected, 0, "Number of rejected profiling records");
252static int mutex_prof_hashsize = MPROF_HASH_SIZE;
253SYSCTL_INT(_debug_mutex_prof, OID_AUTO, hashsize, CTLFLAG_RD,
254 &mutex_prof_hashsize, 0, "Hash size");
255static int mutex_prof_collisions = 0;
256SYSCTL_INT(_debug_mutex_prof, OID_AUTO, collisions, CTLFLAG_RD,
257 &mutex_prof_collisions, 0, "Number of hash collisions");
258
259/*
260 * mprof_mtx protects the profiling buffers and the hash.
261 */
262static struct mtx mprof_mtx;
263MTX_SYSINIT(mprof, &mprof_mtx, "mutex profiling lock", MTX_SPIN | MTX_QUIET);
264
265static u_int64_t
266nanoseconds(void)
282void
283init_turnstiles(void)
267{
284{
268 struct timespec tv;
285 int i;
269
286
270 nanotime(&tv);
271 return (tv.tv_sec * (u_int64_t)1000000000 + tv.tv_nsec);
287 for (i = 0; i < TC_TABLESIZE; i++) {
288 LIST_INIT(&turnstile_chains[i].tc_turnstiles);
289 mtx_init(&turnstile_chains[i].tc_lock, "turnstile chain",
290 NULL, MTX_SPIN);
291 }
292 mtx_init(&td_contested_lock, "td_contested", NULL, MTX_SPIN);
293#ifdef INVARIANTS
294 thread0.td_turnstile = NULL;
295#endif
272}
273
296}
297
274static int
275dump_mutex_prof_stats(SYSCTL_HANDLER_ARGS)
298static void
299init_turnstile0(void *dummy)
276{
300{
277 struct sbuf *sb;
278 int error, i;
279 static int multiplier = 1;
280
301
281 if (first_free_mprof_buf == 0)
282 return (SYSCTL_OUT(req, "No locking recorded",
283 sizeof("No locking recorded")));
284
285retry_sbufops:
286 sb = sbuf_new(NULL, NULL, MPROF_SBUF_SIZE * multiplier, SBUF_FIXEDLEN);
287 sbuf_printf(sb, "%6s %12s %11s %5s %s\n",
288 "max", "total", "count", "avg", "name");
289 /*
290 * XXX this spinlock seems to be by far the largest perpetrator
291 * of spinlock latency (1.6 msec on an Athlon1600 was recorded
292 * even before I pessimized it further by moving the average
293 * computation here).
294 */
295 mtx_lock_spin(&mprof_mtx);
296 for (i = 0; i < first_free_mprof_buf; ++i) {
297 sbuf_printf(sb, "%6ju %12ju %11ju %5ju %s:%d (%s)\n",
298 mprof_buf[i].cnt_max / 1000,
299 mprof_buf[i].cnt_tot / 1000,
300 mprof_buf[i].cnt_cur,
301 mprof_buf[i].cnt_cur == 0 ? (uintmax_t)0 :
302 mprof_buf[i].cnt_tot / (mprof_buf[i].cnt_cur * 1000),
303 mprof_buf[i].file, mprof_buf[i].line, mprof_buf[i].name);
304 if (sbuf_overflowed(sb)) {
305 mtx_unlock_spin(&mprof_mtx);
306 sbuf_delete(sb);
307 multiplier++;
308 goto retry_sbufops;
309 }
310 }
311 mtx_unlock_spin(&mprof_mtx);
312 sbuf_finish(sb);
313 error = SYSCTL_OUT(req, sbuf_data(sb), sbuf_len(sb) + 1);
314 sbuf_delete(sb);
315 return (error);
302 thread0.td_turnstile = turnstile_alloc();
316}
303}
317SYSCTL_PROC(_debug_mutex_prof, OID_AUTO, stats, CTLTYPE_STRING | CTLFLAG_RD,
318 NULL, 0, dump_mutex_prof_stats, "A", "Mutex profiling statistics");
319#endif
304SYSINIT(turnstile0, SI_SUB_LOCK, SI_ORDER_ANY, init_turnstile0, NULL);
320
321/*
305
306/*
322 * Function versions of the inlined __mtx_* macros. These are used by
323 * modules and can also be called from assembly language if needed.
307 * Set the owner of the lock this turnstile is attached to.
324 */
308 */
325void
326_mtx_lock_flags(struct mtx *m, int opts, const char *file, int line)
309static void
310turnstile_setowner(struct turnstile *ts, struct thread *owner)
327{
328
311{
312
329 MPASS(curthread != NULL);
330 KASSERT(m->mtx_object.lo_class == &lock_class_mtx_sleep,
331 ("mtx_lock() of spin mutex %s @ %s:%d", m->mtx_object.lo_name,
332 file, line));
333 _get_sleep_lock(m, curthread, opts, file, line);
334 LOCK_LOG_LOCK("LOCK", &m->mtx_object, opts, m->mtx_recurse, file,
335 line);
336 WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
337#ifdef MUTEX_PROFILING
338 /* don't reset the timer when/if recursing */
339 if (m->mtx_acqtime == 0) {
340 m->mtx_filename = file;
341 m->mtx_lineno = line;
342 m->mtx_acqtime = mutex_prof_enable ? nanoseconds() : 0;
343 ++mutex_prof_acquisitions;
344 }
345#endif
313 mtx_assert(&td_contested_lock, MA_OWNED);
314 MPASS(owner->td_proc->p_magic == P_MAGIC);
315 MPASS(ts->ts_owner == NULL);
316 ts->ts_owner = owner;
317 LIST_INSERT_HEAD(&owner->td_contested, ts, ts_link);
346}
347
318}
319
348void
349_mtx_unlock_flags(struct mtx *m, int opts, const char *file, int line)
320/*
321 * Malloc a turnstile for a new thread, initialize it and return it.
322 */
323struct turnstile *
324turnstile_alloc(void)
350{
325{
326 struct turnstile *ts;
351
327
352 MPASS(curthread != NULL);
353 KASSERT(m->mtx_object.lo_class == &lock_class_mtx_sleep,
354 ("mtx_unlock() of spin mutex %s @ %s:%d", m->mtx_object.lo_name,
355 file, line));
356 WITNESS_UNLOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
357 LOCK_LOG_LOCK("UNLOCK", &m->mtx_object, opts, m->mtx_recurse, file,
358 line);
359 mtx_assert(m, MA_OWNED);
360#ifdef MUTEX_PROFILING
361 if (m->mtx_acqtime != 0) {
362 static const char *unknown = "(unknown)";
363 struct mutex_prof *mpp;
364 u_int64_t acqtime, now;
365 const char *p, *q;
366 volatile u_int hash;
367
368 now = nanoseconds();
369 acqtime = m->mtx_acqtime;
370 m->mtx_acqtime = 0;
371 if (now <= acqtime)
372 goto out;
373 for (p = m->mtx_filename;
374 p != NULL && strncmp(p, "../", 3) == 0; p += 3)
375 /* nothing */ ;
376 if (p == NULL || *p == '\0')
377 p = unknown;
378 for (hash = m->mtx_lineno, q = p; *q != '\0'; ++q)
379 hash = (hash * 2 + *q) % MPROF_HASH_SIZE;
380 mtx_lock_spin(&mprof_mtx);
381 for (mpp = mprof_hash[hash]; mpp != NULL; mpp = mpp->next)
382 if (mpp->line == m->mtx_lineno &&
383 strcmp(mpp->file, p) == 0)
384 break;
385 if (mpp == NULL) {
386 /* Just exit if we cannot get a trace buffer */
387 if (first_free_mprof_buf >= NUM_MPROF_BUFFERS) {
388 ++mutex_prof_rejected;
389 goto unlock;
390 }
391 mpp = &mprof_buf[first_free_mprof_buf++];
392 mpp->name = mtx_name(m);
393 mpp->file = p;
394 mpp->line = m->mtx_lineno;
395 mpp->next = mprof_hash[hash];
396 if (mprof_hash[hash] != NULL)
397 ++mutex_prof_collisions;
398 mprof_hash[hash] = mpp;
399 ++mutex_prof_records;
400 }
401 /*
402 * Record if the mutex has been held longer now than ever
403 * before.
404 */
405 if (now - acqtime > mpp->cnt_max)
406 mpp->cnt_max = now - acqtime;
407 mpp->cnt_tot += now - acqtime;
408 mpp->cnt_cur++;
409unlock:
410 mtx_unlock_spin(&mprof_mtx);
411 }
412out:
413#endif
414 _rel_sleep_lock(m, curthread, opts, file, line);
328 ts = malloc(sizeof(struct turnstile), M_TURNSTILE, M_WAITOK | M_ZERO);
329 TAILQ_INIT(&ts->ts_blocked);
330 TAILQ_INIT(&ts->ts_pending);
331 LIST_INIT(&ts->ts_free);
332 return (ts);
415}
416
333}
334
335/*
336 * Free a turnstile when a thread is destroyed.
337 */
417void
338void
418_mtx_lock_spin_flags(struct mtx *m, int opts, const char *file, int line)
339turnstile_free(struct turnstile *ts)
419{
420
340{
341
421 MPASS(curthread != NULL);
422 KASSERT(m->mtx_object.lo_class == &lock_class_mtx_spin,
423 ("mtx_lock_spin() of sleep mutex %s @ %s:%d",
424 m->mtx_object.lo_name, file, line));
425#if defined(SMP) || LOCK_DEBUG > 0 || 1
426 _get_spin_lock(m, curthread, opts, file, line);
427#else
428 critical_enter();
429#endif
430 LOCK_LOG_LOCK("LOCK", &m->mtx_object, opts, m->mtx_recurse, file,
431 line);
432 WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
342 MPASS(ts != NULL);
343 MPASS(TAILQ_EMPTY(&ts->ts_blocked));
344 MPASS(TAILQ_EMPTY(&ts->ts_pending));
345 free(ts, M_TURNSTILE);
433}
434
346}
347
435void
436_mtx_unlock_spin_flags(struct mtx *m, int opts, const char *file, int line)
437{
438
439 MPASS(curthread != NULL);
440 KASSERT(m->mtx_object.lo_class == &lock_class_mtx_spin,
441 ("mtx_unlock_spin() of sleep mutex %s @ %s:%d",
442 m->mtx_object.lo_name, file, line));
443 WITNESS_UNLOCK(&m->mtx_object, opts | LOP_EXCLUSIVE, file, line);
444 LOCK_LOG_LOCK("UNLOCK", &m->mtx_object, opts, m->mtx_recurse, file,
445 line);
446 mtx_assert(m, MA_OWNED);
447#if defined(SMP) || LOCK_DEBUG > 0 || 1
448 _rel_spin_lock(m);
449#else
450 critical_exit();
451#endif
452}
453
454/*
348/*
455 * The important part of mtx_trylock{,_flags}()
456 * Tries to acquire lock `m.' We do NOT handle recursion here. If this
457 * function is called on a recursed mutex, it will return failure and
458 * will not recursively acquire the lock. You are expected to know what
459 * you are doing.
349 * Look up the turnstile for a lock in the hash table locking the associated
350 * turnstile chain along the way. Return with the turnstile chain locked.
351 * If no turnstile is found in the hash table, NULL is returned.
460 */
352 */
461int
462_mtx_trylock(struct mtx *m, int opts, const char *file, int line)
353struct turnstile *
354turnstile_lookup(struct lock_object *lock)
463{
355{
464 int rval;
356 struct turnstile_chain *tc;
357 struct turnstile *ts;
465
358
466 MPASS(curthread != NULL);
467
468 rval = _obtain_lock(m, curthread);
469
470 LOCK_LOG_TRY("LOCK", &m->mtx_object, opts, rval, file, line);
471 if (rval)
472 WITNESS_LOCK(&m->mtx_object, opts | LOP_EXCLUSIVE | LOP_TRYLOCK,
473 file, line);
474
475 return (rval);
359 tc = TC_LOOKUP(lock);
360 mtx_lock_spin(&tc->tc_lock);
361 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash)
362 if (ts->ts_lockobj == lock)
363 return (ts);
364 return (NULL);
476}
477
478/*
365}
366
367/*
479 * _mtx_lock_sleep: the tougher part of acquiring an MTX_DEF lock.
480 *
481 * We call this if the lock is either contested (i.e. we need to go to
482 * sleep waiting for it), or if we need to recurse on it.
368 * Unlock the turnstile chain associated with a given lock.
483 */
484void
369 */
370void
485_mtx_lock_sleep(struct mtx *m, int opts, const char *file, int line)
371turnstile_release(struct lock_object *lock)
486{
372{
487 struct thread *td = curthread;
488 struct thread *td1;
489#if defined(SMP) && defined(ADAPTIVE_MUTEXES)
490 struct thread *owner;
491#endif
492 uintptr_t v;
493#ifdef KTR
494 int cont_logged = 0;
495#endif
373 struct turnstile_chain *tc;
496
374
497 if (mtx_owned(m)) {
498 m->mtx_recurse++;
499 atomic_set_ptr(&m->mtx_lock, MTX_RECURSED);
500 if (LOCK_LOG_TEST(&m->mtx_object, opts))
501 CTR1(KTR_LOCK, "_mtx_lock_sleep: %p recursing", m);
502 return;
503 }
504
505 if (LOCK_LOG_TEST(&m->mtx_object, opts))
506 CTR4(KTR_LOCK,
507 "_mtx_lock_sleep: %s contested (lock=%p) at %s:%d",
508 m->mtx_object.lo_name, (void *)m->mtx_lock, file, line);
509
510 while (!_obtain_lock(m, td)) {
511
512 mtx_lock_spin(&sched_lock);
513 v = m->mtx_lock;
514
515 /*
516 * Check if the lock has been released while spinning for
517 * the sched_lock.
518 */
519 if (v == MTX_UNOWNED) {
520 mtx_unlock_spin(&sched_lock);
521#ifdef __i386__
522 ia32_pause();
523#endif
524 continue;
525 }
526
527 /*
528 * The mutex was marked contested on release. This means that
529 * there are other threads blocked on it. Grab ownership of
530 * it and propagate its priority to the current thread if
531 * necessary.
532 */
533 if (v == MTX_CONTESTED) {
534 td1 = TAILQ_FIRST(&m->mtx_blocked);
535 MPASS(td1 != NULL);
536 m->mtx_lock = (uintptr_t)td | MTX_CONTESTED;
537 LIST_INSERT_HEAD(&td->td_contested, m, mtx_contested);
538
539 if (td1->td_priority < td->td_priority)
540 td->td_priority = td1->td_priority;
541 mtx_unlock_spin(&sched_lock);
542 return;
543 }
544
545 /*
546 * If the mutex isn't already contested and a failure occurs
547 * setting the contested bit, the mutex was either released
548 * or the state of the MTX_RECURSED bit changed.
549 */
550 if ((v & MTX_CONTESTED) == 0 &&
551 !atomic_cmpset_ptr(&m->mtx_lock, (void *)v,
552 (void *)(v | MTX_CONTESTED))) {
553 mtx_unlock_spin(&sched_lock);
554#ifdef __i386__
555 ia32_pause();
556#endif
557 continue;
558 }
559
560#if defined(SMP) && defined(ADAPTIVE_MUTEXES)
561 /*
562 * If the current owner of the lock is executing on another
563 * CPU, spin instead of blocking.
564 */
565 owner = (struct thread *)(v & MTX_FLAGMASK);
566 if (m != &Giant && TD_IS_RUNNING(owner)) {
567 mtx_unlock_spin(&sched_lock);
568 while (mtx_owner(m) == owner && TD_IS_RUNNING(owner)) {
569#ifdef __i386__
570 ia32_pause();
571#endif
572 }
573 continue;
574 }
575#endif /* SMP && ADAPTIVE_MUTEXES */
576
577 /*
578 * We definitely must sleep for this lock.
579 */
580 mtx_assert(m, MA_NOTOWNED);
581
582#ifdef notyet
583 /*
584 * If we're borrowing an interrupted thread's VM context, we
585 * must clean up before going to sleep.
586 */
587 if (td->td_ithd != NULL) {
588 struct ithd *it = td->td_ithd;
589
590 if (it->it_interrupted) {
591 if (LOCK_LOG_TEST(&m->mtx_object, opts))
592 CTR2(KTR_LOCK,
593 "_mtx_lock_sleep: %p interrupted %p",
594 it, it->it_interrupted);
595 intr_thd_fixup(it);
596 }
597 }
598#endif
599
600 /*
601 * Put us on the list of threads blocked on this mutex
602 * and add this mutex to the owning thread's list of
603 * contested mutexes if needed.
604 */
605 if (TAILQ_EMPTY(&m->mtx_blocked)) {
606 td1 = mtx_owner(m);
607 LIST_INSERT_HEAD(&td1->td_contested, m, mtx_contested);
608 TAILQ_INSERT_TAIL(&m->mtx_blocked, td, td_lockq);
609 } else {
610 TAILQ_FOREACH(td1, &m->mtx_blocked, td_lockq)
611 if (td1->td_priority > td->td_priority)
612 break;
613 if (td1)
614 TAILQ_INSERT_BEFORE(td1, td, td_lockq);
615 else
616 TAILQ_INSERT_TAIL(&m->mtx_blocked, td, td_lockq);
617 }
618#ifdef KTR
619 if (!cont_logged) {
620 CTR6(KTR_CONTENTION,
621 "contention: %p at %s:%d wants %s, taken by %s:%d",
622 td, file, line, m->mtx_object.lo_name,
623 WITNESS_FILE(&m->mtx_object),
624 WITNESS_LINE(&m->mtx_object));
625 cont_logged = 1;
626 }
627#endif
628
629 /*
630 * Save who we're blocked on.
631 */
632 td->td_blocked = m;
633 td->td_lockname = m->mtx_object.lo_name;
634 TD_SET_LOCK(td);
635 propagate_priority(td);
636
637 if (LOCK_LOG_TEST(&m->mtx_object, opts))
638 CTR3(KTR_LOCK,
639 "_mtx_lock_sleep: p %p blocked on [%p] %s", td, m,
640 m->mtx_object.lo_name);
641
642 td->td_proc->p_stats->p_ru.ru_nvcsw++;
643 mi_switch();
644
645 if (LOCK_LOG_TEST(&m->mtx_object, opts))
646 CTR3(KTR_LOCK,
647 "_mtx_lock_sleep: p %p free from blocked on [%p] %s",
648 td, m, m->mtx_object.lo_name);
649
650 mtx_unlock_spin(&sched_lock);
651 }
652
653#ifdef KTR
654 if (cont_logged) {
655 CTR4(KTR_CONTENTION,
656 "contention end: %s acquired by %p at %s:%d",
657 m->mtx_object.lo_name, td, file, line);
658 }
659#endif
660 return;
375 tc = TC_LOOKUP(lock);
376 mtx_unlock_spin(&tc->tc_lock);
661}
662
663/*
377}
378
379/*
664 * _mtx_lock_spin: the tougher part of acquiring an MTX_SPIN lock.
665 *
666 * This is only called if we need to actually spin for the lock. Recursion
667 * is handled inline.
380 * Take ownership of a turnstile and adjust the priority of the new
381 * owner appropriately.
668 */
669void
382 */
383void
670_mtx_lock_spin(struct mtx *m, int opts, const char *file, int line)
384turnstile_claim(struct turnstile *ts)
671{
385{
672 int i = 0;
386 struct turnstile_chain *tc;
387 struct thread *td, *owner;
673
388
674 if (LOCK_LOG_TEST(&m->mtx_object, opts))
675 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spinning", m);
389 tc = TC_LOOKUP(ts->ts_lockobj);
390 mtx_assert(&tc->tc_lock, MA_OWNED);
676
391
677 for (;;) {
678 if (_obtain_lock(m, curthread))
679 break;
392 owner = curthread;
393 mtx_lock_spin(&td_contested_lock);
394 turnstile_setowner(ts, owner);
395 mtx_unlock_spin(&td_contested_lock);
680
396
681 /* Give interrupts a chance while we spin. */
682 critical_exit();
683 while (m->mtx_lock != MTX_UNOWNED) {
684 if (i++ < 10000000) {
685#ifdef __i386__
686 ia32_pause();
687#endif
688 continue;
689 }
690 if (i < 60000000)
691 DELAY(1);
692#ifdef DDB
693 else if (!db_active) {
694#else
695 else {
696#endif
697 printf("spin lock %s held by %p for > 5 seconds\n",
698 m->mtx_object.lo_name, (void *)m->mtx_lock);
699#ifdef WITNESS
700 witness_display_spinlock(&m->mtx_object,
701 mtx_owner(m));
702#endif
703 panic("spin lock held too long");
704 }
705#ifdef __i386__
706 ia32_pause();
707#endif
708 }
709 critical_enter();
710 }
397 td = TAILQ_FIRST(&ts->ts_blocked);
398 MPASS(td != NULL);
399 MPASS(td->td_proc->p_magic == P_MAGIC);
400 mtx_unlock_spin(&tc->tc_lock);
711
401
712 if (LOCK_LOG_TEST(&m->mtx_object, opts))
713 CTR1(KTR_LOCK, "_mtx_lock_spin: %p spin done", m);
714
715 return;
402 /*
403 * Update the priority of the new owner if needed.
404 */
405 mtx_lock_spin(&sched_lock);
406 if (td->td_priority < owner->td_priority)
407 owner->td_priority = td->td_priority;
408 mtx_unlock_spin(&sched_lock);
716}
717
718/*
409}
410
411/*
719 * _mtx_unlock_sleep: the tougher part of releasing an MTX_DEF lock.
720 *
721 * We are only called here if the lock is recursed or contested (i.e. we
722 * need to wake up a blocked thread).
412 * Block the current thread on the turnstile ts. This function will context
413 * switch and not return until this thread has been woken back up. This
414 * function must be called with the appropriate turnstile chain locked and
415 * will return with it unlocked.
723 */
724void
416 */
417void
725_mtx_unlock_sleep(struct mtx *m, int opts, const char *file, int line)
418turnstile_wait(struct turnstile *ts, struct lock_object *lock,
419 struct thread *owner)
726{
420{
421 struct turnstile_chain *tc;
727 struct thread *td, *td1;
422 struct thread *td, *td1;
728 struct mtx *m1;
729 int pri;
730
731 td = curthread;
423
424 td = curthread;
425 tc = TC_LOOKUP(lock);
426 mtx_assert(&tc->tc_lock, MA_OWNED);
427 MPASS(td->td_turnstile != NULL);
428 MPASS(owner != NULL);
429 MPASS(owner->td_proc->p_magic == P_MAGIC);
732
430
733 if (mtx_recursed(m)) {
734 if (--(m->mtx_recurse) == 0)
735 atomic_clear_ptr(&m->mtx_lock, MTX_RECURSED);
736 if (LOCK_LOG_TEST(&m->mtx_object, opts))
737 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p unrecurse", m);
738 return;
431 /* If the passed in turnstile is NULL, use this thread's turnstile. */
432 if (ts == NULL) {
433 ts = td->td_turnstile;
434 LIST_INSERT_HEAD(&tc->tc_turnstiles, ts, ts_hash);
435 KASSERT(TAILQ_EMPTY(&ts->ts_pending),
436 ("thread's turnstile has pending threads"));
437 KASSERT(TAILQ_EMPTY(&ts->ts_blocked),
438 ("thread's turnstile has a non-empty queue"));
439 KASSERT(LIST_EMPTY(&ts->ts_free),
440 ("thread's turnstile has a non-empty free list"));
441 KASSERT(ts->ts_lockobj == NULL, ("stale ts_lockobj pointer"));
442 ts->ts_lockobj = lock;
443 mtx_lock_spin(&td_contested_lock);
444 TAILQ_INSERT_TAIL(&ts->ts_blocked, td, td_lockq);
445 turnstile_setowner(ts, owner);
446 mtx_unlock_spin(&td_contested_lock);
447 } else {
448 TAILQ_FOREACH(td1, &ts->ts_blocked, td_lockq)
449 if (td1->td_priority > td->td_priority)
450 break;
451 mtx_lock_spin(&td_contested_lock);
452 if (td1 != NULL)
453 TAILQ_INSERT_BEFORE(td1, td, td_lockq);
454 else
455 TAILQ_INSERT_TAIL(&ts->ts_blocked, td, td_lockq);
456 mtx_unlock_spin(&td_contested_lock);
457 MPASS(td->td_turnstile != NULL);
458 LIST_INSERT_HEAD(&ts->ts_free, td->td_turnstile, ts_hash);
459 MPASS(owner == ts->ts_owner);
739 }
460 }
461#ifdef INVARIANTS
462 td->td_turnstile = NULL;
463#endif
464 mtx_unlock_spin(&tc->tc_lock);
740
741 mtx_lock_spin(&sched_lock);
465
466 mtx_lock_spin(&sched_lock);
742 if (LOCK_LOG_TEST(&m->mtx_object, opts))
743 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p contested", m);
744
745 td1 = TAILQ_FIRST(&m->mtx_blocked);
746#if defined(SMP) && defined(ADAPTIVE_MUTEXES)
747 if (td1 == NULL) {
748 _release_lock_quick(m);
749 if (LOCK_LOG_TEST(&m->mtx_object, opts))
750 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p no sleepers", m);
467 /*
468 * Handle race condition where a thread on another CPU that owns
469 * lock 'lock' could have woken us in between us dropping the
470 * turnstile chain lock and acquiring the sched_lock.
471 */
472 if (td->td_flags & TDF_TSNOBLOCK) {
473 td->td_flags &= ~TDF_TSNOBLOCK;
751 mtx_unlock_spin(&sched_lock);
752 return;
753 }
474 mtx_unlock_spin(&sched_lock);
475 return;
476 }
754#endif
755 MPASS(td->td_proc->p_magic == P_MAGIC);
756 MPASS(td1->td_proc->p_magic == P_MAGIC);
477
478#ifdef notyet
479 /*
480 * If we're borrowing an interrupted thread's VM context, we
481 * must clean up before going to sleep.
482 */
483 if (td->td_ithd != NULL) {
484 struct ithd *it = td->td_ithd;
757
485
758 TAILQ_REMOVE(&m->mtx_blocked, td1, td_lockq);
759
760 LIST_REMOVE(m, mtx_contested);
761 if (TAILQ_EMPTY(&m->mtx_blocked)) {
762 _release_lock_quick(m);
763 if (LOCK_LOG_TEST(&m->mtx_object, opts))
764 CTR1(KTR_LOCK, "_mtx_unlock_sleep: %p not held", m);
765 } else
766 m->mtx_lock = MTX_CONTESTED;
767
768 pri = PRI_MAX;
769 LIST_FOREACH(m1, &td->td_contested, mtx_contested) {
770 int cp = TAILQ_FIRST(&m1->mtx_blocked)->td_priority;
771 if (cp < pri)
772 pri = cp;
486 if (it->it_interrupted) {
487 if (LOCK_LOG_TEST(lock, 0))
488 CTR3(KTR_LOCK, "%s: %p interrupted %p",
489 __func__, it, it->it_interrupted);
490 intr_thd_fixup(it);
491 }
773 }
492 }
493#endif
774
494
775 if (pri > td->td_base_pri)
776 pri = td->td_base_pri;
777 td->td_priority = pri;
495 /* Save who we are blocked on and switch. */
496 td->td_blocked = ts;
497 td->td_lockname = lock->lo_name;
498 TD_SET_LOCK(td);
499 propagate_priority(td);
778
500
779 if (LOCK_LOG_TEST(&m->mtx_object, opts))
780 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p contested setrunqueue %p",
781 m, td1);
501 if (LOCK_LOG_TEST(lock, 0))
502 CTR4(KTR_LOCK, "%s: td %p blocked on [%p] %s", __func__, td,
503 lock, lock->lo_name);
782
504
783 td1->td_blocked = NULL;
784 TD_CLR_LOCK(td1);
785 if (!TD_CAN_RUN(td1)) {
786 mtx_unlock_spin(&sched_lock);
787 return;
788 }
789 setrunqueue(td1);
505 td->td_proc->p_stats->p_ru.ru_nvcsw++;
506 mi_switch();
790
507
791 if (td->td_critnest == 1 && td1->td_priority < pri) {
792#ifdef notyet
793 if (td->td_ithd != NULL) {
794 struct ithd *it = td->td_ithd;
508 if (LOCK_LOG_TEST(lock, 0))
509 CTR4(KTR_LOCK, "%s: td %p free from blocked on [%p] %s",
510 __func__, td, lock, lock->lo_name);
795
511
796 if (it->it_interrupted) {
797 if (LOCK_LOG_TEST(&m->mtx_object, opts))
798 CTR2(KTR_LOCK,
799 "_mtx_unlock_sleep: %p interrupted %p",
800 it, it->it_interrupted);
801 intr_thd_fixup(it);
802 }
803 }
804#endif
805 if (LOCK_LOG_TEST(&m->mtx_object, opts))
806 CTR2(KTR_LOCK,
807 "_mtx_unlock_sleep: %p switching out lock=%p", m,
808 (void *)m->mtx_lock);
809
810 td->td_proc->p_stats->p_ru.ru_nivcsw++;
811 mi_switch();
812 if (LOCK_LOG_TEST(&m->mtx_object, opts))
813 CTR2(KTR_LOCK, "_mtx_unlock_sleep: %p resuming lock=%p",
814 m, (void *)m->mtx_lock);
815 }
816
817 mtx_unlock_spin(&sched_lock);
512 mtx_unlock_spin(&sched_lock);
818
819 return;
820}
821
822/*
513}
514
515/*
823 * All the unlocking of MTX_SPIN locks is done inline.
824 * See the _rel_spin_lock() macro for the details.
516 * Pick the highest priority thread on this turnstile and put it on the
517 * pending list. This must be called with the turnstile chain locked.
825 */
518 */
826
827/*
828 * The backing function for the INVARIANTS-enabled mtx_assert()
829 */
830#ifdef INVARIANT_SUPPORT
831void
832_mtx_assert(struct mtx *m, int what, const char *file, int line)
519int
520turnstile_signal(struct turnstile *ts)
833{
521{
522 struct turnstile_chain *tc;
523 struct thread *td;
524 int empty;
834
525
835 if (panicstr != NULL)
836 return;
837 switch (what) {
838 case MA_OWNED:
839 case MA_OWNED | MA_RECURSED:
840 case MA_OWNED | MA_NOTRECURSED:
841 if (!mtx_owned(m))
842 panic("mutex %s not owned at %s:%d",
843 m->mtx_object.lo_name, file, line);
844 if (mtx_recursed(m)) {
845 if ((what & MA_NOTRECURSED) != 0)
846 panic("mutex %s recursed at %s:%d",
847 m->mtx_object.lo_name, file, line);
848 } else if ((what & MA_RECURSED) != 0) {
849 panic("mutex %s unrecursed at %s:%d",
850 m->mtx_object.lo_name, file, line);
851 }
852 break;
853 case MA_NOTOWNED:
854 if (mtx_owned(m))
855 panic("mutex %s owned at %s:%d",
856 m->mtx_object.lo_name, file, line);
857 break;
858 default:
859 panic("unknown mtx_assert at %s:%d", file, line);
860 }
861}
862#endif
526 MPASS(ts != NULL);
527 MPASS(curthread->td_proc->p_magic == P_MAGIC);
528 MPASS(ts->ts_owner == curthread);
529 tc = TC_LOOKUP(ts->ts_lockobj);
530 mtx_assert(&tc->tc_lock, MA_OWNED);
863
531
864/*
865 * The MUTEX_DEBUG-enabled mtx_validate()
866 *
867 * Most of these checks have been moved off into the LO_INITIALIZED flag
868 * maintained by the witness code.
869 */
870#ifdef MUTEX_DEBUG
532 /*
533 * Pick the highest priority thread blocked on this lock and
534 * move it to the pending list.
535 */
536 td = TAILQ_FIRST(&ts->ts_blocked);
537 MPASS(td->td_proc->p_magic == P_MAGIC);
538 mtx_lock_spin(&td_contested_lock);
539 TAILQ_REMOVE(&ts->ts_blocked, td, td_lockq);
540 mtx_unlock_spin(&td_contested_lock);
541 TAILQ_INSERT_TAIL(&ts->ts_pending, td, td_lockq);
871
542
872void mtx_validate(struct mtx *);
873
874void
875mtx_validate(struct mtx *m)
876{
877
878/*
879 * XXX: When kernacc() does not require Giant we can reenable this check
880 */
881#ifdef notyet
882/*
883 * XXX - When kernacc() is fixed on the alpha to handle K0_SEG memory properly
884 * we can re-enable the kernacc() checks.
885 */
886#ifndef __alpha__
887 /*
543 /*
888 * Can't call kernacc() from early init386(), especially when
889 * initializing Giant mutex, because some stuff in kernacc()
890 * requires Giant itself.
544 * If the turnstile is now empty, remove it from its chain and
545 * give it to the about-to-be-woken thread. Otherwise take a
546 * turnstile from the free list and give it to the thread.
891 */
547 */
892 if (!cold)
893 if (!kernacc((caddr_t)m, sizeof(m),
894 VM_PROT_READ | VM_PROT_WRITE))
895 panic("Can't read and write to mutex %p", m);
896#endif
897#endif
898}
899#endif
548 empty = TAILQ_EMPTY(&ts->ts_blocked);
549 if (empty)
550 MPASS(LIST_EMPTY(&ts->ts_free));
551 else
552 ts = LIST_FIRST(&ts->ts_free);
553 LIST_REMOVE(ts, ts_hash);
554 td->td_turnstile = ts;
900
555
556 return (empty);
557}
558
901/*
559/*
902 * General init routine used by the MTX_SYSINIT() macro.
560 * Put all blocked threads on the pending list. This must be called with
561 * the turnstile chain locked.
903 */
904void
562 */
563void
905mtx_sysinit(void *arg)
564turnstile_wakeup(struct turnstile *ts)
906{
565{
907 struct mtx_args *margs = arg;
566 struct turnstile_chain *tc;
567 struct turnstile *ts1;
568 struct thread *td;
908
569
909 mtx_init(margs->ma_mtx, margs->ma_desc, NULL, margs->ma_opts);
910}
570 MPASS(ts != NULL);
571 MPASS(curthread->td_proc->p_magic == P_MAGIC);
572 MPASS(ts->ts_owner == curthread);
573 tc = TC_LOOKUP(ts->ts_lockobj);
574 mtx_assert(&tc->tc_lock, MA_OWNED);
911
575
576 /*
577 * Transfer the blocked list to the pending list.
578 */
579 mtx_lock_spin(&td_contested_lock);
580 TAILQ_CONCAT(&ts->ts_pending, &ts->ts_blocked, td_lockq);
581 mtx_unlock_spin(&td_contested_lock);
582
583 /*
584 * Give a turnstile to each thread. The last thread gets
585 * this turnstile.
586 */
587 TAILQ_FOREACH(td, &ts->ts_pending, td_lockq) {
588 if (LIST_EMPTY(&ts->ts_free)) {
589 MPASS(TAILQ_NEXT(td, td_lockq) == NULL);
590 ts1 = ts;
591 } else
592 ts1 = LIST_FIRST(&ts->ts_free);
593 LIST_REMOVE(ts1, ts_hash);
594 td->td_turnstile = ts1;
595 }
596}
597
912/*
598/*
913 * Mutex initialization routine; initialize lock `m' of type contained in
914 * `opts' with options contained in `opts' and name `name.' The optional
915 * lock type `type' is used as a general lock category name for use with
916 * witness.
599 * Wakeup all threads on the pending list and adjust the priority of the
600 * current thread appropriately. This must be called with the turnstile
601 * chain locked.
917 */
918void
602 */
603void
919mtx_init(struct mtx *m, const char *name, const char *type, int opts)
604turnstile_unpend(struct turnstile *ts)
920{
605{
921 struct lock_object *lock;
606 TAILQ_HEAD( ,thread) pending_threads;
607 struct turnstile_chain *tc;
608 struct thread *td;
609 int cp, pri;
922
610
923 MPASS((opts & ~(MTX_SPIN | MTX_QUIET | MTX_RECURSE |
924 MTX_NOWITNESS | MTX_DUPOK)) == 0);
611 MPASS(ts != NULL);
612 MPASS(ts->ts_owner == curthread);
613 tc = TC_LOOKUP(ts->ts_lockobj);
614 mtx_assert(&tc->tc_lock, MA_OWNED);
615 MPASS(!TAILQ_EMPTY(&ts->ts_pending));
925
616
926#ifdef MUTEX_DEBUG
927 /* Diagnostic and error correction */
928 mtx_validate(m);
617 /*
618 * Move the list of pending threads out of the turnstile and
619 * into a local variable.
620 */
621 TAILQ_INIT(&pending_threads);
622 TAILQ_CONCAT(&pending_threads, &ts->ts_pending, td_lockq);
623#ifdef INVARIANTS
624 if (TAILQ_EMPTY(&ts->ts_blocked))
625 ts->ts_lockobj = NULL;
929#endif
930
626#endif
627
931 lock = &m->mtx_object;
932 KASSERT((lock->lo_flags & LO_INITIALIZED) == 0,
933 ("mutex \"%s\" %p already initialized", name, m));
934 bzero(m, sizeof(*m));
935 if (opts & MTX_SPIN)
936 lock->lo_class = &lock_class_mtx_spin;
937 else
938 lock->lo_class = &lock_class_mtx_sleep;
939 lock->lo_name = name;
940 lock->lo_type = type != NULL ? type : name;
941 if (opts & MTX_QUIET)
942 lock->lo_flags = LO_QUIET;
943 if (opts & MTX_RECURSE)
944 lock->lo_flags |= LO_RECURSABLE;
945 if ((opts & MTX_NOWITNESS) == 0)
946 lock->lo_flags |= LO_WITNESS;
947 if (opts & MTX_DUPOK)
948 lock->lo_flags |= LO_DUPOK;
628 /*
629 * Remove the turnstile from this thread's list of contested locks
630 * since this thread doesn't own it anymore. New threads will
631 * not be blocking on the turnstile until it is claimed by a new
632 * owner.
633 */
634 mtx_lock_spin(&td_contested_lock);
635#ifdef INVARIANTS
636 ts->ts_owner = NULL;
637#endif
638 LIST_REMOVE(ts, ts_link);
639 mtx_unlock_spin(&td_contested_lock);
640 mtx_unlock_spin(&tc->tc_lock);
949
641
950 m->mtx_lock = MTX_UNOWNED;
951 TAILQ_INIT(&m->mtx_blocked);
642 /*
643 * Adjust the priority of curthread based on other contested
644 * locks it owns. Don't lower the priority below the base
645 * priority however.
646 */
647 td = curthread;
648 pri = PRI_MAX;
649 mtx_lock_spin(&sched_lock);
650 mtx_lock_spin(&td_contested_lock);
651 LIST_FOREACH(ts, &td->td_contested, ts_link) {
652 cp = TAILQ_FIRST(&ts->ts_blocked)->td_priority;
653 if (cp < pri)
654 pri = cp;
655 }
656 mtx_unlock_spin(&td_contested_lock);
657 if (pri > td->td_base_pri)
658 pri = td->td_base_pri;
659 td->td_priority = pri;
952
660
953 LOCK_LOG_INIT(lock, opts);
954
955 WITNESS_INIT(lock);
661 /*
662 * Wake up all the pending threads. If a thread is not blocked
663 * on a lock, then it is currently executing on another CPU in
664 * turnstile_wait(). Set a flag to force it to try to acquire
665 * the lock again instead of blocking.
666 */
667 while (!TAILQ_EMPTY(&pending_threads)) {
668 td = TAILQ_FIRST(&pending_threads);
669 TAILQ_REMOVE(&pending_threads, td, td_lockq);
670 MPASS(td->td_proc->p_magic == P_MAGIC);
671 if (TD_ON_LOCK(td)) {
672 td->td_blocked = NULL;
673 td->td_lockname = NULL;
674 TD_CLR_LOCK(td);
675 MPASS(TD_CAN_RUN(td));
676 setrunqueue(td);
677 } else {
678 td->td_flags |= TDF_TSNOBLOCK;
679 MPASS(TD_IS_RUNNING(td));
680 }
681 }
682 mtx_unlock_spin(&sched_lock);
956}
957
958/*
683}
684
685/*
959 * Remove lock `m' from all_mtx queue. We don't allow MTX_QUIET to be
960 * passed in as a flag here because if the corresponding mtx_init() was
961 * called with MTX_QUIET set, then it will already be set in the mutex's
962 * flags.
686 * Return the first thread in a turnstile.
963 */
687 */
964void
965mtx_destroy(struct mtx *m)
688struct thread *
689turnstile_head(struct turnstile *ts)
966{
690{
691#ifdef INVARIANTS
692 struct turnstile_chain *tc;
967
693
968 LOCK_LOG_DESTROY(&m->mtx_object, 0);
969
970 if (!mtx_owned(m))
971 MPASS(mtx_unowned(m));
972 else {
973 MPASS((m->mtx_lock & (MTX_RECURSED|MTX_CONTESTED)) == 0);
974
975 /* Tell witness this isn't locked to make it happy. */
976 WITNESS_UNLOCK(&m->mtx_object, LOP_EXCLUSIVE, __FILE__,
977 __LINE__);
978 }
979
980 WITNESS_DESTROY(&m->mtx_object);
694 MPASS(ts != NULL);
695 tc = TC_LOOKUP(ts->ts_lockobj);
696 mtx_assert(&tc->tc_lock, MA_OWNED);
697#endif
698 return (TAILQ_FIRST(&ts->ts_blocked));
981}
982
983/*
699}
700
701/*
984 * Intialize the mutex code and system mutexes. This is called from the MD
985 * startup code prior to mi_startup(). The per-CPU data space needs to be
986 * setup before this is called.
702 * Returns true if a turnstile is empty.
987 */
703 */
988void
989mutex_init(void)
704int
705turnstile_empty(struct turnstile *ts)
990{
706{
707#ifdef INVARIANTS
708 struct turnstile_chain *tc;
991
709
992 /* Setup thread0 so that mutexes work. */
993 LIST_INIT(&thread0.td_contested);
994
995 /*
996 * Initialize mutexes.
997 */
998 mtx_init(&Giant, "Giant", NULL, MTX_DEF | MTX_RECURSE);
999 mtx_init(&sched_lock, "sched lock", NULL, MTX_SPIN | MTX_RECURSE);
1000 mtx_init(&proc0.p_mtx, "process lock", NULL, MTX_DEF | MTX_DUPOK);
1001 mtx_lock(&Giant);
710 MPASS(ts != NULL);
711 tc = TC_LOOKUP(ts->ts_lockobj);
712 mtx_assert(&tc->tc_lock, MA_OWNED);
713#endif
714 return (TAILQ_EMPTY(&ts->ts_blocked));
1002}
715}