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