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