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