Back to index

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