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