Rev 5129 | Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4973 | right-hear | 1 | /* Copyright (C) 1999 DJ Delorie, see COPYING.DJ for details */ |
2 | /* Copyright (C) 1998 DJ Delorie, see COPYING.DJ for details */ |
||
3 | /* Copyright (C) 1997 DJ Delorie, see COPYING.DJ for details */ |
||
4 | |||
5 | #include |
||
6 | #include |
||
7 | #include |
||
8 | #include |
||
9 | |||
10 | typedef struct BLOCK { |
||
11 | size_t size; |
||
12 | struct BLOCK *next; |
||
13 | int bucket; |
||
14 | } BLOCK; |
||
15 | |||
16 | #define BEFORE(bp) ((BLOCK *)((char *)bp - *(int *)((char *)bp - 4) - 8)) |
||
17 | #define BEFSZ(bp) (*(size_t *)((char *)bp - 4)) |
||
18 | #define ENDSZ(bp) (*(size_t *)((char *)bp + bp->size + 4)) |
||
19 | #define AFTER(bp) ((BLOCK *)((char *)bp + bp->size + 8)) |
||
20 | #define DATA(bp) ((char *)&(bp->next)) |
||
21 | |||
22 | #define NUMSMALL 0 |
||
23 | #define ALIGN 8 |
||
24 | #define SMALL (NUMSMALL*ALIGN) |
||
25 | |||
26 | DECLARE_STATIC_SEM(malloc_mutex) |
||
27 | |||
28 | static BLOCK *slop = 0; |
||
29 | static BLOCK *freelist[30]; |
||
30 | #if NUMSMALL |
||
31 | static BLOCK *smallblocks[NUMSMALL]; |
||
32 | #endif |
||
33 | |||
34 | static inline void malloc_lock(void) |
||
35 | { |
||
36 | sem_lock(&malloc_mutex); |
||
37 | } |
||
38 | |||
39 | static inline void malloc_unlock(void) |
||
40 | { |
||
41 | sem_unlock(&malloc_mutex); |
||
42 | } |
||
43 | |||
44 | #define MIN_SAVE_EXTRA 64 |
||
45 | #define BIG_BLOCK 4096 |
||
46 | |||
47 | #define DEBUG 0 |
||
48 | |||
49 | #if DEBUG |
||
50 | static void |
||
51 | check(BLOCK *b) |
||
52 | { |
||
53 | printf("check %08x %d %08x %d\n", b, b->size, &(ENDSZ(b)), ENDSZ(b)); |
||
54 | } |
||
55 | #define CHECK(p) do { check(p); assert(p->size == ENDSZ(p)); consistency(); } while (0) |
||
56 | #define CHECK1(p) do { check(p); assert(p->size == ENDSZ(p)); } while (0) |
||
57 | static void |
||
58 | consistency() |
||
59 | { |
||
60 | #if 0 |
||
61 | int b; |
||
62 | BLOCK *bl; |
||
63 | if (slop) |
||
64 | CHECK1(slop); |
||
65 | for (b=0; b<32; b++) |
||
66 | for (bl=freelist[b]; bl; bl=bl->next) |
||
67 | CHECK1(bl); |
||
68 | #endif |
||
69 | } |
||
70 | #else |
||
71 | #define CHECK(p) |
||
72 | #endif |
||
73 | |||
74 | static inline int |
||
75 | size2bucket(size_t size) |
||
76 | { |
||
77 | int rv=0; |
||
78 | size>>=2; |
||
79 | while (size) |
||
80 | { |
||
81 | rv++; |
||
82 | size>>=1; |
||
83 | } |
||
84 | return rv; |
||
85 | } |
||
86 | |||
87 | static inline int |
||
88 | b2bucket(BLOCK *b) |
||
89 | { |
||
90 | if (b->bucket == -1) |
||
91 | b->bucket = size2bucket(b->size); |
||
92 | return b->bucket; |
||
93 | } |
||
94 | |||
95 | static inline BLOCK * |
||
96 | split_block(BLOCK *b, size_t size) |
||
97 | { |
||
98 | BLOCK *rv = (BLOCK *)((char *)b + size+8); |
||
99 | #if DEBUG |
||
100 | printf(" split %u/%08x to %u/%08x, %u/%08x\n", |
||
101 | b->size, b, size, b, b->size - size - 8, rv); |
||
102 | #endif |
||
103 | rv->size = b->size - size - 8; |
||
104 | rv->bucket = -1; |
||
105 | b->size = size; |
||
106 | ENDSZ(b) = b->size; |
||
107 | ENDSZ(rv) = rv->size; |
||
108 | CHECK(b); |
||
109 | CHECK(rv); |
||
110 | return rv; |
||
111 | } |
||
112 | |||
113 | #define RET(rv) CHECK(rv); ENDSZ(rv) |= 1; rv->size |= 1; return DATA(rv) |
||
114 | |||
115 | void * malloc(size_t size) |
||
116 | { |
||
117 | int b, chunk_size; |
||
118 | BLOCK *rv, **prev; |
||
119 | static BLOCK *expected_sbrk = 0; |
||
120 | |||
121 | if (size |
||
122 | size = (size+(ALIGN-1))&~(ALIGN-1); |
||
123 | #if DEBUG |
||
124 | printf("malloc(%u)\n", size); |
||
125 | #endif |
||
126 | |||
127 | #if NUMSMALL |
||
128 | if (size < SMALL) |
||
129 | { |
||
130 | rv = smallblocks[size/ALIGN]; |
||
131 | if (rv) |
||
132 | { |
||
133 | smallblocks[size/ALIGN] = rv->next; |
||
134 | return DATA(rv); |
||
135 | } |
||
136 | } |
||
137 | #endif |
||
138 | |||
139 | if (slop && slop->size >= size) |
||
140 | { |
||
141 | rv = slop; |
||
142 | #if DEBUG |
||
143 | printf(" using slop %u/%08x\n", slop->size, slop); |
||
144 | #endif |
||
145 | if (slop->size >= size+MIN_SAVE_EXTRA) |
||
146 | { |
||
147 | slop = split_block(slop, size); |
||
148 | #if DEBUG |
||
149 | printf(" remaining slop %u/%08x\n", slop->size, slop); |
||
150 | #endif |
||
151 | } |
||
152 | else |
||
153 | slop = 0; |
||
154 | RET(rv); |
||
155 | } |
||
156 | |||
157 | b = size2bucket(size); |
||
158 | prev = &(freelist[b]); |
||
159 | for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next) |
||
160 | { |
||
161 | if (rv->size >= size && rv->size < size+size/4) |
||
162 | { |
||
163 | *prev = rv->next; |
||
164 | RET(rv); |
||
165 | } |
||
166 | } |
||
167 | |||
168 | while (b < 30) |
||
169 | { |
||
170 | prev = &(freelist[b]); |
||
171 | #if DEBUG |
||
172 | printf(" checking bucket %d\n", b); |
||
173 | #endif |
||
174 | for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next) |
||
175 | if (rv->size >= size) |
||
176 | { |
||
177 | #if DEBUG |
||
178 | printf(" found size %d/%08x\n", rv->size, rv); |
||
179 | #endif |
||
180 | *prev = rv->next; |
||
181 | if (rv->size >= size+MIN_SAVE_EXTRA) |
||
182 | { |
||
183 | #if DEBUG |
||
184 | printf(" enough to save\n"); |
||
185 | #endif |
||
186 | if (slop) |
||
187 | { |
||
188 | b = b2bucket(slop); |
||
189 | #if DEBUG |
||
190 | printf(" putting old slop %u/%08x on free list %d\n", |
||
191 | slop->size, slop, b); |
||
192 | #endif |
||
193 | slop->next = freelist[b]; |
||
194 | freelist[b] = slop; |
||
195 | } |
||
196 | slop = split_block(rv, size); |
||
197 | #if DEBUG |
||
198 | printf(" slop size %u/%08x\n", slop->size, slop); |
||
199 | #endif |
||
200 | } |
||
201 | RET(rv); |
||
202 | } |
||
203 | b++; |
||
204 | } |
||
205 | |||
206 | chunk_size = size+16; /* two ends plus two placeholders */ |
||
207 | rv = (BLOCK *)sbrk(chunk_size); |
||
208 | if (rv == (BLOCK *)(-1)) |
||
209 | return 0; |
||
210 | #if DEBUG |
||
211 | printf("sbrk(%d) -> %08x, expected %08x\n", chunk_size, rv, expected_sbrk); |
||
212 | #endif |
||
213 | if (rv == expected_sbrk) |
||
214 | { |
||
215 | expected_sbrk = (BLOCK *)((char *)rv + chunk_size); |
||
216 | /* absorb old end-block-marker */ |
||
217 | #if DEBUG |
||
218 | printf(" got expected sbrk\n"); |
||
219 | #endif |
||
220 | rv = (BLOCK *)((char *)rv - 4); |
||
221 | } |
||
222 | else |
||
223 | { |
||
224 | expected_sbrk = (BLOCK *)((char *)rv + chunk_size); |
||
225 | #if DEBUG |
||
226 | printf(" disconnected sbrk\n"); |
||
227 | #endif |
||
228 | /* build start-block-marker */ |
||
229 | rv->size = 1; |
||
230 | rv = (BLOCK *)((char *)rv + 4); |
||
231 | chunk_size -= 8; |
||
232 | } |
||
233 | rv->size = chunk_size - 8; |
||
234 | ENDSZ(rv) = rv->size; |
||
235 | AFTER(rv)->size = 1; |
||
236 | CHECK(rv); |
||
237 | |||
238 | RET(rv); |
||
239 | } |
||
240 | |||
241 | static inline BLOCK * |
||
242 | merge(BLOCK *a, BLOCK *b, BLOCK *c) |
||
243 | { |
||
244 | int bu; |
||
245 | BLOCK *bp, **bpp; |
||
246 | |||
247 | #if DEBUG |
||
248 | printf(" merge %u/%08x + %u/%08x = %u\n", |
||
249 | a->size, a, b->size, b, a->size+b->size+8); |
||
250 | #endif |
||
251 | |||
252 | CHECK(a); |
||
253 | CHECK(b); |
||
254 | CHECK(c); |
||
255 | if (c == slop) |
||
256 | { |
||
257 | #if DEBUG |
||
258 | printf(" snipping slop %u/%08x\n", slop->size, slop); |
||
259 | #endif |
||
260 | slop = 0; |
||
261 | } |
||
262 | bu = b2bucket(c); |
||
263 | #if DEBUG |
||
264 | printf("bucket for %u/%08x is %d\n", c->size, c, bu); |
||
265 | #endif |
||
266 | bpp = freelist+bu; |
||
267 | for (bp=freelist[bu]; bp; bpp=&(bp->next), bp=bp->next) |
||
268 | { |
||
269 | #if DEBUG |
||
270 | printf(" %08x", bp); |
||
271 | #endif |
||
272 | if (bp == c) |
||
273 | { |
||
274 | #if DEBUG |
||
275 | printf("\n snipping %u/%08x from freelist[%d]\n", bp->size, bp, bu); |
||
276 | #endif |
||
277 | *bpp = bp->next; |
||
278 | break; |
||
279 | } |
||
280 | } |
||
281 | CHECK(c); |
||
282 | |||
283 | a->size += b->size + 8; |
||
284 | a->bucket = -1; |
||
285 | ENDSZ(a) = a->size; |
||
286 | |||
287 | CHECK(a); |
||
288 | return a; |
||
289 | } |
||
290 | |||
291 | void |
||
292 | free(void *ptr) |
||
293 | { |
||
294 | int b; |
||
295 | BLOCK *block; |
||
296 | if (ptr == 0) |
||
297 | return; |
||
298 | block = (BLOCK *)((char *)ptr-4); |
||
299 | |||
300 | #if NUMSMALL |
||
301 | if (block->size < SMALL) |
||
302 | { |
||
303 | block->next = smallblocks[block->size/ALIGN]; |
||
304 | smallblocks[block->size/ALIGN] = block; |
||
305 | return; |
||
306 | } |
||
307 | #endif |
||
308 | |||
309 | block->size &= ~1; |
||
310 | ENDSZ(block) &= ~1; |
||
311 | block->bucket = -1; |
||
312 | #if DEBUG |
||
313 | printf("free(%u/%08x)\n", block->size, block); |
||
314 | #endif |
||
315 | |||
316 | CHECK(block); |
||
317 | if (! (AFTER(block)->size & 1)) |
||
318 | { |
||
319 | CHECK(AFTER(block)); |
||
320 | } |
||
321 | if (! (BEFSZ(block) & 1)) |
||
322 | { |
||
323 | CHECK(BEFORE(block)); |
||
324 | block = merge(BEFORE(block), block, BEFORE(block)); |
||
325 | } |
||
326 | CHECK(block); |
||
327 | if (! (AFTER(block)->size & 1)) |
||
328 | { |
||
329 | CHECK(AFTER(block)); |
||
330 | block = merge(block, AFTER(block), AFTER(block)); |
||
331 | } |
||
332 | CHECK(block); |
||
333 | |||
334 | b = b2bucket(block); |
||
335 | block->next = freelist[b]; |
||
336 | freelist[b] = block; |
||
337 | CHECK(block); |
||
338 | } |
||
339 | |||
340 | void * realloc(void *ptr, size_t size) |
||
341 | { |
||
342 | BLOCK *b; |
||
343 | char *newptr; |
||
344 | size_t copysize; |
||
345 | if (ptr == 0) return malloc(size); |
||
346 | b = (BLOCK *)((char *)ptr-4); |
||
347 | copysize = b->size & ~1; |
||
348 | if (size <= copysize) |
||
349 | { |
||
350 | return ptr; |
||
351 | copysize = size; |
||
352 | } |
||
353 | newptr = (char *)malloc(size); |
||
354 | if (!newptr) return NULL; |
||
355 | memcpy(newptr, ptr, copysize); |
||
356 | free(ptr); |
||
357 | return newptr; |
||
358 | }=>>>>>32;> |