libiberty/alloca.c

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