![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to kernel_stack.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / kern|
Return to kernel_stack.c CVS log | Up to [Apple Darwin 0.x] / kernel / kern |
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.