treewide: introduce osbase package and move things around
All except localregistry moved from metropolis/pkg to osbase,
localregistry moved to metropolis/test as its only used there anyway.
Change-Id: If1a4bf377364bef0ac23169e1b90379c71b06d72
Reviewed-on: https://review.monogon.dev/c/monogon/+/3079
Tested-by: Jenkins CI
Reviewed-by: Serge Bazanski <serge@monogon.tech>
diff --git a/osbase/kmod/BUILD.bazel b/osbase/kmod/BUILD.bazel
new file mode 100644
index 0000000..a8ade05
--- /dev/null
+++ b/osbase/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("//osbase/test/ktest:ktest.bzl", "ktest")
+
+go_library(
+ name = "kmod",
+ srcs = [
+ "manager.go",
+ "meta.go",
+ "modinfo.go",
+ "radix.go",
+ "syscall.go",
+ ],
+ importpath = "source.monogon.dev/osbase/kmod",
+ visibility = ["//visibility:public"],
+ deps = [
+ "//osbase/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 = [
+ "//osbase/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 = "//osbase/test/ktest:linux-testing",
+ metadata = "@linux-firmware//:metadata",
+)
+
+ktest(
+ fsspecs = [
+ ":firmware",
+ ],
+ tester = ":kmod_test",
+)
diff --git a/osbase/kmod/manager.go b/osbase/kmod/manager.go
new file mode 100644
index 0000000..6369212
--- /dev/null
+++ b/osbase/kmod/manager.go
@@ -0,0 +1,159 @@
+package kmod
+
+import (
+ "bufio"
+ "errors"
+ "fmt"
+ "os"
+ "path/filepath"
+ "strings"
+ "sync"
+
+ "golang.org/x/sys/unix"
+ "google.golang.org/protobuf/proto"
+
+ kmodpb "source.monogon.dev/osbase/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 && errors.Is(err, unix.EEXIST) {
+ return fmt.Errorf("error loading kernel module %v: %w", modMeta.Name, err)
+ }
+ s.loadedModules[modIdx] = true
+ return nil
+}
diff --git a/osbase/kmod/manager_test.go b/osbase/kmod/manager_test.go
new file mode 100644
index 0000000..43c9428
--- /dev/null
+++ b/osbase/kmod/manager_test.go
@@ -0,0 +1,48 @@
+package kmod
+
+import (
+ "errors"
+ "os"
+ "testing"
+)
+
+func TestManagerIntegration(t *testing.T) {
+ if os.Getenv("IN_KTEST") != "true" {
+ t.Skip("Not in ktest")
+ }
+ 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/osbase/kmod/meta.go b/osbase/kmod/meta.go
new file mode 100644
index 0000000..c005a7c
--- /dev/null
+++ b/osbase/kmod/meta.go
@@ -0,0 +1,50 @@
+package kmod
+
+import (
+ "fmt"
+ "log"
+
+ kmodpb "source.monogon.dev/osbase/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/osbase/kmod/modinfo.go b/osbase/kmod/modinfo.go
new file mode 100644
index 0000000..5c01681
--- /dev/null
+++ b/osbase/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 = 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"]
+}
+
+// Licenses 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/osbase/kmod/radix.go b/osbase/kmod/radix.go
new file mode 100644
index 0000000..c20b48d
--- /dev/null
+++ b/osbase/kmod/radix.go
@@ -0,0 +1,267 @@
+package kmod
+
+import (
+ "errors"
+ "fmt"
+ "log"
+ "sort"
+ "strings"
+
+ kmodpb "source.monogon.dev/osbase/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
+ }
+ }
+}
+
+// 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/osbase/kmod/radix_test.go b/osbase/kmod/radix_test.go
new file mode 100644
index 0000000..62e9d95
--- /dev/null
+++ b/osbase/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/osbase/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/osbase/kmod/spec/BUILD.bazel b/osbase/kmod/spec/BUILD.bazel
new file mode 100644
index 0000000..75bcf63
--- /dev/null
+++ b/osbase/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/osbase/kmod/spec",
+ proto = ":spec_proto",
+ visibility = ["//visibility:public"],
+)
+
+go_library(
+ name = "spec",
+ embed = [":spec_go_proto"],
+ importpath = "source.monogon.dev/osbase/kmod/spec",
+ visibility = ["//visibility:public"],
+)
diff --git a/osbase/kmod/spec/gomod-generated-placeholder.go b/osbase/kmod/spec/gomod-generated-placeholder.go
new file mode 100644
index 0000000..f09cd57
--- /dev/null
+++ b/osbase/kmod/spec/gomod-generated-placeholder.go
@@ -0,0 +1 @@
+package spec
diff --git a/osbase/kmod/spec/meta.proto b/osbase/kmod/spec/meta.proto
new file mode 100644
index 0000000..ed2cc73
--- /dev/null
+++ b/osbase/kmod/spec/meta.proto
@@ -0,0 +1,57 @@
+syntax = "proto3";
+
+package metropolis.pkg.kmod;
+
+option go_package = "source.monogon.dev/osbase/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/osbase/kmod/syscall.go b/osbase/kmod/syscall.go
new file mode 100644
index 0000000..41d3233
--- /dev/null
+++ b/osbase/kmod/syscall.go
@@ -0,0 +1,46 @@
+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")
+ }
+ var errNo unix.Errno
+ ctrlErr := sc.Control(func(fd uintptr) {
+ _, _, errNo = 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 errNo != unix.Errno(0) {
+ return errNo
+ }
+ 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")
+ }
+ _, _, errNo := unix.Syscall(unix.SYS_DELETE_MODULE, uintptr(unsafe.Pointer(nameRaw)), flags, 0)
+ if errNo != unix.Errno(0) {
+ return errNo
+ }
+ return nil
+}