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