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