Return to alloca.c CVS log

Up to [Apple XNU] / GNUtools / libg++ / libiberty

Annotation of GNUtools/libg++/libiberty/alloca.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.