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