1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
package btf
import (
"fmt"
"testing"
"github.com/go-quicktest/qt"
)
func TestPostorderTraversal(t *testing.T) {
ptr := newCyclicalType(2).(*Pointer)
cst := ptr.Target.(*Const)
str := cst.Type.(*Struct)
t.Logf("%3v", ptr)
pending := []Type{str, cst, ptr}
visitInPostorder(ptr, nil, func(typ Type) bool {
qt.Assert(t, qt.Equals(typ, pending[0]))
pending = pending[1:]
return true
})
qt.Assert(t, qt.HasLen(pending, 0))
i := &Int{Name: "foo"}
// i appears twice at the same nesting depth.
arr := &Array{Index: i, Type: i}
seen := make(map[Type]bool)
visitInPostorder(arr, nil, func(typ Type) bool {
qt.Assert(t, qt.IsFalse(seen[typ]))
seen[typ] = true
return true
})
qt.Assert(t, qt.IsTrue(seen[arr]))
qt.Assert(t, qt.IsTrue(seen[i]))
}
func TestPostorderTraversalVmlinux(t *testing.T) {
spec := vmlinuxTestdataSpec(t)
typ, err := spec.AnyTypeByName("gov_update_cpu_data")
if err != nil {
t.Fatal(err)
}
for _, typ := range []Type{typ} {
t.Run(fmt.Sprintf("%s", typ), func(t *testing.T) {
seen := make(map[Type]bool)
var last Type
visitInPostorder(typ, nil, func(typ Type) bool {
if seen[typ] {
t.Fatalf("%s visited twice", typ)
}
seen[typ] = true
last = typ
return true
})
if last != typ {
t.Fatalf("Expected %s got %s as last type", typ, last)
}
children(typ, func(child *Type) bool {
qt.Check(t, qt.IsTrue(seen[*child]), qt.Commentf("missing child %s", *child))
return true
})
})
}
}
func BenchmarkPostorderTraversal(b *testing.B) {
spec := vmlinuxTestdataSpec(b)
var fn *Func
err := spec.TypeByName("gov_update_cpu_data", &fn)
if err != nil {
b.Fatal(err)
}
for _, test := range []struct {
name string
typ Type
}{
{"single type", &Int{}},
{"cycle(1)", newCyclicalType(1)},
{"cycle(10)", newCyclicalType(10)},
{"gov_update_cpu_data", fn},
} {
b.Logf("%10v", test.typ)
b.Run(test.name, func(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
visitInPostorder(test.typ, nil, func(t Type) bool { return true })
}
})
}
}
|
