Mercurial > hg > xemacs-beta

comparison src/alloca.c @ 428:3ecd8885ac67 r21-2-22

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-22
author cvs
date Mon, 13 Aug 2007 11:28:15 +0200
parents
children abe6d1db359e
comparison
equal deleted inserted replaced
427:0a0253eac470 428:3ecd8885ac67
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 #ifndef WINDOWSNT
90 #define NULL 0
91 #endif
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
106 #ifndef WINDOWSNT
107 extern pointer malloc ();
108 #else
109 extern void *malloc();
110 #endif
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 */