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