Repository: cilium/ebpf
Pull request #1084 (2023-07-03 10:40:10)

btf: don't copy types during CO-RE relocation
btf: add CO-RE benchmark

    Signed-off-by: Lorenz Bauer <lmb@isovalent.com>

btf: don't copy types during CO-RE relocation

    During CO-RE relocation we need to ignore qualifiers and Typedefs. So far
    we've done this by creating a full copy of each target type with those types
    stripped out.It turns out that this is really expensive especially for large
    types like struct sk_buff.

    Stop copying types during CO-RE relocation and instead use the existing
    UnderlyingType() and a new helper as() to skip when appropriate. As a rule
    of thumb, anytime we do a type assertion during CO-RE relocation we should
    use one of these helpers as appropriate.

    Embarrassingly this leads to a speedup of 99.99% for large types:

        goos: linux
       goarch: amd64
       pkg: github.com/cilium/ebpf/btf
       cpu: 12th Gen Intel(R) Core(TM) i7-1260P
                                   │     base.txt     │               opt.txt   
                │
                                   │      sec/op      │    sec/op     vs base   
                │
       CORESkBuff/byte_off-16         2987010.0n ±  2%   311.9n ±  1%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/byte_sz-16          3016966.0n ±  0%   348.2n ±  1%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/field_exists-16     3036697.5n ±  2%   320.9n ±  2%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/signed-16           3133408.5n ±  3%   211.9n ±  1%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/lshift_u64-16       3129531.5n ±  5%   358.9n ±  4%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/rshift_u64-16       3131090.5n ±  6%   346.9n ±  1%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/local_type_id-16        23.83n ±  2%   23.12n ±  2%    -2.98%
    (p=0.002 n=6)
       CORESkBuff/target_type_id-16   3660381.0n ± 48%   266.7n ±  4%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/type_exists-16      6158062.0n ± 18%   256.6n ±  6%  -100.00%
    (p=0.002 n=6)
       CORESkBuff/type_size-16        4724512.0n ±  6%   282.9n ±  1%   -99.99%
    (p=0.002 n=6)
       CORESkBuff/enumval_exists-16       703.0n ±  7%   271.2n ± 12%   -61.42%
    (p=0.002 n=6)
       CORESkBuff/enumval_value-16        749.0n ±  9%   335.8n ± 18%   -55.16%
    (p=0.002 n=6)
       geomean                            319.3µ         240.5n         -99.92%

    Signed-off-by: Lorenz Bauer <lmb@isovalent.com>

Updates #1081

lmb: FYI @brycekahle 

