gdk_heap.mx

这个是内存数据库中的一个管理工具

	size_t next;		/* index of next block                   */
} CHUNK;

@c
#define roundup_8(x)	(((x)+7)&~7)
#define roundup_4(x)	(((x)+3)&~3)
#define blocksize(h,p)	((p)->size)

static INLINE size_t
roundup_num(size_t number, size_t alignment)
{
	size_t rval = number + alignment - 1;

	rval -= (rval % alignment);
	return (rval);
}

size_t
HEAP_private(Heap *h)
{
	(void) h;
	return roundup_8(sizeof(HEADER));
}

#ifdef TRACE
static void
HEAP_printstatus(Heap *heap)
{
	HEADER *hheader = HEAP_index(heap, 0, HEADER);
	size_t block, cur_free = hheader->head;
	CHUNK *blockp;

	THRprintf(GDKout, "#HEAP has head " SZFMT " and alignment %d and size " SZFMT "\n", hheader->head, hheader->alignment, heap->free);

	/*
	   // Walk the blocklist;
	 */
	block = hheader->firstblock;

	while (block < heap->free) {
		blockp = HEAP_index(heap, block, CHUNK);

		if (block == cur_free) {
			THRprintf(GDKout, "#   free block at " PTRFMT " has size " SZFMT " and next " SZFMT "\n", PTRFMTCAST(void *)block, blockp->size, blockp->next);

			cur_free = blockp->next;
			block += blockp->size;
		} else {
			size_t size = blocksize(hheader, blockp);

			THRprintf(GDKout, "#   block at " SZFMT " with size " SZFMT "\n", block, size);
			block += size;
		}
	}
}
#endif /* TRACE */

static void
HEAP_empty(Heap *heap, size_t nprivate, int alignment)
{
	/*
	   // Find position of header block.
	 */
	HEADER *hheader = HEAP_index(heap, 0, HEADER);

	/*
	   // Calculate position of first and only free block.
	 */
	size_t head = roundup_num(roundup_8(sizeof(HEADER)) + roundup_8(nprivate), alignment);
	CHUNK *headp = HEAP_index(heap, head, CHUNK);

	/*
	   // Fill header block.
	 */
	hheader->head = head;
	hheader->sizefcn = NULL;
	hheader->alignment = alignment;
	hheader->firstblock = head;
	hheader->version = HEAPVERSION;

	/*
	   // Fill first free block.
	 */
	headp->size = heap->size - head;
	headp->next = 0;
#ifdef TRACE
	THRprintf(GDKout, "#We created the following heap\n");
	HEAP_printstatus(heap);
#endif
}

void
HEAP_initialize(Heap *heap, size_t nbytes, size_t nprivate, int alignment)
{
	/*
	   // For now we know about two alignments.
	 */
	if (alignment != 8) {
		alignment = 4;
	}
	if ((size_t) alignment < sizeof(size_t))
		alignment = sizeof(size_t);

	/*
	   // Calculate number of bytes needed for heap + structures.
	 */
	{
		size_t total = 100 + nbytes + nprivate + sizeof(HEADER) + sizeof(CHUNK);

		total = roundup_8(total);
		if (HEAPalloc(heap, total, 1) < 0)
			return;
		heap->free = heap->size;
	}

	/*
	   // initialize heap as empty
	 */
	HEAP_empty(heap, nprivate, alignment);
}


