lib/libc/cdb/cdbr.c

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