00001 /* alloca.c -- allocate automatically reclaimed memory 00002 (Mostly) portable public-domain implementation -- D A Gwyn 00003 00004 This implementation of the PWB library alloca function, 00005 which is used to allocate space off the run-time stack so 00006 that it is automatically reclaimed upon procedure exit, 00007 was inspired by discussions with J. Q. Johnson of Cornell. 00008 J.Otto Tennant <jot@cray.com> contributed the Cray support. 00009 00010 There are some preprocessor constants that can 00011 be defined when compiling for your specific system, for 00012 improved efficiency; however, the defaults should be okay. 00013 00014 The general concept of this implementation is to keep 00015 track of all alloca-allocated blocks, and reclaim any 00016 that are found to be deeper in the stack than the current 00017 invocation. This heuristic does not reclaim storage as 00018 soon as it becomes invalid, but it will do so eventually. 00019 00020 As a special case, alloca(0) reclaims storage without 00021 allocating any. It is a good idea to use alloca(0) in 00022 your main control loop, etc. to force garbage collection. */ 00023 00024 #ifdef HAVE_CONFIG_H 00025 #include <config.h> 00026 #endif 00027 00028 #ifdef HAVE_STRING_H 00029 #include <string.h> 00030 #endif 00031 #ifdef HAVE_STDLIB_H 00032 #include <stdlib.h> 00033 #endif 00034 00035 #ifdef emacs 00036 #include "blockinput.h" 00037 #endif 00038 00039 /* If compiling with GCC 2, this file's not needed. */ 00040 #if !defined (__GNUC__) || __GNUC__ < 2 00041 00042 /* If someone has defined alloca as a macro, 00043 there must be some other way alloca is supposed to work. */ 00044 #ifndef alloca 00045 00046 #ifdef emacs 00047 #ifdef static 00048 /* actually, only want this if static is defined as "" 00049 -- this is for usg, in which emacs must undefine static 00050 in order to make unexec workable 00051 */ 00052 #ifndef STACK_DIRECTION 00053 you 00054 lose 00055 -- must know STACK_DIRECTION at compile-time 00056 #endif /* STACK_DIRECTION undefined */ 00057 #endif /* static */ 00058 #endif /* emacs */ 00059 00060 /* If your stack is a linked list of frames, you have to 00061 provide an "address metric" ADDRESS_FUNCTION macro. */ 00062 00063 #if defined (CRAY) && defined (CRAY_STACKSEG_END) 00064 long i00afunc (); 00065 #define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg)) 00066 #else 00067 #define ADDRESS_FUNCTION(arg) &(arg) 00068 #endif 00069 00070 #if __STDC__ 00071 typedef void *pointer; 00072 #else 00073 typedef char *pointer; 00074 #endif 00075 00076 #ifndef NULL 00077 #define NULL 0 00078 #endif 00079 00080 /* Different portions of Emacs need to call different versions of 00081 malloc. The Emacs executable needs alloca to call xmalloc, because 00082 ordinary malloc isn't protected from input signals. On the other 00083 hand, the utilities in lib-src need alloca to call malloc; some of 00084 them are very simple, and don't have an xmalloc routine. 00085 00086 Non-Emacs programs expect this to call xmalloc. 00087 00088 Callers below should use malloc. */ 00089 00090 #ifndef emacs 00091 #define malloc xmalloc 00092 #endif 00093 extern pointer malloc (); 00094 00095 /* Define STACK_DIRECTION if you know the direction of stack 00096 growth for your system; otherwise it will be automatically 00097 deduced at run-time. 00098 00099 STACK_DIRECTION > 0 => grows toward higher addresses 00100 STACK_DIRECTION < 0 => grows toward lower addresses 00101 STACK_DIRECTION = 0 => direction of growth unknown */ 00102 00103 #ifndef STACK_DIRECTION 00104 #define STACK_DIRECTION 0 /* Direction unknown. */ 00105 #endif 00106 00107 #if STACK_DIRECTION != 0 00108 00109 #define STACK_DIR STACK_DIRECTION /* Known at compile-time. */ 00110 00111 #else /* STACK_DIRECTION == 0; need run-time code. */ 00112 00113 static int stack_dir; /* 1 or -1 once known. */ 00114 #define STACK_DIR stack_dir 00115 00116 static void 00117 find_stack_direction () 00118 { 00119 static char *addr = NULL; /* Address of first `dummy', once known. */ 00120 auto char dummy; /* To get stack address. */ 00121 00122 if (addr == NULL) 00123 { /* Initial entry. */ 00124 addr = ADDRESS_FUNCTION (dummy); 00125 00126 find_stack_direction (); /* Recurse once. */ 00127 } 00128 else 00129 { 00130 /* Second entry. */ 00131 if (ADDRESS_FUNCTION (dummy) > addr) 00132 stack_dir = 1; /* Stack grew upward. */ 00133 else 00134 stack_dir = -1; /* Stack grew downward. */ 00135 } 00136 } 00137 00138 #endif /* STACK_DIRECTION == 0 */ 00139 00140 /* An "alloca header" is used to: 00141 (a) chain together all alloca'ed blocks; 00142 (b) keep track of stack depth. 00143 00144 It is very important that sizeof(header) agree with malloc 00145 alignment chunk size. The following default should work okay. */ 00146 00147 #ifndef ALIGN_SIZE 00148 #define ALIGN_SIZE sizeof(double) 00149 #endif 00150 00151 typedef union hdr 00152 { 00153 char align[ALIGN_SIZE]; /* To force sizeof(header). */ 00154 struct 00155 { 00156 union hdr *next; /* For chaining headers. */ 00157 char *deep; /* For stack depth measure. */ 00158 } h; 00159 } header; 00160 00161 static header *last_alloca_header = NULL; /* -> last alloca header. */ 00162 00163 /* Return a pointer to at least SIZE bytes of storage, 00164 which will be automatically reclaimed upon exit from 00165 the procedure that called alloca. Originally, this space 00166 was supposed to be taken from the current stack frame of the 00167 caller, but that method cannot be made to work for some 00168 implementations of C, for example under Gould's UTX/32. */ 00169 00170 pointer 00171 alloca (size) 00172 unsigned size; 00173 { 00174 auto char probe; /* Probes stack depth: */ 00175 register char *depth = ADDRESS_FUNCTION (probe); 00176 00177 #if STACK_DIRECTION == 0 00178 if (STACK_DIR == 0) /* Unknown growth direction. */ 00179 find_stack_direction (); 00180 #endif 00181 00182 /* Reclaim garbage, defined as all alloca'd storage that 00183 was allocated from deeper in the stack than currently. */ 00184 00185 { 00186 register header *hp; /* Traverses linked list. */ 00187 00188 #ifdef emacs 00189 BLOCK_INPUT; 00190 #endif 00191 00192 for (hp = last_alloca_header; hp != NULL;) 00193 if ((STACK_DIR > 0 && hp->h.deep > depth) 00194 || (STACK_DIR < 0 && hp->h.deep < depth)) 00195 { 00196 register header *np = hp->h.next; 00197 00198 free ((pointer) hp); /* Collect garbage. */ 00199 00200 hp = np; /* -> next header. */ 00201 } 00202 else 00203 break; /* Rest are not deeper. */ 00204 00205 last_alloca_header = hp; /* -> last valid storage. */ 00206 00207 #ifdef emacs 00208 UNBLOCK_INPUT; 00209 #endif 00210 } 00211 00212 if (size == 0) 00213 return NULL; /* No allocation required. */ 00214 00215 /* Allocate combined header + user data storage. */ 00216 00217 { 00218 register pointer new = malloc (sizeof (header) + size); 00219 /* Address of header. */ 00220 00221 if (new == 0) 00222 abort(); 00223 00224 ((header *) new)->h.next = last_alloca_header; 00225 ((header *) new)->h.deep = depth; 00226 00227 last_alloca_header = (header *) new; 00228 00229 /* User storage begins just after header. */ 00230 00231 return (pointer) ((char *) new + sizeof (header)); 00232 } 00233 } 00234 00235 #if defined (CRAY) && defined (CRAY_STACKSEG_END) 00236 00237 #ifdef DEBUG_I00AFUNC 00238 #include <stdio.h> 00239 #endif 00240 00241 #ifndef CRAY_STACK 00242 #define CRAY_STACK 00243 #ifndef CRAY2 00244 /* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */ 00245 struct stack_control_header 00246 { 00247 long shgrow:32; /* Number of times stack has grown. */ 00248 long shaseg:32; /* Size of increments to stack. */ 00249 long shhwm:32; /* High water mark of stack. */ 00250 long shsize:32; /* Current size of stack (all segments). */ 00251 }; 00252 00253 /* The stack segment linkage control information occurs at 00254 the high-address end of a stack segment. (The stack 00255 grows from low addresses to high addresses.) The initial 00256 part of the stack segment linkage control information is 00257 0200 (octal) words. This provides for register storage 00258 for the routine which overflows the stack. */ 00259 00260 struct stack_segment_linkage 00261 { 00262 long ss[0200]; /* 0200 overflow words. */ 00263 long sssize:32; /* Number of words in this segment. */ 00264 long ssbase:32; /* Offset to stack base. */ 00265 long:32; 00266 long sspseg:32; /* Offset to linkage control of previous 00267 segment of stack. */ 00268 long:32; 00269 long sstcpt:32; /* Pointer to task common address block. */ 00270 long sscsnm; /* Private control structure number for 00271 microtasking. */ 00272 long ssusr1; /* Reserved for user. */ 00273 long ssusr2; /* Reserved for user. */ 00274 long sstpid; /* Process ID for pid based multi-tasking. */ 00275 long ssgvup; /* Pointer to multitasking thread giveup. */ 00276 long sscray[7]; /* Reserved for Cray Research. */ 00277 long ssa0; 00278 long ssa1; 00279 long ssa2; 00280 long ssa3; 00281 long ssa4; 00282 long ssa5; 00283 long ssa6; 00284 long ssa7; 00285 long sss0; 00286 long sss1; 00287 long sss2; 00288 long sss3; 00289 long sss4; 00290 long sss5; 00291 long sss6; 00292 long sss7; 00293 }; 00294 00295 #else /* CRAY2 */ 00296 /* The following structure defines the vector of words 00297 returned by the STKSTAT library routine. */ 00298 struct stk_stat 00299 { 00300 long now; /* Current total stack size. */ 00301 long maxc; /* Amount of contiguous space which would 00302 be required to satisfy the maximum 00303 stack demand to date. */ 00304 long high_water; /* Stack high-water mark. */ 00305 long overflows; /* Number of stack overflow ($STKOFEN) calls. */ 00306 long hits; /* Number of internal buffer hits. */ 00307 long extends; /* Number of block extensions. */ 00308 long stko_mallocs; /* Block allocations by $STKOFEN. */ 00309 long underflows; /* Number of stack underflow calls ($STKRETN). */ 00310 long stko_free; /* Number of deallocations by $STKRETN. */ 00311 long stkm_free; /* Number of deallocations by $STKMRET. */ 00312 long segments; /* Current number of stack segments. */ 00313 long maxs; /* Maximum number of stack segments so far. */ 00314 long pad_size; /* Stack pad size. */ 00315 long current_address; /* Current stack segment address. */ 00316 long current_size; /* Current stack segment size. This 00317 number is actually corrupted by STKSTAT to 00318 include the fifteen word trailer area. */ 00319 long initial_address; /* Address of initial segment. */ 00320 long initial_size; /* Size of initial segment. */ 00321 }; 00322 00323 /* The following structure describes the data structure which trails 00324 any stack segment. I think that the description in 'asdef' is 00325 out of date. I only describe the parts that I am sure about. */ 00326 00327 struct stk_trailer 00328 { 00329 long this_address; /* Address of this block. */ 00330 long this_size; /* Size of this block (does not include 00331 this trailer). */ 00332 long unknown2; 00333 long unknown3; 00334 long link; /* Address of trailer block of previous 00335 segment. */ 00336 long unknown5; 00337 long unknown6; 00338 long unknown7; 00339 long unknown8; 00340 long unknown9; 00341 long unknown10; 00342 long unknown11; 00343 long unknown12; 00344 long unknown13; 00345 long unknown14; 00346 }; 00347 00348 #endif /* CRAY2 */ 00349 #endif /* not CRAY_STACK */ 00350 00351 #ifdef CRAY2 00352 /* Determine a "stack measure" for an arbitrary ADDRESS. 00353 I doubt that "lint" will like this much. */ 00354 00355 static long 00356 i00afunc (long *address) 00357 { 00358 struct stk_stat status; 00359 struct stk_trailer *trailer; 00360 long *block, size; 00361 long result = 0; 00362 00363 /* We want to iterate through all of the segments. The first 00364 step is to get the stack status structure. We could do this 00365 more quickly and more directly, perhaps, by referencing the 00366 $LM00 common block, but I know that this works. */ 00367 00368 STKSTAT (&status); 00369 00370 /* Set up the iteration. */ 00371 00372 trailer = (struct stk_trailer *) (status.current_address 00373 + status.current_size 00374 - 15); 00375 00376 /* There must be at least one stack segment. Therefore it is 00377 a fatal error if "trailer" is null. */ 00378 00379 if (trailer == 0) 00380 abort (); 00381 00382 /* Discard segments that do not contain our argument address. */ 00383 00384 while (trailer != 0) 00385 { 00386 block = (long *) trailer->this_address; 00387 size = trailer->this_size; 00388 if (block == 0 || size == 0) 00389 abort (); 00390 trailer = (struct stk_trailer *) trailer->link; 00391 if ((block <= address) && (address < (block + size))) 00392 break; 00393 } 00394 00395 /* Set the result to the offset in this segment and add the sizes 00396 of all predecessor segments. */ 00397 00398 result = address - block; 00399 00400 if (trailer == 0) 00401 { 00402 return result; 00403 } 00404 00405 do 00406 { 00407 if (trailer->this_size <= 0) 00408 abort (); 00409 result += trailer->this_size; 00410 trailer = (struct stk_trailer *) trailer->link; 00411 } 00412 while (trailer != 0); 00413 00414 /* We are done. Note that if you present a bogus address (one 00415 not in any segment), you will get a different number back, formed 00416 from subtracting the address of the first block. This is probably 00417 not what you want. */ 00418 00419 return (result); 00420 } 00421 00422 #else /* not CRAY2 */ 00423 /* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP. 00424 Determine the number of the cell within the stack, 00425 given the address of the cell. The purpose of this 00426 routine is to linearize, in some sense, stack addresses 00427 for alloca. */ 00428 00429 static long 00430 i00afunc (long address) 00431 { 00432 long stkl = 0; 00433 00434 long size, pseg, this_segment, stack; 00435 long result = 0; 00436 00437 struct stack_segment_linkage *ssptr; 00438 00439 /* Register B67 contains the address of the end of the 00440 current stack segment. If you (as a subprogram) store 00441 your registers on the stack and find that you are past 00442 the contents of B67, you have overflowed the segment. 00443 00444 B67 also points to the stack segment linkage control 00445 area, which is what we are really interested in. */ 00446 00447 stkl = CRAY_STACKSEG_END (); 00448 ssptr = (struct stack_segment_linkage *) stkl; 00449 00450 /* If one subtracts 'size' from the end of the segment, 00451 one has the address of the first word of the segment. 00452 00453 If this is not the first segment, 'pseg' will be 00454 nonzero. */ 00455 00456 pseg = ssptr->sspseg; 00457 size = ssptr->sssize; 00458 00459 this_segment = stkl - size; 00460 00461 /* It is possible that calling this routine itself caused 00462 a stack overflow. Discard stack segments which do not 00463 contain the target address. */ 00464 00465 while (!(this_segment <= address && address <= stkl)) 00466 { 00467 #ifdef DEBUG_I00AFUNC 00468 fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl); 00469 #endif 00470 if (pseg == 0) 00471 break; 00472 stkl = stkl - pseg; 00473 ssptr = (struct stack_segment_linkage *) stkl; 00474 size = ssptr->sssize; 00475 pseg = ssptr->sspseg; 00476 this_segment = stkl - size; 00477 } 00478 00479 result = address - this_segment; 00480 00481 /* If you subtract pseg from the current end of the stack, 00482 you get the address of the previous stack segment's end. 00483 This seems a little convoluted to me, but I'll bet you save 00484 a cycle somewhere. */ 00485 00486 while (pseg != 0) 00487 { 00488 #ifdef DEBUG_I00AFUNC 00489 fprintf (stderr, "%011o %011o\n", pseg, size); 00490 #endif 00491 stkl = stkl - pseg; 00492 ssptr = (struct stack_segment_linkage *) stkl; 00493 size = ssptr->sssize; 00494 pseg = ssptr->sspseg; 00495 result += size; 00496 } 00497 return (result); 00498 } 00499 00500 #endif /* not CRAY2 */ 00501 #endif /* CRAY */ 00502 00503 #endif /* no alloca */ 00504 #endif /* not GCC version 2 */