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