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