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