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 /* If compiling with GCC 2, this file's not needed. */
25 #if !defined (__GNUC__) || __GNUC__ < 2
26
27 /* If someone has defined alloca as a macro,
28 there must be some other way alloca is supposed to work. */
29 #ifndef alloca
30
31 /* If your stack is a linked list of frames, you have to
32 provide an "address metric" ADDRESS_FUNCTION macro. */
33
34 #if defined (CRAY) && defined (CRAY_STACKSEG_END)
35 long i00afunc ();
36 #define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
37 #else
38 #define ADDRESS_FUNCTION(arg) &(arg)
39 #endif
40
41 typedef void *pointer;
42
43 #define NULL 0
44
45 /* Different portions of Emacs need to call different versions of
46 malloc. The Emacs executable needs alloca to call xmalloc, because
47 ordinary malloc isn't protected from input signals. On the other
48 hand, the utilities in lib-src need alloca to call malloc; some of
49 them are very simple, and don't have an xmalloc routine.
50
51 Non-Emacs programs expect this to call use xmalloc.
52
53 Callers below should use malloc. */
54
55 #define malloc xmalloc
56 extern pointer malloc ();
57
58 /* Define STACK_DIRECTION if you know the direction of stack
59 growth for your system; otherwise it will be automatically
60 deduced at run-time.
61
62 STACK_DIRECTION > 0 => grows toward higher addresses
63 STACK_DIRECTION < 0 => grows toward lower addresses
64 STACK_DIRECTION = 0 => direction of growth unknown */
65
66 #ifndef STACK_DIRECTION
67 #define STACK_DIRECTION 0 /* Direction unknown. */
68 #endif
69
70 #if STACK_DIRECTION != 0
71
72 #define STACK_DIR STACK_DIRECTION /* Known at compile-time. */
73
74 #else /* STACK_DIRECTION == 0; need run-time code. */
75
76 static int stack_dir; /* 1 or -1 once known. */
77 #define STACK_DIR stack_dir
78
79 static void
find_stack_direction()80 find_stack_direction ()
81 {
82 static char *addr = NULL; /* Address of first `dummy', once known. */
83 auto char dummy; /* To get stack address. */
84
85 if (addr == NULL)
86 { /* Initial entry. */
87 addr = ADDRESS_FUNCTION (dummy);
88
89 find_stack_direction (); /* Recurse once. */
90 }
91 else
92 {
93 /* Second entry. */
94 if (ADDRESS_FUNCTION (dummy) > addr)
95 stack_dir = 1; /* Stack grew upward. */
96 else
97 stack_dir = -1; /* Stack grew downward. */
98 }
99 }
100
101 #endif /* STACK_DIRECTION == 0 */
102
103 /* An "alloca header" is used to:
104 (a) chain together all alloca'ed blocks;
105 (b) keep track of stack depth.
106
107 It is very important that sizeof(header) agree with malloc
108 alignment chunk size. The following default should work okay. */
109
110 #ifndef ALIGN_SIZE
111 #define ALIGN_SIZE sizeof(double)
112 #endif
113
114 typedef union hdr
115 {
116 char align[ALIGN_SIZE]; /* To force sizeof(header). */
117 struct
118 {
119 union hdr *next; /* For chaining headers. */
120 char *deep; /* For stack depth measure. */
121 } h;
122 } header;
123
124 static header *last_alloca_header = NULL; /* -> last alloca header. */
125
126 /* Return a pointer to at least SIZE bytes of storage,
127 which will be automatically reclaimed upon exit from
128 the procedure that called alloca. Originally, this space
129 was supposed to be taken from the current stack frame of the
130 caller, but that method cannot be made to work for some
131 implementations of C, for example under Gould's UTX/32. */
132
133 pointer
alloca(size)134 alloca (size)
135 unsigned size;
136 {
137 auto char probe; /* Probes stack depth: */
138 register char *depth = ADDRESS_FUNCTION (probe);
139
140 #if STACK_DIRECTION == 0
141 if (STACK_DIR == 0) /* Unknown growth direction. */
142 find_stack_direction ();
143 #endif
144
145 /* Reclaim garbage, defined as all alloca'd storage that
146 was allocated from deeper in the stack than currently. */
147
148 {
149 register header *hp; /* Traverses linked list. */
150
151 for (hp = last_alloca_header; hp != NULL;)
152 if ((STACK_DIR > 0 && hp->h.deep > depth)
153 || (STACK_DIR < 0 && hp->h.deep < depth))
154 {
155 register header *np = hp->h.next;
156
157 free ((pointer) hp); /* Collect garbage. */
158
159 hp = np; /* -> next header. */
160 }
161 else
162 break; /* Rest are not deeper. */
163
164 last_alloca_header = hp; /* -> last valid storage. */
165 }
166
167 if (size == 0)
168 return NULL; /* No allocation required. */
169
170 /* Allocate combined header + user data storage. */
171
172 {
173 register pointer new = malloc (sizeof (header) + size);
174 /* Address of header. */
175
176 ((header *) new)->h.next = last_alloca_header;
177 ((header *) new)->h.deep = depth;
178
179 last_alloca_header = (header *) new;
180
181 /* User storage begins just after header. */
182
183 return (pointer) ((char *) new + sizeof (header));
184 }
185 }
186
187 #if defined (CRAY) && defined (CRAY_STACKSEG_END)
188
189 #ifdef DEBUG_I00AFUNC
190 #include <stdio.h>
191 #endif
192
193 #ifndef CRAY_STACK
194 #define CRAY_STACK
195 #ifndef CRAY2
196 /* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */
197 struct stack_control_header
198 {
199 long shgrow:32; /* Number of times stack has grown. */
200 long shaseg:32; /* Size of increments to stack. */
201 long shhwm:32; /* High water mark of stack. */
202 long shsize:32; /* Current size of stack (all segments). */
203 };
204
205 /* The stack segment linkage control information occurs at
206 the high-address end of a stack segment. (The stack
207 grows from low addresses to high addresses.) The initial
208 part of the stack segment linkage control information is
209 0200 (octal) words. This provides for register storage
210 for the routine which overflows the stack. */
211
212 struct stack_segment_linkage
213 {
214 long ss[0200]; /* 0200 overflow words. */
215 long sssize:32; /* Number of words in this segment. */
216 long ssbase:32; /* Offset to stack base. */
217 long:32;
218 long sspseg:32; /* Offset to linkage control of previous
219 segment of stack. */
220 long:32;
221 long sstcpt:32; /* Pointer to task common address block. */
222 long sscsnm; /* Private control structure number for
223 microtasking. */
224 long ssusr1; /* Reserved for user. */
225 long ssusr2; /* Reserved for user. */
226 long sstpid; /* Process ID for pid based multi-tasking. */
227 long ssgvup; /* Pointer to multitasking thread giveup. */
228 long sscray[7]; /* Reserved for Cray Research. */
229 long ssa0;
230 long ssa1;
231 long ssa2;
232 long ssa3;
233 long ssa4;
234 long ssa5;
235 long ssa6;
236 long ssa7;
237 long sss0;
238 long sss1;
239 long sss2;
240 long sss3;
241 long sss4;
242 long sss5;
243 long sss6;
244 long sss7;
245 };
246
247 #else /* CRAY2 */
248 /* The following structure defines the vector of words
249 returned by the STKSTAT library routine. */
250 struct stk_stat
251 {
252 long now; /* Current total stack size. */
253 long maxc; /* Amount of contiguous space which would
254 be required to satisfy the maximum
255 stack demand to date. */
256 long high_water; /* Stack high-water mark. */
257 long overflows; /* Number of stack overflow ($STKOFEN) calls. */
258 long hits; /* Number of internal buffer hits. */
259 long extends; /* Number of block extensions. */
260 long stko_mallocs; /* Block allocations by $STKOFEN. */
261 long underflows; /* Number of stack underflow calls ($STKRETN). */
262 long stko_free; /* Number of deallocations by $STKRETN. */
263 long stkm_free; /* Number of deallocations by $STKMRET. */
264 long segments; /* Current number of stack segments. */
265 long maxs; /* Maximum number of stack segments so far. */
266 long pad_size; /* Stack pad size. */
267 long current_address; /* Current stack segment address. */
268 long current_size; /* Current stack segment size. This
269 number is actually corrupted by STKSTAT to
270 include the fifteen word trailer area. */
271 long initial_address; /* Address of initial segment. */
272 long initial_size; /* Size of initial segment. */
273 };
274
275 /* The following structure describes the data structure which trails
276 any stack segment. I think that the description in 'asdef' is
277 out of date. I only describe the parts that I am sure about. */
278
279 struct stk_trailer
280 {
281 long this_address; /* Address of this block. */
282 long this_size; /* Size of this block (does not include
283 this trailer). */
284 long unknown2;
285 long unknown3;
286 long link; /* Address of trailer block of previous
287 segment. */
288 long unknown5;
289 long unknown6;
290 long unknown7;
291 long unknown8;
292 long unknown9;
293 long unknown10;
294 long unknown11;
295 long unknown12;
296 long unknown13;
297 long unknown14;
298 };
299
300 #endif /* CRAY2 */
301 #endif /* not CRAY_STACK */
302
303 #ifdef CRAY2
304 /* Determine a "stack measure" for an arbitrary ADDRESS.
305 I doubt that "lint" will like this much. */
306
307 static long
i00afunc(long * address)308 i00afunc (long *address)
309 {
310 struct stk_stat status;
311 struct stk_trailer *trailer;
312 long *block, size;
313 long result = 0;
314
315 /* We want to iterate through all of the segments. The first
316 step is to get the stack status structure. We could do this
317 more quickly and more directly, perhaps, by referencing the
318 $LM00 common block, but I know that this works. */
319
320 STKSTAT (&status);
321
322 /* Set up the iteration. */
323
324 trailer = (struct stk_trailer *) (status.current_address
325 + status.current_size
326 - 15);
327
328 /* There must be at least one stack segment. Therefore it is
329 a fatal error if "trailer" is null. */
330
331 if (trailer == 0)
332 abort ();
333
334 /* Discard segments that do not contain our argument address. */
335
336 while (trailer != 0)
337 {
338 block = (long *) trailer->this_address;
339 size = trailer->this_size;
340 if (block == 0 || size == 0)
341 abort ();
342 trailer = (struct stk_trailer *) trailer->link;
343 if ((block <= address) && (address < (block + size)))
344 break;
345 }
346
347 /* Set the result to the offset in this segment and add the sizes
348 of all predecessor segments. */
349
350 result = address - block;
351
352 if (trailer == 0)
353 {
354 return result;
355 }
356
357 do
358 {
359 if (trailer->this_size <= 0)
360 abort ();
361 result += trailer->this_size;
362 trailer = (struct stk_trailer *) trailer->link;
363 }
364 while (trailer != 0);
365
366 /* We are done. Note that if you present a bogus address (one
367 not in any segment), you will get a different number back, formed
368 from subtracting the address of the first block. This is probably
369 not what you want. */
370
371 return (result);
372 }
373
374 #else /* not CRAY2 */
375 /* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP.
376 Determine the number of the cell within the stack,
377 given the address of the cell. The purpose of this
378 routine is to linearize, in some sense, stack addresses
379 for alloca. */
380
381 static long
i00afunc(long address)382 i00afunc (long address)
383 {
384 long stkl = 0;
385
386 long size, pseg, this_segment, stack;
387 long result = 0;
388
389 struct stack_segment_linkage *ssptr;
390
391 /* Register B67 contains the address of the end of the
392 current stack segment. If you (as a subprogram) store
393 your registers on the stack and find that you are past
394 the contents of B67, you have overflowed the segment.
395
396 B67 also points to the stack segment linkage control
397 area, which is what we are really interested in. */
398
399 stkl = CRAY_STACKSEG_END ();
400 ssptr = (struct stack_segment_linkage *) stkl;
401
402 /* If one subtracts 'size' from the end of the segment,
403 one has the address of the first word of the segment.
404
405 If this is not the first segment, 'pseg' will be
406 nonzero. */
407
408 pseg = ssptr->sspseg;
409 size = ssptr->sssize;
410
411 this_segment = stkl - size;
412
413 /* It is possible that calling this routine itself caused
414 a stack overflow. Discard stack segments which do not
415 contain the target address. */
416
417 while (!(this_segment <= address && address <= stkl))
418 {
419 #ifdef DEBUG_I00AFUNC
420 fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl);
421 #endif
422 if (pseg == 0)
423 break;
424 stkl = stkl - pseg;
425 ssptr = (struct stack_segment_linkage *) stkl;
426 size = ssptr->sssize;
427 pseg = ssptr->sspseg;
428 this_segment = stkl - size;
429 }
430
431 result = address - this_segment;
432
433 /* If you subtract pseg from the current end of the stack,
434 you get the address of the previous stack segment's end.
435 This seems a little convoluted to me, but I'll bet you save
436 a cycle somewhere. */
437
438 while (pseg != 0)
439 {
440 #ifdef DEBUG_I00AFUNC
441 fprintf (stderr, "%011o %011o\n", pseg, size);
442 #endif
443 stkl = stkl - pseg;
444 ssptr = (struct stack_segment_linkage *) stkl;
445 size = ssptr->sssize;
446 pseg = ssptr->sspseg;
447 result += size;
448 }
449 return (result);
450 }
451
452 #endif /* not CRAY2 */
453 #endif /* CRAY */
454
455 #endif /* no alloca */
456 #endif /* not GCC version 2 */
457