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