| 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 <[email protected]> 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 | /*
|
|---|
| 25 |
|
|---|
| 26 | @deftypefn Replacement void* alloca (size_t @var{size})
|
|---|
| 27 |
|
|---|
| 28 | This function allocates memory which will be automatically reclaimed
|
|---|
| 29 | after the procedure exits. The @libib{} implementation does not free
|
|---|
| 30 | the memory immediately but will do so eventually during subsequent
|
|---|
| 31 | calls to this function. Memory is allocated using @code{xmalloc} under
|
|---|
| 32 | normal circumstances.
|
|---|
| 33 |
|
|---|
| 34 | The header file @file{alloca-conf.h} can be used in conjunction with the
|
|---|
| 35 | GNU Autoconf test @code{AC_FUNC_ALLOCA} to test for and properly make
|
|---|
| 36 | available this function. The @code{AC_FUNC_ALLOCA} test requires that
|
|---|
| 37 | client code use a block of preprocessor code to be safe (see the Autoconf
|
|---|
| 38 | manual for more); this header incorporates that logic and more, including
|
|---|
| 39 | the possibility of a GCC built-in function.
|
|---|
| 40 |
|
|---|
| 41 | @end deftypefn
|
|---|
| 42 |
|
|---|
| 43 | */
|
|---|
| 44 |
|
|---|
| 45 | #ifdef HAVE_CONFIG_H
|
|---|
| 46 | #include <config.h>
|
|---|
| 47 | #endif
|
|---|
| 48 |
|
|---|
| 49 | #include <libiberty.h>
|
|---|
| 50 |
|
|---|
| 51 | #ifdef HAVE_STRING_H
|
|---|
| 52 | #include <string.h>
|
|---|
| 53 | #endif
|
|---|
| 54 | #ifdef HAVE_STDLIB_H
|
|---|
| 55 | #include <stdlib.h>
|
|---|
| 56 | #endif
|
|---|
| 57 |
|
|---|
| 58 | /* These variables are used by the ASTRDUP implementation that relies
|
|---|
| 59 | on C_alloca. */
|
|---|
| 60 | const char *libiberty_optr;
|
|---|
| 61 | char *libiberty_nptr;
|
|---|
| 62 | unsigned long libiberty_len;
|
|---|
| 63 |
|
|---|
| 64 | /* If your stack is a linked list of frames, you have to
|
|---|
| 65 | provide an "address metric" ADDRESS_FUNCTION macro. */
|
|---|
| 66 |
|
|---|
| 67 | #if defined (CRAY) && defined (CRAY_STACKSEG_END)
|
|---|
| 68 | static long i00afunc ();
|
|---|
| 69 | #define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
|
|---|
| 70 | #else
|
|---|
| 71 | #define ADDRESS_FUNCTION(arg) &(arg)
|
|---|
| 72 | #endif
|
|---|
| 73 |
|
|---|
| 74 | #ifndef NULL
|
|---|
| 75 | #define NULL 0
|
|---|
| 76 | #endif
|
|---|
| 77 |
|
|---|
| 78 | /* Define STACK_DIRECTION if you know the direction of stack
|
|---|
| 79 | growth for your system; otherwise it will be automatically
|
|---|
| 80 | deduced at run-time.
|
|---|
| 81 |
|
|---|
| 82 | STACK_DIRECTION > 0 => grows toward higher addresses
|
|---|
| 83 | STACK_DIRECTION < 0 => grows toward lower addresses
|
|---|
| 84 | STACK_DIRECTION = 0 => direction of growth unknown */
|
|---|
| 85 |
|
|---|
| 86 | #ifndef STACK_DIRECTION
|
|---|
| 87 | #define STACK_DIRECTION 0 /* Direction unknown. */
|
|---|
| 88 | #endif
|
|---|
| 89 |
|
|---|
| 90 | #if STACK_DIRECTION != 0
|
|---|
| 91 |
|
|---|
| 92 | #define STACK_DIR STACK_DIRECTION /* Known at compile-time. */
|
|---|
| 93 |
|
|---|
| 94 | #else /* STACK_DIRECTION == 0; need run-time code. */
|
|---|
| 95 |
|
|---|
| 96 | static int stack_dir; /* 1 or -1 once known. */
|
|---|
| 97 | #define STACK_DIR stack_dir
|
|---|
| 98 |
|
|---|
| 99 | static void
|
|---|
| 100 | find_stack_direction ()
|
|---|
| 101 | {
|
|---|
| 102 | static char *addr = NULL; /* Address of first `dummy', once known. */
|
|---|
| 103 | auto char dummy; /* To get stack address. */
|
|---|
| 104 |
|
|---|
| 105 | if (addr == NULL)
|
|---|
| 106 | { /* Initial entry. */
|
|---|
| 107 | addr = ADDRESS_FUNCTION (dummy);
|
|---|
| 108 |
|
|---|
| 109 | find_stack_direction (); /* Recurse once. */
|
|---|
| 110 | }
|
|---|
| 111 | else
|
|---|
| 112 | {
|
|---|
| 113 | /* Second entry. */
|
|---|
| 114 | if (ADDRESS_FUNCTION (dummy) > addr)
|
|---|
| 115 | stack_dir = 1; /* Stack grew upward. */
|
|---|
| 116 | else
|
|---|
| 117 | stack_dir = -1; /* Stack grew downward. */
|
|---|
| 118 | }
|
|---|
| 119 | }
|
|---|
| 120 |
|
|---|
| 121 | #endif /* STACK_DIRECTION == 0 */
|
|---|
| 122 |
|
|---|
| 123 | /* An "alloca header" is used to:
|
|---|
| 124 | (a) chain together all alloca'ed blocks;
|
|---|
| 125 | (b) keep track of stack depth.
|
|---|
| 126 |
|
|---|
| 127 | It is very important that sizeof(header) agree with malloc
|
|---|
| 128 | alignment chunk size. The following default should work okay. */
|
|---|
| 129 |
|
|---|
| 130 | #ifndef ALIGN_SIZE
|
|---|
| 131 | #define ALIGN_SIZE sizeof(double)
|
|---|
| 132 | #endif
|
|---|
| 133 |
|
|---|
| 134 | typedef union hdr
|
|---|
| 135 | {
|
|---|
| 136 | char align[ALIGN_SIZE]; /* To force sizeof(header). */
|
|---|
| 137 | struct
|
|---|
| 138 | {
|
|---|
| 139 | union hdr *next; /* For chaining headers. */
|
|---|
| 140 | char *deep; /* For stack depth measure. */
|
|---|
| 141 | } h;
|
|---|
| 142 | } header;
|
|---|
| 143 |
|
|---|
| 144 | static header *last_alloca_header = NULL; /* -> last alloca header. */
|
|---|
| 145 |
|
|---|
| 146 | /* Return a pointer to at least SIZE bytes of storage,
|
|---|
| 147 | which will be automatically reclaimed upon exit from
|
|---|
| 148 | the procedure that called alloca. Originally, this space
|
|---|
| 149 | was supposed to be taken from the current stack frame of the
|
|---|
| 150 | caller, but that method cannot be made to work for some
|
|---|
| 151 | implementations of C, for example under Gould's UTX/32. */
|
|---|
| 152 |
|
|---|
| 153 | /* @undocumented C_alloca */
|
|---|
| 154 |
|
|---|
| 155 | PTR
|
|---|
| 156 | C_alloca (size)
|
|---|
| 157 | size_t size;
|
|---|
| 158 | {
|
|---|
| 159 | auto char probe; /* Probes stack depth: */
|
|---|
| 160 | register char *depth = ADDRESS_FUNCTION (probe);
|
|---|
| 161 |
|
|---|
| 162 | #if STACK_DIRECTION == 0
|
|---|
| 163 | if (STACK_DIR == 0) /* Unknown growth direction. */
|
|---|
| 164 | find_stack_direction ();
|
|---|
| 165 | #endif
|
|---|
| 166 |
|
|---|
| 167 | /* Reclaim garbage, defined as all alloca'd storage that
|
|---|
| 168 | was allocated from deeper in the stack than currently. */
|
|---|
| 169 |
|
|---|
| 170 | {
|
|---|
| 171 | register header *hp; /* Traverses linked list. */
|
|---|
| 172 |
|
|---|
| 173 | for (hp = last_alloca_header; hp != NULL;)
|
|---|
| 174 | if ((STACK_DIR > 0 && hp->h.deep > depth)
|
|---|
| 175 | || (STACK_DIR < 0 && hp->h.deep < depth))
|
|---|
| 176 | {
|
|---|
| 177 | register header *np = hp->h.next;
|
|---|
| 178 |
|
|---|
| 179 | free ((PTR) hp); /* Collect garbage. */
|
|---|
| 180 |
|
|---|
| 181 | hp = np; /* -> next header. */
|
|---|
| 182 | }
|
|---|
| 183 | else
|
|---|
| 184 | break; /* Rest are not deeper. */
|
|---|
| 185 |
|
|---|
| 186 | last_alloca_header = hp; /* -> last valid storage. */
|
|---|
| 187 | }
|
|---|
| 188 |
|
|---|
| 189 | if (size == 0)
|
|---|
| 190 | return NULL; /* No allocation required. */
|
|---|
| 191 |
|
|---|
| 192 | /* Allocate combined header + user data storage. */
|
|---|
| 193 |
|
|---|
| 194 | {
|
|---|
| 195 | register PTR new = xmalloc (sizeof (header) + size);
|
|---|
| 196 | /* Address of header. */
|
|---|
| 197 |
|
|---|
| 198 | if (new == 0)
|
|---|
| 199 | abort();
|
|---|
| 200 |
|
|---|
| 201 | ((header *) new)->h.next = last_alloca_header;
|
|---|
| 202 | ((header *) new)->h.deep = depth;
|
|---|
| 203 |
|
|---|
| 204 | last_alloca_header = (header *) new;
|
|---|
| 205 |
|
|---|
| 206 | /* User storage begins just after header. */
|
|---|
| 207 |
|
|---|
| 208 | return (PTR) ((char *) new + sizeof (header));
|
|---|
| 209 | }
|
|---|
| 210 | }
|
|---|
| 211 |
|
|---|
| 212 | #if defined (CRAY) && defined (CRAY_STACKSEG_END)
|
|---|
| 213 |
|
|---|
| 214 | #ifdef DEBUG_I00AFUNC
|
|---|
| 215 | #include <stdio.h>
|
|---|
| 216 | #endif
|
|---|
| 217 |
|
|---|
| 218 | #ifndef CRAY_STACK
|
|---|
| 219 | #define CRAY_STACK
|
|---|
| 220 | #ifndef CRAY2
|
|---|
| 221 | /* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */
|
|---|
| 222 | struct stack_control_header
|
|---|
| 223 | {
|
|---|
| 224 | long shgrow:32; /* Number of times stack has grown. */
|
|---|
| 225 | long shaseg:32; /* Size of increments to stack. */
|
|---|
| 226 | long shhwm:32; /* High water mark of stack. */
|
|---|
| 227 | long shsize:32; /* Current size of stack (all segments). */
|
|---|
| 228 | };
|
|---|
| 229 |
|
|---|
| 230 | /* The stack segment linkage control information occurs at
|
|---|
| 231 | the high-address end of a stack segment. (The stack
|
|---|
| 232 | grows from low addresses to high addresses.) The initial
|
|---|
| 233 | part of the stack segment linkage control information is
|
|---|
| 234 | 0200 (octal) words. This provides for register storage
|
|---|
| 235 | for the routine which overflows the stack. */
|
|---|
| 236 |
|
|---|
| 237 | struct stack_segment_linkage
|
|---|
| 238 | {
|
|---|
| 239 | long ss[0200]; /* 0200 overflow words. */
|
|---|
| 240 | long sssize:32; /* Number of words in this segment. */
|
|---|
| 241 | long ssbase:32; /* Offset to stack base. */
|
|---|
| 242 | long:32;
|
|---|
| 243 | long sspseg:32; /* Offset to linkage control of previous
|
|---|
| 244 | segment of stack. */
|
|---|
| 245 | long:32;
|
|---|
| 246 | long sstcpt:32; /* Pointer to task common address block. */
|
|---|
| 247 | long sscsnm; /* Private control structure number for
|
|---|
| 248 | microtasking. */
|
|---|
| 249 | long ssusr1; /* Reserved for user. */
|
|---|
| 250 | long ssusr2; /* Reserved for user. */
|
|---|
| 251 | long sstpid; /* Process ID for pid based multi-tasking. */
|
|---|
| 252 | long ssgvup; /* Pointer to multitasking thread giveup. */
|
|---|
| 253 | long sscray[7]; /* Reserved for Cray Research. */
|
|---|
| 254 | long ssa0;
|
|---|
| 255 | long ssa1;
|
|---|
| 256 | long ssa2;
|
|---|
| 257 | long ssa3;
|
|---|
| 258 | long ssa4;
|
|---|
| 259 | long ssa5;
|
|---|
| 260 | long ssa6;
|
|---|
| 261 | long ssa7;
|
|---|
| 262 | long sss0;
|
|---|
| 263 | long sss1;
|
|---|
| 264 | long sss2;
|
|---|
| 265 | long sss3;
|
|---|
| 266 | long sss4;
|
|---|
| 267 | long sss5;
|
|---|
| 268 | long sss6;
|
|---|
| 269 | long sss7;
|
|---|
| 270 | };
|
|---|
| 271 |
|
|---|
| 272 | #else /* CRAY2 */
|
|---|
| 273 | /* The following structure defines the vector of words
|
|---|
| 274 | returned by the STKSTAT library routine. */
|
|---|
| 275 | struct stk_stat
|
|---|
| 276 | {
|
|---|
| 277 | long now; /* Current total stack size. */
|
|---|
| 278 | long maxc; /* Amount of contiguous space which would
|
|---|
| 279 | be required to satisfy the maximum
|
|---|
| 280 | stack demand to date. */
|
|---|
| 281 | long high_water; /* Stack high-water mark. */
|
|---|
| 282 | long overflows; /* Number of stack overflow ($STKOFEN) calls. */
|
|---|
| 283 | long hits; /* Number of internal buffer hits. */
|
|---|
| 284 | long extends; /* Number of block extensions. */
|
|---|
| 285 | long stko_mallocs; /* Block allocations by $STKOFEN. */
|
|---|
| 286 | long underflows; /* Number of stack underflow calls ($STKRETN). */
|
|---|
| 287 | long stko_free; /* Number of deallocations by $STKRETN. */
|
|---|
| 288 | long stkm_free; /* Number of deallocations by $STKMRET. */
|
|---|
| 289 | long segments; /* Current number of stack segments. */
|
|---|
| 290 | long maxs; /* Maximum number of stack segments so far. */
|
|---|
| 291 | long pad_size; /* Stack pad size. */
|
|---|
| 292 | long current_address; /* Current stack segment address. */
|
|---|
| 293 | long current_size; /* Current stack segment size. This
|
|---|
| 294 | number is actually corrupted by STKSTAT to
|
|---|
| 295 | include the fifteen word trailer area. */
|
|---|
| 296 | long initial_address; /* Address of initial segment. */
|
|---|
| 297 | long initial_size; /* Size of initial segment. */
|
|---|
| 298 | };
|
|---|
| 299 |
|
|---|
| 300 | /* The following structure describes the data structure which trails
|
|---|
| 301 | any stack segment. I think that the description in 'asdef' is
|
|---|
| 302 | out of date. I only describe the parts that I am sure about. */
|
|---|
| 303 |
|
|---|
| 304 | struct stk_trailer
|
|---|
| 305 | {
|
|---|
| 306 | long this_address; /* Address of this block. */
|
|---|
| 307 | long this_size; /* Size of this block (does not include
|
|---|
| 308 | this trailer). */
|
|---|
| 309 | long unknown2;
|
|---|
| 310 | long unknown3;
|
|---|
| 311 | long link; /* Address of trailer block of previous
|
|---|
| 312 | segment. */
|
|---|
| 313 | long unknown5;
|
|---|
| 314 | long unknown6;
|
|---|
| 315 | long unknown7;
|
|---|
| 316 | long unknown8;
|
|---|
| 317 | long unknown9;
|
|---|
| 318 | long unknown10;
|
|---|
| 319 | long unknown11;
|
|---|
| 320 | long unknown12;
|
|---|
| 321 | long unknown13;
|
|---|
| 322 | long unknown14;
|
|---|
| 323 | };
|
|---|
| 324 |
|
|---|
| 325 | #endif /* CRAY2 */
|
|---|
| 326 | #endif /* not CRAY_STACK */
|
|---|
| 327 |
|
|---|
| 328 | #ifdef CRAY2
|
|---|
| 329 | /* Determine a "stack measure" for an arbitrary ADDRESS.
|
|---|
| 330 | I doubt that "lint" will like this much. */
|
|---|
| 331 |
|
|---|
| 332 | static long
|
|---|
| 333 | i00afunc (long *address)
|
|---|
| 334 | {
|
|---|
| 335 | struct stk_stat status;
|
|---|
| 336 | struct stk_trailer *trailer;
|
|---|
| 337 | long *block, size;
|
|---|
| 338 | long result = 0;
|
|---|
| 339 |
|
|---|
| 340 | /* We want to iterate through all of the segments. The first
|
|---|
| 341 | step is to get the stack status structure. We could do this
|
|---|
| 342 | more quickly and more directly, perhaps, by referencing the
|
|---|
| 343 | $LM00 common block, but I know that this works. */
|
|---|
| 344 |
|
|---|
| 345 | STKSTAT (&status);
|
|---|
| 346 |
|
|---|
| 347 | /* Set up the iteration. */
|
|---|
| 348 |
|
|---|
| 349 | trailer = (struct stk_trailer *) (status.current_address
|
|---|
| 350 | + status.current_size
|
|---|
| 351 | - 15);
|
|---|
| 352 |
|
|---|
| 353 | /* There must be at least one stack segment. Therefore it is
|
|---|
| 354 | a fatal error if "trailer" is null. */
|
|---|
| 355 |
|
|---|
|
|---|
