/* $Id: ncbi_heapmgr.c,v 6.13 2001/07/31 15:07:58 lavr Exp $
* ===========================================================================
*
* PUBLIC DOMAIN NOTICE
* National Center for Biotechnology Information
*
* This software/database is a "United States Government Work" under the
* terms of the United States Copyright Act. It was written as part of
* the author's official duties as a United States Government employee and
* thus cannot be copyrighted. This software/database is freely available
* to the public for use. The National Library of Medicine and the U.S.
* Government have not placed any restriction on its use or reproduction.
*
* Although all reasonable efforts have been taken to ensure the accuracy
* and reliability of the software and data, the NLM and the U.S.
* Government do not and cannot warrant the performance or results that
* may be obtained by using this software or data. The NLM and the U.S.
* Government disclaim all warranties, express or implied, including
* warranties of performance, merchantability or fitness for any particular
* purpose.
*
* Please cite the author in any work or product based on this material.
*
* ===========================================================================
*
* Author: Anton Lavrentiev
*
* Abstract:
*
* This is a simple heap manager with a primitive garbage collection.
* The heap contains blocks of data, stored in the common contiguous pool,
* each block preceded with a SHEAP_Block structure. Low word of 'flag'
* is either non-zero (True), when the block is in use, or zero (False),
* when the block is vacant. 'Size' shows the length of the block in bytes,
* (uninterpreted) data field of which is extended past the header
* (the header size IS counted in the size of the block).
*
* When 'HEAP_Alloc' is called, the return value is either a heap pointer,
* which points to the block header, marked as allocated and guaranteed
* to have enough space to hold the requested data size; or 0 meaning, that the
* heap has no more room to provide such a block (reasons for that:
* heap is corrupted, heap has no provision to be expanded, expansion failed,
* or the heap was attached read-only).
*
* An application program can then use the data field on its need,
* providing not to overcome the size limit. The current block header
* can be used to find the next heap block with the use of 'size' member
* (note, however, some restrictions below).
*
* The application program is NOT assumed to keep the returned block pointer,
* as the garbage collection can occur on the next allocation attempt,
* thus making any heap pointers invalid. Instead, the application program
* can keep track of the heap base (header of the very first heap block -
* see 'HEAP_Create'), and the size of the heap, and can traverse the heap by
* this means, or with call to 'HEAP_Walk' (described below).
*
* While traversing, if the block found is no longer needed, it can be freed
* with 'HEAP_Free' call, supplying the address of the block header
* as an argument.
*
* Prior the heap use, the initialization is required, which comprises
* call to either 'HEAP_Create' or 'HEAP_Attach' with the information about
* the base heap pointer. 'HEAP_Create' also requires the size of initial
* heap area (if there is one), and size of chunk (usually, a page size)
* to be used in heap expansions (defaults to alignment if provided as 0).
* Additionally (but not compulsory) the application program can provide
* heap manager with 'expand' routine, which is supposed to be called,
* when no more room is available in the heap, or the heap was not
* preallocated (base = 0 in 'HEAP_Create'), and given the arguments:
* - current heap base address (or 0 if this is the very first heap alloc),
* - new required heap size (or 0 if this is the very last call to deallocate
* the entire heap).
* If successful, the expand routine must return the new heap base
* address (if any) of expanded heap area, and where the exact copy of
* the current heap is made.
*
* Note that all heap base pointers must be aligned on a 'double' boundary.
* Please also be warned not to store pointers to the heap area, as a
* garbage collection can clobber them. Within a block, however,
* it is possible to use local pointers (offsets), which remain same
* regardless of garbage collections.
*
* For automatic traverse purposes there is a 'HEAP_Walk' call, which returns
* the next block (either free, or used) from the heap. Given a NULL-pointer,
* this function returns the very first block, whereas all subsequent calls
* with the argument being the last observed block results in the next block
* returned. NULL comes back when no more blocks exist in the heap.
*
* Note that for proper heap operations, no allocations should happen between
* successive calls to 'HEAP_Walk', whereas deallocation of the seen block
* is okay.
*
* Explicit heap traversing should not overcome the heap limit,
* as any information above the limit is not maintained by the heap manager.
* Every heap operation guarantees, that there are no adjacent free blocks,
* only used blocks can follow each other sequentially.
*
* To discontinue to use the heap, 'HEAP_Destroy' or 'HEAP_Detach' can be
* called. The former deallocated the heap (by means of call to 'expand'),
* the latter just removes the heap handle, retaining the heap data intact.
* Later, such a heap could be used again if attached with 'HEAP_Attach'.
*
* Note that attached heap is in read-only mode, that is nothing can be
* allocated and/or freed in that heap, as well as an attempt to call
* 'HEAP_Destroy' will not destroy the heap data.
*
* Note also, that 'HEAP_Create' always does heap reset, that is the
* memory area pointed by 'base' (if not 0) gets reformatted and lose
* all previous contents.
*
* --------------------------------------------------------------------------
* $Log: ncbi_heapmgr.c,v $
* Revision 6.13 2001/07/31 15:07:58 lavr
* Added paranoia log message: freeing a block in a NULL heap
*
* Revision 6.12 2001/07/13 20:09:27 lavr
* If remaining space in a block is equal to block header,
* do not leave this space as a padding of the block been allocated,
* but instead form a new block consisting only of the header.
* The block becomes a subject for a later garbage collecting.
*
* Revision 6.11 2001/07/03 20:24:03 lavr
* Added function: HEAP_Copy()
*
* Revision 6.10 2001/06/25 15:32:41 lavr
* Typo fixed
*
* Revision 6.9 2001/06/19 22:22:56 juran
* Heed warning: Make s_HEAP_Take() static
*
* Revision 6.8 2001/06/19 19:12:01 lavr
* Type change: size_t -> TNCBI_Size; time_t -> TNCBI_Time
*
* Revision 6.7 2001/03/02 20:08:26 lavr
* Typos fixed
*
* Revision 6.6 2001/02/14 22:03:09 lavr
* 0x... constants explicitly made unsigned
*
* Revision 6.5 2001/01/12 23:51:39 lavr
* Message logging modified for use LOG facility only
*
* Revision 6.4 2000/05/23 21:41:07 lavr
* Alignment changed to 'double'
*
* Revision 6.3 2000/05/17 14:22:30 lavr
* Small cosmetic changes
*
* Revision 6.2 2000/05/16 15:06:05 lavr
* Minor changes for format <-> argument correspondence in warnings
*
* Revision 6.1 2000/05/12 18:33:44 lavr
* First working revision
*
* ==========================================================================
*/
#include "ncbi_priv.h"
#include
#include
#include
struct SHEAP_tag {
char* base;
TNCBI_Size size;
TNCBI_Size chunk;
FHEAP_Expand expand;
int/*bool*/ copy;
};
#define _HEAP_ALIGN(a, b) (((unsigned long) (a) + (b) - 1) & ~((b) - 1))
#define _HEAP_ALIGNMENT sizeof(double)
#define HEAP_ALIGN(a) _HEAP_ALIGN(a, _HEAP_ALIGNMENT)
#define HEAP_LAST 0x80000000UL
#define HEAP_USED 0x0DEAD2F0UL
#define HEAP_FREE 0
#define HEAP_ISFREE(b) (((b)->flag & ~HEAP_LAST) == HEAP_FREE)
#define HEAP_ISUSED(b) (((b)->flag & ~HEAP_LAST) == HEAP_USED)
#define HEAP_ISLAST(b) ((b)->flag & HEAP_LAST)
HEAP HEAP_Create(char* base, TNCBI_Size size,
TNCBI_Size chunk, FHEAP_Expand expand)
{
SHEAP_Block* b;
HEAP heap;
if ((!base && size) || (base && !size) ||
!(heap = (HEAP) malloc(sizeof(*heap))))
return 0;
chunk = (TNCBI_Size) HEAP_ALIGN(chunk);
if (!base) {
size = (TNCBI_Size) _HEAP_ALIGN(sizeof(*b) + 1, chunk);
if (!expand || !(base = (*expand)(base, size))) {
CORE_LOGF(eLOG_Warning,
("Heap Create: Cannot create (size = %u)",
(unsigned) size));
free(heap);
return 0;
}
}
if ((char*) HEAP_ALIGN(base) != base)
CORE_LOGF(eLOG_Warning,
("Heap Create: Unaligned base (0x%08lX)", (long) base));
if (size < (TNCBI_Size) HEAP_ALIGN(sizeof(*b) + 1))
CORE_LOGF(eLOG_Warning, ("Heap Create: Heap is too small (%u, %u)",
(unsigned) size, (unsigned) sizeof(*b)));
heap->base = base;
heap->size = size;
heap->chunk = chunk;
heap->expand = expand;
heap->copy = 0;
b = (SHEAP_Block*) heap->base;
b->flag = HEAP_FREE | HEAP_LAST;
b->size = size;
return heap;
}
HEAP HEAP_Attach(char* base)
{
SHEAP_Block* b;
HEAP heap;
if (!base || !(heap = (HEAP) malloc(sizeof(*heap))))
return 0;
if ((char*) HEAP_ALIGN(base) != base)
CORE_LOGF(eLOG_Warning,
("Heap Attach: Unaligned base (0x%08lX)", (long) base));
heap->size = 0;
for (b = (SHEAP_Block*) base; ; b = (SHEAP_Block*) ((char*) b + b->size)) {
if (!HEAP_ISUSED(b) && !HEAP_ISFREE(b)) {
CORE_LOGF(eLOG_Warning,
("Heap Attach: Heap corrupted (0x%08X, %u)",
b->flag, (unsigned) b->size));
free(heap);
return 0;
}
heap->size += b->size;
if (HEAP_ISLAST(b))
break;
}
heap->base = base;
heap->chunk = 0;
heap->expand = 0;
heap->copy = 0;
return heap;
}
/* Check if a given block 'b' is adjacent to a free block, which
* follows 'b', and/or to optionally passed previous block 'p'.
* Join block(s) to form a larger free block, and return a pointer
* to the next block.
*/
static SHEAP_Block* s_HEAP_Join(SHEAP_Block* p, SHEAP_Block* b)
{
/* Block following 'b' */
SHEAP_Block* n = (SHEAP_Block*) ((char*) b + b->size);
if (!HEAP_ISFREE(b))
CORE_LOG(eLOG_Warning, "Heap Join: Block is not free");
else {
if (!HEAP_ISLAST(b) && HEAP_ISFREE(n)) {
b->size += n->size;
b->flag = n->flag;
n = (SHEAP_Block*) ((char*) n + n->size);
}
if (p && HEAP_ISFREE(p)) {
p->size += b->size;
p->flag = b->flag;
}
}
return n;
}
/* Collect garbage in the heap, moving all contents to the
* top of the heap, and merging all free blocks at the end
* in one large free block. Return pointer to that free block.
*/
static SHEAP_Block* s_HEAP_Collect(HEAP heap)
{
SHEAP_Block* b = (SHEAP_Block*) heap->base, *f = 0;
while ((char*) b < heap->base + heap->size) {
if (HEAP_ISFREE(b))
f = b;
else if (HEAP_ISUSED(b) && f) {
unsigned int last = b->flag & HEAP_LAST;
TNCBI_Size save = f->size;
memmove(f, b, b->size);
f->flag &= ~HEAP_LAST;
f = (SHEAP_Block*) ((char*) f + f->size);
f->flag = HEAP_FREE | last;
f->size = save;
b = s_HEAP_Join(0, f);
continue;
}
b = (SHEAP_Block*) ((char*) b + b->size);
}
return f;
}
/* Take the block 'b' (maybe split in two, if it's roomy enough)
* for use of by at most 'size' bytes (including block header).
* Return the block to use if taken okay; 0 otherwise.
*/
static SHEAP_Block* s_HEAP_Take(SHEAP_Block* b, TNCBI_Size size)
{
unsigned int last = b->flag & HEAP_LAST;
if (HEAP_ISUSED(b)) {
CORE_LOG(eLOG_Warning, "Heap Take: Block is not free");
return 0;
}
if (b->size < size) {
CORE_LOG(eLOG_Warning, "Heap Take: Block is too small");
return 0;
}
if (b->size >= size + sizeof(*b)) {
SHEAP_Block* n = (SHEAP_Block*) ((char*) b + size);
n->flag = HEAP_FREE | last;
n->size = b->size - size;
b->flag = HEAP_USED;
b->size = size;
s_HEAP_Join(0, n);
} else
b->flag = HEAP_USED | last;
return b;
}
SHEAP_Block* HEAP_Alloc(HEAP heap, TNCBI_Size size)
{
SHEAP_Block* b, *p = 0;
TNCBI_Size free = 0;
if (!heap || size < 1)
return 0;
if (!heap->chunk) {
CORE_LOG(eLOG_Warning, "Heap Alloc: Heap is read-only");
return 0;
}
size = (TNCBI_Size) HEAP_ALIGN(sizeof(*b) + size);
b = (SHEAP_Block*) heap->base;
while ((char*) b < heap->base + heap->size) {
if (HEAP_ISFREE(b)) {
if (b->size >= size)
/* Empty, large enough block found, take it! */
return s_HEAP_Take(b, size);
free += b->size;
} else if (!HEAP_ISUSED(b)) {
CORE_LOGF(eLOG_Warning,
("Heap Alloc: Heap corrupted (0x%08X, %u)",
b->flag, (unsigned) b->size));
return 0;
}
p = b;
b = (SHEAP_Block*) ((char*) b + b->size);
}
/* Heap exhausted, no free block found */
if (free >= size)
b = s_HEAP_Collect(heap);
else if (!heap->expand)
return 0;
else {
TNCBI_Size hsize =
(TNCBI_Size) _HEAP_ALIGN(heap->size + size, heap->chunk);
ptrdiff_t dp = (char*) p - heap->base;
char* base;
if (!(base = (*heap->expand)(heap->base, hsize)))
return 0;
p = (SHEAP_Block*) (base + dp);
if (!HEAP_ISLAST(p))
CORE_LOG(eLOG_Warning, "Heap Alloc: Last block lost");
if (HEAP_ISUSED(p)) {
p->flag &= ~HEAP_LAST;
/* New block is the very top on the heap */
b = (SHEAP_Block*) (base + heap->size);
b->size = hsize - heap->size;
b->flag = HEAP_FREE | HEAP_LAST;
} else {
/* Extend last free block */
p->size += hsize - heap->size;
b = p;
}
heap->base = base;
heap->size = hsize;
}
return s_HEAP_Take(b, size);
}
void HEAP_Free(HEAP heap, SHEAP_Block* ptr)
{
SHEAP_Block* b, *p = 0;
if (!heap || !ptr) {
if (ptr)
CORE_LOG(eLOG_Warning, "Heap Free: Cannot free in NULL heap");
return;
}
if (!heap->chunk) {
CORE_LOG(eLOG_Warning, "Heap Free: Heap is read-only");
return;
}
b = (SHEAP_Block*) heap->base;
while ((char*) b < heap->base + heap->size) {
if (HEAP_ISFREE(b)) {
if (b == ptr) {
CORE_LOG(eLOG_Warning, "Heap Free: Freeing free block");
return;
}
} else if (HEAP_ISUSED(b)) {
if (b == ptr) {
b->flag = HEAP_FREE | (b->flag & HEAP_LAST);
s_HEAP_Join(p, b);
return;
}
} else {
CORE_LOGF(eLOG_Warning,
("Heap Free: Heap corrupted (0x%08X, %u)",
b->flag, (unsigned) b->size));
return;
}
p = b;
b = (SHEAP_Block*) ((char*) p + p->size);
}
CORE_LOG(eLOG_Warning, "Heap Free: Block not found");
}
SHEAP_Block* HEAP_Walk(HEAP heap, const SHEAP_Block* p)
{
SHEAP_Block* b;
if (!heap) {
CORE_LOG(eLOG_Warning, "Heap Walk: NULL heap");
return 0;
}
if (!p ||
((char*) p >= heap->base && (char*) p < heap->base + heap->size)) {
b = (SHEAP_Block*) (p ? (char*) p + p->size : heap->base);
if ((char*) b < heap->base + heap->size) {
if (b->size >= sizeof(*b) &&
b->size == (TNCBI_Size) HEAP_ALIGN(b->size) &&
(char*) b + b->size <= heap->base + heap->size &&
(HEAP_ISFREE(b) || HEAP_ISUSED(b))) {
/* Block 'b' seems valid, but... */
if (!p)
return b;
if (HEAP_ISLAST(p))
CORE_LOG(eLOG_Warning, "Heap Walk: Misplaced last block");
else if (HEAP_ISFREE(b) && HEAP_ISFREE(p))
CORE_LOG(eLOG_Warning, "Heap Walk: Adjacent free blocks");
else
return b;
} else
CORE_LOGF(eLOG_Warning,
("Heap Walk: Heap corrupted (0x%08X, %u)",
b->flag, (unsigned) b->size));
} else if ((char*) b > heap->base + heap->size)
CORE_LOG(eLOG_Warning, "Heap Walk: Heap corrupted");
else if (!HEAP_ISLAST(p))
CORE_LOG(eLOG_Warning, "Heap Walk: Last block lost");
} else
CORE_LOG(eLOG_Warning, "Heap Walk: Alien pointer passed");
return 0;
}
HEAP HEAP_Copy(HEAP heap)
{
HEAP newheap;
char* buf;
if (!heap ||
!(buf = (char*) malloc(HEAP_ALIGN(heap->size) + sizeof(*newheap))))
return 0;
memcpy(buf, heap->base, heap->size);
newheap = (HEAP) (buf + HEAP_ALIGN(heap->size));
newheap->base = buf;
newheap->size = heap->size;
newheap->chunk = 0;
newheap->expand = 0;
newheap->copy = 1;
return newheap;
}
void HEAP_Detach(HEAP heap)
{
if (heap) {
if (heap->copy)
free(heap->base);
else
free(heap);
}
}
void HEAP_Destroy(HEAP heap)
{
if (heap) {
if (!heap->chunk && !heap->copy) {
CORE_LOG(eLOG_Warning, "Heap Destroy: Heap is read-only");
return;
}
if (heap->expand)
(*heap->expand)(heap->base, 0);
HEAP_Detach(heap);
}
}