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