Repository: cilium/ebpf
Pull request #609 (2022-03-28 19:38:18)

asm: add Instruction Source metadata
asm: add Instruction Source metadata

    This commit adds Source metadata to Instruction, which is data about
    the origin of a series of Instructions. A Source can be any fmt.Stringer.

    Instructions.Format will now print the source information in-line with the
    Instruction on which it is set. This results in instructions being annotated
    with original source code when loaded from an ELF file, or custom annotations
    if fmt.Stringers are ssigned using Instruction.WithSource.

asm: use sparse metadata

    Replace the struct based metadata with a linked list. This reduces the amount of memory
    needed when the metadata is sparse, aka when there are more different kinds of metadata.
    This also allows packages to have their own private metadata, which we'll use to store
    BTF ext_infos.

    The most common operation on metadata is Get, since we need to check for the presence of
    multiple bits of metadata for every single instruction. This is captured by the get_miss
    benchmark. The second most operation will be repeated calls to Set. This is captured
    by the add_first and add_last benchmarks.

    My initial implementation used a map[interface{}]interface{} to store metadata, but it
    turns out that a linked list is more efficient. When using a map, each additional call
    to Set has to copy all previously set keys. We can avoid this with the linked list since
    we can simply prepend a new item.

    Timo proposed an implementation based on a slice, but this too suffers from having to copy
    previous KVs.

        name \ time/op           map.txt      slice.txt    ll.txt
        Metadata/add_first-4     97.6ns ± 2%  48.4ns ± 0%  25.1ns ± 2%
        Metadata/add_last-4       162ns ± 1%   104ns ± 1%    27ns ± 1%
        Metadata/add_existing-4  15.0ns ± 0%   9.0ns ± 0%   7.2ns ± 1%
        Metadata/get_miss-4      8.10ns ± 0%  3.73ns ± 0%  2.80ns ± 0%

        name \ alloc/op          map.txt      slice.txt    ll.txt
        Metadata/add_first-4       336B ± 0%     56B ± 0%     48B ± 0%
        Metadata/add_last-4        336B ± 0%    216B ± 0%     48B ± 0%
        Metadata/add_existing-4   0.00B        0.00B        0.00B
        Metadata/get_miss-4       0.00B        0.00B        0.00B

        name \ allocs/op         map.txt      slice.txt    ll.txt
        Metadata/add_first-4       2.00 ± 0%    2.00 ± 0%    1.00 ± 0%
        Metadata/add_last-4        2.00 ± 0%    3.00 ± 0%    1.00 ± 0%
        Metadata/add_existing-4    0.00         0.00         0.00
        Metadata/get_miss-4        0.00         0.00         0.00

elf: add simple benchmark

lmb: > I'm wondering if we could fold the value == nil case into m.remove() so we can avoid the fallthrough behaviour and make it more concise.

I looked into this, and it's not more straight forward. I think of `Set` in two stages: first, obtain a `head` that doesn't contain an element with `key` in it. Second, depending on `value`, prepend an element or use the new head directly.
lmb: I've rejigged `Set` once more, I think it's now as clear as it'll get. Let me know what you think!

Patch:
diff --git a/asm/instruction.go b/asm/instruction.go
index 0f99d18..5bf9920 100644
--- a/asm/instruction.go
+++ b/asm/instruction.go
@@ -37,8 +37,8 @@ type Instruction struct {
 	Offset   int16
 	Constant int64
 
-	// Metadata contains optional metadata about this instruction
-	metadata *metadata
+	// Metadata contains optional metadata about this instruction.
+	Metadata Metadata
 }
 
 // Unmarshal decodes a BPF instruction.
@@ -139,10 +139,8 @@ func (ins *Instruction) AssociateMap(m FDer) error {
 		return errors.New("not a load from a map")
 	}
 
-	ins.setMap(m)
-
-	// Remove any Reference as it has now been resolved.
-	*ins = ins.WithReference("")
+	ins.Metadata.Set(referenceMeta{}, nil)
+	ins.Metadata.Set(mapMeta{}, m)
 
 	return nil
 }
