gdk_heap.c

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

			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
}



#line 985 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_heap.mx"


#line 994 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_heap.mx"
/* 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;
}



#line 1054 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_heap.mx"