(file) Return to alloca.c CVS log (file) (dir) Up to [RizwankCVS] / testProject / compat

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

Rizwan Kassim
Powered by
ViewCVS 0.9.2