libkmod/libkmod-index.c

   1 /*
   2  * libkmod - interface to kernel module operations
   3  *
   4  * Copyright (C) 2011-2013  ProFUSION embedded systems
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  */
  20
  21 #include <arpa/inet.h>
  22 #include <assert.h>
  23 #include <errno.h>
  24 #include <fnmatch.h>
  25 #include <inttypes.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #include <shared/macro.h>
  31 #include <shared/util.h>
  32
  33 #include "libkmod-internal.h"
  34 #include "libkmod-index.h"
  35
  36 /* index.c: module index file shared functions for modprobe and depmod */
  37
  38 #define INDEX_CHILDMAX 128
  39
  40 /* Disk format:
  41
  42    uint32_t magic = INDEX_MAGIC;
  43    uint32_t version = INDEX_VERSION;
  44    uint32_t root_offset;
  45
  46    (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
  47
  48         char[] prefix; // nul terminated
  49
  50         char first;
  51         char last;
  52         uint32_t children[last - first + 1];
  53
  54         uint32_t value_count;
  55         struct {
  56             uint32_t priority;
  57             char[] value; // nul terminated
  58         } values[value_count];
  59
  60    (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
  61    Empty prefixes are omitted, leaf nodes omit the three child-related fields.
  62
  63    This could be optimised further by adding a sparse child format
  64    (indicated using a new flag).
  65  */
  66
  67 /* Format of node offsets within index file */
  68 enum node_offset {
  69         INDEX_NODE_FLAGS    = 0xF0000000, /* Flags in high nibble */
  70         INDEX_NODE_PREFIX   = 0x80000000,
  71         INDEX_NODE_VALUES = 0x40000000,
  72         INDEX_NODE_CHILDS   = 0x20000000,
  73
  74         INDEX_NODE_MASK     = 0x0FFFFFFF, /* Offset value */
  75 };
  76
  77 void index_values_free(struct index_value *values)
  78 {
  79         while (values) {
  80                 struct index_value *value = values;
  81
  82                 values = value->next;
  83                 free(value);
  84         }
  85 }
  86
  87 static int add_value(struct index_value **values,
  88                      const char *value, unsigned len, unsigned int priority)
  89 {
  90         struct index_value *v;
  91
  92         /* find position to insert value */
  93         while (*values && (*values)->priority < priority)
  94                 values = &(*values)->next;
  95
  96         v = malloc(sizeof(struct index_value) + len + 1);
  97         if (!v)
  98                 return -1;
  99         v->next = *values;
 100         v->priority = priority;
 101         v->len = len;
 102         memcpy(v->value, value, len);
 103         v->value[len] = '\0';
 104         *values = v;
 105
 106         return 0;
 107 }
 108
 109 static void read_error(void)
 110 {
 111         fatal("Module index: unexpected error: %s\n"
 112                         "Try re-running depmod\n", errno ? strerror(errno) : "EOF");
 113 }
 114
 115 static int read_char(FILE *in)
 116 {
 117         int ch;
 118
 119         errno = 0;
 120         ch = getc_unlocked(in);
 121         if (ch == EOF)
 122                 read_error();
 123         return ch;
 124 }
 125
 126 static uint32_t read_long(FILE *in)
 127 {
 128         uint32_t l;
 129
 130         errno = 0;
 131         if (fread(&l, sizeof(uint32_t), 1, in) != sizeof(uint32_t))
 132                 read_error();
 133         return ntohl(l);
 134 }
 135
 136 /*
 137  * Buffer abstract data type
 138  *
 139  * Used internally to store the current path during tree traversal.
 140  * They help build wildcard key strings to pass to fnmatch(),
 141  * as well as building values of matching keys.
 142  */
 143 struct buffer {
 144         char *bytes;
 145         unsigned size;
 146         unsigned used;
 147 };
 148
 149 #define BUF_STEP (2048)
 150 static bool buf_grow(struct buffer *buf, size_t newsize)
 151 {
 152         void *tmp;
 153         size_t sz;
 154
 155         if (newsize % BUF_STEP == 0)
 156                 sz = newsize;
 157         else
 158                 sz = ((newsize / BUF_STEP) + 1) * BUF_STEP;
 159
 160         if (buf->size == sz)
 161                 return true;
 162
 163         tmp = realloc(buf->bytes, sz);
 164         if (sz > 0 && tmp == NULL)
 165                 return false;
 166         buf->bytes = tmp;
 167         buf->size = sz;
 168         return true;
 169 }
 170
 171 static void buf_init(struct buffer *buf)
 172 {
 173         buf->bytes = NULL;
 174         buf->size = 0;
 175         buf->used = 0;
 176 }
 177
 178 static void buf_release(struct buffer *buf)
 179 {
 180         free(buf->bytes);
 181 }
 182
 183 /* Destroy buffer and return a copy as a C string */
 184 static char *buf_steal(struct buffer *buf)
 185 {
 186         char *bytes;
 187
 188         bytes = realloc(buf->bytes, buf->used + 1);
 189         if (!bytes) {
 190                 free(buf->bytes);
 191                 return NULL;
 192         }
 193         bytes[buf->used] = '\0';
 194         return bytes;
 195 }
 196
 197 /* Return a C string owned by the buffer
 198    (invalidated if the buffer is changed).
 199  */
 200 static const char *buf_str(struct buffer *buf)
 201 {
 202         if (!buf_grow(buf, buf->used + 1))
 203                 return NULL;
 204         buf->bytes[buf->used] = '\0';
 205         return buf->bytes;
 206 }
 207
 208 static bool buf_pushchar(struct buffer *buf, char ch)
 209 {
 210         if (!buf_grow(buf, buf->used + 1))
 211                 return false;
 212         buf->bytes[buf->used] = ch;
 213         buf->used++;
 214         return true;
 215 }
 216
 217 static unsigned buf_pushchars(struct buffer *buf, const char *str)
 218 {
 219         unsigned i = 0;
 220         int ch;
 221
 222         while ((ch = str[i])) {
 223                 buf_pushchar(buf, ch);
 224                 i++;
 225         }
 226
 227         return i;
 228 }
 229
 230 static unsigned buf_freadchars(struct buffer *buf, FILE *in)
 231 {
 232         unsigned i = 0;
 233         int ch;
 234
 235         while ((ch = read_char(in))) {
 236                 if (!buf_pushchar(buf, ch))
 237                         break;
 238                 i++;
 239         }
 240
 241         return i;
 242 }
 243
 244 static void buf_popchar(struct buffer *buf)
 245 {
 246         assert(buf->used > 0);
 247         buf->used--;
 248 }
 249
 250 static void buf_popchars(struct buffer *buf, unsigned n)
 251 {
 252         assert(buf->used >= n);
 253         buf->used -= n;
 254 }
 255
 256 static void buf_clear(struct buffer *buf)
 257 {
 258         buf->used = 0;
 259 }
 260
 261 /*
 262  * Index file searching
 263  */
 264 struct index_node_f {
 265         FILE *file;
 266         char *prefix;           /* path compression */
 267         struct index_value *values;
 268         unsigned char first;    /* range of child nodes */
 269         unsigned char last;
 270         uint32_t children[0];
 271 };
 272
 273 static struct index_node_f *index_read(FILE *in, uint32_t offset)
 274 {
 275         struct index_node_f *node;
 276         char *prefix;
 277         int i, child_count = 0;
 278
 279         if ((offset & INDEX_NODE_MASK) == 0)
 280                 return NULL;
 281
 282         fseek(in, offset & INDEX_NODE_MASK, SEEK_SET);
 283
 284         if (offset & INDEX_NODE_PREFIX) {
 285                 struct buffer buf;
 286                 buf_init(&buf);
 287                 buf_freadchars(&buf, in);
 288                 prefix = buf_steal(&buf);
 289         } else
 290                 prefix = NOFAIL(strdup(""));
 291
 292         if (offset & INDEX_NODE_CHILDS) {
 293                 char first = read_char(in);
 294                 char last = read_char(in);
 295                 child_count = last - first + 1;
 296
 297                 node = NOFAIL(malloc(sizeof(struct index_node_f) +
 298                                      sizeof(uint32_t) * child_count));
 299
 300                 node->first = first;
 301                 node->last = last;
 302
 303                 for (i = 0; i < child_count; i++)
 304                         node->children[i] = read_long(in);
 305         } else {
 306                 node = NOFAIL(malloc(sizeof(struct index_node_f)));
 307                 node->first = INDEX_CHILDMAX;
 308                 node->last = 0;
 309         }
 310
 311         node->values = NULL;
 312         if (offset & INDEX_NODE_VALUES) {
 313                 int value_count;
 314                 struct buffer buf;
 315                 const char *value;
 316                 unsigned int priority;
 317
 318                 value_count = read_long(in);
 319
 320                 buf_init(&buf);
 321                 while (value_count--) {
 322                         priority = read_long(in);
 323                         buf_freadchars(&buf, in);
 324                         value = buf_str(&buf);
 325                         add_value(&node->values, value, buf.used, priority);
 326                         buf_clear(&buf);
 327                 }
 328                 buf_release(&buf);
 329         }
 330
 331         node->prefix = prefix;
 332         node->file = in;
 333         return node;
 334 }
 335
 336 static void index_close(struct index_node_f *node)
 337 {
 338         free(node->prefix);
 339         index_values_free(node->values);
 340         free(node);
 341 }
 342
 343 struct index_file {
 344         FILE *file;
 345         uint32_t root_offset;
 346 };
 347
 348 /* Failures are silent; modprobe will fall back to text files */
 349 struct index_file *index_file_open(const char *filename)
 350 {
 351         FILE *file;
 352         uint32_t magic, version;
 353         struct index_file *new;
 354
 355         file = fopen(filename, "re");
 356         if (!file)
 357                 return NULL;
 358         errno = EINVAL;
 359
 360         magic = read_long(file);
 361         if (magic != INDEX_MAGIC) {
 362                 fclose(file);
 363                 return NULL;
 364         }
 365
 366         version = read_long(file);
 367         if (version >> 16 != INDEX_VERSION_MAJOR) {
 368                 fclose(file);
 369                 return NULL;
 370         }
 371
 372         new = NOFAIL(malloc(sizeof(struct index_file)));
 373         new->file = file;
 374         new->root_offset = read_long(new->file);
 375
 376         errno = 0;
 377         return new;
 378 }
 379
 380 void index_file_close(struct index_file *idx)
 381 {
 382         fclose(idx->file);
 383         free(idx);
 384 }
 385
 386 static struct index_node_f *index_readroot(struct index_file *in)
 387 {
 388         return index_read(in->file, in->root_offset);
 389 }
 390
 391 static struct index_node_f *index_readchild(const struct index_node_f *parent,
 392                                             int ch)
 393 {
 394         if (parent->first <= ch && ch <= parent->last) {
 395                 return index_read(parent->file,
 396                                        parent->children[ch - parent->first]);
 397         }
 398
 399         return NULL;
 400 }
 401
 402 static void index_dump_node(struct index_node_f *node, struct buffer *buf,
 403                                                                 int fd)
 404 {
 405         struct index_value *v;
 406         int ch, pushed;
 407
 408         pushed = buf_pushchars(buf, node->prefix);
 409
 410         for (v = node->values; v != NULL; v = v->next) {
 411                 write_str_safe(fd, buf->bytes, buf->used);
 412                 write_str_safe(fd, " ", 1);
 413                 write_str_safe(fd, v->value, strlen(v->value));
 414                 write_str_safe(fd, "\n", 1);
 415         }
 416
 417         for (ch = node->first; ch <= node->last; ch++) {
 418                 struct index_node_f *child = index_readchild(node, ch);
 419
 420                 if (!child)
 421                         continue;
 422
 423                 buf_pushchar(buf, ch);
 424                 index_dump_node(child, buf, fd);
 425                 buf_popchar(buf);
 426         }
 427
 428         buf_popchars(buf, pushed);
 429         index_close(node);
 430 }
 431
 432 void index_dump(struct index_file *in, int fd, const char *prefix)
 433 {
 434         struct index_node_f *root;
 435         struct buffer buf;
 436
 437         root = index_readroot(in);
 438         if (root == NULL)
 439                 return;
 440
 441         buf_init(&buf);
 442         buf_pushchars(&buf, prefix);
 443         index_dump_node(root, &buf, fd);
 444         buf_release(&buf);
 445 }
 446
 447 static char *index_search__node(struct index_node_f *node, const char *key, int i)
 448 {
 449         char *value;
 450         struct index_node_f *child;
 451         int ch;
 452         int j;
 453
 454         while(node) {
 455                 for (j = 0; node->prefix[j]; j++) {
 456                         ch = node->prefix[j];
 457
 458                         if (ch != key[i+j]) {
 459                                 index_close(node);
 460                                 return NULL;
 461                         }
 462                 }
 463
 464                 i += j;
 465
 466                 if (key[i] == '\0') {
 467                         value = node->values != NULL
 468                                 ? strdup(node->values[0].value)
 469                                 : NULL;
 470
 471                         index_close(node);
 472                         return value;
 473                 }
 474
 475                 child = index_readchild(node, key[i]);
 476                 index_close(node);
 477                 node = child;
 478                 i++;
 479         }
 480
 481         return NULL;
 482 }
 483
 484 /*
 485  * Search the index for a key
 486  *
 487  * Returns the value of the first match
 488  *
 489  * The recursive functions free their node argument (using index_close).
 490  */
 491 char *index_search(struct index_file *in, const char *key)
 492 {
 493 // FIXME: return value by reference instead of strdup
 494         struct index_node_f *root;
 495         char *value;
 496
 497         root = index_readroot(in);
 498         value = index_search__node(root, key, 0);
 499
 500         return value;
 501 }
 502
 503
 504
 505 /* Level 4: add all the values from a matching node */
 506 static void index_searchwild__allvalues(struct index_node_f *node,
 507                                         struct index_value **out)
 508 {
 509         struct index_value *v;
 510
 511         for (v = node->values; v != NULL; v = v->next)
 512                 add_value(out, v->value, v->len, v->priority);
 513
 514         index_close(node);
 515 }
 516
 517 /*
 518  * Level 3: traverse a sub-keyspace which starts with a wildcard,
 519  * looking for matches.
 520  */
 521 static void index_searchwild__all(struct index_node_f *node, int j,
 522                                   struct buffer *buf,
 523                                   const char *subkey,
 524                                   struct index_value **out)
 525 {
 526         int pushed = 0;
 527         int ch;
 528
 529         while (node->prefix[j]) {
 530                 ch = node->prefix[j];
 531
 532                 buf_pushchar(buf, ch);
 533                 pushed++;
 534                 j++;
 535         }
 536
 537         for (ch = node->first; ch <= node->last; ch++) {
 538                 struct index_node_f *child = index_readchild(node, ch);
 539
 540                 if (!child)
 541                         continue;
 542
 543                 buf_pushchar(buf, ch);
 544                 index_searchwild__all(child, 0, buf, subkey, out);
 545                 buf_popchar(buf);
 546         }
 547
 548         if (node->values) {
 549                 if (fnmatch(buf_str(buf), subkey, 0) == 0)
 550                         index_searchwild__allvalues(node, out);
 551                 else
 552                         index_close(node);
 553         } else {
 554                 index_close(node);
 555         }
 556
 557         buf_popchars(buf, pushed);
 558 }
 559
 560 /* Level 2: descend the tree (until we hit a wildcard) */
 561 static void index_searchwild__node(struct index_node_f *node,
 562                                    struct buffer *buf,
 563                                    const char *key, int i,
 564                                    struct index_value **out)
 565 {
 566         struct index_node_f *child;
 567         int j;
 568         int ch;
 569
 570         while(node) {
 571                 for (j = 0; node->prefix[j]; j++) {
 572                         ch = node->prefix[j];
 573
 574                         if (ch == '*' || ch == '?' || ch == '[') {
 575                                 index_searchwild__all(node, j, buf,
 576                                                       &key[i+j], out);
 577                                 return;
 578                         }
 579
 580                         if (ch != key[i+j]) {
 581                                 index_close(node);
 582                                 return;
 583                         }
 584                 }
 585
 586                 i += j;
 587
 588                 child = index_readchild(node, '*');
 589                 if (child) {
 590                         buf_pushchar(buf, '*');
 591                         index_searchwild__all(child, 0, buf, &key[i], out);
 592                         buf_popchar(buf);
 593                 }
 594
 595                 child = index_readchild(node, '?');
 596                 if (child) {
 597                         buf_pushchar(buf, '?');
 598                         index_searchwild__all(child, 0, buf, &key[i], out);
 599                         buf_popchar(buf);
 600                 }
 601
 602                 child = index_readchild(node, '[');
 603                 if (child) {
 604                         buf_pushchar(buf, '[');
 605                         index_searchwild__all(child, 0, buf, &key[i], out);
 606                         buf_popchar(buf);
 607                 }
 608
 609                 if (key[i] == '\0') {
 610                         index_searchwild__allvalues(node, out);
 611
 612                         return;
 613                 }
 614
 615                 child = index_readchild(node, key[i]);
 616                 index_close(node);
 617                 node = child;
 618                 i++;
 619         }
 620 }
 621
 622 /*
 623  * Search the index for a key.  The index may contain wildcards.
 624  *
 625  * Returns a list of all the values of matching keys.
 626  */
 627 struct index_value *index_searchwild(struct index_file *in, const char *key)
 628 {
 629         struct index_node_f *root = index_readroot(in);
 630         struct buffer buf;
 631         struct index_value *out = NULL;
 632
 633         buf_init(&buf);
 634         index_searchwild__node(root, &buf, key, 0, &out);
 635         buf_release(&buf);
 636         return out;
 637 }
 638
 639 #include <sys/mman.h>
 640 #include <sys/stat.h>
 641 #include <unistd.h>
 642
 643 static const char _idx_empty_str[] = "";
 644
 645 /**************************************************************************/
 646 /*
 647  * Alternative implementation, using mmap to map all the file to memory when
 648  * starting
 649  */
 650 struct index_mm {
 651         struct kmod_ctx *ctx;
 652         void *mm;
 653         uint32_t root_offset;
 654         size_t size;
 655 };
 656
 657 struct index_mm_value {
 658         unsigned int priority;
 659         unsigned int len;
 660         const char *value;
 661 };
 662
 663 struct index_mm_value_array {
 664         struct index_mm_value *values;
 665         unsigned int len;
 666 };
 667
 668 struct index_mm_node {
 669         struct index_mm *idx;
 670         const char *prefix; /* mmape'd value */
 671         struct index_mm_value_array values;
 672         unsigned char first;
 673         unsigned char last;
 674         uint32_t children[];
 675 };
 676
 677 static inline uint32_t read_long_mm(void **p)
 678 {
 679         uint8_t *addr = *(uint8_t **)p;
 680         uint32_t v;
 681
 682         /* addr may be unalined to uint32_t */
 683         v = get_unaligned((uint32_t *) addr);
 684
 685         *p = addr + sizeof(uint32_t);
 686         return ntohl(v);
 687 }
 688
 689 static inline uint8_t read_char_mm(void **p)
 690 {
 691         uint8_t *addr = *(uint8_t **)p;
 692         uint8_t v = *addr;
 693         *p = addr + sizeof(uint8_t);
 694         return v;
 695 }
 696
 697 static inline char *read_chars_mm(void **p, unsigned *rlen)
 698 {
 699         char *addr = *(char **)p;
 700         size_t len = *rlen = strlen(addr);
 701         *p = addr + len + 1;
 702         return addr;
 703 }
 704
 705 static struct index_mm_node *index_mm_read_node(struct index_mm *idx,
 706                                                         uint32_t offset) {
 707         void *p = idx->mm;
 708         struct index_mm_node *node;
 709         const char *prefix;
 710         int i, child_count, value_count, children_padding;
 711         uint32_t children[INDEX_CHILDMAX];
 712         char first, last;
 713
 714         if ((offset & INDEX_NODE_MASK) == 0)
 715                 return NULL;
 716
 717         p = (char *)p + (offset & INDEX_NODE_MASK);
 718
 719         if (offset & INDEX_NODE_PREFIX) {
 720                 unsigned len;
 721                 prefix = read_chars_mm(&p, &len);
 722         } else
 723                 prefix = _idx_empty_str;
 724
 725         if (offset & INDEX_NODE_CHILDS) {
 726                 first = read_char_mm(&p);
 727                 last = read_char_mm(&p);
 728                 child_count = last - first + 1;
 729                 for (i = 0; i < child_count; i++)
 730                         children[i] = read_long_mm(&p);
 731         } else {
 732                 first = INDEX_CHILDMAX;
 733                 last = 0;
 734                 child_count = 0;
 735         }
 736
 737         children_padding = (sizeof(struct index_mm_node) +
 738                             (sizeof(uint32_t) * child_count)) % sizeof(void *);
 739
 740         if (offset & INDEX_NODE_VALUES)
 741                 value_count = read_long_mm(&p);
 742         else
 743                 value_count = 0;
 744
 745         node = malloc(sizeof(struct index_mm_node)
 746                       + sizeof(uint32_t) * child_count + children_padding
 747                       + sizeof(struct index_mm_value) * value_count);
 748         if (node == NULL)
 749                 return NULL;
 750
 751         node->idx = idx;
 752         node->prefix = prefix;
 753         if (value_count == 0)
 754                 node->values.values = NULL;
 755         else {
 756                 node->values.values = (struct index_mm_value *)
 757                         ((char *)node + sizeof(struct index_mm_node) +
 758                          sizeof(uint32_t) * child_count + children_padding);
 759         }
 760         node->values.len = value_count;
 761         node->first = first;
 762         node->last = last;
 763         memcpy(node->children, children, sizeof(uint32_t) * child_count);
 764
 765         for (i = 0; i < value_count; i++) {
 766                 struct index_mm_value *v = node->values.values + i;
 767                 v->priority = read_long_mm(&p);
 768                 v->value = read_chars_mm(&p, &v->len);
 769         }
 770
 771         return node;
 772 }
 773
 774 static void index_mm_free_node(struct index_mm_node *node)
 775 {
 776         free(node);
 777 }
 778
 779 struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename,
 780                                                 unsigned long long *stamp)
 781 {
 782         int fd;
 783         struct stat st;
 784         struct index_mm *idx;
 785         struct {
 786                 uint32_t magic;
 787                 uint32_t version;
 788                 uint32_t root_offset;
 789         } hdr;
 790         void *p;
 791
 792         DBG(ctx, "file=%s\n", filename);
 793
 794         idx = malloc(sizeof(*idx));
 795         if (idx == NULL) {
 796                 ERR(ctx, "malloc: %m\n");
 797                 return NULL;
 798         }
 799
 800         if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
 801                 DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename);
 802                 goto fail_open;
 803         }
 804
 805         if (fstat(fd, &st) < 0)
 806                 goto fail_nommap;
 807         if ((size_t) st.st_size < sizeof(hdr))
 808                 goto fail_nommap;
 809
 810         if ((idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0))
 811                                                         == MAP_FAILED) {
 812                 ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n",
 813                                                         st.st_size, fd);
 814                 goto fail_nommap;
 815         }
 816
 817         p = idx->mm;
 818         hdr.magic = read_long_mm(&p);
 819         hdr.version = read_long_mm(&p);
 820         hdr.root_offset = read_long_mm(&p);
 821
 822         if (hdr.magic != INDEX_MAGIC) {
 823                 ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic,
 824                                                                 INDEX_MAGIC);
 825                 goto fail;
 826         }
 827
 828         if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
 829                 ERR(ctx, "major version check fail: %u instead of %u\n",
 830                                         hdr.version >> 16, INDEX_VERSION_MAJOR);
 831                 goto fail;
 832         }
 833
 834         idx->root_offset = hdr.root_offset;
 835         idx->size = st.st_size;
 836         idx->ctx = ctx;
 837         close(fd);
 838
 839         *stamp = stat_mstamp(&st);
 840
 841         return idx;
 842
 843 fail:
 844         munmap(idx->mm, st.st_size);
 845 fail_nommap:
 846         close(fd);
 847 fail_open:
 848         free(idx);
 849         return NULL;
 850 }
 851
 852 void index_mm_close(struct index_mm *idx)
 853 {
 854         munmap(idx->mm, idx->size);
 855         free(idx);
 856 }
 857
 858 static struct index_mm_node *index_mm_readroot(struct index_mm *idx)
 859 {
 860         return index_mm_read_node(idx, idx->root_offset);
 861 }
 862
 863 static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent,
 864                                                                         int ch)
 865 {
 866         if (parent->first <= ch && ch <= parent->last) {
 867                 return index_mm_read_node(parent->idx,
 868                                         parent->children[ch - parent->first]);
 869         }
 870
 871         return NULL;
 872 }
 873
 874 static void index_mm_dump_node(struct index_mm_node *node, struct buffer *buf,
 875                                                                 int fd)
 876 {
 877         struct index_mm_value *itr, *itr_end;
 878         int ch, pushed;
 879
 880         pushed = buf_pushchars(buf, node->prefix);
 881
 882         itr = node->values.values;
 883         itr_end = itr + node->values.len;
 884         for (; itr < itr_end; itr++) {
 885                 write_str_safe(fd, buf->bytes, buf->used);
 886                 write_str_safe(fd, " ", 1);
 887                 write_str_safe(fd, itr->value, itr->len);
 888                 write_str_safe(fd, "\n", 1);
 889         }
 890
 891         for (ch = node->first; ch <= node->last; ch++) {
 892                 struct index_mm_node *child = index_mm_readchild(node, ch);
 893
 894                 if (child == NULL)
 895                         continue;
 896
 897                 buf_pushchar(buf, ch);
 898                 index_mm_dump_node(child, buf, fd);
 899                 buf_popchar(buf);
 900         }
 901
 902         buf_popchars(buf, pushed);
 903         index_mm_free_node(node);
 904 }
 905
 906 void index_mm_dump(struct index_mm *idx, int fd, const char *prefix)
 907 {
 908         struct index_mm_node *root;
 909         struct buffer buf;
 910
 911         root = index_mm_readroot(idx);
 912         if (root == NULL)
 913                 return;
 914
 915         buf_init(&buf);
 916         buf_pushchars(&buf, prefix);
 917         index_mm_dump_node(root, &buf, fd);
 918         buf_release(&buf);
 919 }
 920
 921 static char *index_mm_search_node(struct index_mm_node *node, const char *key,
 922                                                                         int i)
 923 {
 924         char *value;
 925         struct index_mm_node *child;
 926         int ch;
 927         int j;
 928
 929         while(node) {
 930                 for (j = 0; node->prefix[j]; j++) {
 931                         ch = node->prefix[j];
 932
 933                         if (ch != key[i+j]) {
 934                                 index_mm_free_node(node);
 935                                 return NULL;
 936                         }
 937                 }
 938
 939                 i += j;
 940
 941                 if (key[i] == '\0') {
 942                         value = node->values.len > 0
 943                                 ? strdup(node->values.values[0].value)
 944                                 : NULL;
 945
 946                         index_mm_free_node(node);
 947                         return value;
 948                 }
 949
 950                 child = index_mm_readchild(node, key[i]);
 951                 index_mm_free_node(node);
 952                 node = child;
 953                 i++;
 954         }
 955
 956         return NULL;
 957 }
 958
 959 /*
 960  * Search the index for a key
 961  *
 962  * Returns the value of the first match
 963  *
 964  * The recursive functions free their node argument (using index_close).
 965  */
 966 char *index_mm_search(struct index_mm *idx, const char *key)
 967 {
 968 // FIXME: return value by reference instead of strdup
 969         struct index_mm_node *root;
 970         char *value;
 971
 972         root = index_mm_readroot(idx);
 973         value = index_mm_search_node(root, key, 0);
 974
 975         return value;
 976 }
 977
 978 /* Level 4: add all the values from a matching node */
 979 static void index_mm_searchwild_allvalues(struct index_mm_node *node,
 980                                                 struct index_value **out)
 981 {
 982         struct index_mm_value *itr, *itr_end;
 983
 984         itr = node->values.values;
 985         itr_end = itr + node->values.len;
 986         for (; itr < itr_end; itr++)
 987                 add_value(out, itr->value, itr->len, itr->priority);
 988
 989         index_mm_free_node(node);
 990 }
 991
 992 /*
 993  * Level 3: traverse a sub-keyspace which starts with a wildcard,
 994  * looking for matches.
 995  */
 996 static void index_mm_searchwild_all(struct index_mm_node *node, int j,
 997                                           struct buffer *buf,
 998                                           const char *subkey,
 999                                           struct index_value **out)
