Branch data Line data Source code
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 : 0 : static inline struct ts_ops *lookup_ts_algo(const char *name)
114 : : {
115 : : struct ts_ops *o;
116 : :
117 : : rcu_read_lock();
118 [ # # ]: 0 : list_for_each_entry_rcu(o, &ts_ops, list) {
119 [ # # ]: 0 : if (!strcmp(name, o->name)) {
120 [ # # ]: 0 : if (!try_module_get(o->owner))
121 : : o = NULL;
122 : : rcu_read_unlock();
123 : 0 : return o;
124 : : }
125 : : }
126 : : rcu_read_unlock();
127 : :
128 : 0 : 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 : 0 : int textsearch_register(struct ts_ops *ops)
144 : : {
145 : : int err = -EEXIST;
146 : : struct ts_ops *o;
147 : :
148 [ # # # # : 0 : if (ops->name == NULL || ops->find == NULL || ops->init == NULL ||
# # # # ]
149 [ # # ]: 0 : ops->get_pattern == NULL || ops->get_pattern_len == NULL)
150 : : return -EINVAL;
151 : :
152 : : spin_lock(&ts_mod_lock);
153 [ # # ]: 0 : list_for_each_entry(o, &ts_ops, list) {
154 [ # # ]: 0 : if (!strcmp(ops->name, o->name))
155 : : goto errout;
156 : : }
157 : :
158 : 0 : list_add_tail_rcu(&ops->list, &ts_ops);
159 : : err = 0;
160 : : errout:
161 : : spin_unlock(&ts_mod_lock);
162 : 0 : 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 : 0 : 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 [ # # ]: 0 : list_for_each_entry(o, &ts_ops, list) {
185 [ # # ]: 0 : 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 : 0 : 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 : 0 : 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 [ # # ]: 0 : if (likely(consumed < st->len)) {
211 : 0 : *dst = st->data + consumed;
212 : 0 : 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 : 0 : 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 : 0 : conf->get_next_block = get_linear_data;
238 : 0 : st->data = data;
239 : 0 : st->len = len;
240 : :
241 : 0 : 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 : 0 : 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 [ # # ]: 0 : if (len == 0)
271 : : return ERR_PTR(-EINVAL);
272 : :
273 : 0 : 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 [ # # # # ]: 0 : if (ops == NULL && flags & TS_AUTOLOAD) {
281 : 0 : request_module("ts_%s", algo);
282 : 0 : ops = lookup_ts_algo(algo);
283 : : }
284 : : #endif
285 : :
286 [ # # ]: 0 : if (ops == NULL)
287 : : goto errout;
288 : :
289 : 0 : conf = ops->init(pattern, len, gfp_mask, flags);
290 [ # # ]: 0 : if (IS_ERR(conf)) {
291 : : err = PTR_ERR(conf);
292 : 0 : goto errout;
293 : : }
294 : :
295 : 0 : conf->ops = ops;
296 : 0 : return conf;
297 : :
298 : : errout:
299 [ # # ]: 0 : if (ops)
300 : 0 : module_put(ops->owner);
301 : :
302 : 0 : 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 : 0 : void textsearch_destroy(struct ts_config *conf)
314 : : {
315 [ # # ]: 0 : if (conf->ops) {
316 [ # # ]: 0 : if (conf->ops->destroy)
317 : 0 : conf->ops->destroy(conf);
318 : 0 : module_put(conf->ops->owner);
319 : : }
320 : :
321 : 0 : kfree(conf);
322 : 0 : }
323 : : EXPORT_SYMBOL(textsearch_destroy);
|
