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
55you
56lose
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)
66long i00afunc ();
67#define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
68#else
69#define ADDRESS_FUNCTION(arg) &(arg)
70#endif
71
72#if __STDC__
73typedef void *pointer;
74#else
75typedef 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
100static int stack_dir;       /* 1 or -1 once known.  */
101#define STACK_DIR   stack_dir
102
103static void
104find_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
138typedef 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
148static 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
157pointer
158alloca (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 */
232struct 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
247struct 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.  */
285struct 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
314struct 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
342static long
343i00afunc (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
416static long
417i00afunc (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