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
58 you
59 lose
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
85 static int stack_dir; /* 1 or -1 once known. */
86 # define STACK_DIR stack_dir
87
88 static int
89 find_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
112 typedef 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
122 static 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
131 void *
alloca(size_t size)132 alloca (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