kernel/linux.git/lib/ts_bm.c, branch v4.19.310

lib/ts_bm: reset initial match offset for every block of text

2023-08-11T09:45:07+00:00

[ Upstream commit 6f67fbf8192da80c4db01a1800c7fceaca9cf1f9 ] The `shift` variable which indicates the offset in the string at which to start matching the pattern is initialized to `bm->patlen - 1`, but it is not reset when a new block is retrieved. This means the implemen- tation may start looking at later and later positions in each successive block and miss occurrences of the pattern at the beginning. E.g., consider a HTTP packet held in a non-linear skb, where the HTTP request line occurs in the second block: [... 52 bytes of packet headers ...] GET /bmtest HTTP/1.1\r\nHost: www.example.com\r\n\r\n and the pattern is "GET /bmtest". Once the first block comprising the packet headers has been examined, `shift` will be pointing to somewhere near the end of the block, and so when the second block is examined the request line at the beginning will be missed. Reinitialize the variable for each new block. Fixes: 8082e4ed0a61 ("[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2") Link: https://bugzilla.netfilter.org/show_bug.cgi?id=1390 Signed-off-by: Jeremy Sowden Signed-off-by: Pablo Neira Ayuso Signed-off-by: Sasha Levin

textsearch: ts_bm: support case insensitive searching in Boyer-Moore algorithm

2008-07-08T09:37:54+00:00

Add support for case insensitive search to Boyer-Moore algorithm. Signed-off-by: Joonwoo Park Signed-off-by: Patrick McHardy Signed-off-by: David S. Miller

textsearch: fix Boyer-Moore text search bug

2008-06-30T19:42:23+00:00

The current logic has a bug which cannot find matching pattern, if the pattern is matched from the first character of target string. for example: pattern=abc, string=abcdefg pattern=a, string=abcdefg Searching algorithm should return 0 for those things. Signed-off-by: Joonwoo Park Signed-off-by: Patrick McHardy Signed-off-by: David S. Miller

[TEXTSEARCH]: Fix Boyer Moore initialization bug

2006-08-22T21:33:58+00:00

The pattern is set after trying to compute the prefix table, which tries to use it. Initialize it before calling compute_prefix_tbl, make compute_prefix_tbl consistently use only the data from struct ts_bm and remove the now unnecessary arguments. Signed-off-by: Michael Rash Signed-off-by: Patrick McHardy Signed-off-by: David S. Miller

Remove obsolete #include

2006-06-30T17:25:36+00:00

Signed-off-by: Jörn Engel Signed-off-by: Adrian Bunk

[TEXTSEARCH]: Fix broken good shift array calculation in Boyer-Moore

2006-02-03T01:15:41+00:00

The current logic does not calculate correctly the good shift array: Let x be the pattern that is being searched. Let y be the block of data. The good shift array aligns the segment: x[i+1 ... m-1] = y[i+j+1 ... j+m-1] with its rightmost occurrence in x that fulfils x[i] neq y[i+j]. In previous version, the good shift array for the pattern ANPANMAN is: [1, 8, 3, 8, 8, 8, 8, 8] and should be: [1, 8, 3, 6, 6, 6, 6, 6] Signed-off-by: Pablo Neira Ayuso Signed-off-by: David S. Miller

[PATCH] gfp flags annotations - part 1

2005-10-08T22:00:57+00:00

- added typedef unsigned int __nocast gfp_t; - replaced __nocast uses for gfp flags with gfp_t - it gives exactly the same warnings as far as sparse is concerned, doesn't change generated code (from gcc point of view we replaced unsigned int with typedef) and documents what's going on far better. Signed-off-by: Al Viro Signed-off-by: Linus Torvalds

[TEXTSEARCH]: fix sparse gfp nocast warnings

2005-10-05T05:45:14+00:00

Fix nocast sparse warnings: include/linux/textsearch.h:165:57: warning: implicit cast to nocast type Signed-off-by: Randy Dunlap Signed-off-by: David S. Miller

[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2

2005-08-29T23:11:06+00:00

Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso Signed-off-by: David S. Miller