Patch:
diff --git a/btf/core.go b/btf/core.go
index a638334..21b3a4b 100644
--- a/btf/core.go
+++ b/btf/core.go
@@ -245,12 +245,11 @@ var errIncompatibleTypes = errors.New("incompatible types")
 func coreCalculateFixups(relos []*CORERelocation, targetSpec *Spec, targets []Type, bo binary.ByteOrder) ([]COREFixup, error) {
 	bestScore := len(relos)
 	var bestFixups []COREFixup
-	for i := range targets {
-		targetID, err := targetSpec.TypeID(targets[i])
+	for _, target := range targets {
+		targetID, err := targetSpec.TypeID(target)
 		if err != nil {
 			return nil, fmt.Errorf("target type ID: %w", err)
 		}
-		target := Copy(targets[i], UnderlyingType)
 
 		score := 0 // lower is better
 		fixups := make([]COREFixup, 0, len(relos))
@@ -321,7 +320,7 @@ func coreCalculateFixup(relo *CORERelocation, target Type, targetID TypeID, bo b
 	}
 	zero := COREFixup{}
 
-	local := Copy(relo.typ, UnderlyingType)
+	local := relo.typ
 
 	switch relo.kind {
 	case reloTypeIDTarget, reloTypeSize, reloTypeExists:
@@ -376,12 +375,12 @@ func coreCalculateFixup(relo *CORERelocation, target Type, targetID TypeID, bo b
 		}
 
 	case reloFieldSigned:
-		switch local.(type) {
+		switch l := UnderlyingType(local).(type) {
 		case *Enum:
 			return fixup(1, 1)
 		case *Int:
 			return fixup(
-				uint32(local.(*Int).Encoding&Signed),
+				uint32(l.Encoding&Signed),
 				uint32(target.(*Int).Encoding&Signed),
 			)
 		default:
@@ -389,7 +388,7 @@ func coreCalculateFixup(relo *CORERelocation, target Type, targetID TypeID, bo b
 		}
 
 	case reloFieldByteOffset, reloFieldByteSize, reloFieldExists, reloFieldLShiftU64, reloFieldRShiftU64:
-		if _, ok := target.(*Fwd); ok {
+		if _, ok := as[*Fwd](target); ok {
 			// We can't relocate fields using a forward declaration, so
 			// skip it. If a non-forward declaration is present in the BTF
 			// we'll find it in one of the other iterations.
@@ -519,7 +518,7 @@ func (ca coreAccessor) String() string {
 }
 
 func (ca coreAccessor) enumValue(t Type) (*EnumValue, error) {
-	e, ok := t.(*Enum)
+	e, ok := as[*Enum](t)
 	if !ok {
 		return nil, fmt.Errorf("not an enum: %s", t)
 	}
@@ -634,7 +633,7 @@ func coreFindField(localT Type, localAcc coreAccessor, targetT Type) (coreField,
 
 	var localMaybeFlex, targetMaybeFlex bool
 	for i, acc := range localAcc[1:] {
-		switch localType := local.Type.(type) {
+		switch localType := UnderlyingType(local.Type).(type) {
 		case composite:
 			// For composite types acc is used to find the field in the local type,
 			// and then we try to find a field in target with the same name.
@@ -645,21 +644,21 @@ func coreFindField(localT Type, localAcc coreAccessor, targetT Type) (coreField,
 
 			localMember := localMembers[acc]
 			if localMember.Name == "" {
-				_, ok := localMember.Type.(composite)
+				localMemberType, ok := as[composite](localMember.Type)
 				if !ok {
 					return coreField{}, coreField{}, fmt.Errorf("unnamed field with type %s: %s", localMember.Type, ErrNotSupported)
 				}
 
 				// This is an anonymous struct or union, ignore it.
 				local = coreField{
-					Type:   localMember.Type,
+					Type:   localMemberType,
 					offset: local.offset + localMember.Offset.Bytes(),
 				}
 				localMaybeFlex = false
 				continue
 			}
 
-			targetType, ok := target.Type.(composite)
+			targetType, ok := as[composite](target.Type)
 			if !ok {
 				return coreField{}, coreField{}, fmt.Errorf("target not composite: %w", errImpossibleRelocation)
 			}
@@ -705,7 +704,7 @@ func coreFindField(localT Type, localAcc coreAccessor, targetT Type) (coreField,
 
 		case *Array:
 			// For arrays, acc is the index in the target.
-			targetType, ok := target.Type.(*Array)
+			targetType, ok := as[*Array](target.Type)
 			if !ok {
 				return coreField{}, coreField{}, fmt.Errorf("target not array: %w", errImpossibleRelocation)
 			}
@@ -799,7 +798,7 @@ func coreFindMember(typ composite, name string) (Member, bool, error) {
 				continue
 			}
 
-			comp, ok := member.Type.(composite)
+			comp, ok := as[composite](member.Type)
 			if !ok {
 				return Member{}, false, fmt.Errorf("anonymous non-composite type %T not allowed", member.Type)
 			}
@@ -818,7 +817,7 @@ func coreFindEnumValue(local Type, localAcc coreAccessor, target Type) (localVal
 		return nil, nil, err
 	}
 
-	targetEnum, ok := target.(*Enum)
+	targetEnum, ok := as[*Enum](target)
 	if !ok {
 		return nil, nil, errImpossibleRelocation
 	}
@@ -839,10 +838,7 @@ func coreFindEnumValue(local Type, localAcc coreAccessor, target Type) (localVal
 //
 // Only layout compatibility is checked, ignoring names of the root type.
 func CheckTypeCompatibility(localType Type, targetType Type) error {
-	l := Copy(localType, UnderlyingType)
-	t := Copy(targetType, UnderlyingType)
-
-	return coreAreTypesCompatible(l, t)
+	return coreAreTypesCompatible(localType, targetType)
 }
 
 /* The comment below is from bpf_core_types_are_compat in libbpf.c:
@@ -881,8 +877,8 @@ func coreAreTypesCompatible(localType Type, targetType Type) error {
 			return errors.New("types are nested too deep")
 		}
 
-		localType = *l
-		targetType = *t
+		localType = UnderlyingType(*l)
+		targetType = UnderlyingType(*t)
 
 		if reflect.TypeOf(localType) != reflect.TypeOf(targetType) {
 			return fmt.Errorf("type mismatch: %w", errIncompatibleTypes)
@@ -949,6 +945,9 @@ func coreAreTypesCompatible(localType Type, targetType Type) error {
  * Returns errImpossibleRelocation if the members are not compatible.
  */
 func coreAreMembersCompatible(localType Type, targetType Type) error {
+	localType = UnderlyingType(localType)
+	targetType = UnderlyingType(targetType)
+
 	doNamesMatch := func(a, b string) error {
 		if a == "" || b == "" {
 			// allow anonymous and named type to match
diff --git a/btf/types.go b/btf/types.go
index 38cc76a..dd34e89 100644
--- a/btf/types.go
+++ b/btf/types.go
@@ -218,6 +218,7 @@ func copyMembers(orig []Member) []Member {
 }
 
 type composite interface {
+	Type
 	members() []Member
 }
 
@@ -1145,6 +1146,29 @@ func UnderlyingType(typ Type) Type {
 	return &cycle{typ}
 }
 
+// as returns typ if is of type T. Otherwise it peels qualifiers and Typedefs
+// until it finds a T.
+//
+// Returns the zero value and false if there is no T or if the type is nested
+// too deeply.
+func as[T Type](typ Type) (T, bool) {
+	for depth := 0; depth <= maxTypeDepth; depth++ {
+		switch v := (typ).(type) {
+		case T:
+			return v, true
+		case qualifier:
+			typ = v.qualify()
+		case *Typedef:
+			typ = v.Type
+		default:
+			goto notFound
+		}
+	}
+notFound:
+	var zero T
+	return zero, false
+}
+
 type formatState struct {
 	fmt.State
 	depth int


Test patch:
diff --git a/btf/core_test.go b/btf/core_test.go
index 6cf07f7..8cb36fc 100644
--- a/btf/core_test.go
+++ b/btf/core_test.go
@@ -659,3 +659,47 @@ func TestCORECopyWithoutQualifiers(t *testing.T) {
 		qt.Assert(t, got, qt.DeepEquals, root)
 	})
 }
+
+func BenchmarkCORESkBuff(b *testing.B) {
+	spec := vmlinuxTestdataSpec(b)
+
+	var skb *Struct
+	err := spec.TypeByName("sk_buff", &skb)
+	qt.Assert(b, err, qt.IsNil)
+
+	skbID, err := spec.TypeID(skb)
+	qt.Assert(b, err, qt.IsNil)
+
+	var pktHashTypes *Enum
+	err = spec.TypeByName("pkt_hash_types", &pktHashTypes)
+	qt.Assert(b, err, qt.IsNil)
+
+	pktHashTypesID, err := spec.TypeID(pktHashTypes)
+	qt.Assert(b, err, qt.IsNil)
+
+	for _, relo := range []*CORERelocation{
+		{skb, coreAccessor{0, 0}, reloFieldByteOffset, skbID},
+		{skb, coreAccessor{0, 0}, reloFieldByteSize, skbID},
+		{skb, coreAccessor{0, 0}, reloFieldExists, skbID},
+		{skb, coreAccessor{0, 0}, reloFieldSigned, skbID},
+		{skb, coreAccessor{0, 0}, reloFieldLShiftU64, skbID},
+		{skb, coreAccessor{0, 0}, reloFieldRShiftU64, skbID},
+		{skb, coreAccessor{0}, reloTypeIDLocal, skbID},
+		{skb, coreAccessor{0}, reloTypeIDTarget, skbID},
+		{skb, coreAccessor{0}, reloTypeExists, skbID},
+		{skb, coreAccessor{0}, reloTypeSize, skbID},
+		{pktHashTypes, coreAccessor{0}, reloEnumvalExists, pktHashTypesID},
+		{pktHashTypes, coreAccessor{0}, reloEnumvalValue, pktHashTypesID},
+	} {
+		b.Run(relo.kind.String(), func(b *testing.B) {
+			b.ReportAllocs()
+
+			for i := 0; i < b.N; i++ {
+				_, err = CORERelocate([]*CORERelocation{relo}, spec, spec.byteOrder)
+				if err != nil {
+					b.Fatal(err)
+				}
+			}
+		})
+	}
+}
diff --git a/btf/types_test.go b/btf/types_test.go
index ce3bd5c..60a4194 100644
--- a/btf/types_test.go
+++ b/btf/types_test.go
@@ -91,6 +91,41 @@ func TestCopy(t *testing.T) {
 	})
 }
 
+func TestAs(t *testing.T) {
+	i := &Int{}
+	ptr := &Pointer{i}
+	td := &Typedef{Type: ptr}
+	cst := &Const{td}
+	vol := &Volatile{cst}
+
+	// It's possible to retrieve qualifiers and Typedefs.
+	haveVol, ok := as[*Volatile](vol)
+	qt.Assert(t, ok, qt.IsTrue)
+	qt.Assert(t, haveVol, qt.Equals, vol)
+
+	haveTd, ok := as[*Typedef](vol)
+	qt.Assert(t, ok, qt.IsTrue)
+	qt.Assert(t, haveTd, qt.Equals, td)
+
+	haveCst, ok := as[*Const](vol)
+	qt.Assert(t, ok, qt.IsTrue)
+	qt.Assert(t, haveCst, qt.Equals, cst)
+
+	// Make sure we don't skip Pointer.
+	haveI, ok := as[*Int](vol)
+	qt.Assert(t, ok, qt.IsFalse)
+	qt.Assert(t, haveI, qt.IsNil)
+
+	// Make sure we can always retrieve Pointer.
+	for _, typ := range []Type{
+		td, cst, vol, ptr,
+	} {
+		have, ok := as[*Pointer](typ)
+		qt.Assert(t, ok, qt.IsTrue)
+		qt.Assert(t, have, qt.Equals, ptr)
+	}
+}
+
 func BenchmarkCopy(b *testing.B) {
 	typ := newCyclicalType(10)
 
diff --git a/internal/testutils/seed.go b/internal/testutils/seed.go
index 2c6e706..5892e0e 100644
--- a/internal/testutils/seed.go
+++ b/internal/testutils/seed.go
@@ -15,7 +15,7 @@ var randSeed struct {
 func Rand() *rand.Rand {
 	randSeed.once.Do(func() {
 		randSeed.value = time.Now().UnixMicro()
-		fmt.Printf("Rand is %d", randSeed.value)
+		fmt.Printf("Random seed is %d\n", randSeed.value)
 	})
 	return rand.New(rand.NewSource(randSeed.value))
 }