1 /* 2 * Copyright (c) 2003,2004,2009 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 35 /* 36 * lwkt_token - Implement soft token locks. 37 * 38 * Tokens are locks which serialize a thread only while the thread is 39 * running. If the thread blocks all tokens are released, then reacquired 40 * when the thread resumes. 41 * 42 * This implementation requires no critical sections or spin locks, but 43 * does use atomic_cmpset_ptr(). 44 * 45 * Tokens may be recursively acquired by the same thread. However the 46 * caller must be sure to release such tokens in reverse order. 47 */ 48 #include <sys/param.h> 49 #include <sys/systm.h> 50 #include <sys/kernel.h> 51 #include <sys/proc.h> 52 #include <sys/rtprio.h> 53 #include <sys/queue.h> 54 #include <sys/sysctl.h> 55 #include <sys/ktr.h> 56 #include <sys/kthread.h> 57 #include <machine/cpu.h> 58 #include <sys/lock.h> 59 #include <sys/caps.h> 60 #include <sys/spinlock.h> 61 62 #include <sys/thread2.h> 63 #include <sys/spinlock2.h> 64 65 #include <vm/vm.h> 66 #include <vm/vm_param.h> 67 #include <vm/vm_kern.h> 68 #include <vm/vm_object.h> 69 #include <vm/vm_page.h> 70 #include <vm/vm_map.h> 71 #include <vm/vm_pager.h> 72 #include <vm/vm_extern.h> 73 #include <vm/vm_zone.h> 74 75 #include <machine/stdarg.h> 76 #include <machine/smp.h> 77 78 #ifndef LWKT_NUM_POOL_TOKENS 79 #define LWKT_NUM_POOL_TOKENS 1024 /* power of 2 */ 80 #endif 81 #define LWKT_MASK_POOL_TOKENS (LWKT_NUM_POOL_TOKENS - 1) 82 83 #ifdef INVARIANTS 84 static int token_debug = 0; 85 #endif 86 87 static lwkt_token pool_tokens[LWKT_NUM_POOL_TOKENS]; 88 89 #define TOKEN_STRING "REF=%p TOK=%p TD=%p" 90 #define CONTENDED_STRING "REF=%p TOK=%p TD=%p (contention started)" 91 #define UNCONTENDED_STRING "REF=%p TOK=%p TD=%p (contention stopped)" 92 #if !defined(KTR_TOKENS) 93 #define KTR_TOKENS KTR_ALL 94 #endif 95 96 KTR_INFO_MASTER(tokens); 97 KTR_INFO(KTR_TOKENS, tokens, fail, 0, TOKEN_STRING, sizeof(void *) * 3); 98 KTR_INFO(KTR_TOKENS, tokens, succ, 1, TOKEN_STRING, sizeof(void *) * 3); 99 #if 0 100 KTR_INFO(KTR_TOKENS, tokens, release, 2, TOKEN_STRING, sizeof(void *) * 3); 101 KTR_INFO(KTR_TOKENS, tokens, remote, 3, TOKEN_STRING, sizeof(void *) * 3); 102 KTR_INFO(KTR_TOKENS, tokens, reqremote, 4, TOKEN_STRING, sizeof(void *) * 3); 103 KTR_INFO(KTR_TOKENS, tokens, reqfail, 5, TOKEN_STRING, sizeof(void *) * 3); 104 KTR_INFO(KTR_TOKENS, tokens, drain, 6, TOKEN_STRING, sizeof(void *) * 3); 105 KTR_INFO(KTR_TOKENS, tokens, contention_start, 7, CONTENDED_STRING, sizeof(void *) * 3); 106 KTR_INFO(KTR_TOKENS, tokens, contention_stop, 7, UNCONTENDED_STRING, sizeof(void *) * 3); 107 #endif 108 109 #define logtoken(name, ref) \ 110 KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread) 111 112 #ifdef INVARIANTS 113 SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, ""); 114 #endif 115 116 /* 117 * Return a pool token given an address 118 */ 119 static __inline 120 lwkt_token_t 121 _lwkt_token_pool_lookup(void *ptr) 122 { 123 int i; 124 125 i = ((int)(intptr_t)ptr >> 2) ^ ((int)(intptr_t)ptr >> 12); 126 return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]); 127 } 128 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. If a failure occurs 133 * any partially acquired tokens will be released prior to return. 134 * 135 * lwkt_getalltokens is called by the LWKT scheduler to acquire all 136 * tokens that the thread had acquired prior to going to sleep. 137 * 138 * Called from a critical section. 139 */ 140 int 141 lwkt_getalltokens(thread_t td) 142 { 143 lwkt_tokref_t scan1; 144 lwkt_tokref_t scan2; 145 lwkt_tokref_t ref; 146 lwkt_token_t tok; 147 148 for (scan1 = td->td_toks; scan1; scan1 = scan1->tr_next) { 149 tok = scan1->tr_tok; 150 for (;;) { 151 /* 152 * Try to acquire the token if we do not already have 153 * it. 154 * 155 * NOTE: If atomic_cmpset_ptr() fails we have to 156 * loop and try again. It just means we 157 * lost a cpu race. 158 */ 159 ref = tok->t_ref; 160 if (ref == scan1) 161 break; 162 if (ref == NULL) { 163 if (atomic_cmpset_ptr(&tok->t_ref, NULL, scan1)) 164 break; 165 continue; 166 } 167 168 /* 169 * If acquisition fails the token might be held 170 * recursively by another ref owned by the same 171 * thread. 172 * 173 * NOTE! We cannot just dereference 'ref' to test 174 * the tr_owner as its storage will be 175 * unstable if it belongs to another thread. 176 * 177 * NOTE! Since tokens are inserted at the head 178 * of the list we must migrate such tokens 179 * so the actual lock is not cleared until 180 * the last release. 181 */ 182 scan2 = td->td_toks; 183 for (;;) { 184 if (scan2 == scan1) { 185 lwkt_relalltokens(td); 186 return(FALSE); 187 } 188 if (scan2 == ref) { 189 tok->t_ref = scan1; 190 break; 191 } 192 scan2 = scan2->tr_next; 193 } 194 break; 195 } 196 } 197 return (TRUE); 198 } 199 200 /* 201 * Release all tokens owned by the specified thread on the current cpu. 202 * 203 * This code is really simple. Even in cases where we own all the tokens 204 * note that t_ref may not match the scan for recursively held tokens, 205 * or for the case where a lwkt_getalltokens() failed. 206 * 207 * Called from a critical section. 208 */ 209 void 210 lwkt_relalltokens(thread_t td) 211 { 212 lwkt_tokref_t scan1; 213 lwkt_token_t tok; 214 215 for (scan1 = td->td_toks; scan1; scan1 = scan1->tr_next) { 216 tok = scan1->tr_tok; 217 if (tok->t_ref == scan1) 218 tok->t_ref = NULL; 219 } 220 } 221 222 /* 223 * Token acquisition helper function. Note that get/trytokenref do not 224 * reset t_lastowner if the token is already held. Only lwkt_token_is_stale() 225 * is allowed to do that. 226 * 227 * NOTE: On failure, this function doesn't remove the token from the 228 * thread's token list, so that you have to perform that yourself: 229 * 230 * td->td_toks = ref->tr_next; 231 */ 232 static __inline 233 int 234 _lwkt_trytokref2(lwkt_tokref_t nref, thread_t td) 235 { 236 lwkt_tokref_t ref; 237 lwkt_tokref_t scan2; 238 lwkt_token_t tok; 239 240 KKASSERT(td->td_gd->gd_intr_nesting_level == 0); 241 242 /* 243 * Link the tokref into curthread's list. Make sure the 244 * cpu does not reorder these instructions! 245 */ 246 nref->tr_next = td->td_toks; 247 cpu_ccfence(); 248 td->td_toks = nref; 249 cpu_ccfence(); 250 251 /* 252 * Attempt to gain ownership 253 */ 254 tok = nref->tr_tok; 255 for (;;) { 256 /* 257 * Try to acquire the token if we do not already have 258 * it. 259 */ 260 ref = tok->t_ref; 261 if (ref == nref) 262 return (TRUE); 263 if (ref == NULL) { 264 /* 265 * NOTE: If atomic_cmpset_ptr() fails we have to 266 * loop and try again. It just means we 267 * lost a cpu race. 268 */ 269 if (atomic_cmpset_ptr(&tok->t_ref, NULL, nref)) 270 return (TRUE); 271 continue; 272 } 273 274 /* 275 * If acquisition fails the token might be held 276 * recursively by another ref owned by the same 277 * thread. 278 * 279 * NOTE! We cannot just dereference 'ref' to test 280 * the tr_owner as its storage will be 281 * unstable if it belongs to another thread. 282 * 283 * NOTE! We do not migrate t_ref to nref here as we 284 * want the recursion unwinding in reverse order 285 * to NOT release the token until last the 286 * recursive ref is released. 287 */ 288 for (scan2 = nref->tr_next; scan2; scan2 = scan2->tr_next) { 289 if (scan2 == ref) 290 return(TRUE); 291 } 292 return(FALSE); 293 } 294 } 295 296 /* 297 * Acquire a serializing token. This routine does not block. 298 */ 299 static __inline 300 int 301 _lwkt_trytokref(lwkt_tokref_t ref, thread_t td) 302 { 303 if (_lwkt_trytokref2(ref, td) == FALSE) { 304 /* 305 * Cleanup. Remove the token from the thread's list. 306 */ 307 td->td_toks = ref->tr_next; 308 return (FALSE); 309 } 310 return (TRUE); 311 } 312 313 /* 314 * Acquire a serializing token. This routine can block. 315 */ 316 static __inline 317 void 318 _lwkt_gettokref(lwkt_tokref_t ref, thread_t td) 319 { 320 if (_lwkt_trytokref2(ref, td) == FALSE) { 321 /* 322 * Give up running if we can't acquire the token right now. 323 * But as we have linked in the tokref to the thread's list 324 * (_lwkt_trytokref2), the scheduler now takes care to acquire 325 * the token (by calling lwkt_getalltokens) before resuming 326 * execution. As such, when we return from lwkt_yield(), 327 * the token is acquired. 328 * 329 * Since we failed this is not a recursive token so upon 330 * return tr_tok->t_ref should be assigned to this specific 331 * ref. 332 */ 333 logtoken(fail, ref); 334 lwkt_yield(); 335 logtoken(succ, ref); 336 #if 0 337 if (ref->tr_tok->t_ref != ref) { 338 lwkt_tokref_t scan; 339 kprintf("gettokref %p failed, held by tok %p ref %p\n", 340 ref, ref->tr_tok, ref->tr_tok->t_ref); 341 for (scan = td->td_toks; scan; scan = scan->tr_next) { 342 kprintf(" %p\n", scan); 343 } 344 } 345 #endif 346 KKASSERT(ref->tr_tok->t_ref == ref); 347 } 348 } 349 350 void 351 lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok) 352 { 353 thread_t td = curthread; 354 355 lwkt_tokref_init(ref, tok, td); 356 _lwkt_gettokref(ref, td); 357 } 358 359 void 360 lwkt_getpooltoken(lwkt_tokref_t ref, void *ptr) 361 { 362 thread_t td = curthread; 363 364 lwkt_tokref_init(ref, _lwkt_token_pool_lookup(ptr), td); 365 _lwkt_gettokref(ref, td); 366 } 367 368 void 369 lwkt_gettokref(lwkt_tokref_t ref) 370 { 371 _lwkt_gettokref(ref, ref->tr_owner); 372 } 373 374 int 375 lwkt_trytoken(lwkt_tokref_t ref, lwkt_token_t tok) 376 { 377 thread_t td = curthread; 378 379 lwkt_tokref_init(ref, tok, td); 380 return(_lwkt_trytokref(ref, td)); 381 } 382 383 int 384 lwkt_trytokref(lwkt_tokref_t ref) 385 { 386 return(_lwkt_trytokref(ref, ref->tr_owner)); 387 } 388 389 /* 390 * Release a serializing token. 391 * 392 * WARNING! Any recursive tokens must be released in reverse order. 393 */ 394 void 395 lwkt_reltoken(lwkt_tokref_t ref) 396 { 397 struct lwkt_tokref **scanp; 398 lwkt_token_t tok; 399 thread_t td; 400 401 tok = ref->tr_tok; 402 403 /* 404 * Remove the ref from the thread's token list. 405 * 406 * NOTE: td == curthread 407 */ 408 td = ref->tr_owner; 409 for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next)) 410 ; 411 *scanp = ref->tr_next; 412 cpu_ccfence(); 413 414 /* 415 * Only clear the token if it matches ref. If ref was a recursively 416 * acquired token it may not match. 417 */ 418 if (tok->t_ref == ref) 419 tok->t_ref = NULL; 420 } 421 422 /* 423 * Pool tokens are used to provide a type-stable serializing token 424 * pointer that does not race against disappearing data structures. 425 * 426 * This routine is called in early boot just after we setup the BSP's 427 * globaldata structure. 428 */ 429 void 430 lwkt_token_pool_init(void) 431 { 432 int i; 433 434 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 435 lwkt_token_init(&pool_tokens[i]); 436 } 437 438 lwkt_token_t 439 lwkt_token_pool_lookup(void *ptr) 440 { 441 return (_lwkt_token_pool_lookup(ptr)); 442 } 443 444 /* 445 * Initialize the owner and release-to cpu to the current cpu 446 * and reset the generation count. 447 */ 448 void 449 lwkt_token_init(lwkt_token_t tok) 450 { 451 tok->t_ref = NULL; 452 } 453 454 void 455 lwkt_token_uninit(lwkt_token_t tok) 456 { 457 /* empty */ 458 } 459 460 #if 0 461 int 462 lwkt_token_is_stale(lwkt_tokref_t ref) 463 { 464 lwkt_token_t tok = ref->tr_tok; 465 466 KKASSERT(tok->t_owner == curthread && ref->tr_state == 1 && 467 tok->t_count > 0); 468 469 /* Token is not stale */ 470 if (tok->t_lastowner == tok->t_owner) 471 return (FALSE); 472 473 /* 474 * The token is stale. Reset to not stale so that the next call to 475 * lwkt_token_is_stale will return "not stale" unless the token 476 * was acquired in-between by another thread. 477 */ 478 tok->t_lastowner = tok->t_owner; 479 return (TRUE); 480 } 481 #endif 482