1 /* Library support for -fsplit-stack.  */
2 /* Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
3    Contributed by Ian Lance Taylor <iant@google.com>.
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11 
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16 
17 Under Section 7 of GPL version 3, you are granted additional
18 permissions described in the GCC Runtime Library Exception, version
19 3.1, as published by the Free Software Foundation.
20 
21 You should have received a copy of the GNU General Public License and
22 a copy of the GCC Runtime Library Exception along with this program;
23 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 <http://www.gnu.org/licenses/>.  */
25 
26 #include "tconfig.h"
27 #include "tsystem.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "libgcc_tm.h"
31 
32 /* If inhibit_libc is defined, we can not compile this file.  The
33    effect is that people will not be able to use -fsplit-stack.  That
34    is much better than failing the build particularly since people
35    will want to define inhibit_libc while building a compiler which
36    can build glibc.  */
37 
38 #ifndef inhibit_libc
39 
40 #include <assert.h>
41 #include <errno.h>
42 #include <signal.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <unistd.h>
46 #include <sys/mman.h>
47 #include <sys/uio.h>
48 
49 #include "generic-morestack.h"
50 
51 typedef unsigned uintptr_type __attribute__ ((mode (pointer)));
52 
53 /* This file contains subroutines that are used by code compiled with
54    -fsplit-stack.  */
55 
56 /* Declare functions to avoid warnings--there is no header file for
57    these internal functions.  We give most of these functions the
58    flatten attribute in order to minimize their stack usage--here we
59    must minimize stack usage even at the cost of code size, and in
60    general inlining everything will do that.  */
61 
62 extern void
63 __generic_morestack_set_initial_sp (void *sp, size_t len)
64   __attribute__ ((no_split_stack, flatten, visibility ("hidden")));
65 
66 extern void *
67 __generic_morestack (size_t *frame_size, void *old_stack, size_t param_size)
68   __attribute__ ((no_split_stack, flatten, visibility ("hidden")));
69 
70 extern void *
71 __generic_releasestack (size_t *pavailable)
72   __attribute__ ((no_split_stack, flatten, visibility ("hidden")));
73 
74 extern void
75 __morestack_block_signals (void)
76   __attribute__ ((no_split_stack, flatten, visibility ("hidden")));
77 
78 extern void
79 __morestack_unblock_signals (void)
80   __attribute__ ((no_split_stack, flatten, visibility ("hidden")));
81 
82 extern size_t
83 __generic_findstack (void *stack)
84   __attribute__ ((no_split_stack, flatten, visibility ("hidden")));
85 
86 extern void
87 __morestack_load_mmap (void)
88   __attribute__ ((no_split_stack, visibility ("hidden")));
89 
90 extern void *
91 __morestack_allocate_stack_space (size_t size)
92   __attribute__ ((visibility ("hidden")));
93 
94 /* These are functions which -fsplit-stack code can call.  These are
95    not called by the compiler, and are not hidden.  FIXME: These
96    should be in some header file somewhere, somehow.  */
97 
98 extern void *
99 __splitstack_find (void *, void *, size_t *, void **, void **, void **)
100   __attribute__ ((visibility ("default")));
101 
102 extern void
103 __splitstack_block_signals (int *, int *)
104   __attribute__ ((visibility ("default")));
105 
106 extern void
107 __splitstack_getcontext (void *context[10])
108   __attribute__ ((no_split_stack, visibility ("default")));
109 
110 extern void
111 __splitstack_setcontext (void *context[10])
112   __attribute__ ((no_split_stack, visibility ("default")));
113 
114 extern void *
115 __splitstack_makecontext (size_t, void *context[10], size_t *)
116   __attribute__ ((visibility ("default")));
117 
118 extern void *
119 __splitstack_resetcontext (void *context[10], size_t *)
120   __attribute__ ((visibility ("default")));
121 
122 extern void
123 __splitstack_releasecontext (void *context[10])
124   __attribute__ ((visibility ("default")));
125 
126 extern void
127 __splitstack_block_signals_context (void *context[10], int *, int *)
128   __attribute__ ((visibility ("default")));
129 
130 extern void *
131 __splitstack_find_context (void *context[10], size_t *, void **, void **,
132 			   void **)
133   __attribute__ ((visibility ("default")));
134 
135 /* These functions must be defined by the processor specific code.  */
136 
137 extern void *__morestack_get_guard (void)
138   __attribute__ ((no_split_stack, visibility ("hidden")));
139 
140 extern void __morestack_set_guard (void *)
141   __attribute__ ((no_split_stack, visibility ("hidden")));
142 
143 extern void *__morestack_make_guard (void *, size_t)
144   __attribute__ ((no_split_stack, visibility ("hidden")));
145 
146 /* When we allocate a stack segment we put this header at the
147    start.  */
148 
149 struct stack_segment
150 {
151   /* The previous stack segment--when a function running on this stack
152      segment returns, it will run on the previous one.  */
153   struct stack_segment *prev;
154   /* The next stack segment, if it has been allocated--when a function
155      is running on this stack segment, the next one is not being
156      used.  */
157   struct stack_segment *next;
158   /* The total size of this stack segment.  */
159   size_t size;
160   /* The stack address when this stack was created.  This is used when
161      popping the stack.  */
162   void *old_stack;
163   /* A list of memory blocks allocated by dynamic stack
164      allocation.  */
165   struct dynamic_allocation_blocks *dynamic_allocation;
166   /* A list of dynamic memory blocks no longer needed.  */
167   struct dynamic_allocation_blocks *free_dynamic_allocation;
168   /* An extra pointer in case we need some more information some
169      day.  */
170   void *extra;
171 };
172 
173 /* This structure holds the (approximate) initial stack pointer and
174    size for the system supplied stack for a thread.  This is set when
175    the thread is created.  We also store a sigset_t here to hold the
176    signal mask while splitting the stack, since we don't want to store
177    that on the stack.  */
178 
179 struct initial_sp
180 {
181   /* The initial stack pointer.  */
182   void *sp;
183   /* The stack length.  */
184   size_t len;
185   /* A signal mask, put here so that the thread can use it without
186      needing stack space.  */
187   sigset_t mask;
188   /* Non-zero if we should not block signals.  This is a reversed flag
189      so that the default zero value is the safe value.  The type is
190      uintptr_type because it replaced one of the void * pointers in
191      extra.  */
192   uintptr_type dont_block_signals;
193   /* Some extra space for later extensibility.  */
194   void *extra[4];
195 };
196 
197 /* A list of memory blocks allocated by dynamic stack allocation.
198    This is used for code that calls alloca or uses variably sized
199    arrays.  */
200 
201 struct dynamic_allocation_blocks
202 {
203   /* The next block in the list.  */
204   struct dynamic_allocation_blocks *next;
205   /* The size of the allocated memory.  */
206   size_t size;
207   /* The allocated memory.  */
208   void *block;
209 };
210 
211 /* These thread local global variables must be shared by all split
212    stack code across shared library boundaries.  Therefore, they have
213    default visibility.  They have extensibility fields if needed for
214    new versions.  If more radical changes are needed, new code can be
215    written using new variable names, while still using the existing
216    variables in a backward compatible manner.  Symbol versioning is
217    also used, although, since these variables are only referenced by
218    code in this file and generic-morestack-thread.c, it is likely that
219    simply using new names will suffice.  */
220 
221 /* The first stack segment allocated for this thread.  */
222 
223 __thread struct stack_segment *__morestack_segments
224   __attribute__ ((visibility ("default")));
225 
226 /* The stack segment that we think we are currently using.  This will
227    be correct in normal usage, but will be incorrect if an exception
228    unwinds into a different stack segment or if longjmp jumps to a
229    different stack segment.  */
230 
231 __thread struct stack_segment *__morestack_current_segment
232   __attribute__ ((visibility ("default")));
233 
234 /* The initial stack pointer and size for this thread.  */
235 
236 __thread struct initial_sp __morestack_initial_sp
237   __attribute__ ((visibility ("default")));
238 
239 /* A static signal mask, to avoid taking up stack space.  */
240 
241 static sigset_t __morestack_fullmask;
242 
243 /* Convert an integer to a decimal string without using much stack
244    space.  Return a pointer to the part of the buffer to use.  We this
245    instead of sprintf because sprintf will require too much stack
246    space.  */
247 
248 static char *
print_int(int val,char * buf,int buflen,size_t * print_len)249 print_int (int val, char *buf, int buflen, size_t *print_len)
250 {
251   int is_negative;
252   int i;
253   unsigned int uval;
254 
255   uval = (unsigned int) val;
256   if (val >= 0)
257     is_negative = 0;
258   else
259     {
260       is_negative = 1;
261       uval = - uval;
262     }
263 
264   i = buflen;
265   do
266     {
267       --i;
268       buf[i] = '0' + (uval % 10);
269       uval /= 10;
270     }
271   while (uval != 0 && i > 0);
272 
273   if (is_negative)
274     {
275       if (i > 0)
276 	--i;
277       buf[i] = '-';
278     }
279 
280   *print_len = buflen - i;
281   return buf + i;
282 }
283 
284 /* Print the string MSG/LEN, the errno number ERR, and a newline on
285    stderr.  Then crash.  */
286 
287 void
288 __morestack_fail (const char *, size_t, int) __attribute__ ((noreturn));
289 
290 void
__morestack_fail(const char * msg,size_t len,int err)291 __morestack_fail (const char *msg, size_t len, int err)
292 {
293   char buf[24];
294   static const char nl[] = "\n";
295   struct iovec iov[3];
296   union { char *p; const char *cp; } const_cast;
297 
298   const_cast.cp = msg;
299   iov[0].iov_base = const_cast.p;
300   iov[0].iov_len = len;
301   /* We can't call strerror, because it may try to translate the error
302      message, and that would use too much stack space.  */
303   iov[1].iov_base = print_int (err, buf, sizeof buf, &iov[1].iov_len);
304   const_cast.cp = &nl[0];
305   iov[2].iov_base = const_cast.p;
306   iov[2].iov_len = sizeof nl - 1;
307   /* FIXME: On systems without writev we need to issue three write
308      calls, or punt on printing errno.  For now this is irrelevant
309      since stack splitting only works on GNU/Linux anyhow.  */
310   writev (2, iov, 3);
311   abort ();
312 }
313 
314 /* Allocate a new stack segment.  FRAME_SIZE is the required frame
315    size.  */
316 
317 static struct stack_segment *
allocate_segment(size_t frame_size)318 allocate_segment (size_t frame_size)
319 {
320   static unsigned int static_pagesize;
321   static int use_guard_page;
322   unsigned int pagesize;
323   unsigned int overhead;
324   unsigned int allocate;
325   void *space;
326   struct stack_segment *pss;
327 
328   pagesize = static_pagesize;
329   if (pagesize == 0)
330     {
331       unsigned int p;
332 
333       pagesize = getpagesize ();
334 
335 #ifdef __GCC_HAVE_SYNC_COMPARE_AND_SWAP_4
336       p = __sync_val_compare_and_swap (&static_pagesize, 0, pagesize);
337 #else
338       /* Just hope this assignment is atomic.  */
339       static_pagesize = pagesize;
340       p = 0;
341 #endif
342 
343       use_guard_page = getenv ("SPLIT_STACK_GUARD") != 0;
344 
345       /* FIXME: I'm not sure this assert should be in the released
346 	 code.  */
347       assert (p == 0 || p == pagesize);
348     }
349 
350   overhead = sizeof (struct stack_segment);
351 
352   allocate = pagesize;
353   if (allocate < MINSIGSTKSZ)
354     allocate = ((MINSIGSTKSZ + overhead + pagesize - 1)
355 		& ~ (pagesize - 1));
356   if (allocate < frame_size)
357     allocate = ((frame_size + overhead + pagesize - 1)
358 		& ~ (pagesize - 1));
359 
360   if (use_guard_page)
361     allocate += pagesize;
362 
363   /* FIXME: If this binary requires an executable stack, then we need
364      to set PROT_EXEC.  Unfortunately figuring that out is complicated
365      and target dependent.  We would need to use dl_iterate_phdr to
366      see if there is any object which does not have a PT_GNU_STACK
367      phdr, though only for architectures which use that mechanism.  */
368   space = mmap (NULL, allocate, PROT_READ | PROT_WRITE,
369 		MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
370   if (space == MAP_FAILED)
371     {
372       static const char msg[] =
373 	"unable to allocate additional stack space: errno ";
374       __morestack_fail (msg, sizeof msg - 1, errno);
375     }
376 
377   if (use_guard_page)
378     {
379       void *guard;
380 
381 #ifdef STACK_GROWS_DOWNWARD
382       guard = space;
383       space = (char *) space + pagesize;
384 #else
385       guard = space + allocate - pagesize;
386 #endif
387 
388       mprotect (guard, pagesize, PROT_NONE);
389       allocate -= pagesize;
390     }
391 
392   pss = (struct stack_segment *) space;
393 
394   pss->prev = NULL;
395   pss->next = NULL;
396   pss->size = allocate - overhead;
397   pss->dynamic_allocation = NULL;
398   pss->free_dynamic_allocation = NULL;
399   pss->extra = NULL;
400 
401   return pss;
402 }
403 
404 /* Free a list of dynamic blocks.  */
405 
406 static void
free_dynamic_blocks(struct dynamic_allocation_blocks * p)407 free_dynamic_blocks (struct dynamic_allocation_blocks *p)
408 {
409   while (p != NULL)
410     {
411       struct dynamic_allocation_blocks *next;
412 
413       next = p->next;
414       free (p->block);
415       free (p);
416       p = next;
417     }
418 }
419 
420 /* Merge two lists of dynamic blocks.  */
421 
422 static struct dynamic_allocation_blocks *
merge_dynamic_blocks(struct dynamic_allocation_blocks * a,struct dynamic_allocation_blocks * b)423 merge_dynamic_blocks (struct dynamic_allocation_blocks *a,
424 		      struct dynamic_allocation_blocks *b)
425 {
426   struct dynamic_allocation_blocks **pp;
427 
428   if (a == NULL)
429     return b;
430   if (b == NULL)
431     return a;
432   for (pp = &a->next; *pp != NULL; pp = &(*pp)->next)
433     ;
434   *pp = b;
435   return a;
436 }
437 
438 /* Release stack segments.  If FREE_DYNAMIC is non-zero, we also free
439    any dynamic blocks.  Otherwise we return them.  */
440 
441 struct dynamic_allocation_blocks *
__morestack_release_segments(struct stack_segment ** pp,int free_dynamic)442 __morestack_release_segments (struct stack_segment **pp, int free_dynamic)
443 {
444   struct dynamic_allocation_blocks *ret;
445   struct stack_segment *pss;
446 
447   ret = NULL;
448   pss = *pp;
449   while (pss != NULL)
450     {
451       struct stack_segment *next;
452       unsigned int allocate;
453 
454       next = pss->next;
455 
456       if (pss->dynamic_allocation != NULL
457 	  || pss->free_dynamic_allocation != NULL)
458 	{
459 	  if (free_dynamic)
460 	    {
461 	      free_dynamic_blocks (pss->dynamic_allocation);
462 	      free_dynamic_blocks (pss->free_dynamic_allocation);
463 	    }
464 	  else
465 	    {
466 	      ret = merge_dynamic_blocks (pss->dynamic_allocation, ret);
467 	      ret = merge_dynamic_blocks (pss->free_dynamic_allocation, ret);
468 	    }
469 	}
470 
471       allocate = pss->size + sizeof (struct stack_segment);
472       if (munmap (pss, allocate) < 0)
473 	{
474 	  static const char msg[] = "munmap of stack space failed: errno ";
475 	  __morestack_fail (msg, sizeof msg - 1, errno);
476 	}
477 
478       pss = next;
479     }
480   *pp = NULL;
481 
482   return ret;
483 }
484 
485 /* This function is called by a processor specific function to set the
486    initial stack pointer for a thread.  The operating system will
487    always create a stack for a thread.  Here we record a stack pointer
488    near the base of that stack.  The size argument lets the processor
489    specific code estimate how much stack space is available on this
490    initial stack.  */
491 
492 void
__generic_morestack_set_initial_sp(void * sp,size_t len)493 __generic_morestack_set_initial_sp (void *sp, size_t len)
494 {
495   /* The stack pointer most likely starts on a page boundary.  Adjust
496      to the nearest 512 byte boundary.  It's not essential that we be
497      precise here; getting it wrong will just leave some stack space
498      unused.  */
499 #ifdef STACK_GROWS_DOWNWARD
500   sp = (void *) ((((__UINTPTR_TYPE__) sp + 511U) / 512U) * 512U);
501 #else
502   sp = (void *) ((((__UINTPTR_TYPE__) sp - 511U) / 512U) * 512U);
503 #endif
504 
505   __morestack_initial_sp.sp = sp;
506   __morestack_initial_sp.len = len;
507   sigemptyset (&__morestack_initial_sp.mask);
508 
509   sigfillset (&__morestack_fullmask);
510 #if defined(__GLIBC__) && defined(__linux__)
511   /* In glibc, the first two real time signals are used by the NPTL
512      threading library.  By taking them out of the set of signals, we
513      avoiding copying the signal mask in pthread_sigmask.  More
514      importantly, pthread_sigmask uses less stack space on x86_64.  */
515   sigdelset (&__morestack_fullmask, __SIGRTMIN);
516   sigdelset (&__morestack_fullmask, __SIGRTMIN + 1);
517 #endif
518 }
519 
520 /* This function is called by a processor specific function which is
521    run in the prologue when more stack is needed.  The processor
522    specific function handles the details of saving registers and
523    frobbing the actual stack pointer.  This function is responsible
524    for allocating a new stack segment and for copying a parameter
525    block from the old stack to the new one.  On function entry
526    *PFRAME_SIZE is the size of the required stack frame--the returned
527    stack must be at least this large.  On function exit *PFRAME_SIZE
528    is the amount of space remaining on the allocated stack.  OLD_STACK
529    points at the parameters the old stack (really the current one
530    while this function is running).  OLD_STACK is saved so that it can
531    be returned by a later call to __generic_releasestack.  PARAM_SIZE
532    is the size in bytes of parameters to copy to the new stack.  This
533    function returns a pointer to the new stack segment, pointing to
534    the memory after the parameters have been copied.  The returned
535    value minus the returned *PFRAME_SIZE (or plus if the stack grows
536    upward) is the first address on the stack which should not be used.
537 
538    This function is running on the old stack and has only a limited
539    amount of stack space available.  */
540 
541 void *
__generic_morestack(size_t * pframe_size,void * old_stack,size_t param_size)542 __generic_morestack (size_t *pframe_size, void *old_stack, size_t param_size)
543 {
544   size_t frame_size = *pframe_size;
545   struct stack_segment *current;
546   struct stack_segment **pp;
547   struct dynamic_allocation_blocks *dynamic;
548   char *from;
549   char *to;
550   void *ret;
551   size_t i;
552 
553   current = __morestack_current_segment;
554 
555   pp = current != NULL ? &current->next : &__morestack_segments;
556   if (*pp != NULL && (*pp)->size < frame_size)
557     dynamic = __morestack_release_segments (pp, 0);
558   else
559     dynamic = NULL;
560   current = *pp;
561 
562   if (current == NULL)
563     {
564       current = allocate_segment (frame_size + param_size);
565       current->prev = __morestack_current_segment;
566       *pp = current;
567     }
568 
569   current->old_stack = old_stack;
570 
571   __morestack_current_segment = current;
572 
573   if (dynamic != NULL)
574     {
575       /* Move the free blocks onto our list.  We don't want to call
576 	 free here, as we are short on stack space.  */
577       current->free_dynamic_allocation =
578 	merge_dynamic_blocks (dynamic, current->free_dynamic_allocation);
579     }
580 
581   *pframe_size = current->size - param_size;
582 
583 #ifdef STACK_GROWS_DOWNWARD
584   {
585     char *bottom = (char *) (current + 1) + current->size;
586     to = bottom - param_size;
587     ret = bottom - param_size;
588   }
589 #else
590   to = current + 1;
591   ret = (char *) (current + 1) + param_size;
592 #endif
593 
594   /* We don't call memcpy to avoid worrying about the dynamic linker
595      trying to resolve it.  */
596   from = (char *) old_stack;
597   for (i = 0; i < param_size; i++)
598     *to++ = *from++;
599 
600   return ret;
601 }
602 
603 /* This function is called by a processor specific function when it is
604    ready to release a stack segment.  We don't actually release the
605    stack segment, we just move back to the previous one.  The current
606    stack segment will still be available if we need it in
607    __generic_morestack.  This returns a pointer to the new stack
608    segment to use, which is the one saved by a previous call to
609    __generic_morestack.  The processor specific function is then
610    responsible for actually updating the stack pointer.  This sets
611    *PAVAILABLE to the amount of stack space now available.  */
612 
613 void *
__generic_releasestack(size_t * pavailable)614 __generic_releasestack (size_t *pavailable)
615 {
616   struct stack_segment *current;
617   void *old_stack;
618 
619   current = __morestack_current_segment;
620   old_stack = current->old_stack;
621   current = current->prev;
622   __morestack_current_segment = current;
623 
624   if (current != NULL)
625     {
626 #ifdef STACK_GROWS_DOWNWARD
627       *pavailable = (char *) old_stack - (char *) (current + 1);
628 #else
629       *pavailable = (char *) (current + 1) + current->size - (char *) old_stack;
630 #endif
631     }
632   else
633     {
634       size_t used;
635 
636       /* We have popped back to the original stack.  */
637 #ifdef STACK_GROWS_DOWNWARD
638       if ((char *) old_stack >= (char *) __morestack_initial_sp.sp)
639 	used = 0;
640       else
641 	used = (char *) __morestack_initial_sp.sp - (char *) old_stack;
642 #else
643       if ((char *) old_stack <= (char *) __morestack_initial_sp.sp)
644 	used = 0;
645       else
646 	used = (char *) old_stack - (char *) __morestack_initial_sp.sp;
647 #endif
648 
649       if (used > __morestack_initial_sp.len)
650 	*pavailable = 0;
651       else
652 	*pavailable = __morestack_initial_sp.len - used;
653     }
654 
655   return old_stack;
656 }
657 
658 /* Block signals while splitting the stack.  This avoids trouble if we
659    try to invoke a signal handler which itself wants to split the
660    stack.  */
661 
662 extern int pthread_sigmask (int, const sigset_t *, sigset_t *)
663   __attribute__ ((weak));
664 
665 void
__morestack_block_signals(void)666 __morestack_block_signals (void)
667 {
668   if (__morestack_initial_sp.dont_block_signals)
669     ;
670   else if (pthread_sigmask)
671     pthread_sigmask (SIG_BLOCK, &__morestack_fullmask,
672 		     &__morestack_initial_sp.mask);
673   else
674     sigprocmask (SIG_BLOCK, &__morestack_fullmask,
675 		 &__morestack_initial_sp.mask);
676 }
677 
678 /* Unblock signals while splitting the stack.  */
679 
680 void
__morestack_unblock_signals(void)681 __morestack_unblock_signals (void)
682 {
683   if (__morestack_initial_sp.dont_block_signals)
684     ;
685   else if (pthread_sigmask)
686     pthread_sigmask (SIG_SETMASK, &__morestack_initial_sp.mask, NULL);
687   else
688     sigprocmask (SIG_SETMASK, &__morestack_initial_sp.mask, NULL);
689 }
690 
691 /* This function is called to allocate dynamic stack space, for alloca
692    or a variably sized array.  This is a regular function with
693    sufficient stack space, so we just use malloc to allocate the
694    space.  We attach the allocated blocks to the current stack
695    segment, so that they will eventually be reused or freed.  */
696 
697 void *
__morestack_allocate_stack_space(size_t size)698 __morestack_allocate_stack_space (size_t size)
699 {
700   struct stack_segment *seg, *current;
701   struct dynamic_allocation_blocks *p;
702 
703   /* We have to block signals to avoid getting confused if we get
704      interrupted by a signal whose handler itself uses alloca or a
705      variably sized array.  */
706   __morestack_block_signals ();
707 
708   /* Since we don't want to call free while we are low on stack space,
709      we may have a list of already allocated blocks waiting to be
710      freed.  Release them all, unless we find one that is large
711      enough.  We don't look at every block to see if one is large
712      enough, just the first one, because we aren't trying to build a
713      memory allocator here, we're just trying to speed up common
714      cases.  */
715 
716   current = __morestack_current_segment;
717   p = NULL;
718   for (seg = __morestack_segments; seg != NULL; seg = seg->next)
719     {
720       p = seg->free_dynamic_allocation;
721       if (p != NULL)
722 	{
723 	  if (p->size >= size)
724 	    {
725 	      seg->free_dynamic_allocation = p->next;
726 	      break;
727 	    }
728 
729 	  free_dynamic_blocks (p);
730 	  seg->free_dynamic_allocation = NULL;
731 	  p = NULL;
732 	}
733     }
734 
735   if (p == NULL)
736     {
737       /* We need to allocate additional memory.  */
738       p = malloc (sizeof (*p));
739       if (p == NULL)
740 	abort ();
741       p->size = size;
742       p->block = malloc (size);
743       if (p->block == NULL)
744 	abort ();
745     }
746 
747   /* If we are still on the initial stack, then we have a space leak.
748      FIXME.  */
749   if (current != NULL)
750     {
751       p->next = current->dynamic_allocation;
752       current->dynamic_allocation = p;
753     }
754 
755   __morestack_unblock_signals ();
756 
757   return p->block;
758 }
759 
760 /* Find the stack segment for STACK and return the amount of space
761    available.  This is used when unwinding the stack because of an
762    exception, in order to reset the stack guard correctly.  */
763 
764 size_t
__generic_findstack(void * stack)765 __generic_findstack (void *stack)
766 {
767   struct stack_segment *pss;
768   size_t used;
769 
770   for (pss = __morestack_current_segment; pss != NULL; pss = pss->prev)
771     {
772       if ((char *) pss < (char *) stack
773 	  && (char *) pss + pss->size > (char *) stack)
774 	{
775 	  __morestack_current_segment = pss;
776 #ifdef STACK_GROWS_DOWNWARD
777 	  return (char *) stack - (char *) (pss + 1);
778 #else
779 	  return (char *) (pss + 1) + pss->size - (char *) stack;
780 #endif
781 	}
782     }
783 
784   /* We have popped back to the original stack.  */
785 
786   if (__morestack_initial_sp.sp == NULL)
787     return 0;
788 
789 #ifdef STACK_GROWS_DOWNWARD
790   if ((char *) stack >= (char *) __morestack_initial_sp.sp)
791     used = 0;
792   else
793     used = (char *) __morestack_initial_sp.sp - (char *) stack;
794 #else
795   if ((char *) stack <= (char *) __morestack_initial_sp.sp)
796     used = 0;
797   else
798     used = (char *) stack - (char *) __morestack_initial_sp.sp;
799 #endif
800 
801   if (used > __morestack_initial_sp.len)
802     return 0;
803   else
804     return __morestack_initial_sp.len - used;
805 }
806 
807 /* This function is called at program startup time to make sure that
808    mmap, munmap, and getpagesize are resolved if linking dynamically.
809    We want to resolve them while we have enough stack for them, rather
810    than calling into the dynamic linker while low on stack space.  */
811 
812 void
__morestack_load_mmap(void)813 __morestack_load_mmap (void)
814 {
815   /* Call with bogus values to run faster.  We don't care if the call
816      fails.  Pass __MORESTACK_CURRENT_SEGMENT to make sure that any
817      TLS accessor function is resolved.  */
818   mmap (__morestack_current_segment, 0, PROT_READ, MAP_ANONYMOUS, -1, 0);
819   mprotect (NULL, 0, 0);
820   munmap (0, getpagesize ());
821 }
822 
823 /* This function may be used to iterate over the stack segments.
824    This can be called like this.
825      void *next_segment = NULL;
826      void *next_sp = NULL;
827      void *initial_sp = NULL;
828      void *stack;
829      size_t stack_size;
830      while ((stack = __splitstack_find (next_segment, next_sp, &stack_size,
831                                         &next_segment, &next_sp,
832 					&initial_sp)) != NULL)
833        {
834          // Stack segment starts at stack and is stack_size bytes long.
835        }
836 
837    There is no way to iterate over the stack segments of a different
838    thread.  However, what is permitted is for one thread to call this
839    with the first two values NULL, to pass next_segment, next_sp, and
840    initial_sp to a different thread, and then to suspend one way or
841    another.  A different thread may run the subsequent
842    __morestack_find iterations.  Of course, this will only work if the
843    first thread is suspended during the __morestack_find iterations.
844    If not, the second thread will be looking at the stack while it is
845    changing, and anything could happen.
846 
847    FIXME: This should be declared in some header file, but where?  */
848 
849 void *
__splitstack_find(void * segment_arg,void * sp,size_t * len,void ** next_segment,void ** next_sp,void ** initial_sp)850 __splitstack_find (void *segment_arg, void *sp, size_t *len,
851 		   void **next_segment, void **next_sp,
852 		   void **initial_sp)
853 {
854   struct stack_segment *segment;
855   void *ret;
856   char *nsp;
857 
858   if (segment_arg == (void *) (uintptr_type) 1)
859     {
860       char *isp = (char *) *initial_sp;
861 
862       if (isp == NULL)
863 	return NULL;
864 
865       *next_segment = (void *) (uintptr_type) 2;
866       *next_sp = NULL;
867 #ifdef STACK_GROWS_DOWNWARD
868       if ((char *) sp >= isp)
869 	return NULL;
870       *len = (char *) isp - (char *) sp;
871       return sp;
872 #else
873       if ((char *) sp <= (char *) isp)
874 	return NULL;
875       *len = (char *) sp - (char *) isp;
876       return (void *) isp;
877 #endif
878     }
879   else if (segment_arg == (void *) (uintptr_type) 2)
880     return NULL;
881   else if (segment_arg != NULL)
882     segment = (struct stack_segment *) segment_arg;
883   else
884     {
885       *initial_sp = __morestack_initial_sp.sp;
886       segment = __morestack_current_segment;
887       sp = (void *) &segment;
888       while (1)
889 	{
890 	  if (segment == NULL)
891 	    return __splitstack_find ((void *) (uintptr_type) 1, sp, len,
892 				      next_segment, next_sp, initial_sp);
893 	  if ((char *) sp >= (char *) (segment + 1)
894 	      && (char *) sp <= (char *) (segment + 1) + segment->size)
895 	    break;
896 	  segment = segment->prev;
897 	}
898     }
899 
900   if (segment->prev == NULL)
901     *next_segment = (void *) (uintptr_type) 1;
902   else
903     *next_segment = segment->prev;
904 
905   /* The old_stack value is the address of the function parameters of
906      the function which called __morestack.  So if f1 called f2 which
907      called __morestack, the stack looks like this:
908 
909          parameters       <- old_stack
910          return in f1
911 	 return in f2
912 	 registers pushed by __morestack
913 
914      The registers pushed by __morestack may not be visible on any
915      other stack, if we are being called by a signal handler
916      immediately after the call to __morestack_unblock_signals.  We
917      want to adjust our return value to include those registers.  This
918      is target dependent.  */
919 
920   nsp = (char *) segment->old_stack;
921 
922   if (nsp == NULL)
923     {
924       /* We've reached the top of the stack.  */
925       *next_segment = (void *) (uintptr_type) 2;
926     }
927   else
928     {
929 #if defined (__x86_64__)
930       nsp -= 12 * sizeof (void *);
931 #elif defined (__i386__)
932       nsp -= 6 * sizeof (void *);
933 #else
934 #error "unrecognized target"
935 #endif
936 
937       *next_sp = (void *) nsp;
938     }
939 
940 #ifdef STACK_GROWS_DOWNWARD
941   *len = (char *) (segment + 1) + segment->size - (char *) sp;
942   ret = (void *) sp;
943 #else
944   *len = (char *) sp - (char *) (segment + 1);
945   ret = (void *) (segment + 1);
946 #endif
947 
948   return ret;
949 }
950 
951 /* Tell the split stack code whether it has to block signals while
952    manipulating the stack.  This is for programs in which some threads
953    block all signals.  If a thread already blocks signals, there is no
954    need for the split stack code to block them as well.  If NEW is not
955    NULL, then if *NEW is non-zero signals will be blocked while
956    splitting the stack, otherwise they will not.  If OLD is not NULL,
957    *OLD will be set to the old value.  */
958 
959 void
__splitstack_block_signals(int * new,int * old)960 __splitstack_block_signals (int *new, int *old)
961 {
962   if (old != NULL)
963     *old = __morestack_initial_sp.dont_block_signals ? 0 : 1;
964   if (new != NULL)
965     __morestack_initial_sp.dont_block_signals = *new ? 0 : 1;
966 }
967 
968 /* The offsets into the arrays used by __splitstack_getcontext and
969    __splitstack_setcontext.  */
970 
971 enum __splitstack_context_offsets
972 {
973   MORESTACK_SEGMENTS = 0,
974   CURRENT_SEGMENT = 1,
975   CURRENT_STACK = 2,
976   STACK_GUARD = 3,
977   INITIAL_SP = 4,
978   INITIAL_SP_LEN = 5,
979   BLOCK_SIGNALS = 6,
980 
981   NUMBER_OFFSETS = 10
982 };
983 
984 /* Get the current split stack context.  This may be used for
985    coroutine switching, similar to getcontext.  The argument should
986    have at least 10 void *pointers for extensibility, although we
987    don't currently use all of them.  This would normally be called
988    immediately before a call to getcontext or swapcontext or
989    setjmp.  */
990 
991 void
__splitstack_getcontext(void * context[NUMBER_OFFSETS])992 __splitstack_getcontext (void *context[NUMBER_OFFSETS])
993 {
994   memset (context, 0, NUMBER_OFFSETS * sizeof (void *));
995   context[MORESTACK_SEGMENTS] = (void *) __morestack_segments;
996   context[CURRENT_SEGMENT] = (void *) __morestack_current_segment;
997   context[CURRENT_STACK] = (void *) &context;
998   context[STACK_GUARD] = __morestack_get_guard ();
999   context[INITIAL_SP] = (void *) __morestack_initial_sp.sp;
1000   context[INITIAL_SP_LEN] = (void *) (uintptr_type) __morestack_initial_sp.len;
1001   context[BLOCK_SIGNALS] = (void *) __morestack_initial_sp.dont_block_signals;
1002 }
1003 
1004 /* Set the current split stack context.  The argument should be a
1005    context previously passed to __splitstack_getcontext.  This would
1006    normally be called immediately after a call to getcontext or
1007    swapcontext or setjmp if something jumped to it.  */
1008 
1009 void
__splitstack_setcontext(void * context[NUMBER_OFFSETS])1010 __splitstack_setcontext (void *context[NUMBER_OFFSETS])
1011 {
1012   __morestack_segments = (struct stack_segment *) context[MORESTACK_SEGMENTS];
1013   __morestack_current_segment =
1014     (struct stack_segment *) context[CURRENT_SEGMENT];
1015   __morestack_set_guard (context[STACK_GUARD]);
1016   __morestack_initial_sp.sp = context[INITIAL_SP];
1017   __morestack_initial_sp.len = (size_t) context[INITIAL_SP_LEN];
1018   __morestack_initial_sp.dont_block_signals =
1019     (uintptr_type) context[BLOCK_SIGNALS];
1020 }
1021 
1022 /* Create a new split stack context.  This will allocate a new stack
1023    segment which may be used by a coroutine.  STACK_SIZE is the
1024    minimum size of the new stack.  The caller is responsible for
1025    actually setting the stack pointer.  This would normally be called
1026    before a call to makecontext, and the returned stack pointer and
1027    size would be used to set the uc_stack field.  A function called
1028    via makecontext on a stack created by __splitstack_makecontext may
1029    not return.  Note that the returned pointer points to the lowest
1030    address in the stack space, and thus may not be the value to which
1031    to set the stack pointer.  */
1032 
1033 void *
__splitstack_makecontext(size_t stack_size,void * context[NUMBER_OFFSETS],size_t * size)1034 __splitstack_makecontext (size_t stack_size, void *context[NUMBER_OFFSETS],
1035 			  size_t *size)
1036 {
1037   struct stack_segment *segment;
1038   void *initial_sp;
1039 
1040   memset (context, 0, NUMBER_OFFSETS * sizeof (void *));
1041   segment = allocate_segment (stack_size);
1042   context[MORESTACK_SEGMENTS] = segment;
1043   context[CURRENT_SEGMENT] = segment;
1044 #ifdef STACK_GROWS_DOWNWARD
1045   initial_sp = (void *) ((char *) (segment + 1) + segment->size);
1046 #else
1047   initial_sp = (void *) (segment + 1);
1048 #endif
1049   context[STACK_GUARD] = __morestack_make_guard (initial_sp, segment->size);
1050   context[INITIAL_SP] = NULL;
1051   context[INITIAL_SP_LEN] = 0;
1052   *size = segment->size;
1053   return (void *) (segment + 1);
1054 }
1055 
1056 /* Given an existing split stack context, reset it back to the start
1057    of the stack.  Return the stack pointer and size, appropriate for
1058    use with makecontext.  This may be used if a coroutine exits, in
1059    order to reuse the stack segments for a new coroutine.  */
1060 
1061 void *
__splitstack_resetcontext(void * context[10],size_t * size)1062 __splitstack_resetcontext (void *context[10], size_t *size)
1063 {
1064   struct stack_segment *segment;
1065   void *initial_sp;
1066   size_t initial_size;
1067   void *ret;
1068 
1069   /* Reset the context assuming that MORESTACK_SEGMENTS, INITIAL_SP
1070      and INITIAL_SP_LEN are correct.  */
1071 
1072   segment = context[MORESTACK_SEGMENTS];
1073   context[CURRENT_SEGMENT] = segment;
1074   context[CURRENT_STACK] = NULL;
1075   if (segment == NULL)
1076     {
1077       initial_sp = context[INITIAL_SP];
1078       initial_size = (uintptr_type) context[INITIAL_SP_LEN];
1079       ret = initial_sp;
1080 #ifdef STACK_GROWS_DOWNWARD
1081       ret = (void *) ((char *) ret - initial_size);
1082 #endif
1083     }
1084   else
1085     {
1086 #ifdef STACK_GROWS_DOWNWARD
1087       initial_sp = (void *) ((char *) (segment + 1) + segment->size);
1088 #else
1089       initial_sp = (void *) (segment + 1);
1090 #endif
1091       initial_size = segment->size;
1092       ret = (void *) (segment + 1);
1093     }
1094   context[STACK_GUARD] = __morestack_make_guard (initial_sp, initial_size);
1095   context[BLOCK_SIGNALS] = NULL;
1096   *size = initial_size;
1097   return ret;
1098 }
1099 
1100 /* Release all the memory associated with a splitstack context.  This
1101    may be used if a coroutine exits and the associated stack should be
1102    freed.  */
1103 
1104 void
__splitstack_releasecontext(void * context[10])1105 __splitstack_releasecontext (void *context[10])
1106 {
1107   __morestack_release_segments (((struct stack_segment **)
1108 				 &context[MORESTACK_SEGMENTS]),
1109 				1);
1110 }
1111 
1112 /* Like __splitstack_block_signals, but operating on CONTEXT, rather
1113    than on the current state.  */
1114 
1115 void
__splitstack_block_signals_context(void * context[NUMBER_OFFSETS],int * new,int * old)1116 __splitstack_block_signals_context (void *context[NUMBER_OFFSETS], int *new,
1117 				    int *old)
1118 {
1119   if (old != NULL)
1120     *old = ((uintptr_type) context[BLOCK_SIGNALS]) != 0 ? 0 : 1;
1121   if (new != NULL)
1122     context[BLOCK_SIGNALS] = (void *) (uintptr_type) (*new ? 0 : 1);
1123 }
1124 
1125 /* Find the stack segments associated with a split stack context.
1126    This will return the address of the first stack segment and set
1127    *STACK_SIZE to its size.  It will set next_segment, next_sp, and
1128    initial_sp which may be passed to __splitstack_find to find the
1129    remaining segments.  */
1130 
1131 void *
__splitstack_find_context(void * context[NUMBER_OFFSETS],size_t * stack_size,void ** next_segment,void ** next_sp,void ** initial_sp)1132 __splitstack_find_context (void *context[NUMBER_OFFSETS], size_t *stack_size,
1133 			   void **next_segment, void **next_sp,
1134 			   void **initial_sp)
1135 {
1136   void *sp;
1137   struct stack_segment *segment;
1138 
1139   *initial_sp = context[INITIAL_SP];
1140 
1141   sp = context[CURRENT_STACK];
1142   if (sp == NULL)
1143     {
1144       /* Most likely this context was created but was never used.  The
1145 	 value 2 is a code used by __splitstack_find to mean that we
1146 	 have reached the end of the list of stacks.  */
1147       *next_segment = (void *) (uintptr_type) 2;
1148       *next_sp = NULL;
1149       *initial_sp = NULL;
1150       return NULL;
1151     }
1152 
1153   segment = context[CURRENT_SEGMENT];
1154   if (segment == NULL)
1155     {
1156       /* Most likely this context was saved by a thread which was not
1157 	 created using __splistack_makecontext and which has never
1158 	 split the stack.  The value 1 is a code used by
1159 	 __splitstack_find to look at the initial stack.  */
1160       segment = (struct stack_segment *) (uintptr_type) 1;
1161     }
1162 
1163   return __splitstack_find (segment, sp, stack_size, next_segment, next_sp,
1164 			    initial_sp);
1165 }
1166 
1167 #endif /* !defined (inhibit_libc) */
1168