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 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); 124