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