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