gdk_heap.mx

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

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f gdk_heap
@a Peter Boncz, Wilko Quak
@+ Atom Heaps
Heaps are the basic mass storage structure of Monet. A heap is a handle
to a large, possibly huge, contiguous area of main memory, that can
be allocated in various ways (discriminated by the heap->storage field):

@table @code
@item STORE_MEM: malloc-ed memory
small (or rather: not huge) heaps are allocated with GDKmalloc.
Notice that GDKmalloc may redirect big requests to anonymous
virtual memory to prevent @emph{memory fragmentation} in the 
malloc library (see gdk_utils.mx). 

@item STORE_MMAP: read-only mapped region
this is a file on disk that is mapped into virtual memory.   
This is normally done MAP_SHARED, so we can use msync() to commit dirty 
data using the OS virtual memory management.

@item STORE_PRIV: read-write mapped region
in order to preserve ACID properties, we use a different memory mapping
on virtual memory that is writable, This is because in case of a crash
on a dirty STORE_MMAP heap, the OS may have written some of the dirty pages
to disk and other not (but it is impossible to determine which).  The OS 
MAP_PRIVATE mode does not modify the file on which is being mapped, rather 
creates substitute pages dynamically taken from the swap file when modifications 
occur. This is the only way to make writing to mmap()-ed regions safe.

@end table

On huge requests, we now open a X.priv file and memory map it (STORE_MMAP).
This is done for heaps of new BATs: these are writable (non-readonly), but 
are non-persistent (yet). Such BATs may be made persistent later on, of course.
Thus, the commit protocol BBPsync/heap_move (gdk_bbp.mx) actually does
not check anymore for hp->storage == STORE_PRIV, but rather for a .priv suffix 
in hp->filename. Thus, persistent STORE_MMAP/.priv heaps are saved with
by explicitly writing a separate full file X to disk (this is expensive, though!).

