textsearch infrastructure + skb_find_text()

The patch below is a report on the current state of the textsearch infrastructure and its first user skb_find_text(). The textsearch is kept as simple as possible but advanced enough to handle non-linear data such as skb fragments. Unlike in many other approaches the text input is not seen as a single pointer but rather as a continuously called callback get_text() until 0 is returned allowing to search on any kind of data and to implement customized from-to limits.

The patch is separated into 3 parts, the first one being the textsearch infrastructure itself followed by a simple Knuth-Morris-Pratt implementation for reference. I'm also working on what could be called the smallest regular expression implementation ever but I left that out for now since it still has issues. Last but not least the function skb_find_text() written in a hurry and probably not yet correct but you should get the idea. From a userspace perspective the first user will be an ematch but writing it will be peanuts so I left it out for now.

Basically what it looks like right now is:

int pos;
struct ts_state;
struct ts_config *conf = textsearch_prepare("kmp", "hanky", 5, GFP_KERNEL, 1);

/* search for "hanky" at offset 20 until end of packet */

for (pos = skb_find_text(skb, 20, INT_MAX, conf, &state;
     pos >= 0;
     pos = textsearch_next(conf, &state)) {
        printk("Need a hanky? I found one at offset %d.\n", pos);
}

textsearch_put(conf);
kfree(conf);

You might wonder about the 1 given to _prepare(), it indicates whether to autoload modules because the ematches will need it to be able to drop rtnl sem.

The code is not tested and cerainly not bug free yet but should compile.

Thoughts?

diff -X dontdiff -Nru linux-2.6.12-rc3.orig/include/linux/textsearch.h linux-2.6.12-rc3/include/linux/textsearch.h
@@ -0,0 +1,169 @@
+#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;
+
+/**
+ * struct ts_state - textsearch state
+ * @offset: current offset for next match
+ * @args: for persistant variables of get_text()
+ */
+struct ts_state
+{
+	int			offset;
+	long			args[6];
+};
+
+/**
+ * struct ts_ops - textsearch operations
+ * @name: name of search algorithm
+ * @init: called upon initialization to prepare a search
+ * @find: does the actual matching on a prepared configuration
+ * @owner: reference to algorithm module if existent
+ * @list: operations list we are on
+ */
+struct ts_ops
+{
+	const char		*name;
+	struct ts_config *	(*init)(const unsigned char *, size_t, int);
+	int			(*find)(struct ts_config *,
+					struct ts_state *);
+	struct module		*owner;
+	struct list_head	list;
+};
+
+/**
+ * struct ts_config - textsearch configuration
+ * @ops: textsearch operations
+ * @get_text: callback to fetch text to search in
+ * @len: length of pattern
+ */
+struct ts_config
+{
+	struct ts_ops		*ops;
+
+	/**
+	 * get_text - return next chunk of text
+	 * @offset: Number of bytes consumed by the matcher
+	 * @dst: destination buffer
+	 * @conf: search configuration
+	 * @state: search state
+	 *
+	 * Gets called repeatedly until 0 is returned.Must assign a pointer
+	 * to the start of the next chunk of text to *dst and return the
+	 * length of the chunk or 0 if at the end. offset==0 indicates
+	 * a new search. May store/read persistant values in state->args[].
+	 */
+	int			(*get_text)(int offset, unsigned char **dst,
+					    struct ts_config *conf,
+					    struct ts_state *state);
+
+	/**
+	 * finish - called when the matching has been completed successful
+	 *          or not.
+	 * @conf: search configuration
+	 * @state: search state
+	 */
+	void			(*finish)(struct ts_config *conf,
+					  struct ts_state *state);
+	int			pattern_len;
+};
+
+/* Do no use this function directly */
+static inline int __textsearch_find(struct ts_config *conf,
+				    struct ts_state *state)
+{
+	int ret = conf->ops->find(conf, state);
+
+	if (conf->finish)
+		conf->finish(conf, state);
+
+	return ret;
+}
+
+/**
+ * textsearch_find - search for a pattern in a text
+ * @conf: search configuration
+ * @state: search state
+ *
+ * Peforms the actual search on the prepared configuration.
+ *
+ * Returns the position of first occurrence of the pattern or a
+ *         negative number if no match was found.
+ */ 
+static inline int textsearch_find(struct ts_config *conf,
+				   struct ts_state *state)
+{
+	state->offset = 0;
+	return __textsearch_find(conf, state);
+}
+
+/**
+ * textsearch_next - continue search for a pattern in a text
+ * @conf: search configuration
+ * @state: search state
+ *
+ * Continues a search looking for more occurrences of the pattern.
+ * You must call textsearch_find() to search the first occurrence
+ * in order to reset the state.
+ *
+ * Returns the position of next occurance of the pattern or a
+ *         negative number if no match was found.
+ */ 
+static inline int textsearch_next(struct ts_config *conf,
+				  struct ts_state *state)
+{
+	state->offset += conf->pattern_len;
+	return __textsearch_find(conf, state);
+}
+
+/**
+ * textsearch_put - give back a textsearch configuration
+ * @conf: search configuration
+ *
+ * Releases all references of the configuration. Must be
+ * called prior to freeing the object.
+ */
+static inline void textsearch_put(struct ts_config *conf)
+{
+	if (conf->ops)
+		module_put(conf->ops->owner);
+}
+
+/**
+ * alloc_ts_config - allocate a textsearch configuration
+ * @payload: size of additional module specific data required
+ * @gfp_mask: allocation mask
+ *
+ * Returns a new, empty textsearch configuration or a ERR_PTR().
+ */
+static inline struct ts_config *alloc_ts_config(size_t payload, int gfp_mask)
+{
+	struct ts_config *conf;
+
+	conf = kmalloc(sizeof(*conf) + payload, gfp_mask);
+	if (conf == NULL)
+		return ERR_PTR(-ENOMEM);
+
+	memset(conf, 0, sizeof(*conf) + payload);
+	return conf;
+}
+
+extern int textsearch_register(struct ts_ops *);
+extern int textsearch_unregister(struct ts_ops *);
+extern struct ts_config *textsearch_prepare(const char *, const unsigned char *,
+					    size_t, int, int);
+extern int textsearch_find_continuous(struct ts_config *, struct ts_state *,
+				      const unsigned char *, size_t);
+
+#endif /* __KERNEL__ */
+
+#endif

diff -X dontdiff -Nru linux-2.6.12-rc3.orig/include/linux/skbuff.h linux-2.6.12-rc3/include/linux/skbuff.h
@@ -28,6 +28,7 @@
 #include <linux/poll.h>
 #include <linux/net.h>
 #include <net/checksum.h>
+#include <linux/textsearch.h>
 
 #define HAVE_ALLOC_SKB		/* For the drivers to know */
 #define HAVE_ALIGNABLE_SKB	/* Ditto 8)		   */

@@ -1186,6 +1187,9 @@
 extern void	       skb_split(struct sk_buff *skb,
 				 struct sk_buff *skb1, const u32 len);
 
+extern int skb_find_text(struct sk_buff *skb, int from, int to,
+			 struct ts_config *config, struct ts_state *state);
+
 static inline void *skb_header_pointer(const struct sk_buff *skb, int offset,
 				       int len, void *buffer)
 {

How is this different from libqsearch? IIRC, it also kept pointers and callbacks.

BTW, I hope theres sync with libqsearch - at least some canibalization of ideas.
Also hopefully, pluggin of ne algorithms is trivial (e.g boyer-moore could be included in addition to kmp etc)

nice

I have a lot of questions:
- does a string have to be terminated by \0?
- do you keep state of the string from the begining? ex: how do you know that preceeding "hanky" was "Need a"?
- all sorts of limits: how long is the string? etc
- what happens if a string spans multiple skbs or even multiple fragments?

do you really wanna leave that decision upto the user?

I dont have time to look at the patch to sufficiently critique it, but it looks like a good start - maybe this weekend.
It would be nice to have other utilities which could be loaded eg; case compare, regualr expressions, strchr after you match, etc
Of course all this to be followed by actions such as strok etc. Probably all this is a layer above this - but essentially when you are doing this keep the desire to do this in mind.

cheers,
jamal

* jamal <[email protected]> 2005-05-05 08:42

The main difference is that my infrastructure is much simpler.

I read the libqsearch code but fixing up all the issues required for my use would have taken up more time than writing up something new.

Very simple, ts_kmp.c is 108 lines whereas simple.c in libqsearch is over 500.

All strings are length terminated.

I store the shift of a match in struct ts_state, add the length of the pattern in the call to textsearch_next() and provide this shift as offset to the get_text() callback.

Both the length of a pattern and the length of a text block is limited by INT_MAX. However, since there can be an arbitary number of blocks there is no limit in the text length. Depending on the search algorithm there might be more limits, for example kmp uses unsigned int for each prefix table entry so this limits the length of the pattern as well (theoretically).

This was the single most important requirement. Actually you can compose the text out of anything. I already wrote some code to handle paged skbs and multiple skbs can be implemented the same way. You could for example store a ts_state per conntrack and call textsearch_next continuously until you find a match. Would require some magic in the get_text() but shouldn't be too hard.

We have to, otherwise we can't use it in ematches without the risk of deadlocks. There is no way around than have the caller drop its locks and call prepare again with no locks held, at least I'm not aware of one.

Indeed, I'm working on the regular expression thing but it has some issues with textsearch_next() for patterns like .+abc.+ which I want to resolve first.

Hi Thomas,

I haven't got too much time to review this stuff in deep though. Impressive work, but I still miss something, some comments:

- A custom destroy function in ts_ops.
- I don't see a way to look for matches in fragments. I mean, say we've got "dancing " in a fragment and "chicken" in the next one. Currently we don't get a match.
- I particularly like Rusty's skb iterator, well you've refactored that code anyway.

I've been reworking the framework for string matching that I sent you two/three months ago, you've definitely worked on a good base. Since then I've introduced a lot of changes and actually I've been testing it (ick, that means that we've clashed!).

I think that I can merge both works and then roll on. I still need more time to study more in deep your proposition.

--
Pablo

* Pablo Neira <[email protected]> 2005-05-05 19:02

Sure, can be added once we need it. Currently none of my algorithms allocate anything on their own. Might be worth to change the API and replace textsearch_put with textesearch_destroy also freeing the configuration though.

This is implemented in skb_find_text(), I just looked through rusty's code and it's very simliar so we could make the args in ts_state a union of long args[6] and char cb[XXX] so we can store skb_iter in there.

I don't think so, my approach is quite different and allows for optimized text searches over fragments, multiple skbs, etc without any hacks around the fragment borders. It's a lot more generic allowing it to be in lib/ so it can be used from other subsystem as well.

Sure go ahead but please don't merge it into netfilter, a) the core really is supposed to be in lib, and b) I don't want any netfilter dependencies in my ematches.

that's fine

Yes, we could just use one of those args in ts_state to store if we found a partial match or not.

Boyer-Moore requires such hack to look for matches around the fragment borders. But no problem, such hack will go inside the bm_find function.

Sure, your approach is definitely more generic because I just thought about using such string matching framework for net apps, it's different from that point of view, but I still see things that reminds me to my proposed framework, say that ts_state thing ;).

No problem mate. Just curious about something, since this stuff will live under lib, what kind of applications in kernel space could use this string matching framework ? I bet that non-net kernel guys will surely ask about it ;->

I'll be back working on this stuff next week, expect some feedback.

--
Pablo

* Pablo Neira <[email protected]> 2005-05-06 03:33

This is not required, I will elaborate the core logic to clarify this. I guess you still think of the logic as:

function find-text(pattern)
foreach text-segment do

    call search-bm(text-segment, pattern);

done
end

This is what most people naturally think of when dealing with this problem and it might be sufficient for many situations, however it requires the searching algorithm to store its state in some persistent memory which can be troublesome depending on the volume of these variables.

My approach is to save the state of the text fetching progress and have the algorithm handle the fetching of new data (if needed), i.e:

function serch-bm(pattern, get-text-callback)
while get-text-callback() returns more data do
do the matching here...
done
end

function find-text(pattern)
call search-bm(pattern, get-text-callback);
end

This allows the searching algorithm to see the text as a continuous byte stream. The get_text() callback is like a char device, altough it returns data in variable sized blocks, there is no random access.

Why? Because it dramatically simplifies the searching algorithms since they can decide when to fetch the next block which is absolutely essential for cases like regular expression where the state machine gets quite complex and a single entry point (i.e. leaving the function and enter it again with new data) would make things much more complex. Minor advantages are a) the get_text() implementation is usually quite small and will hopefully not mess up the cacheline optimizations of the actual searching loop and
b) it allows the searching algorithm to do prefetching.

<< coffee break >>

Now on to the subject of matching over multiple skbs, in a perfect world we can try to do async searching by storing the partial match state in the conntrack entry but then again what do we do when we find a partial match in a skb? Drop it? We can't access the next skb or fragment just now to see if the full pattern is present. So what this would lead to is that we let the handshake and some payload pass until we find the skb that successfully ends a partial match. This is basically what IOS and JunOS do (correct me if I'm wrong). A common use case for this is to filter out malicious HTTP requests and other easy to identify data that might harm a service that is vulnerable but has no fix available just yet. In order to avoid DoS certain limits must be established such as maximum number of skbs or maximum payload scanned before aborting but most of these limits can be worked around for example by pretending huge HTTP headers in front of the malicious header line and it will be very hard to find a breakeven to actually be able to filter out some of it while not allowing a DoS due to massive filtering.