var_t
HEAP_malloc(Heap *heap, size_t nbytes)
{
	size_t block, trail, ttrail;
	CHUNK *blockp;
	CHUNK *trailp;
	HEADER *hheader = HEAP_index(heap, 0, HEADER);

#ifdef TRACE
	THRprintf(GDKout, "#Enter malloc with " SZFMT " bytes\n", nbytes);
#endif

	/* add space for size field */
	nbytes += hheader->alignment;
	if (hheader->alignment == 8) {
		nbytes = roundup_8(nbytes);
	} else if (hheader->alignment == 4) {
		nbytes = roundup_4(nbytes);
	} else {
		GDKfatal("HEAP_malloc: Heap structure corrupt\n");
	}
	if (nbytes < sizeof(CHUNK))
		nbytes = sizeof(CHUNK);

	/*
	   // block  -- points to block with acceptable size (if available).
	   // trail  -- points to predecessor of block.
	   // ttrail -- points to predecessor of trail.
	 */
	ttrail = 0;
	trail = 0;
	for (block = hheader->head; block != 0; block = HEAP_index(heap, block, CHUNK)->next) {
		blockp = HEAP_index(heap, block, CHUNK);

#ifdef TRACE
		THRprintf(GDKout, "#block " SZFMT " is " SZFMT " bytes\n", block, blockp->size);
#endif
		if ((trail != 0) && (block <= trail))
			GDKfatal("HEAP_malloc: Free list is not orderered\n");

		if (blockp->size >= nbytes)
			break;
		ttrail = trail;
		trail = block;
	}

	/*
	   // If no block of acceptable size is found we try to enlarge the heap.
	 */
	if (block == 0) {
		size_t newsize = roundup_8((size_t) (heap->free + MAX(heap->free, nbytes)));

		block = heap->free;	/* current end-of-heap */

#ifdef TRACE
		THRprintf(GDKout, "#No block found\n");
#endif

		/*
		   // Double the size of the heap.
		   // TUNE: increase heap by diffent amount.
		 */
		if (HEAPextend(heap, newsize) < 0)
			return 0;
		heap->free = newsize;
		hheader = HEAP_index(heap, 0, HEADER);

		blockp = HEAP_index(heap, block, CHUNK);
		trailp = HEAP_index(heap, trail, CHUNK);

#ifdef TRACE
		THRprintf(GDKout, "#New block made at pos " SZFMT " with size " SZFMT "\n", block, heap->size - block);
#endif

		blockp->next = 0;
		blockp->size = heap->free - block;	/* determine size of allocated block */

		/*
		   // Try to join the last block in the freelist and the newly allocated
		   // memory
		 */
		if ((trail != 0) && (trail + trailp->size == block)) {
#ifdef TRACE
			THRprintf(GDKout, "#Glue newly generated block to adjacent last\n");
#endif

			trailp->size += blockp->size;
			trailp->next = blockp->next;

			block = trail;
			trail = ttrail;
		}
	}

	/*
	   // Now we have found a block which is big enough in block.
	   // The predecessor of this block is in trail.
	 */
	trailp = HEAP_index(heap, trail, CHUNK);
	blockp = HEAP_index(heap, block, CHUNK);

	/*
	   // If selected block is bigger than block needed split block in two.
	   // TUNE: use different amount than 2*sizeof(CHUNK)
	 */
	if (blockp->size >= nbytes + 2 * sizeof(CHUNK)) {
		size_t newblock = block + nbytes;
		CHUNK *newblockp = HEAP_index(heap, newblock, CHUNK);

		newblockp->size = blockp->size - nbytes;
		newblockp->next = blockp->next;

		blockp->next = newblock;
		blockp->size = nbytes;
	}

	/*
	   // Delete block from freelist
	 */
	if (trail == 0) {
		hheader->head = blockp->next;
	} else {
		trailp = HEAP_index(heap, trail, CHUNK);

		trailp->next = blockp->next;
	}

	block += hheader->alignment;
	return block;
}

