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