thr_stack.c revision 141822 
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: head/lib/libkse/thread/thr_stack.c 141822 2005-02-13 18:38:06Z deischen $
28 */
29#include <sys/types.h>
30#include <sys/mman.h>
31#include <sys/queue.h>
32#include <stdlib.h>
33#include <pthread.h>
34#include "thr_private.h"
35
36/* Spare thread stack. */
37struct stack {
38	LIST_ENTRY(stack)	qe;		/* Stack queue linkage. */
39	size_t			stacksize;	/* Stack size (rounded up). */
40	size_t			guardsize;	/* Guard size. */
41	void			*stackaddr;	/* Stack address. */
42};
43
44/*
45 * Default sized (stack and guard) spare stack queue.  Stacks are cached
46 * to avoid additional complexity managing mmap()ed stack regions.  Spare
47 * stacks are used in LIFO order to increase cache locality.
48 */
49static LIST_HEAD(, stack)	dstackq = LIST_HEAD_INITIALIZER(dstackq);
50
51/*
52 * Miscellaneous sized (non-default stack and/or guard) spare stack queue.
53 * Stacks are cached to avoid additional complexity managing mmap()ed
54 * stack regions.  This list is unordered, since ordering on both stack
55 * size and guard size would be more trouble than it's worth.  Stacks are
56 * allocated from this cache on a first size match basis.
57 */
58static LIST_HEAD(, stack)	mstackq = LIST_HEAD_INITIALIZER(mstackq);
59
60/**
61 * Base address of the last stack allocated (including its red zone, if
62 * there is one).  Stacks are allocated contiguously, starting beyond the
63 * top of the main stack.  When a new stack is created, a red zone is
64 * typically created (actually, the red zone is mapped with PROT_NONE) above
65 * the top of the stack, such that the stack will not be able to grow all
66 * the way to the bottom of the next stack.  This isn't fool-proof.  It is
67 * possible for a stack to grow by a large amount, such that it grows into
68 * the next stack, and as long as the memory within the red zone is never
69 * accessed, nothing will prevent one thread stack from trouncing all over
70 * the next.
71 *
72 * low memory
73 *     . . . . . . . . . . . . . . . . . .
74 *    |                                   |
75 *    |             stack 3               | start of 3rd thread stack
76 *    +-----------------------------------+
77 *    |                                   |
78 *    |       Red Zone (guard page)       | red zone for 2nd thread
79 *    |                                   |
80 *    +-----------------------------------+
81 *    |  stack 2 - PTHREAD_STACK_DEFAULT  | top of 2nd thread stack
82 *    |                                   |
83 *    |                                   |
84 *    |                                   |
85 *    |                                   |
86 *    |             stack 2               |
87 *    +-----------------------------------+ <-- start of 2nd thread stack
88 *    |                                   |
89 *    |       Red Zone                    | red zone for 1st thread
90 *    |                                   |
91 *    +-----------------------------------+
92 *    |  stack 1 - PTHREAD_STACK_DEFAULT  | top of 1st thread stack
93 *    |                                   |
94 *    |                                   |
95 *    |                                   |
96 *    |                                   |
97 *    |             stack 1               |
98 *    +-----------------------------------+ <-- start of 1st thread stack
99 *    |                                   |   (initial value of last_stack)
100 *    |       Red Zone                    |
101 *    |                                   | red zone for main thread
102 *    +-----------------------------------+
103 *    | USRSTACK - PTHREAD_STACK_INITIAL  | top of main thread stack
104 *    |                                   | ^
105 *    |                                   | |
106 *    |                                   | |
107 *    |                                   | | stack growth
108 *    |                                   |
109 *    +-----------------------------------+ <-- start of main thread stack
110 *                                              (USRSTACK)
111 * high memory
112 *
113 */
114static void *last_stack = NULL;
115
116/*
117 * Round size up to the nearest multiple of
118 * _thr_page_size.
119 */
120static inline size_t
121round_up(size_t size)
122{
123	if (size % _thr_page_size != 0)
124		size = ((size / _thr_page_size) + 1) *
125		    _thr_page_size;
126	return size;
127}
128
129int
130_thr_stack_alloc(struct pthread_attr *attr)
131{
132	struct stack *spare_stack;
133	struct kse *curkse;
134	kse_critical_t crit;
135	size_t stacksize;
136	size_t guardsize;
137	char *stackaddr;
138
139	/*
140	 * Round up stack size to nearest multiple of _thr_page_size so
141	 * that mmap() * will work.  If the stack size is not an even
142	 * multiple, we end up initializing things such that there is
143	 * unused space above the beginning of the stack, so the stack
144	 * sits snugly against its guard.
145	 */
146	stacksize = round_up(attr->stacksize_attr);
147	guardsize = round_up(attr->guardsize_attr);
148
149	attr->stackaddr_attr = NULL;
150	attr->flags &= ~THR_STACK_USER;
151
152	/*
153	 * Use the garbage collector lock for synchronization of the
154	 * spare stack lists and allocations from usrstack.
155	 */
156	crit = _kse_critical_enter();
157	curkse = _get_curkse();
158	KSE_LOCK_ACQUIRE(curkse, &_thread_list_lock);
159	/*
160	 * If the stack and guard sizes are default, try to allocate a stack
161	 * from the default-size stack cache:
162	 */
163	if ((stacksize == _thr_stack_default) &&
164	    (guardsize == _thr_guard_default)) {
165		if ((spare_stack = LIST_FIRST(&dstackq)) != NULL) {
166			/* Use the spare stack. */
167			LIST_REMOVE(spare_stack, qe);
168			attr->stackaddr_attr = spare_stack->stackaddr;
169		}
170	}
171	/*
172	 * The user specified a non-default stack and/or guard size, so try to
173	 * allocate a stack from the non-default size stack cache, using the
174	 * rounded up stack size (stack_size) in the search:
175	 */
176	else {
177		LIST_FOREACH(spare_stack, &mstackq, qe) {
178			if (spare_stack->stacksize == stacksize &&
179			    spare_stack->guardsize == guardsize) {
180				LIST_REMOVE(spare_stack, qe);
181				attr->stackaddr_attr = spare_stack->stackaddr;
182				break;
183			}
184		}
185	}
186	if (attr->stackaddr_attr != NULL) {
187		/* A cached stack was found.  Release the lock. */
188		KSE_LOCK_RELEASE(curkse, &_thread_list_lock);
189		_kse_critical_leave(crit);
190	}
191	else {
192		/* Allocate a stack from usrstack. */
193		if (last_stack == NULL)
194			last_stack = _usrstack - _thr_stack_initial -
195			    _thr_guard_default;
196
197		/* Allocate a new stack. */
198		stackaddr = last_stack - stacksize - guardsize;
199
200		/*
201		 * Even if stack allocation fails, we don't want to try to
202		 * use this location again, so unconditionally decrement
203		 * last_stack.  Under normal operating conditions, the most
204		 * likely reason for an mmap() error is a stack overflow of
205		 * the adjacent thread stack.
206		 */
207		last_stack -= (stacksize + guardsize);
208
209		/* Release the lock before mmap'ing it. */
210		KSE_LOCK_RELEASE(curkse, &_thread_list_lock);
211		_kse_critical_leave(crit);
212
213		/* Map the stack and guard page together, and split guard
214		   page from allocated space: */
215		if ((stackaddr = mmap(stackaddr, stacksize+guardsize,
216		     PROT_READ | PROT_WRITE, MAP_STACK,
217		     -1, 0)) != MAP_FAILED &&
218		    (guardsize == 0 ||
219		     mprotect(stackaddr, guardsize, PROT_NONE) == 0)) {
220			stackaddr += guardsize;
221		} else {
222			if (stackaddr != MAP_FAILED)
223				munmap(stackaddr, stacksize + guardsize);
224			stackaddr = NULL;
225		}
226		attr->stackaddr_attr = stackaddr;
227	}
228	if (attr->stackaddr_attr != NULL)
229		return (0);
230	else
231		return (-1);
232}
233
234/* This function must be called with _thread_list_lock held. */
235void
236_thr_stack_free(struct pthread_attr *attr)
237{
238	struct stack *spare_stack;
239
240	if ((attr != NULL) && ((attr->flags & THR_STACK_USER) == 0)
241	    && (attr->stackaddr_attr != NULL)) {
242		spare_stack = (attr->stackaddr_attr + attr->stacksize_attr
243		    - sizeof(struct stack));
244		spare_stack->stacksize = round_up(attr->stacksize_attr);
245		spare_stack->guardsize = round_up(attr->guardsize_attr);
246		spare_stack->stackaddr = attr->stackaddr_attr;
247
248		if (spare_stack->stacksize == _thr_stack_default &&
249		    spare_stack->guardsize == _thr_guard_default) {
250			/* Default stack/guard size. */
251			LIST_INSERT_HEAD(&dstackq, spare_stack, qe);
252		} else {
253			/* Non-default stack/guard size. */
254			LIST_INSERT_HEAD(&mstackq, spare_stack, qe);
255		}
256		attr->stackaddr_attr = NULL;
257	}
258}
259