1/* alloca.c -- allocate automatically reclaimed memory
2   This file is in the public domain.  */
3
4/* (Mostly) portable implementation -- D A Gwyn
5
6   This implementation of the PWB library alloca function,
7   which is used to allocate space off the run-time stack so
8   that it is automatically reclaimed upon procedure exit,
9   was inspired by discussions with J. Q. Johnson of Cornell.
10   J.Otto Tennant <jot@cray.com> contributed the Cray support.
11
12   There are some preprocessor constants that can
13   be defined when compiling for your specific system, for
14   improved efficiency; however, the defaults should be okay.
15
16   The general concept of this implementation is to keep
17   track of all alloca-allocated blocks, and reclaim any
18   that are found to be deeper in the stack than the current
19   invocation.  This heuristic does not reclaim storage as
20   soon as it becomes invalid, but it will do so eventually.
21
22   As a special case, alloca(0) reclaims storage without
23   allocating any.  It is a good idea to use alloca(0) in
24   your main control loop, etc. to force garbage collection.  */
25
26#include <config.h>
27
28#include <alloca.h>
29
30#include <string.h>
31#include <stdlib.h>
32
33#ifdef emacs
34# include "lisp.h"
35# include "blockinput.h"
36# ifdef EMACS_FREE
37#  undef free
38#  define free EMACS_FREE
39# endif
40#else
41# define memory_full() abort ()
42#endif
43
44/* If compiling with GCC or clang, this file is not needed.  */
45#if !(defined __GNUC__ || defined __clang__)
46
47/* If someone has defined alloca as a macro,
48   there must be some other way alloca is supposed to work.  */
49# ifndef alloca
50
51#  ifdef emacs
52#   ifdef static
53/* actually, only want this if static is defined as ""
54   -- this is for usg, in which emacs must undefine static
55   in order to make unexec workable
56   */
57#    ifndef STACK_DIRECTION
58you
59lose
60-- must know STACK_DIRECTION at compile-time
61/* Using #error here is not wise since this file should work for
62   old and obscure compilers.  */
63#    endif /* STACK_DIRECTION undefined */
64#   endif /* static */
65#  endif /* emacs */
66
67/* Define STACK_DIRECTION if you know the direction of stack
68   growth for your system; otherwise it will be automatically
69   deduced at run-time.
70
71   STACK_DIRECTION > 0 => grows toward higher addresses
72   STACK_DIRECTION < 0 => grows toward lower addresses
73   STACK_DIRECTION = 0 => direction of growth unknown  */
74
75#  ifndef STACK_DIRECTION
76#   define STACK_DIRECTION      0       /* Direction unknown.  */
77#  endif
78
79#  if STACK_DIRECTION != 0
80
81#   define STACK_DIR    STACK_DIRECTION /* Known at compile-time.  */
82
83#  else /* STACK_DIRECTION == 0; need run-time code.  */
84
85static int stack_dir;           /* 1 or -1 once known.  */
86#   define STACK_DIR    stack_dir
87
88static int
89find_stack_direction (int *addr, int depth)
90{
91  int dir, dummy = 0;
92  if (! addr)
93    addr = &dummy;
94  *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
95  dir = depth ? find_stack_direction (addr, depth - 1) : 0;
96  return dir + dummy;
97}
98
99#  endif /* STACK_DIRECTION == 0 */
100
101/* An "alloca header" is used to:
102   (a) chain together all alloca'ed blocks;
103   (b) keep track of stack depth.
104
105   It is very important that sizeof(header) agree with malloc
106   alignment chunk size.  The following default should work okay.  */
107
108#  ifndef       ALIGN_SIZE
109#   define ALIGN_SIZE   sizeof(double)
110#  endif
111
112typedef union hdr
113{
114  char align[ALIGN_SIZE];       /* To force sizeof(header).  */
115  struct
116    {
117      union hdr *next;          /* For chaining headers.  */
118      char *deep;               /* For stack depth measure.  */
119    } h;
120} header;
121
122static header *last_alloca_header = NULL;       /* -> last alloca header.  */
123
124/* Return a pointer to at least SIZE bytes of storage,
125   which will be automatically reclaimed upon exit from
126   the procedure that called alloca.  Originally, this space
127   was supposed to be taken from the current stack frame of the
128   caller, but that method cannot be made to work for some
129   implementations of C, for example under Gould's UTX/32.  */
130
131void *
132alloca (size_t size)
133{
134  auto char probe;              /* Probes stack depth: */
135  register char *depth = &probe;
136
137#  if STACK_DIRECTION == 0
138  if (STACK_DIR == 0)           /* Unknown growth direction.  */
139    STACK_DIR = find_stack_direction (NULL, (size & 1) + 20);
140#  endif
141
142  /* Reclaim garbage, defined as all alloca'd storage that
143     was allocated from deeper in the stack than currently.  */
144
145  {
146    register header *hp;        /* Traverses linked list.  */
147
148#  ifdef emacs
149    BLOCK_INPUT;
150#  endif
151
152    for (hp = last_alloca_header; hp != NULL;)
153      if ((STACK_DIR > 0 && hp->h.deep > depth)
154          || (STACK_DIR < 0 && hp->h.deep < depth))
155        {
156          register header *np = hp->h.next;
157
158          free (hp);            /* Collect garbage.  */
159
160          hp = np;              /* -> next header.  */
161        }
162      else
163        break;                  /* Rest are not deeper.  */
164
165    last_alloca_header = hp;    /* -> last valid storage.  */
166
167#  ifdef emacs
168    UNBLOCK_INPUT;
169#  endif
170  }
171
172  if (size == 0)
173    return NULL;                /* No allocation required.  */
174
175  /* Allocate combined header + user data storage.  */
176
177  {
178    /* Address of header.  */
179    register header *new;
180
181    size_t combined_size = sizeof (header) + size;
182    if (combined_size < sizeof (header))
183      memory_full ();
184
185    new = malloc (combined_size);
186
187    if (! new)
188      memory_full ();
189
190    new->h.next = last_alloca_header;
191    new->h.deep = depth;
192
193    last_alloca_header = new;
194
195    /* User storage begins just after header.  */
196
197    return (void *) (new + 1);
198  }
199}
200
201# endif /* no alloca */
202#endif /* not GCC || clang */
203