|
0
|
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
|
|
|
26 /* Authorsip:
|
|
|
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. */
|
|
185
|
79
|
|
0
|
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
|
|
118
|
89 #ifndef WINDOWSNT
|
|
0
|
90 #define NULL 0
|
|
118
|
91 #endif
|
|
0
|
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
|
|
|
103 #ifndef emacs
|
|
|
104 #define malloc xmalloc
|
|
|
105 #endif
|
|
118
|
106 #ifndef WINDOWSNT
|
|
0
|
107 extern pointer malloc ();
|
|
118
|
108 #else
|
|
|
109 extern void *malloc();
|
|
|
110 #endif
|
|
0
|
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: */
|
|
|
196 register char *depth = ADDRESS_FUNCTION (probe);
|
|
|
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 {
|
|
|
207 register header *hp; /* Traverses linked list. */
|
|
|
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 {
|
|
|
213 register header *np = hp->h.next;
|
|
|
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 {
|
|
|
231 register pointer new = malloc (sizeof (header) + size);
|
|
|
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 */
|
