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