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