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