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.29 2006/12/27 06:51:47 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 #ifdef SMP 131 132 /* 133 * Obtain all the tokens required by the specified thread on the current 134 * cpu, return 0 on failure and non-zero on success. 135 * 136 * NOTE: This code does not work with UP 'degenerate' spinlocks. SMP only. 137 * 138 * The preemption code will not allow a target thread holding spinlocks to 139 * preempt the current thread so we do not have to implement this for UP. 140 */ 141 int 142 lwkt_getalltokens(thread_t td) 143 { 144 lwkt_tokref_t refs; 145 lwkt_tokref_t undo; 146 lwkt_token_t tok; 147 148 for (refs = td->td_toks; refs; refs = refs->tr_next) { 149 KKASSERT(refs->tr_state == 0); 150 tok = refs->tr_tok; 151 if (tok->t_owner != td) { 152 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 153 /* 154 * Release the partial list of tokens obtained and return 155 * failure. 156 */ 157 for (undo = td->td_toks; undo != refs; undo = undo->tr_next) { 158 tok = undo->tr_tok; 159 undo->tr_state = 0; 160 if (--tok->t_count == 0) { 161 tok->t_owner = NULL; 162 spin_unlock_wr(&tok->t_spinlock); 163 } 164 } 165 return (FALSE); 166 } 167 tok->t_owner = td; 168 KKASSERT(tok->t_count == 0); 169 } 170 ++tok->t_count; 171 refs->tr_state = 1; 172 } 173 return (TRUE); 174 } 175 176 /* 177 * Release all tokens owned by the specified thread on the current cpu. 178 */ 179 void 180 lwkt_relalltokens(thread_t td) 181 { 182 lwkt_tokref_t scan; 183 lwkt_token_t tok; 184 185 for (scan = td->td_toks; scan; scan = scan->tr_next) { 186 if (scan->tr_state) { 187 scan->tr_state = 0; 188 tok = scan->tr_tok; 189 KKASSERT(tok->t_owner == td && tok->t_count > 0); 190 if (--tok->t_count == 0) { 191 tok->t_owner = NULL; 192 spin_unlock_wr(&tok->t_spinlock); 193 } 194 } 195 } 196 } 197 198 #endif 199 200 /* 201 * Acquire a serializing token. This routine can block. 202 * 203 * On SMP systems we track ownership and a per-owner counter. Tokens are 204 * released when a thread switches out and reacquired when a thread 205 * switches back in. On UP systems we track a global counter for debugging 206 * but otherwise the only issue we have is if a preempting thread wants a 207 * token that is being held by the preempted thread. 208 */ 209 static __inline 210 void 211 _lwkt_gettokref(lwkt_tokref_t ref) 212 { 213 #ifndef SMP 214 lwkt_tokref_t scan; 215 #endif 216 lwkt_token_t tok; 217 thread_t td; 218 219 KKASSERT(mycpu->gd_intr_nesting_level == 0); 220 td = curthread; 221 tok = ref->tr_tok; 222 223 /* 224 * Link the tokref to the thread's list 225 */ 226 ref->tr_next = td->td_toks; 227 cpu_ccfence(); 228 td->td_toks = ref; 229 230 #ifdef SMP 231 /* 232 * Gain ownership of the token's spinlock, SMP version. 233 */ 234 if (tok->t_owner != td) { 235 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 236 lwkt_yield(); 237 return; 238 } 239 KKASSERT(tok->t_owner == NULL && tok->t_count == 0); 240 tok->t_owner = td; 241 } 242 ++tok->t_count; 243 #else 244 /* 245 * Gain ownership of the token, UP version. All we have to do 246 * is check the token if we are preempting someone owning the 247 * same token. If we are, we yield the cpu back to the originator 248 * and we will get rescheduled as non-preemptive. 249 */ 250 while ((td = td->td_preempted) != NULL) { 251 for (scan = td->td_toks; scan; scan = scan->tr_next) { 252 if (scan->tr_tok == tok) { 253 lwkt_yield(); 254 return; 255 } 256 } 257 } 258 /* NOTE: 'td' invalid after loop */ 259 ++tok->t_globalcount; 260 #endif 261 ref->tr_state = 1; 262 } 263 264 static __inline 265 int 266 _lwkt_trytokref(lwkt_tokref_t ref) 267 { 268 #ifndef SMP 269 lwkt_tokref_t scan; 270 #endif 271 lwkt_token_t tok; 272 thread_t td; 273 274 KKASSERT(mycpu->gd_intr_nesting_level == 0); 275 td = curthread; 276 tok = ref->tr_tok; 277 278 /* 279 * Link the tokref to the thread's list 280 */ 281 ref->tr_next = td->td_toks; 282 cpu_ccfence(); 283 td->td_toks = ref; 284 285 #ifdef SMP 286 /* 287 * Gain ownership of the token's spinlock, SMP version. 288 */ 289 if (tok->t_owner != td) { 290 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 291 td->td_toks = ref->tr_next; 292 return (FALSE); 293 } 294 KKASSERT(tok->t_owner == NULL && tok->t_count == 0); 295 tok->t_owner = td; 296 } 297 ++tok->t_count; 298 #else 299 /* 300 * Gain ownership of the token, UP version. All we have to do 301 * is check the token if we are preempting someone owning the 302 * same token. If we are, we yield the cpu back to the originator 303 * and we will get rescheduled as non-preemptive. 304 */ 305 while ((td = td->td_preempted) != NULL) { 306 for (scan = td->td_toks; scan; scan = scan->tr_next) { 307 if (scan->tr_tok == tok) { 308 td->td_toks = ref->tr_next; 309 return (FALSE); 310 } 311 } 312 } 313 /* NOTE: 'td' invalid after loop */ 314 ++tok->t_globalcount; 315 #endif 316 ref->tr_state = 1; 317 return (TRUE); 318 } 319 320 void 321 lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok) 322 { 323 lwkt_tokref_init(ref, tok); 324 logtoken(get, ref); 325 _lwkt_gettokref(ref); 326 } 327 328 void 329 lwkt_gettokref(lwkt_tokref_t ref) 330 { 331 logtoken(get, ref); 332 _lwkt_gettokref(ref); 333 } 334 335 int 336 lwkt_trytoken(lwkt_tokref_t ref, lwkt_token_t tok) 337 { 338 lwkt_tokref_init(ref, tok); 339 logtoken(try, ref); 340 return(_lwkt_trytokref(ref)); 341 } 342 343 int 344 lwkt_trytokref(lwkt_tokref_t ref) 345 { 346 logtoken(try, ref); 347 return(_lwkt_trytokref(ref)); 348 } 349 350 /* 351 * Release a serializing token 352 */ 353 void 354 lwkt_reltoken(lwkt_tokref *ref) 355 { 356 struct lwkt_tokref **scanp; 357 lwkt_token_t tok; 358 thread_t td; 359 360 td = curthread; 361 tok = ref->tr_tok; 362 363 #ifdef SMP 364 KKASSERT(ref->tr_state == 1 && tok->t_owner == td && tok->t_count > 0); 365 #else 366 KKASSERT(ref->tr_state == 1 && tok->t_globalcount > 0); 367 #endif 368 369 for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next)) 370 ; 371 *scanp = ref->tr_next; 372 ref->tr_state = 0; 373 374 #ifdef SMP 375 if (--tok->t_count == 0) { 376 tok->t_owner = NULL; 377 spin_unlock_wr(&tok->t_spinlock); 378 } 379 #else 380 --tok->t_globalcount; 381 #endif 382 logtoken(release, ref); 383 } 384 385 /* 386 * Pool tokens are used to provide a type-stable serializing token 387 * pointer that does not race against disappearing data structures. 388 * 389 * This routine is called in early boot just after we setup the BSP's 390 * globaldata structure. 391 */ 392 void 393 lwkt_token_pool_init(void) 394 { 395 int i; 396 397 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 398 lwkt_token_init(&pool_tokens[i]); 399 } 400 401 lwkt_token_t 402 lwkt_token_pool_get(void *ptraddr) 403 { 404 int i; 405 406 i = ((int)(intptr_t)ptraddr >> 2) ^ ((int)(intptr_t)ptraddr >> 12); 407 return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]); 408 } 409 410 /* 411 * Initialize the owner and release-to cpu to the current cpu 412 * and reset the generation count. 413 */ 414 void 415 lwkt_token_init(lwkt_token_t tok) 416 { 417 #ifdef SMP 418 spin_init(&tok->t_spinlock); 419 tok->t_owner = NULL; 420 tok->t_count = 0; 421 #else 422 tok->t_globalcount = 0; 423 #endif 424 } 425 426 void 427 lwkt_token_uninit(lwkt_token_t tok) 428 { 429 /* empty */ 430 } 431