Mercurial > hg > xemacs-beta

comparison src/alloca.c @ 0:376386a54a3c r19-14

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