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