1
/* alloca.c -- allocate automatically reclaimed memory
2
(Mostly) portable public-domain implementation -- D A Gwyn
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.
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.
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.
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. */
24
/* Synched up with: FSF 19.30. */
29
Very few changes for XEmacs.
36
/* XEmacs: If compiling with GCC 2, this file is theoretically not needed.
37
However, alloca() is broken under GCC 2 on many machines: you
38
cannot put a call to alloca() as part of an argument to a function.
40
/* If someone has defined alloca as a macro,
41
there must be some other way alloca is supposed to work. */
42
/* XEmacs sometimes uses the C alloca even when a builtin alloca is available,
43
because it's safer. */
44
#if defined (EMACS_WANTS_C_ALLOCA) || (!defined (alloca) && (!defined (__GNUC__) || __GNUC__ < 2))
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
52
#ifndef STACK_DIRECTION
55
-- must know STACK_DIRECTION at compile-time
56
#endif /* STACK_DIRECTION undefined */
60
/* If your stack is a linked list of frames, you have to
61
provide an "address metric" ADDRESS_FUNCTION macro. */
63
#if defined (CRAY) && defined (CRAY_STACKSEG_END)
65
#define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
67
#define ADDRESS_FUNCTION(arg) &(arg)
70
#ifdef __STDC__ /* XEmacs change */
71
typedef void *pointer;
73
typedef char *pointer;
76
/* XEmacs: With ERROR_CHECK_MALLOC defined, there is no xfree -- it's
77
a macro that does some stuff to try and trap invalid frees,
78
and then calls xfree_1 to actually do the work. */
81
# ifdef ERROR_CHECK_MALLOC
82
void xfree_1 (pointer);
83
# define xfree xfree_1
93
/* Different portions of Emacs need to call different versions of
94
malloc. The Emacs executable needs alloca to call xmalloc, because
95
ordinary malloc isn't protected from input signals. On the other
96
hand, the utilities in lib-src need alloca to call malloc; some of
97
them are very simple, and don't have an xmalloc routine.
99
Non-Emacs programs expect this to call use xmalloc.
101
Callers below should use malloc. */
104
#define malloc xmalloc
107
extern pointer malloc ();
109
extern void *malloc();
112
/* Define STACK_DIRECTION if you know the direction of stack
113
growth for your system; otherwise it will be automatically
116
STACK_DIRECTION > 0 => grows toward higher addresses
117
STACK_DIRECTION < 0 => grows toward lower addresses
118
STACK_DIRECTION = 0 => direction of growth unknown */
120
#ifndef STACK_DIRECTION
121
#define STACK_DIRECTION 0 /* Direction unknown. */
124
#if STACK_DIRECTION != 0
126
#define STACK_DIR STACK_DIRECTION /* Known at compile-time. */
128
#else /* STACK_DIRECTION == 0; need run-time code. */
130
static int stack_dir; /* 1 or -1 once known. */
131
#define STACK_DIR stack_dir
134
find_stack_direction ()
136
static char *addr = NULL; /* Address of first `dummy', once known. */
137
auto char dummy; /* To get stack address. */
140
{ /* Initial entry. */
141
addr = ADDRESS_FUNCTION (dummy);
143
find_stack_direction (); /* Recurse once. */
148
if (ADDRESS_FUNCTION (dummy) > addr)
149
stack_dir = 1; /* Stack grew upward. */
151
stack_dir = -1; /* Stack grew downward. */
155
#endif /* STACK_DIRECTION == 0 */
157
/* An "alloca header" is used to:
158
(a) chain together all alloca'ed blocks;
159
(b) keep track of stack depth.
161
It is very important that sizeof(header) agree with malloc
162
alignment chunk size. The following default should work okay. */
165
#define ALIGN_SIZE sizeof(double)
170
char align[ALIGN_SIZE]; /* To force sizeof(header). */
173
union hdr *next; /* For chaining headers. */
174
char *deep; /* For stack depth measure. */
178
static header *last_alloca_header = NULL; /* -> last alloca header. */
180
/* Return a pointer to at least SIZE bytes of storage,
181
which will be automatically reclaimed upon exit from
182
the procedure that called alloca. Originally, this space
183
was supposed to be taken from the current stack frame of the
184
caller, but that method cannot be made to work for some
185
implementations of C, for example under Gould's UTX/32. */
188
#ifdef EMACS_WANTS_C_ALLOCA
195
auto char probe; /* Probes stack depth: */
196
register char *depth = ADDRESS_FUNCTION (probe);
198
#if STACK_DIRECTION == 0
199
if (STACK_DIR == 0) /* Unknown growth direction. */
200
find_stack_direction ();
203
/* Reclaim garbage, defined as all alloca'd storage that
204
was allocated from deeper in the stack than currently. */
207
register header *hp; /* Traverses linked list. */
209
for (hp = last_alloca_header; hp != NULL;)
210
if ((STACK_DIR > 0 && hp->h.deep > depth)
211
|| (STACK_DIR < 0 && hp->h.deep < depth))
213
register header *np = hp->h.next;
215
free ((pointer) hp); /* Collect garbage. */
217
hp = np; /* -> next header. */
220
break; /* Rest are not deeper. */
222
last_alloca_header = hp; /* -> last valid storage. */
226
return NULL; /* No allocation required. */
228
/* Allocate combined header + user data storage. */
231
register pointer new = malloc (sizeof (header) + size);
232
/* Address of header. */
234
((header *) new)->h.next = last_alloca_header;
235
((header *) new)->h.deep = depth;
237
last_alloca_header = (header *) new;
239
/* User storage begins just after header. */
241
return (pointer) ((char *) new + sizeof (header));
245
#if defined (CRAY) && defined (CRAY_STACKSEG_END)
247
#ifdef DEBUG_I00AFUNC
254
/* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */
255
struct stack_control_header
257
long shgrow:32; /* Number of times stack has grown. */
258
long shaseg:32; /* Size of increments to stack. */
259
long shhwm:32; /* High water mark of stack. */
260
long shsize:32; /* Current size of stack (all segments). */
263
/* The stack segment linkage control information occurs at
264
the high-address end of a stack segment. (The stack
265
grows from low addresses to high addresses.) The initial
266
part of the stack segment linkage control information is
267
0200 (octal) words. This provides for register storage
268
for the routine which overflows the stack. */
270
struct stack_segment_linkage
272
long ss[0200]; /* 0200 overflow words. */
273
long sssize:32; /* Number of words in this segment. */
274
long ssbase:32; /* Offset to stack base. */
276
long sspseg:32; /* Offset to linkage control of previous
279
long sstcpt:32; /* Pointer to task common address block. */
280
long sscsnm; /* Private control structure number for
282
long ssusr1; /* Reserved for user. */
283
long ssusr2; /* Reserved for user. */
284
long sstpid; /* Process ID for pid based multi-tasking. */
285
long ssgvup; /* Pointer to multitasking thread giveup. */
286
long sscray[7]; /* Reserved for Cray Research. */
306
/* The following structure defines the vector of words
307
returned by the STKSTAT library routine. */
310
long now; /* Current total stack size. */
311
long maxc; /* Amount of contiguous space which would
312
be required to satisfy the maximum
313
stack demand to date. */
314
long high_water; /* Stack high-water mark. */
315
long overflows; /* Number of stack overflow ($STKOFEN) calls. */
316
long hits; /* Number of internal buffer hits. */
317
long extends; /* Number of block extensions. */
318
long stko_mallocs; /* Block allocations by $STKOFEN. */
319
long underflows; /* Number of stack underflow calls ($STKRETN). */
320
long stko_free; /* Number of deallocations by $STKRETN. */
321
long stkm_free; /* Number of deallocations by $STKMRET. */
322
long segments; /* Current number of stack segments. */
323
long maxs; /* Maximum number of stack segments so far. */
324
long pad_size; /* Stack pad size. */
325
long current_address; /* Current stack segment address. */
326
long current_size; /* Current stack segment size. This
327
number is actually corrupted by STKSTAT to
328
include the fifteen word trailer area. */
329
long initial_address; /* Address of initial segment. */
330
long initial_size; /* Size of initial segment. */
333
/* The following structure describes the data structure which trails
334
any stack segment. I think that the description in 'asdef' is
335
out of date. I only describe the parts that I am sure about. */
339
long this_address; /* Address of this block. */
340
long this_size; /* Size of this block (does not include
344
long link; /* Address of trailer block of previous
359
#endif /* not CRAY_STACK */
362
/* Determine a "stack measure" for an arbitrary ADDRESS.
363
I doubt that "lint" will like this much. */
366
i00afunc (long *address)
368
struct stk_stat status;
369
struct stk_trailer *trailer;
373
/* We want to iterate through all of the segments. The first
374
step is to get the stack status structure. We could do this
375
more quickly and more directly, perhaps, by referencing the
376
$LM00 common block, but I know that this works. */
380
/* Set up the iteration. */
382
trailer = (struct stk_trailer *) (status.current_address
383
+ status.current_size
386
/* There must be at least one stack segment. Therefore it is
387
a fatal error if "trailer" is null. */
392
/* Discard segments that do not contain our argument address. */
396
block = (long *) trailer->this_address;
397
size = trailer->this_size;
398
if (block == 0 || size == 0)
400
trailer = (struct stk_trailer *) trailer->link;
401
if ((block <= address) && (address < (block + size)))
405
/* Set the result to the offset in this segment and add the sizes
406
of all predecessor segments. */
408
result = address - block;
417
if (trailer->this_size <= 0)
419
result += trailer->this_size;
420
trailer = (struct stk_trailer *) trailer->link;
422
while (trailer != 0);
424
/* We are done. Note that if you present a bogus address (one
425
not in any segment), you will get a different number back, formed
426
from subtracting the address of the first block. This is probably
427
not what you want. */
432
#else /* not CRAY2 */
433
/* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP.
434
Determine the number of the cell within the stack,
435
given the address of the cell. The purpose of this
436
routine is to linearize, in some sense, stack addresses
440
i00afunc (long address)
444
long size, pseg, this_segment, stack;
447
struct stack_segment_linkage *ssptr;
449
/* Register B67 contains the address of the end of the
450
current stack segment. If you (as a subprogram) store
451
your registers on the stack and find that you are past
452
the contents of B67, you have overflowed the segment.
454
B67 also points to the stack segment linkage control
455
area, which is what we are really interested in. */
457
stkl = CRAY_STACKSEG_END ();
458
ssptr = (struct stack_segment_linkage *) stkl;
460
/* If one subtracts 'size' from the end of the segment,
461
one has the address of the first word of the segment.
463
If this is not the first segment, 'pseg' will be
466
pseg = ssptr->sspseg;
467
size = ssptr->sssize;
469
this_segment = stkl - size;
471
/* It is possible that calling this routine itself caused
472
a stack overflow. Discard stack segments which do not
473
contain the target address. */
475
while (!(this_segment <= address && address <= stkl))
477
#ifdef DEBUG_I00AFUNC
478
fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl);
483
ssptr = (struct stack_segment_linkage *) stkl;
484
size = ssptr->sssize;
485
pseg = ssptr->sspseg;
486
this_segment = stkl - size;
489
result = address - this_segment;
491
/* If you subtract pseg from the current end of the stack,
492
you get the address of the previous stack segment's end.
493
This seems a little convoluted to me, but I'll bet you save
494
a cycle somewhere. */
498
#ifdef DEBUG_I00AFUNC
499
fprintf (stderr, "%011o %011o\n", pseg, size);
502
ssptr = (struct stack_segment_linkage *) stkl;
503
size = ssptr->sssize;
504
pseg = ssptr->sspseg;
510
#endif /* not CRAY2 */
513
#endif /* complicated expression at top of file */