X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Falloca.c;h=c7e91ab9336cf44d589d13a077d120518c9ce6e2;hb=a365e1e5d3afa9a9f12d38eacaade8cd8fe0020e;hp=c1ff22227f8effcb02c63d10a47f81515f806a35;hpb=43e78b970f396160a887c9da94531569faeda8a0;p=gnulib.git diff --git a/lib/alloca.c b/lib/alloca.c index c1ff22227..c7e91ab93 100644 --- a/lib/alloca.c +++ b/lib/alloca.c @@ -1,194 +1,478 @@ -/* - alloca -- (mostly) portable public-domain implementation -- D A Gwyn - - last edit: 86/05/30 rms - include config.h, since on VMS it renames some symbols. - Use xmalloc instead of malloc. - - This implementation of the PWB library alloca() function, - which is used to allocate space off the run-time stack so - that it is automatically reclaimed upon procedure exit, - was inspired by discussions with J. Q. Johnson of Cornell. - - It should work under any C implementation that uses an - actual procedure stack (as opposed to a linked list of - frames). There are some preprocessor constants that can - be defined when compiling for your specific system, for - improved efficiency; however, the defaults should be okay. - - The general concept of this implementation is to keep - track of all alloca()-allocated blocks, and reclaim any - that are found to be deeper in the stack than the current - invocation. This heuristic does not reclaim storage as - soon as it becomes invalid, but it will do so eventually. - - As a special case, alloca(0) reclaims storage without - allocating any. It is a good idea to use alloca(0) in - your main control loop, etc. to force garbage collection. -*/ -#ifndef lint -static char SCCSid[] = "@(#)alloca.c 1.1"; /* for the "what" utility */ -#endif +/* alloca.c -- allocate automatically reclaimed memory + (Mostly) portable public-domain implementation -- D A Gwyn + + This implementation of the PWB library alloca function, + which is used to allocate space off the run-time stack so + that it is automatically reclaimed upon procedure exit, + was inspired by discussions with J. Q. Johnson of Cornell. + J.Otto Tennant contributed the Cray support. + + There are some preprocessor constants that can + be defined when compiling for your specific system, for + improved efficiency; however, the defaults should be okay. + + The general concept of this implementation is to keep + track of all alloca-allocated blocks, and reclaim any + that are found to be deeper in the stack than the current + invocation. This heuristic does not reclaim storage as + soon as it becomes invalid, but it will do so eventually. + + As a special case, alloca(0) reclaims storage without + allocating any. It is a good idea to use alloca(0) in + your main control loop, etc. to force garbage collection. */ + +#include + +#include + +#include +#include #ifdef emacs -#include "config.h" -#ifdef static +# include "lisp.h" +# include "blockinput.h" +# ifdef EMACS_FREE +# undef free +# define free EMACS_FREE +# endif +#else +# define memory_full() abort () +#endif + +/* If compiling with GCC 2, this file's not needed. */ +#if !defined (__GNUC__) || __GNUC__ < 2 + +/* If someone has defined alloca as a macro, + there must be some other way alloca is supposed to work. */ +# ifndef alloca + +# ifdef emacs +# ifdef static /* actually, only want this if static is defined as "" -- this is for usg, in which emacs must undefine static in order to make unexec workable */ -#ifndef STACK_DIRECTION +# ifndef STACK_DIRECTION you lose -- must know STACK_DIRECTION at compile-time -#endif /* STACK_DIRECTION undefined */ -#endif /* static */ -#endif /* emacs */ - -#ifndef alloca /* If compiling with GCC, this file's not needed. */ - -#ifdef __STDC__ -typedef void *pointer; /* generic pointer type */ -#else -typedef char *pointer; /* generic pointer type */ -#endif +/* Using #error here is not wise since this file should work for + old and obscure compilers. */ +# endif /* STACK_DIRECTION undefined */ +# endif /* static */ +# endif /* emacs */ -#define NULL 0 /* null pointer constant */ +/* If your stack is a linked list of frames, you have to + provide an "address metric" ADDRESS_FUNCTION macro. */ -extern void free(); -extern pointer xmalloc(); +# if defined (CRAY) && defined (CRAY_STACKSEG_END) +long i00afunc (); +# define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg)) +# else +# define ADDRESS_FUNCTION(arg) &(arg) +# endif -/* - Define STACK_DIRECTION if you know the direction of stack - growth for your system; otherwise it will be automatically - deduced at run-time. +/* Define STACK_DIRECTION if you know the direction of stack + growth for your system; otherwise it will be automatically + deduced at run-time. - STACK_DIRECTION > 0 => grows toward higher addresses - STACK_DIRECTION < 0 => grows toward lower addresses - STACK_DIRECTION = 0 => direction of growth unknown -*/ + STACK_DIRECTION > 0 => grows toward higher addresses + STACK_DIRECTION < 0 => grows toward lower addresses + STACK_DIRECTION = 0 => direction of growth unknown */ -#ifndef STACK_DIRECTION -#define STACK_DIRECTION 0 /* direction unknown */ -#endif +# ifndef STACK_DIRECTION +# define STACK_DIRECTION 0 /* Direction unknown. */ +# endif -#if STACK_DIRECTION != 0 +# if STACK_DIRECTION != 0 -#define STACK_DIR STACK_DIRECTION /* known at compile-time */ +# define STACK_DIR STACK_DIRECTION /* Known at compile-time. */ -#else /* STACK_DIRECTION == 0; need run-time code */ +# else /* STACK_DIRECTION == 0; need run-time code. */ -static int stack_dir; /* 1 or -1 once known */ -#define STACK_DIR stack_dir +static int stack_dir; /* 1 or -1 once known. */ +# define STACK_DIR stack_dir -static void -find_stack_direction (/* void */) +static int +find_stack_direction (int *addr, int depth) { - static char *addr = NULL; /* address of first - `dummy', once known */ - auto char dummy; /* to get stack address */ - - if (addr == NULL) - { /* initial entry */ - addr = &dummy; - - find_stack_direction (); /* recurse once */ - } - else /* second entry */ - if (&dummy > addr) - stack_dir = 1; /* stack grew upward */ - else - stack_dir = -1; /* stack grew downward */ + int dir, dummy = 0; + if (! addr) + addr = &dummy; + *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1; + dir = depth ? find_stack_direction (addr, depth - 1) : 0; + return dir + dummy; } -#endif /* STACK_DIRECTION == 0 */ +# endif /* STACK_DIRECTION == 0 */ -/* - An "alloca header" is used to: - (a) chain together all alloca()ed blocks; - (b) keep track of stack depth. +/* An "alloca header" is used to: + (a) chain together all alloca'ed blocks; + (b) keep track of stack depth. - It is very important that sizeof(header) agree with malloc() - alignment chunk size. The following default should work okay. -*/ + It is very important that sizeof(header) agree with malloc + alignment chunk size. The following default should work okay. */ -#ifndef ALIGN_SIZE -#define ALIGN_SIZE sizeof(double) -#endif +# ifndef ALIGN_SIZE +# define ALIGN_SIZE sizeof(double) +# endif typedef union hdr { - char align[ALIGN_SIZE]; /* to force sizeof(header) */ + char align[ALIGN_SIZE]; /* To force sizeof(header). */ struct { - union hdr *next; /* for chaining headers */ - char *deep; /* for stack depth measure */ + union hdr *next; /* For chaining headers. */ + char *deep; /* For stack depth measure. */ } h; } header; -/* - alloca( size ) returns a pointer to at least `size' bytes of - storage which will be automatically reclaimed upon exit from - the procedure that called alloca(). Originally, this space - was supposed to be taken from the current stack frame of the - caller, but that method cannot be made to work for some - implementations of C, for example under Gould's UTX/32. -*/ +static header *last_alloca_header = NULL; /* -> last alloca header. */ -static header *last_alloca_header = NULL; /* -> last alloca header */ +/* Return a pointer to at least SIZE bytes of storage, + which will be automatically reclaimed upon exit from + the procedure that called alloca. Originally, this space + was supposed to be taken from the current stack frame of the + caller, but that method cannot be made to work for some + implementations of C, for example under Gould's UTX/32. */ -pointer -alloca (size) /* returns pointer to storage */ - unsigned size; /* # bytes to allocate */ +void * +alloca (size_t size) { - auto char probe; /* probes stack depth: */ - register char *depth = &probe; + auto char probe; /* Probes stack depth: */ + register char *depth = ADDRESS_FUNCTION (probe); -#if STACK_DIRECTION == 0 - if (STACK_DIR == 0) /* unknown growth direction */ - find_stack_direction (); -#endif +# if STACK_DIRECTION == 0 + if (STACK_DIR == 0) /* Unknown growth direction. */ + STACK_DIR = find_stack_direction (NULL, (size & 1) + 20); +# endif - /* Reclaim garbage, defined as all alloca()ed storage that - was allocated from deeper in the stack than currently. */ + /* Reclaim garbage, defined as all alloca'd storage that + was allocated from deeper in the stack than currently. */ { - register header *hp; /* traverses linked list */ + register header *hp; /* Traverses linked list. */ + +# ifdef emacs + BLOCK_INPUT; +# endif for (hp = last_alloca_header; hp != NULL;) if ((STACK_DIR > 0 && hp->h.deep > depth) - || (STACK_DIR < 0 && hp->h.deep < depth)) - { - register header *np = hp->h.next; + || (STACK_DIR < 0 && hp->h.deep < depth)) + { + register header *np = hp->h.next; - free ((pointer) hp); /* collect garbage */ + free (hp); /* Collect garbage. */ - hp = np; /* -> next header */ - } + hp = np; /* -> next header. */ + } else - break; /* rest are not deeper */ + break; /* Rest are not deeper. */ + + last_alloca_header = hp; /* -> last valid storage. */ - last_alloca_header = hp; /* -> last valid storage */ +# ifdef emacs + UNBLOCK_INPUT; +# endif } if (size == 0) - return NULL; /* no allocation required */ + return NULL; /* No allocation required. */ - /* Allocate combined header + user data storage. */ + /* Allocate combined header + user data storage. */ { - register pointer new = xmalloc (sizeof (header) + size); - /* address of header */ + /* Address of header. */ + register header *new; - ((header *)new)->h.next = last_alloca_header; - ((header *)new)->h.deep = depth; + size_t combined_size = sizeof (header) + size; + if (combined_size < sizeof (header)) + memory_full (); - last_alloca_header = (header *)new; + new = malloc (combined_size); - /* User storage begins just after header. */ + if (! new) + memory_full (); - return (pointer)((char *)new + sizeof(header)); + new->h.next = last_alloca_header; + new->h.deep = depth; + + last_alloca_header = new; + + /* User storage begins just after header. */ + + return (void *) (new + 1); } } -#endif /* no alloca */ +# if defined (CRAY) && defined (CRAY_STACKSEG_END) + +# ifdef DEBUG_I00AFUNC +# include +# endif + +# ifndef CRAY_STACK +# define CRAY_STACK +# ifndef CRAY2 +/* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */ +struct stack_control_header + { + long shgrow:32; /* Number of times stack has grown. */ + long shaseg:32; /* Size of increments to stack. */ + long shhwm:32; /* High water mark of stack. */ + long shsize:32; /* Current size of stack (all segments). */ + }; + +/* The stack segment linkage control information occurs at + the high-address end of a stack segment. (The stack + grows from low addresses to high addresses.) The initial + part of the stack segment linkage control information is + 0200 (octal) words. This provides for register storage + for the routine which overflows the stack. */ + +struct stack_segment_linkage + { + long ss[0200]; /* 0200 overflow words. */ + long sssize:32; /* Number of words in this segment. */ + long ssbase:32; /* Offset to stack base. */ + long:32; + long sspseg:32; /* Offset to linkage control of previous + segment of stack. */ + long:32; + long sstcpt:32; /* Pointer to task common address block. */ + long sscsnm; /* Private control structure number for + microtasking. */ + long ssusr1; /* Reserved for user. */ + long ssusr2; /* Reserved for user. */ + long sstpid; /* Process ID for pid based multi-tasking. */ + long ssgvup; /* Pointer to multitasking thread giveup. */ + long sscray[7]; /* Reserved for Cray Research. */ + long ssa0; + long ssa1; + long ssa2; + long ssa3; + long ssa4; + long ssa5; + long ssa6; + long ssa7; + long sss0; + long sss1; + long sss2; + long sss3; + long sss4; + long sss5; + long sss6; + long sss7; + }; + +# else /* CRAY2 */ +/* The following structure defines the vector of words + returned by the STKSTAT library routine. */ +struct stk_stat + { + long now; /* Current total stack size. */ + long maxc; /* Amount of contiguous space which would + be required to satisfy the maximum + stack demand to date. */ + long high_water; /* Stack high-water mark. */ + long overflows; /* Number of stack overflow ($STKOFEN) calls. */ + long hits; /* Number of internal buffer hits. */ + long extends; /* Number of block extensions. */ + long stko_mallocs; /* Block allocations by $STKOFEN. */ + long underflows; /* Number of stack underflow calls ($STKRETN). */ + long stko_free; /* Number of deallocations by $STKRETN. */ + long stkm_free; /* Number of deallocations by $STKMRET. */ + long segments; /* Current number of stack segments. */ + long maxs; /* Maximum number of stack segments so far. */ + long pad_size; /* Stack pad size. */ + long current_address; /* Current stack segment address. */ + long current_size; /* Current stack segment size. This + number is actually corrupted by STKSTAT to + include the fifteen word trailer area. */ + long initial_address; /* Address of initial segment. */ + long initial_size; /* Size of initial segment. */ + }; + +/* The following structure describes the data structure which trails + any stack segment. I think that the description in 'asdef' is + out of date. I only describe the parts that I am sure about. */ + +struct stk_trailer + { + long this_address; /* Address of this block. */ + long this_size; /* Size of this block (does not include + this trailer). */ + long unknown2; + long unknown3; + long link; /* Address of trailer block of previous + segment. */ + long unknown5; + long unknown6; + long unknown7; + long unknown8; + long unknown9; + long unknown10; + long unknown11; + long unknown12; + long unknown13; + long unknown14; + }; + +# endif /* CRAY2 */ +# endif /* not CRAY_STACK */ + +# ifdef CRAY2 +/* Determine a "stack measure" for an arbitrary ADDRESS. + I doubt that "lint" will like this much. */ + +static long +i00afunc (long *address) +{ + struct stk_stat status; + struct stk_trailer *trailer; + long *block, size; + long result = 0; + + /* We want to iterate through all of the segments. The first + step is to get the stack status structure. We could do this + more quickly and more directly, perhaps, by referencing the + $LM00 common block, but I know that this works. */ + + STKSTAT (&status); + + /* Set up the iteration. */ + + trailer = (struct stk_trailer *) (status.current_address + + status.current_size + - 15); + + /* There must be at least one stack segment. Therefore it is + a fatal error if "trailer" is null. */ + + if (trailer == 0) + abort (); + + /* Discard segments that do not contain our argument address. */ + + while (trailer != 0) + { + block = (long *) trailer->this_address; + size = trailer->this_size; + if (block == 0 || size == 0) + abort (); + trailer = (struct stk_trailer *) trailer->link; + if ((block <= address) && (address < (block + size))) + break; + } + + /* Set the result to the offset in this segment and add the sizes + of all predecessor segments. */ + + result = address - block; + + if (trailer == 0) + { + return result; + } + + do + { + if (trailer->this_size <= 0) + abort (); + result += trailer->this_size; + trailer = (struct stk_trailer *) trailer->link; + } + while (trailer != 0); + + /* We are done. Note that if you present a bogus address (one + not in any segment), you will get a different number back, formed + from subtracting the address of the first block. This is probably + not what you want. */ + + return (result); +} + +# else /* not CRAY2 */ +/* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP. + Determine the number of the cell within the stack, + given the address of the cell. The purpose of this + routine is to linearize, in some sense, stack addresses + for alloca. */ + +static long +i00afunc (long address) +{ + long stkl = 0; + + long size, pseg, this_segment, stack; + long result = 0; + + struct stack_segment_linkage *ssptr; + + /* Register B67 contains the address of the end of the + current stack segment. If you (as a subprogram) store + your registers on the stack and find that you are past + the contents of B67, you have overflowed the segment. + + B67 also points to the stack segment linkage control + area, which is what we are really interested in. */ + + stkl = CRAY_STACKSEG_END (); + ssptr = (struct stack_segment_linkage *) stkl; + + /* If one subtracts 'size' from the end of the segment, + one has the address of the first word of the segment. + + If this is not the first segment, 'pseg' will be + nonzero. */ + + pseg = ssptr->sspseg; + size = ssptr->sssize; + + this_segment = stkl - size; + + /* It is possible that calling this routine itself caused + a stack overflow. Discard stack segments which do not + contain the target address. */ + + while (!(this_segment <= address && address <= stkl)) + { +# ifdef DEBUG_I00AFUNC + fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl); +# endif + if (pseg == 0) + break; + stkl = stkl - pseg; + ssptr = (struct stack_segment_linkage *) stkl; + size = ssptr->sssize; + pseg = ssptr->sspseg; + this_segment = stkl - size; + } + + result = address - this_segment; + + /* If you subtract pseg from the current end of the stack, + you get the address of the previous stack segment's end. + This seems a little convoluted to me, but I'll bet you save + a cycle somewhere. */ + + while (pseg != 0) + { +# ifdef DEBUG_I00AFUNC + fprintf (stderr, "%011o %011o\n", pseg, size); +# endif + stkl = stkl - pseg; + ssptr = (struct stack_segment_linkage *) stkl; + size = ssptr->sssize; + pseg = ssptr->sspseg; + result += size; + } + return (result); +} + +# endif /* not CRAY2 */ +# endif /* CRAY */ + +# endif /* no alloca */ +#endif /* not GCC version 2 */