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