thr_stack.c revision 136190
180021Sjasone/* 280021Sjasone * Copyright (c) 2001 Daniel Eischen <deischen@freebsd.org> 380021Sjasone * Copyright (c) 2000-2001 Jason Evans <jasone@freebsd.org> 480021Sjasone * All rights reserved. 580021Sjasone * 680021Sjasone * Redistribution and use in source and binary forms, with or without 780021Sjasone * modification, are permitted provided that the following conditions 880021Sjasone * are met: 980021Sjasone * 1. Redistributions of source code must retain the above copyright 1080021Sjasone * notice, this list of conditions and the following disclaimer. 1180021Sjasone * 2. Redistributions in binary form must reproduce the above copyright 1280021Sjasone * notice, this list of conditions and the following disclaimer in the 1380021Sjasone * documentation and/or other materials provided with the distribution. 1480021Sjasone * 1580021Sjasone * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND 1680021Sjasone * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1780021Sjasone * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1880021Sjasone * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE 1980021Sjasone * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2080021Sjasone * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2180021Sjasone * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2280021Sjasone * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2380021Sjasone * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2480021Sjasone * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2580021Sjasone * SUCH DAMAGE. 2680021Sjasone * 2780021Sjasone * $FreeBSD: head/lib/libkse/thread/thr_stack.c 136190 2004-10-06 08:11:07Z davidxu $ 2880021Sjasone */ 2980021Sjasone#include <sys/types.h> 3080021Sjasone#include <sys/mman.h> 3180021Sjasone#include <sys/queue.h> 3280021Sjasone#include <stdlib.h> 3380021Sjasone#include <pthread.h> 34103388Smini#include "thr_private.h" 3580021Sjasone 3680021Sjasone/* Spare thread stack. */ 3780021Sjasonestruct stack { 3880021Sjasone LIST_ENTRY(stack) qe; /* Stack queue linkage. */ 3980021Sjasone size_t stacksize; /* Stack size (rounded up). */ 4080021Sjasone size_t guardsize; /* Guard size. */ 4180021Sjasone void *stackaddr; /* Stack address. */ 4280021Sjasone}; 4380021Sjasone 4480021Sjasone/* 45113658Sdeischen * Default sized (stack and guard) spare stack queue. Stacks are cached 46113658Sdeischen * to avoid additional complexity managing mmap()ed stack regions. Spare 47113658Sdeischen * stacks are used in LIFO order to increase cache locality. 4880021Sjasone */ 49113658Sdeischenstatic LIST_HEAD(, stack) dstackq = LIST_HEAD_INITIALIZER(dstackq); 5080021Sjasone 5180021Sjasone/* 5280021Sjasone * Miscellaneous sized (non-default stack and/or guard) spare stack queue. 53113658Sdeischen * Stacks are cached to avoid additional complexity managing mmap()ed 54113658Sdeischen * stack regions. This list is unordered, since ordering on both stack 55113658Sdeischen * size and guard size would be more trouble than it's worth. Stacks are 56113658Sdeischen * allocated from this cache on a first size match basis. 5780021Sjasone */ 58113658Sdeischenstatic LIST_HEAD(, stack) mstackq = LIST_HEAD_INITIALIZER(mstackq); 5980021Sjasone 6080021Sjasone/** 61113658Sdeischen * Base address of the last stack allocated (including its red zone, if 62113658Sdeischen * there is one). Stacks are allocated contiguously, starting beyond the 63113658Sdeischen * top of the main stack. When a new stack is created, a red zone is 64136190Sdavidxu * typically created (actually, the red zone is mapped with PROT_NONE) above 65113658Sdeischen * the top of the stack, such that the stack will not be able to grow all 66113658Sdeischen * the way to the bottom of the next stack. This isn't fool-proof. It is 67113658Sdeischen * possible for a stack to grow by a large amount, such that it grows into 68113658Sdeischen * the next stack, and as long as the memory within the red zone is never 69113658Sdeischen * accessed, nothing will prevent one thread stack from trouncing all over 70113658Sdeischen * the next. 7180021Sjasone * 7280021Sjasone * low memory 7380021Sjasone * . . . . . . . . . . . . . . . . . . 7480021Sjasone * | | 7580021Sjasone * | stack 3 | start of 3rd thread stack 7680021Sjasone * +-----------------------------------+ 7780021Sjasone * | | 7880021Sjasone * | Red Zone (guard page) | red zone for 2nd thread 7980021Sjasone * | | 8080021Sjasone * +-----------------------------------+ 8180021Sjasone * | stack 2 - PTHREAD_STACK_DEFAULT | top of 2nd thread stack 8280021Sjasone * | | 8380021Sjasone * | | 8480021Sjasone * | | 8580021Sjasone * | | 8680021Sjasone * | stack 2 | 8780021Sjasone * +-----------------------------------+ <-- start of 2nd thread stack 8880021Sjasone * | | 8980021Sjasone * | Red Zone | red zone for 1st thread 9080021Sjasone * | | 9180021Sjasone * +-----------------------------------+ 9280021Sjasone * | stack 1 - PTHREAD_STACK_DEFAULT | top of 1st thread stack 9380021Sjasone * | | 9480021Sjasone * | | 9580021Sjasone * | | 9680021Sjasone * | | 9780021Sjasone * | stack 1 | 9880021Sjasone * +-----------------------------------+ <-- start of 1st thread stack 9980021Sjasone * | | (initial value of last_stack) 10080021Sjasone * | Red Zone | 10180021Sjasone * | | red zone for main thread 10280021Sjasone * +-----------------------------------+ 10380021Sjasone * | USRSTACK - PTHREAD_STACK_INITIAL | top of main thread stack 10480021Sjasone * | | ^ 10580021Sjasone * | | | 10680021Sjasone * | | | 10780021Sjasone * | | | stack growth 10880021Sjasone * | | 10980021Sjasone * +-----------------------------------+ <-- start of main thread stack 11080021Sjasone * (USRSTACK) 11180021Sjasone * high memory 11280021Sjasone * 11380021Sjasone */ 114113658Sdeischenstatic void *last_stack = NULL; 11580021Sjasone 116120072Sdavidxu/* 117120072Sdavidxu * Round size up to the nearest multiple of 118120072Sdavidxu * _thr_page_size. 119120072Sdavidxu */ 120120072Sdavidxustatic inline size_t 121120072Sdavidxuround_up(size_t size) 122120072Sdavidxu{ 123120072Sdavidxu if (size % _thr_page_size != 0) 124120072Sdavidxu size = ((size / _thr_page_size) + 1) * 125120072Sdavidxu _thr_page_size; 126120072Sdavidxu return size; 127120072Sdavidxu} 128120072Sdavidxu 129113658Sdeischenint 130113658Sdeischen_thr_stack_alloc(struct pthread_attr *attr) 13180021Sjasone{ 132113658Sdeischen struct stack *spare_stack; 133113658Sdeischen struct kse *curkse; 134113658Sdeischen kse_critical_t crit; 135113658Sdeischen size_t stacksize; 136113658Sdeischen size_t guardsize; 137136190Sdavidxu char *stackaddr; 13880021Sjasone 13980021Sjasone /* 140113658Sdeischen * Round up stack size to nearest multiple of _thr_page_size so 141113658Sdeischen * that mmap() * will work. If the stack size is not an even 142113658Sdeischen * multiple, we end up initializing things such that there is 143113658Sdeischen * unused space above the beginning of the stack, so the stack 144113658Sdeischen * sits snugly against its guard. 14580021Sjasone */ 146120072Sdavidxu stacksize = round_up(attr->stacksize_attr); 147120072Sdavidxu guardsize = round_up(attr->guardsize_attr); 148120072Sdavidxu 149113658Sdeischen attr->stackaddr_attr = NULL; 150113658Sdeischen attr->flags &= ~THR_STACK_USER; 15180021Sjasone 15280021Sjasone /* 153113658Sdeischen * Use the garbage collector lock for synchronization of the 154113658Sdeischen * spare stack lists and allocations from usrstack. 155113658Sdeischen */ 156113658Sdeischen crit = _kse_critical_enter(); 157113658Sdeischen curkse = _get_curkse(); 158113658Sdeischen KSE_LOCK_ACQUIRE(curkse, &_thread_list_lock); 159113658Sdeischen /* 16080021Sjasone * If the stack and guard sizes are default, try to allocate a stack 16180021Sjasone * from the default-size stack cache: 16280021Sjasone */ 163113658Sdeischen if ((stacksize == THR_STACK_DEFAULT) && 164113658Sdeischen (guardsize == _thr_guard_default)) { 165113658Sdeischen if ((spare_stack = LIST_FIRST(&dstackq)) != NULL) { 166113658Sdeischen /* Use the spare stack. */ 16780021Sjasone LIST_REMOVE(spare_stack, qe); 168113658Sdeischen attr->stackaddr_attr = spare_stack->stackaddr; 16980021Sjasone } 17080021Sjasone } 17180021Sjasone /* 17280021Sjasone * The user specified a non-default stack and/or guard size, so try to 17380021Sjasone * allocate a stack from the non-default size stack cache, using the 17480021Sjasone * rounded up stack size (stack_size) in the search: 17580021Sjasone */ 17680021Sjasone else { 177113658Sdeischen LIST_FOREACH(spare_stack, &mstackq, qe) { 178113658Sdeischen if (spare_stack->stacksize == stacksize && 17980021Sjasone spare_stack->guardsize == guardsize) { 18080021Sjasone LIST_REMOVE(spare_stack, qe); 181113658Sdeischen attr->stackaddr_attr = spare_stack->stackaddr; 18280021Sjasone break; 18380021Sjasone } 18480021Sjasone } 18580021Sjasone } 186113658Sdeischen if (attr->stackaddr_attr != NULL) { 187113658Sdeischen /* A cached stack was found. Release the lock. */ 188113658Sdeischen KSE_LOCK_RELEASE(curkse, &_thread_list_lock); 189113658Sdeischen _kse_critical_leave(crit); 190113658Sdeischen } 191113658Sdeischen else { 192113658Sdeischen /* Allocate a stack from usrstack. */ 19385567Speter if (last_stack == NULL) 194113658Sdeischen last_stack = _usrstack - THR_STACK_INITIAL - 195113658Sdeischen _thr_guard_default; 19685567Speter 19780021Sjasone /* Allocate a new stack. */ 198136190Sdavidxu stackaddr = last_stack - stacksize - guardsize; 19980021Sjasone 20080021Sjasone /* 201113658Sdeischen * Even if stack allocation fails, we don't want to try to 202113658Sdeischen * use this location again, so unconditionally decrement 20380021Sjasone * last_stack. Under normal operating conditions, the most 204113658Sdeischen * likely reason for an mmap() error is a stack overflow of 205113658Sdeischen * the adjacent thread stack. 20680021Sjasone */ 207113658Sdeischen last_stack -= (stacksize + guardsize); 20880021Sjasone 209113658Sdeischen /* Release the lock before mmap'ing it. */ 210113658Sdeischen KSE_LOCK_RELEASE(curkse, &_thread_list_lock); 211113658Sdeischen _kse_critical_leave(crit); 212113658Sdeischen 213136190Sdavidxu /* Map the stack and guard page together, and split guard 214136190Sdavidxu page from allocated space: */ 215136190Sdavidxu if ((stackaddr = mmap(stackaddr, stacksize+guardsize, 216136190Sdavidxu PROT_READ | PROT_WRITE, MAP_STACK, 217136190Sdavidxu -1, 0)) != MAP_FAILED && 218136190Sdavidxu (guardsize == 0 || 219136190Sdavidxu mprotect(stackaddr, guardsize, PROT_NONE) == 0)) { 220136190Sdavidxu stackaddr += guardsize; 221136190Sdavidxu } else { 222136190Sdavidxu if (stackaddr != MAP_FAILED) 223136190Sdavidxu munmap(stackaddr, stacksize + guardsize); 224136190Sdavidxu stackaddr = NULL; 225136190Sdavidxu } 226136190Sdavidxu attr->stackaddr_attr = stackaddr; 22780021Sjasone } 228113658Sdeischen if (attr->stackaddr_attr != NULL) 229113658Sdeischen return (0); 230113658Sdeischen else 231113658Sdeischen return (-1); 23280021Sjasone} 23380021Sjasone 234113658Sdeischen/* This function must be called with _thread_list_lock held. */ 23580021Sjasonevoid 236113658Sdeischen_thr_stack_free(struct pthread_attr *attr) 23780021Sjasone{ 238113658Sdeischen struct stack *spare_stack; 23980021Sjasone 240113658Sdeischen if ((attr != NULL) && ((attr->flags & THR_STACK_USER) == 0) 241113658Sdeischen && (attr->stackaddr_attr != NULL)) { 242113658Sdeischen spare_stack = (attr->stackaddr_attr + attr->stacksize_attr 243113658Sdeischen - sizeof(struct stack)); 244120072Sdavidxu spare_stack->stacksize = round_up(attr->stacksize_attr); 245120072Sdavidxu spare_stack->guardsize = round_up(attr->guardsize_attr); 246113658Sdeischen spare_stack->stackaddr = attr->stackaddr_attr; 24780021Sjasone 248113658Sdeischen if (spare_stack->stacksize == THR_STACK_DEFAULT && 249113658Sdeischen spare_stack->guardsize == _thr_guard_default) { 250113658Sdeischen /* Default stack/guard size. */ 251113658Sdeischen LIST_INSERT_HEAD(&dstackq, spare_stack, qe); 252113658Sdeischen } else { 253113658Sdeischen /* Non-default stack/guard size. */ 254113658Sdeischen LIST_INSERT_HEAD(&mstackq, spare_stack, qe); 255113658Sdeischen } 256113658Sdeischen attr->stackaddr_attr = NULL; 25780021Sjasone } 25880021Sjasone} 259