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