Related to this is saving BAT descriptors. These contain hp->storage fields that 
reflect how the heap should be loaded the *next* time the BAT is re-loaded (may differ
from the *current* mode). In the case of persistent, writable STORE_MMAP
bats (with a X.priv file), we set the `future-storage' to STORE_PRIV. Thus, after
surviving their first commit, any re-load of the BAT will put it in its safe
storage mapping (STORE_PRIV). This is in DESCsetmodes/HEAPcheckmode (gdk_storage.mx).

Another hairy heap issue is changing the BAT readonly/writable state. This 
sometimes implies flushing heaps to disk and even re-loading them with a new 
storage mode.  This is discussed in detail in BATsetaccess (gdk_bat.mx).
@{
@c
#include "monetdb_config.h"
#include "gdk.h"

static char *
decompose_filename(str nme)
{
	char *ext, *priv;

	ext = strchr(nme, '.');	/* extract base and ext from heap file name */
	if (ext) {
		*ext++ = 0;
		priv = strchr(ext, '.');
		if (priv)
			*priv = 0;
	}
	return ext;
}

@}
@- HEAPalloc

Normally, we use GDKmalloc for creating a new heap.  Huge heaps, though, come 
from X.priv files that we create with a large seek (fast, and leads to 
files-with-holes on Unixes).  For this purpose, the filename (X) is supposed 
to have been stored in the heap (NULL is a legal value).

It would have been better to pass this name as a parameter, but this would
also require changing the atom extension ADT interface plus modifying all
extension modules that introduce variable-size atoms (e.g. polygon), as these
provide overloaded versions of HEAPalloc (without heap name, currently).
@{
@c
int
HEAPalloc(Heap *h, size_t nitems, size_t itemsize)
{
	char nme[PATHLENGTH], *ext = NULL;

	if (h->filename) {
		strcpy(nme, h->filename);
		ext = decompose_filename(nme);
	}
	h->base = NULL;
	h->maxsize = h->size = 1;
	h->copied = 0;
	if (itemsize)
		h->maxsize = h->size = MAX(1, nitems) * itemsize;
	h->free = 0;

	/* check for overflow */
	if (itemsize && nitems > (h->size/itemsize)) 
		return -1;

	/* when using anonymous vm we malloc we need 64K chunks, also we
	 * 20% extra malloc */
	if (h->size > GDK_mem_bigsize) {
		h->maxsize = (size_t) ((double) h->maxsize * BATMARGIN) - 1;
		h->maxsize = (1 + (h->maxsize >> 16)) << 16;
	}
	if (h->filename == NULL || (h->size < GDK_vm_minsize)) {
		h->storage = STORE_MEM;
		h->base = (char *) GDKmallocmax(h->size, &h->maxsize, 0);
		if (h->base == 0) 
			GDKerror("HEAPalloc: Insufficient space for HEAP.");
	}
	if (h->filename && h->base == NULL) {
		char privext[PATHLENGTH], *of = h->filename;
		FILE *fp;

		h->filename = NULL;
		sprintf(privext, "%s.priv", ext);
		fp = GDKfilelocate(nme, "wb", privext);
		if (fp != NULL) {
			fclose(fp);
			/* a non-persistent heap: we create a .priv but *not* MMAP_PRIV !!! */
			h->storage = STORE_MMAP;
			HEAPload(h, nme, ext, FALSE);
		}
		GDKfree(of);
	}
	h->newstorage = h->storage;
	return (h->base == NULL) ? -1 : 0;
}

@}
@- HEAPextend

Normally (last case in the below code), we use GDKrealloc, except for the case that the 
heap extends to a huge size, in which case we open an X.priv file and memory map it.

Observe that we may assume that the BAT is writable here (otherwise, why extend?).

For memory mapped files, we may try to extend the file after the end, and also
extend the VM space we already have. This may fail, e.g. due to VM fragmentation
or no swap space (we map the new segment STORE_PRIV). Also, some OS-es might
not support this at all (NOEXTEND_PRIVMAP).

The other way is to just save the mmap-ed heap, free it and reload it.
@{
@c
int
HEAPextend(Heap *h, size_t size)
{
	char nme[PATHLENGTH], *ext = NULL;

	if (h->filename) {
		strcpy(nme, h->filename);
		ext = decompose_filename(nme);
	}
	if (size <= h->size)
		return 0;

	if (h->storage & STORE_MMAP) {
		/* memory mapped files extend: save and remap */
		if (HEAPsave(h, nme, ext) < 0)
			return -1;
		HEAPfree(h);
		h->maxsize = h->size = size;
		if (HEAPload(h, nme, ext, FALSE) >= 0)
			return 0;
	} else {
		/* extend a malloced heap, possibly switching over to file-mapped storage */
		Heap bak = *h;
		int can_mmap = (h->filename && size >= GDK_mem_bigsize);
		int must_mmap = can_mmap && (size >= GDK_vm_minsize || (h->newstorage & STORE_MMAP));
		h->size = size;

		if (can_mmap) {
			/* in anonymous vm, if have to realloc anyway, we reserve some extra space */
			if (size > h->maxsize) {
				h->maxsize = (size_t) ((double) size * BATMARGIN);
			}
			/* when using anonymous vm we malloc we need 64K chunks */
			h->maxsize = (1 + ((h->maxsize-1) >> 16)) << 16;
		} else {
			h->maxsize = size; /* for normal GDKmalloc, maxsize = size */
		}

		/* try GDKrealloc if the heap size stays within reasonable limits */
		if (!must_mmap) {
			h->storage = STORE_MEM;
			h->base = (char *) GDKreallocmax(h->base, size, &h->maxsize, 0);
			if (h->base)
				return 0;
		}
		/* too big: convert it to a disk-based temporary heap */
		if (can_mmap) {
			char privext[PATHLENGTH], *of = h->filename;
			FILE *fp;

			h->filename = NULL;
			sprintf(privext, "%s.priv", ext);
			fp = GDKfilelocate(nme, "wb", privext);
			if (fp != NULL) {
				fclose(fp);
				/* a non-persistent heap: we create a .priv but *not* MMAP_PRIV !!! */
				h->storage = STORE_MMAP;
				if (HEAPload(h, nme, ext, FALSE) >= 0) {
					memcpy(h->base, bak.base, bak.free);
					HEAPfree(&bak);
					return 0;
				}
			}
			GDKfree(of);
		}
		*h = bak;
	}
	return -1;
}

@}
@- HEAPcopy
simple: alloc and copy. Notice that we suppose a preallocated dst->filename (or NULL),
which might be used in HEAPalloc().
@{
@c
int
HEAPcopy(Heap *dst, Heap *src)
{
	if (HEAPalloc(dst, src->size, 1) == 0) {
		dst->free = src->free;
		memcpy(dst->base, src->base, src->free);
		return 0;
	}
	return -1;
}

@}
@- HEAPfree
Is now called even on heaps without memory, just to free the pre-allocated filename.
simple: alloc and copy.
@{
@c
int
HEAPfree(Heap *h)
{
	if (h->base) {
		if (h->storage == STORE_MEM) {	/* plain memory */
			GDKfree(h->base);
		} else {	/* mapped file, or STORE_PRIV */
			int ret = GDKmunmap(h->base, h->maxsize);

			if (ret < 0) {
				GDKsyserror("HEAPfree: %s was not mapped\n", h->filename);
				assert(0);
			}
			IODEBUG THRprintf(GDKout, "#munmap(base=" PTRFMT ", size=" SZFMT ") = %d\n", PTRFMTCAST(void *)h->base, h->maxsize, ret);
		}
		h->base = NULL;
	}
	if (h->filename) {
		GDKfree(h->filename);
		h->filename = NULL;
	}
	return 0;
}

@}
@- HEAPload

If we don't find file X, we try to move X.priv to it. 

If we find both an X and X.priv, the latter is killed.

For STORE_PRIV, we actually then move X to X.priv and mmap on it.
For the other modes, we access X as-is.

This routine initializes the h->filename without deallocating
its previous contents.
@{
@c
int
HEAPload(Heap *h, str nme, str ext, int trunc)
{
	FILE *fp = (FILE *) GDKfilelocate(nme, "mrb", ext);
	int ret = 0, desc_status = 0;
	size_t truncsize = (1 + (((size_t) (h->free * 1.05)) >> REMAP_PAGE_MAXBITS)) << REMAP_PAGE_MAXBITS;
	size_t minsize = (1 + ((h->size - 1) >> REMAP_PAGE_MAXBITS)) << REMAP_PAGE_MAXBITS;
	int priv_storage = (h->storage == STORE_PRIV);
	char priv[80]={0};

	h->maxsize = h->size;
	h->filename = NULL;

	/* round up mmap heap sizes to REMAP_PAGE_MAXSIZE (usually 512KB) segments */
	if ((h->storage & STORE_MMAP) && (minsize != h->size)) {
		h->size = minsize;
		h->maxsize = MAX(minsize, h->maxsize);
	}
	IODEBUG {
		THRprintf(GDKout, "#HEAPload(%s.%s,storage=%d,free=" SZFMT ",size=" SZFMT ")\n", nme, ext, h->storage, h->free, h->size);
	}
	/* On some OSs (WIN32,Solaris), it is prohibited to write to a file that is open 
	 * in MAP_PRIVATE (FILE_MAP_COPY) solution: read from a file renamed to .ext.priv 
	 * .ex.priv files are now also used with STORE_MMAP mode on huge uncommitted BATs.
	 */
	strcpy(priv, ext);
	strcat(priv, ".priv");
	if (fp) {
		ret = fclose(fp);
	} else {
		priv_storage = TRUE;	/* file may be in X.priv file iso X */
	}
	if (priv_storage) {
		long_str path;

		GDKfilepath(path, BATDIR, nme, priv);
		if (fp == NULL) {
			struct stat st;

			ret = stat(path, &st);
		} else {
			/* silently remove any previous .ext.priv file */
			(void) unlink(path);
			ret = GDKmove(BATDIR, nme, ext, BATDIR, nme, priv);
		}
		ext = priv;
	}
	if (ret) {
		return -1;	/* file could not be located */
	}
	/* legacy 2: some old repositories have wasted space => truncate during load */
	if (trunc && truncsize < h->size) {
		fp = (FILE *) GDKfilelocate(nme, "mrb+", ext);
		if (fp) {
			ret = ftruncate(fileno(fp), (off_t) truncsize);
			IODEBUG THRprintf(GDKout, "#ftruncate(file=%s.%s, size=" SZFMT ") = %d\n", nme, ext, truncsize, ret);

			fclose(fp);
			if (ret == 0) {
				h->size = h->maxsize = truncsize;
				desc_status = 1;
			}
		}
	}
	h->base = (char *) GDKload(nme, ext, h->free, h->size, h->storage);
	if (h->base == NULL) {
		return -1;	/* file could  not be read satisfactorily */
	}
	h->newstorage = h->storage;
	h->filename = (char *) GDKmalloc(strlen(nme) + strlen(ext) + 2);
	sprintf(h->filename, "%s.%s", nme, ext);

	return desc_status;	/* ok */
}

@}
@- HEAPsave

Saving STORE_MEM will do a write(fd, buf, size) in GDKsave (explicit IO).

Saving a STORE_PRIV (X.priv) heap means that we must actually write to X, thus
we convert the mode passed to GDKsave to STORE_MEM.

Saving STORE_MMAP will do a msync(buf, MSSYNC) in GDKsave (implicit IO).

After GDKsave returns successfully (>=0), we assume the heaps are safe on stable storage.
@c
@{
int HEAPsave(Heap* h, str nme, str ext) {
	int store = h->storage;
	char *p = h->filename;

	if (h->base == NULL) {
		return -1;
	} 
	if (p == NULL || store == STORE_PRIV) {
		/* anonymous or private VM is saved as if it were malloced */
		store = STORE_MEM; 
	}
	IODEBUG {
		THRprintf(GDKout, "#HEAPsave(%s.%s,storage=%d,free=" SZFMT ",size=" SZFMT ")\n", 
			nme, ext, h->storage, h->free, h->size);
	}
	return GDKsave(nme, ext, h->base, h->free, store);
}
@}
@- HEAPload
Delete any saved heap file. For memory mapped files, also try to remove any remaining X.priv
@{
@c
int
HEAPdelete(Heap *h, str o, str ext)
{
	char ext2[64];

	if (h->size <= 0) {
                return 0;
	}
	if (h->base) {
		if (h->copied == 0 && h->storage & STORE_MMAP) {
			/* truncate file, so OS does not try to flush dirty data in mmap to file that is deleted anyway */
			int ret, fd = GDKfdlocate(h->filename, "rb+", NULL);
			IODEBUG THRprintf(GDKout, "#HEAPdelete(%s) GDKfdlocate(\"rb+\") = %d\n", h->filename, fd);

			ret = ftruncate(fd, LL_CONSTANT(0));
			IODEBUG THRprintf(GDKout, "#HEAPdelete(%s) ftruncate(%d,0LL) = %d\n", h->filename, fd, ret);

			ret = close(fd);
			IODEBUG THRprintf(GDKout, "#HEAPdelete(%s) close(%d) = %d\n", h->filename, fd, ret);
		}
		HEAPfree(h);
	}
	if (h->copied) {
            return 0;
        }
	strcpy(ext2, ext);
	strcat(ext2, ".priv");
	return (GDKunlink(BATDIR, o, ext) == 0) | (GDKunlink(BATDIR, o, ext2) == 0)?0:-1;
}

int HEAPwarm(Heap *h) 
{
	int bogus_result = 0;
	if (h->storage & STORE_MMAP) {
		/* touch the heap sequentially */
                int *cur = (int*) h->base;
                int *lim = (int*) (h->base + h->free) - 4096;
		for(; cur<lim; cur+=4096) /* try to schedule 4 parallel memory accesses */
			bogus_result += cur[0] + cur[1024] + cur[2048] + cur[3072];
	}
	return bogus_result;
}


@}
@- HEAPvmsize
count all memory that takes up address space.
@{
@c
size_t
HEAPvmsize(Heap *h)
{
	if (h && h->free)
		return h->maxsize;
	return 0;
}

@}
@- HEAPmemsize
count all memory that takes up swap space. We conservatively count STORE_PRIV heaps as 
fully backed by swap space.
@{
@c
size_t
HEAPmemsize(Heap *h)
{
	if (h && h->free && h->storage != STORE_MMAP)
		return h->size;
	return 0;
}

@}

@+ Standard Heap Library
This library contains some routines which implement a @emph{ malloc} and @emph{
free} function on the Monet @emph{Heap} structure. They are useful when
implementing a new @emph{ variable-size} atomic data type, or for implementing
new search accelerators.  All functions start with the prefix @emph{HEAP_}. T

Due to non-careful design, the HEADER field was found to be 32/64-bit dependent. 
As we do not (yet) want to change the BAT image on disk, This is now fixed by 
switching on-the-fly between two representations. We ensure that the 64-bit memory 
representation is just as long as the 32-bits version (20 bytes) so the rest of 
the heap never needs to shift. The function HEAP\_checkformat converts at load 
time dynamically between the layout found on disk and the memory format.
Recognition of the header mode is done by looking at the first two ints: 
alignment must be 4 or 8, and head can never be 4 or eight. 

TODO: user HEADER64 for both 32 and 64 bits (requires BAT format change)
@{
@c
/* #define DEBUG */
/* #define TRACE */

#define HEAPVERSION	20030408

typedef struct heapheader {
	size_t head;		/* index to first free block            */
	int alignment;		/* alignment of objects on heap         */
	size_t firstblock;	/* first block in heap                  */
	int version;
	int (*sizefcn) (ptr);	/* ADT function to ask length           */
} HEADER32;

typedef struct {
	int version;
	int alignment;
	size_t head;
	size_t firstblock;
	int (*sizefcn) (ptr);
} HEADER64;

#if SIZEOF_SIZE_T==8
typedef HEADER64 HEADER;
typedef HEADER32 HEADER_OTHER;
#else
typedef HEADER32 HEADER;
typedef HEADER64 HEADER_OTHER;
#endif
typedef struct hfblock {
	size_t size;		/* Size of this block in freelist        */