Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
5191 | serge | 1 | /* objalloc.c -- routines to allocate memory for objects |
2 | Copyright 1997-2012 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 |
||
27 | |||
28 | #if VMS |
||
29 | #include |
||
30 | #include |
||
31 | #else |
||
32 | |||
33 | /* Get a definition for size_t. */ |
||
34 | #include |
||
35 | |||
36 | #ifdef HAVE_STDLIB_H |
||
37 | #include |
||
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 original_len) |
||
116 | { |
||
117 | unsigned long len = original_len; |
||
118 | |||
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 | |||
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 | |||
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 | }>=>> |