Root/
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@netfilter.org> |
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 |
43 | * to the algorithm to store persistent variables. |
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() 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. |
61 | * The returned configuration may then be used for an arbitary |
62 | * amount of times and even in parallel as long as a separate struct |
63 | * ts_state variable is provided to every instance. |
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 |
68 | * the position of the first occurrence of the patern or UINT_MAX if |
69 | * no match was found. Subsequent occurences can be found by calling |
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); |
95 | * ========================================================================== |
96 | */ |
97 | |
98 | #include <linux/module.h> |
99 | #include <linux/types.h> |
100 | #include <linux/string.h> |
101 | #include <linux/init.h> |
102 | #include <linux/rculist.h> |
103 | #include <linux/rcupdate.h> |
104 | #include <linux/err.h> |
105 | #include <linux/textsearch.h> |
106 | #include <linux/slab.h> |
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 | } |
162 | |
163 | /** |
164 | * textsearch_unregister - unregister a textsearch module |
165 | * @ops: operations lookup table |
166 | * |
167 | * This function must be called by textsearch modules to announce |
168 | * their disappearance for examples when the module gets unloaded. |
169 | * The &ops parameter must be the same as the one during the |
170 | * registration. |
171 | * |
172 | * Returns 0 on success or -ENOENT if no matching textsearch |
173 | * registration was found. |
174 | */ |
175 | int textsearch_unregister(struct ts_ops *ops) |
176 | { |
177 | int err = 0; |
178 | struct ts_ops *o; |
179 | |
180 | spin_lock(&ts_mod_lock); |
181 | list_for_each_entry(o, &ts_ops, list) { |
182 | if (o == ops) { |
183 | list_del_rcu(&o->list); |
184 | goto out; |
185 | } |
186 | } |
187 | |
188 | err = -ENOENT; |
189 | out: |
190 | spin_unlock(&ts_mod_lock); |
191 | return err; |
192 | } |
193 | |
194 | struct ts_linear_state |
195 | { |
196 | unsigned int len; |
197 | const void *data; |
198 | }; |
199 | |
200 | static unsigned int get_linear_data(unsigned int consumed, const u8 **dst, |
201 | struct ts_config *conf, |
202 | struct ts_state *state) |
203 | { |
204 | struct ts_linear_state *st = (struct ts_linear_state *) state->cb; |
205 | |
206 | if (likely(consumed < st->len)) { |
207 | *dst = st->data + consumed; |
208 | return st->len - consumed; |
209 | } |
210 | |
211 | return 0; |
212 | } |
213 | |
214 | /** |
215 | * textsearch_find_continuous - search a pattern in continuous/linear data |
216 | * @conf: search configuration |
217 | * @state: search state |
218 | * @data: data to search in |
219 | * @len: length of data |
220 | * |
221 | * A simplified version of textsearch_find() for continuous/linear data. |
222 | * Call textsearch_next() to retrieve subsequent matches. |
223 | * |
224 | * Returns the position of first occurrence of the pattern or |
225 | * %UINT_MAX if no occurrence was found. |
226 | */ |
227 | unsigned int textsearch_find_continuous(struct ts_config *conf, |
228 | struct ts_state *state, |
229 | const void *data, unsigned int len) |
230 | { |
231 | struct ts_linear_state *st = (struct ts_linear_state *) state->cb; |
232 | |
233 | conf->get_next_block = get_linear_data; |
234 | st->data = data; |
235 | st->len = len; |
236 | |
237 | return textsearch_find(conf, state); |
238 | } |
239 | |
240 | /** |
241 | * textsearch_prepare - Prepare a search |
242 | * @algo: name of search algorithm |
243 | * @pattern: pattern data |
244 | * @len: length of pattern |
245 | * @gfp_mask: allocation mask |
246 | * @flags: search flags |
247 | * |
248 | * Looks up the search algorithm module and creates a new textsearch |
249 | * configuration for the specified pattern. Upon completion all |
250 | * necessary refcnts are held and the configuration must be put back |
251 | * using textsearch_put() after usage. |
252 | * |
253 | * Note: The format of the pattern may not be compatible between |
254 | * the various search algorithms. |
255 | * |
256 | * Returns a new textsearch configuration according to the specified |
257 | * parameters or a ERR_PTR(). If a zero length pattern is passed, this |
258 | * function returns EINVAL. |
259 | */ |
260 | struct ts_config *textsearch_prepare(const char *algo, const void *pattern, |
261 | unsigned int len, gfp_t gfp_mask, int flags) |
262 | { |
263 | int err = -ENOENT; |
264 | struct ts_config *conf; |
265 | struct ts_ops *ops; |
266 | |
267 | if (len == 0) |
268 | return ERR_PTR(-EINVAL); |
269 | |
270 | ops = lookup_ts_algo(algo); |
271 | #ifdef CONFIG_MODULES |
272 | /* |
273 | * Why not always autoload you may ask. Some users are |
274 | * in a situation where requesting a module may deadlock, |
275 | * especially when the module is located on a NFS mount. |
276 | */ |
277 | if (ops == NULL && flags & TS_AUTOLOAD) { |
278 | request_module("ts_%s", algo); |
279 | ops = lookup_ts_algo(algo); |
280 | } |
281 | #endif |
282 | |
283 | if (ops == NULL) |
284 | goto errout; |
285 | |
286 | conf = ops->init(pattern, len, gfp_mask, flags); |
287 | if (IS_ERR(conf)) { |
288 | err = PTR_ERR(conf); |
289 | goto errout; |
290 | } |
291 | |
292 | conf->ops = ops; |
293 | return conf; |
294 | |
295 | errout: |
296 | if (ops) |
297 | module_put(ops->owner); |
298 | |
299 | return ERR_PTR(err); |
300 | } |
301 | |
302 | /** |
303 | * textsearch_destroy - destroy a search configuration |
304 | * @conf: search configuration |
305 | * |
306 | * Releases all references of the configuration and frees |
307 | * up the memory. |
308 | */ |
309 | void textsearch_destroy(struct ts_config *conf) |
310 | { |
311 | if (conf->ops) { |
312 | if (conf->ops->destroy) |
313 | conf->ops->destroy(conf); |
314 | module_put(conf->ops->owner); |
315 | } |
316 | |
317 | kfree(conf); |
318 | } |
319 | |
320 | EXPORT_SYMBOL(textsearch_register); |
321 | EXPORT_SYMBOL(textsearch_unregister); |
322 | EXPORT_SYMBOL(textsearch_prepare); |
323 | EXPORT_SYMBOL(textsearch_find_continuous); |
324 | EXPORT_SYMBOL(textsearch_destroy); |
325 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9