Commit | Line | Data |
---|---|---|
2de4ff7b TG |
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> | |
10 | * Pablo Neira Ayuso <pablo@eurodev.net> | |
11 | * | |
12 | * ========================================================================== | |
13 | * | |
14 | * INTRODUCTION | |
15 | * | |
16 | * The textsearch infrastructure provides text searching facitilies for | |
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 | |
d08df601 | 43 | * to the algorithm to store persistent variables. |
2de4ff7b TG |
44 | * (4) Core eventually resets the search offset and forwards the find() |
45 | * request to the algorithm. | |
46 | * (5) Algorithm calls get_next_block() provided by the user continously | |
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 | |
57 | * by calling textsearch_prepare() specyfing the searching algorithm and | |
58 | * the pattern to look for. The returned configuration may then be used | |
59 | * for an arbitary amount of times and even in parallel as long as a | |
60 | * separate struct ts_state variable is provided to every instance. | |
61 | * | |
62 | * The actual search is performed by either calling textsearch_find_- | |
63 | * continuous() for linear data or by providing an own get_next_block() | |
64 | * implementation and calling textsearch_find(). Both functions return | |
65 | * the position of the first occurrence of the patern or UINT_MAX if | |
66 | * no match was found. Subsequent occurences can be found by calling | |
67 | * textsearch_next() regardless of the linearity of the data. | |
68 | * | |
69 | * Once you're done using a configuration it must be given back via | |
70 | * textsearch_destroy. | |
71 | * | |
72 | * EXAMPLE | |
73 | * | |
74 | * int pos; | |
75 | * struct ts_config *conf; | |
76 | * struct ts_state state; | |
77 | * const char *pattern = "chicken"; | |
78 | * const char *example = "We dance the funky chicken"; | |
79 | * | |
80 | * conf = textsearch_prepare("kmp", pattern, strlen(pattern), | |
81 | * GFP_KERNEL, TS_AUTOLOAD); | |
82 | * if (IS_ERR(conf)) { | |
83 | * err = PTR_ERR(conf); | |
84 | * goto errout; | |
85 | * } | |
86 | * | |
87 | * pos = textsearch_find_continuous(conf, &state, example, strlen(example)); | |
88 | * if (pos != UINT_MAX) | |
89 | * panic("Oh my god, dancing chickens at %d\n", pos); | |
90 | * | |
91 | * textsearch_destroy(conf); | |
92 | * | |
93 | * ========================================================================== | |
94 | */ | |
95 | ||
2de4ff7b TG |
96 | #include <linux/module.h> |
97 | #include <linux/types.h> | |
98 | #include <linux/string.h> | |
99 | #include <linux/init.h> | |
100 | #include <linux/rcupdate.h> | |
101 | #include <linux/err.h> | |
102 | #include <linux/textsearch.h> | |
103 | ||
104 | static LIST_HEAD(ts_ops); | |
105 | static DEFINE_SPINLOCK(ts_mod_lock); | |
106 | ||
107 | static inline struct ts_ops *lookup_ts_algo(const char *name) | |
108 | { | |
109 | struct ts_ops *o; | |
110 | ||
111 | rcu_read_lock(); | |
112 | list_for_each_entry_rcu(o, &ts_ops, list) { | |
113 | if (!strcmp(name, o->name)) { | |
114 | if (!try_module_get(o->owner)) | |
115 | o = NULL; | |
116 | rcu_read_unlock(); | |
117 | return o; | |
118 | } | |
119 | } | |
120 | rcu_read_unlock(); | |
121 | ||
122 | return NULL; | |
123 | } | |
124 | ||
125 | /** | |
126 | * textsearch_register - register a textsearch module | |
127 | * @ops: operations lookup table | |
128 | * | |
129 | * This function must be called by textsearch modules to announce | |
130 | * their presence. The specified &@ops must have %name set to a | |
131 | * unique identifier and the callbacks find(), init(), get_pattern(), | |
132 | * and get_pattern_len() must be implemented. | |
133 | * | |
134 | * Returns 0 or -EEXISTS if another module has already registered | |
135 | * with same name. | |
136 | */ | |
137 | int textsearch_register(struct ts_ops *ops) | |
138 | { | |
139 | int err = -EEXIST; | |
140 | struct ts_ops *o; | |
141 | ||
142 | if (ops->name == NULL || ops->find == NULL || ops->init == NULL || | |
143 | ops->get_pattern == NULL || ops->get_pattern_len == NULL) | |
144 | return -EINVAL; | |
145 | ||
146 | spin_lock(&ts_mod_lock); | |
147 | list_for_each_entry(o, &ts_ops, list) { | |
148 | if (!strcmp(ops->name, o->name)) | |
149 | goto errout; | |
150 | } | |
151 | ||
152 | list_add_tail_rcu(&ops->list, &ts_ops); | |
153 | err = 0; | |
154 | errout: | |
155 | spin_unlock(&ts_mod_lock); | |
156 | return err; | |
157 | } | |
158 | ||
159 | /** | |
160 | * textsearch_unregister - unregister a textsearch module | |
161 | * @ops: operations lookup table | |
162 | * | |
163 | * This function must be called by textsearch modules to announce | |
164 | * their disappearance for examples when the module gets unloaded. | |
165 | * The &ops parameter must be the same as the one during the | |
166 | * registration. | |
167 | * | |
168 | * Returns 0 on success or -ENOENT if no matching textsearch | |
169 | * registration was found. | |
170 | */ | |
171 | int textsearch_unregister(struct ts_ops *ops) | |
172 | { | |
173 | int err = 0; | |
174 | struct ts_ops *o; | |
175 | ||
176 | spin_lock(&ts_mod_lock); | |
177 | list_for_each_entry(o, &ts_ops, list) { | |
178 | if (o == ops) { | |
179 | list_del_rcu(&o->list); | |
180 | goto out; | |
181 | } | |
182 | } | |
183 | ||
184 | err = -ENOENT; | |
185 | out: | |
186 | spin_unlock(&ts_mod_lock); | |
187 | return err; | |
188 | } | |
189 | ||
190 | struct ts_linear_state | |
191 | { | |
192 | unsigned int len; | |
193 | const void *data; | |
194 | }; | |
195 | ||
196 | static unsigned int get_linear_data(unsigned int consumed, const u8 **dst, | |
197 | struct ts_config *conf, | |
198 | struct ts_state *state) | |
199 | { | |
200 | struct ts_linear_state *st = (struct ts_linear_state *) state->cb; | |
201 | ||
202 | if (likely(consumed < st->len)) { | |
203 | *dst = st->data + consumed; | |
204 | return st->len - consumed; | |
205 | } | |
206 | ||
207 | return 0; | |
208 | } | |
209 | ||
210 | /** | |
211 | * textsearch_find_continuous - search a pattern in continuous/linear data | |
212 | * @conf: search configuration | |
213 | * @state: search state | |
214 | * @data: data to search in | |
215 | * @len: length of data | |
216 | * | |
217 | * A simplified version of textsearch_find() for continuous/linear data. | |
218 | * Call textsearch_next() to retrieve subsequent matches. | |
219 | * | |
220 | * Returns the position of first occurrence of the pattern or | |
72fd4a35 | 221 | * %UINT_MAX if no occurrence was found. |
2de4ff7b TG |
222 | */ |
223 | unsigned int textsearch_find_continuous(struct ts_config *conf, | |
224 | struct ts_state *state, | |
225 | const void *data, unsigned int len) | |
226 | { | |
227 | struct ts_linear_state *st = (struct ts_linear_state *) state->cb; | |
228 | ||
229 | conf->get_next_block = get_linear_data; | |
230 | st->data = data; | |
231 | st->len = len; | |
232 | ||
233 | return textsearch_find(conf, state); | |
234 | } | |
235 | ||
236 | /** | |
237 | * textsearch_prepare - Prepare a search | |
238 | * @algo: name of search algorithm | |
239 | * @pattern: pattern data | |
240 | * @len: length of pattern | |
241 | * @gfp_mask: allocation mask | |
242 | * @flags: search flags | |
243 | * | |
244 | * Looks up the search algorithm module and creates a new textsearch | |
245 | * configuration for the specified pattern. Upon completion all | |
246 | * necessary refcnts are held and the configuration must be put back | |
247 | * using textsearch_put() after usage. | |
248 | * | |
249 | * Note: The format of the pattern may not be compatible between | |
250 | * the various search algorithms. | |
251 | * | |
252 | * Returns a new textsearch configuration according to the specified | |
253 | * parameters or a ERR_PTR(). | |
254 | */ | |
255 | struct ts_config *textsearch_prepare(const char *algo, const void *pattern, | |
fd4f2df2 | 256 | unsigned int len, gfp_t gfp_mask, int flags) |
2de4ff7b TG |
257 | { |
258 | int err = -ENOENT; | |
259 | struct ts_config *conf; | |
260 | struct ts_ops *ops; | |
261 | ||
262 | ops = lookup_ts_algo(algo); | |
263 | #ifdef CONFIG_KMOD | |
264 | /* | |
265 | * Why not always autoload you may ask. Some users are | |
266 | * in a situation where requesting a module may deadlock, | |
267 | * especially when the module is located on a NFS mount. | |
268 | */ | |
269 | if (ops == NULL && flags & TS_AUTOLOAD) { | |
270 | request_module("ts_%s", algo); | |
271 | ops = lookup_ts_algo(algo); | |
272 | } | |
273 | #endif | |
274 | ||
275 | if (ops == NULL) | |
276 | goto errout; | |
277 | ||
278 | conf = ops->init(pattern, len, gfp_mask); | |
279 | if (IS_ERR(conf)) { | |
280 | err = PTR_ERR(conf); | |
281 | goto errout; | |
282 | } | |
283 | ||
284 | conf->ops = ops; | |
285 | return conf; | |
286 | ||
287 | errout: | |
288 | if (ops) | |
289 | module_put(ops->owner); | |
290 | ||
291 | return ERR_PTR(err); | |
292 | } | |
293 | ||
294 | /** | |
295 | * textsearch_destroy - destroy a search configuration | |
296 | * @conf: search configuration | |
297 | * | |
298 | * Releases all references of the configuration and frees | |
299 | * up the memory. | |
300 | */ | |
301 | void textsearch_destroy(struct ts_config *conf) | |
302 | { | |
303 | if (conf->ops) { | |
304 | if (conf->ops->destroy) | |
305 | conf->ops->destroy(conf); | |
306 | module_put(conf->ops->owner); | |
307 | } | |
308 | ||
309 | kfree(conf); | |
310 | } | |
311 | ||
312 | EXPORT_SYMBOL(textsearch_register); | |
313 | EXPORT_SYMBOL(textsearch_unregister); | |
314 | EXPORT_SYMBOL(textsearch_prepare); | |
315 | EXPORT_SYMBOL(textsearch_find_continuous); | |
316 | EXPORT_SYMBOL(textsearch_destroy); |