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