|
|
1.1 ! root 1: /* ! 2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. ! 3: * ! 4: * @APPLE_LICENSE_HEADER_START@ ! 5: * ! 6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights ! 7: * Reserved. This file contains Original Code and/or Modifications of ! 8: * Original Code as defined in and that are subject to the Apple Public ! 9: * Source License Version 1.1 (the "License"). You may not use this file ! 10: * except in compliance with the License. Please obtain a copy of the ! 11: * License at http://www.apple.com/publicsource and read it before using ! 12: * this file. ! 13: * ! 14: * The Original Code and all software distributed under the License are ! 15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER ! 16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, ! 17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, ! 18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the ! 19: * License for the specific language governing rights and limitations ! 20: * under the License. ! 21: * ! 22: * @APPLE_LICENSE_HEADER_END@ ! 23: */ ! 24: ! 25: /* ! 26: * Copyright (c) 1990 NeXT, Inc. ! 27: * ! 28: * History: ! 29: * ! 30: * 18-Jul-90: Brian Pinkerton at NeXT ! 31: * created ! 32: */ ! 33: ! 34: /* ! 35: * Kernel stack module: handle the allocation, swapping (unwiring) and ! 36: * freeing of thread kernel stacks. Kernel stacks are allocated from whole ! 37: * pages. They may only cross page boundaries if they are bigger than a page. ! 38: * The constant KERNEL_STACK_SIZE (kernel_stack.h) defines the actual size of ! 39: * kernel stacks. ! 40: * ! 41: * The address of a kernel stack given to a client differs from the actual ! 42: * address of the stack. Internally, we prepend a struct _kernelStack to ! 43: * every stack we return to the user. This structure allows us to queue the ! 44: * stacks, and maintain information about the status of the stack. ! 45: * ! 46: * Access to the stack structures is protected by a single lock. We need ! 47: * a sleep lock because certain functions we call can block (for example, ! 48: * vm_map_pageable). Ultimately, this module should use finer granularity ! 49: * locks -- one on the chunk of stacks, one on an individual stack, and an ! 50: * infrequently used one on the entire system. ! 51: * ! 52: * Exported routines: ! 53: * ! 54: * void initKernelStacks() initializes this module ! 55: * vm_offset_t allocStack() allocate a new kernel stack ! 56: * void freeStack(vm_offset_t stack) free a previously alloc'ed kernel stack ! 57: * void swapOutStack(vm_offset_t stack) try to swap out a stack ! 58: * void swapInStack(vm_offset_t stack) swap in a stack ! 59: * ! 60: * Internal routines: ! 61: * ! 62: * vm_offset_t newStack(): allocate new stacks from new memory ! 63: * void enterFreeList(vm_offset_t stack) put a stack on the free list ! 64: * void checkFreeList(vm_offset_t stack) try to free (or swap) an entire page ! 65: * int canSwap(vm_offset_t stack) return TRUE if we can swap this stack ! 66: * void doSwapout(vm_offset_t stack) really swap out this stack ! 67: */ ! 68: ! 69: #import <mach_debug.h> ! 70: ! 71: #import <kern/queue.h> ! 72: #import <kern/thread.h> ! 73: #import <kern/kernel_stack.h> ! 74: #import <kern/sched_prim.h> ! 75: #import <mach/vm_param.h> ! 76: #import <vm/vm_map.h> ! 77: #import <vm/vm_kern.h> ! 78: ! 79: #import <kern/assert.h> ! 80: ! 81: /* ! 82: * Internal prototypes ! 83: */ ! 84: vm_offset_t newStack(); ! 85: static __inline__ vm_offset_t _allocStack(boolean_t canblock); ! 86: static void enterFreeList(vm_offset_t stack); ! 87: static void checkFreeList(vm_offset_t stack); ! 88: int canSwap(vm_offset_t stack); ! 89: void doSwapout(vm_offset_t stack); ! 90: ! 91: /* ! 92: * Data structures ! 93: */ ! 94: static queue_head_t stack_queue; ! 95: lock_data_t stack_queue_lock; ! 96: ! 97: static int kernelStackBlock; /* actual size of stack */ ! 98: static int stacksPerPage; /* can be <= 1 */ ! 99: static int stack_free_count = 0; /* number actually free */ ! 100: static int stack_free_target = 8; /* number we want free */ ! 101: static boolean_t need_stack_wakeup = FALSE;/* if true, notify that ! 102: * stacks are available */ ! 103: ! 104: struct stackStats { ! 105: int allocatedChunks; /* space alloc'ed from the kernel map */ ! 106: int allocatedStacks; /* total number of allocated stacks */ ! 107: int freeStacks; /* number of stacks on the free list */ ! 108: int swappableStacks; /* number of stacks marked swappable */ ! 109: int swappedChunks; /* number of pages swapped out */ ! 110: } stackStats; ! 111: ! 112: ! 113: /* ! 114: * kstack_init: initialize the kernel stack data structures ! 115: */ ! 116: void ! 117: initKernelStacks() ! 118: { ! 119: queue_init(&stack_queue); ! 120: lock_init(&stack_queue_lock, TRUE); ! 121: ! 122: kernelStackBlock = KERNEL_STACK_SIZE + sizeof(struct _kernelStack); ! 123: stacksPerPage = (page_size + kernelStackBlock - 1) / kernelStackBlock; ! 124: } ! 125: ! 126: ! 127: /* ! 128: * enterFreeList: enter a stack on the free list, marking it free in the process ! 129: */ ! 130: static void ! 131: enterFreeList(vm_offset_t stack) ! 132: { ! 133: /* ! 134: * Put the guy on the free list ! 135: */ ! 136: ((kernelStack) stack)->status = STACK_FREE; ! 137: queue_enter(&stack_queue, (kernelStack) stack, kernelStack, freeList); ! 138: stack_free_count ++; ! 139: stackStats.freeStacks++; ! 140: } ! 141: ! 142: ! 143: /* ! 144: * checkFreeList: try to free up a chunk of memory of all stacks in that chunk ! 145: * are free. ! 146: */ ! 147: static void ! 148: checkFreeList(vm_offset_t stack) ! 149: { ! 150: int i, freeAll; ! 151: vm_offset_t page = trunc_page(stack); ! 152: vm_offset_t thisStack; ! 153: ! 154: /* ! 155: * Determine if we should free a page by checking the status of each ! 156: * stack on a page. ! 157: */ ! 158: thisStack = page; ! 159: freeAll = TRUE; ! 160: for (i = 0; i < stacksPerPage; i++) { ! 161: if ( ((kernelStack) thisStack)->status != STACK_FREE ) ! 162: freeAll = FALSE; ! 163: ! 164: thisStack += kernelStackBlock; ! 165: } ! 166: ! 167: if (!freeAll) { ! 168: if (canSwap(stack)) ! 169: doSwapout(stack); ! 170: return; ! 171: } ! 172: ! 173: /* ! 174: * We should free the page, so go through and remove all the stacks ! 175: * on this page from the free list, then free the page. ! 176: */ ! 177: thisStack = page; ! 178: for (i = 0; i < stacksPerPage; i++) { ! 179: queue_remove(&stack_queue, (kernelStack) thisStack, kernelStack, freeList); ! 180: stack_free_count--; ! 181: stackStats.freeStacks--; ! 182: ! 183: #if MACH_DEBUG ! 184: stack_finalize(thisStack + sizeof (struct _kernelStack)); ! 185: #endif /* MACH_DEBUG */ ! 186: ! 187: thisStack += kernelStackBlock; ! 188: } ! 189: ! 190: kmem_free(kernel_map, stack, kernelStackBlock); ! 191: stackStats.allocatedChunks--; ! 192: } ! 193: ! 194: ! 195: /* ! 196: * freeStack: free up a kernel stack ! 197: * ! 198: * We put the stack on the free list, then check all items on that page to see if ! 199: * they can be freed. If so, we remove all the stacks on the page from the free ! 200: * list and free the page. ! 201: * ! 202: * A further optimization would be to try to swap the page if only free stacks and ! 203: * swapped stacks remained on the page. ! 204: */ ! 205: void ! 206: freeStack(vm_offset_t stack) ! 207: { ! 208: stackStats.allocatedStacks--; ! 209: stack -= sizeof(struct _kernelStack); ! 210: ! 211: assert(((kernelStack) stack)->status == STACK_IN_USE); ! 212: ! 213: lock_write(&stack_queue_lock); ! 214: enterFreeList(stack); ! 215: lock_done(&stack_queue_lock); ! 216: ! 217: /* ! 218: * Try to keep some stacks free so not everyone goes through the pain of ! 219: * allocation. ! 220: */ ! 221: if (need_stack_wakeup) { ! 222: need_stack_wakeup = FALSE; ! 223: thread_wakeup(&stack_queue); ! 224: } ! 225: ! 226: if (stack_free_count <= stack_free_target) ! 227: return; ! 228: ! 229: checkFreeList(stack); ! 230: } ! 231: ! 232: ! 233: /* ! 234: * newStack: allocate a new kernel stack ! 235: * ! 236: * Here, we just allocate a new page and break it up into its constituent stacks. ! 237: * One stack (the first in the chunk) is returned as the new stack, and the ! 238: * remaining ones are marked as free and put on the free list. ! 239: */ ! 240: vm_offset_t ! 241: newStack() ! 242: { ! 243: vm_offset_t newPage, stack; ! 244: int i; ! 245: ! 246: if (kmem_alloc_wired(kernel_map, ! 247: &newPage, kernelStackBlock) != KERN_SUCCESS) ! 248: return 0; ! 249: ! 250: stackStats.allocatedChunks++; ! 251: ! 252: ((kernelStack) newPage)->status = STACK_IN_USE; ! 253: ! 254: stackStats.allocatedStacks++; ! 255: ! 256: #if MACH_DEBUG ! 257: stack_init(newPage + sizeof (struct _kernelStack)); ! 258: #endif /* MACH_DEBUG */ ! 259: ! 260: if (stacksPerPage <= 1) ! 261: return newPage + sizeof(struct _kernelStack); ! 262: ! 263: /* ! 264: * Return the first guy on the page as our stack, and create ! 265: * free stacks out of the rest of the slots on the page. ! 266: */ ! 267: lock_write(&stack_queue_lock); ! 268: stack = newPage + kernelStackBlock; ! 269: for (i = 1; i < stacksPerPage; i++) { ! 270: #if MACH_DEBUG ! 271: stack_init(stack + sizeof (struct _kernelStack)); ! 272: #endif /* MACH_DEBUG */ ! 273: enterFreeList(stack); ! 274: stack += kernelStackBlock; ! 275: } ! 276: lock_done(&stack_queue_lock); ! 277: ! 278: return newPage + sizeof(struct _kernelStack); ! 279: } ! 280: ! 281: ! 282: /* ! 283: * allocStack: allocate and return a kernel stack (was stack_alloc) ! 284: * ! 285: * Try to grab a free stack off the list of free stacks. If that fails, get ! 286: * a new stack. If that fails (unlikely), fall asleep and wait for someone to ! 287: * free a stack. ! 288: * ! 289: * Return the address of the new stack. ! 290: */ ! 291: static __inline__ ! 292: vm_offset_t ! 293: _allocStack( ! 294: boolean_t canblock ! 295: ) ! 296: { ! 297: register vm_offset_t stack; ! 298: register boolean_t msg_printed = FALSE; ! 299: register kern_return_t result = THREAD_AWAKENED; ! 300: ! 301: do { ! 302: lock_write(&stack_queue_lock); ! 303: if (stack_free_count != 0) { ! 304: stack = (vm_offset_t) dequeue_head(&stack_queue); ! 305: ((kernelStack) stack)->status = STACK_IN_USE; ! 306: stack += sizeof(struct _kernelStack); ! 307: stack_free_count--; ! 308: stackStats.freeStacks--; ! 309: stackStats.allocatedStacks++; ! 310: } else { ! 311: stack = (vm_offset_t)0; ! 312: } ! 313: lock_done(&stack_queue_lock); ! 314: ! 315: if (!canblock) ! 316: return (stack); ! 317: ! 318: /* ! 319: * If no stacks on queue, allocate one. If that fails, ! 320: * pause and wait for a stack to be freed. ! 321: */ ! 322: if (stack == (vm_offset_t)0) ! 323: stack = newStack(); ! 324: ! 325: if (stack == (vm_offset_t)0) { ! 326: if (!msg_printed ) { ! 327: msg_printed = TRUE; ! 328: uprintf("MACH: Out of kernel stacks, pausing..."); ! 329: if (!need_stack_wakeup) ! 330: printf("stack_alloc: Kernel stacks exhausted\n"); ! 331: } ! 332: else if (result != THREAD_AWAKENED) { ! 333: /* ! 334: * Somebody wants us; return a bogus stack. ! 335: */ ! 336: return((vm_offset_t)0); ! 337: } ! 338: ! 339: /* ! 340: * Now wait for stack, but first make sure one ! 341: * hasn't appeared in the interim. ! 342: */ ! 343: lock_write(&stack_queue_lock); ! 344: if(stack_free_count != 0) { ! 345: lock_done(&stack_queue_lock); ! 346: result = THREAD_AWAKENED; ! 347: continue; ! 348: } ! 349: assert_wait(&stack_queue, FALSE); ! 350: need_stack_wakeup = TRUE; ! 351: lock_done(&stack_queue_lock); ! 352: thread_block(); ! 353: result = current_thread()->wait_result; ! 354: } else { ! 355: if (msg_printed) ! 356: uprintf("continuing\n"); /* got a stack now */ ! 357: } ! 358: } while (stack == (vm_offset_t)0); ! 359: ! 360: return(stack); ! 361: } ! 362: ! 363: vm_offset_t ! 364: allocStack() ! 365: { ! 366: return (_allocStack(TRUE)); ! 367: } ! 368: ! 369: ! 370: /* ! 371: * canSwap: see if we can swap the entire chunk that this stack lives on ! 372: * ! 373: * Return TRUE if we can, FALSE otherwise. ! 374: */ ! 375: int ! 376: canSwap(vm_offset_t stack) ! 377: { ! 378: int i; ! 379: vm_offset_t thisStack; ! 380: ! 381: /* ! 382: * Determine if we should swap a page by checking the status of each ! 383: * stack on a page. ! 384: */ ! 385: thisStack = trunc_page(stack); ! 386: for (i = 0; i < stacksPerPage; i++) { ! 387: if ( ((kernelStack) thisStack)->status == STACK_IN_USE ) ! 388: return FALSE; ! 389: ! 390: thisStack += kernelStackBlock; ! 391: } ! 392: ! 393: return TRUE; ! 394: } ! 395: ! 396: ! 397: /* ! 398: * doSwapout: really swap out a stack. ! 399: * ! 400: * The stack_queue_lock must be held across this call. ! 401: */ ! 402: void ! 403: doSwapout(vm_offset_t stack) ! 404: { ! 405: int i, swapAll; ! 406: vm_offset_t page = trunc_page(stack); ! 407: vm_offset_t thisStack; ! 408: ! 409: /* ! 410: * Make sure we remove all free stacks on this page from the free list. ! 411: */ ! 412: thisStack = page; ! 413: swapAll = TRUE; ! 414: for (i = 0; i < stacksPerPage; i++) { ! 415: ! 416: assert( ((kernelStack) thisStack)->status != STACK_IN_USE ); ! 417: ! 418: if ( ((kernelStack) thisStack)->status == STACK_FREE ) { ! 419: queue_remove(&stack_queue, (kernelStack) thisStack, kernelStack, freeList); ! 420: stack_free_count--; ! 421: stackStats.freeStacks--; ! 422: } ! 423: ! 424: thisStack += kernelStackBlock; ! 425: } ! 426: ! 427: /* ! 428: * Hack... we need a way to designate that the page is really ! 429: * unwired so that when we bring it back in, we can notice that ! 430: * it had been unwired. ! 431: */ ! 432: ((kernelStack) page)->freeList.next = (struct queue_entry *) 0xfeedface; ! 433: (void) vm_map_pageable(kernel_map, page, ! 434: round_page(page + kernelStackBlock), TRUE); ! 435: stackStats.swappedChunks++; ! 436: } ! 437: ! 438: ! 439: /* ! 440: * swapoutStack: try to swap out a stack ! 441: * ! 442: * We swap out stacks by unwiring their memory, then allowing the pagout daemon ! 443: * to page out the unused stack. If a kernel stack spans whole pages, we can just ! 444: * unwire its memory right away. However, if it occupies a fraction of a page, ! 445: * then we must also be able to swap any other stacks on that page. ! 446: */ ! 447: void ! 448: swapoutStack(vm_offset_t stack) ! 449: { ! 450: int i, swapAll; ! 451: vm_offset_t page = trunc_page(stack); ! 452: vm_offset_t thisStack; ! 453: ! 454: stack -= sizeof(struct _kernelStack); ! 455: stackStats.swappableStacks++; ! 456: ! 457: lock_write(&stack_queue_lock); ! 458: /* ! 459: * Mark this stack swappable ! 460: */ ! 461: ((kernelStack) stack)->status = STACK_SWAPPED; ! 462: ! 463: /* ! 464: * Bug out now if we can't swap the stack ! 465: */ ! 466: if (!canSwap(stack)) { ! 467: lock_done(&stack_queue_lock); ! 468: return; ! 469: } ! 470: ! 471: doSwapout(stack); ! 472: lock_done(&stack_queue_lock); ! 473: } ! 474: ! 475: ! 476: /* ! 477: * swapinStack: swap in a stack ! 478: * ! 479: * We swap in stacks by wiring their memory. We can just wire its memory right ! 480: * away. If there are other stacks in that memory, no problem, they just end up ! 481: * resident too. ! 482: */ ! 483: void ! 484: swapinStack(vm_offset_t stack) ! 485: { ! 486: int i, swapAll; ! 487: vm_offset_t page = trunc_page(stack); ! 488: vm_offset_t thisStack; ! 489: ! 490: stack -= sizeof(struct _kernelStack); ! 491: stackStats.swappableStacks--; ! 492: ! 493: (void) vm_map_pageable(kernel_map, page, ! 494: round_page(page + kernelStackBlock), FALSE); ! 495: ! 496: lock_write(&stack_queue_lock); ! 497: /* ! 498: * Mark our particular stack in use. ! 499: */ ! 500: ((kernelStack) stack)->status = STACK_IN_USE; ! 501: ! 502: /* ! 503: * Check the magic hack to see if we've already put this stuff on the free ! 504: * list. ! 505: */ ! 506: if (((kernelStack) page)->freeList.next != (struct queue_entry *) 0xfeedface) { ! 507: lock_done(&stack_queue_lock); ! 508: return; ! 509: } ! 510: ! 511: ((kernelStack) page)->freeList.next = (struct queue_entry *) 0; ! 512: stackStats.swappedChunks--; ! 513: ! 514: /* ! 515: * Scan through the memory we just brought in and put free stacks on ! 516: * the free list. ! 517: */ ! 518: thisStack = page; ! 519: swapAll = TRUE; ! 520: for (i = 0; i < stacksPerPage; i++) { ! 521: if ( ((kernelStack) thisStack)->status == STACK_FREE ) { ! 522: enterFreeList(thisStack); ! 523: } ! 524: ! 525: thisStack += kernelStackBlock; ! 526: } ! 527: lock_done(&stack_queue_lock); ! 528: } ! 529: ! 530: boolean_t stack_alloc_try( ! 531: thread_t thread, ! 532: void (*resume)(thread_t)) ! 533: { ! 534: register vm_offset_t stack = _allocStack(FALSE); ! 535: ! 536: if (!stack) ! 537: stack = thread->stack_privilege; ! 538: if (stack) { ! 539: stack_attach(thread, stack, resume); ! 540: return TRUE; ! 541: } ! 542: ! 543: return FALSE; ! 544: } ! 545: ! 546: void stack_alloc( ! 547: thread_t thread, ! 548: void (*resume)(thread_t)) ! 549: { ! 550: vm_offset_t stack; ! 551: ! 552: stack = allocStack(); ! 553: if (!stack) ! 554: panic("stack_alloc"); ! 555: ! 556: stack_attach(thread, stack, resume); ! 557: } ! 558: ! 559: void stack_free( ! 560: thread_t thread) ! 561: { ! 562: register vm_offset_t stack; ! 563: ! 564: stack = stack_detach(thread); ! 565: ! 566: if (stack != thread->stack_privilege) ! 567: freeStack(stack); ! 568: } ! 569: ! 570: void stack_collect(void) ! 571: { ! 572: } ! 573: ! 574: #if MACH_DEBUG ! 575: ! 576: void stack_statistics( ! 577: natural_t *totalp, ! 578: vm_size_t *maxusagep) ! 579: { ! 580: extern boolean_t stack_check_usage; ! 581: ! 582: lock_read(&stack_queue_lock); ! 583: if (stack_check_usage) { ! 584: vm_offset_t stack; ! 585: ! 586: for (stack = (vm_offset_t)queue_first(&stack_queue); ! 587: !queue_end(&stack_queue, (queue_entry_t)stack); ! 588: stack = (vm_offset_t) ! 589: queue_next((queue_entry_t)stack)) { ! 590: vm_size_t usage = ! 591: stack_usage(stack + ! 592: sizeof (struct _kernelStack)); ! 593: ! 594: if (usage > *maxusagep) ! 595: *maxusagep = usage; ! 596: } ! 597: } ! 598: ! 599: *totalp = stack_free_count; ! 600: lock_done(&stack_queue_lock); ! 601: } ! 602: ! 603: #endif /* MACH_DEBUG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.