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