1 /* 2 * Copyright (c) 2003,2004 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 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 16 * distribution. 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. 20 * 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 32 * SUCH DAMAGE. 33 * 34 * $DragonFly: src/sys/kern/lwkt_token.c,v 1.30 2008/03/01 06:21:28 dillon Exp $ 35 */ 36 37 #ifdef _KERNEL 38 39 #include <sys/param.h> 40 #include <sys/systm.h> 41 #include <sys/kernel.h> 42 #include <sys/proc.h> 43 #include <sys/rtprio.h> 44 #include <sys/queue.h> 45 #include <sys/sysctl.h> 46 #include <sys/ktr.h> 47 #include <sys/kthread.h> 48 #include <machine/cpu.h> 49 #include <sys/lock.h> 50 #include <sys/caps.h> 51 #include <sys/spinlock.h> 52 53 #include <sys/thread2.h> 54 #include <sys/spinlock2.h> 55 56 #include <vm/vm.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> 65 66 #include <machine/stdarg.h> 67 #include <machine/smp.h> 68 69 #else 70 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> 80 #include <stdio.h> 81 #include <stdlib.h> 82 #include <string.h> 83 #include <machine/lock.h> 84 #include <machine/cpu.h> 85 86 #endif 87 88 #ifndef LWKT_NUM_POOL_TOKENS 89 #define LWKT_NUM_POOL_TOKENS 1024 /* power of 2 */ 90 #endif 91 #define LWKT_MASK_POOL_TOKENS (LWKT_NUM_POOL_TOKENS - 1) 92 93 #ifdef INVARIANTS 94 static int token_debug = 0; 95 #endif 96 97 static lwkt_token pool_tokens[LWKT_NUM_POOL_TOKENS]; 98 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 104 #endif 105 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); 110 #if 0 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); 117 #endif 118 119 #define logtoken(name, ref) \ 120 KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread) 121 122 #ifdef _KERNEL 123 124 #ifdef INVARIANTS 125 SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, ""); 126 #endif 127 128 #endif 129 130 /* 131 * Obtain all the tokens required by the specified thread on the current 132 * cpu, return 0 on failure and non-zero on success. 133 * 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). 138 * 139 * lwkt_getalltokens is called by the LWKT scheduler to acquire all 140 * tokens that the thread had aquired prior to going to sleep. 141 * 142 * Called from a critical section. 143 */ 144 int 145 lwkt_getalltokens(thread_t td) 146 { 147 lwkt_tokref_t refs; 148 #ifdef SMP 149 lwkt_tokref_t undo; 150 #endif 151 lwkt_token_t tok; 152 153 for (refs = td->td_toks; refs; refs = refs->tr_next) { 154 KKASSERT(refs->tr_state == 0); 155 tok = refs->tr_tok; 156 if (tok->t_owner != td) { 157 #ifdef SMP 158 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 159 /* 160 * Release the partial list of tokens obtained and return 161 * failure. 162 */ 163 for (undo = td->td_toks; undo != refs; undo = undo->tr_next) { 164 tok = undo->tr_tok; 165 undo->tr_state = 0; 166 if (--tok->t_count == 0) { 167 tok->t_owner = NULL; 168 spin_unlock_wr(&tok->t_spinlock); 169 } 170 } 171 return (FALSE); 172 } 173 #endif 174 KKASSERT(tok->t_owner == NULL && tok->t_count == 0); 175 tok->t_owner = td; 176 177 /* 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(). 184 */ 185 if (tok->t_lastowner != tok->t_owner) 186 tok->t_lastowner = NULL; 187 } 188 ++tok->t_count; 189 refs->tr_state = 1; 190 } 191 return (TRUE); 192 } 193 194 /* 195 * Release all tokens owned by the specified thread on the current cpu. 196 * 197 * Called from a critical section. 198 */ 199 void 200 lwkt_relalltokens(thread_t td) 201 { 202 lwkt_tokref_t refs; 203 lwkt_token_t tok; 204 205 for (refs = td->td_toks; refs; refs = refs->tr_next) { 206 if (refs->tr_state) { 207 refs->tr_state = 0; 208 tok = refs->tr_tok; 209 KKASSERT(tok->t_owner == td && tok->t_count > 0); 210 if (--tok->t_count == 0) { 211 tok->t_owner = NULL; 212 #ifdef SMP 213 spin_unlock_wr(&tok->t_spinlock); 214 #endif 215 } 216 } 217 } 218 } 219 220 /* 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. 224 * 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: 227 * 228 * td->td_toks = ref->tr_next; 229 */ 230 static __inline 231 int 232 _lwkt_trytokref2(lwkt_tokref_t ref, thread_t td) 233 { 234 #ifndef SMP 235 lwkt_tokref_t scan; 236 thread_t itd; 237 #endif 238 lwkt_token_t tok; 239 240 KKASSERT(mycpu->gd_intr_nesting_level == 0); 241 KKASSERT(ref->tr_state == 0); 242 tok = ref->tr_tok; 243 244 /* 245 * Link the tokref to the thread's list 246 */ 247 ref->tr_next = td->td_toks; 248 cpu_ccfence(); 249 250 /* 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). 255 */ 256 td->td_toks = ref; 257 258 if (tok->t_owner != td) { 259 #ifdef SMP 260 /* 261 * Gain ownership of the token's spinlock, SMP version. 262 */ 263 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 264 return (FALSE); 265 } 266 #else 267 /* 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. 271 */ 272 itd = td; 273 while ((itd = itd->td_preempted) != NULL) { 274 for (scan = itd->td_toks; scan; scan = scan->tr_next) { 275 if (scan->tr_tok == tok) { 276 return (FALSE); 277 } 278 } 279 } 280 #endif 281 KKASSERT(tok->t_owner == NULL && tok->t_count == 0); 282 tok->t_owner = td; 283 tok->t_lastowner = td; 284 } 285 ++tok->t_count; 286 ref->tr_state = 1; 287 288 return (TRUE); 289 } 290 291 static __inline 292 int 293 _lwkt_trytokref(lwkt_tokref_t ref) 294 { 295 thread_t td = curthread; 296 297 if (_lwkt_trytokref2(ref, td) == FALSE) { 298 /* 299 * Cleanup. Remove the token from the thread's list. 300 */ 301 td->td_toks = ref->tr_next; 302 return (FALSE); 303 } 304 305 return (TRUE); 306 } 307 308 /* 309 * Acquire a serializing token. This routine can block. 310 * 311 * We track ownership and a per-owner counter. Tokens are 312 * released when a thread switches out and reacquired when a thread 313 * switches back in. 314 */ 315 static __inline 316 void 317 _lwkt_gettokref(lwkt_tokref_t ref) 318 { 319 if (_lwkt_trytokref2(ref, curthread) == FALSE) { 320 /* 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. 326 */ 327 lwkt_yield(); 328 } 329 } 330 331 void 332 lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok) 333 { 334 lwkt_tokref_init(ref, tok); 335 logtoken(get, ref); 336 _lwkt_gettokref(ref); 337 } 338 339 void 340 lwkt_gettokref(lwkt_tokref_t ref) 341 { 342 logtoken(get, ref); 343 _lwkt_gettokref(ref); 344 } 345 346 int 347 lwkt_trytoken(lwkt_tokref_t ref, lwkt_token_t tok) 348 { 349 lwkt_tokref_init(ref, tok); 350 logtoken(try, ref); 351 return(_lwkt_trytokref(ref)); 352 } 353 354 int 355 lwkt_trytokref(lwkt_tokref_t ref) 356 { 357 logtoken(try, ref); 358 return(_lwkt_trytokref(ref)); 359 } 360 361 /* 362 * Release a serializing token 363 */ 364 void 365 lwkt_reltoken(lwkt_tokref_t ref) 366 { 367 struct lwkt_tokref **scanp; 368 lwkt_token_t tok; 369 thread_t td; 370 371 td = curthread; 372 tok = ref->tr_tok; 373 374 KKASSERT(tok->t_owner == td && ref->tr_state == 1 && tok->t_count > 0); 375 376 ref->tr_state = 0; 377 378 /* 379 * Fix-up the count now to avoid racing a preemption which may occur 380 * after the token has been removed from td_toks. 381 */ 382 if (--tok->t_count == 0) { 383 tok->t_owner = NULL; 384 tok->t_lastowner = NULL; 385 #ifdef SMP 386 spin_unlock_wr(&tok->t_spinlock); 387 #endif 388 } 389 390 /* 391 * Remove ref from thread's token list. 392 * 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! 398 * 399 * SMP: Do not modify token after spin_unlock_wr. 400 */ 401 for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next)) 402 ; 403 *scanp = ref->tr_next; 404 405 logtoken(release, ref); 406 } 407 408 /* 409 * Pool tokens are used to provide a type-stable serializing token 410 * pointer that does not race against disappearing data structures. 411 * 412 * This routine is called in early boot just after we setup the BSP's 413 * globaldata structure. 414 */ 415 void 416 lwkt_token_pool_init(void) 417 { 418 int i; 419 420 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 421 lwkt_token_init(&pool_tokens[i]); 422 } 423 424 lwkt_token_t 425 lwkt_token_pool_get(void *ptraddr) 426 { 427 int i; 428 429 i = ((int)(intptr_t)ptraddr >> 2) ^ ((int)(intptr_t)ptraddr >> 12); 430 return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]); 431 } 432 433 /* 434 * Initialize the owner and release-to cpu to the current cpu 435 * and reset the generation count. 436 */ 437 void 438 lwkt_token_init(lwkt_token_t tok) 439 { 440 #ifdef SMP 441 spin_init(&tok->t_spinlock); 442 #endif 443 tok->t_owner = NULL; 444 tok->t_lastowner = NULL; 445 tok->t_count = 0; 446 } 447 448 void 449 lwkt_token_uninit(lwkt_token_t tok) 450 { 451 /* empty */ 452 } 453 454 int 455 lwkt_token_is_stale(lwkt_tokref_t ref) 456 { 457 lwkt_token_t tok = ref->tr_tok; 458 459 KKASSERT(tok->t_owner == curthread && ref->tr_state == 1 && 460 tok->t_count > 0); 461 462 /* Token is not stale */ 463 if (tok->t_lastowner == tok->t_owner) 464 return (FALSE); 465 466 /* 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. 470 */ 471 tok->t_lastowner = tok->t_owner; 472 return (TRUE); 473 } 474