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