diff options
author | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-06-24 00:31:46 -0700 |
---|---|---|
committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-06-24 00:31:46 -0700 |
commit | 59a49e38711a146dc0bef4837c825b5422335460 (patch) | |
tree | 7e6e3d1850159f94e5b05d1c5775bd3cc87c3690 | |
parent | 52c1da39534fb382c061de58b65f678ad74b59f5 (diff) | |
parent | f2d368fa3ef90f2159d9e542303901ebf68144dd (diff) |
Merge rsync://rsync.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6
-rw-r--r-- | drivers/net/slip.c | 14 | ||||
-rw-r--r-- | include/linux/netdevice.h | 11 | ||||
-rw-r--r-- | include/linux/pkt_cls.h | 1 | ||||
-rw-r--r-- | include/linux/rtnetlink.h | 7 | ||||
-rw-r--r-- | include/linux/skbuff.h | 23 | ||||
-rw-r--r-- | include/linux/sysctl.h | 1 | ||||
-rw-r--r-- | include/linux/tc_ematch/tc_em_text.h | 19 | ||||
-rw-r--r-- | include/linux/tcp.h | 1 | ||||
-rw-r--r-- | include/linux/textsearch.h | 180 | ||||
-rw-r--r-- | include/linux/textsearch_fsm.h | 48 | ||||
-rw-r--r-- | include/net/tcp.h | 4 | ||||
-rw-r--r-- | lib/Kconfig | 29 | ||||
-rw-r--r-- | lib/Makefile | 4 | ||||
-rw-r--r-- | lib/textsearch.c | 317 | ||||
-rw-r--r-- | lib/ts_fsm.c | 338 | ||||
-rw-r--r-- | lib/ts_kmp.c | 145 | ||||
-rw-r--r-- | net/core/dev.c | 125 | ||||
-rw-r--r-- | net/core/skbuff.c | 157 | ||||
-rw-r--r-- | net/core/sysctl_net_core.c | 46 | ||||
-rw-r--r-- | net/ipv4/tcp.c | 31 | ||||
-rw-r--r-- | net/ipv4/tcp_cong.c | 46 | ||||
-rw-r--r-- | net/ipv4/tcp_ipv4.c | 2 | ||||
-rw-r--r-- | net/ipv6/tcp_ipv6.c | 2 | ||||
-rw-r--r-- | net/sched/Kconfig | 12 | ||||
-rw-r--r-- | net/sched/Makefile | 1 | ||||
-rw-r--r-- | net/sched/em_text.c | 157 |
26 files changed, 1538 insertions, 183 deletions
diff --git a/drivers/net/slip.c b/drivers/net/slip.c index 19112712daf..c79e0ad4ba0 100644 --- a/drivers/net/slip.c +++ b/drivers/net/slip.c @@ -198,18 +198,12 @@ err_exit: static void sl_free_bufs(struct slip *sl) { - void * tmp; - /* Free all SLIP frame buffers. */ - tmp = xchg(&sl->rbuff, NULL); - kfree(tmp); - tmp = xchg(&sl->xbuff, NULL); - kfree(tmp); + kfree(xchg(&sl->rbuff, NULL)); + kfree(xchg(&sl->xbuff, NULL)); #ifdef SL_INCLUDE_CSLIP - tmp = xchg(&sl->cbuff, NULL); - kfree(tmp); - if ((tmp = xchg(&sl->slcomp, NULL)) != NULL) - slhc_free(tmp); + kfree(xchg(&sl->cbuff, NULL)); + slhc_free(xchg(&sl->slcomp, NULL)); #endif } diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h index d89816ad642..3a0ed7f9e80 100644 --- a/include/linux/netdevice.h +++ b/include/linux/netdevice.h @@ -164,12 +164,6 @@ struct netif_rx_stats unsigned total; unsigned dropped; unsigned time_squeeze; - unsigned throttled; - unsigned fastroute_hit; - unsigned fastroute_success; - unsigned fastroute_defer; - unsigned fastroute_deferred_out; - unsigned fastroute_latency_reduction; unsigned cpu_collision; }; @@ -562,12 +556,9 @@ static inline int unregister_gifconf(unsigned int family) struct softnet_data { - int throttle; - int cng_level; - int avg_blog; + struct net_device *output_queue; struct sk_buff_head input_pkt_queue; struct list_head poll_list; - struct net_device *output_queue; struct sk_buff *completion_queue; struct net_device backlog_dev; /* Sorry. 8) */ diff --git a/include/linux/pkt_cls.h b/include/linux/pkt_cls.h index d2aa214d680..25d2d67c1fa 100644 --- a/include/linux/pkt_cls.h +++ b/include/linux/pkt_cls.h @@ -408,6 +408,7 @@ enum TCF_EM_NBYTE, TCF_EM_U32, TCF_EM_META, + TCF_EM_TEXT, __TCF_EM_MAX }; diff --git a/include/linux/rtnetlink.h b/include/linux/rtnetlink.h index e68dbf0bf57..d021888b58f 100644 --- a/include/linux/rtnetlink.h +++ b/include/linux/rtnetlink.h @@ -892,10 +892,13 @@ extern void __rta_fill(struct sk_buff *skb, int attrtype, int attrlen, const voi goto rtattr_failure; \ __rta_fill(skb, attrtype, attrlen, data); }) -#define RTA_PUT_NOHDR(skb, attrlen, data) \ +#define RTA_APPEND(skb, attrlen, data) \ ({ if (unlikely(skb_tailroom(skb) < (int)(attrlen))) \ goto rtattr_failure; \ - memcpy(skb_put(skb, RTA_ALIGN(attrlen)), data, attrlen); }) + memcpy(skb_put(skb, attrlen), data, attrlen); }) + +#define RTA_PUT_NOHDR(skb, attrlen, data) \ + RTA_APPEND(skb, RTA_ALIGN(attrlen), data) #define RTA_PUT_U8(skb, attrtype, value) \ ({ u8 _tmp = (value); \ diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h index d7c839a2184..416a2e4024b 100644 --- a/include/linux/skbuff.h +++ b/include/linux/skbuff.h @@ -27,6 +27,7 @@ #include <linux/highmem.h> #include <linux/poll.h> #include <linux/net.h> +#include <linux/textsearch.h> #include <net/checksum.h> #define HAVE_ALLOC_SKB /* For the drivers to know */ @@ -321,6 +322,28 @@ extern void skb_over_panic(struct sk_buff *skb, int len, extern void skb_under_panic(struct sk_buff *skb, int len, void *here); +struct skb_seq_state +{ + __u32 lower_offset; + __u32 upper_offset; + __u32 frag_idx; + __u32 stepped_offset; + struct sk_buff *root_skb; + struct sk_buff *cur_skb; + __u8 *frag_data; +}; + +extern void skb_prepare_seq_read(struct sk_buff *skb, + unsigned int from, unsigned int to, + struct skb_seq_state *st); +extern unsigned int skb_seq_read(unsigned int consumed, const u8 **data, + struct skb_seq_state *st); +extern void skb_abort_seq_read(struct skb_seq_state *st); + +extern unsigned int skb_find_text(struct sk_buff *skb, unsigned int from, + unsigned int to, struct ts_config *config, + struct ts_state *state); + /* Internal */ #define skb_shinfo(SKB) ((struct skb_shared_info *)((SKB)->end)) diff --git a/include/linux/sysctl.h b/include/linux/sysctl.h index 72965bfe6cf..ebfe1250f0a 100644 --- a/include/linux/sysctl.h +++ b/include/linux/sysctl.h @@ -243,6 +243,7 @@ enum NET_CORE_MOD_CONG=16, NET_CORE_DEV_WEIGHT=17, NET_CORE_SOMAXCONN=18, + NET_CORE_BUDGET=19, }; /* /proc/sys/net/ethernet */ diff --git a/include/linux/tc_ematch/tc_em_text.h b/include/linux/tc_ematch/tc_em_text.h new file mode 100644 index 00000000000..7cd43e99c7f --- /dev/null +++ b/include/linux/tc_ematch/tc_em_text.h @@ -0,0 +1,19 @@ +#ifndef __LINUX_TC_EM_TEXT_H +#define __LINUX_TC_EM_TEXT_H + +#include <linux/pkt_cls.h> + +#define TC_EM_TEXT_ALGOSIZ 16 + +struct tcf_em_text +{ + char algo[TC_EM_TEXT_ALGOSIZ]; + __u16 from_offset; + __u16 to_offset; + __u16 pattern_len; + __u8 from_layer:4; + __u8 to_layer:4; + __u8 pad; +}; + +#endif diff --git a/include/linux/tcp.h b/include/linux/tcp.h index 3ea75dd6640..dfd93d03f5d 100644 --- a/include/linux/tcp.h +++ b/include/linux/tcp.h @@ -127,6 +127,7 @@ enum { #define TCP_WINDOW_CLAMP 10 /* Bound advertised window */ #define TCP_INFO 11 /* Information about this connection. */ #define TCP_QUICKACK 12 /* Block/reenable quick acks */ +#define TCP_CONGESTION 13 /* Congestion control algorithm */ #define TCPI_OPT_TIMESTAMPS 1 #define TCPI_OPT_SACK 2 diff --git a/include/linux/textsearch.h b/include/linux/textsearch.h new file mode 100644 index 00000000000..941f45ac117 --- /dev/null +++ b/include/linux/textsearch.h @@ -0,0 +1,180 @@ +#ifndef __LINUX_TEXTSEARCH_H +#define __LINUX_TEXTSEARCH_H + +#ifdef __KERNEL__ + +#include <linux/types.h> +#include <linux/list.h> +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/err.h> + +struct ts_config; + +/** + * TS_AUTOLOAD - Automatically load textsearch modules when needed + */ +#define TS_AUTOLOAD 1 + +/** + * struct ts_state - search state + * @offset: offset for next match + * @cb: control buffer, for persistant variables of get_next_block() + */ +struct ts_state +{ + unsigned int offset; + char cb[40]; +}; + +/** + * struct ts_ops - search module operations + * @name: name of search algorithm + * @init: initialization function to prepare a search + * @find: find the next occurrence of the pattern + * @destroy: destroy algorithm specific parts of a search configuration + * @get_pattern: return head of pattern + * @get_pattern_len: return length of pattern + * @owner: module reference to algorithm + */ +struct ts_ops +{ + const char *name; + struct ts_config * (*init)(const void *, unsigned int, int); + unsigned int (*find)(struct ts_config *, + struct ts_state *); + void (*destroy)(struct ts_config *); + void * (*get_pattern)(struct ts_config *); + unsigned int (*get_pattern_len)(struct ts_config *); + struct module *owner; + struct list_head list; +}; + +/** + * struct ts_config - search configuration + * @ops: operations of chosen algorithm + * @get_next_block: callback to fetch the next block to search in + * @finish: callback to finalize a search + */ +struct ts_config +{ + struct ts_ops *ops; + + /** + * get_next_block - fetch next block of data + * @consumed: number of bytes consumed by the caller + * @dst: destination buffer + * @conf: search configuration + * @state: search state + * + * Called repeatedly until 0 is returned. Must assign the + * head of the next block of data to &*dst and return the length + * of the block or 0 if at the end. consumed == 0 indicates + * a new search. May store/read persistant values in state->cb. + */ + unsigned int (*get_next_block)(unsigned int consumed, + const u8 **dst, + struct ts_config *conf, + struct ts_state *state); + + /** + * finish - finalize/clean a series of get_next_block() calls + * @conf: search configuration + * @state: search state + * + * Called after the last use of get_next_block(), may be used + * to cleanup any leftovers. + */ + void (*finish)(struct ts_config *conf, + struct ts_state *state); +}; + +/** + * textsearch_next - continue searching for a pattern + * @conf: search configuration + * @state: search state + * + * Continues a search looking for more occurrences of the pattern. + * textsearch_find() must be called to find the first occurrence + * in order to reset the state. + * + * Returns the position of the next occurrence of the pattern or + * UINT_MAX if not match was found. + */ +static inline unsigned int textsearch_next(struct ts_config *conf, + struct ts_state *state) +{ + unsigned int ret = conf->ops->find(conf, state); + + if (conf->finish) + conf->finish(conf, state); + + return ret; +} + +/** + * textsearch_find - start searching for a pattern + * @conf: search configuration + * @state: search state + * + * Returns the position of first occurrence of the pattern or + * UINT_MAX if no match was found. + */ +static inline unsigned int textsearch_find(struct ts_config *conf, + struct ts_state *state) +{ + state->offset = 0; + return textsearch_next(conf, state); +} + +/** + * textsearch_get_pattern - return head of the pattern + * @conf: search configuration + */ +static inline void *textsearch_get_pattern(struct ts_config *conf) +{ + return conf->ops->get_pattern(conf); +} + +/** + * textsearch_get_pattern_len - return length of the pattern + * @conf: search configuration + */ +static inline unsigned int textsearch_get_pattern_len(struct ts_config *conf) +{ + return conf->ops->get_pattern_len(conf); +} + +extern int textsearch_register(struct ts_ops *); +extern int textsearch_unregister(struct ts_ops *); +extern struct ts_config *textsearch_prepare(const char *, const void *, + unsigned int, int, int); +extern void textsearch_destroy(struct ts_config *conf); +extern unsigned int textsearch_find_continuous(struct ts_config *, + struct ts_state *, + const void *, unsigned int); + + +#define TS_PRIV_ALIGNTO 8 +#define TS_PRIV_ALIGN(len) (((len) + TS_PRIV_ALIGNTO-1) & ~(TS_PRIV_ALIGNTO-1)) + +static inline struct ts_config *alloc_ts_config(size_t payload, int gfp_mask) +{ + struct ts_config *conf; + + conf = kmalloc(TS_PRIV_ALIGN(sizeof(*conf)) + payload, gfp_mask); + if (conf == NULL) + return ERR_PTR(-ENOMEM); + + memset(conf, 0, TS_PRIV_ALIGN(sizeof(*conf)) + payload); + return conf; +} + +static inline void *ts_config_priv(struct ts_config *conf) +{ + return ((u8 *) conf + TS_PRIV_ALIGN(sizeof(struct ts_config))); +} + +#endif /* __KERNEL__ */ + +#endif diff --git a/include/linux/textsearch_fsm.h b/include/linux/textsearch_fsm.h new file mode 100644 index 00000000000..fdfa078c66e --- /dev/null +++ b/include/linux/textsearch_fsm.h @@ -0,0 +1,48 @@ +#ifndef __LINUX_TEXTSEARCH_FSM_H +#define __LINUX_TEXTSEARCH_FSM_H + +#include <linux/types.h> + +enum { + TS_FSM_SPECIFIC, /* specific character */ + TS_FSM_WILDCARD, /* any character */ + TS_FSM_DIGIT, /* isdigit() */ + TS_FSM_XDIGIT, /* isxdigit() */ + TS_FSM_PRINT, /* isprint() */ + TS_FSM_ALPHA, /* isalpha() */ + TS_FSM_ALNUM, /* isalnum() */ + TS_FSM_ASCII, /* isascii() */ + TS_FSM_CNTRL, /* iscntrl() */ + TS_FSM_GRAPH, /* isgraph() */ + TS_FSM_LOWER, /* islower() */ + TS_FSM_UPPER, /* isupper() */ + TS_FSM_PUNCT, /* ispunct() */ + TS_FSM_SPACE, /* isspace() */ + __TS_FSM_TYPE_MAX, +}; +#define TS_FSM_TYPE_MAX (__TS_FSM_TYPE_MAX - 1) + +enum { + TS_FSM_SINGLE, /* 1 occurrence */ + TS_FSM_PERHAPS, /* 1 or 0 occurrence */ + TS_FSM_ANY, /* 0..n occurrences */ + TS_FSM_MULTI, /* 1..n occurrences */ + TS_FSM_HEAD_IGNORE, /* 0..n ignored occurrences at head */ + __TS_FSM_RECUR_MAX, +}; +#define TS_FSM_RECUR_MAX (__TS_FSM_RECUR_MAX - 1) + +/** + * struct ts_fsm_token - state machine token (state) + * @type: type of token + * @recur: number of recurrences + * @value: character value for TS_FSM_SPECIFIC + */ +struct ts_fsm_token +{ + __u16 type; + __u8 recur; + __u8 value; +}; + +#endif diff --git a/include/net/tcp.h b/include/net/tcp.h index e427cf35915..ec9e20c2717 100644 --- a/include/net/tcp.h +++ b/include/net/tcp.h @@ -1162,12 +1162,14 @@ extern void tcp_init_congestion_control(struct tcp_sock *tp); extern void tcp_cleanup_congestion_control(struct tcp_sock *tp); extern int tcp_set_default_congestion_control(const char *name); extern void tcp_get_default_congestion_control(char *name); +extern int tcp_set_congestion_control(struct tcp_sock *tp, const char *name); -extern struct tcp_congestion_ops tcp_reno; +extern struct tcp_congestion_ops tcp_init_congestion_ops; extern u32 tcp_reno_ssthresh(struct tcp_sock *tp); extern void tcp_reno_cong_avoid(struct tcp_sock *tp, u32 ack, u32 rtt, u32 in_flight, int flag); extern u32 tcp_reno_min_cwnd(struct tcp_sock *tp); +extern struct tcp_congestion_ops tcp_reno; static inline void tcp_set_ca_state(struct tcp_sock *tp, u8 ca_state) { diff --git a/lib/Kconfig b/lib/Kconfig index 2d4d4e3bc4a..455833a9e31 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -63,5 +63,32 @@ config REED_SOLOMON_ENC16 config REED_SOLOMON_DEC16 boolean -endmenu +config TEXTSEARCH + boolean "Textsearch infrastructure" + default y + help + Say Y here if you want to provide a textsearch infrastructure + to other subsystems. + +config TEXTSEARCH_KMP + depends on TEXTSEARCH + tristate "Knuth-Morris-Pratt" + help + Say Y here if you want to be able to search text using the + Knuth-Morris-Pratt textsearch algorithm. + To compile this code as a module, choose M here: the + module will be called ts_kmp. + +config TEXTSEARCH_FSM + depends on TEXTSEARCH + tristate "Finite state machine" + help + Say Y here if you want to be able to search text using a + naive finite state machine approach implementing a subset + of regular expressions. + + To compile this code as a module, choose M here: the + module will be called ts_fsm. + +endmenu diff --git a/lib/Makefile b/lib/Makefile index dcb4231916e..beed1585294 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -36,6 +36,10 @@ obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ +obj-$(CONFIG_TEXTSEARCH) += textsearch.o +obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o +obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/textsearch.c b/lib/textsearch.c new file mode 100644 index 00000000000..1e934c196f0 --- /dev/null +++ b/lib/textsearch.c @@ -0,0 +1,317 @@ +/* + * 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> + * Pablo Neira Ayuso <pablo@eurodev.net> + * + * ========================================================================== + * + * INTRODUCTION + * + * The textsearch infrastructure provides text searching facitilies for + * 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 + * to the algorihtm to store persistant variables. + * (4) Core eventually resets the search offset and forwards the find() + * request to the algorithm. + * (5) Algorithm calls get_next_block() provided by the user continously + * 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 + * by calling textsearch_prepare() specyfing the searching algorithm and + * the pattern to look for. The returned configuration may then be used + * for an arbitary amount of times and even in parallel as long as a + * separate struct ts_state variable is provided to every instance. + * + * 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 + * the position of the first occurrence of the patern or UINT_MAX if + * no match was found. Subsequent occurences can be found by calling + * 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/config.h> +#include <linux/module.h> +#include <linux/types.h> +#include <linux/string.h> +#include <linux/init.h> +#include <linux/rcupdate.h> +#include <linux/err.h> +#include <linux/textsearch.h> + +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; +} + +/** + * 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; +} + +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 + * UINT_MAX if no occurrence was found. + */ +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); +} + +/** + * 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 + * configuration for the specified pattern. Upon completion all + * necessary refcnts are held and the configuration must be put back + * using textsearch_put() after usage. + * + * Note: The format of the pattern may not be compatible between + * the various search algorithms. + * + * Returns a new textsearch configuration according to the specified + * parameters or a ERR_PTR(). + */ +struct ts_config *textsearch_prepare(const char *algo, const void *pattern, + unsigned int len, int gfp_mask, int flags) +{ + int err = -ENOENT; + struct ts_config *conf; + struct ts_ops *ops; + + ops = lookup_ts_algo(algo); +#ifdef CONFIG_KMOD + /* + * 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; + + conf = ops->init(pattern, len, gfp_mask); + 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); +} + +/** + * 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_register); +EXPORT_SYMBOL(textsearch_unregister); +EXPORT_SYMBOL(textsearch_prepare); +EXPORT_SYMBOL(textsearch_find_continuous); +EXPORT_SYMBOL(textsearch_destroy); diff --git a/lib/ts_fsm.c b/lib/ts_fsm.c new file mode 100644 index 00000000000..d27c0a07294 --- /dev/null +++ b/lib/ts_fsm.c @@ -0,0 +1,338 @@ +/* + * lib/ts_fsm.c A naive finite state machine text search approach + * + * 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> + * + * ========================================================================== + * + * A finite state machine consists of n states (struct ts_fsm_token) + * representing the pattern as a finite automation. The data is read + * sequentially on a octet basis. Every state token specifies the number + * of recurrences and the type of value accepted which can be either a + * specific character or ctype based set of characters. The available + * type of recurrences include 1, (0|1), [0 n], and [1 n]. + * + * The algorithm differs between strict/non-strict mode specyfing + * whether the pattern has to start at the first octect. Strict mode + * is enabled by default and can be disabled by inserting + * TS_FSM_HEAD_IGNORE as the first token in the chain. + * + * The runtime performance of the algorithm should be around O(n), + * however while in strict mode the average runtime can be better. + */ + +#include <linux/config.h> +#include <linux/module.h> +#include <linux/types.h> +#include <linux/string.h> +#include <linux/ctype.h> +#include <linux/textsearch.h> +#include <linux/textsearch_fsm.h> + +struct ts_fsm +{ + unsigned int ntokens; + struct ts_fsm_token tokens[0]; +}; + +/* other values derived from ctype.h */ +#define _A 0x100 /* ascii */ +#define _W 0x200 /* wildcard */ + +/* Map to _ctype flags and some magic numbers */ +static u16 token_map[TS_FSM_TYPE_MAX+1] = { + [TS_FSM_SPECIFIC] = 0, + [TS_FSM_WILDCARD] = _W, + [TS_FSM_CNTRL] = _C, + [TS_FSM_LOWER] = _L, + [TS_FSM_UPPER] = _U, + [TS_FSM_PUNCT] = _P, + [TS_FSM_SPACE] = _S, + [TS_FSM_DIGIT] = _D, + [TS_FSM_XDIGIT] = _D | _X, + [TS_FSM_ALPHA] = _U | _L, + [TS_FSM_ALNUM] = _U | _L | _D, + [TS_FSM_PRINT] = _P | _U | _L | _D | _SP, + [TS_FSM_GRAPH] = _P | _U | _L | _D, + [TS_FSM_ASCII] = _A, +}; + +static u16 token_lookup_tbl[256] = { +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 0- 3 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 4- 7 */ +_W|_A|_C, _W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C|_S, /* 8- 11 */ +_W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C, _W|_A|_C, /* 12- 15 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 16- 19 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 20- 23 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 24- 27 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 28- 31 */ +_W|_A|_S|_SP, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 32- 35 */ +_W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 36- 39 */ +_W|_A|_P, _W |