diff options
author | George Spelvin <linux@horizon.com> | 2014-08-06 19:09:23 -0400 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2014-08-06 21:01:24 -0400 |
commit | b01250856b25f4417c51aa33afc451fbf7da1484 (patch) | |
tree | d11b68368d63c1ae99814b930ce664d7fd3fa8e6 | |
parent | 62e7ca5280fd8cbf523970757e13f0324ce0daa0 (diff) |
lib: add lib/glob.c
This is a helper function from drivers/ata/libata_core.c, where it is
used to blacklist particular device models. It's being moved to lib/ so
other drivers may use it for the same purpose.
This implementation in non-recursive, so is safe for the kernel stack.
[akpm@linux-foundation.org: fix sparse warning]
Signed-off-by: George Spelvin <linux@horizon.com>
Cc: Randy Dunlap <rdunlap@infradead.org>
Cc: Tejun Heo <tj@kernel.org>
Cc: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
-rw-r--r-- | include/linux/glob.h | 9 | ||||
-rw-r--r-- | lib/Kconfig | 19 | ||||
-rw-r--r-- | lib/Makefile | 2 | ||||
-rw-r--r-- | lib/glob.c | 123 |
4 files changed, 153 insertions, 0 deletions
diff --git a/include/linux/glob.h b/include/linux/glob.h new file mode 100644 index 000000000000..861d8347d08e --- /dev/null +++ b/include/linux/glob.h | |||
@@ -0,0 +1,9 @@ | |||
1 | #ifndef _LINUX_GLOB_H | ||
2 | #define _LINUX_GLOB_H | ||
3 | |||
4 | #include <linux/types.h> /* For bool */ | ||
5 | #include <linux/compiler.h> /* For __pure */ | ||
6 | |||
7 | bool __pure glob_match(char const *pat, char const *str); | ||
8 | |||
9 | #endif /* _LINUX_GLOB_H */ | ||
diff --git a/lib/Kconfig b/lib/Kconfig index a8a775730c09..41bfeec72e40 100644 --- a/lib/Kconfig +++ b/lib/Kconfig | |||
@@ -396,6 +396,25 @@ config CPU_RMAP | |||
396 | config DQL | 396 | config DQL |
397 | bool | 397 | bool |
398 | 398 | ||
399 | config GLOB | ||
400 | bool | ||
401 | # This actually supports modular compilation, but the module overhead | ||
402 | # is ridiculous for the amount of code involved. Until an out-of-tree | ||
403 | # driver asks for it, we'll just link it directly it into the kernel | ||
404 | # when required. Since we're ignoring out-of-tree users, there's also | ||
405 | # no need bother prompting for a manual decision: | ||
406 | # prompt "glob_match() function" | ||
407 | help | ||
408 | This option provides a glob_match function for performing | ||
409 | simple text pattern matching. It originated in the ATA code | ||
410 | to blacklist particular drive models, but other device drivers | ||
411 | may need similar functionality. | ||
412 | |||
413 | All drivers in the Linux kernel tree that require this function | ||
414 | should automatically select this option. Say N unless you | ||
415 | are compiling an out-of tree driver which tells you that it | ||
416 | depends on this. | ||
417 | |||
399 | # | 418 | # |
400 | # Netlink attribute parsing support is select'ed if needed | 419 | # Netlink attribute parsing support is select'ed if needed |
401 | # | 420 | # |
diff --git a/lib/Makefile b/lib/Makefile index 8427df95dade..d6b4bc496408 100644 --- a/lib/Makefile +++ b/lib/Makefile | |||
@@ -137,6 +137,8 @@ obj-$(CONFIG_CORDIC) += cordic.o | |||
137 | 137 | ||
138 | obj-$(CONFIG_DQL) += dynamic_queue_limits.o | 138 | obj-$(CONFIG_DQL) += dynamic_queue_limits.o |
139 | 139 | ||
140 | obj-$(CONFIG_GLOB) += glob.o | ||
141 | |||
140 | obj-$(CONFIG_MPILIB) += mpi/ | 142 | obj-$(CONFIG_MPILIB) += mpi/ |
141 | obj-$(CONFIG_SIGNATURE) += digsig.o | 143 | obj-$(CONFIG_SIGNATURE) += digsig.o |
142 | 144 | ||
diff --git a/lib/glob.c b/lib/glob.c new file mode 100644 index 000000000000..0ba3ea86b546 --- /dev/null +++ b/lib/glob.c | |||
@@ -0,0 +1,123 @@ | |||
1 | #include <linux/module.h> | ||
2 | #include <linux/glob.h> | ||
3 | |||
4 | /* | ||
5 | * The only reason this code can be compiled as a module is because the | ||
6 | * ATA code that depends on it can be as well. In practice, they're | ||
7 | * both usually compiled in and the module overhead goes away. | ||
8 | */ | ||
9 | MODULE_DESCRIPTION("glob(7) matching"); | ||
10 | MODULE_LICENSE("Dual MIT/GPL"); | ||
11 | |||
12 | /** | ||
13 | * glob_match - Shell-style pattern matching, like !fnmatch(pat, str, 0) | ||
14 | * @pat: Shell-style pattern to match, e.g. "*.[ch]". | ||
15 | * @str: String to match. The pattern must match the entire string. | ||
16 | * | ||
17 | * Perform shell-style glob matching, returning true (1) if the match | ||
18 | * succeeds, or false (0) if it fails. Equivalent to !fnmatch(@pat, @str, 0). | ||
19 | * | ||
20 | * Pattern metacharacters are ?, *, [ and \. | ||
21 | * (And, inside character classes, !, - and ].) | ||
22 | * | ||
23 | * This is small and simple implementation intended for device blacklists | ||
24 | * where a string is matched against a number of patterns. Thus, it | ||
25 | * does not preprocess the patterns. It is non-recursive, and run-time | ||
26 | * is at most quadratic: strlen(@str)*strlen(@pat). | ||
27 | * | ||
28 | * An example of the worst case is glob_match("*aaaaa", "aaaaaaaaaa"); | ||
29 | * it takes 6 passes over the pattern before matching the string. | ||
30 | * | ||
31 | * Like !fnmatch(@pat, @str, 0) and unlike the shell, this does NOT | ||
32 | * treat / or leading . specially; it isn't actually used for pathnames. | ||
33 | * | ||
34 | * Note that according to glob(7) (and unlike bash), character classes | ||
35 | * are complemented by a leading !; this does not support the regex-style | ||
36 | * [^a-z] syntax. | ||
37 | * | ||
38 | * An opening bracket without a matching close is matched literally. | ||
39 | */ | ||
40 | bool __pure glob_match(char const *pat, char const *str) | ||
41 | { | ||
42 | /* | ||
43 | * Backtrack to previous * on mismatch and retry starting one | ||
44 | * character later in the string. Because * matches all characters | ||
45 | * (no exception for /), it can be easily proved that there's | ||
46 | * never a need to backtrack multiple levels. | ||
47 | */ | ||
48 | char const *back_pat = NULL, *back_str = back_str; | ||
49 | |||
50 | /* | ||
51 | * Loop over each token (character or class) in pat, matching | ||
52 | * it against the remaining unmatched tail of str. Return false | ||
53 | * on mismatch, or true after matching the trailing nul bytes. | ||
54 | */ | ||
55 | for (;;) { | ||
56 | unsigned char c = *str++; | ||
57 | unsigned char d = *pat++; | ||
58 | |||
59 | switch (d) { | ||
60 | case '?': /* Wildcard: anything but nul */ | ||
61 | if (c == '\0') | ||
62 | return false; | ||
63 | break; | ||
64 | case '*': /* Any-length wildcard */ | ||
65 | if (*pat == '\0') /* Optimize trailing * case */ | ||
66 | return true; | ||
67 | back_pat = pat; | ||
68 | back_str = --str; /* Allow zero-length match */ | ||
69 | break; | ||
70 | case '[': { /* Character class */ | ||
71 | bool match = false, inverted = (*pat == '!'); | ||
72 | char const *class = pat + inverted; | ||
73 | unsigned char a = *class++; | ||
74 | |||
75 | /* | ||
76 | * Iterate over each span in the character class. | ||
77 | * A span is either a single character a, or a | ||
78 | * range a-b. The first span may begin with ']'. | ||
79 | */ | ||
80 | do { | ||
81 | unsigned char b = a; | ||
82 | |||
83 | if (a == '\0') /* Malformed */ | ||
84 | goto literal; | ||
85 | |||
86 | if (class[0] == '-' && class[1] != ']') { | ||
87 | b = class[1]; | ||
88 | |||
89 | if (b == '\0') | ||
90 | goto literal; | ||
91 | |||
92 | class += 2; | ||
93 | /* Any special action if a > b? */ | ||
94 | } | ||
95 | match |= (a <= c && c <= b); | ||
96 | } while ((a = *class++) != ']'); | ||
97 | |||
98 | if (match == inverted) | ||
99 | goto backtrack; | ||
100 | pat = class; | ||
101 | } | ||
102 | break; | ||
103 | case '\\': | ||
104 | d = *pat++; | ||
105 | /*FALLTHROUGH*/ | ||
106 | default: /* Literal character */ | ||
107 | literal: | ||
108 | if (c == d) { | ||
109 | if (d == '\0') | ||
110 | return true; | ||
111 | break; | ||
112 | } | ||
113 | backtrack: | ||
114 | if (c == '\0' || !back_pat) | ||
115 | return false; /* No point continuing */ | ||
116 | /* Try again from last *, one character later in str. */ | ||
117 | pat = back_pat; | ||
118 | str = ++back_str; | ||
119 | break; | ||
120 | } | ||
121 | } | ||
122 | } | ||
123 | EXPORT_SYMBOL(glob_match); | ||