m/p/kmod: init
This adds a package for working with Linux kernel loadable modules in
Go. It contains syscall wrappers for loading and unloading modules, a
metadata format for fast lookup of modules handling devices using a
custom radix tree, parsers for module info metadata and various utility
functions and data structures.
A significant amount of the code in here has no formal spec and is
written against behavior and information extracted from the reference
kmod code as well as the Linux kernel itself.
Change-Id: I3d527f3631f4dd1832b9cfba2d50aeb03a2b88a8
Reviewed-on: https://review.monogon.dev/c/monogon/+/1789
Reviewed-by: Serge Bazanski <serge@monogon.tech>
Tested-by: Jenkins CI
diff --git a/metropolis/pkg/kmod/radix_test.go b/metropolis/pkg/kmod/radix_test.go
new file mode 100644
index 0000000..7a815ba
--- /dev/null
+++ b/metropolis/pkg/kmod/radix_test.go
@@ -0,0 +1,146 @@
+package kmod
+
+import (
+ "fmt"
+ "regexp"
+ "strings"
+ "testing"
+ "unicode"
+
+ "github.com/google/go-cmp/cmp"
+ "google.golang.org/protobuf/testing/protocmp"
+
+ kmodpb "source.monogon.dev/metropolis/pkg/kmod/spec"
+)
+
+func TestParsePattern(t *testing.T) {
+ cases := []struct {
+ name string
+ pattern string
+ expectedNodes []*kmodpb.RadixNode
+ }{
+ {"Empty", "", nil},
+ {"SingleLiteral", "asdf", []*kmodpb.RadixNode{{Type: kmodpb.RadixNode_LITERAL, Literal: "asdf"}}},
+ {"SingleWildcard", "as*df", []*kmodpb.RadixNode{
+ {Type: kmodpb.RadixNode_LITERAL, Literal: "as"},
+ {Type: kmodpb.RadixNode_WILDCARD},
+ {Type: kmodpb.RadixNode_LITERAL, Literal: "df"},
+ }},
+ {"EscapedWildcard", "a\\*", []*kmodpb.RadixNode{{Type: kmodpb.RadixNode_LITERAL, Literal: "a*"}}},
+ {"SingleRange", "[y-z]", []*kmodpb.RadixNode{{Type: kmodpb.RadixNode_BYTE_RANGE, StartByte: 121, EndByte: 122}}},
+ {"SingleWildcardChar", "a?c", []*kmodpb.RadixNode{
+ {Type: kmodpb.RadixNode_LITERAL, Literal: "a"},
+ {Type: kmodpb.RadixNode_SINGLE_WILDCARD},
+ {Type: kmodpb.RadixNode_LITERAL, Literal: "c"},
+ }},
+ }
+ for _, c := range cases {
+ t.Run(c.name, func(t *testing.T) {
+ out, err := parsePattern(c.pattern)
+ if err != nil {
+ t.Fatal(err)
+ }
+ diff := cmp.Diff(c.expectedNodes, out, protocmp.Transform())
+ if diff != "" {
+ t.Error(diff)
+ }
+ })
+ }
+}
+
+func TestLookupComplex(t *testing.T) {
+ root := &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_LITERAL,
+ }
+ if err := AddPattern(root, "usb:v0B95p1790d*dc*dsc*dp*icFFiscFFip00in*", 2); err != nil {
+ t.Error(err)
+ }
+ if err := AddPattern(root, "usb:v0B95p178Ad*dc*dsc*dp*icFFiscFFip00in*", 3); err != nil {
+ t.Error(err)
+ }
+ if err := AddPattern(root, "acpi*:PNP0C14:*", 10); err != nil {
+ t.Error(err)
+ }
+ matches := make(map[uint32]bool)
+ lookupModulesRec(root, "acpi:PNP0C14:asdf", matches)
+ if !matches[10] {
+ t.Error("value should match pattern 10")
+ }
+}
+
+func isASCII(s string) bool {
+ for i := 0; i < len(s); i++ {
+ if s[i] > unicode.MaxASCII {
+ return false
+ }
+ }
+ return true
+}
+
+func FuzzRadixImpl(f *testing.F) {
+ f.Add("acpi*:PNP0C14:*\x00usb:v0B95p1790d*dc*dsc*dp*icFFiscFFip00in*", "acpi:PNP0C14:asdf\x00usb:v0B95p1790d0dc0dsc0dp0icFFiscFFip00in")
+ f.Fuzz(func(t *testing.T, a string, b string) {
+ patternsRaw := strings.Split(a, "\x00")
+ values := strings.Split(b, "\x00")
+ var patternsRegexp []regexp.Regexp
+ root := &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_LITERAL,
+ }
+ for i, p := range patternsRaw {
+ if !isASCII(p) {
+ // Ignore non-ASCII patterns, there are tons of edge cases with them
+ return
+ }
+ pp, err := parsePattern(p)
+ if err != nil {
+ // Bad pattern
+ return
+ }
+ if err := AddPattern(root, p, uint32(i)); err != nil {
+ t.Fatal(err)
+ }
+ var regexb strings.Builder
+ regexb.WriteString("(?s)^")
+ for _, part := range pp {
+ switch part.Type {
+ case kmodpb.RadixNode_LITERAL:
+ regexb.WriteString(regexp.QuoteMeta(part.Literal))
+ case kmodpb.RadixNode_SINGLE_WILDCARD:
+ regexb.WriteString(".")
+ case kmodpb.RadixNode_WILDCARD:
+ regexb.WriteString(".*")
+ case kmodpb.RadixNode_BYTE_RANGE:
+ regexb.WriteString(fmt.Sprintf("[%s-%s]", regexp.QuoteMeta(string([]rune{rune(part.StartByte)})), regexp.QuoteMeta(string([]rune{rune(part.EndByte)}))))
+ default:
+ t.Errorf("Unknown node type %v", part.Type)
+ }
+ }
+ regexb.WriteString("$")
+ patternsRegexp = append(patternsRegexp, *regexp.MustCompile(regexb.String()))
+ }
+ for _, v := range values {
+ if !isASCII(v) {
+ // Ignore non-ASCII values
+ return
+ }
+ if len(v) > 64 {
+ // Ignore big values as they are not realistic and cause the
+ // wildcard matches to be very expensive.
+ return
+ }
+ radixMatchesSet := make(map[uint32]bool)
+ lookupModulesRec(root, v, radixMatchesSet)
+ for i, re := range patternsRegexp {
+ if re.MatchString(v) {
+ if !radixMatchesSet[uint32(i)] {
+ t.Errorf("Pattern %q is expected to match %q but didn't", patternsRaw[i], v)
+ }
+ } else {
+ if radixMatchesSet[uint32(i)] {
+ t.Errorf("Pattern %q is not expected to match %q but did", patternsRaw[i], v)
+ }
+ }
+ }
+ }
+ })
+}