133965Sjdp/* alloca.c -- allocate automatically reclaimed memory 233965Sjdp (Mostly) portable public-domain implementation -- D A Gwyn 333965Sjdp 433965Sjdp This implementation of the PWB library alloca function, 533965Sjdp which is used to allocate space off the run-time stack so 633965Sjdp that it is automatically reclaimed upon procedure exit, 733965Sjdp was inspired by discussions with J. Q. Johnson of Cornell. 833965Sjdp J.Otto Tennant <jot@cray.com> contributed the Cray support. 933965Sjdp 1033965Sjdp There are some preprocessor constants that can 1133965Sjdp be defined when compiling for your specific system, for 1233965Sjdp improved efficiency; however, the defaults should be okay. 1333965Sjdp 1433965Sjdp The general concept of this implementation is to keep 1533965Sjdp track of all alloca-allocated blocks, and reclaim any 1633965Sjdp that are found to be deeper in the stack than the current 1733965Sjdp invocation. This heuristic does not reclaim storage as 1833965Sjdp soon as it becomes invalid, but it will do so eventually. 1933965Sjdp 2033965Sjdp As a special case, alloca(0) reclaims storage without 2133965Sjdp allocating any. It is a good idea to use alloca(0) in 2233965Sjdp your main control loop, etc. to force garbage collection. */ 2333965Sjdp 2489857Sobrien/* 2589857Sobrien 2689857Sobrien@deftypefn Replacement void* alloca (size_t @var{size}) 2789857Sobrien 2889857SobrienThis function allocates memory which will be automatically reclaimed 2989857Sobrienafter the procedure exits. The @libib{} implementation does not free 3089857Sobrienthe memory immediately but will do so eventually during subsequent 3189857Sobriencalls to this function. Memory is allocated using @code{xmalloc} under 3289857Sobriennormal circumstances. 3389857Sobrien 3489857SobrienThe header file @file{alloca-conf.h} can be used in conjunction with the 3589857SobrienGNU Autoconf test @code{AC_FUNC_ALLOCA} to test for and properly make 3689857Sobrienavailable this function. The @code{AC_FUNC_ALLOCA} test requires that 3789857Sobrienclient code use a block of preprocessor code to be safe (see the Autoconf 3889857Sobrienmanual for more); this header incorporates that logic and more, including 3989857Sobrienthe possibility of a GCC built-in function. 4089857Sobrien 4189857Sobrien@end deftypefn 4289857Sobrien 4389857Sobrien*/ 4489857Sobrien 4533965Sjdp#ifdef HAVE_CONFIG_H 4660484Sobrien#include <config.h> 4733965Sjdp#endif 4833965Sjdp 4989857Sobrien#include <libiberty.h> 5089857Sobrien 5160484Sobrien#ifdef HAVE_STRING_H 5260484Sobrien#include <string.h> 5360484Sobrien#endif 5460484Sobrien#ifdef HAVE_STDLIB_H 5560484Sobrien#include <stdlib.h> 5660484Sobrien#endif 5760484Sobrien 5889857Sobrien/* These variables are used by the ASTRDUP implementation that relies 5989857Sobrien on C_alloca. */ 60218822Sdim#ifdef __cplusplus 61218822Sdimextern "C" { 62218822Sdim#endif /* __cplusplus */ 6389857Sobrienconst char *libiberty_optr; 6489857Sobrienchar *libiberty_nptr; 6589857Sobrienunsigned long libiberty_len; 66218822Sdim#ifdef __cplusplus 67218822Sdim} 68218822Sdim#endif /* __cplusplus */ 6960484Sobrien 7033965Sjdp/* If your stack is a linked list of frames, you have to 7133965Sjdp provide an "address metric" ADDRESS_FUNCTION macro. */ 7233965Sjdp 7333965Sjdp#if defined (CRAY) && defined (CRAY_STACKSEG_END) 7489857Sobrienstatic long i00afunc (); 7533965Sjdp#define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg)) 7633965Sjdp#else 7733965Sjdp#define ADDRESS_FUNCTION(arg) &(arg) 7833965Sjdp#endif 7933965Sjdp 8033965Sjdp#ifndef NULL 8133965Sjdp#define NULL 0 8233965Sjdp#endif 8333965Sjdp 8433965Sjdp/* Define STACK_DIRECTION if you know the direction of stack 8533965Sjdp growth for your system; otherwise it will be automatically 8633965Sjdp deduced at run-time. 8733965Sjdp 8833965Sjdp STACK_DIRECTION > 0 => grows toward higher addresses 8933965Sjdp STACK_DIRECTION < 0 => grows toward lower addresses 9033965Sjdp STACK_DIRECTION = 0 => direction of growth unknown */ 9133965Sjdp 9233965Sjdp#ifndef STACK_DIRECTION 9333965Sjdp#define STACK_DIRECTION 0 /* Direction unknown. */ 9433965Sjdp#endif 9533965Sjdp 9633965Sjdp#if STACK_DIRECTION != 0 9733965Sjdp 9833965Sjdp#define STACK_DIR STACK_DIRECTION /* Known at compile-time. */ 9933965Sjdp 10033965Sjdp#else /* STACK_DIRECTION == 0; need run-time code. */ 10133965Sjdp 10233965Sjdpstatic int stack_dir; /* 1 or -1 once known. */ 10333965Sjdp#define STACK_DIR stack_dir 10433965Sjdp 10533965Sjdpstatic void 106218822Sdimfind_stack_direction (void) 10733965Sjdp{ 10833965Sjdp static char *addr = NULL; /* Address of first `dummy', once known. */ 10933965Sjdp auto char dummy; /* To get stack address. */ 11033965Sjdp 11133965Sjdp if (addr == NULL) 11233965Sjdp { /* Initial entry. */ 11333965Sjdp addr = ADDRESS_FUNCTION (dummy); 11433965Sjdp 11533965Sjdp find_stack_direction (); /* Recurse once. */ 11633965Sjdp } 11733965Sjdp else 11833965Sjdp { 11933965Sjdp /* Second entry. */ 12033965Sjdp if (ADDRESS_FUNCTION (dummy) > addr) 12133965Sjdp stack_dir = 1; /* Stack grew upward. */ 12233965Sjdp else 12333965Sjdp stack_dir = -1; /* Stack grew downward. */ 12433965Sjdp } 12533965Sjdp} 12633965Sjdp 12733965Sjdp#endif /* STACK_DIRECTION == 0 */ 12833965Sjdp 12933965Sjdp/* An "alloca header" is used to: 13033965Sjdp (a) chain together all alloca'ed blocks; 13133965Sjdp (b) keep track of stack depth. 13233965Sjdp 13333965Sjdp It is very important that sizeof(header) agree with malloc 13433965Sjdp alignment chunk size. The following default should work okay. */ 13533965Sjdp 13633965Sjdp#ifndef ALIGN_SIZE 13733965Sjdp#define ALIGN_SIZE sizeof(double) 13833965Sjdp#endif 13933965Sjdp 14033965Sjdptypedef union hdr 14133965Sjdp{ 14233965Sjdp char align[ALIGN_SIZE]; /* To force sizeof(header). */ 14333965Sjdp struct 14433965Sjdp { 14533965Sjdp union hdr *next; /* For chaining headers. */ 14633965Sjdp char *deep; /* For stack depth measure. */ 14733965Sjdp } h; 14833965Sjdp} header; 14933965Sjdp 15033965Sjdpstatic header *last_alloca_header = NULL; /* -> last alloca header. */ 15133965Sjdp 15233965Sjdp/* Return a pointer to at least SIZE bytes of storage, 15333965Sjdp which will be automatically reclaimed upon exit from 15433965Sjdp the procedure that called alloca. Originally, this space 15533965Sjdp was supposed to be taken from the current stack frame of the 15633965Sjdp caller, but that method cannot be made to work for some 15733965Sjdp implementations of C, for example under Gould's UTX/32. */ 15833965Sjdp 15989857Sobrien/* @undocumented C_alloca */ 16089857Sobrien 16189857SobrienPTR 162218822SdimC_alloca (size_t size) 16333965Sjdp{ 16433965Sjdp auto char probe; /* Probes stack depth: */ 16533965Sjdp register char *depth = ADDRESS_FUNCTION (probe); 16633965Sjdp 16733965Sjdp#if STACK_DIRECTION == 0 16833965Sjdp if (STACK_DIR == 0) /* Unknown growth direction. */ 16933965Sjdp find_stack_direction (); 17033965Sjdp#endif 17133965Sjdp 17233965Sjdp /* Reclaim garbage, defined as all alloca'd storage that 17360484Sobrien was allocated from deeper in the stack than currently. */ 17433965Sjdp 17533965Sjdp { 17633965Sjdp register header *hp; /* Traverses linked list. */ 17733965Sjdp 17833965Sjdp for (hp = last_alloca_header; hp != NULL;) 17933965Sjdp if ((STACK_DIR > 0 && hp->h.deep > depth) 18033965Sjdp || (STACK_DIR < 0 && hp->h.deep < depth)) 18133965Sjdp { 18233965Sjdp register header *np = hp->h.next; 18333965Sjdp 18489857Sobrien free ((PTR) hp); /* Collect garbage. */ 18533965Sjdp 18633965Sjdp hp = np; /* -> next header. */ 18733965Sjdp } 18833965Sjdp else 18933965Sjdp break; /* Rest are not deeper. */ 19033965Sjdp 19133965Sjdp last_alloca_header = hp; /* -> last valid storage. */ 19233965Sjdp } 19333965Sjdp 19433965Sjdp if (size == 0) 19533965Sjdp return NULL; /* No allocation required. */ 19633965Sjdp 19733965Sjdp /* Allocate combined header + user data storage. */ 19833965Sjdp 19933965Sjdp { 200218822Sdim register void *new_storage = XNEWVEC (char, sizeof (header) + size); 20133965Sjdp /* Address of header. */ 20233965Sjdp 203218822Sdim if (new_storage == 0) 20460484Sobrien abort(); 20560484Sobrien 206218822Sdim ((header *) new_storage)->h.next = last_alloca_header; 207218822Sdim ((header *) new_storage)->h.deep = depth; 20833965Sjdp 209218822Sdim last_alloca_header = (header *) new_storage; 21033965Sjdp 21133965Sjdp /* User storage begins just after header. */ 21233965Sjdp 213218822Sdim return (PTR) ((char *) new_storage + sizeof (header)); 21433965Sjdp } 21533965Sjdp} 21633965Sjdp 21733965Sjdp#if defined (CRAY) && defined (CRAY_STACKSEG_END) 21833965Sjdp 21933965Sjdp#ifdef DEBUG_I00AFUNC 22033965Sjdp#include <stdio.h> 22133965Sjdp#endif 22233965Sjdp 22333965Sjdp#ifndef CRAY_STACK 22433965Sjdp#define CRAY_STACK 22533965Sjdp#ifndef CRAY2 22633965Sjdp/* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */ 22733965Sjdpstruct stack_control_header 22833965Sjdp { 22933965Sjdp long shgrow:32; /* Number of times stack has grown. */ 23033965Sjdp long shaseg:32; /* Size of increments to stack. */ 23133965Sjdp long shhwm:32; /* High water mark of stack. */ 23233965Sjdp long shsize:32; /* Current size of stack (all segments). */ 23333965Sjdp }; 23433965Sjdp 23533965Sjdp/* The stack segment linkage control information occurs at 23633965Sjdp the high-address end of a stack segment. (The stack 23733965Sjdp grows from low addresses to high addresses.) The initial 23833965Sjdp part of the stack segment linkage control information is 23933965Sjdp 0200 (octal) words. This provides for register storage 24033965Sjdp for the routine which overflows the stack. */ 24133965Sjdp 24233965Sjdpstruct stack_segment_linkage 24333965Sjdp { 24433965Sjdp long ss[0200]; /* 0200 overflow words. */ 24533965Sjdp long sssize:32; /* Number of words in this segment. */ 24633965Sjdp long ssbase:32; /* Offset to stack base. */ 24733965Sjdp long:32; 24833965Sjdp long sspseg:32; /* Offset to linkage control of previous 24933965Sjdp segment of stack. */ 25033965Sjdp long:32; 25133965Sjdp long sstcpt:32; /* Pointer to task common address block. */ 25233965Sjdp long sscsnm; /* Private control structure number for 25333965Sjdp microtasking. */ 25433965Sjdp long ssusr1; /* Reserved for user. */ 25533965Sjdp long ssusr2; /* Reserved for user. */ 25633965Sjdp long sstpid; /* Process ID for pid based multi-tasking. */ 25733965Sjdp long ssgvup; /* Pointer to multitasking thread giveup. */ 25833965Sjdp long sscray[7]; /* Reserved for Cray Research. */ 25933965Sjdp long ssa0; 26033965Sjdp long ssa1; 26133965Sjdp long ssa2; 26233965Sjdp long ssa3; 26333965Sjdp long ssa4; 26433965Sjdp long ssa5; 26533965Sjdp long ssa6; 26633965Sjdp long ssa7; 26733965Sjdp long sss0; 26833965Sjdp long sss1; 26933965Sjdp long sss2; 27033965Sjdp long sss3; 27133965Sjdp long sss4; 27233965Sjdp long sss5; 27333965Sjdp long sss6; 27433965Sjdp long sss7; 27533965Sjdp }; 27633965Sjdp 27733965Sjdp#else /* CRAY2 */ 27833965Sjdp/* The following structure defines the vector of words 27933965Sjdp returned by the STKSTAT library routine. */ 28033965Sjdpstruct stk_stat 28133965Sjdp { 28233965Sjdp long now; /* Current total stack size. */ 28333965Sjdp long maxc; /* Amount of contiguous space which would 28433965Sjdp be required to satisfy the maximum 28533965Sjdp stack demand to date. */ 28633965Sjdp long high_water; /* Stack high-water mark. */ 28733965Sjdp long overflows; /* Number of stack overflow ($STKOFEN) calls. */ 28833965Sjdp long hits; /* Number of internal buffer hits. */ 28933965Sjdp long extends; /* Number of block extensions. */ 29033965Sjdp long stko_mallocs; /* Block allocations by $STKOFEN. */ 29133965Sjdp long underflows; /* Number of stack underflow calls ($STKRETN). */ 29233965Sjdp long stko_free; /* Number of deallocations by $STKRETN. */ 29333965Sjdp long stkm_free; /* Number of deallocations by $STKMRET. */ 29433965Sjdp long segments; /* Current number of stack segments. */ 29533965Sjdp long maxs; /* Maximum number of stack segments so far. */ 29633965Sjdp long pad_size; /* Stack pad size. */ 29733965Sjdp long current_address; /* Current stack segment address. */ 29833965Sjdp long current_size; /* Current stack segment size. This 29933965Sjdp number is actually corrupted by STKSTAT to 30033965Sjdp include the fifteen word trailer area. */ 30133965Sjdp long initial_address; /* Address of initial segment. */ 30233965Sjdp long initial_size; /* Size of initial segment. */ 30333965Sjdp }; 30433965Sjdp 30533965Sjdp/* The following structure describes the data structure which trails 30633965Sjdp any stack segment. I think that the description in 'asdef' is 30733965Sjdp out of date. I only describe the parts that I am sure about. */ 30833965Sjdp 30933965Sjdpstruct stk_trailer 31033965Sjdp { 31133965Sjdp long this_address; /* Address of this block. */ 31233965Sjdp long this_size; /* Size of this block (does not include 31333965Sjdp this trailer). */ 31433965Sjdp long unknown2; 31533965Sjdp long unknown3; 31633965Sjdp long link; /* Address of trailer block of previous 31733965Sjdp segment. */ 31833965Sjdp long unknown5; 31933965Sjdp long unknown6; 32033965Sjdp long unknown7; 32133965Sjdp long unknown8; 32233965Sjdp long unknown9; 32333965Sjdp long unknown10; 32433965Sjdp long unknown11; 32533965Sjdp long unknown12; 32633965Sjdp long unknown13; 32733965Sjdp long unknown14; 32833965Sjdp }; 32933965Sjdp 33033965Sjdp#endif /* CRAY2 */ 33133965Sjdp#endif /* not CRAY_STACK */ 33233965Sjdp 33333965Sjdp#ifdef CRAY2 33433965Sjdp/* Determine a "stack measure" for an arbitrary ADDRESS. 33560484Sobrien I doubt that "lint" will like this much. */ 33633965Sjdp 33733965Sjdpstatic long 33833965Sjdpi00afunc (long *address) 33933965Sjdp{ 34033965Sjdp struct stk_stat status; 34133965Sjdp struct stk_trailer *trailer; 34233965Sjdp long *block, size; 34333965Sjdp long result = 0; 34433965Sjdp 34533965Sjdp /* We want to iterate through all of the segments. The first 34633965Sjdp step is to get the stack status structure. We could do this 34733965Sjdp more quickly and more directly, perhaps, by referencing the 34833965Sjdp $LM00 common block, but I know that this works. */ 34933965Sjdp 35033965Sjdp STKSTAT (&status); 35133965Sjdp 35233965Sjdp /* Set up the iteration. */ 35333965Sjdp 35433965Sjdp trailer = (struct stk_trailer *) (status.current_address 35533965Sjdp + status.current_size 35633965Sjdp - 15); 35733965Sjdp 35833965Sjdp /* There must be at least one stack segment. Therefore it is 35933965Sjdp a fatal error if "trailer" is null. */ 36033965Sjdp 36133965Sjdp if (trailer == 0) 36233965Sjdp abort (); 36333965Sjdp 36433965Sjdp /* Discard segments that do not contain our argument address. */ 36533965Sjdp 36633965Sjdp while (trailer != 0) 36733965Sjdp { 36833965Sjdp block = (long *) trailer->this_address; 36933965Sjdp size = trailer->this_size; 37033965Sjdp if (block == 0 || size == 0) 37133965Sjdp abort (); 37233965Sjdp trailer = (struct stk_trailer *) trailer->link; 37333965Sjdp if ((block <= address) && (address < (block + size))) 37433965Sjdp break; 37533965Sjdp } 37633965Sjdp 37733965Sjdp /* Set the result to the offset in this segment and add the sizes 37833965Sjdp of all predecessor segments. */ 37933965Sjdp 38033965Sjdp result = address - block; 38133965Sjdp 38233965Sjdp if (trailer == 0) 38333965Sjdp { 38433965Sjdp return result; 38533965Sjdp } 38633965Sjdp 38733965Sjdp do 38833965Sjdp { 38933965Sjdp if (trailer->this_size <= 0) 39033965Sjdp abort (); 39133965Sjdp result += trailer->this_size; 39233965Sjdp trailer = (struct stk_trailer *) trailer->link; 39333965Sjdp } 39433965Sjdp while (trailer != 0); 39533965Sjdp 39633965Sjdp /* We are done. Note that if you present a bogus address (one 39733965Sjdp not in any segment), you will get a different number back, formed 39833965Sjdp from subtracting the address of the first block. This is probably 39933965Sjdp not what you want. */ 40033965Sjdp 40133965Sjdp return (result); 40233965Sjdp} 40333965Sjdp 40433965Sjdp#else /* not CRAY2 */ 40533965Sjdp/* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP. 40633965Sjdp Determine the number of the cell within the stack, 40733965Sjdp given the address of the cell. The purpose of this 40833965Sjdp routine is to linearize, in some sense, stack addresses 40933965Sjdp for alloca. */ 41033965Sjdp 41133965Sjdpstatic long 41233965Sjdpi00afunc (long address) 41333965Sjdp{ 41433965Sjdp long stkl = 0; 41533965Sjdp 41633965Sjdp long size, pseg, this_segment, stack; 41733965Sjdp long result = 0; 41833965Sjdp 41933965Sjdp struct stack_segment_linkage *ssptr; 42033965Sjdp 42133965Sjdp /* Register B67 contains the address of the end of the 42233965Sjdp current stack segment. If you (as a subprogram) store 42333965Sjdp your registers on the stack and find that you are past 42433965Sjdp the contents of B67, you have overflowed the segment. 42533965Sjdp 42633965Sjdp B67 also points to the stack segment linkage control 42733965Sjdp area, which is what we are really interested in. */ 42833965Sjdp 42933965Sjdp stkl = CRAY_STACKSEG_END (); 43033965Sjdp ssptr = (struct stack_segment_linkage *) stkl; 43133965Sjdp 43233965Sjdp /* If one subtracts 'size' from the end of the segment, 43333965Sjdp one has the address of the first word of the segment. 43433965Sjdp 43533965Sjdp If this is not the first segment, 'pseg' will be 43633965Sjdp nonzero. */ 43733965Sjdp 43833965Sjdp pseg = ssptr->sspseg; 43933965Sjdp size = ssptr->sssize; 44033965Sjdp 44133965Sjdp this_segment = stkl - size; 44233965Sjdp 44333965Sjdp /* It is possible that calling this routine itself caused 44433965Sjdp a stack overflow. Discard stack segments which do not 44533965Sjdp contain the target address. */ 44633965Sjdp 44733965Sjdp while (!(this_segment <= address && address <= stkl)) 44833965Sjdp { 44933965Sjdp#ifdef DEBUG_I00AFUNC 45033965Sjdp fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl); 45133965Sjdp#endif 45233965Sjdp if (pseg == 0) 45333965Sjdp break; 45433965Sjdp stkl = stkl - pseg; 45533965Sjdp ssptr = (struct stack_segment_linkage *) stkl; 45633965Sjdp size = ssptr->sssize; 45733965Sjdp pseg = ssptr->sspseg; 45833965Sjdp this_segment = stkl - size; 45933965Sjdp } 46033965Sjdp 46133965Sjdp result = address - this_segment; 46233965Sjdp 46333965Sjdp /* If you subtract pseg from the current end of the stack, 46433965Sjdp you get the address of the previous stack segment's end. 46533965Sjdp This seems a little convoluted to me, but I'll bet you save 46633965Sjdp a cycle somewhere. */ 46733965Sjdp 46833965Sjdp while (pseg != 0) 46933965Sjdp { 47033965Sjdp#ifdef DEBUG_I00AFUNC 47133965Sjdp fprintf (stderr, "%011o %011o\n", pseg, size); 47233965Sjdp#endif 47333965Sjdp stkl = stkl - pseg; 47433965Sjdp ssptr = (struct stack_segment_linkage *) stkl; 47533965Sjdp size = ssptr->sssize; 47633965Sjdp pseg = ssptr->sspseg; 47733965Sjdp result += size; 47833965Sjdp } 47933965Sjdp return (result); 48033965Sjdp} 48133965Sjdp 48233965Sjdp#endif /* not CRAY2 */ 48333965Sjdp#endif /* CRAY */ 484