|
0
|
1 /* objalloc.c -- routines to allocate memory for objects
|
|
111
|
2 Copyright (C) 1997-2017 Free Software Foundation, Inc.
|
|
0
|
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
|
|
111
|
115 _objalloc_alloc (struct objalloc *o, unsigned long original_len)
|
|
0
|
116 {
|
|
111
|
117 unsigned long len = original_len;
|
|
|
118
|
|
0
|
119 /* We avoid confusion from zero sized objects by always allocating
|
|
|
120 at least 1 byte. */
|
|
|
121 if (len == 0)
|
|
|
122 len = 1;
|
|
|
123
|
|
|
124 len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1);
|
|
|
125
|
|
111
|
126 /* Check for overflow in the alignment operation above and the
|
|
|
127 malloc argument below. */
|
|
|
128 if (len + CHUNK_HEADER_SIZE < original_len)
|
|
|
129 return NULL;
|
|
|
130
|
|
0
|
131 if (len <= o->current_space)
|
|
|
132 {
|
|
|
133 o->current_ptr += len;
|
|
|
134 o->current_space -= len;
|
|
|
135 return (PTR) (o->current_ptr - len);
|
|
|
136 }
|
|
|
137
|
|
|
138 if (len >= BIG_REQUEST)
|
|
|
139 {
|
|
|
140 char *ret;
|
|
|
141 struct objalloc_chunk *chunk;
|
|
|
142
|
|
|
143 ret = (char *) malloc (CHUNK_HEADER_SIZE + len);
|
|
|
144 if (ret == NULL)
|
|
|
145 return NULL;
|
|
|
146
|
|
|
147 chunk = (struct objalloc_chunk *) ret;
|
|
|
148 chunk->next = (struct objalloc_chunk *) o->chunks;
|
|
|
149 chunk->current_ptr = o->current_ptr;
|
|
|
150
|
|
|
151 o->chunks = (PTR) chunk;
|
|
|
152
|
|
|
153 return (PTR) (ret + CHUNK_HEADER_SIZE);
|
|
|
154 }
|
|
|
155 else
|
|
|
156 {
|
|
|
157 struct objalloc_chunk *chunk;
|
|
|
158
|
|
|
159 chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE);
|
|
|
160 if (chunk == NULL)
|
|
|
161 return NULL;
|
|
|
162 chunk->next = (struct objalloc_chunk *) o->chunks;
|
|
|
163 chunk->current_ptr = NULL;
|
|
|
164
|
|
|
165 o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
|
|
|
166 o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
|
|
|
167
|
|
|
168 o->chunks = (PTR) chunk;
|
|
|
169
|
|
|
170 return objalloc_alloc (o, len);
|
|
|
171 }
|
|
|
172 }
|
|
|
173
|
|
|
174 /* Free an entire objalloc structure. */
|
|
|
175
|
|
|
176 void
|
|
|
177 objalloc_free (struct objalloc *o)
|
|
|
178 {
|
|
|
179 struct objalloc_chunk *l;
|
|
|
180
|
|
|
181 l = (struct objalloc_chunk *) o->chunks;
|
|
|
182 while (l != NULL)
|
|
|
183 {
|
|
|
184 struct objalloc_chunk *next;
|
|
|
185
|
|
|
186 next = l->next;
|
|
|
187 free (l);
|
|
|
188 l = next;
|
|
|
189 }
|
|
|
190
|
|
|
191 free (o);
|
|
|
192 }
|
|
|
193
|
|
|
194 /* Free a block from an objalloc structure. This also frees all more
|
|
|
195 recently allocated blocks. */
|
|
|
196
|
|
|
197 void
|
|
|
198 objalloc_free_block (struct objalloc *o, PTR block)
|
|
|
199 {
|
|
|
200 struct objalloc_chunk *p, *small;
|
|
|
201 char *b = (char *) block;
|
|
|
202
|
|
|
203 /* First set P to the chunk which contains the block we are freeing,
|
|
|
204 and set Q to the last small object chunk we see before P. */
|
|
|
205 small = NULL;
|
|
|
206 for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next)
|
|
|
207 {
|
|
|
208 if (p->current_ptr == NULL)
|
|
|
209 {
|
|
|
210 if (b > (char *) p && b < (char *) p + CHUNK_SIZE)
|
|
|
211 break;
|
|
|
212 small = p;
|
|
|
213 }
|
|
|
214 else
|
|
|
215 {
|
|
|
216 if (b == (char *) p + CHUNK_HEADER_SIZE)
|
|
|
217 break;
|
|
|
218 }
|
|
|
219 }
|
|
|
220
|
|
|
221 /* If we can't find the chunk, the caller has made a mistake. */
|
|
|
222 if (p == NULL)
|
|
|
223 abort ();
|
|
|
224
|
|
|
225 if (p->current_ptr == NULL)
|
|
|
226 {
|
|
|
227 struct objalloc_chunk *q;
|
|
|
228 struct objalloc_chunk *first;
|
|
|
229
|
|
|
230 /* The block is in a chunk containing small objects. We can
|
|
|
231 free every chunk through SMALL, because they have certainly
|
|
|
232 been allocated more recently. After SMALL, we will not see
|
|
|
233 any chunks containing small objects; we can free any big
|
|
|
234 chunk if the current_ptr is greater than or equal to B. We
|
|
|
235 can then reset the new current_ptr to B. */
|
|
|
236
|
|
|
237 first = NULL;
|
|
|
238 q = (struct objalloc_chunk *) o->chunks;
|
|
|
239 while (q != p)
|
|
|
240 {
|
|
|
241 struct objalloc_chunk *next;
|
|
|
242
|
|
|
243 next = q->next;
|
|
|
244 if (small != NULL)
|
|
|
245 {
|
|
|
246 if (small == q)
|
|
|
247 small = NULL;
|
|
|
248 free (q);
|
|
|
249 }
|
|
|
250 else if (q->current_ptr > b)
|
|
|
251 free (q);
|
|
|
252 else if (first == NULL)
|
|
|
253 first = q;
|
|
|
254
|
|
|
255 q = next;
|
|
|
256 }
|
|
|
257
|
|
|
258 if (first == NULL)
|
|
|
259 first = p;
|
|
|
260 o->chunks = (PTR) first;
|
|
|
261
|
|
|
262 /* Now start allocating from this small block again. */
|
|
|
263 o->current_ptr = b;
|
|
|
264 o->current_space = ((char *) p + CHUNK_SIZE) - b;
|
|
|
265 }
|
|
|
266 else
|
|
|
267 {
|
|
|
268 struct objalloc_chunk *q;
|
|
|
269 char *current_ptr;
|
|
|
270
|
|
|
271 /* This block is in a large chunk by itself. We can free
|
|
|
272 everything on the list up to and including this block. We
|
|
|
273 then start allocating from the next chunk containing small
|
|
|
274 objects, setting current_ptr from the value stored with the
|
|
|
275 large chunk we are freeing. */
|
|
|
276
|
|
|
277 current_ptr = p->current_ptr;
|
|
|
278 p = p->next;
|
|
|
279
|
|
|
280 q = (struct objalloc_chunk *) o->chunks;
|
|
|
281 while (q != p)
|
|
|
282 {
|
|
|
283 struct objalloc_chunk *next;
|
|
|
284
|
|
|
285 next = q->next;
|
|
|
286 free (q);
|
|
|
287 q = next;
|
|
|
288 }
|
|
|
289
|
|
|
290 o->chunks = (PTR) p;
|
|
|
291
|
|
|
292 while (p->current_ptr != NULL)
|
|
|
293 p = p->next;
|
|
|
294
|
|
|
295 o->current_ptr = current_ptr;
|
|
|
296 o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr;
|
|
|
297 }
|
|
|
298 }
|
