cdbr.c

/*	$NetBSD: cdbr.c,v 1.2 2017/01/10 23:06:06 christos Exp $	*/
/*-
 * Copyright (c) 2010 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Joerg Sonnenberger.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/cdefs.h>
#include <sys/mman.h>
#include <sys/stat.h>

#include <errno.h>
#include <fcntl.h>
#include <inttypes.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "cdbr.h"

#define SET_ERRNO(val) errno = (val)

#ifndef fast_divide32_prepare
#define	fast_divide32_prepare(d,m,s1,s2)	(void)0
#endif

#ifndef fast_remainder32
#define	fast_remainder32(v,d,m,s1,s2)		(v%d)
#endif

extern void mi_vector_hash(const void * __restrict, size_t, uint32_t,
    uint32_t[3]);

struct cdbr {
	void (*unmap)(void *, void *, size_t);
	void *cookie;
	uint8_t *mmap_base;
	size_t mmap_size;

	uint8_t *hash_base;
	uint8_t *offset_base;
	uint8_t *data_base;

	uint32_t data_size;
	uint32_t entries;
	uint32_t entries_index;
	uint32_t seed;

	uint8_t offset_size;
	uint8_t index_size;

	uint32_t entries_m;
	uint32_t entries_index_m;
	uint8_t entries_s1, entries_s2;
	uint8_t entries_index_s1, entries_index_s2;
};

/* From NetBSD sys/external/bsd/libnv/dist/nv_compat.h */
static uint32_t
le32dec(const void *buf)
{
	uint8_t const *p = (uint8_t const *) buf;

	return (((unsigned) p[3] << 24) | (p[2] << 16) | (p[1] << 8) | p[0]);
}

#if !defined(_KERNEL) && !defined(_STANDALONE)
static void
cdbr_unmap(void *cookie __unused, void *base, size_t size)
{
	munmap(base, size);
}

/* ARGSUSED */
struct cdbr *
cdbr_open(const char *path, int flags)
{
	void *base;
	size_t size;
	int fd;
	struct cdbr *cdbr;
	struct stat sb;

	if ((fd = open(path, O_RDONLY)) == -1)
		return NULL;
	if (fstat(fd, &sb) == -1) {
		close(fd);
		return NULL;
	}

	if (sb.st_size >= SSIZE_MAX) {
		close(fd);
		SET_ERRNO(EINVAL);
		return NULL;
	}


	size = (size_t)sb.st_size;
	base = mmap(NULL, size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0);
	close(fd);

	if (base == MAP_FAILED)
		return NULL;

	cdbr = cdbr_open_mem(base, size, flags, cdbr_unmap, NULL);
	if (cdbr == NULL)
		munmap(base, size);
	return cdbr;
}
#endif

struct cdbr *
cdbr_open_mem(void *base, size_t size, int flags __unused,
    void (*unmap)(void *, void *, size_t), void *cookie)
{
	struct cdbr *cdbr;
	uint8_t *buf = base;
	if (size < 40 || memcmp(buf, "NBCDB\n\0\001", 8)) {
		SET_ERRNO(EINVAL);
		return NULL;
	}

	cdbr = malloc(sizeof(*cdbr));
	cdbr->unmap = unmap;
	cdbr->cookie = cookie;

	cdbr->data_size = le32dec(buf + 24);
	cdbr->entries = le32dec(buf + 28);
	cdbr->entries_index = le32dec(buf + 32);
	cdbr->seed = le32dec(buf + 36);

	if (cdbr->data_size < 0x100)
		cdbr->offset_size = 1;
	else if (cdbr->data_size < 0x10000)
		cdbr->offset_size = 2;
	else
		cdbr->offset_size = 4;

	if (cdbr->entries_index < 0x100)
		cdbr->index_size = 1;
	else if (cdbr->entries_index < 0x10000)
		cdbr->index_size = 2;
	else
		cdbr->index_size = 4;

	cdbr->mmap_base = base;
	cdbr->mmap_size = size;

	cdbr->hash_base = cdbr->mmap_base + 40;
	cdbr->offset_base = cdbr->hash_base + cdbr->entries_index * cdbr->index_size;
	if (cdbr->entries_index * cdbr->index_size % cdbr->offset_size)
		cdbr->offset_base += cdbr->offset_size -
		    cdbr->entries_index * cdbr->index_size % cdbr->offset_size;
	cdbr->data_base = cdbr->offset_base + (cdbr->entries + 1) * cdbr->offset_size;

	if (cdbr->hash_base < cdbr->mmap_base ||
	    cdbr->offset_base < cdbr->mmap_base ||
	    cdbr->data_base < cdbr->mmap_base ||
	    cdbr->data_base + cdbr->data_size < cdbr->mmap_base ||
	    cdbr->data_base + cdbr->data_size >
	    cdbr->mmap_base + cdbr->mmap_size) {
		SET_ERRNO(EINVAL);
		free(cdbr);
		return NULL;
	}

	if (cdbr->entries) {
		fast_divide32_prepare(cdbr->entries, &cdbr->entries_m,
		    &cdbr->entries_s1, &cdbr->entries_s2);
	}
	if (cdbr->entries_index) {
		fast_divide32_prepare(cdbr->entries_index,
		    &cdbr->entries_index_m,
		    &cdbr->entries_index_s1, &cdbr->entries_index_s2);
	}

	return cdbr;
}

