lib/libc/cdb/cdbr.c

   1 /*      $NetBSD: cdbr.c,v 1.2 2010/06/03 12:40:52 veego 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.2 2010/06/03 12:40:52 veego Exp $");
  40
  41 #include "namespace.h"
  42
  43 #include <sys/bitops.h>
  44 #include <sys/endian.h>
  45 #include <sys/mman.h>
  46 #include <sys/stat.h>
  47 #include <cdbr.h>
  48 #include <errno.h>
  49 #include <fcntl.h>
  50 #include <inttypes.h>
  51 #include <stdlib.h>
  52 #include <string.h>
  53 #include <unistd.h>
  54
  55 #ifdef __weak_alias
  56 __weak_alias(cdbr_close,_cdbr_close)
  57 __weak_alias(cdbr_find,_cdbr_find)
  58 __weak_alias(cdbr_get,_cdbr_get)
  59 __weak_alias(cdbr_open,_cdbr_open)
  60 #endif
  61
  62 struct cdbr {
  63         uint8_t *mmap_base;
  64         size_t mmap_size;
  65
  66         uint8_t *hash_base;
  67         uint8_t *offset_base;
  68         uint8_t *data_base;
  69
  70         uint32_t data_size;
  71         uint32_t entries;
  72         uint32_t entries_index;
  73         uint32_t seed;
  74
  75         uint8_t offset_size;
  76         uint8_t index_size;
  77
  78         uint32_t entries_m;
  79         uint32_t entries_index_m;
  80         uint8_t entries_s1, entries_s2;
  81         uint8_t entries_index_s1, entries_index_s2;
  82 };
  83
  84 /* ARGSUSED */
  85 struct cdbr *
  86 cdbr_open(const char *path, int flags)
  87 {
  88         uint8_t buf[40];
  89         int fd;
  90         struct cdbr *cdbr;
  91         struct stat sb;
  92
  93         if ((fd = open(path, O_RDONLY)) == -1)
  94                 return NULL;
  95
  96         errno = EINVAL;
  97         if (fstat(fd, &sb) == -1 ||
  98             read(fd, buf, sizeof(buf)) != sizeof(buf) ||
  99             memcmp(buf, "NBCDB\n\0\001", 8) ||
 100             (cdbr = malloc(sizeof(*cdbr))) == NULL) {
 101                 close(fd);
 102                 return NULL;
 103         }
 104
 105         cdbr->data_size = le32dec(buf + 24);
 106         cdbr->entries = le32dec(buf + 28);
 107         cdbr->entries_index = le32dec(buf + 32);
 108         cdbr->seed = le32dec(buf + 36);
 109
 110         if (cdbr->data_size < 0x100)
 111                 cdbr->offset_size = 1;
 112         else if (cdbr->data_size < 0x10000)
 113                 cdbr->offset_size = 2;
 114         else
 115                 cdbr->offset_size = 4;
 116
 117         if (cdbr->entries_index < 0x100)
 118                 cdbr->index_size = 1;
 119         else if (cdbr->entries_index < 0x10000)
 120                 cdbr->index_size = 2;
 121         else
 122                 cdbr->index_size = 4;
 123
 124         cdbr->mmap_size = (size_t)sb.st_size;
 125 #ifdef __minix
 126         if(!(cdbr->mmap_base = malloc(cdbr->mmap_size))) {
 127                 free(cdbr);
 128                 return NULL;
 129         }
 130
 131         if ((size_t)read(fd, cdbr->mmap_base, cdbr->mmap_size) != cdbr->mmap_size)
 132         {
 133                 free(cdbr->mmap_base);
 134                 free(cdbr);
 135                 return NULL;
 136         }
 137 #else /* !__minix */
 138         cdbr->mmap_base = mmap(NULL, cdbr->mmap_size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0);
 139 #endif /* __minix */
 140         close(fd);
 141
 142         if (cdbr->mmap_base == MAP_FAILED) {
 143                 free(cdbr);
 144                 return NULL;
 145         }
 146
 147         cdbr->hash_base = cdbr->mmap_base + 40;
 148         cdbr->offset_base = cdbr->hash_base + cdbr->entries_index * cdbr->index_size;
 149         if (cdbr->entries_index * cdbr->index_size % cdbr->offset_size)
 150                 cdbr->offset_base += cdbr->offset_size -
 151                     cdbr->entries_index * cdbr->index_size % cdbr->offset_size;
 152         cdbr->data_base = cdbr->offset_base + (cdbr->entries + 1) * cdbr->offset_size;
 153
 154         if (cdbr->hash_base < cdbr->mmap_base ||
 155             cdbr->offset_base < cdbr->mmap_base ||
 156             cdbr->data_base < cdbr->mmap_base ||
 157             cdbr->data_base + cdbr->data_size < cdbr->mmap_base ||
 158             cdbr->data_base + cdbr->data_size >
 159             cdbr->mmap_base + cdbr->mmap_size ||
 160             cdbr->entries == 0 || cdbr->entries_index == 0) {
 161                 errno = EINVAL;
 162                 cdbr_close(cdbr);
 163                 return NULL;
 164         }
 165
 166         fast_divide32_prepare(cdbr->entries, &cdbr->entries_m,
 167             &cdbr->entries_s1, &cdbr->entries_s2);
 168         fast_divide32_prepare(cdbr->entries_index, &cdbr->entries_index_m,
 169             &cdbr->entries_index_s1, &cdbr->entries_index_s2);
 170
 171         return cdbr;
 172 }
 173
 174 static inline uint32_t
 175 get_uintX(const uint8_t *addr, uint32_t idx, int size)
 176 {
 177         addr += idx * size;
 178
 179         if (size == 4)
 180                 return /* LINTED */le32toh(*(const uint32_t *)addr);
 181         else if (size == 2)
 182                 return /* LINTED */le16toh(*(const uint16_t *)addr);
 183         else
 184                 return *addr;
 185 }
 186
 187 uint32_t
 188 cdbr_entries(struct cdbr *cdbr)
 189 {
 190
 191         return cdbr->entries;
 192 }
 193
 194 int
 195 cdbr_get(struct cdbr *cdbr, uint32_t idx, const void **data, size_t *data_len)
 196 {
 197         uint32_t start, end;
 198
 199         if (idx >= cdbr->entries) {
 200                 errno = EINVAL;
 201                 return -1;
 202         }
 203
 204         start = get_uintX(cdbr->offset_base, idx, cdbr->offset_size);
 205         end = get_uintX(cdbr->offset_base, idx + 1, cdbr->offset_size);
 206
 207         if (start > end) {
 208                 errno = EIO;
 209                 return -1;
 210         }
 211
 212         if (end > cdbr->data_size) {
 213                 errno = EIO;
 214                 return -1;
 215         }
 216
 217         *data = cdbr->data_base + start;
 218         *data_len = end - start;
 219
 220         return 0;
 221 }
 222
 223 int
 224 cdbr_find(struct cdbr *cdbr, const void *key, size_t key_len,
 225     const void **data, size_t *data_len)
 226 {
 227         uint32_t hashes[3], idx;
 228
 229         if (cdbr->entries_index == 0) {
 230                 errno = EINVAL;
 231                 return -1;
 232         }
 233
 234         mi_vector_hash(key, key_len, cdbr->seed, hashes);
 235
 236         hashes[0] = fast_remainder32(hashes[0], cdbr->entries_index,
 237             cdbr->entries_index_m, cdbr->entries_index_s1,
 238             cdbr->entries_index_s2);
 239         hashes[1] = fast_remainder32(hashes[1], cdbr->entries_index,
 240             cdbr->entries_index_m, cdbr->entries_index_s1,
 241             cdbr->entries_index_s2);
 242         hashes[2] = fast_remainder32(hashes[2], cdbr->entries_index,
 243             cdbr->entries_index_m, cdbr->entries_index_s1,
 244             cdbr->entries_index_s2);
 245
 246         idx = get_uintX(cdbr->hash_base, hashes[0], cdbr->index_size);
 247         idx += get_uintX(cdbr->hash_base, hashes[1], cdbr->index_size);
 248         idx += get_uintX(cdbr->hash_base, hashes[2], cdbr->index_size);
 249
 250         return cdbr_get(cdbr, fast_remainder32(idx, cdbr->entries,
 251             cdbr->entries_m, cdbr->entries_s1, cdbr->entries_s2), data,
 252             data_len);
 253 }
 254
 255 void
 256 cdbr_close(struct cdbr *cdbr)
 257 {
 258 #ifdef __minix
 259         free(cdbr->mmap_base);
 260 #else
 261         munmap(cdbr->mmap_base, cdbr->mmap_size);
 262 #endif
 263         free(cdbr);
 264 }