Can we avoid letting through the initial handshake? Yes but it's probably not worth the effort. Will we be able to ultimatively solve the filtering facitily vs DoS vulnerability issue? No. Can we avoid letting through previous skbs which could do harm as well but only a partial match has been found? Not at this level or without nasty hacks such as acking the data but not passing it up. Worth it? Probably not. To my understanding it is not worth to try too hard and be perfect, I see the textsearch filtering as nice to have for filtering on the first few dozen bytes of the initial payload skb typically carrying enough headers to classify on layer7 basis. If someone thinks the small probability of having a match just between 2 fragments is important then please go ahead and put the matching state into ts_state as well.

Note that your state variable stores the matching state and ts_state stores the state of the get_text() progress.

It definitely belongs into lib/ to my understanding, nobody gets hurt by adding it there and the chances that someone other subsystem having need for it are not that low.

One example (silly one though) that I did out of curiosity is a sys_findtext taking an inode returning the first match. It simply iterates over all blocks belonging to the file making use of the buffer cache if possible. It's really fast. ;->

On Fri, 2005-06-05 at 14:36 +0200, Thomas Graf wrote:
[..]

[..]

I dont see any difference between the two in terms of state storage. Can you really avoid storing state? Can you give an example?

The other scheme is to have the callback return a code which says "get me more text" or " enough/done" in which case the state machine for the search alg is no different in both cases.

