This source file includes following definitions.
- check_cell
- suba_dump
- check_stats
- suba_dump
- check_stats
- suba_getmeminfo
- suba_init
- suba_alloc
- suba_free
1
2
3
4
5
6
7
8
9
10
11
12
13
14 #include "stdlib.h"
15 #include "stddef.h"
16 #include "string.h"
17 #include "semaphore.h"
18
19 #define SUBA_SEMAPHORE_TIMEOUT 1000
20 #define SANITY_CHECKS 1
21
22 #define SUBA_MAGIC 0x53554241
23 #define CELL_MAGIC 0x5342434C
24
25
26 typedef struct {
27 unsigned int magic;
28 size_t size;
29 } cell_hdr;
30
31
32 typedef struct _cell {
33 cell_hdr h;
34 struct _cell* next;
35 } cell;
36
37
38 typedef struct {
39 unsigned int magic;
40 unsigned int* magic2;
41 size_t size;
42 int sem_id;
43 cell head;
44 size_t mincell;
45
46
47 int free_block_count;
48 int free_size;
49 cell* largest_block;
50 size_t allocated_count;
51 size_t allocated_size;
52 size_t allocated_peak;
53 } allocator;
54
55
56 #define ALIGNMASK (sizeof(cell*)-1)
57 #define ALIGN(s) (((s) + ALIGNMASK) & ~ALIGNMASK)
58
59 #define ACTUALSIZE(size) (size + sizeof(cell_hdr))
60 #define ALLOCSIZE(size) (size - sizeof(cell_hdr))
61 #define CELL2ALLOC(c) (void*)((void*)c + sizeof(cell_hdr))
62 #define ALLOC2CELL(p) (cell*)((void*)p - sizeof(cell_hdr))
63
64 #define CEND(c) ((cell*)((char*)c + c->h.size))
65 #define ISADJ(c1,c2) (CEND(c1) == (c2))
66
67 #if SANITY_CHECKS
68 static cell*
69 check_cell(const allocator *suba, cell* c, char *fn, int ln)
70 {
71 if (suba && (c > (cell*)suba) && (c < (cell*)((char*)suba + suba->size))) {
72 if (c->h.magic != CELL_MAGIC)
73 DebugAssert("Corrupt cell header", ln);
74 return c;
75 }
76 char buf[200];
77 sprintf(buf, "%s bad cell - %x %x", fn, c, suba);
78 DebugAssert(buf, ln);
79 return NULL;
80 }
81 #else
82 #define check_cell(s, c, f, l) (c)
83 #endif
84
85 #ifdef SUBA_HOST_DEBUG
86
87 void suba_dump(allocator *suba)
88 {
89 cell *c = &suba->head;
90 printf("%x %d => ", c, suba->mincell);
91 while (c->h.size != 0)
92 {
93 printf("%x %d %x, ", c, c->h.size, c->next);
94 c = c->next;
95 }
96 printf("%x %d %x\n", c, c->h.size, c->next);
97 }
98
99 int check_stats(allocator *suba)
100 {
101 if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
102 {
103 int count = -1;
104 int free_size = 0;
105 cell* largest = &suba->head;
106 cell* c = check_cell(suba, &suba->head, "suba_getmeminfo", __LINE__);
107 while (c->h.size != 0)
108 {
109 count += 1;
110 free_size += ALLOCSIZE(c->h.size);
111 if (c->h.size > largest->h.size) largest = c;
112 c = check_cell(suba, c->next, "suba_getmeminfo", __LINE__);
113 }
114
115 if (suba->largest_block == NULL)
116 suba->largest_block = largest;
117
118 int rv = 1;
119 if (suba->largest_block->h.size != largest->h.size)
120 {
121 printf("Mismatch - largest %x %d %x %d\n", suba->largest_block, suba->largest_block->h.size, largest->h.size);
122 rv = 0;
123 }
124 if (suba->free_size != free_size)
125 {
126 printf("Mismatch - free_size\n");
127 rv = 0;
128 }
129 if (suba->free_block_count != count)
130 {
131 printf("Mismatch - free_block_count\n");
132 rv = 0;
133 }
134
135 GiveSemaphore(suba->sem_id);
136
137 return rv;
138 }
139 else
140 {
141 DebugAssert("check_stats TakeSemaphore fail", __LINE__);
142 }
143
144 return 0;
145 }
146 #endif
147 #ifdef SUBA_DEBUG
148 void suba_dump(allocator *suba)
149 {
150 char buf[200];
151 FILE *fp = fopen("A/suba_dump.log", "w");
152 cell *c = &suba->head;
153 sprintf(buf, "%x %d %x %d =>\n", c, suba->mincell, suba->largest_block, suba->largest_block->h.size);
154 fwrite(buf, strlen(buf), 1, fp);
155 while (c->h.size != 0)
156 {
157 sprintf(buf, "%x %d %x\n", c, c->h.size, c->next);
158 fwrite(buf, strlen(buf), 1, fp);
159 c = c->next;
160 }
161 sprintf(buf, "%x %d %x\n", c, c->h.size, c->next);
162 fwrite(buf, strlen(buf), 1, fp);
163 fclose(fp);
164 }
165
166 void check_stats(allocator *suba)
167 {
168 int count = -1;
169 int free_size = 0;
170 cell* largest = &suba->head;
171 cell* c = check_cell(suba, &suba->head, "check_stats", __LINE__);
172 while (c->h.size != 0)
173 {
174 count += 1;
175 free_size += ALLOCSIZE(c->h.size);
176 if (c->h.size > largest->h.size) largest = c;
177 c = check_cell(suba, c->next, "check_stats", __LINE__);
178 }
179
180 char buf[200];
181
182 if (suba->largest_block->h.size != largest->h.size)
183 {
184 suba_dump(suba);
185 sprintf(buf, "largest %x %d %x %d\n", suba->largest_block, suba->largest_block->h.size, largest, largest->h.size);
186 DebugAssert(buf, __LINE__);
187 }
188 if (suba->free_size != free_size)
189 {
190 suba_dump(suba);
191 sprintf(buf, "free_size %d %d\n", suba->free_size, free_size);
192 DebugAssert(buf, __LINE__);
193 }
194 if (suba->free_block_count != count)
195 {
196 suba_dump(suba);
197 sprintf(buf, "free_count %d %d\n", suba->free_block_count, count);
198 DebugAssert(buf, __LINE__);
199 }
200 }
201 #endif
202
203 void
204 suba_getmeminfo(allocator *suba, int *allocated_size, int *allocated_peak, int *allocated_count, int *free_size, int *largest_block, int *free_block_count)
205 {
206 if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
207 {
208 if (suba->magic != SUBA_MAGIC || *suba->magic2 != SUBA_MAGIC)
209 DebugAssert("suba_getmeminfo BAD MAGIC", __LINE__);
210
211
212 if (suba->largest_block == NULL)
213 {
214 cell* largest = &suba->head;
215 cell* c = check_cell(suba, &suba->head, "suba_getmeminfo", __LINE__);
216 while (c->h.size != 0)
217 {
218 if (c->h.size > largest->h.size) largest = c;
219 c = check_cell(suba, c->next, "suba_getmeminfo", __LINE__);
220 }
221 suba->largest_block = largest;
222 }
223
224 *largest_block = ALLOCSIZE(suba->largest_block->h.size);
225 *free_size = suba->free_size;
226 *free_block_count = suba->free_block_count;
227
228 *allocated_size = suba->allocated_size;
229 *allocated_peak = suba->allocated_peak;
230 *allocated_count = suba->allocated_count;
231
232 #ifdef SUBA_DEBUG
233 check_stats(suba);
234 #endif
235
236 GiveSemaphore(suba->sem_id);
237 }
238 else
239 {
240 DebugAssert("suba_getmeminfo TakeSemaphore fail", __LINE__);
241 }
242 }
243
244 allocator *
245 suba_init(allocator *suba, size_t size, size_t mincell, char *name)
246 {
247 size_t hdrsiz;
248
249 #if SANITY_CHECKS
250 if (suba == NULL || size == 0) {
251 DebugAssert("Invalid parameters to 'suba_init'", __LINE__);
252 return NULL;
253 }
254 #endif
255
256 size = size & ~ALIGNMASK;
257 hdrsiz = ALIGN(sizeof(allocator));
258 mincell = ACTUALSIZE(ALIGN(mincell));
259
260
261 memset(suba, 0, hdrsiz);
262 suba->magic = SUBA_MAGIC;
263
264 suba->mincell = sizeof(cell);
265 if (mincell > suba->mincell)
266 suba->mincell = mincell;
267 suba->size = size;
268 suba->sem_id = CreateBinarySemaphore(name, 1);
269
270
271 cell *c1, *c2;
272
273
274 c1 = (cell*)((void*)suba + hdrsiz);
275 c1->h.size = size - hdrsiz - sizeof(cell);
276 c1->h.magic = CELL_MAGIC;
277
278
279 c2 = CEND(c1);
280 c2->h.size = 0;
281 c2->h.magic = CELL_MAGIC;
282 c2->next = 0;
283
284
285 c1->next = c2;
286 c1->h.size -= sizeof(cell*);
287
288
289 suba->magic2 = (unsigned int*)CEND(c1);
290 *suba->magic2 = SUBA_MAGIC;
291
292
293 suba->free_block_count = 1;
294 suba->free_size = ALLOCSIZE(c1->h.size);
295 suba->largest_block = c1;
296
297
298 suba->head.h.size = sizeof(cell_hdr);
299 suba->head.h.magic = CELL_MAGIC;
300 suba->head.next = c1;
301
302 return suba;
303 }
304
305 void *
306 suba_alloc(allocator *suba, size_t size, int zero)
307 {
308 cell *this_cell = NULL;
309
310
311 size = ALIGN(size);
312 size_t cellsize = ACTUALSIZE(size);
313 if (cellsize < suba->mincell) cellsize = suba->mincell;
314
315 if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
316 {
317
318 cell *prev_cell = &suba->head;
319 this_cell = check_cell(suba, prev_cell->next, "suba_alloc", __LINE__);
320 while (this_cell->h.size > 0 && this_cell->h.size < cellsize) {
321 prev_cell = this_cell;
322 this_cell = check_cell(suba, this_cell->next, "suba_alloc", __LINE__);
323 }
324
325
326 if (this_cell->h.size > 0) {
327 if (this_cell == suba->largest_block)
328 suba->largest_block = NULL;
329
330 if (this_cell->h.size > (cellsize + suba->mincell)) {
331
332 this_cell->h.size = this_cell->h.size - cellsize;
333 this_cell = CEND(this_cell);
334 this_cell->h.size = cellsize;
335 this_cell->h.magic = CELL_MAGIC;
336 suba->free_size -= cellsize;
337 } else {
338
339 prev_cell->next = this_cell->next;
340 cellsize = this_cell->h.size;
341 suba->free_block_count -= 1;
342 suba->free_size -= ALLOCSIZE(cellsize);
343 }
344
345
346 suba->allocated_size += ALLOCSIZE(cellsize);
347 suba->allocated_count++;
348 if(suba->allocated_size > suba->allocated_peak) {
349 suba->allocated_peak = suba->allocated_size;
350 }
351 } else {
352 this_cell = NULL;
353 }
354
355 GiveSemaphore(suba->sem_id);
356 }
357 else
358 {
359 DebugAssert("suba_alloc TakeSemaphore fail", __LINE__);
360 }
361
362 void *p = NULL;
363
364 if (this_cell != NULL)
365 {
366 p = CELL2ALLOC(this_cell);
367 if (zero) memset(p, 0, ALLOCSIZE(cellsize));
368 }
369
370 return p;
371 }
372
373 int
374 suba_free(allocator *suba, void *ptr)
375 {
376 cell* this_cell = ALLOC2CELL(ptr);
377
378 #if SANITY_CHECKS
379
380 check_cell(suba, this_cell, "suba_free", __LINE__);
381 if (this_cell->h.size > suba->size) {
382 DebugAssert("Trying to free bad block", __LINE__);
383 return -1;
384 }
385 #endif
386
387 if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
388 {
389
390 suba->allocated_size -= ALLOCSIZE(this_cell->h.size);
391 suba->allocated_count--;
392
393
394 cell* prev_cell = &suba->head;
395
396
397 while (prev_cell->next < this_cell) {
398 prev_cell = check_cell(suba, prev_cell->next, "suba_free", __LINE__);
399 }
400 cell* next_cell = check_cell(suba, prev_cell->next, "suba_free", __LINE__);
401
402
403 if (ISADJ(prev_cell,this_cell)) {
404 suba->free_size += this_cell->h.size;
405 prev_cell->h.size += this_cell->h.size;
406 this_cell = prev_cell;
407 } else {
408 this_cell->next = prev_cell->next;
409 prev_cell->next = this_cell;
410 suba->free_block_count += 1;
411 suba->free_size += ALLOCSIZE(this_cell->h.size);
412 }
413
414
415 if (ISADJ(this_cell,next_cell)) {
416 this_cell->next = next_cell->next;
417 this_cell->h.size += next_cell->h.size;
418 suba->free_block_count -= 1;
419 suba->free_size += sizeof(cell_hdr);
420 }
421
422
423 if ((suba->largest_block != NULL) && (this_cell->h.size > suba->largest_block->h.size))
424 suba->largest_block = this_cell;
425
426 GiveSemaphore(suba->sem_id);
427 }
428 else
429 {
430 DebugAssert("suba_free TakeSemaphore fail", __LINE__);
431 return -1;
432 }
433
434 return 0;
435 }