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