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 */