1 // SPDX-License-Identifier: (GPL-2.0 OR MIT) 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 '?': /* Wildcard: anything but nul */ 91 if (c == '\0') 92 return false; 93 break; 94 case '*': /* Any-length wildcard */ 95 if (*pat == '\0') /* Optimize trailing * case */ 96 return true; 97 back_pat = pat; 98 back_str = --str; /* Allow zero-length match */ 99 break; 100 case '[': { /* Character class */ 101 if (c == '\0') /* No possible match */ 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') /* Malformed */ 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 /* Any special action if a > b? */ 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: /* Literal character */ 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; /* No point continuing */ 149 /* Try again from last *, one character later in str. */ 150 pat = back_pat; 151 str = ++back_str; 152 break; 153 } 154 } 155 } 156