textsearch.c 9.44 KB
Newer Older
1 2 3 4 5 6 7 8 9
/*
 * lib/textsearch.c	Generic text search interface
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
 *
 * Authors:	Thomas Graf <tgraf@suug.ch>
10
 * 		Pablo Neira Ayuso <pablo@netfilter.org>
11 12 13 14 15
 *
 * ==========================================================================
 *
 * INTRODUCTION
 *
16
 *   The textsearch infrastructure provides text searching facilities for
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
 *   both linear and non-linear data. Individual search algorithms are
 *   implemented in modules and chosen by the user.
 *
 * ARCHITECTURE
 *
 *      User
 *     +----------------+
 *     |        finish()|<--------------(6)-----------------+
 *     |get_next_block()|<--------------(5)---------------+ |
 *     |                |                     Algorithm   | |
 *     |                |                    +------------------------------+
 *     |                |                    |  init()   find()   destroy() |
 *     |                |                    +------------------------------+
 *     |                |       Core API           ^       ^          ^
 *     |                |      +---------------+  (2)     (4)        (8)
 *     |             (1)|----->| prepare()     |---+       |          |
 *     |             (3)|----->| find()/next() |-----------+          |
 *     |             (7)|----->| destroy()     |----------------------+
 *     +----------------+      +---------------+
 *  
 *   (1) User configures a search by calling _prepare() specifying the
 *       search parameters such as the pattern and algorithm name.
 *   (2) Core requests the algorithm to allocate and initialize a search
 *       configuration according to the specified parameters.
 *   (3) User starts the search(es) by calling _find() or _next() to
 *       fetch subsequent occurrences. A state variable is provided
Robert P. J. Day's avatar
Robert P. J. Day committed
43
 *       to the algorithm to store persistent variables.
44 45
 *   (4) Core eventually resets the search offset and forwards the find()
 *       request to the algorithm.
46
 *   (5) Algorithm calls get_next_block() provided by the user continuously
47 48 49 50 51 52 53 54 55 56
 *       to fetch the data to be searched in block by block.
 *   (6) Algorithm invokes finish() after the last call to get_next_block
 *       to clean up any leftovers from get_next_block. (Optional)
 *   (7) User destroys the configuration by calling _destroy().
 *   (8) Core notifies the algorithm to destroy algorithm specific
 *       allocations. (Optional)
 *
 * USAGE
 *
 *   Before a search can be performed, a configuration must be created
57 58 59 60
 *   by calling textsearch_prepare() specifying the searching algorithm,
 *   the pattern to look for and flags. As a flag, you can set TS_IGNORECASE
 *   to perform case insensitive matching. But it might slow down
 *   performance of algorithm, so you should use it at own your risk.
61
 *   The returned configuration may then be used for an arbitrary
62 63
 *   amount of times and even in parallel as long as a separate struct
 *   ts_state variable is provided to every instance.
64 65 66 67
 *
 *   The actual search is performed by either calling textsearch_find_-
 *   continuous() for linear data or by providing an own get_next_block()
 *   implementation and calling textsearch_find(). Both functions return
68 69
 *   the position of the first occurrence of the pattern or UINT_MAX if
 *   no match was found. Subsequent occurrences can be found by calling
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
 *   textsearch_next() regardless of the linearity of the data.
 *
 *   Once you're done using a configuration it must be given back via
 *   textsearch_destroy.
 *
 * EXAMPLE
 *
 *   int pos;
 *   struct ts_config *conf;
 *   struct ts_state state;
 *   const char *pattern = "chicken";
 *   const char *example = "We dance the funky chicken";
 *
 *   conf = textsearch_prepare("kmp", pattern, strlen(pattern),
 *                             GFP_KERNEL, TS_AUTOLOAD);
 *   if (IS_ERR(conf)) {
 *       err = PTR_ERR(conf);
 *       goto errout;
 *   }
 *
 *   pos = textsearch_find_continuous(conf, &state, example, strlen(example));
 *   if (pos != UINT_MAX)
 *       panic("Oh my god, dancing chickens at %d\n", pos);
 *
 *   textsearch_destroy(conf);
 * ==========================================================================
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/string.h>
#include <linux/init.h>
102
#include <linux/rculist.h>
103 104 105
#include <linux/rcupdate.h>
#include <linux/err.h>
#include <linux/textsearch.h>
106
#include <linux/slab.h>
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161

static LIST_HEAD(ts_ops);
static DEFINE_SPINLOCK(ts_mod_lock);

static inline struct ts_ops *lookup_ts_algo(const char *name)
{
	struct ts_ops *o;

	rcu_read_lock();
	list_for_each_entry_rcu(o, &ts_ops, list) {
		if (!strcmp(name, o->name)) {
			if (!try_module_get(o->owner))
				o = NULL;
			rcu_read_unlock();
			return o;
		}
	}
	rcu_read_unlock();

	return NULL;
}

/**
 * textsearch_register - register a textsearch module
 * @ops: operations lookup table
 *
 * This function must be called by textsearch modules to announce
 * their presence. The specified &@ops must have %name set to a
 * unique identifier and the callbacks find(), init(), get_pattern(),
 * and get_pattern_len() must be implemented.
 *
 * Returns 0 or -EEXISTS if another module has already registered
 * with same name.
 */