static uint32_t
get_uintX(const uint8_t *addr, uint32_t idx, int size)
{
	addr += idx * size;

	if (size == 4)
		return /* LINTED */le32toh(*(const uint32_t *)addr);
	else if (size == 2)
		return /* LINTED */le16toh(*(const uint16_t *)addr);
	else
		return *addr;
}

uint32_t
cdbr_entries(struct cdbr *cdbr)
{

	return cdbr->entries;
}

int
cdbr_get(struct cdbr *cdbr, uint32_t idx, const void **data, size_t *data_len)
{
	uint32_t start, end;

	if (idx >= cdbr->entries) {
		SET_ERRNO(EINVAL);
		return -1;
	}

	start = get_uintX(cdbr->offset_base, idx, cdbr->offset_size);
	end = get_uintX(cdbr->offset_base, idx + 1, cdbr->offset_size);

	if (start > end) {
		SET_ERRNO(EIO);
		return -1;
	}

	if (end > cdbr->data_size) {
		SET_ERRNO(EIO);
		return -1;
	}

	*data = cdbr->data_base + start;
	*data_len = end - start;

	return 0;
}

int
cdbr_find(struct cdbr *cdbr, const void *key, size_t key_len,
    const void **data, size_t *data_len)
{
	uint32_t hashes[3], idx;

	if (cdbr->entries_index == 0) {
		SET_ERRNO(EINVAL);
		return -1;
	}

	mi_vector_hash(key, key_len, cdbr->seed, hashes);

	hashes[0] = fast_remainder32(hashes[0], cdbr->entries_index,
	    cdbr->entries_index_m, cdbr->entries_index_s1,
	    cdbr->entries_index_s2);
	hashes[1] = fast_remainder32(hashes[1], cdbr->entries_index,
	    cdbr->entries_index_m, cdbr->entries_index_s1,
	    cdbr->entries_index_s2);
	hashes[2] = fast_remainder32(hashes[2], cdbr->entries_index,
	    cdbr->entries_index_m, cdbr->entries_index_s1,
	    cdbr->entries_index_s2);

	idx = get_uintX(cdbr->hash_base, hashes[0], cdbr->index_size);
	idx += get_uintX(cdbr->hash_base, hashes[1], cdbr->index_size);
	idx += get_uintX(cdbr->hash_base, hashes[2], cdbr->index_size);

	return cdbr_get(cdbr, fast_remainder32(idx, cdbr->entries,
	    cdbr->entries_m, cdbr->entries_s1, cdbr->entries_s2), data,
	    data_len);
}

void
cdbr_close(struct cdbr *cdbr)
{
	if (cdbr->unmap)
		(*cdbr->unmap)(cdbr->cookie, cdbr->mmap_base, cdbr->mmap_size);
	free(cdbr);
}