Annotation of embedaddon/php/main/alloca.c, revision 1.1.1.1

1.1       misho       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 <jot@cray.com> 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: /* $Id: alloca.c 242949 2007-09-26 15:44:16Z cvs2svn $ */
                     25: 
                     26: #include <php_config.h>
                     27: 
                     28: #if !HAVE_ALLOCA
                     29: 
                     30: #ifdef HAVE_STRING_H
                     31: #include <string.h>
                     32: #endif
                     33: #ifdef HAVE_STDLIB_H
                     34: #include <stdlib.h>
                     35: #endif
                     36: 
                     37: #ifdef emacs
                     38: #include "blockinput.h"
                     39: #endif
                     40: 
                     41: /* If compiling with GCC 2, this file's not needed.  */
                     42: #if !defined (__GNUC__) || __GNUC__ < 2
                     43: 
                     44: /* If someone has defined alloca as a macro,
                     45:    there must be some other way alloca is supposed to work.  */
                     46: #ifndef alloca
                     47: 
                     48: #ifdef emacs
                     49: #ifdef static
                     50: /* actually, only want this if static is defined as ""
                     51:    -- this is for usg, in which emacs must undefine static
                     52:    in order to make unexec workable
                     53:    */
                     54: #ifndef STACK_DIRECTION
                     55: you
                     56: lose
                     57: -- must know STACK_DIRECTION at compile-time
                     58: #endif /* STACK_DIRECTION undefined */
                     59: #endif /* static */
                     60: #endif /* emacs */
                     61: 
                     62: /* If your stack is a linked list of frames, you have to
                     63:    provide an "address metric" ADDRESS_FUNCTION macro.  */
                     64: 
                     65: #if defined (CRAY) && defined (CRAY_STACKSEG_END)
                     66: long i00afunc ();
                     67: #define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
                     68: #else
                     69: #define ADDRESS_FUNCTION(arg) &(arg)
                     70: #endif
                     71: 
                     72: #if __STDC__
                     73: typedef void *pointer;
                     74: #else
                     75: typedef char *pointer;
                     76: #endif
                     77: 
                     78: #ifndef NULL
                     79: #define        NULL    0
                     80: #endif
                     81: 
                     82: /* Define STACK_DIRECTION if you know the direction of stack
                     83:    growth for your system; otherwise it will be automatically
                     84:    deduced at run-time.
                     85: 
                     86:    STACK_DIRECTION > 0 => grows toward higher addresses
                     87:    STACK_DIRECTION < 0 => grows toward lower addresses
                     88:    STACK_DIRECTION = 0 => direction of growth unknown  */
                     89: 
                     90: #ifndef STACK_DIRECTION
                     91: #define        STACK_DIRECTION 0       /* Direction unknown.  */
                     92: #endif
                     93: 
                     94: #if STACK_DIRECTION != 0
                     95: 
                     96: #define        STACK_DIR       STACK_DIRECTION /* Known at compile-time.  */
                     97: 
                     98: #else /* STACK_DIRECTION == 0; need run-time code.  */
                     99: 
                    100: static int stack_dir;          /* 1 or -1 once known.  */
                    101: #define        STACK_DIR       stack_dir
                    102: 
                    103: static void
                    104: find_stack_direction ()
                    105: {
                    106:   static char *addr = NULL;    /* Address of first `dummy', once known.  */
                    107:   auto char dummy;             /* To get stack address.  */
                    108: 
                    109:   if (addr == NULL)
                    110:     {                          /* Initial entry.  */
                    111:       addr = ADDRESS_FUNCTION (dummy);
                    112: 
                    113:       find_stack_direction (); /* Recurse once.  */
                    114:     }
                    115:   else
                    116:     {
                    117:       /* Second entry.  */
                    118:       if (ADDRESS_FUNCTION (dummy) > addr)
                    119:        stack_dir = 1;          /* Stack grew upward.  */
                    120:       else
                    121:        stack_dir = -1;         /* Stack grew downward.  */
                    122:     }
                    123: }
                    124: 
                    125: #endif /* STACK_DIRECTION == 0 */
                    126: 
                    127: /* An "alloca header" is used to:
                    128:    (a) chain together all alloca'ed blocks;
                    129:    (b) keep track of stack depth.
                    130: 
                    131:    It is very important that sizeof(header) agree with malloc
                    132:    alignment chunk size.  The following default should work okay.  */
                    133: 
                    134: #ifndef        ALIGN_SIZE
                    135: #define        ALIGN_SIZE      sizeof(double)
                    136: #endif
                    137: 
                    138: typedef union hdr
                    139: {
                    140:   char align[ALIGN_SIZE];      /* To force sizeof(header).  */
                    141:   struct
                    142:     {
                    143:       union hdr *next;         /* For chaining headers.  */
                    144:       char *deep;              /* For stack depth measure.  */
                    145:     } h;
                    146: } header;
                    147: 
                    148: static header *last_alloca_header = NULL;      /* -> last alloca header.  */
                    149: 
                    150: /* Return a pointer to at least SIZE bytes of storage,
                    151:    which will be automatically reclaimed upon exit from
                    152:    the procedure that called alloca.  Originally, this space
                    153:    was supposed to be taken from the current stack frame of the
                    154:    caller, but that method cannot be made to work for some
                    155:    implementations of C, for example under Gould's UTX/32.  */
                    156: 
                    157: pointer
                    158: alloca (size)
                    159:      size_t size;
                    160: {
                    161:   auto char probe;             /* Probes stack depth: */
                    162:   register char *depth = ADDRESS_FUNCTION (probe);
                    163: 
                    164: #if STACK_DIRECTION == 0
                    165:   if (STACK_DIR == 0)          /* Unknown growth direction.  */
                    166:     find_stack_direction ();
                    167: #endif
                    168: 
                    169:   /* Reclaim garbage, defined as all alloca'd storage that
                    170:      was allocated from deeper in the stack than currently. */
                    171: 
                    172:   {
                    173:     register header *hp;       /* Traverses linked list.  */
                    174: 
                    175: #ifdef emacs
                    176:     BLOCK_INPUT;
                    177: #endif
                    178: 
                    179:     for (hp = last_alloca_header; hp != NULL;)
                    180:       if ((STACK_DIR > 0 && hp->h.deep > depth)
                    181:          || (STACK_DIR < 0 && hp->h.deep < depth))
                    182:        {
                    183:          register header *np = hp->h.next;
                    184: 
                    185:          free ((pointer) hp);  /* Collect garbage.  */
                    186: 
                    187:          hp = np;              /* -> next header.  */
                    188:        }
                    189:       else
                    190:        break;                  /* Rest are not deeper.  */
                    191: 
                    192:     last_alloca_header = hp;   /* -> last valid storage.  */
                    193: 
                    194: #ifdef emacs
                    195:     UNBLOCK_INPUT;
                    196: #endif
                    197:   }
                    198: 
                    199:   if (size == 0)
                    200:     return NULL;               /* No allocation required.  */
                    201: 
                    202:   /* Allocate combined header + user data storage.  */
                    203: 
                    204:   {
                    205:     register pointer new = malloc (sizeof (header) + size);
                    206:     /* Address of header.  */
                    207: 
                    208:     if (new == 0)
                    209:       abort();
                    210: 
                    211:     ((header *) new)->h.next = last_alloca_header;
                    212:     ((header *) new)->h.deep = depth;
                    213: 
                    214:     last_alloca_header = (header *) new;
                    215: 
                    216:     /* User storage begins just after header.  */
                    217: 
                    218:     return (pointer) ((char *) new + sizeof (header));
                    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 2 */
                    492: #endif /* HAVE_ALLOCA */
                    493: 
                    494: /*
                    495:  * Local variables:
                    496:  * tab-width: 4
                    497:  * c-basic-offset: 4
                    498:  * End:
                    499:  * vim600: sw=4 ts=4 fdm=marker
                    500:  * vim<600: sw=4 ts=4
                    501:  */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>