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