1000 {
1001         int pushed = 0;
1002         int ch;
1003
1004         while (node->prefix[j]) {
1005                 ch = node->prefix[j];
1006
1007                 buf_pushchar(buf, ch);
1008                 pushed++;
1009                 j++;
1010         }
1011
1012         for (ch = node->first; ch <= node->last; ch++) {
1013                 struct index_mm_node *child = index_mm_readchild(node, ch);
1014
1015                 if (!child)
1016                         continue;
1017
1018                 buf_pushchar(buf, ch);
1019                 index_mm_searchwild_all(child, 0, buf, subkey, out);
1020                 buf_popchar(buf);
1021         }
1022
1023         if (node->values.len > 0) {
1024                 if (fnmatch(buf_str(buf), subkey, 0) == 0)
1025                         index_mm_searchwild_allvalues(node, out);
1026                 else
1027                         index_mm_free_node(node);
1028         } else {
1029                 index_mm_free_node(node);
1030         }
1031
1032         buf_popchars(buf, pushed);
1033 }
1034
1035 /* Level 2: descend the tree (until we hit a wildcard) */
1036 static void index_mm_searchwild_node(struct index_mm_node *node,
1037                                            struct buffer *buf,
1038                                            const char *key, int i,
1039                                            struct index_value **out)
1040 {
1041         struct index_mm_node *child;
1042         int j;
1043         int ch;
1044
1045         while(node) {
1046                 for (j = 0; node->prefix[j]; j++) {
1047                         ch = node->prefix[j];
1048
1049                         if (ch == '*' || ch == '?' || ch == '[') {
1050                                 index_mm_searchwild_all(node, j, buf,
1051                                                       &key[i+j], out);
1052                                 return;
1053                         }
1054
1055                         if (ch != key[i+j]) {
1056                                 index_mm_free_node(node);
1057                                 return;
1058                         }
1059                 }
1060
1061                 i += j;
1062
1063                 child = index_mm_readchild(node, '*');
1064                 if (child) {
1065                         buf_pushchar(buf, '*');
1066                         index_mm_searchwild_all(child, 0, buf, &key[i], out);
1067                         buf_popchar(buf);
1068                 }
1069
1070                 child = index_mm_readchild(node, '?');
1071                 if (child) {
1072                         buf_pushchar(buf, '?');
1073                         index_mm_searchwild_all(child, 0, buf, &key[i], out);
1074                         buf_popchar(buf);
1075                 }
1076
1077                 child = index_mm_readchild(node, '[');
1078                 if (child) {
1079                         buf_pushchar(buf, '[');
1080                         index_mm_searchwild_all(child, 0, buf, &key[i], out);
1081                         buf_popchar(buf);
1082                 }
1083
1084                 if (key[i] == '\0') {
1085                         index_mm_searchwild_allvalues(node, out);
1086
1087                         return;
1088                 }
1089
1090                 child = index_mm_readchild(node, key[i]);
1091                 index_mm_free_node(node);
1092                 node = child;
1093                 i++;
1094         }
1095 }
1096
1097 /*
1098  * Search the index for a key.  The index may contain wildcards.
1099  *
1100  * Returns a list of all the values of matching keys.
1101  */
1102 struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key)
1103 {
1104         struct index_mm_node *root = index_mm_readroot(idx);
1105         struct buffer buf;
1106         struct index_value *out = NULL;
1107
1108         buf_init(&buf);
1109         index_mm_searchwild_node(root, &buf, key, 0, &out);
1110         buf_release(&buf);
1111         return out;
1112 }