|
0
|
1 /* objalloc.c -- routines to allocate memory for objects
|
|
|
2 Copyright 1997 Free Software Foundation, Inc.
|
|
|
3 Written by Ian Lance Taylor, Cygnus Solutions.
|
|
|
4
|
|
|
5 This program is free software; you can redistribute it and/or modify it
|
|
|
6 under the terms of the GNU General Public License as published by the
|
|
|
7 Free Software Foundation; either version 2, or (at your option) any
|
|
|
8 later version.
|
|
|
9
|
|
|
10 This program is distributed in the hope that it will be useful,
|
|
|
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
13 GNU General Public License for more details.
|
|
|
14
|
|
|
15 You should have received a copy of the GNU General Public License
|
|
|
16 along with this program; if not, write to the Free Software
|
|
|
17 Foundation, 51 Franklin Street - Fifth Floor,
|
|
|
18 Boston, MA 02110-1301, USA. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "ansidecl.h"
|
|
|
22
|
|
|
23 #include "objalloc.h"
|
|
|
24
|
|
|
25 /* Get a definition for NULL. */
|
|
|
26 #include <stdio.h>
|
|
|
27
|
|
|
28 #if VMS
|
|
|
29 #include <stdlib.h>
|
|
|
30 #include <unixlib.h>
|
|
|
31 #else
|
|
|
32
|
|
|
33 /* Get a definition for size_t. */
|
|
|
34 #include <stddef.h>
|
|
|
35
|
|
|
36 #ifdef HAVE_STDLIB_H
|
|
|
37 #include <stdlib.h>
|
|
|
38 #else
|
|
|
39 /* For systems with larger pointers than ints, this must be declared. */
|
|
|
40 extern PTR malloc (size_t);
|
|
|
41 extern void free (PTR);
|
|
|
42 #endif
|
|
|
43
|
|
|
44 #endif
|
|
|
45
|
|
|
46 /* These routines allocate space for an object. Freeing allocated
|
|
|
47 space may or may not free all more recently allocated space.
|
|
|
48
|
|
|
49 We handle large and small allocation requests differently. If we
|
|
|
50 don't have enough space in the current block, and the allocation
|
|
|
51 request is for more than 512 bytes, we simply pass it through to
|
|
|
52 malloc. */
|
|
|
53
|
|
|
54 /* The objalloc structure is defined in objalloc.h. */
|
|
|
55
|
|
|
56 /* This structure appears at the start of each chunk. */
|
|
|
57
|
|
|
58 struct objalloc_chunk
|
|
|
59 {
|
|
|
60 /* Next chunk. */
|
|
|
61 struct objalloc_chunk *next;
|
|
|
62 /* If this chunk contains large objects, this is the value of
|
|
|
63 current_ptr when this chunk was allocated. If this chunk
|
|
|
64 contains small objects, this is NULL. */
|
|
|
65 char *current_ptr;
|
|
|
66 };
|
|
|
67
|
|
|
68 /* The aligned size of objalloc_chunk. */
|
|
|
69
|
|
|
70 #define CHUNK_HEADER_SIZE \
|
|
|
71 ((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1) \
|
|
|
72 &~ (OBJALLOC_ALIGN - 1))
|
|
|
73
|
|
|
74 /* We ask for this much memory each time we create a chunk which is to
|
|
|
75 hold small objects. */
|
|
|
76
|
|
|
77 #define CHUNK_SIZE (4096 - 32)
|
|
|
78
|
|
|
79 /* A request for this amount or more is just passed through to malloc. */
|
|
|
80
|
|
|
81 #define BIG_REQUEST (512)
|
|
|
82
|
|
|
83 /* Create an objalloc structure. */
|
|
|
84
|
|
|
85 struct objalloc *
|
|
|
86 objalloc_create (void)
|
|
|
87 {
|
|
|
88 struct objalloc *ret;
|
|
|
89 struct objalloc_chunk *chunk;
|
|
|
90
|
|
|
91 ret = (struct objalloc *) malloc (sizeof *ret);
|
|
|
92 if (ret == NULL)
|
|
|
93 return NULL;
|
|
|
94
|
|
|
95 ret->chunks = (PTR) malloc (CHUNK_SIZE);
|
|
|
96 if (ret->chunks == NULL)
|
|
|
97 {
|
|
|
98 free (ret);
|
|
|
99 return NULL;
|
|
|
100 }
|
|
|
101
|
|
|
102 chunk = (struct objalloc_chunk *) ret->chunks;
|
|
|
103 chunk->next = NULL;
|
|
|
104 chunk->current_ptr = NULL;
|
|
|
105
|
|
|
106 ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
|
|
|
107 ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
|
|
|
108
|
|
|
109 return ret;
|
|
|
110 }
|
|
|
111
|
|
|
112 /* Allocate space from an objalloc structure. */
|
|
|
113
|
|
|
114 PTR
|
|
|
115 _objalloc_alloc (struct objalloc *o, unsigned long len)
|
|
|
116 {
|
|
|
117 /* We avoid confusion from zero sized objects by always allocating
|
|
|
118 at least 1 byte. */
|
|
|
119 if (len == 0)
|
|
|
120 len = 1;
|
|
|
121
|
|
|
122 len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1);
|
|
|
123
|
|
|
124 if (len <= o->current_space)
|
|
|
125 {
|
|
|
126 o->current_ptr += len;
|
|
|
127 o->current_space -= len;
|
|
|
128 return (PTR) (o->current_ptr - len);
|
|
|
129 }
|
|
|
130
|
|
|
131 if (len >= BIG_REQUEST)
|
|
|
132 {
|
|
|
133 char *ret;
|
|
|
134 struct objalloc_chunk *chunk;
|
|
|
135
|
|
|
136 ret = (char *) malloc (CHUNK_HEADER_SIZE + len);
|
|
|
137 if (ret == NULL)
|
|
|
138 return NULL;
|
|
|
139
|
|
|
140 chunk = (struct objalloc_chunk *) ret;
|
|
|
141 chunk->next = (struct objalloc_chunk *) o->chunks;
|
|
|
142 chunk->current_ptr = o->current_ptr;
|
|
|
143
|
|
|
144 o->chunks = (PTR) chunk;
|
|
|
145
|
|
|
146 return (PTR) (ret + CHUNK_HEADER_SIZE);
|
|
|
147 }
|
|
|
148 else
|
|
|
149 {
|
|
|
150 struct objalloc_chunk *chunk;
|
|
|
151
|
|
|
152 chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE);
|
|
|
153 if (chunk == NULL)
|
|
|
154 return NULL;
|
|
|
155 chunk->next = (struct objalloc_chunk *) o->chunks;
|
|
|
156 chunk->current_ptr = NULL;
|
|
|
157
|
|
|
158 o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
|
|
|
159 o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
|
|
|
160
|
|
|
161 o->chunks = (PTR) chunk;
|
|
|
162
|
|
|
163 return objalloc_alloc (o, len);
|
|
|
164 }
|
|
|
165 }
|
|
|
166
|
|
|
167 /* Free an entire objalloc structure. */
|
|
|
168
|
|
|
169 void
|
|
|
170 objalloc_free (struct objalloc *o)
|
|
|
171 {
|
|
|
172 struct objalloc_chunk *l;
|
|
|
173
|
|
|
174 l = (struct objalloc_chunk *) o->chunks;
|
|
|
175 while (l != NULL)
|
|
|
176 {
|
|
|
177 struct objalloc_chunk *next;
|
|
|
178
|
|
|
179 next = l->next;
|
|
|
180 free (l);
|
|
|
181 l = next;
|
|
|
182 }
|
|
|
183
|
|
|
184 free (o);
|
|
|
185 }
|
|
|
186
|
|
|
187 /* Free a block from an objalloc structure. This also frees all more
|
|
|
188 recently allocated blocks. */
|
|
|
189
|
|
|
190 void
|
|
|
191 objalloc_free_block (struct objalloc *o, PTR block)
|
|
|
192 {
|
|
|
193 struct objalloc_chunk *p, *small;
|
|
|
194 char *b = (char *) block;
|
|
|
195
|
|
|
196 /* First set P to the chunk which contains the block we are freeing,
|
|
|
197 and set Q to the last small object chunk we see before P. */
|
|
|
198 small = NULL;
|
|
|
199 for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next)
|
|
|
200 {
|
|
|
201 if (p->current_ptr == NULL)
|
|
|
202 {
|
|
|
203 if (b > (char *) p && b < (char *) p + CHUNK_SIZE)
|
|
|
204 break;
|
|
|
205 small = p;
|
|
|
206 }
|
|
|
207 else
|
|
|
208 {
|
|
|
209 if (b == (char *) p + CHUNK_HEADER_SIZE)
|
|
|
210 break;
|
|
|
211 }
|
|
|
212 }
|
|
|
213
|
|
|
214 /* If we can't find the chunk, the caller has made a mistake. */
|
|
|
215 if (p == NULL)
|
|
|
216 abort ();
|
|
|
217
|
|
|
218 if (p->current_ptr == NULL)
|
|
|
219 {
|
|
|
220 struct objalloc_chunk *q;
|
|
|
221 struct objalloc_chunk *first;
|
|
|
222
|
|
|
223 /* The block is in a chunk containing small objects. We can
|
|
|
224 free every chunk through SMALL, because they have certainly
|
|
|
225 been allocated more recently. After SMALL, we will not see
|
|
|
226 any chunks containing small objects; we can free any big
|
|
|
227 chunk if the current_ptr is greater than or equal to B. We
|
|
|
228 can then reset the new current_ptr to B. */
|
|
|
229
|
|
|
230 first = NULL;
|
|
|
231 q = (struct objalloc_chunk *) o->chunks;
|
|
|
232 while (q != p)
|
|
|
233 {
|
|
|
234 struct objalloc_chunk *next;
|
|
|
235
|
|
|
236 next = q->next;
|
|
|
237 if (small != NULL)
|
|
|
238 {
|
|
|
239 if (small == q)
|
|
|
240 small = NULL;
|
|
|
241 free (q);
|
|
|
242 }
|
|
|
243 else if (q->current_ptr > b)
|
|
|
244 free (q);
|
|
|
245 else if (first == NULL)
|
|
|
246 first = q;
|
|
|
247
|
|
|
248 q = next;
|
|
|
249 }
|
|
|
250
|
|
|
251 if (first == NULL)
|
|
|
252 first = p;
|
|
|
253 o->chunks = (PTR) first;
|
|
|
254
|
|
|
255 /* Now start allocating from this small block again. */
|
|
|
256 o->current_ptr = b;
|
|
|
257 o->current_space = ((char *) p + CHUNK_SIZE) - b;
|
|
|
258 }
|
|
|
259 else
|
|
|
260 {
|
|
|
261 struct objalloc_chunk *q;
|
|
|
262 char *current_ptr;
|
|
|
263
|
|
|
264 /* This block is in a large chunk by itself. We can free
|
|
|
265 everything on the list up to and including this block. We
|
|
|
266 then start allocating from the next chunk containing small
|
|
|
267 objects, setting current_ptr from the value stored with the
|
|
|
268 large chunk we are freeing. */
|
|
|
269
|
|
|
270 current_ptr = p->current_ptr;
|
|
|
271 p = p->next;
|
|
|
272
|
|
|
273 q = (struct objalloc_chunk *) o->chunks;
|
|
|
274 while (q != p)
|
|
|
275 {
|
|
|
276 struct objalloc_chunk *next;
|
|
|
277
|
|
|
278 next = q->next;
|
|
|
279 free (q);
|
|
|
280 q = next;
|
|
|
281 }
|
|
|
282
|
|
|
283 o->chunks = (PTR) p;
|
|
|
284
|
|
|
285 while (p->current_ptr != NULL)
|
|
|
286 p = p->next;
|
|
|
287
|
|
|
288 o->current_ptr = current_ptr;
|
|
|
289 o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr;
|
|
|
290 }
|
|
|
291 }
|
