libkmod/libkmod-index.c

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