Repository: cilium/ebpf
Pull request #1772 (2025-05-01 14:38:03)

btf: lazy decoding of string table
Most of the time in parsing vmlinux BTF is spent in constructing the essentialName -> TypeID index.

1. We need to allocate a lot of strings
2. We need to do a lot of hash table lookups

Replace the hash table with a "fuzzy" index, which doesn't require allocating strings. The trade-off is that lookups now become more expensive, but that is a fine trade-off to make.

    core: 1
    goos: linux
    goarch: amd64
    pkg: github.com/cilium/ebpf/btf
    cpu: 13th Gen Intel(R) Core(TM) i7-1365U
                    │  base.txt   │          lazy-strings.txt           │
                    │   sec/op    │    sec/op     vs base               │
    ParseVmlinux      27.24m ± 1%   15.49m ±  1%  -43.15% (p=0.002 n=6)
    IterateVmlinux    149.9m ± 2%   132.3m ± 15%  -11.73% (p=0.041 n=6)
    InspectorGadget   35.08m ± 2%   21.28m ±  5%  -39.34% (p=0.002 n=6)
    geomean           52.32m        35.20m        -32.73%
    
                    │   base.txt    │          lazy-strings.txt           │
                    │     B/op      │     B/op      vs base               │
    ParseVmlinux       9.969Mi ± 0%   4.960Mi ± 0%  -50.25% (p=0.002 n=6)
    IterateVmlinux     34.72Mi ± 0%   31.92Mi ± 0%   -8.07% (p=0.002 n=6)
    InspectorGadget   11.994Mi ± 0%   7.169Mi ± 0%  -40.23% (p=0.002 n=6)
    geomean            16.07Mi        10.43Mi       -35.10%
    
                    │   base.txt    │          lazy-strings.txt          │
                    │   allocs/op   │  allocs/op   vs base               │
    ParseVmlinux      146058.0 ± 0%    162.0 ± 0%  -99.89% (p=0.002 n=6)
    IterateVmlinux      272.9k ± 0%   291.5k ± 0%   +6.83% (p=0.002 n=6)
    InspectorGadget    155.03k ± 0%   24.30k ± 0%  -84.32% (p=0.002 n=6)
    geomean             183.5k        10.47k       -94.29%



