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