1 /* alloca.c -- allocate automatically reclaimed memory
2 This file is in the public domain. */
3
4 /* (Mostly) portable implementation -- D A Gwyn
5
6 This implementation of the PWB library alloca function,
7 which is used to allocate space off the run-time stack so
8 that it is automatically reclaimed upon procedure exit,
9 was inspired by discussions with J. Q. Johnson of Cornell.
10 J.Otto Tennant <jot@cray.com> contributed the Cray support.
11
12 There are some preprocessor constants that can
13 be defined when compiling for your specific system, for
14 improved efficiency; however, the defaults should be okay.
15
16 The general concept of this implementation is to keep
17 track of all alloca-allocated blocks, and reclaim any
18 that are found to be deeper in the stack than the current
19 invocation. This heuristic does not reclaim storage as
20 soon as it becomes invalid, but it will do so eventually.
21
22 As a special case, alloca(0) reclaims storage without
23 allocating any. It is a good idea to use alloca(0) in
24 your main control loop, etc. to force garbage collection. */
25
26 #include <config.h>
27
28 #include <alloca.h>
29
30 #include <string.h>
31 #include <stdlib.h>
32
33 /* If compiling with GCC or clang, this file is not needed. */
34 #if !(defined __GNUC__ || defined __clang__)
35
36 /* If someone has defined alloca as a macro,
37 there must be some other way alloca is supposed to work. */
38 # ifndef alloca
39
40 /* Define STACK_DIRECTION if you know the direction of stack
41 growth for your system; otherwise it will be automatically
42 deduced at run-time.
43
44 STACK_DIRECTION > 0 => grows toward higher addresses
45 STACK_DIRECTION < 0 => grows toward lower addresses
46 STACK_DIRECTION = 0 => direction of growth unknown */
47
48 # ifndef STACK_DIRECTION
49 # define STACK_DIRECTION 0 /* Direction unknown. */
50 # endif
51
52 # if STACK_DIRECTION != 0
53
54 # define STACK_DIR STACK_DIRECTION /* Known at compile-time. */
55
56 # else /* STACK_DIRECTION == 0; need run-time code. */
57
58 static int stack_dir; /* 1 or -1 once known. */
59 # define STACK_DIR stack_dir
60
61 static int
62 find_stack_direction (int *addr, int depth)
63 {
64 int dir, dummy = 0;
65 if (! addr)
66 addr = &dummy;
67 *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
68 dir = depth ? find_stack_direction (addr, depth - 1) : 0;
69 return dir + dummy;
70 }
71
72 # endif /* STACK_DIRECTION == 0 */
73
74 /* An "alloca header" is used to:
75 (a) chain together all alloca'ed blocks;
76 (b) keep track of stack depth.
77
78 It is very important that sizeof(header) agree with malloc
79 alignment chunk size. The following default should work okay. */
80
81 # ifndef ALIGN_SIZE
82 # define ALIGN_SIZE sizeof(double)
83 # endif
84
85 typedef union hdr
86 {
87 char align[ALIGN_SIZE]; /* To force sizeof(header). */
88 struct
89 {
90 union hdr *next; /* For chaining headers. */
91 char *deep; /* For stack depth measure. */
92 } h;
93 } header;
94
95 static header *last_alloca_header = NULL; /* -> last alloca header. */
96
97 /* Return a pointer to at least SIZE bytes of storage,
98 which will be automatically reclaimed upon exit from
99 the procedure that called alloca. Originally, this space
100 was supposed to be taken from the current stack frame of the
101 caller, but that method cannot be made to work for some
102 implementations of C, for example under Gould's UTX/32. */
103
104 void *
105 alloca (size_t size)
106 {
107 auto char probe; /* Probes stack depth: */
108 register char *depth = &probe;
109
110 # if STACK_DIRECTION == 0
111 if (STACK_DIR == 0) /* Unknown growth direction. */
112 STACK_DIR = find_stack_direction (NULL, (size & 1) + 20);
113 # endif
114
115 /* Reclaim garbage, defined as all alloca'd storage that
116 was allocated from deeper in the stack than currently. */
117
118 {
119 register header *hp; /* Traverses linked list. */
120
121 for (hp = last_alloca_header; hp != NULL;)
122 if ((STACK_DIR > 0 && hp->h.deep > depth)
123 || (STACK_DIR < 0 && hp->h.deep < depth))
124 {
125 register header *np = hp->h.next;
126
127 free (hp); /* Collect garbage. */
128
129 hp = np; /* -> next header. */
130 }
131 else
132 break; /* Rest are not deeper. */
133
134 last_alloca_header = hp; /* -> last valid storage. */
135 }
136
137 if (size == 0)
138 return NULL; /* No allocation required. */
139
140 /* Allocate combined header + user data storage. */
141
142 {
143 /* Address of header. */
144 register header *new;
145
146 size_t combined_size = sizeof (header) + size;
147 if (combined_size < sizeof (header))
148 memory_full ();
149
150 new = malloc (combined_size);
151
152 if (! new)
153 memory_full ();
154
155 new->h.next = last_alloca_header;
156 new->h.deep = depth;
157
158 last_alloca_header = new;
159
160 /* User storage begins just after header. */
161
162 return (void *) (new + 1);
163 }
164 }
165
166 # endif /* no alloca */
167 #endif /* not GCC || clang */