![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloca.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to alloca.c CVS log | Up to [GCC 2.x] / gcc |
1.1.1.4 ! root 1: /* alloca.c -- allocate automatically reclaimed memory ! 2: (Mostly) portable public-domain implementation -- D A Gwyn 1.1 root 3: 1.1.1.4 ! root 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. */ 1.1 root 23: 1.1.1.3 root 24: #ifdef HAVE_CONFIG_H 1.1 root 25: #include "config.h" 1.1.1.3 root 26: #endif 27: 1.1.1.4 ! root 28: /* If compiling with GCC, this file's not needed. */ ! 29: #ifndef alloca ! 30: 1.1.1.3 root 31: #ifdef emacs 1.1 root 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 */ 1.1.1.2 root 42: #endif /* static */ 43: #endif /* emacs */ 1.1 root 44: 1.1.1.4 ! root 45: /* If your stack is a linked list of frames, you have to ! 46: provide an "address metric" ADDRESS_FUNCTION macro. */ ! 47: ! 48: #ifdef CRAY ! 49: long i00afunc (); ! 50: #define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg)) ! 51: #else ! 52: #define ADDRESS_FUNCTION(arg) &(arg) ! 53: #endif 1.1 root 54: 1.1.1.4 ! root 55: #if __STDC__ ! 56: typedef void *pointer; 1.1 root 57: #else 1.1.1.4 ! root 58: typedef char *pointer; 1.1 root 59: #endif 60: 1.1.1.4 ! root 61: #define NULL 0 1.1 root 62: 1.1.1.4 ! root 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. 1.1 root 68: 1.1.1.4 ! root 69: Non-Emacs programs expect this to call use xmalloc. 1.1 root 70: 1.1.1.4 ! root 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 */ 1.1 root 85: 86: #ifndef STACK_DIRECTION 1.1.1.4 ! root 87: #define STACK_DIRECTION 0 /* Direction unknown. */ 1.1 root 88: #endif 89: 90: #if STACK_DIRECTION != 0 91: 1.1.1.4 ! root 92: #define STACK_DIR STACK_DIRECTION /* Known at compile-time. */ 1.1 root 93: 1.1.1.4 ! root 94: #else /* STACK_DIRECTION == 0; need run-time code. */ 1.1 root 95: 1.1.1.4 ! root 96: static int stack_dir; /* 1 or -1 once known. */ 1.1 root 97: #define STACK_DIR stack_dir 98: 99: static void 1.1.1.4 ! root 100: find_stack_direction () 1.1 root 101: { 1.1.1.4 ! root 102: static char *addr = NULL; /* Address of first `dummy', once known. */ ! 103: auto char dummy; /* To get stack address. */ 1.1 root 104: 105: if (addr == NULL) 1.1.1.4 ! root 106: { /* Initial entry. */ ! 107: addr = ADDRESS_FUNCTION (dummy); 1.1 root 108: 1.1.1.4 ! root 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. */ 1.1 root 118: } 119: } 120: 1.1.1.4 ! root 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. 1.1 root 126: 1.1.1.4 ! root 127: It is very important that sizeof(header) agree with malloc ! 128: alignment chunk size. The following default should work okay. */ 1.1 root 129: 130: #ifndef ALIGN_SIZE 131: #define ALIGN_SIZE sizeof(double) 132: #endif 133: 134: typedef union hdr 135: { 1.1.1.4 ! root 136: char align[ALIGN_SIZE]; /* To force sizeof(header). */ 1.1 root 137: struct 138: { 1.1.1.4 ! root 139: union hdr *next; /* For chaining headers. */ ! 140: char *deep; /* For stack depth measure. */ 1.1 root 141: } h; 142: } header; 143: 1.1.1.4 ! root 144: static header *last_alloca_header = NULL; /* -> last alloca header. */ 1.1 root 145: 1.1.1.4 ! root 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. */ 1.1 root 152: 153: pointer 1.1.1.4 ! root 154: alloca (size) ! 155: unsigned size; 1.1 root 156: { 1.1.1.4 ! root 157: auto char probe; /* Probes stack depth: */ ! 158: register char *depth = ADDRESS_FUNCTION (probe); 1.1 root 159: 160: #if STACK_DIRECTION == 0 1.1.1.4 ! root 161: if (STACK_DIR == 0) /* Unknown growth direction. */ 1.1 root 162: find_stack_direction (); 163: #endif 164: 1.1.1.4 ! root 165: /* Reclaim garbage, defined as all alloca'd storage that ! 166: was allocated from deeper in the stack than currently. */ 1.1 root 167: 168: { 1.1.1.4 ! root 169: register header *hp; /* Traverses linked list. */ 1.1 root 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: { 1.1.1.4 ! root 175: register header *np = hp->h.next; 1.1 root 176: 1.1.1.4 ! root 177: free ((pointer) hp); /* Collect garbage. */ 1.1 root 178: 1.1.1.4 ! root 179: hp = np; /* -> next header. */ 1.1 root 180: } 181: else 1.1.1.4 ! root 182: break; /* Rest are not deeper. */ 1.1 root 183: 1.1.1.4 ! root 184: last_alloca_header = hp; /* -> last valid storage. */ 1.1 root 185: } 186: 187: if (size == 0) 1.1.1.4 ! root 188: return NULL; /* No allocation required. */ 1.1 root 189: 1.1.1.4 ! root 190: /* Allocate combined header + user data storage. */ 1.1 root 191: 192: { 1.1.1.4 ! root 193: register pointer new = malloc (sizeof (header) + size); ! 194: /* Address of header. */ 1.1 root 195: 1.1.1.4 ! root 196: ((header *) new)->h.next = last_alloca_header; ! 197: ((header *) new)->h.deep = depth; 1.1 root 198: 1.1.1.4 ! root 199: last_alloca_header = (header *) new; 1.1 root 200: 1.1.1.4 ! root 201: /* User storage begins just after header. */ 1.1 root 202: 1.1.1.4 ! root 203: return (pointer) ((char *) new + sizeof (header)); 1.1 root 204: } 205: } 206: 1.1.1.4 ! root 207: #ifdef CRAY ! 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: 1.1 root 475: #endif /* no alloca */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.