|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/connect/ncbi_heapmgr.c |
source navigation diff markup identifier search freetext search file search |
1 /* $Id: ncbi_heapmgr.c,v 6.46 2008/12/19 19:29:37 kazimird Exp $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government have not placed any restriction on its use or reproduction.
13 *
14 * Although all reasonable efforts have been taken to ensure the accuracy
15 * and reliability of the software and data, the NLM and the U.S.
16 * Government do not and cannot warrant the performance or results that
17 * may be obtained by using this software or data. The NLM and the U.S.
18 * Government disclaim all warranties, express or implied, including
19 * warranties of performance, merchantability or fitness for any particular
20 * purpose.
21 *
22 * Please cite the author in any work or product based on this material.
23 *
24 * ===========================================================================
25 *
26 * Author: Anton Lavrentiev
27 *
28 * Abstract:
29 *
30 * This is a simple heap manager with a primitive garbage collection.
31 * The heap contains blocks of data, stored in a common contiguous pool,
32 * each block preceded with a SHEAP_Block structure. Low word of 'flag'
33 * is either non-zero (True), when the block is in use, or zero (False),
34 * when the block is vacant. 'Size' shows the length of the block in bytes,
35 * (uninterpreted) data field of which is extended past the header
36 * (the header size IS counted in the size of the block).
37 *
38 * When 'HEAP_Alloc' is called, the return value is either a heap pointer,
39 * which points to the block header, marked as allocated and guaranteed
40 * to have enough space to hold the requested data size; or 0 meaning, that the
41 * heap has no more room to provide such a block (reasons for that:
42 * heap is corrupt, heap has no provision to be expanded, expansion failed,
43 * or the heap was attached read-only).
44 *
45 * An application program can then use the data field on its need,
46 * providing not to overcome the size limit. The current block header
47 * can be used to find the next heap block with the use of 'size' member
48 * (note, however, some restrictions below).
49 *
50 * The application program is NOT assumed to keep the returned block pointer,
51 * as the garbage collection can occur on the next allocation attempt,
52 * thus making any heap pointers invalid. Instead, the application program
53 * can keep track of the heap base (header of the very first heap block -
54 * see 'HEAP_Create'), and the size of the heap, and can traverse the heap by
55 * this means, or with call to 'HEAP_Walk' (described below).
56 *
57 * While traversing, if the block found is no longer needed, it can be freed
58 * with 'HEAP_Free' call, supplying the address of the block header
59 * as an argument.
60 *
61 * Prior to the heap use, the initialization is required, which comprises
62 * call to either 'HEAP_Create' or 'HEAP_Attach' with the information about
63 * the base heap pointer. 'HEAP_Create' also takes the size of initial
64 * heap area (if there is one), and size of chunk (usually, a page size)
65 * to be used in heap expansions (defaults to alignment if provided as 0).
66 * Additionally (but not compulsory) the application program can provide
67 * heap manager with 'resize' routine, which is supposed to be called,
68 * when no more room is available in the heap, or the heap has not been
69 * preallocated (base = 0 in 'HEAP_Create'), and given the arguments:
70 * - current heap base address (or 0 if this is the very first heap alloc),
71 * - new required heap size (or 0 if this is the last call to deallocate
72 * the entire heap).
73 * If successful, the resize routine must return the new heap base
74 * address (if any) of expanded heap area, and where the exact copy of
75 * the current heap is made.
76 *
77 * Note that all heap base pointers must be aligned on a 'double' boundary.
78 * Please also be warned not to store pointers to the heap area, as a
79 * garbage collection can clobber them. Within a block, however,
80 * it is possible to use local pointers (offsets), which remain same
81 * regardless of garbage collections.
82 *
83 * For automatic traverse purposes there is a 'HEAP_Walk' call, which returns
84 * the next block (either free, or used) from the heap. Given a NULL-pointer,
85 * this function returns the very first block, whereas all subsequent calls
86 * with the argument being the last observed block results in the next block
87 * returned. NULL comes back when no more blocks exist in the heap.
88 *
89 * Note that for proper heap operations, no allocation(s) should happen between
90 * successive calls to 'HEAP_Walk', whereas deallocation of the seen block
91 * is okay.
92 *
93 * Explicit heap traversing should not overcome the heap limit,
94 * as any information outside is not maintained by the heap manager.
95 * Every heap operation guarantees that there are no adjacent free blocks,
96 * only used blocks can follow each other sequentially.
97 *
98 * To discontinue to use the heap, 'HEAP_Destroy' or 'HEAP_Detach' can be
99 * called. The former deallocates the heap (by means of a call to 'resize'),
100 * the latter just removes the heap handle, retaining the heap data intact.
101 * Later, such a heap can be used again if attached with 'HEAP_Attach'.
102 *
103 * Note that an attached heap is always in read-only mode, that is nothing
104 * can be allocated and/or freed in that heap, as well as an attempt to call
105 * 'HEAP_Destroy' will not actually touch any heap data (but to destroy
106 * the handle only).
107 *
108 * Note also, that 'HEAP_Create' always does heap reset, that is the
109 * memory area pointed to by 'base' (if not 0) gets reformatted and lose
110 * all previous contents.
111 *
112 */
113
114 #include "ncbi_priv.h"
115 #include <connect/ncbi_heapmgr.h>
116 #include <stdlib.h>
117 #include <string.h>
118
119 #define NCBI_USE_ERRCODE_X Connect_HeapMgr
120
121 #if defined(NCBI_OS_MSWIN) && defined(_WIN64)
122 /* Disable ptr->long conversion warning (even on explicit cast!) */
123 # pragma warning (disable : 4311)
124 #endif /*NCBI_OS_MSWIN && _WIN64*/
125
126 #ifdef abs
127 # undef abs
128 #endif
129 #define abs(a) ((a) < 0 ? (a) : -(a))
130
131 #ifdef NCBI_OS_LINUX
132 # if NCBI_PLATFORM_BITS == 64
133 # ifdef __GNUC__
134 # define HEAP_PACKED __attribute__ ((packed))
135 # else
136 # error "Don't know how to pack on this 64-bit platform"
137 # endif
138 # else
139 # define HEAP_PACKED /* */
140 # endif
141 #else
142 # define HEAP_PACKED /* */
143 #endif
144
145
146 /* Heap's own block view */
147 typedef struct HEAP_PACKED {
148 SHEAP_Block head; /* Block head */
149 TNCBI_Size prevfree; /* Heap index for prev free block (if free) */
150 TNCBI_Size nextfree; /* Heap index for next free block (if free) */
151 } SHEAP_HeapBlock;
152
153
154 struct SHEAP_tag {
155 SHEAP_HeapBlock* base; /* Current base of heap extent: !base == !size */
156 TNCBI_Size size; /* Current size of heap extent: !base == !size */
157 TNCBI_Size free; /* Current index of first free block (OOB=none)*/
158 TNCBI_Size last; /* Current index of last heap block (RW heap) */
159 TNCBI_Size chunk; /* Aligned; 0 when the heap is read-only */
160 FHEAP_Resize resize; /* != NULL when resizeable (RW heap only) */
161 void* arg; /* Aux argument to pass to "resize" */
162 unsigned int refc; /* Reference counter (copy heap, 0=original) */
163 int serial; /* Serial number as assigned by (Attach|Copy) */
164 };
165
166
167 static int/*bool*/ s_HEAP_fast = 1/*true*/;
168 static int/*bool*/ s_HEAP_newalk = 0/*false*/;
169
170
171 #define _HEAP_ALIGN(a, b) (((unsigned long)(a) + (b) - 1) & ~((b) - 1))
172 #define _HEAP_ALIGNSHIFT 4
173 #define _HEAP_ALIGNMENT (1 << _HEAP_ALIGNSHIFT)
174 #define HEAP_ALIGN(a) _HEAP_ALIGN(a, _HEAP_ALIGNMENT)
175 #define HEAP_LAST 0x80000000UL
176 #define HEAP_USED 0x0DEAD2F0UL
177 #define HEAP_FREE 0
178 #define HEAP_NEXT(b) ((SHEAP_HeapBlock*)((char*) b + b->head.size))
179 #define HEAP_INDEX(b, base) ((TNCBI_Size)((b) - (base)))
180 #define HEAP_ISFREE(b) (((b)->head.flag & ~HEAP_LAST) == HEAP_FREE)
181 #define HEAP_ISUSED(b) (((b)->head.flag & ~HEAP_LAST) == HEAP_USED)
182 #define HEAP_ISLAST(b) ( (b)->head.flag & HEAP_LAST)
183
184
185 HEAP HEAP_Create(void* base, TNCBI_Size size,
186 TNCBI_Size chunk, FHEAP_Resize resize, void* arg)
187 {
188 HEAP heap;
189
190 assert(_HEAP_ALIGNMENT == sizeof(SHEAP_HeapBlock));
191 if (!base != !size)
192 return 0;
193 if (size && size < _HEAP_ALIGNMENT) {
194 CORE_LOGF_X(1, eLOG_Error,
195 ("Heap Create: Storage too small: "
196 "provided %u, required %u+",
197 size, _HEAP_ALIGNMENT));
198 return 0;
199 }
200 if (!(heap = (HEAP) malloc(sizeof(*heap))))
201 return 0;
202 size &= ~(_HEAP_ALIGNMENT - 1);
203 heap->base = (SHEAP_HeapBlock*) base;
204 heap->size = size >> _HEAP_ALIGNSHIFT;
205 heap->free = 0;
206 heap->last = 0;
207 heap->chunk = chunk ? (TNCBI_Size) HEAP_ALIGN(chunk) : 0;
208 heap->resize = heap->chunk ? resize : 0;
209 heap->arg = heap->resize ? arg : 0;
210 heap->refc = 0/*original*/;
211 heap->serial = 0;
212 if (base) {
213 SHEAP_HeapBlock* b = heap->base;
214 /* Reformat the pre-allocated heap */
215 if (_HEAP_ALIGN(base, sizeof(SHEAP_Block)) != (unsigned long) base) {
216 CORE_LOGF_X(2, eLOG_Warning,
217 ("Heap Create: Unaligned base (0x%08lX)",
218 (long) base));
219 }
220 b->head.flag = HEAP_FREE | HEAP_LAST;
221 b->head.size = size;
222 b->nextfree = 0;
223 b->prevfree = 0;
224 }
225 return heap;
226 }
227
228
229 HEAP HEAP_AttachFast(const void* base, TNCBI_Size size, int serial)
230 {
231 HEAP heap;
232
233 assert(_HEAP_ALIGNMENT == sizeof(SHEAP_HeapBlock));
234 if (!base != !size || !(heap = (HEAP) calloc(1, sizeof(*heap))))
235 return 0;
236 if (_HEAP_ALIGN(base, sizeof(SHEAP_Block)) != (unsigned long) base) {
237 CORE_LOGF_X(3, eLOG_Warning,
238 ("Heap Attach: Unaligned base (0x%08lX)", (long) base));
239 }
240 heap->base = (SHEAP_HeapBlock*) base;
241 heap->size = HEAP_ALIGN(size) >> _HEAP_ALIGNSHIFT;
242 heap->serial = serial;
243 if (size != heap->size << _HEAP_ALIGNSHIFT) {
244 CORE_LOGF_X(4, eLOG_Warning,
245 ("Heap Attach: Heap size alignment (%u->%u) "
246 "can result in garbage in data",
247 size, heap->size << _HEAP_ALIGNSHIFT));
248 }
249 return heap;
250 }
251
252
253 HEAP HEAP_Attach(const void* base, int serial)
254 {
255 TNCBI_Size size = 0;
256
257 if (base) {
258 const SHEAP_HeapBlock* b = (const SHEAP_HeapBlock*) base;
259 for (;;) {
260 if (!HEAP_ISUSED(b) && !HEAP_ISFREE(b)) {
261 CORE_LOGF_X(5, eLOG_Error,
262 ("Heap Attach: Heap corrupt @%u (0x%08X, %u)",
263 HEAP_INDEX(b, (SHEAP_HeapBlock*) base),
264 b->head.flag, b->head.size));
265 return 0;
266 }
267 size += b->head.size;
268 if (HEAP_ISLAST(b))
269 break;
270 b = HEAP_NEXT(b);
271 }
272 }
273 return HEAP_AttachFast(base, size, serial);
274 }
275
276
277 /* Collect garbage in the heap, moving all contents to the
278 * top, and merging all free blocks at the end into a single
279 * large free block. Return pointer to that free block, or
280 * NULL if there is no free space in the heap.
281 */
282 static SHEAP_HeapBlock* s_HEAP_Collect(HEAP heap, TNCBI_Size* prev)
283 {
284 SHEAP_HeapBlock* b = heap->base;
285 SHEAP_HeapBlock *f = 0;
286 TNCBI_Size free = 0;
287
288 *prev = 0;
289 while (b < heap->base + heap->size) {
290 SHEAP_HeapBlock* n = HEAP_NEXT(b);
291 assert(HEAP_ALIGN(b->head.size) == b->head.size);
292 if (HEAP_ISFREE(b)) {
293 free += b->head.size;
294 if (!f)
295 f = b;
296 } else if (f) {
297 assert(HEAP_ISUSED(b));
298 *prev = HEAP_INDEX(f, heap->base);
299 memmove(f, b, b->head.size);
300 f->head.flag &= ~HEAP_LAST;
301 f = HEAP_NEXT(f);
302 }
303 b = n;
304 }
305 if (f) {
306 assert((char*) f + free == (char*) &heap->base[heap->size]);
307 f->head.flag = HEAP_FREE | HEAP_LAST;
308 f->head.size = free;
309 free = HEAP_INDEX(f, heap->base);
310 f->prevfree = free;
311 f->nextfree = free;
312 heap->last = free;
313 heap->free = free;
314 } else
315 assert(heap->free == heap->size);
316 return f;
317 }
318
319
320 /* Book 'size' bytes (aligned, and block header included) within the given
321 * free block 'b' of an adequate size (perhaps causing the block to be split
322 * in two, if it's roomy enough, and the remaining part marked as a new
323 * free block). Non-zero 'fast' parameter inverses the order of locations of
324 * occupied blocks in successive allocations, but saves cycles by sparing
325 * updates of the free block list. Return the block to use.
326 */
327 static SHEAP_Block* s_HEAP_Book(HEAP heap, SHEAP_HeapBlock* b,
328 TNCBI_Size size, int/*bool*/ fast)
329 {
330 unsigned int last = b->head.flag & HEAP_LAST;
331
332 assert(HEAP_ALIGN(size) == size);
333 assert(HEAP_ISFREE(b) && b->head.size >= size);
334 if (b->head.size >= size + _HEAP_ALIGNMENT) {
335 /* the block to use in part */
336 if (fast) {
337 b->head.flag &= ~HEAP_LAST;
338 b->head.size -= size;
339 b = HEAP_NEXT(b);
340 b->head.size = size;
341 if (last)
342 heap->last = HEAP_INDEX(b, heap->base);
343 } else {
344 SHEAP_HeapBlock* f = (SHEAP_HeapBlock*)((char*) b + size);
345 f->head.flag = b->head.flag;
346 f->head.size = b->head.size - size;
347 b->head.flag &= ~HEAP_LAST;
348 b->head.size = size;
349 size = HEAP_INDEX(f, heap->base);
350 if (last) {
351 heap->last = size;
352 last = 0;
353 }
354 if (heap->base + b->prevfree == b) {
355 assert(b->prevfree == b->nextfree);
356 assert(b->prevfree == heap->free);
357 f->prevfree = size;
358 f->nextfree = size;
359 heap->free = size;
360 } else {
361 f->prevfree = b->prevfree;
362 f->nextfree = b->nextfree;
363 assert(HEAP_ISFREE(heap->base + f->prevfree));
364 assert(HEAP_ISFREE(heap->base + f->nextfree));
365 heap->base[f->nextfree].prevfree = size;
366 heap->base[f->prevfree].nextfree = size;
367 if (heap->base + heap->free == b)
368 heap->free = size;
369 }
370 }
371 } else {
372 /* the block to use in whole */
373 size = HEAP_INDEX(b, heap->base);
374 if (b->prevfree != size) {
375 assert(b->nextfree != size);
376 assert(HEAP_ISFREE(heap->base + b->prevfree));
377 assert(HEAP_ISFREE(heap->base + b->nextfree));
378 heap->base[b->nextfree].prevfree = b->prevfree;
379 heap->base[b->prevfree].nextfree = b->nextfree;
380 if (heap->free == size)
381 heap->free = b->prevfree;
382 } else {
383 /* the only free block */
384 assert(b->prevfree == b->nextfree);
385 assert(b->prevfree == heap->free);
386 heap->free = heap->size;
387 }
388 }
389 b->head.flag = HEAP_USED | last;
390 return &b->head;
391 }
392
393
394 static SHEAP_Block* s_HEAP_Take(HEAP heap, SHEAP_HeapBlock* b,
395 TNCBI_Size size, TNCBI_Size real,
396 int/*bool*/ fast)
397 {
398 SHEAP_Block* n = s_HEAP_Book(heap, b, size, fast);
399 if (size -= real)
400 memset((char*) n + real, 0, size); /* block padding (if any) zeroed */
401 return n;
402 }
403
404
405 static const char* s_HEAP_Id(char* buf, HEAP h)
406 {
407 if (!h)
408 return "";
409 if (h->serial && h->refc)
410 sprintf(buf, "[C%d%sR%u]", abs(h->serial),&"-"[h->serial > 0],h->refc);
411 else if (h->serial)
412 sprintf(buf, "[C%d%s]", abs(h->serial), &"-"[h->serial > 0]);
413 else if (h->refc)
414 sprintf(buf, "[R%u]", h->refc);
415 else
416 strcpy(buf, "");
417 return buf;
418 }
419
420
421 static SHEAP_Block* s_HEAP_Alloc(HEAP heap, TNCBI_Size size, int/*bool*/ fast)
422 {
423 SHEAP_HeapBlock* f, *b;
424 TNCBI_Size need;
425 TNCBI_Size free;
426 char _id[32];
427
428 if (!heap) {
429 CORE_LOG_X(6, eLOG_Warning, "Heap Alloc: NULL heap");
430 return 0;
431 }
432 assert(!heap->base == !heap->size);
433
434 if (!heap->chunk) {
435 CORE_LOGF_X(7, eLOG_Error,
436 ("Heap Alloc%s: Heap read-only", s_HEAP_Id(_id, heap)));
437 return 0;
438 }
439 if (size < 1)
440 return 0;
441
442 size += (TNCBI_Size) sizeof(SHEAP_Block);
443 need = (TNCBI_Size) HEAP_ALIGN(size);
444
445 free = 0;
446 if (heap->free < heap->size) {
447 f = heap->base + heap->free;
448 b = f;
449 do {
450 if (!HEAP_ISFREE(b)) {
451 CORE_LOGF_X(8, eLOG_Error,
452 ("Heap Alloc%s: Heap%s corrupt "
453 "@%u/%u (0x%08X, %u)",
454 s_HEAP_Id(_id, heap), b == f ? " header" : "",
455 HEAP_INDEX(b, heap->base), heap->size,
456 b->head.flag, b->head.size));
457 return 0;
458 }
459 if (b->head.size >= need)
460 return s_HEAP_Take(heap, b, need, size, fast);
461 free += b->head.size;
462 b = heap->base + b->nextfree;
463 } while (b != f);
464 }
465
466 /* Heap exhausted: no large enough, free block found */
467 if (free >= need)
468 b = s_HEAP_Collect(heap, &free/*dummy*/);
469 else if (!heap->resize)
470 return 0;
471 else {
472 TNCBI_Size dsize = heap->size << _HEAP_ALIGNSHIFT;
473 TNCBI_Size hsize = ((dsize + need + heap->chunk - 1)
474 / heap->chunk) * heap->chunk;
475 SHEAP_HeapBlock* base = (SHEAP_HeapBlock*)
476 heap->resize(heap->base, hsize, heap->arg);
477 if (_HEAP_ALIGN(base, sizeof(SHEAP_Block)) != (unsigned long) base) {
478 CORE_LOGF_X(9, eLOG_Warning,
479 ("Heap Alloc%s: Unaligned base (0x%08lX)",
480 s_HEAP_Id(_id, heap), (long) base));
481 }
482 if (!base)
483 return 0;
484 dsize = hsize - dsize;
485 memset(base + heap->size, 0, (size_t) dsize); /* security */
486
487 b = base + heap->last;
488 if (!heap->base) {
489 b->head.flag = HEAP_FREE | HEAP_LAST;
490 b->head.size = hsize;
491 b->nextfree = 0;
492 b->prevfree = 0;
493 heap->free = 0;
494 heap->last = 0;
495 } else {
496 assert(HEAP_ISLAST(b));
497 if (HEAP_ISUSED(b)) {
498 b->head.flag &= ~HEAP_LAST;
499 /* New block is at the very top on the heap */
500 b = base + heap->size;
501 b->head.flag = HEAP_FREE | HEAP_LAST;
502 b->head.size = dsize;
503 heap->last = heap->size;
504 if (heap->free < heap->size) {
505 assert(HEAP_ISFREE(base + heap->free));
506 b->prevfree = heap->free;
507 b->nextfree = base[heap->free].nextfree;
508 base[heap->free].nextfree = heap->size;
509 base[b->nextfree].prevfree = heap->size;
510 } else {
511 b->prevfree = heap->size;
512 b->nextfree = heap->size;
513 }
514 heap->free = heap->size;
515 } else {
516 /* Extend last free block */
517 assert(HEAP_ISFREE(b));
518 b->head.size += dsize;
519 }
520 }
521 heap->base = base;
522 heap->size = hsize >> _HEAP_ALIGNSHIFT;
523 }
524 assert(b && HEAP_ISFREE(b) && b->head.size >= need);
525 return s_HEAP_Take(heap, b, need, size, fast);
526 }
527
528
529 SHEAP_Block* HEAP_Alloc(HEAP heap, TNCBI_Size size)
530 {
531 return s_HEAP_Alloc(heap, size, 0);
532 }
533
534
535 SHEAP_Block* HEAP_AllocFast(HEAP heap, TNCBI_Size size)
536 {
537 return s_HEAP_Alloc(heap, size, 1);
538 }
539
540
541 static void s_HEAP_Free(HEAP heap, SHEAP_HeapBlock* p, SHEAP_HeapBlock* b)
542 {
543 unsigned int last = b->head.flag & HEAP_LAST;
544 SHEAP_HeapBlock* n = HEAP_NEXT(b);
545 TNCBI_Size free;
546
547 if (p && HEAP_ISFREE(p)) {
548 free = HEAP_INDEX(p, heap->base);
549 if (!last && HEAP_ISFREE(n)) {
550 /* Unlink last: at least there's "p" */
551 assert(heap->base + n->nextfree != n);
552 assert(heap->base + n->prevfree != n);
553 assert(HEAP_ISFREE(heap->base + n->prevfree));
554 assert(HEAP_ISFREE(heap->base + n->nextfree));
555 heap->base[n->nextfree].prevfree = n->prevfree;
556 heap->base[n->prevfree].nextfree = n->nextfree;
557 /* Merge */
558 b->head.flag = n->head.flag;
559 b->head.size += n->head.size;
560 last = b->head.flag & HEAP_LAST;
561 }
562 /* Merge all together */
563 if (last) {
564 p->head.flag |= HEAP_LAST;
565 heap->last = free;
566 }
567 p->head.size += b->head.size;
568 b = p;
569 } else {
570 free = HEAP_INDEX(b, heap->base);
571 b->head.flag = HEAP_FREE | last;
572 if (!last && HEAP_ISFREE(n)) {
573 /* Merge */
574 b->head.flag = n->head.flag;
575 b->head.size += n->head.size;
576 if (heap->base + n->prevfree == n) {
577 assert(n->prevfree == n->nextfree);
578 assert(n->prevfree == heap->free);
579 b->prevfree = free;
580 b->nextfree = free;
581 } else {
582 assert(heap->base + n->nextfree != n);
583 b->prevfree = n->prevfree;
584 b->nextfree = n->nextfree;
585 /* Link in */
586 assert(HEAP_ISFREE(heap->base + b->prevfree));
587 assert(HEAP_ISFREE(heap->base + b->nextfree));
588 heap->base[b->nextfree].prevfree = free;
589 heap->base[b->prevfree].nextfree = free;
590 }
591 if (HEAP_ISLAST(n))
592 heap->last = free;
593 } else if (heap->free < heap->size) {
594 /* Link in at the heap free position */
595 assert(HEAP_ISFREE(heap->base + heap->free));
596 b->prevfree = heap->free;
597 b->nextfree = heap->base[heap->free].nextfree;
598 heap->base[heap->free].nextfree = free;
599 heap->base[b->nextfree].prevfree = free;
600 } else {
601 /* Link in as the only free block */
602 b->nextfree = free;
603 b->prevfree = free;
604 }
605 }
606 heap->free = free;
607 }
608
609
610 void HEAP_Free(HEAP heap, SHEAP_Block* ptr)
611 {
612 SHEAP_HeapBlock* b, *p;
613 char _id[32];
614
615 if (!heap) {
616 CORE_LOG_X(10, eLOG_Warning, "Heap Free: NULL heap");
617 return;
618 }
619 assert(!heap->base == !heap->size);
620
621 if (!heap->chunk) {
622 CORE_LOGF_X(11, eLOG_Error,
623 ("Heap Free%s: Heap read-only", s_HEAP_Id(_id, heap)));
624 return;
625 }
626 if (!ptr)
627 return;
628
629 p = 0;
630 b = heap->base;
631 while (b < heap->base + heap->size) {
632 if (&b->head == ptr) {
633 if (HEAP_ISUSED(b)) {
634 s_HEAP_Free(heap, p, b);
635 } else if (HEAP_ISFREE(b)) {
636 CORE_LOGF_X(12, eLOG_Warning,
637 ("Heap Free%s: Freeing free block @%u",
638 s_HEAP_Id(_id, heap), HEAP_INDEX(b, heap->base)));
639 } else {
640 CORE_LOGF_X(13, eLOG_Error,
641 ("Heap Free%s: Heap corrupt @%u/%u (0x%08X, %u)",
642 s_HEAP_Id(_id, heap), HEAP_INDEX(b, heap->base),
643 heap->size, b->head.flag, b->head.size));
644 }
645 return;
646 }
647 p = b;
648 b = HEAP_NEXT(b);
649 }
650
651 CORE_LOGF_X(14, eLOG_Error,
652 ("Heap Free%s: Block not found", s_HEAP_Id(_id, heap)));
653 }
654
655
656 void HEAP_FreeFast(HEAP heap, SHEAP_Block* ptr, const SHEAP_Block* prev)
657 {
658 SHEAP_HeapBlock* b, *p;
659 char _id[32];
660
661 if (!heap) {
662 CORE_LOG_X(15, eLOG_Warning, "Heap Free: NULL heap");
663 return;
664 }
665 assert(!heap->base == !heap->size);
666
667 if (!heap->chunk) {
668 CORE_LOGF_X(16, eLOG_Error,
669 ("Heap Free%s: Heap read-only", s_HEAP_Id(_id, heap)));
670 return;
671 }
672 if (!ptr)
673 return;
674
675 p = (SHEAP_HeapBlock*) prev;
676 b = (SHEAP_HeapBlock*) ptr;
677 if (!s_HEAP_fast) {
678 if (b < heap->base || b >= heap->base + heap->size) {
679 CORE_LOGF_X(17, eLOG_Error,
680 ("Heap Free%s: Alien block", s_HEAP_Id(_id, heap)));
681 return;
682 } else if ((!p && b != heap->base) ||
683 ( p && (p < heap->base || HEAP_NEXT(p) != b))) {
684 CORE_LOGF_X(18, eLOG_Warning,
685 ("Heap Free%s: Invalid hint", s_HEAP_Id(_id, heap)));
686 HEAP_Free(heap, ptr);
687 return;
688 } else if (HEAP_ISFREE(b)) {
689 CORE_LOGF_X(19, eLOG_Warning,
690 ("Heap Free%s: Freeing free block @%u",
691 s_HEAP_Id(_id, heap), HEAP_INDEX(b, heap->base)));
692 return;
693 }
694 }
695
696 s_HEAP_Free(heap, p, b);
697 }
698
699
700 static SHEAP_Block* s_HEAP_Walk(const HEAP heap, const SHEAP_Block* ptr)
701 {
702 SHEAP_HeapBlock* p = (SHEAP_HeapBlock*) ptr;
703 SHEAP_HeapBlock* b;
704 char _id[32];
705
706 if (!p || (p >= heap->base && p < heap->base + heap->size)) {
707 b = p ? HEAP_NEXT(p) : heap->base;
708 if (b < heap->base + heap->size && b->head.size > sizeof(SHEAP_Block)
709 && HEAP_NEXT(b) <= heap->base + heap->size) {
710 if ((HEAP_ISFREE(b) || HEAP_ISUSED(b)) &&
711 (!s_HEAP_newalk || HEAP_ALIGN(b->head.size) == b->head.size)) {
712 if (s_HEAP_newalk) {
713 if (HEAP_ISUSED(b) && heap->chunk/*RW heap*/ &&
714 heap->base + heap->free == b) {
715 CORE_LOGF_X(20, eLOG_Warning,
716 ("Heap Walk%s: Used block @ free ptr %u",
717 s_HEAP_Id(_id, heap), heap->free));
718 } else if (HEAP_ISFREE(b)
719 && (b->prevfree >= heap->size ||
720 b->nextfree >= heap->size ||
721 !HEAP_ISFREE(heap->base + b->prevfree) ||
722 !HEAP_ISFREE(heap->base + b->nextfree) ||
723 (b->prevfree != b->nextfree
724 && (heap->base + b->prevfree == b ||
725 heap->base + b->nextfree == b)))) {
726 CORE_LOGF_X(21, eLOG_Warning,
727 ("Heap Walk%s: Free list corrupt @%u/%u"
728 " (%u, <-%u, %u->)", s_HEAP_Id(_id, heap),
729 HEAP_INDEX(b, heap->base), heap->size,
730 b->head.size, b->prevfree, b->nextfree));
731 }
732 }
733 /* Block 'b' seems okay for walking onto, but... */
734 if (!p)
735 return &b->head;
736 if (HEAP_ISLAST(p)) {
737 CORE_LOGF_X(22, eLOG_Error,
738 ("Heap Walk%s: Misplaced last block @%u",
739 s_HEAP_Id(_id,heap),
740 HEAP_INDEX(p, heap->base)));
741 } else if (s_HEAP_newalk && heap->chunk/*RW heap*/ &&
742 HEAP_ISLAST(b) && heap->base + heap->last != b) {
743 CORE_LOGF_X(23, eLOG_Error,
744 ("Heap Walk%s: Last block @%u "
745 "not @ last ptr %u",
746 s_HEAP_Id(_id, heap),
747 HEAP_INDEX(b, heap->base), heap->last));
748 } else if (HEAP_ISFREE(p) && HEAP_ISFREE(b)) {
749 const SHEAP_HeapBlock* c = heap->base;
750 while (c < p) {
751 if (HEAP_ISFREE(c) && HEAP_NEXT(c) >= HEAP_NEXT(b))
752 break;
753 c = HEAP_NEXT(c);
754 }
755 if (c < p)
756 return &b->head;
757 CORE_LOGF_X(24, eLOG_Error,
758 ("Heap Walk%s: Adjacent free blocks "
759 "@%u and @%u",
760 s_HEAP_Id(_id, heap),
761 HEAP_INDEX(p, heap->base),
762 HEAP_INDEX(b, heap->base)));
763 } else
764 return &b->head;
765 } else {
766 CORE_LOGF_X(25, eLOG_Error,
767 ("Heap Walk%s: Heap corrupt @%u/%u (0x%08X, %u)",
768 s_HEAP_Id(_id, heap), HEAP_INDEX(b, heap->base),
769 heap->size, b->head.flag, b->head.size));
770 }
771 } else if (b > heap->base + heap->size) {
772 CORE_LOGF_X(26, eLOG_Error,
773 ("Heap Walk%s: Heap corrupt", s_HEAP_Id(_id, heap)));
774 } else if (b && !HEAP_ISLAST(p)) {
775 CORE_LOGF_X(27, eLOG_Error,
776 ("Heap Walk%s: Last block lost",
777 s_HEAP_Id(_id, heap)));
778 }
779 } else {
780 CORE_LOGF_X(28, eLOG_Error,
781 ("Heap Walk%s: Alien pointer", s_HEAP_Id(_id, heap)));
782 }
783 return 0;
784 }
785
786
787 SHEAP_Block* HEAP_Walk(const HEAP heap, const SHEAP_Block* ptr)
788 {
789 if (!heap) {
790 CORE_LOG_X(29, eLOG_Warning, "Heap Walk: NULL heap");
791 return 0;
792 }
793 assert(!heap->base == !heap->size);
794
795 if (s_HEAP_fast) {
796 SHEAP_HeapBlock* b = (SHEAP_HeapBlock*) ptr;
797 if (!b)
798 return &heap->base->head;
799 b = HEAP_NEXT(b);
800 return b < heap->base + heap->size ? &b->head : 0;
801 }
802 return s_HEAP_Walk(heap, ptr);
803 }
804
805
806 HEAP HEAP_Trim(HEAP heap)
807 {
808 TNCBI_Size prev, hsize, size;
809 SHEAP_HeapBlock* f;
810 char _id[32];
811
812 if (!heap)
813 return 0;
814 assert(!heap->base == !heap->size);
815
816 if (!heap->chunk) {
817 CORE_LOGF_X(30, eLOG_Error,
818 ("Heap Trim%s: Heap read-only", s_HEAP_Id(_id, heap)));
819 return 0;
820 }
821
822 if (!(f = s_HEAP_Collect(heap, &prev)) || f->head.size < heap->chunk) {
823 assert(!f || (HEAP_ISFREE(f) && HEAP_ISLAST(f)));
824 size = 0;
825 hsize = heap->size << _HEAP_ALIGNSHIFT;
826 } else if (!(size = f->head.size % heap->chunk)) {
827 hsize = (heap->size << _HEAP_ALIGNSHIFT) - f->head.size;
828 if (f != heap->base + prev) {
829 f = heap->base + prev;
830 assert(HEAP_ISUSED(f));
831 }
832 } else {
833 assert(HEAP_ISFREE(f));
834 assert(size >= _HEAP_ALIGNMENT);
835 hsize = (heap->size << _HEAP_ALIGNSHIFT) - f->head.size + size;
836 }
837
838 if (heap->resize) {
839 SHEAP_HeapBlock* base = (SHEAP_HeapBlock*)
840 heap->resize(heap->base, hsize, heap->arg);
841 if (!hsize)
842 assert(!base);
843 else if (!base)
844 return 0;
845 if (_HEAP_ALIGN(base, sizeof(SHEAP_Block)) != (unsigned long) base) {
846 CORE_LOGF_X(31, eLOG_Warning,
847 ("Heap Trim%s: Unaligned base (0x%08lX)",
848 s_HEAP_Id(_id, heap), (long) base));
849 }
850 prev = HEAP_INDEX(f, heap->base);
851 heap->base = base;
852 heap->size = hsize >> _HEAP_ALIGNSHIFT;
853 if (base && f) {
854 f = base + prev;
855 f->head.flag |= HEAP_LAST;
856 if (HEAP_ISUSED(f)) {
857 heap->last = prev;
858 heap->free = heap->size;
859 } else if (size)
860 f->head.size = size;
861 }
862 assert(hsize == heap->size << _HEAP_ALIGNSHIFT);
863 assert(hsize % heap->chunk == 0);
864 } else if (hsize != heap->size << _HEAP_ALIGNSHIFT) {
865 CORE_LOGF_X(32, eLOG_Error,
866 ("Heap Trim%s: Heap not trimmable", s_HEAP_Id(_id, heap)));
867 }
868
869 assert(!heap->base == !heap->size);
870 return heap;
871 }
872
873
874 HEAP HEAP_Copy(const HEAP heap, size_t extra, int serial)
875 {
876 HEAP newheap;
877 TNCBI_Size size, hsize;
878
879 if (!heap)
880 return 0;
881 assert(!heap->base == !heap->size);
882
883 size = _HEAP_ALIGN(sizeof(*newheap), sizeof(SHEAP_Block));
884 hsize = heap->size << _HEAP_ALIGNSHIFT;
885 if (!(newheap = (HEAP) malloc(size + hsize + extra)))
886 return 0;
887 newheap->base = (SHEAP_HeapBlock*)(heap->base ? (char*)newheap + size : 0);
888 newheap->size = heap->size;
889 newheap->free = 0;
890 newheap->chunk = 0/*read-only*/;
891 newheap->resize = 0;
892 newheap->arg = 0;
893 newheap->refc = 1/*copy*/;
894 newheap->serial = serial;
895 if (hsize) {
896 memcpy(newheap->base, heap->base, hsize);
897 assert(memset((char*) newheap->base + hsize, 0, extra));
898 }
899 return newheap;
900 }
901
902
903 void HEAP_AddRef(HEAP heap)
904 {
905 if (!heap)
906 return;
907 assert(!heap->base == !heap->size);
908 if (heap->refc) {
909 heap->refc++;
910 assert(heap->refc);
911 }
912 }
913
914
915 void HEAP_Detach(HEAP heap)
916 {
917 if (!heap)
918 return;
919 assert(!heap->base == !heap->size);
920 if (!heap->refc || !--heap->refc) {
921 memset(heap, 0, sizeof(*heap));
922 free(heap);
923 }
924 }
925
926
927 void HEAP_Destroy(HEAP heap)
928 {
929 char _id[32];
930
931 if (!heap)
932 return;
933 assert(!heap->base == !heap->size);
934 if (!heap->chunk && !heap->refc) {
935 CORE_LOGF_X(33, eLOG_Error,
936 ("Heap Destroy%s: Heap read-only", s_HEAP_Id(_id, heap)));
937 } else if (heap->resize/*NB: NULL for heap copies*/)
938 verify(heap->resize(heap->base, 0, heap->arg) == 0);
939 HEAP_Detach(heap);
940 }
941
942
943 void* HEAP_Base(const HEAP heap)
944 {
945 if (!heap)
946 return 0;
947 assert(!heap->base == !heap->size);
948 return heap->base;
949 }
950
951
952 TNCBI_Size HEAP_Size(const HEAP heap)
953 {
954 if (!heap)
955 return 0;
956 assert(!heap->base == !heap->size);
957 return heap->size << _HEAP_ALIGNSHIFT;
958 }
959
960
961 int HEAP_Serial(const HEAP heap)
962 {
963 if (!heap)
964 return 0;
965 assert(!heap->base == !heap->size);
966 return heap->serial;
967 }
968
969
970 void HEAP_Options(ESwitch fast, ESwitch newalk)
971 {
972 switch (fast) {
973 case eOff:
974 s_HEAP_fast = 0/*false*/;
975 case eOn:
976 s_HEAP_fast = 1/*true*/;
977 break;
978 default:
979 break;
980 }
981 switch (newalk) {
982 case eOff:
983 s_HEAP_newalk = 0/*false*/;
984 break;
985 case eOn:
986 s_HEAP_newalk = 1/*true*/;
987 default:
988 break;
989 }
990 }
991 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |