Back to index

tetex-bin  3.0
alloca.c
Go to the documentation of this file.
00001 /* alloca.c -- allocate automatically reclaimed memory
00002    (Mostly) portable public-domain implementation -- D A Gwyn
00003 
00004    This implementation of the PWB library alloca function,
00005    which is used to allocate space off the run-time stack so
00006    that it is automatically reclaimed upon procedure exit,
00007    was inspired by discussions with J. Q. Johnson of Cornell.
00008    J.Otto Tennant <jot@cray.com> contributed the Cray support.
00009 
00010    There are some preprocessor constants that can
00011    be defined when compiling for your specific system, for
00012    improved efficiency; however, the defaults should be okay.
00013 
00014    The general concept of this implementation is to keep
00015    track of all alloca-allocated blocks, and reclaim any
00016    that are found to be deeper in the stack than the current
00017    invocation.  This heuristic does not reclaim storage as
00018    soon as it becomes invalid, but it will do so eventually.
00019 
00020    As a special case, alloca(0) reclaims storage without
00021    allocating any.  It is a good idea to use alloca(0) in
00022    your main control loop, etc. to force garbage collection.  */
00023 
00024 #ifdef HAVE_CONFIG_H
00025 # include <config.h>
00026 #endif
00027 
00028 #include <alloca.h>
00029 
00030 #include <string.h>
00031 #include <stdlib.h>
00032 
00033 #ifdef emacs
00034 # include "lisp.h"
00035 # include "blockinput.h"
00036 # ifdef EMACS_FREE
00037 #  undef free
00038 #  define free EMACS_FREE
00039 # endif
00040 #else
00041 # define memory_full() abort ()
00042 #endif
00043 
00044 /* If compiling with GCC 2, this file's not needed.  */
00045 #if !defined (__GNUC__) || __GNUC__ < 2
00046 
00047 /* If someone has defined alloca as a macro,
00048    there must be some other way alloca is supposed to work.  */
00049 # ifndef alloca
00050 
00051 #  ifdef emacs
00052 #   ifdef static
00053 /* actually, only want this if static is defined as ""
00054    -- this is for usg, in which emacs must undefine static
00055    in order to make unexec workable
00056    */
00057 #    ifndef STACK_DIRECTION
00058 you
00059 lose
00060 -- must know STACK_DIRECTION at compile-time
00061 /* Using #error here is not wise since this file should work for
00062    old and obscure compilers.  */
00063 #    endif /* STACK_DIRECTION undefined */
00064 #   endif /* static */
00065 #  endif /* emacs */
00066 
00067 /* If your stack is a linked list of frames, you have to
00068    provide an "address metric" ADDRESS_FUNCTION macro.  */
00069 
00070 #  if defined (CRAY) && defined (CRAY_STACKSEG_END)
00071 long i00afunc ();
00072 #   define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
00073 #  else
00074 #   define ADDRESS_FUNCTION(arg) &(arg)
00075 #  endif
00076 
00077 /* Define STACK_DIRECTION if you know the direction of stack
00078    growth for your system; otherwise it will be automatically
00079    deduced at run-time.
00080 
00081    STACK_DIRECTION > 0 => grows toward higher addresses
00082    STACK_DIRECTION < 0 => grows toward lower addresses
00083    STACK_DIRECTION = 0 => direction of growth unknown  */
00084 
00085 #  ifndef STACK_DIRECTION
00086 #   define STACK_DIRECTION  0      /* Direction unknown.  */
00087 #  endif
00088 
00089 #  if STACK_DIRECTION != 0
00090 
00091 #   define STACK_DIR STACK_DIRECTION      /* Known at compile-time.  */
00092 
00093 #  else /* STACK_DIRECTION == 0; need run-time code.  */
00094 
00095 static int stack_dir;              /* 1 or -1 once known.  */
00096 #   define STACK_DIR stack_dir
00097 
00098 static void
00099 find_stack_direction (void)
00100 {
00101   static char *addr = NULL; /* Address of first `dummy', once known.  */
00102   auto char dummy;          /* To get stack address.  */
00103 
00104   if (addr == NULL)
00105     {                       /* Initial entry.  */
00106       addr = ADDRESS_FUNCTION (dummy);
00107 
00108       find_stack_direction ();     /* Recurse once.  */
00109     }
00110   else
00111     {
00112       /* Second entry.  */
00113       if (ADDRESS_FUNCTION (dummy) > addr)
00114        stack_dir = 1;              /* Stack grew upward.  */
00115       else
00116        stack_dir = -1;             /* Stack grew downward.  */
00117     }
00118 }
00119 
00120 #  endif /* STACK_DIRECTION == 0 */
00121 
00122 /* An "alloca header" is used to:
00123    (a) chain together all alloca'ed blocks;
00124    (b) keep track of stack depth.
00125 
00126    It is very important that sizeof(header) agree with malloc
00127    alignment chunk size.  The following default should work okay.  */
00128 
00129 #  ifndef     ALIGN_SIZE
00130 #   define ALIGN_SIZE       sizeof(double)
00131 #  endif
00132 
00133 typedef union hdr
00134 {
00135   char align[ALIGN_SIZE];   /* To force sizeof(header).  */
00136   struct
00137     {
00138       union hdr *next;             /* For chaining headers.  */
00139       char *deep;           /* For stack depth measure.  */
00140     } h;
00141 } header;
00142 
00143 static header *last_alloca_header = NULL; /* -> last alloca header.  */
00144 
00145 /* Return a pointer to at least SIZE bytes of storage,
00146    which will be automatically reclaimed upon exit from
00147    the procedure that called alloca.  Originally, this space
00148    was supposed to be taken from the current stack frame of the
00149    caller, but that method cannot be made to work for some
00150    implementations of C, for example under Gould's UTX/32.  */
00151 
00152 void *
00153 alloca (size_t size)
00154 {
00155   auto char probe;          /* Probes stack depth: */
00156   register char *depth = ADDRESS_FUNCTION (probe);
00157 
00158 #  if STACK_DIRECTION == 0
00159   if (STACK_DIR == 0)              /* Unknown growth direction.  */
00160     find_stack_direction ();
00161 #  endif
00162 
00163   /* Reclaim garbage, defined as all alloca'd storage that
00164      was allocated from deeper in the stack than currently.  */
00165 
00166   {
00167     register header *hp;    /* Traverses linked list.  */
00168 
00169 #  ifdef emacs
00170     BLOCK_INPUT;
00171 #  endif
00172 
00173     for (hp = last_alloca_header; hp != NULL;)
00174       if ((STACK_DIR > 0 && hp->h.deep > depth)
00175          || (STACK_DIR < 0 && hp->h.deep < depth))
00176        {
00177          register header *np = hp->h.next;
00178 
00179          free (hp);         /* Collect garbage.  */
00180 
00181          hp = np;           /* -> next header.  */
00182        }
00183       else
00184        break;               /* Rest are not deeper.  */
00185 
00186     last_alloca_header = hp;       /* -> last valid storage.  */
00187 
00188 #  ifdef emacs
00189     UNBLOCK_INPUT;
00190 #  endif
00191   }
00192 
00193   if (size == 0)
00194     return NULL;            /* No allocation required.  */
00195 
00196   /* Allocate combined header + user data storage.  */
00197 
00198   {
00199     /* Address of header.  */
00200     register header *new;
00201 
00202     size_t combined_size = sizeof (header) + size;
00203     if (combined_size < sizeof (header))
00204       memory_full ();
00205 
00206     new = malloc (combined_size);
00207 
00208     if (! new)
00209       memory_full ();
00210 
00211     new->h.next = last_alloca_header;
00212     new->h.deep = depth;
00213 
00214     last_alloca_header = new;
00215 
00216     /* User storage begins just after header.  */
00217 
00218     return (void *) (new + 1);
00219   }
00220 }
00221 
00222 #  if defined (CRAY) && defined (CRAY_STACKSEG_END)
00223 
00224 #   ifdef DEBUG_I00AFUNC
00225 #    include <stdio.h>
00226 #   endif
00227 
00228 #   ifndef CRAY_STACK
00229 #    define CRAY_STACK
00230 #    ifndef CRAY2
00231 /* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */
00232 struct stack_control_header
00233   {
00234     long shgrow:32;         /* Number of times stack has grown.  */
00235     long shaseg:32;         /* Size of increments to stack.  */
00236     long shhwm:32;          /* High water mark of stack.  */
00237     long shsize:32;         /* Current size of stack (all segments).  */
00238   };
00239 
00240 /* The stack segment linkage control information occurs at
00241    the high-address end of a stack segment.  (The stack
00242    grows from low addresses to high addresses.)  The initial
00243    part of the stack segment linkage control information is
00244    0200 (octal) words.  This provides for register storage
00245    for the routine which overflows the stack.  */
00246 
00247 struct stack_segment_linkage
00248   {
00249     long ss[0200];          /* 0200 overflow words.  */
00250     long sssize:32;         /* Number of words in this segment.  */
00251     long ssbase:32;         /* Offset to stack base.  */
00252     long:32;
00253     long sspseg:32;         /* Offset to linkage control of previous
00254                                segment of stack.  */
00255     long:32;
00256     long sstcpt:32;         /* Pointer to task common address block.  */
00257     long sscsnm;            /* Private control structure number for
00258                                microtasking.  */
00259     long ssusr1;            /* Reserved for user.  */
00260     long ssusr2;            /* Reserved for user.  */
00261     long sstpid;            /* Process ID for pid based multi-tasking.  */
00262     long ssgvup;            /* Pointer to multitasking thread giveup.  */
00263     long sscray[7];         /* Reserved for Cray Research.  */
00264     long ssa0;
00265     long ssa1;
00266     long ssa2;
00267     long ssa3;
00268     long ssa4;
00269     long ssa5;
00270     long ssa6;
00271     long ssa7;
00272     long sss0;
00273     long sss1;
00274     long sss2;
00275     long sss3;
00276     long sss4;
00277     long sss5;
00278     long sss6;
00279     long sss7;
00280   };
00281 
00282 #    else /* CRAY2 */
00283 /* The following structure defines the vector of words
00284    returned by the STKSTAT library routine.  */
00285 struct stk_stat
00286   {
00287     long now;               /* Current total stack size.  */
00288     long maxc;                     /* Amount of contiguous space which would
00289                                be required to satisfy the maximum
00290                                stack demand to date.  */
00291     long high_water;        /* Stack high-water mark.  */
00292     long overflows;         /* Number of stack overflow ($STKOFEN) calls.  */
00293     long hits;                     /* Number of internal buffer hits.  */
00294     long extends;           /* Number of block extensions.  */
00295     long stko_mallocs;             /* Block allocations by $STKOFEN.  */
00296     long underflows;        /* Number of stack underflow calls ($STKRETN).  */
00297     long stko_free;         /* Number of deallocations by $STKRETN.  */
00298     long stkm_free;         /* Number of deallocations by $STKMRET.  */
00299     long segments;          /* Current number of stack segments.  */
00300     long maxs;                     /* Maximum number of stack segments so far.  */
00301     long pad_size;          /* Stack pad size.  */
00302     long current_address;   /* Current stack segment address.  */
00303     long current_size;             /* Current stack segment size.  This
00304                                number is actually corrupted by STKSTAT to
00305                                include the fifteen word trailer area.  */
00306     long initial_address;   /* Address of initial segment.  */
00307     long initial_size;             /* Size of initial segment.  */
00308   };
00309 
00310 /* The following structure describes the data structure which trails
00311    any stack segment.  I think that the description in 'asdef' is
00312    out of date.  I only describe the parts that I am sure about.  */
00313 
00314 struct stk_trailer
00315   {
00316     long this_address;             /* Address of this block.  */
00317     long this_size;         /* Size of this block (does not include
00318                                this trailer).  */
00319     long unknown2;
00320     long unknown3;
00321     long link;                     /* Address of trailer block of previous
00322                                segment.  */
00323     long unknown5;
00324     long unknown6;
00325     long unknown7;
00326     long unknown8;
00327     long unknown9;
00328     long unknown10;
00329     long unknown11;
00330     long unknown12;
00331     long unknown13;
00332     long unknown14;
00333   };
00334 
00335 #    endif /* CRAY2 */
00336 #   endif /* not CRAY_STACK */
00337 
00338 #   ifdef CRAY2
00339 /* Determine a "stack measure" for an arbitrary ADDRESS.
00340    I doubt that "lint" will like this much.  */
00341 
00342 static long
00343 i00afunc (long *address)
00344 {
00345   struct stk_stat status;
00346   struct stk_trailer *trailer;
00347   long *block, size;
00348   long result = 0;
00349 
00350   /* We want to iterate through all of the segments.  The first
00351      step is to get the stack status structure.  We could do this
00352      more quickly and more directly, perhaps, by referencing the
00353      $LM00 common block, but I know that this works.  */
00354 
00355   STKSTAT (&status);
00356 
00357   /* Set up the iteration.  */
00358 
00359   trailer = (struct stk_trailer *) (status.current_address
00360                                 + status.current_size
00361                                 - 15);
00362 
00363   /* There must be at least one stack segment.  Therefore it is
00364      a fatal error if "trailer" is null.  */
00365 
00366   if (trailer == 0)
00367     abort ();
00368 
00369   /* Discard segments that do not contain our argument address.  */
00370 
00371   while (trailer != 0)
00372     {
00373       block = (long *) trailer->this_address;
00374       size = trailer->this_size;
00375       if (block == 0 || size == 0)
00376        abort ();
00377       trailer = (struct stk_trailer *) trailer->link;
00378       if ((block <= address) && (address < (block + size)))
00379        break;
00380     }
00381 
00382   /* Set the result to the offset in this segment and add the sizes
00383      of all predecessor segments.  */
00384 
00385   result = address - block;
00386 
00387   if (trailer == 0)
00388     {
00389       return result;
00390     }
00391 
00392   do
00393     {
00394       if (trailer->this_size <= 0)
00395        abort ();
00396       result += trailer->this_size;
00397       trailer = (struct stk_trailer *) trailer->link;
00398     }
00399   while (trailer != 0);
00400 
00401   /* We are done.  Note that if you present a bogus address (one
00402      not in any segment), you will get a different number back, formed
00403      from subtracting the address of the first block.  This is probably
00404      not what you want.  */
00405 
00406   return (result);
00407 }
00408 
00409 #   else /* not CRAY2 */
00410 /* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP.
00411    Determine the number of the cell within the stack,
00412    given the address of the cell.  The purpose of this
00413    routine is to linearize, in some sense, stack addresses
00414    for alloca.  */
00415 
00416 static long
00417 i00afunc (long address)
00418 {
00419   long stkl = 0;
00420 
00421   long size, pseg, this_segment, stack;
00422   long result = 0;
00423 
00424   struct stack_segment_linkage *ssptr;
00425 
00426   /* Register B67 contains the address of the end of the
00427      current stack segment.  If you (as a subprogram) store
00428      your registers on the stack and find that you are past
00429      the contents of B67, you have overflowed the segment.
00430 
00431      B67 also points to the stack segment linkage control
00432      area, which is what we are really interested in.  */
00433 
00434   stkl = CRAY_STACKSEG_END ();
00435   ssptr = (struct stack_segment_linkage *) stkl;
00436 
00437   /* If one subtracts 'size' from the end of the segment,
00438      one has the address of the first word of the segment.
00439 
00440      If this is not the first segment, 'pseg' will be
00441      nonzero.  */
00442 
00443   pseg = ssptr->sspseg;
00444   size = ssptr->sssize;
00445 
00446   this_segment = stkl - size;
00447 
00448   /* It is possible that calling this routine itself caused
00449      a stack overflow.  Discard stack segments which do not
00450      contain the target address.  */
00451 
00452   while (!(this_segment <= address && address <= stkl))
00453     {
00454 #    ifdef DEBUG_I00AFUNC
00455       fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl);
00456 #    endif
00457       if (pseg == 0)
00458        break;
00459       stkl = stkl - pseg;
00460       ssptr = (struct stack_segment_linkage *) stkl;
00461       size = ssptr->sssize;
00462       pseg = ssptr->sspseg;
00463       this_segment = stkl - size;
00464     }
00465 
00466   result = address - this_segment;
00467 
00468   /* If you subtract pseg from the current end of the stack,
00469      you get the address of the previous stack segment's end.
00470      This seems a little convoluted to me, but I'll bet you save
00471      a cycle somewhere.  */
00472 
00473   while (pseg != 0)
00474     {
00475 #    ifdef DEBUG_I00AFUNC
00476       fprintf (stderr, "%011o %011o\n", pseg, size);
00477 #    endif
00478       stkl = stkl - pseg;
00479       ssptr = (struct stack_segment_linkage *) stkl;
00480       size = ssptr->sssize;
00481       pseg = ssptr->sspseg;
00482       result += size;
00483     }
00484   return (result);
00485 }
00486 
00487 #   endif /* not CRAY2 */
00488 #  endif /* CRAY */
00489 
00490 # endif /* no alloca */
00491 #endif /* not GCC version 2 */