textsearch.c 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316
  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
  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() 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. #include <linux/module.h>
  96. #include <linux/types.h>
  97. #include <linux/string.h>
  98. #include <linux/init.h>
  99. #include <linux/rcupdate.h>
  100. #include <linux/err.h>
  101. #include <linux/textsearch.h>
  102. static LIST_HEAD(ts_ops);
  103. static DEFINE_SPINLOCK(ts_mod_lock);
  104. static inline struct ts_ops *lookup_ts_algo(const char *name)
  105. {
  106. struct ts_ops *o;
  107. rcu_read_lock();
  108. list_for_each_entry_rcu(o, &ts_ops, list) {
  109. if (!strcmp(name, o->name)) {
  110. if (!try_module_get(o->owner))
  111. o = NULL;
  112. rcu_read_unlock();
  113. return o;
  114. }
  115. }
  116. rcu_read_unlock();
  117. return NULL;
  118. }
  119. /**
  120. * textsearch_register - register a textsearch module
  121. * @ops: operations lookup table
  122. *
  123. * This function must be called by textsearch modules to announce
  124. * their presence. The specified &@ops must have %name set to a
  125. * unique identifier and the callbacks find(), init(), get_pattern(),
  126. * and get_pattern_len() must be implemented.
  127. *
  128. * Returns 0 or -EEXISTS if another module has already registered
  129. * with same name.
  130. */
  131. int textsearch_register(struct ts_ops *ops)
  132. {
  133. int err = -EEXIST;
  134. struct ts_ops *o;
  135. if (ops->name == NULL || ops->find == NULL || ops->init == NULL ||
  136. ops->get_pattern == NULL || ops->get_pattern_len == NULL)
  137. return -EINVAL;
  138. spin_lock(&ts_mod_lock);
  139. list_for_each_entry(o, &ts_ops, list) {
  140. if (!strcmp(ops->name, o->name))
  141. goto errout;
  142. }
  143. list_add_tail_rcu(&ops->list, &ts_ops);
  144. err = 0;
  145. errout:
  146. spin_unlock(&ts_mod_lock);
  147. return err;
  148. }
  149. /**
  150. * textsearch_unregister - unregister a textsearch module
  151. * @ops: operations lookup table
  152. *
  153. * This function must be called by textsearch modules to announce
  154. * their disappearance for examples when the module gets unloaded.
  155. * The &ops parameter must be the same as the one during the
  156. * registration.
  157. *
  158. * Returns 0 on success or -ENOENT if no matching textsearch
  159. * registration was found.
  160. */
  161. int textsearch_unregister(struct ts_ops *ops)
  162. {
  163. int err = 0;
  164. struct ts_ops *o;
  165. spin_lock(&ts_mod_lock);
  166. list_for_each_entry(o, &ts_ops, list) {
  167. if (o == ops) {
  168. list_del_rcu(&o->list);
  169. goto out;
  170. }
  171. }
  172. err = -ENOENT;
  173. out:
  174. spin_unlock(&ts_mod_lock);
  175. return err;
  176. }
  177. struct ts_linear_state
  178. {
  179. unsigned int len;
  180. const void *data;
  181. };
  182. static unsigned int get_linear_data(unsigned int consumed, const u8 **dst,
  183. struct ts_config *conf,
  184. struct ts_state *state)
  185. {
  186. struct ts_linear_state *st = (struct ts_linear_state *) state->cb;
  187. if (likely(consumed < st->len)) {
  188. *dst = st->data + consumed;
  189. return st->len - consumed;
  190. }
  191. return 0;
  192. }
  193. /**
  194. * textsearch_find_continuous - search a pattern in continuous/linear data
  195. * @conf: search configuration
  196. * @state: search state
  197. * @data: data to search in
  198. * @len: length of data
  199. *
  200. * A simplified version of textsearch_find() for continuous/linear data.
  201. * Call textsearch_next() to retrieve subsequent matches.
  202. *
  203. * Returns the position of first occurrence of the pattern or
  204. * %UINT_MAX if no occurrence was found.
  205. */
  206. unsigned int textsearch_find_continuous(struct ts_config *conf,
  207. struct ts_state *state,
  208. const void *data, unsigned int len)
  209. {
  210. struct ts_linear_state *st = (struct ts_linear_state *) state->cb;
  211. conf->get_next_block = get_linear_data;
  212. st->data = data;
  213. st->len = len;
  214. return textsearch_find(conf, state);
  215. }
  216. /**
  217. * textsearch_prepare - Prepare a search
  218. * @algo: name of search algorithm
  219. * @pattern: pattern data
  220. * @len: length of pattern
  221. * @gfp_mask: allocation mask
  222. * @flags: search flags
  223. *
  224. * Looks up the search algorithm module and creates a new textsearch
  225. * configuration for the specified pattern. Upon completion all
  226. * necessary refcnts are held and the configuration must be put back
  227. * using textsearch_put() after usage.
  228. *
  229. * Note: The format of the pattern may not be compatible between
  230. * the various search algorithms.
  231. *
  232. * Returns a new textsearch configuration according to the specified
  233. * parameters or a ERR_PTR().
  234. */
  235. struct ts_config *textsearch_prepare(const char *algo, const void *pattern,
  236. unsigned int len, gfp_t gfp_mask, int flags)
  237. {
  238. int err = -ENOENT;
  239. struct ts_config *conf;
  240. struct ts_ops *ops;
  241. ops = lookup_ts_algo(algo);
  242. #ifdef CONFIG_KMOD
  243. /*
  244. * Why not always autoload you may ask. Some users are
  245. * in a situation where requesting a module may deadlock,
  246. * especially when the module is located on a NFS mount.
  247. */
  248. if (ops == NULL && flags & TS_AUTOLOAD) {
  249. request_module("ts_%s", algo);
  250. ops = lookup_ts_algo(algo);
  251. }
  252. #endif
  253. if (ops == NULL)
  254. goto errout;
  255. conf = ops->init(pattern, len, gfp_mask);
  256. if (IS_ERR(conf)) {
  257. err = PTR_ERR(conf);
  258. goto errout;
  259. }
  260. conf->ops = ops;
  261. return conf;
  262. errout:
  263. if (ops)
  264. module_put(ops->owner);
  265. return ERR_PTR(err);
  266. }
  267. /**
  268. * textsearch_destroy - destroy a search configuration
  269. * @conf: search configuration
  270. *
  271. * Releases all references of the configuration and frees
  272. * up the memory.
  273. */
  274. void textsearch_destroy(struct ts_config *conf)
  275. {
  276. if (conf->ops) {
  277. if (conf->ops->destroy)
  278. conf->ops->destroy(conf);
  279. module_put(conf->ops->owner);
  280. }
  281. kfree(conf);
  282. }
  283. EXPORT_SYMBOL(textsearch_register);
  284. EXPORT_SYMBOL(textsearch_unregister);
  285. EXPORT_SYMBOL(textsearch_prepare);
  286. EXPORT_SYMBOL(textsearch_find_continuous);
  287. EXPORT_SYMBOL(textsearch_destroy);