void
HEAP_free(Heap *heap, var_t block)
{
	HEADER *hheader = HEAP_index(heap, 0, HEADER);
	CHUNK *beforep;
	CHUNK *blockp;
	CHUNK *afterp;
	size_t after, before;

	if (hheader->alignment != 8 && hheader->alignment != 4) {
		GDKfatal("HEAP_free: Heap structure corrupt\n");
	}

	block -= hheader->alignment;
	blockp = HEAP_index(heap, block, CHUNK);

	/*
	   // block   -- block which we want to free
	   // before  -- first free block before block
	   // after   -- first free block after block
	 */

	before = 0;
	for (after = hheader->head; after != 0; after = HEAP_index(heap, after, CHUNK)->next) {
		if (after > block)
			break;
		before = after;
	}

	beforep = HEAP_index(heap, before, CHUNK);
	afterp = HEAP_index(heap, after, CHUNK);

	/*
	   // If it is not the last free block.
	 */
	if (after != 0) {
		/*
		   // If this block and the block after are consecutive.
		 */
		if (block + blockp->size == after) {
			/*
			   // We unite them.
			 */
			blockp->size += afterp->size;
			blockp->next = afterp->next;
		} else
			blockp->next = after;
	} else {
		/*
		   // It is the last block in the freelist.
		 */
		blockp->next = 0;
	}

	/*
	   //  If it is not the first block in the list.
	 */
	if (before != 0) {
		/*
		   // If the before block and this block are consecutive.
		 */
		if (before + beforep->size == block) {
			/*
			   // We unite them.
			 */
			beforep->size += blockp->size;
			beforep->next = blockp->next;
		} else
			beforep->next = block;
	} else {
		/*
		   //  Add block at head of free list.
		 */
		hheader->head = block;
	}
}

int
HEAP_check(Heap *heap, HeapRepair *hr)
{
	HEADER *hheader = HEAP_index(heap, 0, HEADER);
	size_t head = hheader->head, alignshift = 2;
	size_t block, nwords = (heap->free - 1) >> 7;
	size_t *freemask, prevblock = 0;
	CHUNK *blockp;

	hr->alignment = hheader->alignment;
	hr->minpos = sizeof(HEADER);
	hr->maxpos = heap->free;
	hr->validmask = NULL;

	if (hheader->alignment == 8) {
		nwords >>= 1;
		alignshift = 3;
	} else if (hheader->alignment != 4) {
		GDKerror("HEAP_check: Heap structure corrupt alignment = %d\n", hheader->alignment);
		return FALSE;
	}
	if ((head != roundup_num(head, hheader->alignment))) {
		GDKerror("HEAP_check: Heap structure corrupt: head = %d\n", head);
		return FALSE;
	}

	/*
	   // Create bitmasks that will hold all valid block positions
	 */
	hr->validmask = (size_t *) GDKmalloc(sizeof(size_t) * ++nwords);
	freemask = (size_t *) GDKmalloc(sizeof(size_t) * nwords);
	for (block = 0; block < nwords; block++)
		freemask[block] = hr->validmask[block] = 0;

	/*
	   // Walk the freelist; register them in freemask
	 */
	for (block = hheader->head; block != 0; block = HEAP_index(heap, block, CHUNK)->next) {
		size_t idx = block >> alignshift;
		size_t pos = idx >> 5;
		size_t mask = (size_t) 1 << (idx & 31);

		if ((block <= prevblock) && (block != 0)) {
			GDKerror("HEAP_check: Freelist is not ordered\n");
		} else if (block <= 0 || block > heap->free) {
			GDKerror("HEAP_check: Entry freelist corrupt: block %d not in heap\n", block);
		} else {
			freemask[pos] |= mask;
			continue;
		}
		goto xit;
	}

	/*
	   // Walk the blocklist; register in validmask/eliminate from freemask
	 */
	block = hheader->firstblock;
	while (block < heap->free) {
		size_t idx = block >> alignshift;
		size_t pos = idx >> 5;
		size_t mask = (size_t) 1 << (idx & 31);

		hr->validmask[pos] |= mask;
		blockp = HEAP_index(heap, block, CHUNK);

		if (freemask[pos] & mask) {
			freemask[pos] &= ~mask;
			block += blockp->size;
		} else {
			block += blocksize(hheader, blockp);
		}
	}
	if (block != heap->free) {
		GDKerror("HEAP_check: Something wrong with heap\n");
		goto xit;
	}

	/*
	   // Check if there are left over free blocks
	 */
	for (block = hheader->head; block != 0; block = HEAP_index(heap, block, CHUNK)->next) {
		size_t idx = block >> alignshift;
		size_t pos = idx >> 5;
		size_t mask = (size_t) 1 << (idx & 31);

		if (freemask[pos] & mask) {
			GDKerror("HEAP_check: Entry freelist corrupt: block %d not in blocklist\n", block);
			goto xit;
		}
	}
	GDKfree(freemask);
	return TRUE;
      xit:
	GDKfree(freemask);
	GDKfree(hr->validmask);
	hr->validmask = NULL;
	return FALSE;
}

