import NSD 4.0.0, tests from Dorian Büttner, Patrik Lundin, requested by brad@

1 files changed, 2018 insertions, 0 deletions

diff --git a/usr.sbin/nsd/udb.c b/usr.sbin/nsd/udb.c
new file mode 100644
index 00000000000..6c0ffe7d0c0
--- /dev/null
+++ b/usr.sbin/nsd/udb.c
@@ -0,0 +1,2018 @@
+/* udb.c - u(micro) data base.
+ * By W.C.A. Wijngaards
+ * Copyright 2010, NLnet Labs.
+ * BSD, see LICENSE.
+ */
+#include "config.h"
+#include "udb.h"
+#include <string.h>
+#include <errno.h>
+#include <stdio.h>
+#include <unistd.h>
+#include <assert.h>
+#include "lookup3.h"
+#include "util.h"
+
+/* mmap and friends */
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <sys/mman.h>
+
+/* for systems without, portable definition, failed-1 and async is a flag */
+#ifndef MAP_FAILED
+#define MAP_FAILED ((void*)-1)
+#endif
+#ifndef MS_SYNC
+#define MS_SYNC 0
+#endif
+
+/** move and fixup xl segment */
+static void move_xl_segment(void* base, udb_base* udb, udb_void xl,
+	udb_void n, uint64_t sz, uint64_t startseg);
+/** attempt to compact the data and move free space to the end */
+static int udb_alloc_compact(void* base, udb_alloc* alloc);
+
+/** convert pointer to the data part to a pointer to the base of the chunk */
+static udb_void
+chunk_from_dataptr(udb_void data)
+{
+	/* we use that sizeof(udb_chunk_d) != sizeof(udb_xl_chunk_d) and
+	 * that xl_chunk_d is aligned on x**1024 boundaries. */
+	udb_void xl = data - sizeof(udb_xl_chunk_d);
+	if( (xl & (UDB_ALLOC_CHUNK_SIZE-1)) == 0)
+		return xl;
+	return data - sizeof(udb_chunk_d);
+}
+
+udb_void chunk_from_dataptr_ext(udb_void data) {
+	return chunk_from_dataptr(data);
+}
+
+#ifndef NDEBUG
+/** read last octet from a chunk */
+static uint8_t
+chunk_get_last(void* base, udb_void chunk, int exp)
+{
+	return *((uint8_t*)UDB_REL(base, chunk+(1<<exp)-1));
+}
+#endif
+
+/** write last octet of a chunk */
+static void
+chunk_set_last(void* base, udb_void chunk, int exp, uint8_t value)
+{
+	*((uint8_t*)UDB_REL(base, chunk+(1<<exp)-1)) = value;
+}
+
+/** create udb_base from a file descriptor (must be at start of file) */
+udb_base*
+udb_base_create_fd(const char* fname, int fd, udb_walk_relptr_func walkfunc,
+	void* arg)
+{
+	uint64_t m;
+	udb_glob_d g;
+	ssize_t r;
+	udb_base* udb = (udb_base*)xalloc_zero(sizeof(*udb));
+	if(!udb) {
+		log_msg(LOG_ERR, "out of memory");
+		close(fd);
+		return NULL;
+	}
+	udb->fname = strdup(fname);
+	if(!udb->fname) {
+		log_msg(LOG_ERR, "out of memory");
+		free(udb);
+		close(fd);
+		return NULL;
+	}
+	udb->walkfunc = walkfunc;
+	udb->walkarg = arg;
+	udb->fd = fd;
+	udb->ram_size = 1024;
+	udb->ram_mask = (int)udb->ram_size - 1;
+	udb->ram_hash = (udb_ptr**)xalloc_zero(sizeof(udb_ptr*)*udb->ram_size);
+	if(!udb->ram_hash) {
+		free(udb->fname);
+		free(udb);
+		log_msg(LOG_ERR, "out of memory");
+		close(fd);
+		return NULL;
+	}
+
+	/* read magic */
+	if((r=read(fd, &m, sizeof(m))) == -1) {
+		log_msg(LOG_ERR, "%s: %s", fname, strerror(errno));
+		goto fail;
+	} else if(r != (ssize_t)sizeof(m)) {
+		log_msg(LOG_ERR, "%s: file too short", fname);
+		goto fail;
+	}
+	/* TODO : what if bigendian and littleendian file, see magic */
+	if(m != UDB_MAGIC) {
+		log_msg(LOG_ERR, "%s: wrong type of file", fname);
+		goto fail;
+	}
+	/* read header */
+	if((r=read(fd, &g, sizeof(g))) == -1) {
+		log_msg(LOG_ERR, "%s: %s\n", fname, strerror(errno));
+		goto fail;
+	} else if(r != (ssize_t)sizeof(g)) {
+		log_msg(LOG_ERR, "%s: file too short", fname);
+		goto fail;
+	}
+	if(g.version != 0) {
+		log_msg(LOG_ERR, "%s: unknown file version %d", fname,
+			(int)g.version);
+		goto fail;
+	}
+	if(g.hsize < UDB_HEADER_SIZE) {
+		log_msg(LOG_ERR, "%s: header size too small %d", fname,
+			(int)g.hsize);
+		goto fail;
+	}
+	if(g.hsize > UDB_HEADER_SIZE) {
+		log_msg(LOG_WARNING, "%s: header size too large %d", fname,
+			(int)g.hsize);
+		log_msg(LOG_WARNING, "attempting to continue...");
+	}
+	if(g.clean_close != 0) {
+		log_msg(LOG_WARNING, "%s: not cleanly closed %d", fname,
+			(int)g.clean_close);
+		log_msg(LOG_WARNING, "attempting to continue...");
+	}
+	/* TODO check if too large (>4g on 32bit); mmap-usage would fail */
+	
+	/* mmap it */
+	if(g.fsize < UDB_HEADER_SIZE || g.fsize < g.hsize) {
+		log_msg(LOG_ERR, "%s: file too short", fname);
+		goto fail;
+	}
+	udb->base_size = (size_t)g.fsize;
+	/* note the size_t casts must be there for portability, on some
+	 * systems the layout of memory is otherwise broken. */
+	udb->base = mmap(NULL, (size_t)udb->base_size,
+		(int)PROT_READ|PROT_WRITE, (int)MAP_SHARED,
+		(int)udb->fd, (off_t)0);
+	if(udb->base == MAP_FAILED) {
+		udb->base = NULL;
+		log_msg(LOG_ERR, "mmap(size %u) error: %s",
+			(unsigned)udb->base_size, strerror(errno));
+	fail:
+		close(fd);
+		free(udb->fname);
+		free(udb->ram_hash);
+		free(udb);
+		return NULL;
+	}
+
+	/* init completion */
+	udb->glob_data = (udb_glob_d*)(udb->base+sizeof(uint64_t));
+	r = 0;
+	if(udb->glob_data->dirty_alloc != udb_dirty_clean)
+		r = 1;
+	udb->alloc = udb_alloc_create(udb, (udb_alloc_d*)(
+		(void*)udb->glob_data+sizeof(*udb->glob_data)));
+	if(!udb->alloc) {
+		log_msg(LOG_ERR, "out of memory");
+		udb_base_free(udb);
+		return NULL;
+	}
+	if(r) {
+		/* and compact now, or resume compacting */
+		udb_alloc_compact(udb, udb->alloc);
+		udb_base_sync(udb, 1);
+	}
+
+	return udb;
+}
+
+udb_base* udb_base_create_read(const char* fname, udb_walk_relptr_func walkfunc,
+	void* arg)
+{
+	int fd = open(fname, O_RDWR);
+	if(fd == -1) {
+		log_msg(LOG_ERR, "%s: %s", fname, strerror(errno));
+		return NULL;
+	}
+	return udb_base_create_fd(fname, fd, walkfunc, arg);
+}
+
+/** init new udb_global structure */
+static void udb_glob_init_new(udb_glob_d* g)
+{
+	memset(g, 0, sizeof(*g));
+	g->hsize = UDB_HEADER_SIZE;
+	g->fsize = UDB_HEADER_SIZE;
+}
+
+/** write data to file and check result */
+static int
+write_fdata(const char* fname, int fd, void* data, size_t len)
+{
+	ssize_t w;
+	if((w=write(fd, data, len)) == -1) {
+		log_msg(LOG_ERR, "%s: %s", fname, strerror(errno));
+		close(fd);
+		return 0;
+	} else if(w != (ssize_t)len) {
+		log_msg(LOG_ERR, "%s: short write (disk full?)", fname);
+		close(fd);
+		return 0;
+	}
+	return 1;
+}
+
+udb_base* udb_base_create_new(const char* fname, udb_walk_relptr_func walkfunc,
+	void* arg)
+{
+	uint64_t m;
+	udb_glob_d g;
+	udb_alloc_d a;
+	uint64_t endsize = UDB_HEADER_SIZE;
+	uint64_t endexp = 0;
+	int fd = open(fname, O_CREAT|O_RDWR, 0600);
+	if(fd == -1) {
+		log_msg(LOG_ERR, "%s: %s", fname, strerror(errno));
+		return NULL;
+	}
+	m = UDB_MAGIC;
+	udb_glob_init_new(&g);
+	udb_alloc_init_new(&a);
+
+	/* write new data to file (closes fd on error) */
+	if(!write_fdata(fname, fd, &m, sizeof(m)))
+		return NULL;
+	if(!write_fdata(fname, fd, &g, sizeof(g)))
+		return NULL;
+	if(!write_fdata(fname, fd, &a, sizeof(a)))
+		return NULL;
+	if(!write_fdata(fname, fd, &endsize, sizeof(endsize)))
+		return NULL;
+	if(!write_fdata(fname, fd, &endexp, sizeof(endexp)))
+		return NULL;
+	/* rewind to start */
+	if(lseek(fd, (off_t)0, SEEK_SET) == (off_t)-1) {
+		log_msg(LOG_ERR, "%s: lseek %s", fname, strerror(errno));
+		close(fd);
+		return NULL;
+	}
+	return udb_base_create_fd(fname, fd, walkfunc, arg);
+}
+
+/** shrink the udb base if it has unused space at the end */
+static void
+udb_base_shrink(udb_base* udb, uint64_t nsize)
+{
+	udb->glob_data->dirty_alloc = udb_dirty_fsize;
+	udb->glob_data->fsize = nsize;
+	/* sync, does not *seem* to be required on Linux, but it is
+	   certainly required on OpenBSD.  Otherwise changed data is lost. */
+	msync(udb->base, udb->base_size, MS_ASYNC);
+	if(ftruncate(udb->fd, (off_t)nsize) != 0) {
+		log_msg(LOG_ERR, "%s: ftruncate(%u) %s", udb->fname,
+			(unsigned)nsize, strerror(errno));
+	}
+	udb->glob_data->dirty_alloc = udb_dirty_clean;
+}
+
+void udb_base_close(udb_base* udb)
+{
+	if(!udb)
+		return;
+	if(udb->fd != -1 && udb->base && udb->alloc) {
+		uint64_t nsize = udb->alloc->disk->nextgrow;
+		if(nsize < udb->base_size)
+			udb_base_shrink(udb, nsize);
+	}
+	if(udb->fd != -1) {
+		close(udb->fd);
+		udb->fd = -1;
+	}
+	if(udb->base) {
+		if(munmap(udb->base, udb->base_size) == -1) {
+			log_msg(LOG_ERR, "munmap: %s", strerror(errno));
+		}
+		udb->base = NULL;
+	}
+}
+
+void udb_base_free(udb_base* udb)
+{
+	if(!udb)
+		return;
+	udb_base_close(udb);
+	udb_alloc_delete(udb->alloc);
+	free(udb->ram_hash);
+	free(udb->fname);
+	free(udb);
+}
+
+void udb_base_free_keep_mmap(udb_base* udb)
+{
+	if(!udb) return;
+	if(udb->fd != -1) {
+		close(udb->fd);
+		udb->fd = -1;
+	}
+	udb->base = NULL;
+	udb_alloc_delete(udb->alloc);
+	free(udb->ram_hash);
+	free(udb->fname);
+	free(udb);
+}
+
+void udb_base_sync(udb_base* udb, int wait)
+{
+	if(msync(udb->base, udb->base_size, wait?MS_SYNC:MS_ASYNC) != 0) {
+		log_msg(LOG_ERR, "msync(%s) error %s",
+			udb->fname, strerror(errno));
+	}
+}
+
+/** hash a chunk pointer */
+static uint32_t
+chunk_hash_ptr(udb_void p)
+{
+	/* put p into an array of uint32 */
+	uint32_t h[sizeof(p)/sizeof(uint32_t)];
+	memcpy(&h, &p, sizeof(h));
+	return hashword(h, sizeof(p)/sizeof(uint32_t), 0x8763);
+}
+
+/** check that the given pointer is on the bucket for the given offset */
+int udb_ptr_is_on_bucket(udb_base* udb, udb_ptr* ptr, udb_void to)
+{
+	uint32_t i = chunk_hash_ptr(to) & udb->ram_mask;
+	udb_ptr* p;
+	assert((size_t)i < udb->ram_size);
+	for(p = udb->ram_hash[i]; p; p=p->next) {
+		if(p == ptr)
+			return 1;
+	}
+	return 0;
+}
+
+/** grow the ram array */
+static void
+grow_ram_hash(udb_base* udb, udb_ptr** newhash)
+{
+	size_t i;
+	size_t osize= udb->ram_size;
+	udb_ptr* p, *np;
+	udb_ptr** oldhash = udb->ram_hash;
+	udb->ram_size *= 2;
+	udb->ram_mask <<= 1;
+	udb->ram_mask |= 1;
+	udb->ram_hash = newhash;
+	/* have to link in every element in the old list into the new list*/
+	for(i=0; i<osize; i++) {
+		p = oldhash[i];
+		while(p) {
+			np = p->next;
+			/* link into newhash */
+			p->prev=NULL;
+			p->next=newhash[chunk_hash_ptr(p->data)&udb->ram_mask];
+			if(p->next) p->next->prev = p;
+			/* go to next element of oldhash */
+			p = np;
+		}
+	}
+	free(oldhash);
+}
+
+void udb_base_link_ptr(udb_base* udb, udb_ptr* ptr)
+{
+	uint32_t i = chunk_hash_ptr(ptr->data) & udb->ram_mask;
+	assert((size_t)i < udb->ram_size);
+#ifdef UDB_CHECK
+	assert(udb_valid_dataptr(udb, ptr->data)); /* must be to whole chunk*/
+#endif
+	udb->ram_num++;
+	if(udb->ram_num == udb->ram_size && udb->ram_size<(size_t)0xefffffff) {
+		/* grow the array, if allocation succeeds */
+		udb_ptr** newram = (udb_ptr**)xalloc_zero(sizeof(udb_ptr*)*
+			udb->ram_size*2);
+		if(newram) {
+			grow_ram_hash(udb, newram);
+		}
+	}
+	ptr->prev = NULL;
+	ptr->next = udb->ram_hash[i];
+	udb->ram_hash[i] = ptr;
+	if(ptr->next)
+		ptr->next->prev = ptr;
+}
+
+void udb_base_unlink_ptr(udb_base* udb, udb_ptr* ptr)
+{
+	assert(ptr->data);
+#ifdef UDB_CHECK
+	assert(udb_valid_dataptr(udb, ptr->data)); /* ptr must be inited */
+	assert(udb_ptr_is_on_bucket(udb, ptr, ptr->data));
+#endif
+	udb->ram_num--;
+	if(ptr->next)
+		ptr->next->prev = ptr->prev;
+	if(ptr->prev)
+		ptr->prev->next = ptr->next;
+	else	{
+		uint32_t i = chunk_hash_ptr(ptr->data) & udb->ram_mask;
+		assert((size_t)i < udb->ram_size);
+		udb->ram_hash[i] = ptr->next;
+	}
+}
+
+/** change a set of ram ptrs to a new value */
+static void
+udb_base_ram_ptr_edit(udb_base* udb, udb_void old, udb_void newd)
+{
+	uint32_t io = chunk_hash_ptr(old) & udb->ram_mask;
+	udb_ptr* p, *np;
+	/* edit them and move them into the new position */
+	p = udb->ram_hash[io];
+	while(p) {
+		np = p->next;
+		if(p->data == old) {
+			udb_base_unlink_ptr(udb, p);
+			p->data = newd;
+			udb_base_link_ptr(udb, p);
+		}
+		p = np;
+	}
+}
+
+udb_rel_ptr* udb_base_get_userdata(udb_base* udb)
+{
+	return &udb->glob_data->user_global;
+}
+
+void udb_base_set_userdata(udb_base* udb, udb_void user)
+{
+#ifdef UDB_CHECK
+	if(user) { assert(udb_valid_dataptr(udb, user)); }
+#endif
+	udb_rel_ptr_set(udb->base, &udb->glob_data->user_global, user);
+}
+
+void udb_base_set_userflags(udb_base* udb, uint8_t v)
+{
+	udb->glob_data->userflags = v;
+}
+
+uint8_t udb_base_get_userflags(udb_base* udb)
+{
+	return udb->glob_data->userflags;
+}
+
+/** re-mmap the udb to specified size */
+static void*
+udb_base_remap(udb_base* udb, udb_alloc* alloc, uint64_t nsize)
+{
+	void* nb;
+	/* for use with valgrind, do not use mremap, but the other version */
+#ifdef MREMAP_MAYMOVE
+	nb = mremap(udb->base, udb->base_size, nsize, MREMAP_MAYMOVE);
+	if(nb == MAP_FAILED) {
+		log_msg(LOG_ERR, "mremap(%s, size %u) error %s",
+			udb->fname, (unsigned)nsize, strerror(errno));
+		return 0;
+	}
+#else /* !HAVE MREMAP */
+	/* use munmap-mmap to simulate mremap */
+	if(munmap(udb->base, udb->base_size) != 0) {
+		log_msg(LOG_ERR, "munmap(%s) error %s",
+			udb->fname, strerror(errno));
+	}
+	/* provide hint for new location */
+	/* note the size_t casts must be there for portability, on some
+	 * systems the layout of memory is otherwise broken. */
+	nb = mmap(udb->base, (size_t)nsize, (int)PROT_READ|PROT_WRITE,
+		(int)MAP_SHARED, (int)udb->fd, (off_t)0);
+	/* retry the mmap without basept in case of ENOMEM (FreeBSD8),
+	 * the kernel can then try to mmap it at a different location
+	 * where more memory is available */
+	if(nb == MAP_FAILED && errno == ENOMEM) {
+		nb = mmap(NULL, (size_t)nsize, (int)PROT_READ|PROT_WRITE,
+			(int)MAP_SHARED, (int)udb->fd, (off_t)0);
+	}
+	if(nb == MAP_FAILED) {
+		log_msg(LOG_ERR, "mmap(%s, size %u) error %s",
+			udb->fname, (unsigned)nsize, strerror(errno));
+		udb->base = NULL;
+		return 0;
+	}
+#endif /* HAVE MREMAP */
+	if(nb != udb->base) {
+		/* fix up realpointers in udb and alloc */
+		/* but mremap may have been nice and not move the base */
+		udb->base = nb;
+		udb->glob_data = (udb_glob_d*)(nb+sizeof(uint64_t));
+		/* use passed alloc pointer because the udb->alloc may not
+		 * be initialized yet */
+		alloc->disk = (udb_alloc_d*)((void*)udb->glob_data
+			+sizeof(*udb->glob_data));
+	}
+	udb->base_size = nsize;
+	return nb;
+}
+
+void
+udb_base_remap_process(udb_base* udb)
+{
+	/* assume that fsize is still accessible */
+	udb_base_remap(udb, udb->alloc, udb->glob_data->fsize);
+}
+
+/** grow file to specified size and re-mmap, return new base */
+static void*
+udb_base_grow_and_remap(udb_base* udb, uint64_t nsize)
+{
+	/* grow file by writing a single zero at that spot, the
+	 * rest is filled in with zeroes. */
+	uint8_t z = 0;
+	ssize_t w;
+
+	assert(nsize > 0);
+	udb->glob_data->dirty_alloc = udb_dirty_fsize;
+#ifdef HAVE_PWRITE
+	if((w=pwrite(udb->fd, &z, sizeof(z), (off_t)(nsize-1))) == -1) {
+#else
+	if(lseek(udb->fd, (off_t)(nsize-1), SEEK_SET) == -1) {
+		log_msg(LOG_ERR, "fseek %s: %s", udb->fname, strerror(errno));
+		return 0;
+	}
+	if((w=write(udb->fd, &z, sizeof(z))) == -1) {
+#endif
+		log_msg(LOG_ERR, "grow(%s, size %u) error %s",
+			udb->fname, (unsigned)nsize, strerror(errno));
+		return 0;
+	} else if(w != (ssize_t)sizeof(z)) {
+		log_msg(LOG_ERR, "grow(%s, size %u) failed (disk full?)",
+			udb->fname, (unsigned)nsize);
+		return 0;
+	}
+	udb->glob_data->fsize = nsize;
+	udb->glob_data->dirty_alloc = udb_dirty_clean;
+	return udb_base_remap(udb, udb->alloc, nsize);
+}
+
+int udb_exp_size(uint64_t a)
+{
+	/* find enclosing value such that 2**x >= a */
+	int x = 0;
+	uint64_t i = a;
+	assert(a != 0);
+
+	i --;
+	/* could optimise this with uint8* access, depends on endianness */
+	/* first whole bytes */
+	while( (i&(~(uint64_t)0xff)) ) {
+		i >>= 8;
+		x += 8;
+	}
+	/* now details */
+	while(i) {
+		i >>= 1;
+		x ++;
+	}
+	assert( ((uint64_t)1<<x) >= a);
+	assert( x==0 || ((uint64_t)1<<(x-1)) < a);
+	return x;
+}
+
+int udb_exp_offset(uint64_t o)
+{
+	/* this means measuring the number of 0 bits on the right */
+	/* so, if exp zero bits then (o&(2**x-1))==0 */
+	int x = 0;
+	uint64_t i = o;
+	assert(o != 0);
+	/* first whole bytes */
+	while( (i&(uint64_t)0xff) == 0) {
+		i >>= 8;
+		x += 8;
+	}
+	/* now details */
+	while( (i&(uint64_t)0x1) == 0) {
+		i >>= 1;
+		x ++;
+	}
+	assert( o % ((uint64_t)1<<x) == 0);
+	assert( o % ((uint64_t)1<<(x+1)) != 0);
+	return x;
+}
+
+void udb_alloc_init_new(udb_alloc_d* a)
+{
+	assert(UDB_HEADER_SIZE % UDB_ALLOC_CHUNK_MINSIZE == 0);
+	memset(a, 0, sizeof(*a));
+	/* set new allocations after header, as if allocated in a sequence
+	 * of minsize allocations */
+	a->nextgrow = UDB_HEADER_SIZE;
+}
+
+/** fsck the file size, false if failed and file is useless */
+static int
+fsck_fsize(udb_base* udb, udb_alloc* alloc)
+{
+	off_t realsize;
+	log_msg(LOG_WARNING, "udb-fsck %s: file size wrong", udb->fname);
+	realsize = lseek(udb->fd, (off_t)0, SEEK_END);
+	if(realsize == (off_t)-1) {
+		log_msg(LOG_ERR, "lseek(%s): %s", udb->fname, strerror(errno));
+		return 0;
+	}
+	udb->glob_data->fsize = (uint64_t)realsize;
+	if(!udb_base_remap(udb, alloc, (uint64_t)realsize))
+		return 0;
+	udb->glob_data->dirty_alloc = udb_dirty_clean;
+	log_msg(LOG_WARNING, "udb-fsck %s: file size fixed (sync)", udb->fname);
+	udb_base_sync(udb, 1);
+	return 1;
+}
+
+/** regenerate freelist add a new free chunk, return next todo */
+static udb_void
+regen_free(void* base, udb_void c, int exp, udb_alloc_d* regen)
+{
+	udb_free_chunk_d* cp = UDB_FREE_CHUNK(c);
+	uint64_t esz = (uint64_t)1<<exp;
+	if(exp < UDB_ALLOC_CHUNK_MINEXP || exp > UDB_ALLOC_CHUNKS_MAX) {
+		return 0;
+	}
+	cp->type = udb_chunk_type_free;
+	cp->flags = 0;
+	chunk_set_last(base, c, exp, (uint8_t)exp);
+	cp->prev = 0;
+	cp->next = regen->free[exp-UDB_ALLOC_CHUNK_MINEXP];
+	if(cp->next)
+		UDB_FREE_CHUNK(cp->next)->prev = c;
+	regen->stat_free += esz;
+	return c + esz;
+}
+
+/** regenerate xl chunk, return next todo */
+static udb_void
+regen_xl(void* base, udb_void c, udb_alloc_d* regen)
+{
+	udb_xl_chunk_d* cp = UDB_XL_CHUNK(c);
+	uint64_t xlsz = cp->size;
+	if( (xlsz&(UDB_ALLOC_CHUNK_SIZE-1)) != 0) {
+		return 0;
+	}
+	if( (c&(UDB_ALLOC_CHUNK_SIZE-1)) != 0) {
+		return 0;
+	}
+	/* fixup end-size and end-expmarker */
+	regen->stat_alloc += xlsz;
+	return c + xlsz;
+}
+
+/** regenerate data chunk, return next todo */
+static udb_void
+regen_data(void* base, udb_void c, int exp, udb_alloc_d* regen)
+{
+	uint64_t esz = (uint64_t)1<<exp;
+	if(exp < UDB_ALLOC_CHUNK_MINEXP || exp > UDB_ALLOC_CHUNKS_MAX) {
+		return 0;
+	}
+	chunk_set_last(base, c, exp, (uint8_t)exp);
+	regen->stat_alloc += esz;
+	return c + esz;
+}
+
+/** regenerate a relptr structure inside a data segment */
+static void
+regen_relptr_func(void* base, udb_rel_ptr* rp, void* arg)
+{
+	udb_void* a = (udb_void*)arg;
+	/* ignore 0 pointers */
+	if(!rp->data)
+		return;
+
+	/* edit relptrs that point to oldmoved to point to newmoved. */
+	if(rp->data == a[0])
+		rp->data = a[1];
+
+	/* regenerate relptr lists, add this item to the relptr list for
+	 * the data that it points to */
+	udb_rel_ptr_link(base, rp, rp->data);
+}
+
+/** regenerate the relptrs store in this data segment */
+static void
+regen_its_ptrs(void* base, udb_base* udb, udb_chunk_d* atp,
+	void* data, uint64_t dsz, udb_void rb_old, udb_void rb_new)
+{
+	udb_void arg[2];
+	arg[0] = rb_old; arg[1] = rb_new;
+	/* walk through the structs here and put them on their respective
+	 * relptr lists */
+	(*udb->walkfunc)(base, udb->walkarg, atp->type, data, dsz, 
+		&regen_relptr_func, arg);
+
+}
+
+/** regenerate relptrlists in the file */
+static void
+regen_ptrlist(void* base, udb_base* udb, udb_alloc* alloc,
+	udb_void rb_old, udb_void rb_new)
+{
+	udb_void at = alloc->udb->glob_data->hsize;
+	/* clear all ptrlist start pointers in the file. */
+	while(at < alloc->disk->nextgrow) {
+		int exp = (int)UDB_CHUNK(at)->exp;
+		udb_chunk_type tp = (udb_chunk_type)UDB_CHUNK(at)->type;
+		if(exp == UDB_EXP_XL) {
+			UDB_XL_CHUNK(at)->ptrlist = 0;
+			at += UDB_XL_CHUNK(at)->size;
+		} else if(tp == udb_chunk_type_free) {
+			at += (uint64_t)1<<exp;
+		} else { /* data chunk */
+			UDB_CHUNK(at)->ptrlist = 0;
+			at += (uint64_t)1<<exp;
+		}
+	}
+	/* walk through all relptr structs and put on the right list. */
+	at = alloc->udb->glob_data->hsize;
+	while(at < alloc->disk->nextgrow) {
+		udb_chunk_d* atp = UDB_CHUNK(at);
+		int exp = (int)atp->exp;
+		udb_chunk_type tp = (udb_chunk_type)atp->type;
+		uint64_t sz = ((exp == UDB_EXP_XL)?UDB_XL_CHUNK(at)->size:
+			(uint64_t)1<<exp);
+		if(exp == UDB_EXP_XL) {
+			assert(at != rb_old); /* should have been freed */
+			regen_its_ptrs(base, udb, atp,
+				((void*)atp)+sizeof(udb_xl_chunk_d),
+				sz-sizeof(udb_xl_chunk_d) - sizeof(uint64_t)*2,
+				rb_old, rb_new);
+			at += sz;
+		} else if(tp == udb_chunk_type_free) {
+			at += sz;
+		} else { /* data chunk */
+			assert(at != rb_old); /* should have been freed */
+			regen_its_ptrs(base, udb, atp,
+				((void*)atp)+sizeof(udb_chunk_d),
+				sz-sizeof(udb_chunk_d)-1, rb_old, rb_new);
+			at += sz;
+		}
+	}
+}
+
+
+/** mark free elements from ex XL chunk space and later fixups pick that up */
+static void
+rb_mark_free_segs(void* base, udb_void s, uint64_t m)
+{
+	udb_void q = s + m - UDB_ALLOC_CHUNK_SIZE;
+	/* because of header and alignment we know s >= UDB_ALLOC_CHUNK_SIZE*/
+	assert(s >= UDB_ALLOC_CHUNK_SIZE);
+	while(q >= s) {
+		UDB_CHUNK(q)->exp = UDB_ALLOC_CHUNKS_MAX;
+		UDB_CHUNK(q)->type = udb_chunk_type_free;
+		q -= UDB_ALLOC_CHUNK_SIZE;
+	}
+}
+
+
+/** fsck rollback or rollforward XL move results */
+static int
+fsck_rb_xl(void* base, udb_base* udb, udb_void rb_old, udb_void rb_new,
+	uint64_t rb_size, uint64_t rb_seg)
+{
+
+	if(rb_old <= rb_new)
+		return 0; /* XL move one way */
+	if( (rb_size&(UDB_ALLOC_CHUNK_SIZE-1)) != 0)
+		return 0; /* not aligned */
+	if( (rb_old&(UDB_ALLOC_CHUNK_SIZE-1)) != 0)
+		return 0; /* not aligned */
+	if( (rb_new&(UDB_ALLOC_CHUNK_SIZE-1)) != 0)
+		return 0; /* not aligned */
+	if(rb_new + rb_size <= rb_old) {
+		/* not overlapping: resume copy */
+		memcpy(UDB_CHUNK(rb_new), UDB_CHUNK(rb_old), rb_size);
+		/* and free up old piece(s) */
+		rb_mark_free_segs(base, rb_old, rb_size);
+	} else {
+		/* overlapping, see what segment we stopped at
+		 * and continue there. */
+		move_xl_segment(base, udb, rb_old, rb_new, rb_size, rb_seg);
+		/* free up old piece(s); from the end of the moved segment,
+		 * until the end of the old segment */
+		rb_mark_free_segs(base, rb_new+rb_size, (rb_old+rb_size)-
+			(rb_new+rb_size));
+	}
+	/* do not call fix_ptrs, regenptrs does the job */
+	return 1;
+}
+
+/** fsck rollback or rollforward move results */
+static int
+fsck_rb(void* base, udb_void rb_old, udb_void rb_new, uint64_t rb_size,
+	udb_void* make_free)
+{
+	if( (rb_size&(rb_size-1)) != 0)
+		return 0; /* not powerof2 */
+	if( (rb_old&(rb_size-1)) != 0)
+		return 0; /* not aligned */
+	if( (rb_new&(rb_size-1)) != 0)
+		return 0; /* not aligned */
+	/* resume copy */
+	memcpy(UDB_CHUNK(rb_new), UDB_CHUNK(rb_old), rb_size);
+	/* do not call fix_ptrs, regenptrs does the job */
+	/* make sure udb_old is freed */
+	*make_free = rb_old;
+	return 1;
+}
+
+/** fsck the file and salvage, false if failed and file is useless */
+static int
+fsck_file(udb_base* udb, udb_alloc* alloc, int moved)
+{
+	void* base = udb->base;
+	udb_alloc_d regen;
+	udb_void at = udb->glob_data->hsize;
+	udb_void rb_old = udb->glob_data->rb_old;
+	udb_void rb_new = udb->glob_data->rb_new;
+	udb_void rb_seg = udb->glob_data->rb_seg;
+	udb_void make_free = 0;
+	uint64_t rb_size = udb->glob_data->rb_size;
+	log_msg(LOG_WARNING, "udb-fsck %s: salvaging", udb->fname);
+	/* walk through the file, use the exp values to see what can be
+	 * salvaged */
+	if(moved && rb_old && rb_new && rb_size) {
+		if(rb_old+rb_size <= alloc->disk->nextgrow
+			&& rb_new+rb_size <= alloc->disk->nextgrow) {
+			/* we can use the move information to fix up the
+			 * duplicate element (or partially moved element) */
+			if(rb_size > 1024*1024) {
+				/* XL chunk */
+				if(!fsck_rb_xl(base, udb, rb_old, rb_new,
+					rb_size, rb_seg))
+					return 0;
+			} else {
+				if(!fsck_rb(base, rb_old, rb_new, rb_size,
+					&make_free))
+					return 0;
+			}
+		}
+	}
+	
+	/* rebuild freelists */
+	/* recalculate stats in alloc (except 'stat_data') */
+	/* possibly new end 'nextgrow' value */
+	memset(&regen, 0, sizeof(regen));
+	regen.nextgrow = alloc->disk->nextgrow;
+	while(at < regen.nextgrow) {
+		/* figure out this chunk */
+		int exp = (int)UDB_CHUNK(at)->exp;
+		udb_chunk_type tp = (udb_chunk_type)UDB_CHUNK(at)->type;
+		/* consistency check possible here with end-exp */
+		if(tp == udb_chunk_type_free || at == make_free) {
+			at = regen_free(base, at, exp, &regen);
+			if(!at) return 0;
+		} else if(exp == UDB_EXP_XL) {
+			/* allocated data of XL size */
+			at = regen_xl(base, at, &regen);
+			if(!at) return 0;
+		} else if(exp >= UDB_ALLOC_CHUNK_MINEXP
+			&& exp <= UDB_ALLOC_CHUNKS_MAX) {
+			/* allocated data */
+			at = regen_data(base, at, exp, &regen);
+			if(!at) return 0;
+		} else {
+			/* garbage; this must be EOF then */
+			regen.nextgrow = at;
+			break;
+		}
+	}
+	*alloc->disk = regen;
+
+	/* rebuild relptr lists */
+	regen_ptrlist(base, udb, alloc, rb_old, rb_new);
+
+	log_msg(LOG_WARNING, "udb-fsck %s: salvaged successfully (sync)",
+		udb->fname);
+	udb->glob_data->rb_old = 0;
+	udb->glob_data->rb_new = 0;
+	udb->glob_data->rb_size = 0;
+	udb->glob_data->dirty_alloc = udb_dirty_clean;
+	udb_base_sync(udb, 1);
+	return 1;
+}
+
+
+udb_alloc* udb_alloc_create(udb_base* udb, udb_alloc_d* disk)
+{
+	udb_alloc* alloc = (udb_alloc*)xalloc_zero(sizeof(*alloc));
+	if(!alloc)
+		return NULL;
+	alloc->udb = udb;
+	alloc->disk = disk;
+	/* see if committed but uncompleted actions need to be done */
+	/* preserves the alloc state */
+	if(udb->glob_data->dirty_alloc != udb_dirty_clean) {
+		if(udb->glob_data->dirty_alloc == udb_dirty_fsize) {
+			if(fsck_fsize(udb, alloc))
+				return alloc;
+		} else if(udb->glob_data->dirty_alloc == udb_dirty_fl) {
+			if(fsck_file(udb, alloc, 0))
+				return alloc;
+		} else if(udb->glob_data->dirty_alloc == udb_dirty_compact) {
+			if(fsck_file(udb, alloc, 1))
+				return alloc;
+		}
+		log_msg(LOG_ERR, "error: file allocation dirty (%d)",
+			(int)udb->glob_data->dirty_alloc);
+		free(alloc);
+		return NULL;
+	}
+	return alloc;
+}
+
+void udb_alloc_delete(udb_alloc* alloc)
+{
+	if(!alloc) return;
+	free(alloc);
+}
+
+/** unlink this element from its freelist */
+static void
+udb_alloc_unlink_fl(void* base, udb_alloc* alloc, udb_void chunk, int exp)
+{
+	udb_free_chunk_d* fp = UDB_FREE_CHUNK(chunk);
+	assert(chunk);
+	/* chunk is a free chunk */
+	assert(fp->exp == (uint8_t)exp);
+	assert(fp->type == udb_chunk_type_free);
+	assert(chunk_get_last(base, chunk, exp) == (uint8_t)exp);
+	/* and thus freelist not empty */
+	assert(alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP]);
+	/* unlink */
+	if(fp->prev)
+		UDB_FREE_CHUNK(fp->prev)->next = fp->next;
+	else	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = fp->next;
+	if(fp->next)
+		UDB_FREE_CHUNK(fp->next)->prev = fp->prev;
+}
+
+/** pop first element off freelist, list may not be empty */
+static udb_void
+udb_alloc_pop_fl(void* base, udb_alloc* alloc, int exp)
+{
+	udb_void f = alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP];
+	udb_free_chunk_d* fp = UDB_FREE_CHUNK(f);
+	assert(f);
+	assert(fp->exp == (uint8_t)exp);
+	assert(fp->type == udb_chunk_type_free);
+	assert(chunk_get_last(base, f, exp) == (uint8_t)exp);
+	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = fp->next;
+	if(fp->next) {
+		UDB_FREE_CHUNK(fp->next)->prev = 0;
+	}
+	return f;
+}
+
+/** push new element onto freelist */
+static void
+udb_alloc_push_fl(void* base, udb_alloc* alloc, udb_void f, int exp)
+{
+	udb_free_chunk_d* fp = UDB_FREE_CHUNK(f);
+	assert(f);
+	fp->exp = (uint8_t)exp;
+	fp->type = udb_chunk_type_free;
+	fp->flags = 0;
+	fp->prev = 0;
+	fp->next = alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP];
+	if(fp->next)
+		UDB_FREE_CHUNK(fp->next)->prev = f;
+	chunk_set_last(base, f, exp, (uint8_t)exp);
+	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = f;
+}
+
+/** push new element onto freelist - do not initialize the elt */
+static void
+udb_alloc_push_fl_noinit(void* base, udb_alloc* alloc, udb_void f, int exp)
+{
+	udb_free_chunk_d* fp = UDB_FREE_CHUNK(f);
+	assert(f);
+	assert(fp->exp == (uint8_t)exp);
+	assert(fp->type == udb_chunk_type_free);
+	assert(chunk_get_last(base, f, exp) == (uint8_t)exp);
+	fp->prev = 0;
+	fp->next = alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP];
+	if(fp->next)
+		UDB_FREE_CHUNK(fp->next)->prev = f;
+	alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP] = f;
+}
+
+/** add free chunks at end until specified alignment occurs */
+static void
+grow_align(void* base, udb_alloc* alloc, uint64_t esz)
+{
+	while( (alloc->disk->nextgrow & (esz-1)) != 0) {
+		/* the nextgrow is not a whole multiple of esz. */
+		/* grow a free chunk of max allowed size */
+		int fexp = udb_exp_offset(alloc->disk->nextgrow);
+		uint64_t fsz = (uint64_t)1<<fexp;
+		udb_void f = alloc->disk->nextgrow;
+		udb_void fn = alloc->disk->nextgrow+fsz;
+		assert(fn <= alloc->udb->base_size);
+		alloc->disk->stat_free += fsz;
+		udb_alloc_push_fl(base, alloc, f, fexp);
+		/* now increase nextgrow to commit that free chunk */
+		alloc->disk->nextgrow = fn;
+	}
+}
+
+/** append chunks at end of memory space to get size exp, return dataptr */
+static udb_void
+grow_chunks(void* base, udb_alloc* alloc, size_t sz, int exp)
+{
+	uint64_t esz = (uint64_t)1<<exp;
+	udb_void ret;
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_fl;
+	grow_align(base, alloc, esz);
+	/* free chunks are grown, grow the one we want to use */
+	ret = alloc->disk->nextgrow;
+	/* take a new alloced chunk into use */
+	UDB_CHUNK(ret)->exp = (uint8_t)exp;
+	UDB_CHUNK(ret)->flags = 0;
+	UDB_CHUNK(ret)->ptrlist = 0;
+	UDB_CHUNK(ret)->type = udb_chunk_type_data;
+	/* store last octet */
+	chunk_set_last(base, ret, exp, (uint8_t)exp);
+	/* update stats */
+	alloc->disk->stat_alloc += esz;
+	alloc->disk->stat_data += sz;
+	/* now increase nextgrow to commit this newly allocated chunk */
+	alloc->disk->nextgrow += esz;
+	assert(alloc->disk->nextgrow <= alloc->udb->base_size);
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+	return ret + sizeof(udb_chunk_d); /* ptr to data */
+}
+
+/** calculate how much space is necessary to grow for this exp */
+static uint64_t
+grow_end_calc(udb_alloc* alloc, int exp)
+{
+	uint64_t sz = (uint64_t)1<<exp;
+	uint64_t ng = alloc->disk->nextgrow;
+	uint64_t res;
+	/* if nextgrow is 2**expness, no extra growth needed, only size */
+	if( (ng & (sz-1)) == 0) {
+		/* sz-1 is like 0xfff, and checks if ng is whole 2**exp */
+		return ng+sz; /* must grow exactly 2**exp */
+	}
+	/* grow until 2**expness and then we need 2**exp as well */
+	/* so, round ng down to whole sz (basically  ng-ng%sz, or ng/sz*sz)
+	 * and then add the sz twice (go up to whole sz, and to allocate) */
+	res = (ng & ~(sz-1)) + 2*sz;
+	return res;
+}
+
+/** see if we need to grow more than specified to enable sustained growth */
+static uint64_t
+grow_extra_check(udb_alloc* alloc, uint64_t ge)
+{
+	const uint64_t mb = 1024*1024;
+	uint64_t bsz = alloc->udb->base_size;
+	if(bsz <= mb) {
+		/* below 1 Mb, double sizes for exponential growth */
+		/* takes about 15 times to grow to 1Mb */
+		if(ge < bsz*2)
+			return bsz*2;
+	} else {
+		uint64_t gnow = ge - bsz;
+		/* above 1Mb, grow at least 1 Mb, or 12.5% of current size,
+		 * in whole megabytes rounded up. */
+		uint64_t want = ((bsz / 8) & ~(mb-1)) + mb;
+		if(gnow < want)
+			return bsz + want;
+	}
+	return ge;
+}
+
+/** see if free space is enogh to warrant shrink (while file is open) */
+static int
+enough_free(udb_alloc* alloc)
+{
+	if(alloc->udb->base_size <= 2*1024*1024) {
+		/* below 1 Mb, grown by double size, (so up to 2 mb),
+		 * do not shrink unless we can 1/3 in size */
+		if(((size_t)alloc->disk->nextgrow)*3 <= alloc->udb->base_size)
+			return 1;
+	} else {
+		/* grown 12.5%, shrink 25% if possible, at least one mb */
+		/* between 1mb and 4mb size, it shrinks by 1mb if possible */
+		uint64_t space = alloc->udb->base_size - alloc->disk->nextgrow;
+		if(space >= 1024*1024 && (space*4 >= alloc->udb->base_size
+			|| alloc->udb->base_size < 4*1024*1024))
+			return 1;
+	}
+	return 0;
+}
+
+/** grow space for a chunk of 2**exp and return dataptr */
+static udb_void
+udb_alloc_grow_space(void* base, udb_alloc* alloc, size_t sz, int exp)
+{
+	/* commit the grow action
+	 * - the file grow only changes filesize, but not the nextgrow.
+	 * - taking space after nextgrow into use (as free space),
+	 *   is like free-ing a chunk (one at a time).
+	 * - and the last chunk taken into use is like alloc.
+	 */
+	/* predict how much free space is needed for this */
+	uint64_t grow_end = grow_end_calc(alloc, exp);
+	assert(alloc->udb->base_size >= alloc->disk->nextgrow);
+	if(grow_end <= alloc->udb->base_size) {
+		/* we can do this with the available space */
+		return grow_chunks(base, alloc, sz, exp);
+	}
+	/* we have to grow the file, re-mmap */
+	/* see if we need to grow a little more, to avoid endless grow
+	 * efforts on adding data */
+	grow_end = grow_extra_check(alloc, grow_end);
+	if(!(base=udb_base_grow_and_remap(alloc->udb, grow_end))) {
+		return 0; /* mmap or write failed (disk or mem full) */
+	}
+	/* we have enough space now */
+	assert(grow_end <= alloc->udb->base_size);
+	assert(alloc->udb->glob_data->fsize == alloc->udb->base_size);
+	return grow_chunks(base, alloc, sz, exp);
+}
+
+/** take XL allocation into use at end of file, return dataptr */
+static udb_void
+grow_xl(void* base, udb_alloc* alloc, uint64_t xlsz, uint64_t sz)
+{
+	udb_void ret;
+	udb_xl_chunk_d* p;
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_fl;
+
+	/* align growth to whole mbs */
+	grow_align(base, alloc, UDB_ALLOC_CHUNK_SIZE);
+
+	/* grow XL segment */
+	ret = alloc->disk->nextgrow;
+	p = UDB_XL_CHUNK(ret);
+	p->exp = UDB_EXP_XL;
+	p->size = xlsz;
+	p->flags = 0;
+	p->ptrlist = 0;
+	p->type = udb_chunk_type_data;
+
+	/* also put size and marker at end for compaction */
+	*((uint64_t*)(UDB_REL(base, ret+xlsz-sizeof(uint64_t)*2))) = xlsz;
+	*((uint8_t*)(UDB_REL(base, ret+xlsz-1))) = UDB_EXP_XL;
+
+	/* stats */
+	alloc->disk->stat_data += sz;
+	alloc->disk->stat_alloc += xlsz;
+	/* now increase the nextgrow to commit this xl chunk */
+	alloc->disk->nextgrow += xlsz;
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+	return ret + sizeof(udb_xl_chunk_d); /* data ptr */
+}
+
+/** make space for XL allocation */
+static udb_void
+udb_alloc_xl_space(void* base, udb_alloc* alloc, size_t sz)
+{
+	/* allocate whole mbs of space, at end of space */
+	uint64_t asz = sz + sizeof(udb_xl_chunk_d) + sizeof(uint64_t)*2;
+	uint64_t need=(asz+UDB_ALLOC_CHUNK_SIZE-1)&(~(UDB_ALLOC_CHUNK_SIZE-1));
+	uint64_t grow_end = grow_end_calc(alloc, UDB_ALLOC_CHUNKS_MAX) + need;
+	assert(need >= asz);
+	if(grow_end <= alloc->udb->base_size) {
+		/* can do this in available space */
+		return grow_xl(base, alloc, need, sz);
+	}
+	/* have to grow file and re-mmap */
+	grow_end = grow_extra_check(alloc, grow_end);
+	if(!(base=udb_base_grow_and_remap(alloc->udb, grow_end))) {
+		return 0; /* mmap or write failed (disk or mem full) */
+	}
+	/* we have enough space now */
+	assert(grow_end <= alloc->udb->base_size);
+	assert(alloc->udb->glob_data->fsize == alloc->udb->base_size);
+	return grow_xl(base, alloc, need, sz);
+}
+
+/** divide big(2**e2) into pieces so 2**exp fits */
+static udb_void
+udb_alloc_subdivide(void* base, udb_alloc* alloc, udb_void big, int e2,
+	int exp)
+{
+	int e = e2;
+	uint64_t sz = (uint64_t)1<<e2;
+	assert(big && e2 > exp);
+	/* so the returned piece to use is the first piece,
+	 * offload the later half until it fits */
+	do {
+		sz >>= 1; /* divide size of big by two */
+		e--;      /* that means its exp is one smaller */
+		udb_alloc_push_fl(base, alloc, big+sz, e);
+	} while(e != exp);
+	/* exit loop when last pushed is same size as what we want */
+	return big;
+}
+
+/** returns the exponent size of the chunk needed for data sz */
+static int
+udb_alloc_exp_needed(size_t sz)
+{
+	uint64_t asz = sz + sizeof(udb_chunk_d) + 1;
+	if(asz > UDB_ALLOC_CHUNK_SIZE) {
+		return UDB_EXP_XL;
+	} else if(asz <= UDB_ALLOC_CHUNK_MINSIZE) {
+		return UDB_ALLOC_CHUNK_MINEXP;
+	}
+	return udb_exp_size(asz);
+}
+
+udb_void udb_alloc_space(udb_alloc* alloc, size_t sz)
+{
+	void* base = alloc->udb->base;
+	/* calculate actual allocation size */
+	int e2, exp = udb_alloc_exp_needed(sz);
+	if(exp == UDB_EXP_XL)
+		return udb_alloc_xl_space(base, alloc, sz);
+	/* see if there is a free chunk of that size exactly */
+	if(alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP]) {
+		/* snip from freelist, udb_chunk_d */
+		udb_void ret;
+		alloc->udb->glob_data->dirty_alloc = udb_dirty_fl;
+		ret = udb_alloc_pop_fl(base, alloc, exp);
+		/* use it - size octets already OK */
+		UDB_CHUNK(ret)->flags = 0;
+		UDB_CHUNK(ret)->ptrlist = 0;
+		UDB_CHUNK(ret)->type = udb_chunk_type_data;
+		/* update stats */
+		alloc->disk->stat_data += sz;
+		alloc->disk->stat_alloc += (1<<exp);
+		assert(alloc->disk->stat_free >= (1u<<exp));
+		alloc->disk->stat_free -= (1<<exp);
+		alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+		return ret + sizeof(udb_chunk_d); /* ptr to data */
+	}
+	/* see if we can subdivide a larger chunk */
+	for(e2 = exp+1; e2 < UDB_ALLOC_CHUNKS_MAX; e2++)
+		if(alloc->disk->free[e2-UDB_ALLOC_CHUNK_MINEXP]) {
+			udb_void big, ret; /* udb_chunk_d */
+			alloc->udb->glob_data->dirty_alloc = udb_dirty_fl;
+			big = udb_alloc_pop_fl(base, alloc, e2);
+			/* push other parts onto freelists (needs inited) */
+			ret = udb_alloc_subdivide(base, alloc, big, e2, exp);
+			/* use final part (needs inited) */
+			UDB_CHUNK(ret)->exp = (uint8_t)exp;
+			/* if stop here; the new exp makes smaller free chunk*/
+			UDB_CHUNK(ret)->flags = 0;
+			UDB_CHUNK(ret)->ptrlist = 0;
+			/* set type to commit data chunk */
+			UDB_CHUNK(ret)->type = udb_chunk_type_data;
+			/* store last octet */
+			chunk_set_last(base, ret, exp, (uint8_t)exp);
+			/* update stats */
+			alloc->disk->stat_data += sz;
+			alloc->disk->stat_alloc += (1<<exp);
+			assert(alloc->disk->stat_free >= (1u<<exp));
+			alloc->disk->stat_free -= (1<<exp);
+			alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+			return ret + sizeof(udb_chunk_d); /* ptr to data */
+		}
+	/* we need to grow an extra chunk */
+	return udb_alloc_grow_space(base, alloc, sz, exp);
+}
+
+/** see if there is free space to allocate a chunk into */
+static int
+have_free_for(udb_alloc* alloc, int exp)
+{
+	int e2;
+	if(alloc->disk->free[exp-UDB_ALLOC_CHUNK_MINEXP])
+		return exp;
+	for(e2 = exp+1; e2 < UDB_ALLOC_CHUNKS_MAX; e2++)
+		if(alloc->disk->free[e2-UDB_ALLOC_CHUNK_MINEXP]) {
+			return e2;
+		}
+	return 0;
+}
+
+/** fix relptr prev and next for moved relptr structures */
+static void
+chunk_fix_ptr_each(void* base, udb_rel_ptr* rp, void* arg)
+{
+	udb_void* data = (udb_void*)arg;
+	udb_void r;
+	if(!rp->data)
+		return;
+	r = UDB_SYSTOREL(base, rp);
+	if(rp->next)
+		UDB_REL_PTR(rp->next)->prev = r;
+	if(rp->prev)
+		UDB_REL_PTR(rp->prev)->next = r;
+	else	{
+		/* if this is a pointer to its own chunk, fix it up;
+		 * the data ptr gets set by relptr_edit later. */
+		if(rp->data == data[0])
+			UDB_CHUNK(data[1])->ptrlist = r;
+		else	UDB_CHUNK(chunk_from_dataptr(rp->data))->ptrlist = r;
+	}
+}
+
+/** fix pointers from and to a moved chunk */
+static void
+chunk_fix_ptrs(void* base, udb_base* udb, udb_chunk_d* cp, udb_void data,
+	uint64_t dsz, udb_void olddata)
+{
+	udb_void d[2];
+	d[0] = olddata;
+	d[1] = data;
+	(*udb->walkfunc)(base, udb->walkarg, cp->type, UDB_REL(base, data),
+		dsz, &chunk_fix_ptr_each, d);
+	udb_rel_ptr_edit(base, cp->ptrlist, data);
+	udb_base_ram_ptr_edit(udb, olddata, data);
+}
+
+/** move an allocated chunk to use a free chunk */
+static void
+move_chunk(void* base, udb_alloc* alloc, udb_void f, int exp, uint64_t esz,
+	int e2)
+{
+	udb_void res = udb_alloc_pop_fl(base, alloc, e2);
+	udb_chunk_d* rp;
+	udb_chunk_d* fp;
+	if(exp != e2) {
+		/* it is bigger, subdivide it */
+		res = udb_alloc_subdivide(base, alloc, res, e2, exp);
+	}
+	assert(res != f);
+	/* setup rollback information */
+	alloc->udb->glob_data->rb_old = f;
+	alloc->udb->glob_data->rb_new = res;
+	alloc->udb->glob_data->rb_size = esz;
+	/* take the res, exp into use */
+	rp = UDB_CHUNK(res);
+	fp = UDB_CHUNK(f);
+	/* copy over the data */
+	memcpy(rp, fp, esz);
+	/* adjust rel ptrs */
+	chunk_fix_ptrs(base, alloc->udb, rp, res+sizeof(udb_chunk_d),
+		esz-sizeof(udb_chunk_d)-1, f+sizeof(udb_chunk_d));
+
+	/* do not freeup the fp; caller does that */
+}
+
+/** unlink several free elements to overwrite with xl chunk */
+static void
+free_xl_space(void* base, udb_alloc* alloc, udb_void s, uint64_t m)
+{
+	udb_void q = s + m - UDB_ALLOC_CHUNK_SIZE;
+	/* because of header and alignment we know s >= UDB_ALLOC_CHUNK_SIZE*/
+	assert(s >= UDB_ALLOC_CHUNK_SIZE);
+	while(q >= s) {
+		assert(UDB_CHUNK(q)->exp == UDB_ALLOC_CHUNKS_MAX);
+		assert(UDB_CHUNK(q)->type == udb_chunk_type_free);
+		udb_alloc_unlink_fl(base, alloc, q, UDB_ALLOC_CHUNKS_MAX);
+		q -= UDB_ALLOC_CHUNK_SIZE;
+	}
+}
+
+/** move an XL chunk, and keep track of segments for rollback */
+static void
+move_xl_segment(void* base, udb_base* udb, udb_void xl, udb_void n,
+	uint64_t sz, uint64_t startseg)
+{
+	udb_xl_chunk_d* xlp = UDB_XL_CHUNK(xl);
+	udb_xl_chunk_d* np = UDB_XL_CHUNK(n);
+	uint64_t amount = xl - n;
+	assert(n < xl); /* move to compact */
+
+	/* setup move rollback */
+	udb->glob_data->rb_old = xl;
+	udb->glob_data->rb_new = n;
+	udb->glob_data->rb_size = sz;
+
+	/* is it overlapping? */
+	if(sz <= amount) {
+		memcpy(np, xlp, sz);
+	} else {
+		/* move and commit per 1M segment to avoid data loss */
+		uint64_t seg, maxseg = amount/UDB_ALLOC_CHUNK_SIZE;
+		for(seg = startseg; seg<maxseg; seg++) {
+			udb->glob_data->rb_seg = seg;
+			memcpy(np+seg*UDB_ALLOC_CHUNK_SIZE,
+				xlp+seg*UDB_ALLOC_CHUNK_SIZE,
+				UDB_ALLOC_CHUNK_SIZE);
+		}
+
+	}
+}
+
+/** move list of XL chunks to the front by the shift amount */
+static void
+move_xl_list(void* base, udb_alloc* alloc, udb_void xl_start, uint64_t xl_sz,
+	uint64_t amount)
+{
+	udb_void xl = xl_start;
+	assert( (xl_start&(UDB_ALLOC_CHUNK_SIZE-1)) == 0 ); /* aligned */
+	assert( (amount&(UDB_ALLOC_CHUNK_SIZE-1)) == 0 ); /* multiples */
+	assert( (xl_sz&(UDB_ALLOC_CHUNK_SIZE-1)) == 0 ); /* multiples */
+	while(xl < xl_start+xl_sz) {
+		udb_xl_chunk_d* xlp = UDB_XL_CHUNK(xl);
+		udb_void n = xl-amount;
+		uint64_t sz = xlp->size;
+		assert(xlp->exp == UDB_EXP_XL);
+		move_xl_segment(base, alloc->udb, xl, n, sz, 0);
+		chunk_fix_ptrs(base, alloc->udb, UDB_CHUNK(n),
+			n+sizeof(udb_xl_chunk_d),
+			sz-sizeof(udb_xl_chunk_d)-sizeof(uint64_t)*2,
+			xl+sizeof(udb_xl_chunk_d));
+	}
+	alloc->disk->stat_free -= amount;
+	alloc->disk->nextgrow -= amount;
+	alloc->udb->glob_data->rb_old = 0;
+	alloc->udb->glob_data->rb_new = 0;
+	alloc->udb->glob_data->rb_size = 0;
+}
+
+/** see if free chunk can coagulate with another chunk, return other chunk */
+static udb_void
+coagulate_possible(void* base, udb_alloc* alloc, udb_void f, int exp,
+	uint64_t esz)
+{
+	udb_void other = f^esz;
+	if(exp == UDB_ALLOC_CHUNKS_MAX)
+		return 0; /* no further merges */
+	if(other >= alloc->udb->base_size)
+		return 0; /* not allocated */
+	if(other >= alloc->disk->nextgrow)
+		return 0; /* not in use */
+	if(other < alloc->udb->glob_data->hsize)
+		return 0; /* cannot merge with header */
+		/* the header is also protected by the special exp marker */
+	/* see if the other chunk is a free chunk */
+
+	/* check closest marker to avoid large memory churn */
+	/* and also it makes XL allocations and header special markers work */
+	if(f > other) {
+		assert(f > 1); /* this is certain because of header */
+		if(*((uint8_t*)UDB_REL(base, f-1)) == (uint8_t)exp) {
+			/* can do it if the other part is a free chunk */
+			assert(UDB_FREE_CHUNK(other)->exp == (uint8_t)exp);
+			if(UDB_CHUNK(other)->type == udb_chunk_type_free)
+				return other;
+		}
+	} else {
+		if(UDB_CHUNK(other)->exp == (uint8_t)exp) {
+			/* can do it if the other part is a free chunk */
+			assert(chunk_get_last(base, other, exp)==(uint8_t)exp);
+			if(UDB_CHUNK(other)->type == udb_chunk_type_free)
+				return other;
+		}
+	}
+	return 0;
+}
+
+/** coagulate and then add new free segment, return final free segment */
+static udb_void
+coagulate_and_push(void* base, udb_alloc* alloc, udb_void last, int exp,
+	uint64_t esz)
+{
+	/* new free chunk here, attempt coagulate */
+	udb_void other;
+	while( (other=coagulate_possible(base, alloc, last, exp, esz)) ) {
+		/* unlink that other chunk */
+		udb_alloc_unlink_fl(base, alloc, other, exp);
+		/* merge up */
+		if(other < last)
+			last = other;
+		exp++;
+		esz <<= 1;
+	}
+	/* free the final segment */
+	udb_alloc_push_fl(base, alloc, last, exp);
+	return last;
+}
+
+/** attempt to compact the data and move free space to the end */
+static int
+udb_alloc_compact(void* base, udb_alloc* alloc)
+{
+	udb_void last;
+	int exp, e2;
+	uint64_t esz;
+	uint64_t at = alloc->disk->nextgrow;
+	udb_void xl_start = 0;
+	uint64_t xl_sz = 0;
+	while(at > alloc->udb->glob_data->hsize) {
+		/* grab last entry */
+		exp = (int)*((uint8_t*)UDB_REL(base, at-1));
+		if(exp == UDB_EXP_XL) {
+			/* for XL chunks:
+			 * - inspect the size of the XLchunklist at end
+			 * - attempt to compact in front of of XLchunklist
+			 */
+			uint64_t xlsz = *((uint64_t*)UDB_REL(base,
+				at-sizeof(uint64_t)*2));
+			udb_void xl = at-xlsz;
+#ifndef NDEBUG
+			udb_xl_chunk_d* xlp = UDB_XL_CHUNK(xl);
+			assert(xlp->exp == UDB_EXP_XL);
+			assert(xlp->type != udb_chunk_type_free);
+#endif
+			/* got thesegment add to the xl chunk list */
+			if(xl_start != 0 && xl+xlsz != xl_start) {
+				/* nonadjoining XL part, but they are aligned,
+				 * so the space in between is whole Mbs,
+				 * shift the later part(s) and continue */
+				uint64_t m = xl_start - (xl+xlsz);
+				assert(xl_start > xl+xlsz);
+				alloc->udb->glob_data->dirty_alloc = udb_dirty_compact;
+				free_xl_space(base, alloc, xl+xlsz, m);
+				move_xl_list(base, alloc, xl_start, xl_sz, m);
+				alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+			}
+			xl_start = xl;
+			xl_sz += xlsz;
+			at = xl;
+			continue;
+			/* end of XL if */
+		} else if(exp < UDB_ALLOC_CHUNK_MINEXP
+			|| exp > UDB_ALLOC_CHUNKS_MAX)
+			break; /* special chunk or garbage */
+		esz = (uint64_t)1<<exp;
+		last = at - esz;
+		assert(UDB_CHUNK(last)->exp == (uint8_t)exp);
+		if(UDB_CHUNK(last)->type == udb_chunk_type_free) {
+			/* if xlstart continue looking to move stuff, but do
+			 * not unlink this free segment */
+			if(!xl_start) {
+				/* it is a free chunk, remove it */
+				alloc->udb->glob_data->dirty_alloc = udb_dirty_fl;
+				udb_alloc_unlink_fl(base, alloc, last, exp);
+				alloc->disk->stat_free -= esz;
+				alloc->disk->nextgrow = last;
+				alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+				/* and continue at this point */
+			}
+			at = last;
+		} else if( (e2=have_free_for(alloc, exp)) ) {
+			/* last entry can be allocated in free chunks
+			 * move it to its new position, adjust rel_ptrs */
+			alloc->udb->glob_data->dirty_alloc = udb_dirty_compact;
+			move_chunk(base, alloc, last, exp, esz, e2);
+			if(xl_start) {
+				last = coagulate_and_push(base, alloc,
+					last, exp, esz);
+			} else {
+				/* shorten usage */
+				alloc->disk->stat_free -= esz;
+				alloc->disk->nextgrow = last;
+			}
+			alloc->udb->glob_data->rb_old = 0;
+			alloc->udb->glob_data->rb_new = 0;
+			alloc->udb->glob_data->rb_size = 0;
+			alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+			/* and continue in front of it */
+			at = last;
+		} else {
+			/* cannot compact this block, stop compacting */
+			break;
+		}
+		/* if that worked, repeat it */
+	}
+	/* if we passed xl chunks, see if XL-chunklist can move */
+	if(xl_start) {
+		/* calculate free space in front of the XLchunklist. */
+		/* has to be whole mbs of free space */
+		/* if so, we can move the XL chunks.  Move them all back
+		 * by the new free space. */
+		/* this compacts very well, but the XL chunks can be moved
+		 * multiple times; worst case for every mb freed a huge sized
+		 * xlchunklist gets moved. */
+		/* free space must be, since aligned and coagulated, in
+		 * chunks of a whole MB */
+		udb_void at = xl_start;
+		uint64_t m = 0;
+		while(*((uint8_t*)UDB_REL(base, at-1))==UDB_ALLOC_CHUNKS_MAX){
+			udb_void chunk = at - UDB_ALLOC_CHUNK_SIZE;
+			if(UDB_CHUNK(chunk)->type != udb_chunk_type_free)
+				break;
+			assert(UDB_CHUNK(chunk)->exp==UDB_ALLOC_CHUNKS_MAX);
+			m += UDB_ALLOC_CHUNK_SIZE;
+			at = chunk;
+		}
+		if(m != 0) {
+			assert(at+m == xl_start);
+			alloc->udb->glob_data->dirty_alloc = udb_dirty_compact;
+			free_xl_space(base, alloc, at, m);
+			move_xl_list(base, alloc, xl_start, xl_sz, m);
+			alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+		}
+	}
+
+	/* if enough free, shrink the file; re-mmap */
+	if(enough_free(alloc)) {
+		uint64_t nsize = alloc->disk->nextgrow;
+		udb_base_shrink(alloc->udb, nsize);
+		if(!udb_base_remap(alloc->udb, alloc, nsize))
+			return 0;
+	}
+	return 1;
+}
+
+#ifdef UDB_CHECK
+/** check that rptrs are really zero before free */
+void udb_check_rptr_zero(void* base, udb_rel_ptr* p, void* arg)
+{
+	(void)base;
+	(void)arg;
+	assert(p->data == 0);
+}
+#endif /* UDB_CHECK */
+
+/** free XL chunk as multiples of CHUNK_SIZE free segments */
+static void
+udb_free_xl(void* base, udb_alloc* alloc, udb_void f, udb_xl_chunk_d* fp,
+	size_t sz)
+{
+	uint64_t xlsz = fp->size;
+	uint64_t c;
+	/* lightweight check for buffer overflow in xl data */
+	assert(*((uint64_t*)(UDB_REL(base, f+xlsz-sizeof(uint64_t)*2)))==xlsz);
+	assert(*((uint8_t*)(UDB_REL(base, f+xlsz-1))) == UDB_EXP_XL);
+	assert( (xlsz & (UDB_ALLOC_CHUNK_SIZE-1)) == 0 ); /* whole mbs */
+	assert( (f & (UDB_ALLOC_CHUNK_SIZE-1)) == 0 ); /* aligned */
+#ifdef UDB_CHECK
+	/* check that relptrs in this chunk have been zeroed */
+	(*alloc->udb->walkfunc)(base, alloc->udb->walkarg, fp->type,
+		UDB_REL(base, f+sizeof(udb_xl_chunk_d)), xlsz,
+		&udb_check_rptr_zero, NULL);
+#endif
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_fl;
+	/* update stats */
+	alloc->disk->stat_data -= sz;
+	alloc->disk->stat_alloc -= xlsz;
+	alloc->disk->stat_free += xlsz;
+	/* walk in reverse, so the front blocks go first on the list */
+	c = f + xlsz - UDB_ALLOC_CHUNK_SIZE;
+	/* because of header and alignment we know f >= UDB_ALLOC_CHUNK_SIZE*/
+	assert(f >= UDB_ALLOC_CHUNK_SIZE);
+	while(c >= f) {
+		/* free a block of CHUNK_SIZE (1 Mb) */
+		udb_alloc_push_fl(base, alloc, c, UDB_ALLOC_CHUNKS_MAX);
+		c -= UDB_ALLOC_CHUNK_SIZE;
+	}
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+}
+
+int udb_alloc_free(udb_alloc* alloc, udb_void r, size_t sz)
+{
+	void* base;
+	/* lookup chunk ptr */
+	udb_void f;
+	udb_chunk_d* fp;
+	uint64_t esz;
+	int exp;
+	udb_void other;
+	int coagulated = 0;
+	if(!r)
+		return 1; /* free(NULL) does nothing */
+
+	/* lookup size of chunk */
+	base = alloc->udb->base;
+	/* fails for XL blocks */
+	f = chunk_from_dataptr(r);
+	fp = UDB_CHUNK(f);
+	assert(fp->type != udb_chunk_type_free);
+
+	/* see if it has a ptrlist, if so: trouble, the list is not properly
+	 * cleaned up. (although you can imagine a wholesale delete where
+	 * it does not matter) */
+	assert(fp->ptrlist == 0);
+
+	/* set ptrlist to 0 to stop relptr from using it, robustness. */
+	fp->ptrlist = 0;
+
+	if(fp->exp == UDB_EXP_XL) {
+		udb_free_xl(base, alloc, f, (udb_xl_chunk_d*)fp, sz);
+		/* compact */
+		return udb_alloc_compact(base, alloc);
+	}
+	/* it is a regular chunk of 2**exp size */
+	exp = (int)fp->exp;
+	esz = (uint64_t)1<<exp;
+	/* light check for e.g. buffer overflow of the data */
+	assert(sz < esz);
+	assert(chunk_get_last(base, f, exp) == (uint8_t)exp);
+#ifdef UDB_CHECK
+	/* check that relptrs in this chunk have been zeroed */
+	(*alloc->udb->walkfunc)(base, alloc->udb->walkarg, fp->type,
+		UDB_REL(base, r), esz, &udb_check_rptr_zero, NULL);
+#endif
+
+	/* update the stats */
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_fl;
+	alloc->disk->stat_data -= sz;
+	alloc->disk->stat_free += esz;
+	alloc->disk->stat_alloc -= esz;
+
+	/* if it can be merged with other free chunks, do so */
+	while( (other=coagulate_possible(base, alloc, f, exp, esz)) ) {
+		coagulated = 1;
+		/* unlink that other chunk and expand it (it has same size) */
+		udb_alloc_unlink_fl(base, alloc, other, exp);
+		/* merge up */
+		if(other < f)
+			f = other;
+		exp++;
+		esz <<= 1;
+	}
+	if(coagulated) {
+		/* put big free chunk into freelist, and init it */
+		udb_alloc_push_fl(base, alloc, f, exp);
+	} else {
+		/* we do not need to touch the last-exp-byte, which may save
+		 * a reference to that page of memory */
+		fp->type = udb_chunk_type_free;
+		fp->flags = 0;
+		udb_alloc_push_fl_noinit(base, alloc, f, exp);
+	}
+	alloc->udb->glob_data->dirty_alloc = udb_dirty_clean;
+	/* compact */
+	return udb_alloc_compact(base, alloc);
+}
+
+udb_void udb_alloc_init(udb_alloc* alloc, void* d, size_t sz)
+{
+	/* could be faster maybe, if grown? */
+	udb_void r = udb_alloc_space(alloc, sz);
+	if(!r) return r;
+	memcpy(UDB_REL(alloc->udb->base, r), d, sz);
+	return r;
+}
+
+udb_void udb_alloc_realloc(udb_alloc* alloc, udb_void r, size_t osz, size_t sz)
+{
+	void* base = alloc->udb->base;
+	udb_void c, n, newd;
+	udb_chunk_d* cp, *np;
+	uint64_t avail;
+	uint8_t cp_type;
+	/* emulate some posix realloc stuff */
+	if(r == 0)
+		return udb_alloc_space(alloc, sz);
+	if(sz == 0) {
+		if(!udb_alloc_free(alloc, r, osz))
+			log_msg(LOG_ERR, "udb_alloc_realloc: free failed");
+		return 0;
+	}
+	c = chunk_from_dataptr(r);
+	cp = UDB_CHUNK(c);
+	cp_type = cp->type;
+	if(cp->exp == UDB_EXP_XL) {
+		avail = UDB_XL_CHUNK(c)->size - sizeof(udb_xl_chunk_d)
+			- sizeof(uint64_t)*2;
+	} else {
+		avail = ((uint64_t)1<<cp->exp) - sizeof(udb_chunk_d) - 1;
+	}
+	if(sz <= avail)
+		return r;
+	/* reallocate it, and copy */
+	newd = udb_alloc_space(alloc, sz);
+	if(!newd) return 0;
+	/* re-base after alloc, since re-mmap may have happened */
+	base = alloc->udb->base;
+	cp = NULL; /* may be invalid now, robustness */
+	n = chunk_from_dataptr(newd);
+	np = UDB_CHUNK(n);
+	np->type = cp_type;
+	memcpy(UDB_REL(base, newd), UDB_REL(base, r), osz);
+	/* fixup ptrs */
+	chunk_fix_ptrs(base, alloc->udb, np, newd, osz, r);
+
+	if(!udb_alloc_free(alloc, r, osz))
+		log_msg(LOG_ERR, "udb_alloc_realloc: free failed");
+	return newd;
+}
+
+int udb_alloc_grow(udb_alloc* alloc, size_t sz, size_t num)
+{
+	const uint64_t mb = 1024*1024;
+	int exp = udb_alloc_exp_needed(sz);
+	uint64_t esz;
+	uint64_t want;
+	if(exp == UDB_EXP_XL)
+		esz = (sz&(mb-1))+mb;
+	else	esz = (uint64_t)1<<exp;
+	/* we need grow_end_calc to take into account alignment */
+	want = grow_end_calc(alloc, exp) + esz*(num-1);
+	assert(want >= alloc->udb->base_size);
+	if(!udb_base_grow_and_remap(alloc->udb, want)) {
+		log_msg(LOG_ERR, "failed to grow the specified amount");
+		return 0;
+	}
+	return 1;
+}
+
+void udb_alloc_set_type(udb_alloc* alloc, udb_void r, udb_chunk_type tp)
+{
+	void* base = alloc->udb->base;
+	udb_void f = chunk_from_dataptr(r);
+	udb_chunk_d* fp = UDB_CHUNK(f);
+	/* not the 'free' type, that must be set by allocation routines */
+	assert(fp->type != udb_chunk_type_free);
+	assert(tp != udb_chunk_type_free);
+	fp->type = tp;
+}
+
+int udb_valid_offset(udb_base* udb, udb_void to, size_t destsize)
+{
+	/* pointers are not valid before the header-size or after the
+	 * used-region of the mmap */
+	return ( (to+destsize) <= udb->base_size &&
+		to >= (udb->glob_data->hsize-2*sizeof(udb_rel_ptr)) &&
+		(to+destsize) <= udb->alloc->disk->nextgrow);
+}
+
+int udb_valid_dataptr(udb_base* udb, udb_void to)
+{
+	void* base = udb->base;
+	udb_void ch;
+	int exp;
+	uint64_t esz;
+	/* our data chunks are aligned and at least 8 bytes */
+	if(!udb_valid_offset(udb, to, sizeof(uint64_t)))
+		return 0;
+	/* get the chunk pointer */
+	ch = chunk_from_dataptr(to);
+	if(!udb_valid_offset(udb, ch, sizeof(udb_chunk_d)))
+		return 0;
+	/* check its size */
+	exp = UDB_CHUNK(ch)->exp;
+	if(exp == UDB_EXP_XL) {
+		/* check XL chunk */
+		uint64_t xlsz;
+		if(!udb_valid_offset(udb, ch, sizeof(udb_xl_chunk_d)))
+			return 0;
+		xlsz = UDB_XL_CHUNK(ch)->size;
+		if(!udb_valid_offset(udb, ch+xlsz-1, 1))
+			return 0;
+		if(*((uint8_t*)UDB_REL(base, ch+xlsz-1)) != UDB_EXP_XL)
+			return 0;
+		if(*((uint64_t*)UDB_REL(base, ch+xlsz-sizeof(uint64_t)*2))
+			!= xlsz)
+			return 0;
+		return 1;
+	}
+	/* check if regular chunk has matching end byte */
+	if(exp < UDB_ALLOC_CHUNK_MINEXP || exp > UDB_ALLOC_CHUNKS_MAX)
+		return 0; /* cannot be a valid chunk */
+	esz = 1<<exp;
+	if(!udb_valid_offset(udb, ch+esz-1, 1))
+		return 0;
+	if(*((uint8_t*)UDB_REL(base, ch+esz-1)) != exp)
+		return 0;
+	return 1;
+}
+
+int udb_valid_rptr(udb_base* udb, udb_void rptr, udb_void to)
+{
+	void* base = udb->base;
+	udb_void p;
+	if(!udb_valid_offset(udb, rptr, sizeof(udb_rel_ptr)))
+		return 0;
+	if(!udb_valid_dataptr(udb, to))
+		return 0;
+	p = UDB_CHUNK(chunk_from_dataptr(to))->ptrlist;
+	while(p) {
+		if(!udb_valid_offset(udb, p, sizeof(udb_rel_ptr)))
+			return 0;
+		if(p == rptr)
+			return 1;
+		p = UDB_REL_PTR(p)->next;
+	}
+	return 0;
+}
+
+void udb_rel_ptr_init(udb_rel_ptr* ptr)
+{
+	memset(ptr, 0, sizeof(*ptr));
+}
+
+void udb_rel_ptr_unlink(void* base, udb_rel_ptr* ptr)
+{
+	if(!ptr->data)
+		return;
+	if(ptr->prev) {
+		UDB_REL_PTR(ptr->prev)->next = ptr->next;
+	} else {
+		UDB_CHUNK(chunk_from_dataptr(ptr->data))->ptrlist = ptr->next;
+	}
+	if(ptr->next) {
+		UDB_REL_PTR(ptr->next)->prev = ptr->prev;
+	}
+}
+
+void udb_rel_ptr_link(void* base, udb_rel_ptr* ptr, udb_void to)
+{
+	udb_chunk_d* chunk = UDB_CHUNK(chunk_from_dataptr(to));
+	ptr->prev = 0;
+	ptr->next = chunk->ptrlist;
+	if(ptr->next)
+		UDB_REL_PTR(ptr->next)->prev = UDB_SYSTOREL(base, ptr);
+	chunk->ptrlist = UDB_SYSTOREL(base, ptr);
+	ptr->data = to;
+}
+
+void udb_rel_ptr_set(void* base, udb_rel_ptr* ptr, udb_void to)
+{
+	assert(to == 0 || to > 64);
+	udb_rel_ptr_unlink(base, ptr);
+	if(to)
+		udb_rel_ptr_link(base, ptr, to);
+	else	ptr->data = to;
+}
+
+void udb_rel_ptr_edit(void* base, udb_void list, udb_void to)
+{
+	udb_void p = list;
+	while(p) {
+		UDB_REL_PTR(p)->data = to;
+		p = UDB_REL_PTR(p)->next;
+	}
+}
+
+#ifdef UDB_CHECK
+/** check that all pointers are validly chained */
+static void
+udb_check_ptrs_valid(udb_base* udb)
+{
+	size_t i;
+	udb_ptr* p, *prev;
+	for(i=0; i<udb->ram_size; i++) {
+		prev = NULL;
+		for(p=udb->ram_hash[i]; p; p=p->next) {
+			assert(p->prev == prev);
+			assert((size_t)(chunk_hash_ptr(p->data)&udb->ram_mask)
+				== i);
+			assert(p->base == &udb->base);
+			prev = p;
+		}
+	}
+}
+#endif /* UDB_CHECK */
+
+void udb_ptr_init(udb_ptr* ptr, udb_base* udb)
+{
+#ifdef UDB_CHECK
+	udb_check_ptrs_valid(udb); /* previous ptrs have been unlinked */
+#endif
+	memset(ptr, 0, sizeof(*ptr));
+	ptr->base = &udb->base;
+}
+
+void udb_ptr_set(udb_ptr* ptr, udb_base* udb, udb_void newval)
+{
+	assert(newval == 0 || newval > 64);
+	if(ptr->data)
+		udb_base_unlink_ptr(udb, ptr);
+	ptr->data = newval;
+	if(newval)
+		udb_base_link_ptr(udb, ptr);
+}
+
+int udb_ptr_alloc_space(udb_ptr* ptr, udb_base* udb, udb_chunk_type type,
+	size_t sz)
+{
+	udb_void r;
+	r = udb_alloc_space(udb->alloc, sz);
+	if(!r) return 0;
+	udb_alloc_set_type(udb->alloc, r, type);
+	udb_ptr_init(ptr, udb);
+	udb_ptr_set(ptr, udb, r);
+	return 1;
+}
+
+void udb_ptr_free_space(udb_ptr* ptr, udb_base* udb, size_t sz)
+{
+	if(ptr->data) {
+		udb_void d = ptr->data;
+		udb_ptr_set(ptr, udb, 0);
+		udb_alloc_free(udb->alloc, d, sz);
+	}
+}
+
+udb_chunk_type udb_ptr_get_type(udb_ptr* ptr)
+{
+	udb_void f;
+	if(!ptr || ptr->data == 0) return udb_chunk_type_internal; /* something bad*/
+	f = chunk_from_dataptr(ptr->data);
+	return ((udb_chunk_d*)UDB_REL(*ptr->base, f))->type;
+}