xref: /PHP-8.1/main/alloca.c (revision 462da6e0)
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'd 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 give up.  */
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