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