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.27 2006/06/04 21:09:50 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/ipl.h> 68 #include <machine/smp.h> 69 70 #define THREAD_STACK (UPAGES * PAGE_SIZE) 71 72 #else 73 74 #include <sys/stdint.h> 75 #include <libcaps/thread.h> 76 #include <sys/thread.h> 77 #include <sys/msgport.h> 78 #include <sys/errno.h> 79 #include <libcaps/globaldata.h> 80 #include <machine/cpufunc.h> 81 #include <sys/thread2.h> 82 #include <sys/msgport2.h> 83 #include <stdio.h> 84 #include <stdlib.h> 85 #include <string.h> 86 #include <machine/lock.h> 87 #include <machine/cpu.h> 88 89 #endif 90 91 #ifndef LWKT_NUM_POOL_TOKENS 92 #define LWKT_NUM_POOL_TOKENS 1024 /* power of 2 */ 93 #endif 94 #define LWKT_MASK_POOL_TOKENS (LWKT_NUM_POOL_TOKENS - 1) 95 96 #ifdef INVARIANTS 97 static int token_debug = 0; 98 #endif 99 100 static lwkt_token pool_tokens[LWKT_NUM_POOL_TOKENS]; 101 102 #define TOKEN_STRING "REF=%p TOK=%p TD=%p" 103 #define CONTENDED_STRING "REF=%p TOK=%p TD=%p (contention started)" 104 #define UNCONTENDED_STRING "REF=%p TOK=%p TD=%p (contention stopped)" 105 #if !defined(KTR_TOKENS) 106 #define KTR_TOKENS KTR_ALL 107 #endif 108 109 KTR_INFO_MASTER(tokens); 110 KTR_INFO(KTR_TOKENS, tokens, try, 0, TOKEN_STRING, sizeof(void *) * 3); 111 KTR_INFO(KTR_TOKENS, tokens, get, 1, TOKEN_STRING, sizeof(void *) * 3); 112 KTR_INFO(KTR_TOKENS, tokens, release, 2, TOKEN_STRING, sizeof(void *) * 3); 113 #if 0 114 KTR_INFO(KTR_TOKENS, tokens, remote, 3, TOKEN_STRING, sizeof(void *) * 3); 115 KTR_INFO(KTR_TOKENS, tokens, reqremote, 4, TOKEN_STRING, sizeof(void *) * 3); 116 KTR_INFO(KTR_TOKENS, tokens, reqfail, 5, TOKEN_STRING, sizeof(void *) * 3); 117 KTR_INFO(KTR_TOKENS, tokens, drain, 6, TOKEN_STRING, sizeof(void *) * 3); 118 KTR_INFO(KTR_TOKENS, tokens, contention_start, 7, CONTENDED_STRING, sizeof(void *) * 3); 119 KTR_INFO(KTR_TOKENS, tokens, contention_stop, 7, UNCONTENDED_STRING, sizeof(void *) * 3); 120 #endif 121 122 #define logtoken(name, ref) \ 123 KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread) 124 125 #ifdef _KERNEL 126 127 #ifdef INVARIANTS 128 SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, ""); 129 #endif 130 131 #endif 132 133 #ifdef SMP 134 135 /* 136 * Obtain all the tokens required by the specified thread on the current 137 * cpu, return 0 on failure and non-zero on success. 138 * 139 * NOTE: This code does not work with UP 'degenerate' spinlocks. SMP only. 140 * 141 * The preemption code will not allow a target thread holding spinlocks to 142 * preempt the current thread so we do not have to implement this for UP. 143 */ 144 int 145 lwkt_getalltokens(thread_t td) 146 { 147 lwkt_tokref_t refs; 148 lwkt_tokref_t undo; 149 lwkt_token_t tok; 150 151 for (refs = td->td_toks; refs; refs = refs->tr_next) { 152 KKASSERT(refs->tr_state == 0); 153 tok = refs->tr_tok; 154 if (tok->t_owner != td) { 155 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 156 /* 157 * Release the partial list of tokens obtained and return 158 * failure. 159 */ 160 for (undo = td->td_toks; undo != refs; undo = undo->tr_next) { 161 tok = undo->tr_tok; 162 undo->tr_state = 0; 163 if (--tok->t_count == 0) { 164 tok->t_owner = NULL; 165 spin_unlock_wr(&tok->t_spinlock); 166 } 167 } 168 return (FALSE); 169 } 170 tok->t_owner = td; 171 KKASSERT(tok->t_count == 0); 172 } 173 ++tok->t_count; 174 refs->tr_state = 1; 175 } 176 return (TRUE); 177 } 178 179 /* 180 * Release all tokens owned by the specified thread on the current cpu. 181 */ 182 void 183 lwkt_relalltokens(thread_t td) 184 { 185 lwkt_tokref_t scan; 186 lwkt_token_t tok; 187 188 for (scan = td->td_toks; scan; scan = scan->tr_next) { 189 if (scan->tr_state) { 190 scan->tr_state = 0; 191 tok = scan->tr_tok; 192 KKASSERT(tok->t_owner == td && tok->t_count > 0); 193 if (--tok->t_count == 0) { 194 tok->t_owner = NULL; 195 spin_unlock_wr(&tok->t_spinlock); 196 } 197 } 198 } 199 } 200 201 #endif 202 203 /* 204 * Acquire a serializing token. This routine can block. 205 * 206 * On SMP systems we track ownership and a per-owner counter. Tokens are 207 * released when a thread switches out and reacquired when a thread 208 * switches back in. On UP systems we track a global counter for debugging 209 * but otherwise the only issue we have is if a preempting thread wants a 210 * token that is being held by the preempted thread. 211 */ 212 static __inline 213 void 214 _lwkt_gettokref(lwkt_tokref_t ref) 215 { 216 #ifndef SMP 217 lwkt_tokref_t scan; 218 #endif 219 lwkt_token_t tok; 220 thread_t td; 221 222 KKASSERT(mycpu->gd_intr_nesting_level == 0); 223 td = curthread; 224 tok = ref->tr_tok; 225 226 /* 227 * Link the tokref to the thread's list 228 */ 229 ref->tr_next = td->td_toks; 230 cpu_ccfence(); 231 td->td_toks = ref; 232 233 #ifdef SMP 234 /* 235 * Gain ownership of the token's spinlock, SMP version. 236 */ 237 if (tok->t_owner != td) { 238 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 239 lwkt_yield(); 240 return; 241 } 242 KKASSERT(tok->t_owner == NULL && tok->t_count == 0); 243 tok->t_owner = td; 244 } 245 ++tok->t_count; 246 #else 247 /* 248 * Gain ownership of the token, UP version. All we have to do 249 * is check the token if we are preempting someone owning the 250 * same token. If we are, we yield the cpu back to the originator 251 * and we will get rescheduled as non-preemptive. 252 */ 253 while ((td = td->td_preempted) != NULL) { 254 for (scan = td->td_toks; scan; scan = scan->tr_next) { 255 if (scan->tr_tok == tok) { 256 lwkt_yield(); 257 return; 258 } 259 } 260 } 261 /* NOTE: 'td' invalid after loop */ 262 ++tok->t_globalcount; 263 #endif 264 ref->tr_state = 1; 265 } 266 267 static __inline 268 int 269 _lwkt_trytokref(lwkt_tokref_t ref) 270 { 271 #ifndef SMP 272 lwkt_tokref_t scan; 273 #endif 274 lwkt_token_t tok; 275 thread_t td; 276 277 KKASSERT(mycpu->gd_intr_nesting_level == 0); 278 td = curthread; 279 tok = ref->tr_tok; 280 281 /* 282 * Link the tokref to the thread's list 283 */ 284 ref->tr_next = td->td_toks; 285 cpu_ccfence(); 286 td->td_toks = ref; 287 288 #ifdef SMP 289 /* 290 * Gain ownership of the token's spinlock, SMP version. 291 */ 292 if (tok->t_owner != td) { 293 if (spin_trylock_wr(&tok->t_spinlock) == 0) { 294 td->td_toks = ref->tr_next; 295 return (FALSE); 296 } 297 KKASSERT(tok->t_owner == NULL && tok->t_count == 0); 298 tok->t_owner = td; 299 } 300 ++tok->t_count; 301 #else 302 /* 303 * Gain ownership of the token, UP version. All we have to do 304 * is check the token if we are preempting someone owning the 305 * same token. If we are, we yield the cpu back to the originator 306 * and we will get rescheduled as non-preemptive. 307 */ 308 while ((td = td->td_preempted) != NULL) { 309 for (scan = td->td_toks; scan; scan = scan->tr_next) { 310 if (scan->tr_tok == tok) { 311 td->td_toks = ref->tr_next; 312 return (FALSE); 313 } 314 } 315 } 316 /* NOTE: 'td' invalid after loop */ 317 ++tok->t_globalcount; 318 #endif 319 ref->tr_state = 1; 320 return (TRUE); 321 } 322 323 void 324 lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok) 325 { 326 lwkt_tokref_init(ref, tok); 327 logtoken(get, ref); 328 _lwkt_gettokref(ref); 329 } 330 331 void 332 lwkt_gettokref(lwkt_tokref_t ref) 333 { 334 logtoken(get, ref); 335 _lwkt_gettokref(ref); 336 } 337 338 int 339 lwkt_trytoken(lwkt_tokref_t ref, lwkt_token_t tok) 340 { 341 lwkt_tokref_init(ref, tok); 342 logtoken(try, ref); 343 return(_lwkt_trytokref(ref)); 344 } 345 346 int 347 lwkt_trytokref(lwkt_tokref_t ref) 348 { 349 logtoken(try, ref); 350 return(_lwkt_trytokref(ref)); 351 } 352 353 /* 354 * Release a serializing token 355 */ 356 void 357 lwkt_reltoken(lwkt_tokref *ref) 358 { 359 struct lwkt_tokref **scanp; 360 lwkt_token_t tok; 361 thread_t td; 362 363 td = curthread; 364 tok = ref->tr_tok; 365 366 #ifdef SMP 367 KKASSERT(ref->tr_state == 1 && tok->t_owner == td && tok->t_count > 0); 368 #else 369 KKASSERT(ref->tr_state == 1 && tok->t_globalcount > 0); 370 #endif 371 372 for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next)) 373 ; 374 *scanp = ref->tr_next; 375 ref->tr_state = 0; 376 377 #ifdef SMP 378 if (--tok->t_count == 0) { 379 tok->t_owner = NULL; 380 spin_unlock_wr(&tok->t_spinlock); 381 } 382 #else 383 --tok->t_globalcount; 384 #endif 385 logtoken(release, ref); 386 } 387 388 /* 389 * Pool tokens are used to provide a type-stable serializing token 390 * pointer that does not race against disappearing data structures. 391 * 392 * This routine is called in early boot just after we setup the BSP's 393 * globaldata structure. 394 */ 395 void 396 lwkt_token_pool_init(void) 397 { 398 int i; 399 400 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 401 lwkt_token_init(&pool_tokens[i]); 402 } 403 404 lwkt_token_t 405 lwkt_token_pool_get(void *ptraddr) 406 { 407 int i; 408 409 i = ((int)(intptr_t)ptraddr >> 2) ^ ((int)(intptr_t)ptraddr >> 12); 410 return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]); 411 } 412 413 /* 414 * Initialize the owner and release-to cpu to the current cpu 415 * and reset the generation count. 416 */ 417 void 418 lwkt_token_init(lwkt_token_t tok) 419 { 420 #ifdef SMP 421 spin_init(&tok->t_spinlock); 422 tok->t_owner = NULL; 423 tok->t_count = 0; 424 #else 425 tok->t_globalcount = 0; 426 #endif 427 } 428 429 void 430 lwkt_token_uninit(lwkt_token_t tok) 431 { 432 /* empty */ 433 } 434