Annotation of embedaddon/php/main/alloca.c, revision 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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to alloca.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / main