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; 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 if (c == '\0') /* No possible match */ 72 return false; 73 bool match = false, inverted = (*pat == '!'); 74 char const *class = pat + inverted; 75 unsigned char a = *class++; 76 77 /* 78 * Iterate over each span in the character class. 79 * A span is either a single character a, or a 80 * range a-b. The first span may begin with ']'. 81 */ 82 do { 83 unsigned char b = a; 84 85 if (a == '\0') /* Malformed */ 86 goto literal; 87 88 if (class[0] == '-' && class[1] != ']') { 89 b = class[1]; 90 91 if (b == '\0') 92 goto literal; 93 94 class += 2; 95 /* Any special action if a > b? */ 96 } 97 match |= (a <= c && c <= b); 98 } while ((a = *class++) != ']'); 99 100 if (match == inverted) 101 goto backtrack; 102 pat = class; 103 } 104 break; 105 case '\\': 106 d = *pat++; 107 fallthrough; 108 default: /* Literal character */ 109 literal: 110 if (c == d) { 111 if (d == '\0') 112 return true; 113 break; 114 } 115 backtrack: 116 if (c == '\0' || !back_pat) 117 return false; /* No point continuing */ 118 /* Try again from last *, one character later in str. */ 119 pat = back_pat; 120 str = ++back_str; 121 break; 122 } 123 } 124 } 125 EXPORT_SYMBOL(glob_match); 126