source: trunk/third/diffutils/alloca.c @ 16149

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