| 1 | |
| 2 | #include <linux/module.h>
|
| 3 | #include <linux/glob.h>
|
| 4 | #include <linux/export.h>
|
| 5 |
|
| 6 | |
| 7 | * The only reason this code can be compiled as a module is because the
|
| 8 | * ATA code that depends on it can be as well. In practice, they're
|
| 9 | * both usually compiled in and the module overhead goes away.
|
| 10 |
|
| 11 | MODULE_DESCRIPTION("glob(7) matching");
|
| 12 | MODULE_LICENSE("Dual MIT/GPL");
|
| 13 |
|
| 14 | static bool __pure glob_match_str(char const *pat, char const *str,
|
| 15 | char const *str_end);
|
| 16 |
|
| 17 | |
| 18 | * glob_match - Shell-style pattern matching, like !fnmatch(pat, str, 0)
|
| 19 | * @pat: Shell-style pattern to match, e.g. "*.[ch]".
|
| 20 | * @str: String to match. The pattern must match the entire string.
|
| 21 | *
|
| 22 | * Perform shell-style glob matching, returning true (1) if the match
|
| 23 | * succeeds, or false (0) if it fails. Equivalent to !fnmatch(@pat, @str, 0).
|
| 24 | *
|
| 25 | * Pattern metacharacters are ?, *, [ and \.
|
| 26 | * (And, inside character classes, !, - and ].)
|
| 27 | *
|
| 28 | * This is a small and simple implementation intended for device denylists
|
| 29 | * where a string is matched against a number of patterns. Thus, it
|
| 30 | * does not preprocess the patterns. It is non-recursive, and run-time
|
| 31 | * is at most quadratic: strlen(@str)*strlen(@pat).
|
| 32 | *
|
| 33 | * An example of the worst case is glob_match("*aaaaa", "aaaaaaaaaa");
|
| 34 | * it takes 6 passes over the pattern before matching the string.
|
| 35 | *
|
| 36 | * Like !fnmatch(@pat, @str, 0) and unlike the shell, this does NOT
|
| 37 | * treat / or leading . specially; it isn't actually used for pathnames.
|
| 38 | *
|
| 39 | * Note that according to glob(7) (and unlike bash), character classes
|
| 40 | * are complemented by a leading !; this does not support the regex-style
|
| 41 | * [^a-z] syntax.
|
| 42 | *
|
| 43 | * An opening bracket without a matching close is matched literally.
|
| 44 |
|
| 45 | bool __pure glob_match(char const *pat, char const *str)
|
| 46 | {
|
| 47 | return glob_match_str(pat, str, NULL);
|
| 48 | }
|
| 49 | EXPORT_SYMBOL(glob_match);
|
| 50 |
|
| 51 | |
| 52 | * glob_match_len - glob match against a length-bounded string
|
| 53 | * @pat: Shell-style pattern to match.
|
| 54 | * @str: String to match. Need not be NUL-terminated.
|
| 55 | * @len: Number of bytes of @str that may be read.
|
| 56 | *
|
| 57 | * Like glob_match(), but @str is only read up to @len bytes, so it can be
|
| 58 | * used on buffers that are not NUL-terminated (e.g. trace event fields).
|
| 59 | * A NUL byte within @len still terminates the string.
|
| 60 |
|
| 61 | bool __pure glob_match_len(char const *pat, char const *str, size_t len)
|
| 62 | {
|
| 63 | return glob_match_str(pat, str, str + len);
|
| 64 | }
|
| 65 | EXPORT_SYMBOL(glob_match_len);
|
| 66 |
|
| 67 | static bool __pure glob_match_str(char const *pat, char const *str,
|
| 68 | char const *str_end)
|
| 69 | {
|
| 70 | |
| 71 | * Backtrack to previous * on mismatch and retry starting one
|
| 72 | * character later in the string. Because * matches all characters
|
| 73 | * (no exception for /), it can be easily proved that there's
|
| 74 | * never a need to backtrack multiple levels.
|
| 75 |
|
| 76 | char const *back_pat = NULL, *back_str = NULL;
|
| 77 |
|
| 78 | |
| 79 | * Loop over each token (character or class) in pat, matching
|
| 80 | * it against the remaining unmatched tail of str. Return false
|
| 81 | * on mismatch, or true after matching the trailing nul bytes.
|
| 82 |
|
| 83 | for (;;) {
|
| 84 | unsigned char c = (str_end && str >= str_end) ? '\0' : *str;
|
| 85 | unsigned char d = *pat++;
|
| 86 |
|
| 87 | str++;
|
| 88 |
|
| 89 | switch (d) {
|
| 90 | case '?':
|
| 91 | if (c == '\0')
|
| 92 | return false;
|
| 93 | break;
|
| 94 | case '*':
|
| 95 | if (*pat == '\0')
|
| 96 | return true;
|
| 97 | back_pat = pat;
|
| 98 | back_str = --str;
|
| 99 | break;
|
| 100 | case '[': {
|
| 101 | if (c == '\0')
|
| 102 | return false;
|
| 103 | bool match = false, inverted = (*pat == '!');
|
| 104 | char const *class = inverted ? pat + 1 : pat;
|
| 105 | unsigned char a = *class++;
|
| 106 |
|
| 107 | |
| 108 | * Iterate over each span in the character class.
|
| 109 | * A span is either a single character a, or a
|
| 110 | * range a-b. The first span may begin with ']'.
|
| 111 |
|
| 112 | do {
|
| 113 | unsigned char b = a;
|
| 114 |
|
| 115 | if (a == '\0')
|
| 116 | goto literal;
|
| 117 |
|
| 118 | if (class[0] == '-' && class[1] != ']') {
|
| 119 | b = class[1];
|
| 120 |
|
| 121 | if (b == '\0')
|
| 122 | goto literal;
|
| 123 |
|
| 124 | class += 2;
|
| 125 |
|
| 126 | }
|
| 127 | if (a <= c && c <= b)
|
| 128 | match = true;
|
| 129 | } while ((a = *class++) != ']');
|
| 130 |
|
| 131 | if (match == inverted)
|
| 132 | goto backtrack;
|
| 133 | pat = class;
|
| 134 | }
|
| 135 | break;
|
| 136 | case '\\':
|
| 137 | d = *pat++;
|
| 138 | fallthrough;
|
| 139 | default:
|
| 140 | literal:
|
| 141 | if (c == d) {
|
| 142 | if (d == '\0')
|
| 143 | return true;
|
| 144 | break;
|
| 145 | }
|
| 146 | backtrack:
|
| 147 | if (c == '\0' || !back_pat)
|
| 148 | return false;
|
| 149 |
|
| 150 | pat = back_pat;
|
| 151 | str = ++back_str;
|
| 152 | break;
|
| 153 | }
|
| 154 | }
|
| 155 | }
|