void
HEAP_checkformat(Heap *heap)
{
#if 0
	HEADER_OTHER image = *HEAP_index(heap, 0, HEADER_OTHER);

	if (image.alignment == 4 || image.alignment == 8) {
		/* it is the other format => correct to the desired format */
		HEADER *hheader = HEAP_index(heap, 0, HEADER);

#if SIZEOF_SIZE_T==8
		size_t hasfcn = *(size_t *) & image.sizefcn;
#else
		size_t hasfcn = (size_t) (image.sizefcn || image.dummy);

		hheader->dummy = 0;
#endif
		hheader->head = image.head;
		hheader->firstblock = image.firstblock;
		hheader->alignment = image.alignment;
		hheader->sizefcn = (int (*)(ptr)) hasfcn;
	}
#else
	(void) heap;
#endif
}

@}
@-
If the elements in the heap tend to be small, it is a waste to allocate extra space
for a size field. especially so if we know that we are going to store only one kind
of atoms in the heap. from the content of the atom we can then derive its length. 
Such a heap can now be created with the HEAP_initialize_compact() function.
The HEAP_init() function is called in the BAT load sequence, if Monet sees that a 
standard heap is being loaded (it looks for a directly registered HEAP_check ADT function). 
@{
@c
/* save space in the heap by registering a size function */
void
HEAP_initialize_compact(Heap *heap, size_t nbytes, size_t nprivate, int alignment, int (*sizefcn) (ptr val))
{
	HEAP_initialize(heap, nbytes, nprivate, alignment);
	if (heap->base) {
		HEADER *hheader = HEAP_index(heap, 0, HEADER);

		hheader->sizefcn = sizefcn;
	}
}

/* reinitialize the size function after a load */
void
HEAP_init(Heap *heap, int tpe)
{
	HEADER *hheader = HEAP_index(heap, 0, HEADER);

	if (hheader->sizefcn) {
		hheader->sizefcn = BATatoms[tpe].atomLen;
	}

	/* make sure the freelist does not point after the end of the heap */
	if (hheader->head > heap->free) {
		hheader->head = 0;	/* cut off free block */
	} else if (hheader->head) {
		size_t idx = hheader->head;

		while (idx) {
			CHUNK *blk = HEAP_index(heap, idx, CHUNK);

			if (idx + blk->size > heap->free) {
				blk->size = heap->free - idx;	/* cut off illegal tail of block */
			}
			if (blk->next > heap->free || blk->next < (idx + blk->size) || (blk->next & (hheader->alignment - 1))) {
				blk->next = 0;	/* cut off next block */
				break;
			}
			idx = blk->next;
		}
	}
}

/* a heap is mmapabble (in append-only mode) if it only has a hole at the end */
int
HEAP_mmappable(Heap *heap)
{
	HEADER *hheader = HEAP_index(heap, 0, HEADER);

	if (hheader->head) {
		CHUNK *blk = HEAP_index(heap, hheader->head, CHUNK);

		if (hheader->head + blk->size >= heap->free) {
			return TRUE;
		}
	}
	return FALSE;
}

@}