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