int textsearch_register(struct ts_ops *ops)
{
	int err = -EEXIST;
	struct ts_ops *o;

	if (ops->name == NULL || ops->find == NULL || ops->init == NULL ||
	    ops->get_pattern == NULL || ops->get_pattern_len == NULL)
		return -EINVAL;

	spin_lock(&ts_mod_lock);
	list_for_each_entry(o, &ts_ops, list) {
		if (!strcmp(ops->name, o->name))
			goto errout;
	}

	list_add_tail_rcu(&ops->list, &ts_ops);
	err = 0;
errout:
	spin_unlock(&ts_mod_lock);
	return err;
}
162
EXPORT_SYMBOL(textsearch_register);
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193

/**
 * textsearch_unregister - unregister a textsearch module
 * @ops: operations lookup table
 *
 * This function must be called by textsearch modules to announce
 * their disappearance for examples when the module gets unloaded.
 * The &ops parameter must be the same as the one during the
 * registration.
 *
 * Returns 0 on success or -ENOENT if no matching textsearch
 * registration was found.
 */
int textsearch_unregister(struct ts_ops *ops)
{
	int err = 0;
	struct ts_ops *o;

	spin_lock(&ts_mod_lock);
	list_for_each_entry(o, &ts_ops, list) {
		if (o == ops) {
			list_del_rcu(&o->list);
			goto out;
		}
	}

	err = -ENOENT;
out:
	spin_unlock(&ts_mod_lock);
	return err;
}
194
EXPORT_SYMBOL(textsearch_unregister);
195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226

struct ts_linear_state
{
	unsigned int	len;
	const void	*data;
};

static unsigned int get_linear_data(unsigned int consumed, const u8 **dst,
				    struct ts_config *conf,
				    struct ts_state *state)
{
	struct ts_linear_state *st = (struct ts_linear_state *) state->cb;

	if (likely(consumed < st->len)) {
		*dst = st->data + consumed;
		return st->len - consumed;
	}

	return 0;
}

/**
 * textsearch_find_continuous - search a pattern in continuous/linear data
 * @conf: search configuration
 * @state: search state
 * @data: data to search in
 * @len: length of data
 *
 * A simplified version of textsearch_find() for continuous/linear data.
 * Call textsearch_next() to retrieve subsequent matches.
 *
 * Returns the position of first occurrence of the pattern or
227
 * %UINT_MAX if no occurrence was found.
228 229 230 231 232 233 234 235 236 237 238 239 240
 */ 
unsigned int textsearch_find_continuous(struct ts_config *conf,
					struct ts_state *state,
					const void *data, unsigned int len)
{
	struct ts_linear_state *st = (struct ts_linear_state *) state->cb;

	conf->get_next_block = get_linear_data;
	st->data = data;
	st->len = len;

	return textsearch_find(conf, state);
}
241
EXPORT_SYMBOL(textsearch_find_continuous);
242 243 244 245 246 247 248 249 250 251

/**
 * textsearch_prepare - Prepare a search
 * @algo: name of search algorithm
 * @pattern: pattern data
 * @len: length of pattern
 * @gfp_mask: allocation mask
 * @flags: search flags
 *
 * Looks up the search algorithm module and creates a new textsearch
252
 * configuration for the specified pattern.
253 254 255 256 257
 *
 * Note: The format of the pattern may not be compatible between
 *       the various search algorithms.
 *
 * Returns a new textsearch configuration according to the specified
258 259
 * parameters or a ERR_PTR(). If a zero length pattern is passed, this
 * function returns EINVAL.
260 261
 */
struct ts_config *textsearch_prepare(const char *algo, const void *pattern,
Al Viro's avatar
Al Viro committed
262
				     unsigned int len, gfp_t gfp_mask, int flags)
263 264 265 266 267
{
	int err = -ENOENT;
	struct ts_config *conf;
	struct ts_ops *ops;
	
268 269 270
	if (len == 0)
		return ERR_PTR(-EINVAL);

271
	ops = lookup_ts_algo(algo);
Johannes Berg's avatar
Johannes Berg committed
272
#ifdef CONFIG_MODULES
273 274 275 276 277 278 279 280 281 282 283 284 285 286
	/*
	 * Why not always autoload you may ask. Some users are
	 * in a situation where requesting a module may deadlock,
	 * especially when the module is located on a NFS mount.
	 */
	if (ops == NULL && flags & TS_AUTOLOAD) {
		request_module("ts_%s", algo);
		ops = lookup_ts_algo(algo);
	}
#endif

	if (ops == NULL)
		goto errout;

287
	conf = ops->init(pattern, len, gfp_mask, flags);
288 289 290 291 292 293 294 295 296 297 298 299 300 301
	if (IS_ERR(conf)) {
		err = PTR_ERR(conf);
		goto errout;
	}

	conf->ops = ops;
	return conf;

errout:
	if (ops)
		module_put(ops->owner);
		
	return ERR_PTR(err);
}
302
EXPORT_SYMBOL(textsearch_prepare);
303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321

/**
 * textsearch_destroy - destroy a search configuration
 * @conf: search configuration
 *
 * Releases all references of the configuration and frees
 * up the memory.
 */
void textsearch_destroy(struct ts_config *conf)
{
	if (conf->ops) {
		if (conf->ops->destroy)
			conf->ops->destroy(conf);
		module_put(conf->ops->owner);
	}

	kfree(conf);
}
EXPORT_SYMBOL(textsearch_destroy);