It depends on the search algorithm - if it is small, you benefit from either scheme. If it is large, you loose in both.

I am trying to sink this in; prefetching would be valuable for regexp, but why would the other scheme not be able to do it?

I have to run to work while you get coffee ;->
I will read the rest later.

cheers,
jamal

* jamal <[email protected]> 2005-05-06 09:04

The state is kept on the stack since there is only one call to the algorithm's search function per match iteration. Look at the code below, it is called once and fetches the data continuously until EOF or a match has been found.

get_text() sets *text to the start of the next buffer at the virtual absolute position `consumed' and returns the length of the new buffer.

	int i, q = 0, consumed = state->offset;

	for (;;) {
		text_len = conf->get_text(consumed, &text, conf, state);

		if (text_len == 0)
			break; /* no match found */

		for (i = 0; i < text_len; i++) {
			while (q > 0 && pattern[q] != text[i])
				q = prefix_tbl[q - 1];
			if (pattern[q] == text[i])
				q++;
			if (q == pattern_len) {
				state->offset = consumed + i - pattern_len + 1;
				return state->offset;
			}
		}

		consumed += text_len;
	}

A very simple implementation of get_text() could look like this:

static inline int get_linear_text(int offset, unsigned char **text,
struct ts_config *conf, struct ts_state *state)

{
	unsigned char *string = (unsigned char *) state->args[0];
	size_t len = state->args[1];

	if (offset < len) {
		*text = string + offset;
		return len - offset;
	} else
		return 0;
}

As you can see, it expects a char * in args[0] and the length of it in args[1]. All it does is check whether all bytes have been read already and if not return the remaining part of the buffer so even if the search algorithm can't consume all the bytes returned it will still work as expected.

In the case of interruptable search algorithms, we have to make sure to save enough state information to continue at the same position. Surely this is no problem with KMP or BM but gets real complex in the case of automata based searching algorithms such as regular expressions. It would mean to have a set of conditional jumps into the algorithms, I tried it and it really gets complex.

Example: Assume we are are processing a regular expression with automata approach and are currently look at a 'ANY' (+) recurrence. First thing we do is check if there are more torkens to parse, if not we can return true immediately. Otherwise we have to do a look ahead on the pattern and cycle through the text looking if we can find the token following the 'ANY' recurrence, e.g.

pattern := "c*\d+A"
current-token := \d+
next-token := 'A'
text := "ccc123A"
current-character := text[3] ('1')

while NOT next-token matches current-character do
if current-token matches current-character then
goto no-match
endif
current-character := next(text) proceed-to-next-character()
/* At this position we'd have to return, fetch new text and come back
right here with the exact same state, difficult huh? */
if NOT more text to process then
goto no-match
endif
endwhile

Not sure if this is clear out of context but maybe it gives you an idea why it is easier to maintain state of get_text() rather than the state of a whole searching algorithm.

That's true, smallish algorithms such as KMP and BM don't gain much but for complex algorithms such as regexp my approach really is a lot faster.

I'm really not an expert on the validity of L1 caches and how to optimize it best but I believe that the less memory movement is in between the more likely prefetching helps? Both schemes involve a switch to another stack namespace but get_text() tends to be a lot smaller and less intrusive than a store & reload of a complex state machine. I really can't tell which is better regarding this subject without trying it out actually.

Ok, makes sense - in the case of a string spanning multi skbs, i suppose it wouldnt matter, correct?

[..]

I got it. I suppose in the case of text contained within one skb this would be an improvement (spanning across multi-skb should be no difference; an improvemengt nonetheless)

Sorry - I thought you were talking about pre-fetching text as in lookahead for text in a regexp state machine.
I am not sure i see the L1 cache connection. Both seem to have tight for loops and depending on the algorithm there would be no difference in cache warmth afaics. Infact your scheme may suffer more because it has a lot of stuff on the stack. However, playing around with the code is the only way to find out.

cheers,
jamal

* Jamal Hadi Salim <[email protected]> 2005-05-07 09:03

Strings spanning multiple skbs can be handled just like a paged skbs _iff_ all skbs are known at the point the search starts, otherwise we'll need more trickering.

You're probably right, I suspect mine to perform better because in a typical search there is less work to do per loop and the interruption to fetch the next block of text is less intrusive. Time will tell.

Quite silly regular expression implementation for textsearch infrastructure. Still has issues with textsearch_next() and can probably be optimized a lot but should be a good base to work on.

diff -Nru -X dontdiff linux-2.6.12-rc3.orig/include/linux/textsearch_regexp.h linux-2.6.12-rc3/include/linux/textsearch_regexp.h
@@ -0,0 +1,47 @@
+#ifndef __LINUX_TEXTSEARCH_REGEXP_H
+#define __LINUX_TEXTSEARCH_REGEXP_H
+
+#include <linux/types.h>
+
+enum {
+	TS_RE_SPECIFIC,		/* specific character */
+	TS_RE_WILDCARD,		/* any character */
+	TS_RE_DIGIT,		/* isdigit() */
+	TS_RE_XDIGIT,		/* isxdigit() */
+	TS_RE_PRINT,		/* isprint() */
+	TS_RE_ALPHA,		/* isalpha() */
+	TS_RE_ALNUM,		/* isalnum() */
+	TS_RE_ASCII,		/* isascii() */
+	TS_RE_CNTRL,		/* iscntrl() */
+	TS_RE_GRAPH,		/* isgraph() */
+	TS_RE_LOWER,		/* islower() */
+	TS_RE_UPPER,		/* isupper() */
+	TS_RE_PUNCT,		/* ispunct() */
+	TS_RE_SPACE,		/* isspace() */
+	__TS_RE_TYPE_MAX,
+};
+#define TS_RE_TYPE_MAX (__TS_RE_TYPE_MAX - 1)
+
+enum {
+	TS_RE_SINGLE,		/* 1 occurrence */
+	TS_RE_PERHAPS,		/* 1 or 0 occurrence */
+	TS_RE_ANY,		/* 0..n occurrences */
+	TS_RE_MULTI,		/* 1..n occurrences */
+	__TS_RE_RECUR_MAX,
+};
+#define TS_RE_RECUR_MAX (__TS_RE_RECUR_MAX - 1)
+
+/**
+ * struct ts_regexp_token - regular expression token
+ * @type: type of token
+ * @recur: number of recurrences
+ * @value: character value for TS_RE_SPECIFIC
+ */
+struct ts_regexp_token
+{
+	__u16		type;
+	__u8		recur;
+	__u8		value;
+};
+
+#endif

In article <[email protected]> (at Fri, 6 May 2005 23:44:37 +0200), Thomas Graf <[email protected]> says:

Would you add some reference(s) on algorithm etc.? Thanks.

--yoshfuji

* YOSHIFUJI Hideaki / ?$B5HF#1QL@ <[email protected]> 2005-05-07 09:17

Comes out of my own mind which means it's probably pretty poor, it simply takes a deterministic finite state machine and runs it on the text.