libkmod/libkmod-index.h

   1 /*
   2  * libkmod - interface to kernel module operations
   3  *
   4  * Copyright (C) 2008  Alan Jenkins <alan.christopher.jenkins@googlemail.com>
   5  * Copyright (C) 2011  ProFUSION embedded systems
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation version 2.1.
  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 #ifndef _LIBKMOD_INDEX_H
  22 #define _LIBKMOD_INDEX_H
  23
  24 #include <stdint.h>
  25
  26 /* Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
  27    All files start with a magic number.
  28
  29    Magic spells "BOOTFAST". Second one used on newer versioned binary files.
  30  */
  31 /* #define INDEX_MAGIC_OLD 0xB007FA57 */
  32 #define INDEX_MAGIC 0xB007F457
  33
  34 /* We use a version string to keep track of changes to the binary format
  35  * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
  36  * case we ever decide to have minor changes that are not incompatible.
  37  */
  38
  39 #define INDEX_VERSION_MAJOR 0x0002
  40 #define INDEX_VERSION_MINOR 0x0001
  41 #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
  42
  43 /* The index file maps keys to values. Both keys and values are ASCII strings.
  44    Each key can have multiple values. Values are sorted by an integer priority.
  45
  46    The reader also implements a wildcard search (including range expressions)
  47    where the keys in the index are treated as patterns.
  48    This feature is required for module aliases.
  49 */
  50
  51 /* Implementation is based on a radix tree, or "trie".
  52    Each arc from parent to child is labelled with a character.
  53    Each path from the root represents a string.
  54
  55    == Example strings ==
  56
  57    ask
  58    ate
  59    on
  60    once
  61    one
  62
  63    == Key ==
  64     + Normal node
  65     * Marked node, representing a key and it's values.
  66
  67    +
  68    |-a-+-s-+-k-*
  69    |   |
  70    |   `-t-+-e-*
  71    |
  72    `-o-+-n-*-c-+-e-*
  73            |
  74            `-e-*
  75
  76    Naive implementations tend to be very space inefficient; child pointers
  77    are stored in arrays indexed by character, but most child pointers are null.
  78
  79    Our implementation uses a scheme described by Wikipedia as a Patrica trie,
  80
  81        "easiest to understand as a space-optimized trie where
  82         each node with only one child is merged with its child"
  83
  84    +
  85    |-a-+-sk-*
  86    |   |
  87    |   `-te-*
  88    |
  89    `-on-*-ce-*
  90         |
  91         `-e-*
  92
  93    We still use arrays of child pointers indexed by a single character;
  94    the remaining characters of the label are stored as a "prefix" in the child.
  95
  96    The paper describing the original Patrica trie works on individiual bits -
  97    each node has a maximum of two children, which increases space efficiency.
  98    However for this application it is simpler to use the ASCII character set.
  99    Since the index file is read-only, it can be compressed by omitting null
 100    child pointers at the start and end of arrays.
 101 */
 102
 103 #define INDEX_PRIORITY_MIN UINT32_MAX
 104
 105 struct index_value {
 106         struct index_value *next;
 107         unsigned int priority;
 108         unsigned int len;
 109         char value[0];
 110 };
 111
 112 /* In-memory index (depmod only) */
 113
 114 #define INDEX_CHILDMAX 128
 115 struct index_node {
 116         char *prefix;           /* path compression */
 117         struct index_value *values;
 118         unsigned char first;    /* range of child nodes */
 119         unsigned char last;
 120         struct index_node *children[INDEX_CHILDMAX]; /* indexed by character */
 121 };
 122
 123 /* Disk format:
 124
 125    uint32_t magic = INDEX_MAGIC;
 126    uint32_t version = INDEX_VERSION;
 127    uint32_t root_offset;
 128
 129    (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
 130
 131         char[] prefix; // nul terminated
 132
 133         char first;
 134         char last;
 135         uint32_t children[last - first + 1];
 136
 137         uint32_t value_count;
 138         struct {
 139             uint32_t priority;
 140             char[] value; // nul terminated
 141         } values[value_count];
 142
 143    (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
 144    Empty prefixes are omitted, leaf nodes omit the three child-related fields.
 145
 146    This could be optimised further by adding a sparse child format
 147    (indicated using a new flag).
 148  */
 149
 150 /* Format of node offsets within index file */
 151 enum node_offset {
 152         INDEX_NODE_FLAGS    = 0xF0000000, /* Flags in high nibble */
 153         INDEX_NODE_PREFIX   = 0x80000000,
 154         INDEX_NODE_VALUES = 0x40000000,
 155         INDEX_NODE_CHILDS   = 0x20000000,
 156
 157         INDEX_NODE_MASK     = 0x0FFFFFFF, /* Offset value */
 158 };
 159
 160 struct index_file;
 161 struct index_file *index_file_open(const char *filename);
 162 void index_file_close(struct index_file *idx);
 163 char *index_search(struct index_file *idx, const char *key);
 164 struct index_value *index_searchwild(struct index_file *idx, const char *key);
 165
 166 void index_values_free(struct index_value *values);
 167
 168 /* Implementation using mmap */
 169 struct index_mm;
 170 struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename,
 171                                                                 bool populate);
 172 void index_mm_close(struct index_mm *index);
 173 char *index_mm_search(struct index_mm *idx, const char *key);
 174 struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key);
 175
 176 #endif