From 0e8ecba96e72ecb57a5f2a668b645214e2f3b12b Mon Sep 17 00:00:00 2001 From: Jan Janssen Date: Thu, 9 Jun 2022 10:05:52 +0200 Subject: [PATCH] boot: Add efi_fnmatch Unlike MetaiMatch from the UEFI spec/EDK2 this implementation is intended to be compatible with POSIX fnmatch. --- src/boot/efi/efi-string.c | 105 +++++++++++++++++++++++++++++++++ src/boot/efi/efi-string.h | 2 + src/boot/efi/test-efi-string.c | 48 +++++++++++++++ 3 files changed, 155 insertions(+) diff --git a/src/boot/efi/efi-string.c b/src/boot/efi/efi-string.c index 4b405155a0..505830e310 100644 --- a/src/boot/efi/efi-string.c +++ b/src/boot/efi/efi-string.c @@ -139,6 +139,111 @@ DEFINE_STRCHR(char16_t, strchr16); DEFINE_STRNDUP(char, xstrndup8, strnlen8); DEFINE_STRNDUP(char16_t, xstrndup16, strnlen16); +/* Patterns are fnmatch-compatible (with reduced feature support). */ +static bool efi_fnmatch_internal(const char16_t *p, const char16_t *h, int max_depth) { + assert(p); + assert(h); + + if (max_depth == 0) + return false; + + for (;; p++, h++) + switch (*p) { + case '\0': + /* End of pattern. Check that haystack is now empty. */ + return *h == '\0'; + + case '\\': + p++; + if (*p == '\0' || *p != *h) + /* Trailing escape or no match. */ + return false; + break; + + case '?': + if (*h == '\0') + /* Early end of haystack. */ + return false; + break; + + case '*': + /* No need to recurse for consecutive '*'. */ + while (*p == '*') + p++; + + do { + /* Try matching haystack with remaining pattern. */ + if (efi_fnmatch_internal(p, h, max_depth - 1)) + return true; + + /* Otherwise, we match one char here. */ + h++; + } while (*h != '\0'); + + /* End of haystack. Pattern needs to be empty too for a match. */ + return *p == '\0'; + + case '[': + if (*h == '\0') + /* Early end of haystack. */ + return false; + + bool first = true, can_range = true, match = false; + for (;; first = false) { + p++; + if (*p == '\0') + return false; + + if (*p == '\\') { + p++; + if (*p == '\0') + return false; + match |= *p == *h; + can_range = true; + continue; + } + + /* End of set unless it's the first char. */ + if (*p == ']' && !first) + break; + + /* Range pattern if '-' is not first or last in set. */ + if (*p == '-' && can_range && !first && *(p + 1) != ']') { + char16_t low = *(p - 1); + p++; + if (*p == '\\') + p++; + if (*p == '\0') + return false; + + if (low <= *h && *h <= *p) + match = true; + + /* Ranges cannot be chained: [a-c-f] == [-abcf] */ + can_range = false; + continue; + } + + if (*p == *h) + match = true; + can_range = true; + } + + if (!match) + return false; + break; + + default: + if (*p != *h) + /* Single char mismatch. */ + return false; + } +} + +bool efi_fnmatch(const char16_t *pattern, const char16_t *haystack) { + return efi_fnmatch_internal(pattern, haystack, 32); +} + int efi_memcmp(const void *p1, const void *p2, size_t n) { const uint8_t *up1 = p1, *up2 = p2; int r; diff --git a/src/boot/efi/efi-string.h b/src/boot/efi/efi-string.h index b4870975bc..55c9c6e47a 100644 --- a/src/boot/efi/efi-string.h +++ b/src/boot/efi/efi-string.h @@ -99,6 +99,8 @@ static inline char16_t *xstrdup16(const char16_t *s) { return xstrndup16(s, SIZE_MAX); } +bool efi_fnmatch(const char16_t *pattern, const char16_t *haystack); + #ifdef SD_BOOT /* The compiler normally has knowledge about standard functions such as memcmp, but this is not the case when * compiling with -ffreestanding. By referring to builtins, the compiler can check arguments and do diff --git a/src/boot/efi/test-efi-string.c b/src/boot/efi/test-efi-string.c index b688c6ae41..5aaa1f713f 100644 --- a/src/boot/efi/test-efi-string.c +++ b/src/boot/efi/test-efi-string.c @@ -1,5 +1,7 @@ /* SPDX-License-Identifier: LGPL-2.1-or-later */ +#include + #include "efi-string.h" #include "tests.h" @@ -322,6 +324,52 @@ TEST(xstrdup16) { free(s); } +#define TEST_FNMATCH_ONE(pattern, haystack, expect) \ + ({ \ + assert_se(fnmatch(pattern, haystack, 0) == (expect ? 0 : FNM_NOMATCH)); \ + assert_se(efi_fnmatch(u##pattern, u##haystack) == expect); \ + }) + +TEST(efi_fnmatch) { + TEST_FNMATCH_ONE("", "", true); + TEST_FNMATCH_ONE("abc", "abc", true); + TEST_FNMATCH_ONE("aBc", "abc", false); + TEST_FNMATCH_ONE("b", "a", false); + TEST_FNMATCH_ONE("b", "", false); + TEST_FNMATCH_ONE("abc", "a", false); + TEST_FNMATCH_ONE("a?c", "azc", true); + TEST_FNMATCH_ONE("???", "?.9", true); + TEST_FNMATCH_ONE("1?", "1", false); + TEST_FNMATCH_ONE("***", "", true); + TEST_FNMATCH_ONE("*", "123", true); + TEST_FNMATCH_ONE("**", "abcd", true); + TEST_FNMATCH_ONE("*b*", "abcd", true); + TEST_FNMATCH_ONE("*.conf", "arch.conf", true); + TEST_FNMATCH_ONE("debian-*.conf", "debian-wheezy.conf", true); + TEST_FNMATCH_ONE("debian-*.*", "debian-wheezy.efi", true); + TEST_FNMATCH_ONE("ab*cde", "abzcd", false); + TEST_FNMATCH_ONE("\\*\\a\\[", "*a[", true); + TEST_FNMATCH_ONE("[abc] [abc] [abc]", "a b c", true); + TEST_FNMATCH_ONE("abc]", "abc]", true); + TEST_FNMATCH_ONE("[abc]", "z", false); + TEST_FNMATCH_ONE("[abc", "a", false); + TEST_FNMATCH_ONE("[][!] [][!] [][!]", "[ ] !", true); + TEST_FNMATCH_ONE("[]-] []-]", "] -", true); + TEST_FNMATCH_ONE("[1\\]] [1\\]]", "1 ]", true); + TEST_FNMATCH_ONE("[$-\\+]", "&", true); + TEST_FNMATCH_ONE("[1-3A-C] [1-3A-C]", "2 B", true); + TEST_FNMATCH_ONE("[3-5] [3-5] [3-5]", "3 4 5", true); + TEST_FNMATCH_ONE("[f-h] [f-h] [f-h]", "f g h", true); + TEST_FNMATCH_ONE("[a-c-f] [a-c-f] [a-c-f] [a-c-f] [a-c-f]", "a b c - f", true); + TEST_FNMATCH_ONE("[a-c-f]", "e", false); + TEST_FNMATCH_ONE("[--0] [--0] [--0]", "- . 0", true); + TEST_FNMATCH_ONE("[+--] [+--] [+--]", "+ , -", true); + TEST_FNMATCH_ONE("[f-l]", "m", false); + TEST_FNMATCH_ONE("[b]", "z-a", false); + TEST_FNMATCH_ONE("[a\\-z]", "b", false); + TEST_FNMATCH_ONE("?a*b[.-0]c", "/a/b/c", true); +} + TEST(efi_memcmp) { assert_se(efi_memcmp(NULL, NULL, 0) == 0); assert_se(efi_memcmp(NULL, NULL, 1) == 0); -- 2.25.1