/* 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)
{
        assert(exp >= 0 && exp <= 63);
        *((uint8_t*)UDB_REL(base, chunk+((uint64_t)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, fsz;
        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_array_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);
                goto fail;
        }
        if(g.clean_close != 1) {
                log_msg(LOG_WARNING, "%s: not cleanly closed %d", fname,
                        (int)g.clean_close);
                goto fail;
        }
        if(g.dirty_alloc != 0) {
                log_msg(LOG_WARNING, "%s: not cleanly closed (alloc:%d)", fname,
                        (int)g.dirty_alloc);
                goto fail;
        }

        /* check file size correctly written, for 4.0.2 nsd.db failure */
        fsz = (uint64_t)lseek(fd, (off_t)0, SEEK_END);
        (void)lseek(fd, (off_t)0, SEEK_SET);
        if(g.fsize != fsz) {
                log_msg(LOG_WARNING, "%s: file size %llu but mmap header "
                        "has size %llu", fname, (unsigned long long)fsz,
                        (unsigned long long)g.fsize);
                goto fail;
        }

        /* mmap it */
        if(g.fsize < UDB_HEADER_SIZE || g.fsize < g.hsize) {
                log_msg(LOG_ERR, "%s: file too short", fname);
                goto fail;
        }
        if(g.fsize > (uint64_t)400*1024*1024*1024*1024) /* 400 Tb */ {
                log_msg(LOG_WARNING, "%s: file size too large %llu",
                        fname, (unsigned long long)g.fsize);
                goto fail;
        }
        udb->base_size = (size_t)g.fsize;
#ifdef HAVE_MMAP
        /* 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);
#else
        udb->base = MAP_FAILED; errno = ENOSYS;
#endif
        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*)((char*)udb->base+sizeof(uint64_t));
        r = 0;
        /* cannot be dirty because that is goto fail above */
        if(udb->glob_data->dirty_alloc != udb_dirty_clean)
                r = 1;
        udb->alloc = udb_alloc_create(udb, (udb_alloc_d*)(
                (char*)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);
        }
        udb->glob_data->clean_close = 0;

        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);
        g.clean_close = 1;

        /* 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;
        }
        /* truncate to the right size */
        if(ftruncate(fd, (off_t)g.fsize) < 0) {
                log_msg(LOG_ERR, "%s: ftruncate(%d): %s", fname,
                        (int)g.fsize, 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. */
#ifdef HAVE_MMAP
        msync(udb->base, udb->base_size, MS_ASYNC);
#endif
        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) {
                udb->glob_data->clean_close = 1;
                close(udb->fd);
                udb->fd = -1;
        }
        if(udb->base) {
#ifdef HAVE_MMAP
                if(munmap(udb->base, udb->base_size) == -1) {
                        log_msg(LOG_ERR, "munmap: %s", strerror(errno));
                }
#endif
                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(!udb) return;
#ifdef HAVE_MMAP
        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));
        }
#else
        (void)wait;
#endif
}

/** 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;
#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)0x7fffffff) {
                /* grow the array, if allocation succeeds */
                udb_ptr** newram = (udb_ptr**)xalloc_array_zero(
                        sizeof(udb_ptr*), udb->ram_size*2);
                if(newram) {
                        grow_ram_hash(udb, newram);
                }
        }
        i = chunk_hash_ptr(ptr->data) & udb->ram_mask;
        assert((size_t)i < udb->ram_size);

        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)
{
#ifdef HAVE_MMAP
        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*)((char*)nb+sizeof(uint64_t));
                /* use passed alloc pointer because the udb->alloc may not
                 * be initialized yet */
                alloc->disk = (udb_alloc_d*)((char*)udb->glob_data
                        +sizeof(*udb->glob_data));
        }
        udb->base_size = nsize;
        return nb;
#else /* HAVE_MMAP */
        (void)udb; (void)alloc; (void)nsize;
        return NULL;
#endif /* HAVE_MMAP */
}

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( x>=0 && x<=63);
        assert( ((uint64_t)1<<x) >= a);
        assert( x==0 || /* <<x-1 without negative number analyzer complaints: */ (((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,
                                ((char*)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,
                                ((char*)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 enough 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;
        int exp;
        if(asz > UDB_ALLOC_CHUNK_SIZE) {
                return UDB_EXP_XL;
        } else if(asz <= UDB_ALLOC_CHUNK_MINSIZE) {
                return UDB_ALLOC_CHUNK_MINEXP;
        }
        exp = udb_exp_size(asz);
        assert(exp <= UDB_ALLOC_CHUNKS_MAX);
        return exp;
}

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 */
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;
        if(alloc->udb->inhibit_compact)
                return 1;
        alloc->udb->useful_compact = 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;
}

int
udb_compact(udb_base* udb)
{
        if(!udb) return 1;
        if(!udb->useful_compact) return 1;
        DEBUG(DEBUG_DBACCESS, 1, (LOG_INFO, "Compacting database..."));
        return udb_alloc_compact(udb->base, udb->alloc);
}

void udb_compact_inhibited(udb_base* udb, int inhibit)
{
        if(!udb) return;
        udb->inhibit_compact = inhibit;
}

#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 */
                if(alloc->udb->inhibit_compact) {
                        alloc->udb->useful_compact = 1;
                        return 1;
                }
                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 */
        if(alloc->udb->inhibit_compact) {
                alloc->udb->useful_compact = 1;
                return 1;
        }
        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;
}