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/BUILD.bazel b/metropolis/pkg/kmod/BUILD.bazel
new file mode 100644
index 0000000..6264bf9
--- /dev/null
+++ b/metropolis/pkg/kmod/BUILD.bazel
@@ -0,0 +1,49 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+load("//metropolis/node/build/fwprune:def.bzl", "fsspec_linux_firmware")
+load("//metropolis/test/ktest:ktest.bzl", "ktest")
+
+go_library(
+ name = "kmod",
+ srcs = [
+ "manager.go",
+ "meta.go",
+ "modinfo.go",
+ "radix.go",
+ "syscall.go",
+ ],
+ importpath = "source.monogon.dev/metropolis/pkg/kmod",
+ visibility = ["//visibility:public"],
+ deps = [
+ "//metropolis/pkg/kmod/spec",
+ "@org_golang_google_protobuf//proto",
+ "@org_golang_x_sys//unix",
+ ],
+)
+
+go_test(
+ name = "kmod_test",
+ srcs = [
+ "manager_test.go",
+ "radix_test.go",
+ ],
+ embed = [":kmod"],
+ deps = [
+ "//metropolis/pkg/kmod/spec",
+ "@com_github_google_go_cmp//cmp",
+ "@org_golang_google_protobuf//testing/protocmp",
+ ],
+)
+
+fsspec_linux_firmware(
+ name = "firmware",
+ firmware_files = ["@linux-firmware//:all_files"],
+ kernel = "//metropolis/test/ktest:linux-testing",
+ metadata = "@linux-firmware//:metadata",
+)
+
+ktest(
+ fsspecs = [
+ ":firmware",
+ ],
+ tester = ":kmod_test",
+)
diff --git a/metropolis/pkg/kmod/manager.go b/metropolis/pkg/kmod/manager.go
new file mode 100644
index 0000000..1630a7f
--- /dev/null
+++ b/metropolis/pkg/kmod/manager.go
@@ -0,0 +1,158 @@
+package kmod
+
+import (
+ "bufio"
+ "fmt"
+ "os"
+ "path/filepath"
+ "strings"
+ "sync"
+
+ "golang.org/x/sys/unix"
+ "google.golang.org/protobuf/proto"
+
+ kmodpb "source.monogon.dev/metropolis/pkg/kmod/spec"
+)
+
+// Manager contains all the logic and metadata required to efficiently load
+// Linux kernel modules. It has internal loading tracking, thus it's recommended
+// to only keep one Manager instance running per kernel. It can recreate its
+// internal state quite well, but there are edge cases where the kernel makes
+// it hard to do so (MODULE_STATE_UNFORMED) thus if possible that single
+// instance should be kept alive. It currently does not support unloading
+// modules, but that can be added to the existing design if deemed necessary.
+type Manager struct {
+ // Directory the modules are loaded from. The path in each module Meta
+ // message is relative to this.
+ modulesPath string
+ meta *kmodpb.Meta
+ // Extra map to quickly find module indexes from names
+ moduleIndexes map[string]uint32
+
+ // mutex protects loadedModules, rest is read-only
+ // This cannot use a RWMutex as locks cannot be upgraded
+ mutex sync.Mutex
+ loadedModules map[uint32]bool
+}
+
+// NewManager instantiates a kernel module loading manager. Please take a look
+// at the additional considerations on the Manager type itself.
+func NewManager(meta *kmodpb.Meta, modulesPath string) (*Manager, error) {
+ modIndexes := make(map[string]uint32)
+ for i, m := range meta.Modules {
+ modIndexes[m.Name] = uint32(i)
+ }
+ modulesFile, err := os.Open("/proc/modules")
+ if err != nil {
+ return nil, err
+ }
+ loadedModules := make(map[uint32]bool)
+ s := bufio.NewScanner(modulesFile)
+ for s.Scan() {
+ fields := strings.Fields(s.Text())
+ if len(fields) == 0 {
+ // Skip invalid lines
+ continue
+ }
+ modIdx, ok := modIndexes[fields[0]]
+ if !ok {
+ // Certain modules are only available as built-in and are thus not
+ // part of the module metadata. They do not need to be handled by
+ // this code, ignore them.
+ continue
+ }
+ loadedModules[modIdx] = true
+ }
+ return &Manager{
+ modulesPath: modulesPath,
+ meta: meta,
+ moduleIndexes: modIndexes,
+ loadedModules: loadedModules,
+ }, nil
+}
+
+// NewManagerFromPath instantiates a new kernel module loading manager from a
+// path containing a meta.pb file containing a kmod.Meta message as well as the
+// kernel modules within. Please take a look at the additional considerations on
+// the Manager type itself.
+func NewManagerFromPath(modulesPath string) (*Manager, error) {
+ moduleMetaRaw, err := os.ReadFile(filepath.Join(modulesPath, "meta.pb"))
+ if err != nil {
+ return nil, fmt.Errorf("error reading module metadata: %w", err)
+ }
+ var moduleMeta kmodpb.Meta
+ if err := proto.Unmarshal(moduleMetaRaw, &moduleMeta); err != nil {
+ return nil, fmt.Errorf("error decoding module metadata: %w", err)
+ }
+ return NewManager(&moduleMeta, modulesPath)
+}
+
+// ErrNotFound is returned when an attempt is made to load a module which does
+// not exist according to the loaded metadata.
+type ErrNotFound struct {
+ Name string
+}
+
+func (e *ErrNotFound) Error() string {
+ return fmt.Sprintf("module %q does not exist", e.Name)
+}
+
+// LoadModule loads the module with the given name. If the module is already
+// loaded or built-in, it returns no error. If it failed loading the module or
+// the module does not exist, it returns an error.
+func (s *Manager) LoadModule(name string) error {
+ modIdx, ok := s.moduleIndexes[name]
+ if !ok {
+ return &ErrNotFound{Name: name}
+ }
+ s.mutex.Lock()
+ defer s.mutex.Unlock()
+ return s.loadModuleRecursive(modIdx)
+}
+
+// LoadModulesForDevice loads all modules whose device match expressions
+// (modaliases) match the given device modalias. It only returns an error if
+// a module which matched the device or one of its dependencies caused an error
+// when loading. A device modalias string which matches nothing is not an error.
+func (s *Manager) LoadModulesForDevice(devModalias string) error {
+ matches := make(map[uint32]bool)
+ lookupModulesRec(s.meta.ModuleDeviceMatches, devModalias, matches)
+ s.mutex.Lock()
+ defer s.mutex.Unlock()
+ for m := range matches {
+ if err := s.loadModuleRecursive(m); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+// Caller is REQUIRED to hold s.mutex!
+func (s *Manager) loadModuleRecursive(modIdx uint32) error {
+ if s.loadedModules[modIdx] {
+ return nil
+ }
+ modMeta := s.meta.Modules[modIdx]
+ if modMeta.Path == "" {
+ // Module is built-in, dependency always satisfied
+ return nil
+ }
+ for _, dep := range modMeta.Depends {
+ if err := s.loadModuleRecursive(dep); err != nil {
+ // Pass though as is, recursion can otherwise cause
+ // extremely large errors
+ return err
+ }
+ }
+ module, err := os.Open(filepath.Join(s.modulesPath, modMeta.Path))
+ if err != nil {
+ return fmt.Errorf("error opening kernel module: %w", err)
+ }
+ defer module.Close()
+ err = LoadModule(module, "", 0)
+ if err != nil && err != unix.EEXIST {
+ return fmt.Errorf("error loading kernel module %v: %w", modMeta.Name, err)
+ }
+ s.loadedModules[modIdx] = true
+ return nil
+}
diff --git a/metropolis/pkg/kmod/manager_test.go b/metropolis/pkg/kmod/manager_test.go
new file mode 100644
index 0000000..4f06d17
--- /dev/null
+++ b/metropolis/pkg/kmod/manager_test.go
@@ -0,0 +1,49 @@
+package kmod
+
+import (
+ "errors"
+ "os"
+ "testing"
+)
+
+func TestManagerIntegration(t *testing.T) {
+ if os.Getenv("IN_KTEST") != "true" {
+ t.Skip("Not in ktest")
+ }
+ t.Skip("Only works from the final CL in the stack as it has a dep on the new kernel config")
+ mgr, err := NewManagerFromPath("/lib/modules")
+ if err != nil {
+ t.Fatal(err)
+ }
+ t.Run("LoadExampleModule", func(t *testing.T) {
+ if err := mgr.LoadModule("r8169"); err != nil {
+ t.Error(err)
+ }
+ if _, err := os.Stat("/sys/module/r8169"); err != nil {
+ t.Error("module load returned success, but module not in sysfs")
+ }
+ })
+ t.Run("LoadNonexistentModule", func(t *testing.T) {
+ err := mgr.LoadModule("definitelynomodule")
+ var notFoundErr *ErrNotFound
+ if !errors.As(err, ¬FoundErr) {
+ t.Errorf("expected ErrNotFound, got %v", err)
+ }
+ })
+ t.Run("LoadModuleTwice", func(t *testing.T) {
+ if err := mgr.LoadModule("r8169"); err != nil {
+ t.Error(err)
+ }
+ })
+ // TODO(lorenz): Should test loading dependencies here, but we currently
+ // have none in the kernel config and I'm not about to build another kernel
+ // just for this.
+ t.Run("LoadDeviceModule", func(t *testing.T) {
+ if err := mgr.LoadModulesForDevice("pci:v00008086d00001591sv00001043sd000085F0bc02sc00i00"); err != nil {
+ t.Error(err)
+ }
+ if _, err := os.Stat("/sys/module/ice"); err != nil {
+ t.Error("module load returned success, but module not in sysfs")
+ }
+ })
+}
diff --git a/metropolis/pkg/kmod/meta.go b/metropolis/pkg/kmod/meta.go
new file mode 100644
index 0000000..2554c33
--- /dev/null
+++ b/metropolis/pkg/kmod/meta.go
@@ -0,0 +1,50 @@
+package kmod
+
+import (
+ "fmt"
+ "log"
+
+ kmodpb "source.monogon.dev/metropolis/pkg/kmod/spec"
+)
+
+// MakeMetaFromModuleInfo is a more flexible alternative to MakeMeta. It only
+// relies on ModuleInfo structures, additional processing can be done outside of
+// this function. It does however require that for dynamically-loaded modules
+// the "path" key is set to the path of the .ko file relative to the module
+// root.
+func MakeMetaFromModuleInfo(modinfos []ModuleInfo) (*kmodpb.Meta, error) {
+ modIndices := make(map[string]uint32)
+ modInfoMap := make(map[string]ModuleInfo)
+ var meta kmodpb.Meta
+ meta.ModuleDeviceMatches = &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_ROOT,
+ }
+ var i uint32
+ for _, m := range modinfos {
+ meta.Modules = append(meta.Modules, &kmodpb.Module{
+ Name: m.Name(),
+ Path: m.Get("path"),
+ })
+ for _, p := range m.Aliases() {
+ if m.Get("path") == "" {
+ // Ignore built-in modaliases as they do not need to be loaded.
+ continue
+ }
+ if err := AddPattern(meta.ModuleDeviceMatches, p, i); err != nil {
+ return nil, fmt.Errorf("failed adding device match %q: %w", p, err)
+ }
+ }
+ modIndices[m.Name()] = i
+ modInfoMap[m.Name()] = m
+ i++
+ }
+ for _, m := range meta.Modules {
+ for _, dep := range modInfoMap[m.Name].GetDependencies() {
+ if _, ok := modIndices[dep]; !ok {
+ log.Printf("Unknown dependency %q for module %q", modInfoMap[m.Name].GetDependencies(), m.Name)
+ }
+ m.Depends = append(m.Depends, modIndices[dep])
+ }
+ }
+ return &meta, nil
+}
diff --git a/metropolis/pkg/kmod/modinfo.go b/metropolis/pkg/kmod/modinfo.go
new file mode 100644
index 0000000..adaf5d1
--- /dev/null
+++ b/metropolis/pkg/kmod/modinfo.go
@@ -0,0 +1,206 @@
+package kmod
+
+import (
+ "bufio"
+ "bytes"
+ "debug/elf"
+ "errors"
+ "fmt"
+ "io"
+ "strings"
+)
+
+// ModuleInfo contains Linux kernel module metadata. It maps keys to a list
+// of values. For known keys accessor functions are provided.
+type ModuleInfo map[string][]string
+
+// Get returns the first value of the given key or an empty string if the key
+// does not exist.
+func (i ModuleInfo) Get(key string) string {
+ if len(i[key]) > 0 {
+ return i[key][0]
+ }
+ return ""
+}
+
+// Name returns the name of the module as defined in kbuild.
+func (i ModuleInfo) Name() string {
+ return i.Get("name")
+}
+
+// Authors returns the list of a authors of the module.
+func (i ModuleInfo) Authors() []string {
+ return i["author"]
+}
+
+// Description returns a human-readable description of the module or an empty
+// string if it is not available.
+func (i ModuleInfo) Description() string {
+ return i.Get("description")
+}
+
+// GetDependencies returns a list of module names which need to be loaded
+// before this one.
+func (i ModuleInfo) GetDependencies() []string {
+ if len(i["depends"]) == 1 && i["depends"][0] == "" {
+ return nil
+ }
+ return i["depends"]
+}
+
+type OptionalDependencies struct {
+ // Pre contains a list of module names to be optionally loaded before the
+ // module itself.
+ Pre []string
+ // Post contains a list of module names to be optionally loaded after the
+ // module itself.
+ Post []string
+}
+
+// GetOptionalDependencies returns a set of modules which are recommended to
+// be loaded before and after this module. These are optional, but enhance
+// the functionality of this module.
+func (i ModuleInfo) GetOptionalDependencies() OptionalDependencies {
+ var out OptionalDependencies
+ for _, s := range i["softdep"] {
+ tokens := strings.Fields(s)
+ const (
+ MODE_IDLE = 0
+ MODE_PRE = 1
+ MODE_POST = 2
+ )
+ var state int = MODE_IDLE
+ for _, token := range tokens {
+ switch token {
+ case "pre:":
+ state = MODE_PRE
+ case "post:":
+ state = MODE_POST
+ default:
+ switch state {
+ case MODE_PRE:
+ out.Pre = append(out.Pre, token)
+ case MODE_POST:
+ out.Post = append(out.Post, token)
+ default:
+ }
+ }
+ }
+ }
+ return out
+}
+
+// Aliases returns a list of match expressions for matching devices handled
+// by this module. Every returned string consists of a literal as well as '*'
+// wildcards matching one or more characters. These should be matched against
+// the kobject MODALIAS field or the modalias sysfs file.
+func (i ModuleInfo) Aliases() []string {
+ return i["alias"]
+}
+
+// Firmware returns a list of firmware file paths required by this module.
+// These paths are usually relative to the root of a linux-firmware install
+// unless the firmware is non-redistributable.
+func (i ModuleInfo) Firmware() []string {
+ return i["firmware"]
+}
+
+// License returns the licenses use of this module is governed by. For mainline
+// modules, the list of valid license strings is documented in the kernel's
+// Documentation/process/license-rules.rst file under the `MODULE_LICENSE`
+// section.
+func (i ModuleInfo) Licenses() []string {
+ return i["license"]
+}
+
+// IsInTree returns true if the module was built in the Linux source tree and
+// not externally. This does not necessarily mean that the module is in the
+// mainline kernel.
+func (i ModuleInfo) IsInTree() bool {
+ return i.Get("intree") == "Y"
+}
+
+// vermagic and retpoline are intentionally not exposed here, if you need them
+// you should know how to get them out of the map yourself as AFAIK these
+// are not a stable interface and most programs should not process them.
+
+func nullByteSplit(data []byte, atEOF bool) (advance int, token []byte, err error) {
+ if atEOF && len(data) == 0 {
+ return 0, nil, nil
+ }
+ if i := bytes.IndexByte(data, 0x00); i >= 0 {
+ return i + 1, bytes.TrimLeft(data[0:i], "\x00"), nil
+ }
+ if atEOF {
+ return len(data), data, nil
+ }
+ return 0, nil, nil
+}
+
+// GetModuleInfo looks for a ".modinfo" section in the passed ELF Linux kernel
+// module and parses it into a ModuleInfo structure.
+func GetModuleInfo(e *elf.File) (ModuleInfo, error) {
+ for _, section := range e.Sections {
+ if section.Name == ".modinfo" {
+ out := make(ModuleInfo)
+ s := bufio.NewScanner(io.NewSectionReader(section, 0, int64(section.Size)))
+ s.Split(nullByteSplit)
+
+ for s.Scan() {
+ // Format is <key>=<value>
+ key, value, ok := bytes.Cut(s.Bytes(), []byte("="))
+ if !ok {
+ continue
+ }
+ keyStr := string(key)
+ out[keyStr] = append(out[keyStr], string(value))
+ }
+ return out, nil
+ }
+ }
+ return nil, errors.New("no .modinfo section found")
+}
+
+// GetBuiltinModulesInfo parses all modinfo structures for builtin modules from
+// a modinfo file (modules.builtin.modinfo).
+func GetBuiltinModulesInfo(f io.Reader) ([]ModuleInfo, error) {
+ var out []ModuleInfo
+ s := bufio.NewScanner(f)
+ s.Split(nullByteSplit)
+
+ currModule := make(ModuleInfo)
+ for s.Scan() {
+ if s.Err() != nil {
+ return nil, fmt.Errorf("failed scanning for next token: %w", s.Err())
+ }
+ // Format is <module>.<key>=<value>
+ modName, entry, ok := bytes.Cut(s.Bytes(), []byte{'.'})
+ if !ok {
+ continue
+ }
+ if string(modName) != currModule.Name() {
+ if currModule.Name() != "" {
+ out = append(out, currModule)
+ }
+ currModule = make(ModuleInfo)
+ currModule["name"] = []string{string(modName)}
+ }
+ key, value, ok := bytes.Cut(entry, []byte("="))
+ if !ok {
+ continue
+ }
+ keyStr := string(key)
+ currModule[keyStr] = append(currModule[keyStr], string(value))
+ }
+ if currModule.Name() != "" {
+ out = append(out, currModule)
+ }
+ seenModNames := make(map[string]bool)
+ for _, m := range out {
+ if seenModNames[m.Name()] {
+ return nil, fmt.Errorf("duplicate/out-of-order module metadata for module %q", m)
+ }
+ seenModNames[m.Name()] = true
+ }
+ return out, nil
+}
diff --git a/metropolis/pkg/kmod/radix.go b/metropolis/pkg/kmod/radix.go
new file mode 100644
index 0000000..60e75f0
--- /dev/null
+++ b/metropolis/pkg/kmod/radix.go
@@ -0,0 +1,268 @@
+package kmod
+
+import (
+ "errors"
+ "fmt"
+ "log"
+ "sort"
+ "strings"
+
+ kmodpb "source.monogon.dev/metropolis/pkg/kmod/spec"
+)
+
+// LookupModules looks up all matching modules for a given modalias device
+// identifier.
+func LookupModules(meta *kmodpb.Meta, modalias string) (mods []*kmodpb.Module) {
+ matches := make(map[uint32]bool)
+ lookupModulesRec(meta.ModuleDeviceMatches, modalias, matches)
+ for idx := range matches {
+ mods = append(mods, meta.Modules[idx])
+ }
+ sort.Slice(mods, func(i, j int) bool { return mods[i].Name < mods[j].Name })
+ return
+}
+
+func lookupModulesRec(n *kmodpb.RadixNode, needle string, matches map[uint32]bool) {
+ for _, c := range n.Children {
+ switch c.Type {
+ case kmodpb.RadixNode_LITERAL:
+ if len(needle) < len(c.Literal) {
+ continue
+ }
+ if c.Literal == needle[:len(c.Literal)] {
+ lookupModulesRec(c, needle[len(c.Literal):], matches)
+ }
+ case kmodpb.RadixNode_WILDCARD:
+ for i := 0; i <= len(needle); i++ {
+ lookupModulesRec(c, needle[i:], matches)
+ }
+ case kmodpb.RadixNode_SINGLE_WILDCARD:
+ if len(needle) < 1 {
+ continue
+ }
+ lookupModulesRec(c, needle[1:], matches)
+ case kmodpb.RadixNode_BYTE_RANGE:
+ if len(needle) < 1 {
+ continue
+ }
+ if needle[0] >= byte(c.StartByte) && needle[0] <= byte(c.EndByte) {
+ lookupModulesRec(c, needle[1:], matches)
+ }
+ }
+ }
+ if len(needle) == 0 {
+ for _, mi := range n.ModuleIndex {
+ matches[mi] = true
+ }
+ }
+ return
+}
+
+// AddPattern adds a new pattern associated with a moduleIndex to the radix tree
+// rooted at root.
+func AddPattern(root *kmodpb.RadixNode, pattern string, moduleIndex uint32) error {
+ pp, err := parsePattern(pattern)
+ if err != nil {
+ return fmt.Errorf("error parsing pattern %q: %w", pattern, err)
+ }
+ if len(pp) > 0 {
+ pp[len(pp)-1].ModuleIndex = []uint32{moduleIndex}
+ } else {
+ // This exists to handle empty patterns, which have little use in
+ // practice (but their behavior is well-defined). It exists primarily
+ // to not crash in that case as well as to appease the Fuzzer.
+ root.ModuleIndex = append(root.ModuleIndex, moduleIndex)
+ }
+ return addPatternRec(root, pp, nil)
+}
+
+// addPatternRec recursively adds a new pattern to the radix tree.
+// If currPartOverride is non-nil it is used instead of the first part in the
+// parts array.
+func addPatternRec(n *kmodpb.RadixNode, parts []*kmodpb.RadixNode, currPartOverride *kmodpb.RadixNode) error {
+ if len(parts) == 0 {
+ return nil
+ }
+ var currPart *kmodpb.RadixNode
+ if currPartOverride != nil {
+ currPart = currPartOverride
+ } else {
+ currPart = parts[0]
+ }
+ for _, c := range n.Children {
+ if c.Type != currPart.Type {
+ continue
+ }
+ switch c.Type {
+ case kmodpb.RadixNode_LITERAL:
+ if c.Literal[0] == currPart.Literal[0] {
+ var i int
+ for i < len(c.Literal) && i < len(currPart.Literal) && c.Literal[i] == currPart.Literal[i] {
+ i++
+ }
+ if i == len(c.Literal) && i == len(currPart.Literal) {
+ if len(parts) == 1 {
+ c.ModuleIndex = append(c.ModuleIndex, parts[0].ModuleIndex...)
+ return nil
+ }
+ return addPatternRec(c, parts[1:], nil)
+ }
+ if i == len(c.Literal) {
+ return addPatternRec(c, parts, &kmodpb.RadixNode{Type: kmodpb.RadixNode_LITERAL, Literal: currPart.Literal[i:], ModuleIndex: currPart.ModuleIndex})
+ }
+ // Split current node
+ splitOldPart := &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_LITERAL,
+ Literal: c.Literal[i:],
+ Children: c.Children,
+ ModuleIndex: c.ModuleIndex,
+ }
+ var splitNewPart *kmodpb.RadixNode
+ // Current part is a strict subset of the node being traversed
+ if i == len(currPart.Literal) {
+ if len(parts) < 2 {
+ c.Children = []*kmodpb.RadixNode{splitOldPart}
+ c.Literal = currPart.Literal
+ c.ModuleIndex = currPart.ModuleIndex
+ return nil
+ }
+ splitNewPart = parts[1]
+ parts = parts[1:]
+ } else {
+ splitNewPart = &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_LITERAL,
+ Literal: currPart.Literal[i:],
+ ModuleIndex: currPart.ModuleIndex,
+ }
+ }
+ c.Children = []*kmodpb.RadixNode{
+ splitOldPart,
+ splitNewPart,
+ }
+ c.Literal = currPart.Literal[:i]
+ c.ModuleIndex = nil
+ return addPatternRec(splitNewPart, parts[1:], nil)
+ }
+
+ case kmodpb.RadixNode_BYTE_RANGE:
+ if c.StartByte == currPart.StartByte && c.EndByte == currPart.EndByte {
+ if len(parts) == 1 {
+ c.ModuleIndex = append(c.ModuleIndex, parts[0].ModuleIndex...)
+ }
+ return addPatternRec(c, parts[1:], nil)
+ }
+ case kmodpb.RadixNode_SINGLE_WILDCARD, kmodpb.RadixNode_WILDCARD:
+ if len(parts) == 1 {
+ c.ModuleIndex = append(c.ModuleIndex, parts[0].ModuleIndex...)
+ }
+ return addPatternRec(c, parts[1:], nil)
+ }
+ }
+ // No child or common prefix found, append node
+ n.Children = append(n.Children, currPart)
+ return addPatternRec(currPart, parts[1:], nil)
+}
+
+// PrintTree prints the tree from the given root node to standard out.
+// The output is not stable and should only be used for debugging/diagnostics.
+// It will log and exit the process if it encounters invalid nodes.
+func PrintTree(r *kmodpb.RadixNode) {
+ printTree(r, 0, false)
+}
+
+func printTree(r *kmodpb.RadixNode, indent int, noIndent bool) {
+ if !noIndent {
+ for i := 0; i < indent; i++ {
+ fmt.Print(" ")
+ }
+ }
+ if len(r.ModuleIndex) > 0 {
+ fmt.Printf("%v ", r.ModuleIndex)
+ }
+ switch r.Type {
+ case kmodpb.RadixNode_LITERAL:
+ fmt.Printf("%q: ", r.Literal)
+ case kmodpb.RadixNode_SINGLE_WILDCARD:
+ fmt.Printf("?: ")
+ case kmodpb.RadixNode_WILDCARD:
+ fmt.Printf("*: ")
+ case kmodpb.RadixNode_BYTE_RANGE:
+ fmt.Printf("[%c-%c]: ", rune(r.StartByte), rune(r.EndByte))
+ default:
+ log.Fatalf("Unknown tree type %T\n", r)
+ }
+ if len(r.Children) == 1 {
+ printTree(r.Children[0], indent, true)
+ return
+ }
+ fmt.Println("")
+ for _, c := range r.Children {
+ printTree(c, indent+1, false)
+ }
+}
+
+// parsePattern parses a string pattern into a non-hierarchical list of
+// RadixNodes. These nodes can then be futher modified and integrated into
+// a Radix tree.
+func parsePattern(pattern string) ([]*kmodpb.RadixNode, error) {
+ var out []*kmodpb.RadixNode
+ var i int
+ var currentLiteral strings.Builder
+ storeCurrentLiteral := func() {
+ if currentLiteral.Len() > 0 {
+ out = append(out, &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_LITERAL,
+ Literal: currentLiteral.String(),
+ })
+ currentLiteral.Reset()
+ }
+ }
+ for i < len(pattern) {
+ switch pattern[i] {
+ case '*':
+ storeCurrentLiteral()
+ i += 1
+ if len(out) > 0 && out[len(out)-1].Type == kmodpb.RadixNode_WILDCARD {
+ continue
+ }
+ out = append(out, &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_WILDCARD,
+ })
+ case '?':
+ storeCurrentLiteral()
+ out = append(out, &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_SINGLE_WILDCARD,
+ })
+ i += 1
+ case '[':
+ storeCurrentLiteral()
+ if len(pattern) <= i+4 {
+ return nil, errors.New("illegal byte range notation, not enough characters")
+ }
+ if pattern[i+2] != '-' || pattern[i+4] != ']' {
+ return nil, errors.New("illegal byte range notation, incorrect dash or closing character")
+ }
+ nn := &kmodpb.RadixNode{
+ Type: kmodpb.RadixNode_BYTE_RANGE,
+ StartByte: uint32(pattern[i+1]),
+ EndByte: uint32(pattern[i+3]),
+ }
+ if nn.StartByte > nn.EndByte {
+ return nil, errors.New("byte range start byte larger than end byte")
+ }
+ out = append(out, nn)
+ i += 5
+ case '\\':
+ if len(pattern) <= i+1 {
+ return nil, errors.New("illegal escape character at the end of the string")
+ }
+ currentLiteral.WriteByte(pattern[i+1])
+ i += 2
+ default:
+ currentLiteral.WriteByte(pattern[i])
+ i += 1
+ }
+ }
+ storeCurrentLiteral()
+ return out, nil
+}
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)
+ }
+ }
+ }
+ }
+ })
+}
diff --git a/metropolis/pkg/kmod/spec/BUILD.bazel b/metropolis/pkg/kmod/spec/BUILD.bazel
new file mode 100644
index 0000000..145ab7b
--- /dev/null
+++ b/metropolis/pkg/kmod/spec/BUILD.bazel
@@ -0,0 +1,23 @@
+load("@rules_proto//proto:defs.bzl", "proto_library")
+load("@io_bazel_rules_go//go:def.bzl", "go_library")
+load("@io_bazel_rules_go//proto:def.bzl", "go_proto_library")
+
+proto_library(
+ name = "spec_proto",
+ srcs = ["meta.proto"],
+ visibility = ["//visibility:public"],
+)
+
+go_proto_library(
+ name = "spec_go_proto",
+ importpath = "source.monogon.dev/metropolis/pkg/kmod/spec",
+ proto = ":spec_proto",
+ visibility = ["//visibility:public"],
+)
+
+go_library(
+ name = "spec",
+ embed = [":spec_go_proto"],
+ importpath = "source.monogon.dev/metropolis/pkg/kmod/spec",
+ visibility = ["//visibility:public"],
+)
diff --git a/metropolis/pkg/kmod/spec/gomod-generated-placeholder.go b/metropolis/pkg/kmod/spec/gomod-generated-placeholder.go
new file mode 100644
index 0000000..f09cd57
--- /dev/null
+++ b/metropolis/pkg/kmod/spec/gomod-generated-placeholder.go
@@ -0,0 +1 @@
+package spec
diff --git a/metropolis/pkg/kmod/spec/meta.proto b/metropolis/pkg/kmod/spec/meta.proto
new file mode 100644
index 0000000..a608b69
--- /dev/null
+++ b/metropolis/pkg/kmod/spec/meta.proto
@@ -0,0 +1,57 @@
+syntax = "proto3";
+
+package metropolis.pkg.kmod;
+
+option go_package = "source.monogon.dev/metropolis/pkg/kmod/spec";
+
+// Module contains important metadata about a Linux kernel module.
+message Module {
+ // Name of the module
+ string name = 1;
+ // Path of the module, relative to the module root.
+ // Unset if built-in.
+ string path = 2;
+ // List of Meta.modules indices on which this module depends.
+ repeated uint32 depends = 3;
+}
+
+message RadixNode {
+ enum Type {
+ // Matches one or more characters literally.
+ LITERAL = 0;
+ // Matches zero or more arbitrary characters.
+ WILDCARD = 1;
+ // Matches exactly one arbitrary character.
+ SINGLE_WILDCARD = 2;
+ // Matches exactly one character between start_byte and end_byte.
+ BYTE_RANGE = 3;
+ // Root matches nothing, but serves a the root node for a radix
+ // tree.
+ ROOT = 4;
+ }
+ Type type = 1;
+
+ // Only valid for LITERAL type
+ string literal = 2;
+
+ // Only valid when BYTE_RANGE type
+ uint32 start_byte = 3;
+ uint32 end_byte = 4;
+
+ // Contains a list of radix nodes which are children of this node.
+ repeated RadixNode children = 5;
+
+ // A list of module indices (in the Meta.modules list) which have
+ // match expressions ending at this node.
+ repeated uint32 module_index = 6;
+}
+
+// Meta contains metadata about all modules in a Linux kernel
+message Meta {
+ // Contains a list of modules, including built-in ones.
+ repeated Module modules = 1;
+
+ // Contains the root node of a radix tree for looking up modules to load
+ // for a given device modalias.
+ RadixNode module_device_matches = 2;
+}
\ No newline at end of file
diff --git a/metropolis/pkg/kmod/syscall.go b/metropolis/pkg/kmod/syscall.go
new file mode 100644
index 0000000..c4e7471
--- /dev/null
+++ b/metropolis/pkg/kmod/syscall.go
@@ -0,0 +1,45 @@
+package kmod
+
+import (
+ "errors"
+ "fmt"
+ "syscall"
+ "unsafe"
+
+ "golang.org/x/sys/unix"
+)
+
+// LoadModule loads a kernel module into the kernel.
+func LoadModule(file syscall.Conn, params string, flags uintptr) error {
+ sc, err := file.SyscallConn()
+ if err != nil {
+ return fmt.Errorf("failed getting SyscallConn handle: %w", err)
+ }
+ paramsRaw, err := unix.BytePtrFromString(params)
+ if err != nil {
+ return errors.New("invalid null byte in params")
+ }
+ ctrlErr := sc.Control(func(fd uintptr) {
+ _, _, err = unix.Syscall(unix.SYS_FINIT_MODULE, fd, uintptr(unsafe.Pointer(paramsRaw)), flags)
+ })
+ if ctrlErr != nil {
+ return fmt.Errorf("unable to get control handle: %w", ctrlErr)
+ }
+ if err != unix.Errno(0) {
+ return err
+ }
+ return nil
+}
+
+// UnloadModule unloads a kernel module from the kernel.
+func UnloadModule(name string, flags uintptr) error {
+ nameRaw, err := unix.BytePtrFromString(name)
+ if err != nil {
+ return errors.New("invalid null byte in name")
+ }
+ _, _, err = unix.Syscall(unix.SYS_DELETE_MODULE, uintptr(unsafe.Pointer(nameRaw)), flags, 0)
+ if err != unix.Errno(0) {
+ return err
+ }
+ return err
+}