Annotation of OpenXM/src/asir-doc/jtexindex/C/alloca.c, Revision 1.1.1.1
1.1 noro 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: #ifdef HAVE_CONFIG_H
25: #include <config.h>
26: #endif
27:
28: #ifdef emacs
29: #include "blockinput.h"
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: #ifdef emacs
180: BLOCK_INPUT;
181: #endif
182:
183: for (hp = last_alloca_header; hp != NULL;)
184: if ((STACK_DIR > 0 && hp->h.deep > depth)
185: || (STACK_DIR < 0 && hp->h.deep < depth))
186: {
187: register header *np = hp->h.next;
188:
189: free ((pointer) hp); /* Collect garbage. */
190:
191: hp = np; /* -> next header. */
192: }
193: else
194: break; /* Rest are not deeper. */
195:
196: last_alloca_header = hp; /* -> last valid storage. */
197:
198: #ifdef emacs
199: UNBLOCK_INPUT;
200: #endif
201: }
202:
203: if (size == 0)
204: return NULL; /* No allocation required. */
205:
206: /* Allocate combined header + user data storage. */
207:
208: {
209: register pointer new = malloc (sizeof (header) + size);
210: /* Address of header. */
211:
212: ((header *) new)->h.next = last_alloca_header;
213: ((header *) new)->h.deep = depth;
214:
215: last_alloca_header = (header *) new;
216:
217: /* User storage begins just after header. */
218:
219: return (pointer) ((char *) new + sizeof (header));
220: }
221: }
222:
223: #if defined (CRAY) && defined (CRAY_STACKSEG_END)
224:
225: #ifdef DEBUG_I00AFUNC
226: #include <stdio.h>
227: #endif
228:
229: #ifndef CRAY_STACK
230: #define CRAY_STACK
231: #ifndef CRAY2
232: /* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */
233: struct stack_control_header
234: {
235: long shgrow:32; /* Number of times stack has grown. */
236: long shaseg:32; /* Size of increments to stack. */
237: long shhwm:32; /* High water mark of stack. */
238: long shsize:32; /* Current size of stack (all segments). */
239: };
240:
241: /* The stack segment linkage control information occurs at
242: the high-address end of a stack segment. (The stack
243: grows from low addresses to high addresses.) The initial
244: part of the stack segment linkage control information is
245: 0200 (octal) words. This provides for register storage
246: for the routine which overflows the stack. */
247:
248: struct stack_segment_linkage
249: {
250: long ss[0200]; /* 0200 overflow words. */
251: long sssize:32; /* Number of words in this segment. */
252: long ssbase:32; /* Offset to stack base. */
253: long:32;
254: long sspseg:32; /* Offset to linkage control of previous
255: segment of stack. */
256: long:32;
257: long sstcpt:32; /* Pointer to task common address block. */
258: long sscsnm; /* Private control structure number for
259: microtasking. */
260: long ssusr1; /* Reserved for user. */
261: long ssusr2; /* Reserved for user. */
262: long sstpid; /* Process ID for pid based multi-tasking. */
263: long ssgvup; /* Pointer to multitasking thread giveup. */
264: long sscray[7]; /* Reserved for Cray Research. */
265: long ssa0;
266: long ssa1;
267: long ssa2;
268: long ssa3;
269: long ssa4;
270: long ssa5;
271: long ssa6;
272: long ssa7;
273: long sss0;
274: long sss1;
275: long sss2;
276: long sss3;
277: long sss4;
278: long sss5;
279: long sss6;
280: long sss7;
281: };
282:
283: #else /* CRAY2 */
284: /* The following structure defines the vector of words
285: returned by the STKSTAT library routine. */
286: struct stk_stat
287: {
288: long now; /* Current total stack size. */
289: long maxc; /* Amount of contiguous space which would
290: be required to satisfy the maximum
291: stack demand to date. */
292: long high_water; /* Stack high-water mark. */
293: long overflows; /* Number of stack overflow ($STKOFEN) calls. */
294: long hits; /* Number of internal buffer hits. */
295: long extends; /* Number of block extensions. */
296: long stko_mallocs; /* Block allocations by $STKOFEN. */
297: long underflows; /* Number of stack underflow calls ($STKRETN). */
298: long stko_free; /* Number of deallocations by $STKRETN. */
299: long stkm_free; /* Number of deallocations by $STKMRET. */
300: long segments; /* Current number of stack segments. */
301: long maxs; /* Maximum number of stack segments so far. */
302: long pad_size; /* Stack pad size. */
303: long current_address; /* Current stack segment address. */
304: long current_size; /* Current stack segment size. This
305: number is actually corrupted by STKSTAT to
306: include the fifteen word trailer area. */
307: long initial_address; /* Address of initial segment. */
308: long initial_size; /* Size of initial segment. */
309: };
310:
311: /* The following structure describes the data structure which trails
312: any stack segment. I think that the description in 'asdef' is
313: out of date. I only describe the parts that I am sure about. */
314:
315: struct stk_trailer
316: {
317: long this_address; /* Address of this block. */
318: long this_size; /* Size of this block (does not include
319: this trailer). */
320: long unknown2;
321: long unknown3;
322: long link; /* Address of trailer block of previous
323: segment. */
324: long unknown5;
325: long unknown6;
326: long unknown7;
327: long unknown8;
328: long unknown9;
329: long unknown10;
330: long unknown11;
331: long unknown12;
332: long unknown13;
333: long unknown14;
334: };
335:
336: #endif /* CRAY2 */
337: #endif /* not CRAY_STACK */
338:
339: #ifdef CRAY2
340: /* Determine a "stack measure" for an arbitrary ADDRESS.
341: I doubt that "lint" will like this much. */
342:
343: static long
344: i00afunc (long *address)
345: {
346: struct stk_stat status;
347: struct stk_trailer *trailer;
348: long *block, size;
349: long result = 0;
350:
351: /* We want to iterate through all of the segments. The first
352: step is to get the stack status structure. We could do this
353: more quickly and more directly, perhaps, by referencing the
354: $LM00 common block, but I know that this works. */
355:
356: STKSTAT (&status);
357:
358: /* Set up the iteration. */
359:
360: trailer = (struct stk_trailer *) (status.current_address
361: + status.current_size
362: - 15);
363:
364: /* There must be at least one stack segment. Therefore it is
365: a fatal error if "trailer" is null. */
366:
367: if (trailer == 0)
368: abort ();
369:
370: /* Discard segments that do not contain our argument address. */
371:
372: while (trailer != 0)
373: {
374: block = (long *) trailer->this_address;
375: size = trailer->this_size;
376: if (block == 0 || size == 0)
377: abort ();
378: trailer = (struct stk_trailer *) trailer->link;
379: if ((block <= address) && (address < (block + size)))
380: break;
381: }
382:
383: /* Set the result to the offset in this segment and add the sizes
384: of all predecessor segments. */
385:
386: result = address - block;
387:
388: if (trailer == 0)
389: {
390: return result;
391: }
392:
393: do
394: {
395: if (trailer->this_size <= 0)
396: abort ();
397: result += trailer->this_size;
398: trailer = (struct stk_trailer *) trailer->link;
399: }
400: while (trailer != 0);
401:
402: /* We are done. Note that if you present a bogus address (one
403: not in any segment), you will get a different number back, formed
404: from subtracting the address of the first block. This is probably
405: not what you want. */
406:
407: return (result);
408: }
409:
410: #else /* not CRAY2 */
411: /* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP.
412: Determine the number of the cell within the stack,
413: given the address of the cell. The purpose of this
414: routine is to linearize, in some sense, stack addresses
415: for alloca. */
416:
417: static long
418: i00afunc (long address)
419: {
420: long stkl = 0;
421:
422: long size, pseg, this_segment, stack;
423: long result = 0;
424:
425: struct stack_segment_linkage *ssptr;
426:
427: /* Register B67 contains the address of the end of the
428: current stack segment. If you (as a subprogram) store
429: your registers on the stack and find that you are past
430: the contents of B67, you have overflowed the segment.
431:
432: B67 also points to the stack segment linkage control
433: area, which is what we are really interested in. */
434:
435: stkl = CRAY_STACKSEG_END ();
436: ssptr = (struct stack_segment_linkage *) stkl;
437:
438: /* If one subtracts 'size' from the end of the segment,
439: one has the address of the first word of the segment.
440:
441: If this is not the first segment, 'pseg' will be
442: nonzero. */
443:
444: pseg = ssptr->sspseg;
445: size = ssptr->sssize;
446:
447: this_segment = stkl - size;
448:
449: /* It is possible that calling this routine itself caused
450: a stack overflow. Discard stack segments which do not
451: contain the target address. */
452:
453: while (!(this_segment <= address && address <= stkl))
454: {
455: #ifdef DEBUG_I00AFUNC
456: fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl);
457: #endif
458: if (pseg == 0)
459: break;
460: stkl = stkl - pseg;
461: ssptr = (struct stack_segment_linkage *) stkl;
462: size = ssptr->sssize;
463: pseg = ssptr->sspseg;
464: this_segment = stkl - size;
465: }
466:
467: result = address - this_segment;
468:
469: /* If you subtract pseg from the current end of the stack,
470: you get the address of the previous stack segment's end.
471: This seems a little convoluted to me, but I'll bet you save
472: a cycle somewhere. */
473:
474: while (pseg != 0)
475: {
476: #ifdef DEBUG_I00AFUNC
477: fprintf (stderr, "%011o %011o\n", pseg, size);
478: #endif
479: stkl = stkl - pseg;
480: ssptr = (struct stack_segment_linkage *) stkl;
481: size = ssptr->sssize;
482: pseg = ssptr->sspseg;
483: result += size;
484: }
485: return (result);
486: }
487:
488: #endif /* not CRAY2 */
489: #endif /* CRAY */
490:
491: #endif /* no alloca */
492: #endif /* not GCC version 2 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>