Patch:
diff --git a/btf/btf.go b/btf/btf.go
index 4bf0f3d..8112b6c 100644
--- a/btf/btf.go
+++ b/btf/btf.go
@@ -12,6 +12,7 @@ import (
 	"math"
 	"os"
 	"reflect"
+	"slices"
 
 	"github.com/cilium/ebpf/internal"
 	"github.com/cilium/ebpf/internal/sys"
@@ -243,6 +244,10 @@ func guessRawBTFByteOrder(r io.ReaderAt) binary.ByteOrder {
 // fixupDatasec attempts to patch up missing info in Datasecs and its members by
 // supplementing them with information from the ELF headers and symbol table.
 func (elf *elfData) fixupDatasec(typ Type) error {
+	if elf == nil {
+		return nil
+	}
+
 	if ds, ok := typ.(*Datasec); ok {
 		if elf.fixups[ds] {
 			return nil
@@ -373,10 +378,6 @@ func (s *Spec) TypeByID(id TypeID) (Type, error) {
 		return nil, fmt.Errorf("inflate type: %w", err)
 	}
 
-	if s.elf == nil {
-		return typ, nil
-	}
-
 	if err := s.elf.fixupDatasec(typ); err != nil {
 		return nil, err
 	}
@@ -399,28 +400,25 @@ func (s *Spec) TypeID(typ Type) (TypeID, error) {
 //
 // Returns an error wrapping ErrNotFound if no matching Type exists in the Spec.
 func (s *Spec) AnyTypesByName(name string) ([]Type, error) {
-	typeIDs := s.TypeIDsByName(newEssentialName(name))
-	if len(typeIDs) == 0 {
-		return nil, fmt.Errorf("type name %s: %w", name, ErrNotFound)
-	}
-
-	// Return a copy to prevent changes to namedTypes.
-	result := make([]Type, 0, len(typeIDs))
-	for _, id := range typeIDs {
-		typ, err := s.TypeByID(id)
-		if errors.Is(err, ErrNotFound) {
-			return nil, fmt.Errorf("no type with ID %d", id)
-		} else if err != nil {
-			return nil, err
-		}
+	types, err := s.TypesByName(newEssentialName(name))
+	if err != nil {
+		return nil, err
+	}
 
+	for i := 0; i < len(types); i++ {
 		// Match against the full name, not just the essential one
 		// in case the type being looked up is a struct flavor.
-		if typ.TypeName() == name {
-			result = append(result, typ)
+		if types[i].TypeName() != name {
+			types = slices.Delete(types, i, i+1)
+			continue
+		}
+
+		if err := s.elf.fixupDatasec(types[i]); err != nil {
+			return nil, err
 		}
 	}
-	return result, nil
+
+	return types, nil
 }
 
 // AnyTypeByName returns a Type with the given name.
diff --git a/btf/core.go b/btf/core.go
index ca4997f..f128011 100644
--- a/btf/core.go
+++ b/btf/core.go
@@ -6,7 +6,6 @@ import (
 	"fmt"
 	"math"
 	"reflect"
-	"slices"
 	"strconv"
 	"strings"
 
@@ -265,16 +264,14 @@ func CORERelocate(relos []*CORERelocation, targets []*Spec, bo binary.ByteOrder,
 
 		var targetTypes []Type
 		for _, target := range targets {
-			namedTypeIDs := target.TypeIDsByName(essentialName)
-			targetTypes = slices.Grow(targetTypes, len(namedTypeIDs))
-			for _, id := range namedTypeIDs {
-				typ, err := target.TypeByID(id)
-				if err != nil {
-					return nil, err
-				}
-
-				targetTypes = append(targetTypes, typ)
+			namedTypes, err := target.TypesByName(essentialName)
+			if errors.Is(err, ErrNotFound) {
+				continue
+			} else if err != nil {
+				return nil, err
 			}
+
+			targetTypes = append(targetTypes, namedTypes...)
 		}
 
 		fixups, err := coreCalculateFixups(group.relos, targetTypes, bo, resolveTargetTypeID)
diff --git a/btf/strings.go b/btf/strings.go
index 7c31461..f4a3957 100644
--- a/btf/strings.go
+++ b/btf/strings.go
@@ -1,21 +1,17 @@
 package btf
 
 import (
-	"bufio"
 	"bytes"
 	"errors"
 	"fmt"
 	"io"
 	"maps"
-	"slices"
 	"strings"
 )
 
 type stringTable struct {
-	base    *stringTable
-	offsets []uint32
-	prevIdx int
-	strings []string
+	base  *stringTable
+	bytes []byte
 }
 
 // sizedReader is implemented by bytes.Reader, io.SectionReader, strings.Reader, etc.
@@ -29,89 +25,67 @@ func readStringTable(r sizedReader, base *stringTable) (*stringTable, error) {
 	// from the last entry offset of the base BTF.
 	firstStringOffset := uint32(0)
 	if base != nil {
-		idx := len(base.offsets) - 1
-		firstStringOffset = base.offsets[idx] + uint32(len(base.strings[idx])) + 1
+		firstStringOffset = uint32(len(base.bytes))
 	}
 
-	// Derived from vmlinux BTF.
-	const averageStringLength = 16
-
-	n := int(r.Size() / averageStringLength)
-	offsets := make([]uint32, 0, n)
-	strings := make([]string, 0, n)
-
-	offset := firstStringOffset
-	scanner := bufio.NewScanner(r)
-	scanner.Split(splitNull)
-	for scanner.Scan() {
-		str := scanner.Text()
-		offsets = append(offsets, offset)
-		strings = append(strings, str)
-		offset += uint32(len(str)) + 1
-	}
-	if err := scanner.Err(); err != nil {
+	bytes := make([]byte, r.Size())
+	if _, err := io.ReadFull(r, bytes); err != nil {
 		return nil, err
 	}
 
-	if len(strings) == 0 {
+	if len(bytes) == 0 {
 		return nil, errors.New("string table is empty")
 	}
 
-	if firstStringOffset == 0 && strings[0] != "" {
-		return nil, errors.New("first item in string table is non-empty")
+	if bytes[len(bytes)-1] != 0 {
+		return nil, errors.New("string table isn't null terminated")
 	}
 
-	return &stringTable{base, offsets, 0, strings}, nil
-}
-
-func splitNull(data []byte, atEOF bool) (advance int, token []byte, err error) {
-	i := bytes.IndexByte(data, 0)
-	if i == -1 {
-		if atEOF && len(data) > 0 {
-			return 0, nil, errors.New("string table isn't null terminated")
-		}
-		return 0, nil, nil
+	if firstStringOffset == 0 && bytes[0] != 0 {
+		return nil, errors.New("first item in string table is non-empty")
 	}
 
-	return i + 1, data[:i], nil
+	return &stringTable{base: base, bytes: bytes}, nil
 }
 
 func (st *stringTable) Lookup(offset uint32) (string, error) {
-	if st.base != nil && offset <= st.base.offsets[len(st.base.offsets)-1] {
-		return st.base.lookup(offset)
+	// Fast path: zero offset is the empty string, looked up frequently.
+	if offset == 0 {
+		return "", nil
 	}
-	return st.lookup(offset)
+
+	b, err := st.lookupSlow(offset)
+	return string(b), err
 }
 
-func (st *stringTable) lookup(offset uint32) (string, error) {
+func (st *stringTable) LookupBytes(offset uint32) ([]byte, error) {
 	// Fast path: zero offset is the empty string, looked up frequently.
-	if offset == 0 && st.base == nil {
-		return "", nil
+	if offset == 0 {
+		return nil, nil
 	}
 
-	// Accesses tend to be globally increasing, so check if the next string is
-	// the one we want. This skips the binary search in about 50% of cases.
-	if st.prevIdx+1 < len(st.offsets) && st.offsets[st.prevIdx+1] == offset {
-		st.prevIdx++
-		return st.strings[st.prevIdx], nil
-	}
+	return st.lookupSlow(offset)
+}
 
-	i, found := slices.BinarySearch(st.offsets, offset)
-	if !found {
-		return "", fmt.Errorf("offset %d isn't start of a string", offset)
+func (st *stringTable) lookupSlow(offset uint32) ([]byte, error) {
+	if st.base != nil {
+		n := uint32(len(st.base.bytes))
+		if offset < n {
+			return st.base.lookupSlow(offset)
+		}
+		offset -= n
 	}
 
-	// Set the new increment index, but only if its greater than the current.
-	if i > st.prevIdx+1 {
-		st.prevIdx = i
+	if offset > uint32(len(st.bytes)) {
+		return nil, fmt.Errorf("offset %d is out of bounds of string table", offset)
 	}
 
-	return st.strings[i], nil
-}
+	if offset > 0 && st.bytes[offset-1] != 0 {
+		return nil, fmt.Errorf("offset %d is not the beginning of a string", offset)
+	}
 
-// Num returns the number of strings in the table.
-func (st *stringTable) Num() int {
-	return len(st.strings)
+	i := bytes.IndexByte(st.bytes[offset:], 0)
+	return st.bytes[offset : offset+uint32(i)], nil
 }
 
 // stringTableBuilder builds BTF string tables.
diff --git a/btf/unmarshal.go b/btf/unmarshal.go
index 98cd017..a55d79d 100644
--- a/btf/unmarshal.go
+++ b/btf/unmarshal.go
@@ -1,12 +1,15 @@
 package btf
 
 import (
+	"bytes"
 	"encoding/binary"
 	"fmt"
+	"hash/maphash"
 	"io"
 	"iter"
 	"maps"
 	"math"
+	"slices"
 	"sync"
 )
 
@@ -21,9 +24,10 @@ type decoder struct {
 	firstTypeID TypeID
 	// Map from TypeID to offset of the marshaled data in raw. Contains an entry
 	// for each TypeID, including 0 aka Void. The offset for Void is invalid.
-	offsets    []int
-	declTags   map[TypeID][]TypeID
-	namedTypes map[essentialName][]TypeID
+	offsets  []int
+	declTags map[TypeID][]TypeID
+	// An index from essentialName to TypeID.
+	namedTypes *fuzzyStringIndex
 
 	// Protection for mutable fields below.
 	mu              sync.Mutex
@@ -74,7 +78,7 @@ func newDecoder(raw []byte, bo binary.ByteOrder, strings *stringTable, base *dec
 
 	offsets := make([]int, 0, numTypes)
 	declTags := make(map[TypeID][]TypeID, numDeclTags)
-	namedTypes := make(map[essentialName][]TypeID, numNamedTypes)
+	namedTypes := newFuzzyStringIndex(numNamedTypes)
 
 	if firstTypeID == 0 {
 		// Add a sentinel for Void.
@@ -94,27 +98,27 @@ func newDecoder(raw []byte, bo binary.ByteOrder, strings *stringTable, base *dec
 		}
 
 		// Build named type index.
-		name, err := strings.Lookup(header.NameOff)
+		name, err := strings.LookupBytes(header.NameOff)
 		if err != nil {
 			return nil, fmt.Errorf("lookup type name for id %v: %w", id, err)
 		}
 
-		if name := newEssentialName(name); name != "" {
-			ids := namedTypes[name]
-			if ids == nil {
-				// Almost all names will only have a single name to them.
-				// Explicitly allocate a slice of capacity 1 instead of relying
-				// on append behaviour.
-				ids = []TypeID{id}
-			} else {
-				ids = append(ids, id)
+		if len(name) > 0 {
+			if i := bytes.Index(name, []byte("___")); i != -1 {
+				// Flavours are rare. It's cheaper to find the first index for some
+				// reason.
+				i = bytes.LastIndex(name, []byte("___"))
+				name = name[:i]
 			}
-			namedTypes[name] = ids
+
+			namedTypes.Add(name, id)
 		}
 
 		id++
 	}
 
+	namedTypes.Build()
+
 	return &decoder{
 		base,
 		bo,
@@ -211,11 +215,28 @@ func (d *decoder) TypeID(typ Type) (TypeID, error) {
 	return id, nil
 }
 
-// TypeIDsByName returns all type IDs which have the given essential name.
+// TypesByName returns all types which have the given essential name.
 //
-// The returned slice must not be modified.
-func (d *decoder) TypeIDsByName(name essentialName) []TypeID {
-	return d.namedTypes[name]
+// Returns ErrNotFound if no matching Type exists.
+func (d *decoder) TypesByName(name essentialName) ([]Type, error) {
+	var types []Type
+	for id := range d.namedTypes.Find(string(name)) {
+		typ, err := d.TypeByID(id)
+		if err != nil {
+			return nil, err
+		}
+
+		if newEssentialName(typ.TypeName()) == name {
+			// Deal with hash collisions by checking against the name.
+			types = append(types, typ)
+		}
+	}
+
+	if len(types) == 0 {
+		return nil, fmt.Errorf("type with name %s: %w", name, ErrNotFound)
+	}
+
+	return types, nil
 }
 
 // TypeByID decodes a type and any of its descendants.
@@ -649,3 +670,73 @@ func (d *decoder) inflateType(id TypeID) (typ Type, err error) {
 
 	return typ, nil
 }
+
+// An index from string to TypeID.
+//
+// Fuzzy because it may return false positive matches.
+type fuzzyStringIndex struct {
+	seed    maphash.Seed
+	entries []fuzzyStringIndexEntry
+}
+
+func newFuzzyStringIndex(capacity int) *fuzzyStringIndex {
+	return &fuzzyStringIndex{
+		maphash.MakeSeed(),
+		make([]fuzzyStringIndexEntry, 0, capacity),
+	}
+}
+
+// Add a string to the index.
+//
+// Calling the method with identical arguments will create duplicate entries.
+func (idx *fuzzyStringIndex) Add(name []byte, id TypeID) {
+	hash := uint32(maphash.Bytes(idx.seed, name))
+	idx.entries = append(idx.entries, newFuzzyStringIndexEntry(hash, id))
+}
+
+// Build the index.
+//
+// Must be called after [Add] and before [Match].
+func (idx *fuzzyStringIndex) Build() {
+	slices.Sort(idx.entries)
+}
+
+// Find TypeIDs which may match the name.
+//
+// May return false positives, but is guaranteed to not have false negatives.
+//
+// You must call [Build] at least once before calling this method.
+func (idx *fuzzyStringIndex) Find(name string) iter.Seq[TypeID] {
+	return func(yield func(TypeID) bool) {
+		hash := uint32(maphash.String(idx.seed, name))
+
+		// We match only on the first 32 bits here, so ignore found.
+		i, _ := slices.BinarySearch(idx.entries, fuzzyStringIndexEntry(hash)<<32)
+		for i := i; i < len(idx.entries); i++ {
+			if idx.entries[i].hash() != hash {
+				break
+			}
+
+			if !yield(idx.entries[i].id()) {
+				return
+			}
+		}
+	}
+}
+
+// Tuple mapping the hash of an essential name to a type.
+//
+// Encoded in an uint64 so that it implements cmp.Ordered.
+type fuzzyStringIndexEntry uint64
+
+func newFuzzyStringIndexEntry(hash uint32, id TypeID) fuzzyStringIndexEntry {
+	return fuzzyStringIndexEntry(hash)<<32 | fuzzyStringIndexEntry(id)
+}
+
+func (e fuzzyStringIndexEntry) hash() uint32 {
+	return uint32(e >> 32)
+}
+
+func (e fuzzyStringIndexEntry) id() TypeID {
+	return TypeID(e)
+}


Test patch:
diff --git a/btf/btf_test.go b/btf/btf_test.go
index 35fca41..d205a11 100644
--- a/btf/btf_test.go
+++ b/btf/btf_test.go
@@ -249,22 +249,9 @@ func BenchmarkIterateVmlinux(b *testing.B) {
 func TestParseCurrentKernelBTF(t *testing.T) {
 	spec := vmlinuxSpec(t)
 
-	if len(spec.namedTypes) == 0 {
+	if len(spec.offsets) == 0 {
 		t.Fatal("Empty kernel BTF")
 	}
-
-	totalBytes := 0
-	distinct := 0
-	seen := make(map[string]bool)
-	for _, str := range spec.strings.strings {
-		totalBytes += len(str)
-		if !seen[str] {
-			distinct++
-			seen[str] = true
-		}
-	}
-	t.Logf("%d strings total, %d distinct", len(spec.strings.strings), distinct)
-	t.Logf("Average string size: %.0f", float64(totalBytes)/float64(len(spec.strings.strings)))
 }
 
 func TestFindVMLinux(t *testing.T) {
@@ -280,7 +267,7 @@ func TestFindVMLinux(t *testing.T) {
 		t.Fatal("Can't load BTF:", err)
 	}
 
-	if len(spec.namedTypes) == 0 {
+	if len(spec.offsets) == 0 {
 		t.Fatal("Empty kernel BTF")
 	}
 }
diff --git a/btf/unmarshal_test.go b/btf/unmarshal_test.go
new file mode 100644
index 0000000..cf9bd95
--- /dev/null
+++ b/btf/unmarshal_test.go
@@ -0,0 +1,36 @@
+package btf
+
+import (
+	"iter"
+	"math"
+	"testing"
+
+	"github.com/go-quicktest/qt"
+)
+
+func TestFuzzyStringIndex(t *testing.T) {
+	idx := newFuzzyStringIndex(10)
+	count := testing.AllocsPerRun(1, func() {
+		idx.Add([]byte("foo"), 1)
+	})
+	qt.Assert(t, qt.Equals(count, 0))
+
+	idx.entries = idx.entries[:0]
+	idx.Add([]byte("foo"), 1)
+	idx.Add([]byte("bar"), 2)
+	idx.Add([]byte("baz"), 3)
+	idx.Build()
+
+	all := func(it iter.Seq[TypeID]) (ids []TypeID) {
+		for id := range it {
+			ids = append(ids, id)
+		}
+		return
+	}
+
+	qt.Assert(t, qt.SliceContains(all(idx.Find("foo")), 1))
+	qt.Assert(t, qt.SliceContains(all(idx.Find("bar")), 2))
+	qt.Assert(t, qt.SliceContains(all(idx.Find("baz")), 3))
+
+	qt.Assert(t, qt.IsTrue(newFuzzyStringIndexEntry(0, math.MaxUint32) < newFuzzyStringIndexEntry(1, 0)))
+}