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