From 7eb611efb7f1dc00a875eb37cf518b3037531a38 Mon Sep 17 00:00:00 2001 From: Matthew Dillon Date: Sat, 1 Mar 2008 06:21:28 +0000 Subject: [PATCH] Clean up the token code and implement lwkt_token_is_stale(). Users of the token code are now able to detect if the token was acquired and released by someone else while they were blocked. Submitted-by: Michael Neumann --- sys/kern/lwkt_thread.c | 9 +- sys/kern/lwkt_token.c | 265 ++++++++++++++++++++++++++++--------------------- sys/sys/thread.h | 32 +++--- 3 files changed, 174 insertions(+), 132 deletions(-) diff --git a/sys/kern/lwkt_thread.c b/sys/kern/lwkt_thread.c index cf26a61b85..677a234673 100644 --- a/sys/kern/lwkt_thread.c +++ b/sys/kern/lwkt_thread.c @@ -31,7 +31,7 @@ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $DragonFly: src/sys/kern/lwkt_thread.c,v 1.111 2008/02/17 21:54:42 nant Exp $ + * $DragonFly: src/sys/kern/lwkt_thread.c,v 1.112 2008/03/01 06:21:28 dillon Exp $ */ /* @@ -524,10 +524,8 @@ lwkt_switch(void) td->td_release(td); crit_enter_gd(gd); -#ifdef SMP if (td->td_toks) lwkt_relalltokens(td); -#endif /* * We had better not be holding any spin locks, but don't get into an @@ -696,8 +694,11 @@ again: #else /* * THREAD SELECTION FOR A UP MACHINE BUILD. We don't have to - * worry about tokens or the BGL. + * worry about tokens or the BGL. However, we still have + * to call lwkt_getalltokens() in order to properly detect + * stale tokens. This call cannot fail for a UP build! */ + lwkt_getalltokens(ntd); ++gd->gd_cnt.v_swtch; TAILQ_REMOVE(&gd->gd_tdrunq[nq], ntd, td_threadq); TAILQ_INSERT_TAIL(&gd->gd_tdrunq[nq], ntd, td_threadq); diff --git a/sys/kern/lwkt_token.c b/sys/kern/lwkt_token.c index 2584c5edf5..a3548102b1 100644 --- a/sys/kern/lwkt_token.c +++ b/sys/kern/lwkt_token.c @@ -31,7 +31,7 @@ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $DragonFly: src/sys/kern/lwkt_token.c,v 1.29 2006/12/27 06:51:47 dillon Exp $ + * $DragonFly: src/sys/kern/lwkt_token.c,v 1.30 2008/03/01 06:21:28 dillon Exp $ */ #ifdef _KERNEL @@ -127,28 +127,34 @@ SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, ""); #endif -#ifdef SMP - /* * Obtain all the tokens required by the specified thread on the current * cpu, return 0 on failure and non-zero on success. * - * NOTE: This code does not work with UP 'degenerate' spinlocks. SMP only. - * * The preemption code will not allow a target thread holding spinlocks to * preempt the current thread so we do not have to implement this for UP. + * The only reason why we implement this for UP is that we want to detect + * stale tokens (lwkt_token_is_stale). + * + * lwkt_getalltokens is called by the LWKT scheduler to acquire all + * tokens that the thread had aquired prior to going to sleep. + * + * Called from a critical section. */ int lwkt_getalltokens(thread_t td) { lwkt_tokref_t refs; +#ifdef SMP lwkt_tokref_t undo; +#endif lwkt_token_t tok; for (refs = td->td_toks; refs; refs = refs->tr_next) { KKASSERT(refs->tr_state == 0); tok = refs->tr_tok; if (tok->t_owner != td) { +#ifdef SMP if (spin_trylock_wr(&tok->t_spinlock) == 0) { /* * Release the partial list of tokens obtained and return @@ -164,8 +170,20 @@ lwkt_getalltokens(thread_t td) } return (FALSE); } +#endif + KKASSERT(tok->t_owner == NULL && tok->t_count == 0); tok->t_owner = td; - KKASSERT(tok->t_count == 0); + + /* + * Detect the situation where the token was acquired by + * another thread while the token was released from the + * current thread due to a blocking condition. + * In this case we set t_lastowner to NULL to mark the + * token as stale from the point of view of BOTH threads. + * See lwkt_token_is_stale(). + */ + if (tok->t_lastowner != tok->t_owner) + tok->t_lastowner = NULL; } ++tok->t_count; refs->tr_state = 1; @@ -175,49 +193,52 @@ lwkt_getalltokens(thread_t td) /* * Release all tokens owned by the specified thread on the current cpu. + * + * Called from a critical section. */ void lwkt_relalltokens(thread_t td) { - lwkt_tokref_t scan; + lwkt_tokref_t refs; lwkt_token_t tok; - for (scan = td->td_toks; scan; scan = scan->tr_next) { - if (scan->tr_state) { - scan->tr_state = 0; - tok = scan->tr_tok; + for (refs = td->td_toks; refs; refs = refs->tr_next) { + if (refs->tr_state) { + refs->tr_state = 0; + tok = refs->tr_tok; KKASSERT(tok->t_owner == td && tok->t_count > 0); if (--tok->t_count == 0) { tok->t_owner = NULL; +#ifdef SMP spin_unlock_wr(&tok->t_spinlock); +#endif } } } } -#endif - /* - * Acquire a serializing token. This routine can block. + * Token acquisition helper function. Note that get/trytokenref do not + * reset t_lastowner if the token is already held. Only lwkt_token_is_stale() + * is allowed to do that. * - * On SMP systems we track ownership and a per-owner counter. Tokens are - * released when a thread switches out and reacquired when a thread - * switches back in. On UP systems we track a global counter for debugging - * but otherwise the only issue we have is if a preempting thread wants a - * token that is being held by the preempted thread. + * NOTE: On failure, this function doesn't remove the token from the + * thread's token list, so that you have to perform that yourself: + * + * td->td_toks = ref->tr_next; */ static __inline -void -_lwkt_gettokref(lwkt_tokref_t ref) +int +_lwkt_trytokref2(lwkt_tokref_t ref, thread_t td) { #ifndef SMP lwkt_tokref_t scan; + thread_t itd; #endif lwkt_token_t tok; - thread_t td; KKASSERT(mycpu->gd_intr_nesting_level == 0); - td = curthread; + KKASSERT(ref->tr_state == 0); tok = ref->tr_tok; /* @@ -225,98 +246,88 @@ _lwkt_gettokref(lwkt_tokref_t ref) */ ref->tr_next = td->td_toks; cpu_ccfence(); - td->td_toks = ref; -#ifdef SMP - /* - * Gain ownership of the token's spinlock, SMP version. + /* + * Once td_toks is set to a non NULL value, we can't preempt + * another thread anymore (the scheduler takes care that this + * won't happen). Additionally, we can't get preempted by + * another thread that wants to access the same token (tok). */ + td->td_toks = ref; + if (tok->t_owner != td) { +#ifdef SMP + /* + * Gain ownership of the token's spinlock, SMP version. + */ if (spin_trylock_wr(&tok->t_spinlock) == 0) { - lwkt_yield(); - return; + return (FALSE); } - KKASSERT(tok->t_owner == NULL && tok->t_count == 0); - tok->t_owner = td; - } - ++tok->t_count; #else - /* - * Gain ownership of the token, UP version. All we have to do - * is check the token if we are preempting someone owning the - * same token. If we are, we yield the cpu back to the originator - * and we will get rescheduled as non-preemptive. - */ - while ((td = td->td_preempted) != NULL) { - for (scan = td->td_toks; scan; scan = scan->tr_next) { - if (scan->tr_tok == tok) { - lwkt_yield(); - return; + /* + * Gain ownership of the token, UP version. All we have to do + * is check the token if we are preempting someone owning the + * same token, in which case we fail to acquire the token. + */ + itd = td; + while ((itd = itd->td_preempted) != NULL) { + for (scan = itd->td_toks; scan; scan = scan->tr_next) { + if (scan->tr_tok == tok) { + return (FALSE); + } } } - } - /* NOTE: 'td' invalid after loop */ - ++tok->t_globalcount; #endif + KKASSERT(tok->t_owner == NULL && tok->t_count == 0); + tok->t_owner = td; + tok->t_lastowner = td; + } + ++tok->t_count; ref->tr_state = 1; + + return (TRUE); } static __inline int _lwkt_trytokref(lwkt_tokref_t ref) { -#ifndef SMP - lwkt_tokref_t scan; -#endif - lwkt_token_t tok; - thread_t td; - - KKASSERT(mycpu->gd_intr_nesting_level == 0); - td = curthread; - tok = ref->tr_tok; - - /* - * Link the tokref to the thread's list - */ - ref->tr_next = td->td_toks; - cpu_ccfence(); - td->td_toks = ref; - -#ifdef SMP - /* - * Gain ownership of the token's spinlock, SMP version. - */ - if (tok->t_owner != td) { - if (spin_trylock_wr(&tok->t_spinlock) == 0) { - td->td_toks = ref->tr_next; - return (FALSE); - } - KKASSERT(tok->t_owner == NULL && tok->t_count == 0); - tok->t_owner = td; - } - ++tok->t_count; -#else - /* - * Gain ownership of the token, UP version. All we have to do - * is check the token if we are preempting someone owning the - * same token. If we are, we yield the cpu back to the originator - * and we will get rescheduled as non-preemptive. - */ - while ((td = td->td_preempted) != NULL) { - for (scan = td->td_toks; scan; scan = scan->tr_next) { - if (scan->tr_tok == tok) { - td->td_toks = ref->tr_next; - return (FALSE); - } - } + thread_t td = curthread; + + if (_lwkt_trytokref2(ref, td) == FALSE) { + /* + * Cleanup. Remove the token from the thread's list. + */ + td->td_toks = ref->tr_next; + return (FALSE); } - /* NOTE: 'td' invalid after loop */ - ++tok->t_globalcount; -#endif - ref->tr_state = 1; + return (TRUE); } +/* + * Acquire a serializing token. This routine can block. + * + * We track ownership and a per-owner counter. Tokens are + * released when a thread switches out and reacquired when a thread + * switches back in. + */ +static __inline +void +_lwkt_gettokref(lwkt_tokref_t ref) +{ + if (_lwkt_trytokref2(ref, curthread) == FALSE) { + /* + * Give up running if we can't acquire the token right now. But as we + * have linked in the tokref to the thread's list (_lwkt_trytokref2), + * the scheduler now takes care to acquire the token (by calling + * lwkt_getalltokens) before resuming execution. As such, when we + * return from lwkt_yield(), the token is acquired. + */ + lwkt_yield(); + } +} + void lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok) { @@ -351,7 +362,7 @@ lwkt_trytokref(lwkt_tokref_t ref) * Release a serializing token */ void -lwkt_reltoken(lwkt_tokref *ref) +lwkt_reltoken(lwkt_tokref_t ref) { struct lwkt_tokref **scanp; lwkt_token_t tok; @@ -360,25 +371,37 @@ lwkt_reltoken(lwkt_tokref *ref) td = curthread; tok = ref->tr_tok; -#ifdef SMP - KKASSERT(ref->tr_state == 1 && tok->t_owner == td && tok->t_count > 0); -#else - KKASSERT(ref->tr_state == 1 && tok->t_globalcount > 0); -#endif + KKASSERT(tok->t_owner == td && ref->tr_state == 1 && tok->t_count > 0); - for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next)) - ; - *scanp = ref->tr_next; ref->tr_state = 0; -#ifdef SMP + /* + * Fix-up the count now to avoid racing a preemption which may occur + * after the token has been removed from td_toks. + */ if (--tok->t_count == 0) { tok->t_owner = NULL; + tok->t_lastowner = NULL; +#ifdef SMP spin_unlock_wr(&tok->t_spinlock); - } -#else - --tok->t_globalcount; #endif + } + + /* + * Remove ref from thread's token list. + * + * After removing the token from the thread's list, it's unsafe + * on a UP machine to modify the token, because we might get + * preempted by another thread that wants to acquire the same token. + * This thread now thinks that it can acquire the token, because it's + * no longer in our thread's list. Bang! + * + * SMP: Do not modify token after spin_unlock_wr. + */ + for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next)) + ; + *scanp = ref->tr_next; + logtoken(release, ref); } @@ -416,11 +439,10 @@ lwkt_token_init(lwkt_token_t tok) { #ifdef SMP spin_init(&tok->t_spinlock); +#endif tok->t_owner = NULL; + tok->t_lastowner = NULL; tok->t_count = 0; -#else - tok->t_globalcount = 0; -#endif } void @@ -428,3 +450,24 @@ lwkt_token_uninit(lwkt_token_t tok) { /* empty */ } + +int +lwkt_token_is_stale(lwkt_tokref_t ref) +{ + lwkt_token_t tok = ref->tr_tok; + + KKASSERT(tok->t_owner == curthread && ref->tr_state == 1 && + tok->t_count > 0); + + /* Token is not stale */ + if (tok->t_lastowner == tok->t_owner) + return (FALSE); + + /* + * The token is stale. Reset to not stale so that the next call to + * lwkt_token_is_stale will return "not stale" unless the token + * was acquired in-between by another thread. + */ + tok->t_lastowner = tok->t_owner; + return (TRUE); +} diff --git a/sys/sys/thread.h b/sys/sys/thread.h index cfb8ef22e2..4272198b67 100644 --- a/sys/sys/thread.h +++ b/sys/sys/thread.h @@ -7,7 +7,7 @@ * Types which must already be defined when this header is included by * userland: struct md_thread * - * $DragonFly: src/sys/sys/thread.h,v 1.90 2007/12/12 23:49:24 dillon Exp $ + * $DragonFly: src/sys/sys/thread.h,v 1.91 2008/03/01 06:21:26 dillon Exp $ */ #ifndef _SYS_THREAD_H_ @@ -89,34 +89,31 @@ struct intrframe; * preemption. An interrupt which attempts to use the same token as the * thread being preempted will reschedule itself for non-preemptive * operation, so the new token code is capable of interlocking against - * interrupts as well as other cpus. + * interrupts as well as other cpus. This means that your token can only + * be (temporarily) lost if you *explicitly* block. * * Tokens are managed through a helper reference structure, lwkt_tokref, * which is typically declared on the caller's stack. Multiple tokref's * may reference the same token. * - * We do not actually have to track any information in the token itself - * on UP systems. Simply linking the reference into the thread's td_toks - * list is sufficient. We still track a global t_globalcount on UP for - * debugging purposes. + * It is possible to detect that your token was temporarily lost via + * lwkt_token_is_stale(), which uses the t_lastowner field. This field + * does NOT necessarily represent the current owner and can become stale + * (not point to a valid structure). It is used solely to detect + * whether the token was temporarily lost to another thread. The lost + * state is cleared by the function. */ -#ifdef SMP typedef struct lwkt_token { +#ifdef SMP struct spinlock t_spinlock; /* Controls access */ - struct thread *t_owner; /* The current owner of the token */ - int t_count; /* Per-thread count */ -} lwkt_token; - #else - -typedef struct lwkt_token { struct spinlock t_unused01; - struct thread *t_unused02; - int t_globalcount; /* Global reference count */ -} lwkt_token; - #endif + struct thread *t_owner; /* The current owner of the token */ + int t_count; /* Per-thread count */ + struct thread *t_lastowner; /* Last owner that acquired token */ +} lwkt_token; typedef struct lwkt_tokref { lwkt_token_t tr_tok; /* token in question */ @@ -361,6 +358,7 @@ extern void lwkt_relalltokens(thread_t); extern void lwkt_drain_token_requests(void); extern void lwkt_token_init(lwkt_token_t); extern void lwkt_token_uninit(lwkt_token_t); +extern int lwkt_token_is_stale(lwkt_tokref_t); extern void lwkt_token_pool_init(void); extern lwkt_token_t lwkt_token_pool_get(void *); -- 2.11.4.GIT