2 * Copyright (c) 2003,2004 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * $DragonFly: src/sys/kern/lwkt_token.c,v 1.30 2008/03/01 06:21:28 dillon Exp $
39 #include <sys/param.h>
40 #include <sys/systm.h>
41 #include <sys/kernel.h>
43 #include <sys/rtprio.h>
44 #include <sys/queue.h>
45 #include <sys/sysctl.h>
47 #include <sys/kthread.h>
48 #include <machine/cpu.h>
51 #include <sys/spinlock.h>
53 #include <sys/thread2.h>
54 #include <sys/spinlock2.h>
57 #include <vm/vm_param.h>
58 #include <vm/vm_kern.h>
59 #include <vm/vm_object.h>
60 #include <vm/vm_page.h>
61 #include <vm/vm_map.h>
62 #include <vm/vm_pager.h>
63 #include <vm/vm_extern.h>
64 #include <vm/vm_zone.h>
66 #include <machine/stdarg.h>
67 #include <machine/smp.h>
71 #include <sys/stdint.h>
72 #include <libcaps/thread.h>
73 #include <sys/thread.h>
74 #include <sys/msgport.h>
75 #include <sys/errno.h>
76 #include <libcaps/globaldata.h>
77 #include <machine/cpufunc.h>
78 #include <sys/thread2.h>
79 #include <sys/msgport2.h>
83 #include <machine/lock.h>
84 #include <machine/cpu.h>
88 #ifndef LWKT_NUM_POOL_TOKENS
89 #define LWKT_NUM_POOL_TOKENS 1024 /* power of 2 */
91 #define LWKT_MASK_POOL_TOKENS (LWKT_NUM_POOL_TOKENS - 1)
94 static int token_debug = 0;
97 static lwkt_token pool_tokens[LWKT_NUM_POOL_TOKENS];
99 #define TOKEN_STRING "REF=%p TOK=%p TD=%p"
100 #define CONTENDED_STRING "REF=%p TOK=%p TD=%p (contention started)"
101 #define UNCONTENDED_STRING "REF=%p TOK=%p TD=%p (contention stopped)"
102 #if !defined(KTR_TOKENS)
103 #define KTR_TOKENS KTR_ALL
106 KTR_INFO_MASTER(tokens);
107 KTR_INFO(KTR_TOKENS, tokens, try, 0, TOKEN_STRING, sizeof(void *) * 3);
108 KTR_INFO(KTR_TOKENS, tokens, get, 1, TOKEN_STRING, sizeof(void *) * 3);
109 KTR_INFO(KTR_TOKENS, tokens, release, 2, TOKEN_STRING, sizeof(void *) * 3);
111 KTR_INFO(KTR_TOKENS, tokens, remote, 3, TOKEN_STRING, sizeof(void *) * 3);
112 KTR_INFO(KTR_TOKENS, tokens, reqremote, 4, TOKEN_STRING, sizeof(void *) * 3);
113 KTR_INFO(KTR_TOKENS, tokens, reqfail, 5, TOKEN_STRING, sizeof(void *) * 3);
114 KTR_INFO(KTR_TOKENS, tokens, drain, 6, TOKEN_STRING, sizeof(void *) * 3);
115 KTR_INFO(KTR_TOKENS, tokens, contention_start, 7, CONTENDED_STRING, sizeof(void *) * 3);
116 KTR_INFO(KTR_TOKENS, tokens, contention_stop, 7, UNCONTENDED_STRING, sizeof(void *) * 3);
119 #define logtoken(name, ref) \
120 KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread)
125 SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, "");
131 * Obtain all the tokens required by the specified thread on the current
132 * cpu, return 0 on failure and non-zero on success.
134 * The preemption code will not allow a target thread holding spinlocks to
135 * preempt the current thread so we do not have to implement this for UP.
136 * The only reason why we implement this for UP is that we want to detect
137 * stale tokens (lwkt_token_is_stale).
139 * lwkt_getalltokens is called by the LWKT scheduler to acquire all
140 * tokens that the thread had aquired prior to going to sleep.
142 * Called from a critical section.
145 lwkt_getalltokens(thread_t td)
153 for (refs = td->td_toks; refs; refs = refs->tr_next) {
154 KKASSERT(refs->tr_state == 0);
156 if (tok->t_owner != td) {
158 if (spin_trylock_wr(&tok->t_spinlock) == 0) {
160 * Release the partial list of tokens obtained and return
163 for (undo = td->td_toks; undo != refs; undo = undo->tr_next) {
166 if (--tok->t_count == 0) {
168 spin_unlock_wr(&tok->t_spinlock);
174 KKASSERT(tok->t_owner == NULL && tok->t_count == 0);
178 * Detect the situation where the token was acquired by
179 * another thread while the token was released from the
180 * current thread due to a blocking condition.
181 * In this case we set t_lastowner to NULL to mark the
182 * token as stale from the point of view of BOTH threads.
183 * See lwkt_token_is_stale().
185 if (tok->t_lastowner != tok->t_owner)
186 tok->t_lastowner = NULL;
195 * Release all tokens owned by the specified thread on the current cpu.
197 * Called from a critical section.
200 lwkt_relalltokens(thread_t td)
205 for (refs = td->td_toks; refs; refs = refs->tr_next) {
206 if (refs->tr_state) {
209 KKASSERT(tok->t_owner == td && tok->t_count > 0);
210 if (--tok->t_count == 0) {
213 spin_unlock_wr(&tok->t_spinlock);
221 * Token acquisition helper function. Note that get/trytokenref do not
222 * reset t_lastowner if the token is already held. Only lwkt_token_is_stale()
223 * is allowed to do that.
225 * NOTE: On failure, this function doesn't remove the token from the
226 * thread's token list, so that you have to perform that yourself:
228 * td->td_toks = ref->tr_next;
232 _lwkt_trytokref2(lwkt_tokref_t ref, thread_t td)
240 KKASSERT(mycpu->gd_intr_nesting_level == 0);
241 KKASSERT(ref->tr_state == 0);
245 * Link the tokref to the thread's list
247 ref->tr_next = td->td_toks;
251 * Once td_toks is set to a non NULL value, we can't preempt
252 * another thread anymore (the scheduler takes care that this
253 * won't happen). Additionally, we can't get preempted by
254 * another thread that wants to access the same token (tok).
258 if (tok->t_owner != td) {
261 * Gain ownership of the token's spinlock, SMP version.
263 if (spin_trylock_wr(&tok->t_spinlock) == 0) {
268 * Gain ownership of the token, UP version. All we have to do
269 * is check the token if we are preempting someone owning the
270 * same token, in which case we fail to acquire the token.
273 while ((itd = itd->td_preempted) != NULL) {
274 for (scan = itd->td_toks; scan; scan = scan->tr_next) {
275 if (scan->tr_tok == tok) {
281 KKASSERT(tok->t_owner == NULL && tok->t_count == 0);
283 tok->t_lastowner = td;
293 _lwkt_trytokref(lwkt_tokref_t ref)
295 thread_t td = curthread;
297 if (_lwkt_trytokref2(ref, td) == FALSE) {
299 * Cleanup. Remove the token from the thread's list.
301 td->td_toks = ref->tr_next;
309 * Acquire a serializing token. This routine can block.
311 * We track ownership and a per-owner counter. Tokens are
312 * released when a thread switches out and reacquired when a thread
317 _lwkt_gettokref(lwkt_tokref_t ref)
319 if (_lwkt_trytokref2(ref, curthread) == FALSE) {
321 * Give up running if we can't acquire the token right now. But as we
322 * have linked in the tokref to the thread's list (_lwkt_trytokref2),
323 * the scheduler now takes care to acquire the token (by calling
324 * lwkt_getalltokens) before resuming execution. As such, when we
325 * return from lwkt_yield(), the token is acquired.
332 lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok)
334 lwkt_tokref_init(ref, tok);
336 _lwkt_gettokref(ref);
340 lwkt_gettokref(lwkt_tokref_t ref)
343 _lwkt_gettokref(ref);
347 lwkt_trytoken(lwkt_tokref_t ref, lwkt_token_t tok)
349 lwkt_tokref_init(ref, tok);
351 return(_lwkt_trytokref(ref));
355 lwkt_trytokref(lwkt_tokref_t ref)
358 return(_lwkt_trytokref(ref));
362 * Release a serializing token
365 lwkt_reltoken(lwkt_tokref_t ref)
367 struct lwkt_tokref **scanp;
374 KKASSERT(tok->t_owner == td && ref->tr_state == 1 && tok->t_count > 0);
379 * Fix-up the count now to avoid racing a preemption which may occur
380 * after the token has been removed from td_toks.
382 if (--tok->t_count == 0) {
384 tok->t_lastowner = NULL;
386 spin_unlock_wr(&tok->t_spinlock);
391 * Remove ref from thread's token list.
393 * After removing the token from the thread's list, it's unsafe
394 * on a UP machine to modify the token, because we might get
395 * preempted by another thread that wants to acquire the same token.
396 * This thread now thinks that it can acquire the token, because it's
397 * no longer in our thread's list. Bang!
399 * SMP: Do not modify token after spin_unlock_wr.
401 for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next))
403 *scanp = ref->tr_next;
405 logtoken(release, ref);
409 * Pool tokens are used to provide a type-stable serializing token
410 * pointer that does not race against disappearing data structures.
412 * This routine is called in early boot just after we setup the BSP's
413 * globaldata structure.
416 lwkt_token_pool_init(void)
420 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i)
421 lwkt_token_init(&pool_tokens[i]);
425 lwkt_token_pool_get(void *ptraddr)
429 i = ((int)(intptr_t)ptraddr >> 2) ^ ((int)(intptr_t)ptraddr >> 12);
430 return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]);
434 * Initialize the owner and release-to cpu to the current cpu
435 * and reset the generation count.
438 lwkt_token_init(lwkt_token_t tok)
441 spin_init(&tok->t_spinlock);
444 tok->t_lastowner = NULL;
449 lwkt_token_uninit(lwkt_token_t tok)
455 lwkt_token_is_stale(lwkt_tokref_t ref)
457 lwkt_token_t tok = ref->tr_tok;
459 KKASSERT(tok->t_owner == curthread && ref->tr_state == 1 &&
462 /* Token is not stale */
463 if (tok->t_lastowner == tok->t_owner)
467 * The token is stale. Reset to not stale so that the next call to
468 * lwkt_token_is_stale will return "not stale" unless the token
469 * was acquired in-between by another thread.
471 tok->t_lastowner = tok->t_owner;