common/lib/libc/cdb/cdbr.c

   1 /*      $NetBSD: cdbr.c,v 1.1 2013/12/11 01:24:08 joerg Exp $   */
   2 /*-
   3  * Copyright (c) 2010 The NetBSD Foundation, Inc.
   4  * All rights reserved.
   5  *
   6  * This code is derived from software contributed to The NetBSD Foundation
   7  * by Joerg Sonnenberger.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in
  17  *    the documentation and/or other materials provided with the
  18  *    distribution.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  24  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  28  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  29  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  30  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #if HAVE_NBTOOL_CONFIG_H
  35 #include "nbtool_config.h"
  36 #endif
  37
  38 #include <sys/cdefs.h>
  39 __RCSID("$NetBSD: cdbr.c,v 1.1 2013/12/11 01:24:08 joerg Exp $");
  40
  41 #if !defined(_KERNEL) && !defined(_STANDALONE)
  42 #include "namespace.h"
  43 #endif
  44
  45 #if !HAVE_NBTOOL_CONFIG_H
  46 #include <sys/bitops.h>
  47 #endif
  48 #if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
  49 #include <sys/endian.h>
  50 #endif
  51
  52 #if defined(_KERNEL) || defined(_STANDALONE)
  53 #include <sys/cdbr.h>
  54 #include <sys/kmem.h>
  55 #include <sys/systm.h>
  56 #include <lib/libkern/libkern.h>
  57 #define SET_ERRNO(val)
  58 #define malloc(size) kmem_alloc(size, KM_SLEEP)
  59 #define free(ptr) kmem_free(ptr, sizeof(struct cdbr))
  60 #else
  61 #include <sys/mman.h>
  62 #include <sys/stat.h>
  63 #include <cdbr.h>
  64 #include <errno.h>
  65 #include <fcntl.h>
  66 #include <inttypes.h>
  67 #include <limits.h>
  68 #include <stdlib.h>
  69 #include <string.h>
  70 #include <unistd.h>
  71 #define SET_ERRNO(val) errno = (val)
  72 #endif
  73
  74 #if !defined(_KERNEL) && !defined(_STANDALONE)
  75 #ifdef __weak_alias
  76 __weak_alias(cdbr_close,_cdbr_close)
  77 __weak_alias(cdbr_find,_cdbr_find)
  78 __weak_alias(cdbr_get,_cdbr_get)
  79 __weak_alias(cdbr_open,_cdbr_open)
  80 __weak_alias(cdbr_open_mem,_cdbr_open_mem)
  81 #endif
  82 #endif
  83
  84 #if HAVE_NBTOOL_CONFIG_H
  85 #define fast_divide32_prepare(d,m,s1,s2)        (void)0
  86 #define fast_remainder32(v,d,m,s1,s2)           (v%d)
  87 #endif
  88
  89 struct cdbr {
  90         void (*unmap)(void *, void *, size_t);
  91         void *cookie;
  92         uint8_t *mmap_base;
  93         size_t mmap_size;
  94
  95         uint8_t *hash_base;
  96         uint8_t *offset_base;
  97         uint8_t *data_base;
  98
  99         uint32_t data_size;
 100         uint32_t entries;
 101         uint32_t entries_index;
 102         uint32_t seed;
 103
 104         uint8_t offset_size;
 105         uint8_t index_size;
 106
 107         uint32_t entries_m;
 108         uint32_t entries_index_m;
 109         uint8_t entries_s1, entries_s2;
 110         uint8_t entries_index_s1, entries_index_s2;
 111 };
 112
 113 #if !defined(_KERNEL) && !defined(_STANDALONE)
 114 static void
 115 cdbr_unmap(void *cookie __unused, void *base, size_t size)
 116 {
 117         munmap(base, size);
 118 }
 119
 120 /* ARGSUSED */
 121 struct cdbr *
 122 cdbr_open(const char *path, int flags)
 123 {
 124         void *base;
 125         size_t size;
 126         int fd;
 127         struct cdbr *cdbr;
 128         struct stat sb;
 129
 130         if ((fd = open(path, O_RDONLY)) == -1)
 131                 return NULL;
 132         if (fstat(fd, &sb) == -1) {
 133                 close(fd);
 134                 return NULL;
 135         }
 136
 137         if (sb.st_size >= SSIZE_MAX) {
 138                 close(fd);
 139                 SET_ERRNO(EINVAL);
 140                 return NULL;
 141         }
 142
 143
 144         size = (size_t)sb.st_size;
 145         base = mmap(NULL, size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0);
 146         close(fd);
 147
 148         if (base == MAP_FAILED)
 149                 return NULL;
 150
 151         cdbr = cdbr_open_mem(base, size, flags, cdbr_unmap, NULL);
 152         if (cdbr == NULL)
 153                 munmap(base, size);
 154         return cdbr;
 155 }
 156 #endif
 157
 158 struct cdbr *
 159 cdbr_open_mem(void *base, size_t size, int flags,
 160     void (*unmap)(void *, void *, size_t), void *cookie)
 161 {
 162         struct cdbr *cdbr;
 163         uint8_t *buf = base;
 164         if (size < 40 || memcmp(buf, "NBCDB\n\0\001", 8)) {
 165                 SET_ERRNO(EINVAL);
 166                 return NULL;
 167         }
 168
 169         cdbr = malloc(sizeof(*cdbr));
 170         cdbr->unmap = unmap;
 171         cdbr->cookie = cookie;
 172
 173         cdbr->data_size = le32dec(buf + 24);
 174         cdbr->entries = le32dec(buf + 28);
 175         cdbr->entries_index = le32dec(buf + 32);
 176         cdbr->seed = le32dec(buf + 36);
 177
 178         if (cdbr->data_size < 0x100)
 179                 cdbr->offset_size = 1;
 180         else if (cdbr->data_size < 0x10000)
 181                 cdbr->offset_size = 2;
 182         else
 183                 cdbr->offset_size = 4;
 184
 185         if (cdbr->entries_index < 0x100)
 186                 cdbr->index_size = 1;
 187         else if (cdbr->entries_index < 0x10000)
 188                 cdbr->index_size = 2;
 189         else
 190                 cdbr->index_size = 4;
 191
 192         cdbr->mmap_base = base;
 193         cdbr->mmap_size = size;
 194
 195         cdbr->hash_base = cdbr->mmap_base + 40;
 196         cdbr->offset_base = cdbr->hash_base + cdbr->entries_index * cdbr->index_size;
 197         if (cdbr->entries_index * cdbr->index_size % cdbr->offset_size)
 198                 cdbr->offset_base += cdbr->offset_size -
 199                     cdbr->entries_index * cdbr->index_size % cdbr->offset_size;
 200         cdbr->data_base = cdbr->offset_base + (cdbr->entries + 1) * cdbr->offset_size;
 201
 202         if (cdbr->hash_base < cdbr->mmap_base ||
 203             cdbr->offset_base < cdbr->mmap_base ||
 204             cdbr->data_base < cdbr->mmap_base ||
 205             cdbr->data_base + cdbr->data_size < cdbr->mmap_base ||
 206             cdbr->data_base + cdbr->data_size >
 207             cdbr->mmap_base + cdbr->mmap_size) {
 208                 SET_ERRNO(EINVAL);
 209                 free(cdbr);
 210                 return NULL;
 211         }
 212
 213         if (cdbr->entries) {
 214                 fast_divide32_prepare(cdbr->entries, &cdbr->entries_m,
 215                     &cdbr->entries_s1, &cdbr->entries_s2);
 216         }
 217         if (cdbr->entries_index) {
 218                 fast_divide32_prepare(cdbr->entries_index,
 219                     &cdbr->entries_index_m,
 220                     &cdbr->entries_index_s1, &cdbr->entries_index_s2);
 221         }
 222
 223         return cdbr;
 224 }
 225
 226 static inline uint32_t
 227 get_uintX(const uint8_t *addr, uint32_t idx, int size)
 228 {
 229         addr += idx * size;
 230
 231         if (size == 4)
 232                 return /* LINTED */le32toh(*(const uint32_t *)addr);
 233         else if (size == 2)
 234                 return /* LINTED */le16toh(*(const uint16_t *)addr);
 235         else
 236                 return *addr;
 237 }
 238
 239 uint32_t
 240 cdbr_entries(struct cdbr *cdbr)
 241 {
 242
 243         return cdbr->entries;
 244 }
 245
 246 int
 247 cdbr_get(struct cdbr *cdbr, uint32_t idx, const void **data, size_t *data_len)
 248 {
 249         uint32_t start, end;
 250
 251         if (idx >= cdbr->entries) {
 252                 SET_ERRNO(EINVAL);
 253                 return -1;
 254         }
 255
 256         start = get_uintX(cdbr->offset_base, idx, cdbr->offset_size);
 257         end = get_uintX(cdbr->offset_base, idx + 1, cdbr->offset_size);
 258
 259         if (start > end) {
 260                 SET_ERRNO(EIO);
 261                 return -1;
 262         }
 263
 264         if (end > cdbr->data_size) {
 265                 SET_ERRNO(EIO);
 266                 return -1;
 267         }
 268
 269         *data = cdbr->data_base + start;
 270         *data_len = end - start;
 271
 272         return 0;
 273 }
 274
 275 int
 276 cdbr_find(struct cdbr *cdbr, const void *key, size_t key_len,
 277     const void **data, size_t *data_len)
 278 {
 279         uint32_t hashes[3], idx;
 280
 281         if (cdbr->entries_index == 0) {
 282                 SET_ERRNO(EINVAL);
 283                 return -1;
 284         }
 285
 286         mi_vector_hash(key, key_len, cdbr->seed, hashes);
 287
 288         hashes[0] = fast_remainder32(hashes[0], cdbr->entries_index,
 289             cdbr->entries_index_m, cdbr->entries_index_s1,
 290             cdbr->entries_index_s2);
 291         hashes[1] = fast_remainder32(hashes[1], cdbr->entries_index,
 292             cdbr->entries_index_m, cdbr->entries_index_s1,
 293             cdbr->entries_index_s2);
 294         hashes[2] = fast_remainder32(hashes[2], cdbr->entries_index,
 295             cdbr->entries_index_m, cdbr->entries_index_s1,
 296             cdbr->entries_index_s2);
 297
 298         idx = get_uintX(cdbr->hash_base, hashes[0], cdbr->index_size);
 299         idx += get_uintX(cdbr->hash_base, hashes[1], cdbr->index_size);
 300         idx += get_uintX(cdbr->hash_base, hashes[2], cdbr->index_size);
 301
 302         return cdbr_get(cdbr, fast_remainder32(idx, cdbr->entries,
 303             cdbr->entries_m, cdbr->entries_s1, cdbr->entries_s2), data,
 304             data_len);
 305 }
 306
 307 void
 308 cdbr_close(struct cdbr *cdbr)
 309 {
 310         if (cdbr->unmap)
 311                 (*cdbr->unmap)(cdbr->cookie, cdbr->mmap_base, cdbr->mmap_size);
 312         free(cdbr);
 313 }