1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * lib/textsearch.c Generic text search interface 4 * 5 * Authors: Thomas Graf <tgraf@suug.ch> 6 * Pablo Neira Ayuso <pablo@netfilter.org> 7 * 8 * ========================================================================== 9 */ 10 11 /** 12 * DOC: ts_intro 13 * INTRODUCTION 14 * 15 * The textsearch infrastructure provides text searching facilities for 16 * both linear and non-linear data. Individual search algorithms are 17 * implemented in modules and chosen by the user. 18 * 19 * ARCHITECTURE 20 * 21 * .. code-block:: none 22 * 23 * User 24 * +----------------+ 25 * | finish()|<--------------(6)-----------------+ 26 * |get_next_block()|<--------------(5)---------------+ | 27 * | | Algorithm | | 28 * | | +------------------------------+ 29 * | | | init() find() destroy() | 30 * | | +------------------------------+ 31 * | | Core API ^ ^ ^ 32 * | | +---------------+ (2) (4) (8) 33 * | (1)|----->| prepare() |---+ | | 34 * | (3)|----->| find()/next() |-----------+ | 35 * | (7)|----->| destroy() |----------------------+ 36 * +----------------+ +---------------+ 37 * 38 * (1) User configures a search by calling textsearch_prepare() specifying 39 * the search parameters such as the pattern and algorithm name. 40 * (2) Core requests the algorithm to allocate and initialize a search 41 * configuration according to the specified parameters. 42 * (3) User starts the search(es) by calling textsearch_find() or 43 * textsearch_next() to fetch subsequent occurrences. A state variable 44 * is provided to the algorithm to store persistent variables. 45 * (4) Core eventually resets the search offset and forwards the find() 46 * request to the algorithm. 47 * (5) Algorithm calls get_next_block() provided by the user continuously 48 * to fetch the data to be searched in block by block. 49 * (6) Algorithm invokes finish() after the last call to get_next_block 50 * to clean up any leftovers from get_next_block. (Optional) 51 * (7) User destroys the configuration by calling textsearch_destroy(). 52 * (8) Core notifies the algorithm to destroy algorithm specific 53 * allocations. (Optional) 54 * 55 * USAGE 56 * 57 * Before a search can be performed, a configuration must be created 58 * by calling textsearch_prepare() specifying the searching algorithm, 59 * the pattern to look for and flags. As a flag, you can set TS_IGNORECASE 60 * to perform case insensitive matching. But it might slow down 61 * performance of algorithm, so you should use it at own your risk. 62 * The returned configuration may then be used for an arbitrary 63 * amount of times and even in parallel as long as a separate struct 64 * ts_state variable is provided to every instance. 65 * 66 * The actual search is performed by either calling 67 * textsearch_find_continuous() for linear data or by providing 68 * an own get_next_block() implementation and 69 * calling textsearch_find(). Both functions return 70 * the position of the first occurrence of the pattern or UINT_MAX if 71 * no match was found. Subsequent occurrences can be found by calling 72 * textsearch_next() regardless of the linearity of the data. 73 * 74 * Once you're done using a configuration it must be given back via 75 * textsearch_destroy. 76 * 77 * EXAMPLE:: 78 * 79 * int pos; 80 * struct ts_config *conf; 81 * struct ts_state state; 82 * const char *pattern = "chicken"; 83 * const char *example = "We dance the funky chicken"; 84 * 85 * conf = textsearch_prepare("kmp", pattern, strlen(pattern), 86 * GFP_KERNEL, TS_AUTOLOAD); 87 * if (IS_ERR(conf)) { 88 * err = PTR_ERR(conf); 89 * goto errout; 90 * } 91 * 92 * pos = textsearch_find_continuous(conf, &state, example, strlen(example)); 93 * if (pos != UINT_MAX) 94 * panic("Oh my god, dancing chickens at %d\n", pos); 95 * 96 * textsearch_destroy(conf); 97 */ 98 /* ========================================================================== */ 99 100 #include <linux/module.h> 101 #include <linux/types.h> 102 #include <linux/string.h> 103 #include <linux/init.h> 104 #include <linux/rculist.h> 105 #include <linux/rcupdate.h> 106 #include <linux/err.h> 107 #include <linux/textsearch.h> 108 #include <linux/slab.h> 109 110 static LIST_HEAD(ts_ops); 111 static DEFINE_SPINLOCK(ts_mod_lock); 112 113 static inline struct ts_ops *lookup_ts_algo(const char *name) 114 { 115 struct ts_ops *o; 116 117 rcu_read_lock(); 118 list_for_each_entry_rcu(o, &ts_ops, list) { 119 if (!strcmp(name, o->name)) { 120 if (!try_module_get(o->owner)) 121 o = NULL; 122 rcu_read_unlock(); 123 return o; 124 } 125 } 126 rcu_read_unlock(); 127 128 return NULL; 129 } 130 131 /** 132 * textsearch_register - register a textsearch module 133 * @ops: operations lookup table 134 * 135 * This function must be called by textsearch modules to announce 136 * their presence. The specified &@ops must have %name set to a 137 * unique identifier and the callbacks find(), init(), get_pattern(), 138 * and get_pattern_len() must be implemented. 139 * 140 * Returns 0 or -EEXISTS if another module has already registered 141 * with same name. 142 */ 143 int textsearch_register(struct ts_ops *ops) 144 { 145 int err = -EEXIST; 146 struct ts_ops *o; 147 148 if (ops->name == NULL || ops->find == NULL || ops->init == NULL || 149 ops->get_pattern == NULL || ops->get_pattern_len == NULL) 150 return -EINVAL; 151 152 spin_lock(&ts_mod_lock); 153 list_for_each_entry(o, &ts_ops, list) { 154 if (!strcmp(ops->name, o->name)) 155 goto errout; 156 } 157 158 list_add_tail_rcu(&ops->list, &ts_ops); 159 err = 0; 160 errout: 161 spin_unlock(&ts_mod_lock); 162 return err; 163 } 164 EXPORT_SYMBOL(textsearch_register); 165 166 /** 167 * textsearch_unregister - unregister a textsearch module 168 * @ops: operations lookup table 169 * 170 * This function must be called by textsearch modules to announce 171 * their disappearance for examples when the module gets unloaded. 172 * The &ops parameter must be the same as the one during the 173 * registration. 174 * 175 * Returns 0 on success or -ENOENT if no matching textsearch 176 * registration was found. 177 */ 178 int textsearch_unregister(struct ts_ops *ops) 179 { 180 int err = 0; 181 struct ts_ops *o; 182 183 spin_lock(&ts_mod_lock); 184 list_for_each_entry(o, &ts_ops, list) { 185 if (o == ops) { 186 list_del_rcu(&o->list); 187 goto out; 188 } 189 } 190 191 err = -ENOENT; 192 out: 193 spin_unlock(&ts_mod_lock); 194 return err; 195 } 196 EXPORT_SYMBOL(textsearch_unregister); 197 198 struct ts_linear_state 199 { 200 unsigned int len; 201 const void *data; 202 }; 203 204 static unsigned int get_linear_data(unsigned int consumed, const u8 **dst, 205 struct ts_config *conf, 206 struct ts_state *state) 207 { 208 struct ts_linear_state *st = (struct ts_linear_state *) state->cb; 209 210 if (likely(consumed < st->len)) { 211 *dst = st->data + consumed; 212 return st->len - consumed; 213 } 214 215 return 0; 216 } 217 218 /** 219 * textsearch_find_continuous - search a pattern in continuous/linear data 220 * @conf: search configuration 221 * @state: search state 222 * @data: data to search in 223 * @len: length of data 224 * 225 * A simplified version of textsearch_find() for continuous/linear data. 226 * Call textsearch_next() to retrieve subsequent matches. 227 * 228 * Returns the position of first occurrence of the pattern or 229 * %UINT_MAX if no occurrence was found. 230 */ 231 unsigned int textsearch_find_continuous(struct ts_config *conf, 232 struct ts_state *state, 233 const void *data, unsigned int len) 234 { 235 struct ts_linear_state *st = (struct ts_linear_state *) state->cb; 236 237 conf->get_next_block = get_linear_data; 238 st->data = data; 239 st->len = len; 240 241 return textsearch_find(conf, state); 242 } 243 EXPORT_SYMBOL(textsearch_find_continuous); 244 245 /** 246 * textsearch_prepare - Prepare a search 247 * @algo: name of search algorithm 248 * @pattern: pattern data 249 * @len: length of pattern 250 * @gfp_mask: allocation mask 251 * @flags: search flags 252 * 253 * Looks up the search algorithm module and creates a new textsearch 254 * configuration for the specified pattern. 255 * 256 * Note: The format of the pattern may not be compatible between 257 * the various search algorithms. 258 * 259 * Returns a new textsearch configuration according to the specified 260 * parameters or a ERR_PTR(). If a zero length pattern is passed, this 261 * function returns EINVAL. 262 */ 263 struct ts_config *textsearch_prepare(const char *algo, const void *pattern, 264 unsigned int len, gfp_t gfp_mask, int flags) 265 { 266 int err = -ENOENT; 267 struct ts_config *conf; 268 struct ts_ops *ops; 269 270 if (len == 0) 271 return ERR_PTR(-EINVAL); 272 273 ops = lookup_ts_algo(algo); 274 #ifdef CONFIG_MODULES 275 /* 276 * Why not always autoload you may ask. Some users are 277 * in a situation where requesting a module may deadlock, 278 * especially when the module is located on a NFS mount. 279 */ 280 if (ops == NULL && flags & TS_AUTOLOAD) { 281 request_module("ts_%s", algo); 282 ops = lookup_ts_algo(algo); 283 } 284 #endif 285 286 if (ops == NULL) 287 goto errout; 288 289 conf = ops->init(pattern, len, gfp_mask, flags); 290 if (IS_ERR(conf)) { 291 err = PTR_ERR(conf); 292 goto errout; 293 } 294 295 conf->ops = ops; 296 return conf; 297 298 errout: 299 if (ops) 300 module_put(ops->owner); 301 302 return ERR_PTR(err); 303 } 304 EXPORT_SYMBOL(textsearch_prepare); 305 306 /** 307 * textsearch_destroy - destroy a search configuration 308 * @conf: search configuration 309 * 310 * Releases all references of the configuration and frees 311 * up the memory. 312 */ 313 void textsearch_destroy(struct ts_config *conf) 314 { 315 if (conf->ops) { 316 if (conf->ops->destroy) 317 conf->ops->destroy(conf); 318 module_put(conf->ops->owner); 319 } 320 321 kfree(conf); 322 } 323 EXPORT_SYMBOL(textsearch_destroy); 324