1 /* SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause) */ 2 /* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */ 3 #pragma once 4 #include "bpf_arena_common.h" 5 6 __noinline int bpf_arena_strlen(const char __arena *s __arg_arena) 7 { 8 const char __arena *sc; 9 10 for (sc = s; *sc != '\0'; ++sc) 11 cond_break; 12 return sc - s; 13 } 14 15 /** 16 * glob_match - Shell-style pattern matching, like !fnmatch(pat, str, 0) 17 * @pat: Shell-style pattern to match, e.g. "*.[ch]". 18 * @str: String to match. The pattern must match the entire string. 19 * 20 * Perform shell-style glob matching, returning true (1) if the match 21 * succeeds, or false (0) if it fails. Equivalent to !fnmatch(@pat, @str, 0). 22 * 23 * Pattern metacharacters are ?, *, [ and \. 24 * (And, inside character classes, !, - and ].) 25 * 26 * This is small and simple implementation intended for device blacklists 27 * where a string is matched against a number of patterns. Thus, it 28 * does not preprocess the patterns. It is non-recursive, and run-time 29 * is at most quadratic: strlen(@str)*strlen(@pat). 30 * 31 * An example of the worst case is glob_match("*aaaaa", "aaaaaaaaaa"); 32 * it takes 6 passes over the pattern before matching the string. 33 * 34 * Like !fnmatch(@pat, @str, 0) and unlike the shell, this does NOT 35 * treat / or leading . specially; it isn't actually used for pathnames. 36 * 37 * Note that according to glob(7) (and unlike bash), character classes 38 * are complemented by a leading !; this does not support the regex-style 39 * [^a-z] syntax. 40 * 41 * An opening bracket without a matching close is matched literally. 42 */ 43 __noinline bool glob_match(char const __arena *pat __arg_arena, char const __arena *str __arg_arena) 44 { 45 /* 46 * Backtrack to previous * on mismatch and retry starting one 47 * character later in the string. Because * matches all characters 48 * (no exception for /), it can be easily proved that there's 49 * never a need to backtrack multiple levels. 50 */ 51 char const __arena *back_pat = NULL, *back_str; 52 53 /* 54 * Loop over each token (character or class) in pat, matching 55 * it against the remaining unmatched tail of str. Return false 56 * on mismatch, or true after matching the trailing nul bytes. 57 */ 58 for (;;) { 59 unsigned char c = *str++; 60 unsigned char d = *pat++; 61 62 switch (d) { 63 case '?': /* Wildcard: anything but nul */ 64 if (c == '\0') 65 return false; 66 break; 67 case '*': /* Any-length wildcard */ 68 if (*pat == '\0') /* Optimize trailing * case */ 69 return true; 70 back_pat = pat; 71 back_str = --str; /* Allow zero-length match */ 72 break; 73 case '[': { /* Character class */ 74 bool match = false, inverted = (*pat == '!'); 75 char const __arena *class = pat + inverted; 76 unsigned char a = *class++; 77 78 /* 79 * Iterate over each span in the character class. 80 * A span is either a single character a, or a 81 * range a-b. The first span may begin with ']'. 82 */ 83 do { 84 unsigned char b = a; 85 86 if (a == '\0') /* Malformed */ 87 goto literal; 88 89 if (class[0] == '-' && class[1] != ']') { 90 b = class[1]; 91 92 if (b == '\0') 93 goto literal; 94 95 class += 2; 96 /* Any special action if a > b? */ 97 } 98 match |= (a <= c && c <= b); 99 cond_break; 100 } while ((a = *class++) != ']'); 101 102 if (match == inverted) 103 goto backtrack; 104 pat = class; 105 } 106 break; 107 case '\\': 108 d = *pat++; 109 __attribute__((__fallthrough__)); 110 default: /* Literal character */ 111 literal: 112 if (c == d) { 113 if (d == '\0') 114 return true; 115 break; 116 } 117 backtrack: 118 if (c == '\0' || !back_pat) 119 return false; /* No point continuing */ 120 /* Try again from last *, one character later in str. */ 121 pat = back_pat; 122 str = ++back_str; 123 break; 124 } 125 cond_break; 126 } 127 return false; 128 } 129