1 /* 2 * Copyright (c) 2001 Daniel Eischen <deischen@freebsd.org> 3 * Copyright (c) 2000-2001 Jason Evans <jasone@freebsd.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * $FreeBSD$ 28 */ 29 #include <sys/types.h> 30 #include <sys/mman.h> 31 #include <sys/param.h> 32 #include <sys/queue.h> 33 #include <sys/user.h> 34 #include <stdlib.h> 35 #include <pthread.h> 36 #include "thr_private.h" 37 38 /* Spare thread stack. */ 39 struct stack { 40 LIST_ENTRY(stack) qe; /* Stack queue linkage. */ 41 size_t stacksize; /* Stack size (rounded up). */ 42 size_t guardsize; /* Guard size. */ 43 void *stackaddr; /* Stack address. */ 44 }; 45 46 /* 47 * Default sized (stack and guard) spare stack queue. Stacks are cached to 48 * avoid additional complexity managing mmap()ed stack regions. Spare stacks 49 * are used in LIFO order to increase cache locality. 50 */ 51 static LIST_HEAD(, stack) _dstackq = LIST_HEAD_INITIALIZER(_dstackq); 52 53 /* 54 * Miscellaneous sized (non-default stack and/or guard) spare stack queue. 55 * Stacks are cached to avoid additional complexity managing mmap()ed stack 56 * regions. This list is unordered, since ordering on both stack size and guard 57 * size would be more trouble than it's worth. Stacks are allocated from this 58 * cache on a first size match basis. 59 */ 60 static LIST_HEAD(, stack) _mstackq = LIST_HEAD_INITIALIZER(_mstackq); 61 62 /** 63 * Base address of the last stack allocated (including its red zone, if there is 64 * one). Stacks are allocated contiguously, starting beyond the top of the main 65 * stack. When a new stack is created, a red zone is typically created 66 * (actually, the red zone is simply left unmapped) above the top of the stack, 67 * such that the stack will not be able to grow all the way to the bottom of the 68 * next stack. This isn't fool-proof. It is possible for a stack to grow by a 69 * large amount, such that it grows into the next stack, and as long as the 70 * memory within the red zone is never accessed, nothing will prevent one thread 71 * stack from trouncing all over the next. 72 * 73 * low memory 74 * . . . . . . . . . . . . . . . . . . 75 * | | 76 * | stack 3 | start of 3rd thread stack 77 * +-----------------------------------+ 78 * | | 79 * | Red Zone (guard page) | red zone for 2nd thread 80 * | | 81 * +-----------------------------------+ 82 * | stack 2 - PTHREAD_STACK_DEFAULT | top of 2nd thread stack 83 * | | 84 * | | 85 * | | 86 * | | 87 * | stack 2 | 88 * +-----------------------------------+ <-- start of 2nd thread stack 89 * | | 90 * | Red Zone | red zone for 1st thread 91 * | | 92 * +-----------------------------------+ 93 * | stack 1 - PTHREAD_STACK_DEFAULT | top of 1st thread stack 94 * | | 95 * | | 96 * | | 97 * | | 98 * | stack 1 | 99 * +-----------------------------------+ <-- start of 1st thread stack 100 * | | (initial value of last_stack) 101 * | Red Zone | 102 * | | red zone for main thread 103 * +-----------------------------------+ 104 * | USRSTACK - PTHREAD_STACK_INITIAL | top of main thread stack 105 * | | ^ 106 * | | | 107 * | | | 108 * | | | stack growth 109 * | | 110 * +-----------------------------------+ <-- start of main thread stack 111 * (USRSTACK) 112 * high memory 113 * 114 */ 115 static void * last_stack; 116 117 void * 118 _thread_stack_alloc(size_t stacksize, size_t guardsize) 119 { 120 void *stack = NULL; 121 struct stack *spare_stack; 122 size_t stack_size; 123 124 /* 125 * Round up stack size to nearest multiple of _pthread_page_size, 126 * so that mmap() * will work. If the stack size is not an even 127 * multiple, we end up initializing things such that there is unused 128 * space above the beginning of the stack, so the stack sits snugly 129 * against its guard. 130 */ 131 if (stacksize % _pthread_page_size != 0) 132 stack_size = ((stacksize / _pthread_page_size) + 1) * 133 _pthread_page_size; 134 else 135 stack_size = stacksize; 136 137 /* 138 * If the stack and guard sizes are default, try to allocate a stack 139 * from the default-size stack cache: 140 */ 141 if (stack_size == PTHREAD_STACK_DEFAULT && 142 guardsize == _pthread_guard_default) { 143 /* 144 * Use the garbage collector mutex for synchronization of the 145 * spare stack list. 146 */ 147 STACK_LOCK; 148 149 if ((spare_stack = LIST_FIRST(&_dstackq)) != NULL) { 150 /* Use the spare stack. */ 151 LIST_REMOVE(spare_stack, qe); 152 stack = spare_stack->stackaddr; 153 } 154 155 /* Unlock the garbage collector mutex. */ 156 STACK_UNLOCK; 157 } 158 /* 159 * The user specified a non-default stack and/or guard size, so try to 160 * allocate a stack from the non-default size stack cache, using the 161 * rounded up stack size (stack_size) in the search: 162 */ 163 else { 164 /* 165 * Use the garbage collector mutex for synchronization of the 166 * spare stack list. 167 */ 168 STACK_LOCK; 169 170 LIST_FOREACH(spare_stack, &_mstackq, qe) { 171 if (spare_stack->stacksize == stack_size && 172 spare_stack->guardsize == guardsize) { 173 LIST_REMOVE(spare_stack, qe); 174 stack = spare_stack->stackaddr; 175 break; 176 } 177 } 178 179 /* Unlock the garbage collector mutex. */ 180 STACK_UNLOCK; 181 } 182 183 /* Check if a stack was not allocated from a stack cache: */ 184 if (stack == NULL) { 185 186 if (last_stack == NULL) 187 last_stack = _usrstack - PTHREAD_STACK_INITIAL - 188 _pthread_guard_default; 189 190 /* Allocate a new stack. */ 191 stack = last_stack - stack_size; 192 193 /* 194 * Even if stack allocation fails, we don't want to try to use 195 * this location again, so unconditionally decrement 196 * last_stack. Under normal operating conditions, the most 197 * likely reason for an mmap() error is a stack overflow of the 198 * adjacent thread stack. 199 */ 200 last_stack -= (stack_size + guardsize); 201 202 /* Stack: */ 203 if (mmap(stack, stack_size, PROT_READ | PROT_WRITE, MAP_STACK, 204 -1, 0) == MAP_FAILED) 205 stack = NULL; 206 } 207 208 return (stack); 209 } 210 211 /* This function must be called with the 'dead thread list' lock held. */ 212 void 213 _thread_stack_free(void *stack, size_t stacksize, size_t guardsize) 214 { 215 struct stack *spare_stack; 216 217 spare_stack = (stack + stacksize - sizeof(struct stack)); 218 /* Round stacksize up to nearest multiple of _pthread_page_size. */ 219 if (stacksize % _pthread_page_size != 0) { 220 spare_stack->stacksize = 221 ((stacksize / _pthread_page_size) + 1) * 222 _pthread_page_size; 223 } else 224 spare_stack->stacksize = stacksize; 225 spare_stack->guardsize = guardsize; 226 spare_stack->stackaddr = stack; 227 228 if (spare_stack->stacksize == PTHREAD_STACK_DEFAULT && 229 spare_stack->guardsize == _pthread_guard_default) { 230 /* Default stack/guard size. */ 231 LIST_INSERT_HEAD(&_dstackq, spare_stack, qe); 232 } else { 233 /* Non-default stack/guard size. */ 234 LIST_INSERT_HEAD(&_mstackq, spare_stack, qe); 235 } 236 } 237