@@ -178,8 +176,8 @@ func (ins *Instruction) encodeMapFD(fd int) {
 // Deprecated: use Map() instead.
 func (ins *Instruction) MapPtr() int {
 	// If there is a map associated with the instruction, return its FD.
-	if ins.metadata != nil && ins.metadata.bpfMap != nil {
-		return ins.metadata.bpfMap.FD()
+	if fd := ins.Metadata.Get(mapMeta{}); fd != nil {
+		return fd.(FDer).FD()
 	}
 
 	// Fall back to the fd stored in the Constant field
@@ -355,14 +353,12 @@ func (ins Instruction) Size() uint64 {
 	return uint64(InstructionSize * ins.OpCode.rawInstructions())
 }
 
+type symbolMeta struct{}
+
 // WithSymbol marks the Instruction as a Symbol, which other Instructions
 // can point to using corresponding calls to WithReference.
 func (ins Instruction) WithSymbol(name string) Instruction {
-	if ins.Symbol() == name {
-		return ins
-	}
-
-	ins.copyMetadata().symbol = name
+	ins.Metadata.Set(symbolMeta{}, name)
 	return ins
 }
 
@@ -377,46 +373,56 @@ func (ins Instruction) Sym(name string) Instruction {
 // otherwise returns an empty string. A symbol is often an Instruction
 // at the start of a function body.
 func (ins Instruction) Symbol() string {
-	return ins.metadata.Symbol()
+	sym, _ := ins.Metadata.Get(symbolMeta{}).(string)
+	return sym
 }
 
+type referenceMeta struct{}
+
 // WithReference makes ins reference another Symbol or map by name.
 func (ins Instruction) WithReference(ref string) Instruction {
-	if ins.Reference() == ref {
-		return ins
-	}
-
-	ins.copyMetadata().reference = ref
+	ins.Metadata.Set(referenceMeta{}, ref)
 	return ins
 }
 
 // Reference returns the Symbol or map name referenced by ins, if any.
 func (ins Instruction) Reference() string {
-	return ins.metadata.Reference()
+	ref, _ := ins.Metadata.Get(referenceMeta{}).(string)
+	return ref
 }
 
+type mapMeta struct{}
+
 // Map returns the Map referenced by ins, if any.
 // An Instruction will contain a Map if e.g. it references an existing,
 // pinned map that was opened during ELF loading.
 func (ins Instruction) Map() FDer {
-	return ins.metadata.Map()
+	fd, _ := ins.Metadata.Get(mapMeta{}).(FDer)
+	return fd
 }
 
-// copyMetadata is a convenience method for copying ins.metadata, assigning
-// the new copy to its metadata field and returning a pointer to the copy
-// so one access can be chained.
-func (ins *Instruction) copyMetadata() *metadata {
-	ins.metadata = ins.metadata.copy()
-	return ins.metadata
+type sourceMeta struct{}
+
+// WithSource adds source information about the Instruction.
+func (ins Instruction) WithSource(src fmt.Stringer) Instruction {
+	ins.Metadata.Set(sourceMeta{}, src)
+	return ins
 }
 
-// setMap sets the given Map m in the metadata of this instruction.
-func (ins *Instruction) setMap(m FDer) {
-	if ins.metadata.Map() == m {
-		return
-	}
+// Source returns source information about the Instruction. The field is
+// present when the compiler emits BTF line info about the Instruction and
+// usually contains the line of source code responsible for it.
+func (ins Instruction) Source() fmt.Stringer {
+	str, _ := ins.Metadata.Get(sourceMeta{}).(fmt.Stringer)
+	return str
+}
 
-	ins.copyMetadata().bpfMap = m
+// A Comment can be passed to Instruction.WithSource to add a comment
+// to an instruction.
+type Comment string
+
+func (s Comment) String() string {
+	return string(s)
 }
 
 // FDer represents a resource tied to an underlying file descriptor.
@@ -426,54 +432,6 @@ type FDer interface {
 	FD() int
 }
 
-// metadata holds metadata about an Instruction.
-type metadata struct {
-	// reference denotes a reference (e.g. a jump) to another symbol.
-	reference string
-	// symbol denotes an instruction at the start of a function body.
-	symbol string
-
-	// bpfMap denotes the Map whose fd is used by this instruction.
-	bpfMap FDer
-}
-
-// Reference is a safe accessor to metadata's reference field.
-// It can be called on a nil m, in which case it will return the default value.
-func (m *metadata) Reference() string {
-	if m == nil {
-		return ""
-	}
-	return m.reference
-}
-
-// Symbol is a safe accessor to metadata's symbol field.
-// It can be called on a nil m, in which case it will return the default value.
-func (m *metadata) Symbol() string {
-	if m == nil {
-		return ""
-	}
-	return m.symbol
-}
-
-// Map is a safe accessor to metadata's bpfMap field.
-// It can be called on a nil m, in which case it will return the default value.
-func (m *metadata) Map() FDer {
-	if m == nil {
-		return nil
-	}
-	return m.bpfMap
-}
-
-// copy returns a copy of metadata.
-// Always returns a valid pointer, even when called on a nil metadata.
-func (m *metadata) copy() *metadata {
-	var copy metadata
-	if m != nil {
-		copy = *m
-	}
-	return &copy
-}
-
 // Instructions is an eBPF program.
 type Instructions []Instruction
 
@@ -697,6 +655,12 @@ func (insns Instructions) Format(f fmt.State, c rune) {
 		if iter.Ins.Symbol() != "" {
 			fmt.Fprintf(f, "%s%s:\n", symIndent, iter.Ins.Symbol())
 		}
+		if src := iter.Ins.Source(); src != nil {
+			line := strings.TrimSpace(src.String())
+			if line != "" {
+				fmt.Fprintf(f, "%s%*s; %s\n", indent, offsetWidth, " ", line)
+			}
+		}
 		fmt.Fprintf(f, "%s%*d: %v\n", indent, offsetWidth, iter.Offset, iter.Ins)
 	}
 }
diff --git a/asm/metadata.go b/asm/metadata.go
new file mode 100644
index 0000000..dd368a9
--- /dev/null
+++ b/asm/metadata.go
@@ -0,0 +1,80 @@
+package asm
+
+// Metadata contains metadata about an instruction.
+type Metadata struct {
+	head *metaElement
+}
+
+type metaElement struct {
+	next       *metaElement
+	key, value interface{}
+}
+
+// Find the element containing key.
+//
+// Returns nil if there is no such element.
+func (m *Metadata) find(key interface{}) *metaElement {
+	for e := m.head; e != nil; e = e.next {
+		if e.key == key {
+			return e
+		}
+	}
+	return nil
+}
+
+// Remove an element from the linked list.
+//
+// Copies as many elements of the list as necessary to remove r, but doesn't
+// perform a full copy.
+func (m *Metadata) remove(r *metaElement) {
+	current := &m.head
+	for e := m.head; e != nil; e = e.next {
+		if e == r {
+			// We've found the element we want to remove.
+			*current = e.next
+
+			// No need to copy the tail.
+			return
+		}
+
+		// There is another element in front of the one we want to remove.
+		// We have to copy it to be able to change metaElement.next.
+		cpy := &metaElement{key: e.key, value: e.value}
+		*current = cpy
+		current = &cpy.next
+	}
+}
+
+// Set a key to a value.
+//
+// If value is nil, the key is removed. Avoids modifying old metadata by
+// copying if necessary.
+func (m *Metadata) Set(key, value interface{}) {
+	if e := m.find(key); e != nil {
+		if e.value == value {
+			// Key is present and the value is the same. Nothing to do.
+			return
+		}
+
+		// Key is present with a different value. Create a copy of the list
+		// which doesn't have the element in it.
+		m.remove(e)
+	}
+
+	// m.head is now a linked list that doesn't contain key.
+	if value == nil {
+		return
+	}
+
+	m.head = &metaElement{key: key, value: value, next: m.head}
+}
+
+// Get the value of a key.
+//
+// Returns nil if no value with the given key is present.
+func (m *Metadata) Get(key interface{}) interface{} {
+	if e := m.find(key); e != nil {
+		return e.value
+	}
+	return nil
+}


Test patch:
diff --git a/asm/instruction_test.go b/asm/instruction_test.go
index 70da1f7..ef3a37d 100644
--- a/asm/instruction_test.go
+++ b/asm/instruction_test.go
@@ -180,9 +180,10 @@ func TestInstructionsRewriteMapPtr(t *testing.T) {
 // You can use format flags to change the way an eBPF
 // program is stringified.
 func ExampleInstructions_Format() {
+
 	insns := Instructions{
-		FnMapLookupElem.Call().WithSymbol("my_func"),
-		LoadImm(R0, 42, DWord),
+		FnMapLookupElem.Call().WithSymbol("my_func").WithSource(Comment("bpf_map_lookup_elem()")),
+		LoadImm(R0, 42, DWord).WithSource(Comment("abc = 42")),
 		Return(),
 	}
 
@@ -200,25 +201,33 @@ func ExampleInstructions_Format() {
 
 	// Output: Default format:
 	// my_func:
+	//	 ; bpf_map_lookup_elem()
 	// 	0: Call FnMapLookupElem
+	//	 ; abc = 42
 	// 	1: LdImmDW dst: r0 imm: 42
 	// 	3: Exit
 	//
 	// Don't indent instructions:
 	// my_func:
+	//  ; bpf_map_lookup_elem()
 	// 0: Call FnMapLookupElem
+	//  ; abc = 42
 	// 1: LdImmDW dst: r0 imm: 42
 	// 3: Exit
 	//
 	// Indent using spaces:
 	// my_func:
+	//   ; bpf_map_lookup_elem()
 	//  0: Call FnMapLookupElem
+	//   ; abc = 42
 	//  1: LdImmDW dst: r0 imm: 42
 	//  3: Exit
 	//
 	// Control symbol indentation:
 	// 		my_func:
+	//	 ; bpf_map_lookup_elem()
 	// 	0: Call FnMapLookupElem
+	//	 ; abc = 42
 	// 	1: LdImmDW dst: r0 imm: 42
 	// 	3: Exit
 }
@@ -293,7 +302,6 @@ func TestMetadataCopyOnWrite(t *testing.T) {
 
 	c.Assert(ins.Reference(), qt.Equals, "my_func", qt.Commentf("WithReference updated ins"))
 	c.Assert(ins2.Reference(), qt.Equals, "my_func2", qt.Commentf("WithReference didn't update ins2"))
-	c.Assert(ins.metadata, qt.Not(qt.Equals), ins2.metadata, qt.Commentf("modified metadata should not be equal"))
 
 	// Symbol
 	ins = Ja.Label("").WithSymbol("my_sym")
@@ -301,7 +309,6 @@ func TestMetadataCopyOnWrite(t *testing.T) {
 
 	c.Assert(ins.Symbol(), qt.Equals, "my_sym", qt.Commentf("WithSymbol updated ins"))
 	c.Assert(ins2.Symbol(), qt.Equals, "my_sym2", qt.Commentf("WithSymbol didn't update ins2"))
-	c.Assert(ins.metadata, qt.Not(qt.Equals), ins2.metadata, qt.Commentf("modified metadata should not be equal"))
 
 	// Map
 	ins = LoadMapPtr(R1, 0)
@@ -312,7 +319,6 @@ func TestMetadataCopyOnWrite(t *testing.T) {
 
 	c.Assert(ins.Map(), qt.IsNil, qt.Commentf("AssociateMap updated ins"))
 	c.Assert(ins2.Map(), qt.Equals, testMap, qt.Commentf("AssociateMap didn't update ins2"))
-	c.Assert(ins.metadata, qt.Not(qt.Equals), ins2.metadata, qt.Commentf("modified metadata should not be equal"))
 }
 
 type testFDer int
diff --git a/asm/metadata_test.go b/asm/metadata_test.go
new file mode 100644
index 0000000..2d70a95
--- /dev/null
+++ b/asm/metadata_test.go
@@ -0,0 +1,109 @@
+package asm
+
+import (
+	"testing"
+	"unsafe"
+
+	qt "github.com/frankban/quicktest"
+)
+
+func TestMetadata(t *testing.T) {
+	var m Metadata
+
+	// Metadata should be the size of a pointer.
+	qt.Assert(t, unsafe.Sizeof(m), qt.Equals, unsafe.Sizeof(uintptr(0)))
+
+	// A lookup in a nil meta should return nil.
+	qt.Assert(t, m.Get(bool(false)), qt.IsNil)
+
+	// We can look up anything we inserted.
+	m.Set(bool(false), int(0))
+	m.Set(int(1), int(1))
+	qt.Assert(t, m.Get(bool(false)), qt.Equals, int(0))
+	qt.Assert(t, m.Get(int(1)), qt.Equals, int(1))
+
+	// We have copy on write semantics
+	old := m
+	m.Set(bool(false), int(1))
+	qt.Assert(t, m.Get(bool(false)), qt.Equals, int(1))
+	qt.Assert(t, m.Get(int(1)), qt.Equals, int(1))
+	qt.Assert(t, old.Get(bool(false)), qt.Equals, int(0))
+	qt.Assert(t, old.Get(int(1)), qt.Equals, int(1))
+
+	// Newtypes are handled distinctly.
+	type b bool
+	m.Set(b(false), int(42))
+	qt.Assert(t, m.Get(bool(false)), qt.Equals, int(1))
+	qt.Assert(t, m.Get(int(1)), qt.Equals, int(1))
+	qt.Assert(t, m.Get(b(false)), qt.Equals, int(42))
+
+	// Setting nil removes a key.
+	m.Set(bool(false), nil)
+	qt.Assert(t, m.Get(bool(false)), qt.IsNil)
+	qt.Assert(t, m.Get(int(1)), qt.Equals, int(1))
+	qt.Assert(t, m.Get(b(false)), qt.Equals, int(42))
+}
+
+func BenchmarkMetadata(b *testing.B) {
+	// Assume that three bits of metadata on a single instruction is
+	// our worst case.
+	const worstCaseItems = 3
+
+	type t struct{}
+
+	b.Run("add first", func(b *testing.B) {
+		b.ReportAllocs()
+
+		for i := 0; i < b.N; i++ {
+			var v Metadata
+			v.Set(t{}, 0)
+		}
+	})
+
+	b.Run("add last", func(b *testing.B) {
+		var m Metadata
+		for i := 0; i < worstCaseItems-1; i++ {
+			m.Set(i, i)
+		}
+
+		b.ReportAllocs()
+		b.ResetTimer()
+
+		for i := 0; i < b.N; i++ {
+			v := m
+			v.Set(t{}, 0)
+		}
+	})
+
+	b.Run("add existing", func(b *testing.B) {
+		var m Metadata
+		for i := 0; i < worstCaseItems-1; i++ {
+			m.Set(i, i)
+		}
+		m.Set(t{}, 0)
+
+		b.ReportAllocs()
+		b.ResetTimer()
+
+		for i := 0; i < b.N; i++ {
+			v := m
+			v.Set(t{}, 0)
+		}
+	})
+
+	b.Run("get miss", func(b *testing.B) {
+		var m Metadata
+		for i := 0; i < worstCaseItems; i++ {
+			m.Set(i, i)
+		}
+
+		b.ReportAllocs()
+		b.ResetTimer()
+
+		for i := 0; i < b.N; i++ {
+			if m.Get(t{}) != nil {
+				b.Fatal("got result from miss")
+			}
+		}
+	})
+}
diff --git a/elf_reader_test.go b/elf_reader_test.go
index c1e5bee..acbe13d 100644
--- a/elf_reader_test.go
+++ b/elf_reader_test.go
@@ -222,6 +222,14 @@ func TestLoadCollectionSpec(t *testing.T) {
 	})
 }
 
+func BenchmarkELFLoader(b *testing.B) {
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		_, _ = LoadCollectionSpec("testdata/loader-el.elf")
+	}
+}
+
 func TestDataSections(t *testing.T) {
 	file := fmt.Sprintf("testdata/loader-%s.elf", internal.ClangEndian)
 	coll, err := LoadCollectionSpec(file)