libkmod/libkmod-index.h

   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 #pragma once
  22
  23 #include <stdint.h>
  24
  25 /* Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
  26    All files start with a magic number.
  27
  28    Magic spells "BOOTFAST". Second one used on newer versioned binary files.
  29  */
  30 /* #define INDEX_MAGIC_OLD 0xB007FA57 */
  31 #define INDEX_MAGIC 0xB007F457
  32
  33 /* We use a version string to keep track of changes to the binary format
  34  * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
  35  * case we ever decide to have minor changes that are not incompatible.
  36  */
  37
  38 #define INDEX_VERSION_MAJOR 0x0002
  39 #define INDEX_VERSION_MINOR 0x0001
  40 #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
  41
  42 /* The index file maps keys to values. Both keys and values are ASCII strings.
  43    Each key can have multiple values. Values are sorted by an integer priority.
  44
  45    The reader also implements a wildcard search (including range expressions)
  46    where the keys in the index are treated as patterns.
  47    This feature is required for module aliases.
  48 */
  49
  50 /* Implementation is based on a radix tree, or "trie".
  51    Each arc from parent to child is labelled with a character.
  52    Each path from the root represents a string.
  53
  54    == Example strings ==
  55
  56    ask
  57    ate
  58    on
  59    once
  60    one
  61
  62    == Key ==
  63     + Normal node
  64     * Marked node, representing a key and it's values.
  65
  66    +
  67    |-a-+-s-+-k-*
  68    |   |
  69    |   `-t-+-e-*
  70    |
  71    `-o-+-n-*-c-+-e-*
  72            |
  73            `-e-*
  74
  75    Naive implementations tend to be very space inefficient; child pointers
  76    are stored in arrays indexed by character, but most child pointers are null.
  77
  78    Our implementation uses a scheme described by Wikipedia as a Patrica trie,
  79
  80        "easiest to understand as a space-optimized trie where
  81         each node with only one child is merged with its child"
  82
  83    +
  84    |-a-+-sk-*
  85    |   |
  86    |   `-te-*
  87    |
  88    `-on-*-ce-*
  89         |
  90         `-e-*
  91
  92    We still use arrays of child pointers indexed by a single character;
  93    the remaining characters of the label are stored as a "prefix" in the child.
  94
  95    The paper describing the original Patrica trie works on individiual bits -
  96    each node has a maximum of two children, which increases space efficiency.
  97    However for this application it is simpler to use the ASCII character set.
  98    Since the index file is read-only, it can be compressed by omitting null
  99    child pointers at the start and end of arrays.
 100 */
 101
 102 #define INDEX_PRIORITY_MIN UINT32_MAX
 103
 104 struct index_value {
 105         struct index_value *next;
 106         unsigned int priority;
 107         unsigned int len;
 108         char value[0];
 109 };
 110
 111 /* In-memory index (depmod only) */
 112 struct index_file;
 113 struct index_file *index_file_open(const char *filename);
 114 void index_file_close(struct index_file *idx);
 115 char *index_search(struct index_file *idx, const char *key);
 116 void index_dump(struct index_file *in, int fd, const char *prefix);
 117 struct index_value *index_searchwild(struct index_file *idx, const char *key);
 118
 119 void index_values_free(struct index_value *values);
 120
 121 /* Implementation using mmap */
 122 struct index_mm;
 123 struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename,
 124                                                 unsigned long long *stamp);
 125 void index_mm_close(struct index_mm *index);
 126 char *index_mm_search(struct index_mm *idx, const char *key);
 127 struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key);
 128 void index_mm_dump(struct index_mm *idx, int fd, const char *prefix);