Repository: cilium/ebpf
Pull request #177 (2020-11-25 17:17:57)

CO-RE: add type / field compatibility logic
btf: port CO-RE relocation compatibility logic
    
    coreAreTypesCompatible will be used to figure out if a particular target
    (aka kernel) type can be substituted for a local type. coreAreMembersCompatible
    will be used to figure out if we can relocate a load from a local type with
    a load from a target type.
    
    This code is based on Bryce Kahle's CO-RE work and derived from libbpf
    under a BSD 2-Clause license.
    
Updates #114

btf: use a deque instead of a stack
    
    For some of the CO-RE algorithms it's useful to get the first *Type
    from the stack, rather than the last one. Implement a deque based on
    a resizing ring buffer and use it instead of copyStack.


Patch:
diff --git a/internal/btf/core.go b/internal/btf/core.go
new file mode 100644
index 0000000..ed7b7c0
--- /dev/null
+++ b/internal/btf/core.go
@@ -0,0 +1,178 @@
+package btf
+
+import (
+	"errors"
+	"fmt"
+	"reflect"
+)
+
+// Code in this file is derived from libbpf, which is available under a BSD
+// 2-Clause license.
+
+/* The comment below is from bpf_core_types_are_compat in libbpf.c:
+ *
+ * Check local and target types for compatibility. This check is used for
+ * type-based CO-RE relocations and follow slightly different rules than
+ * field-based relocations. This function assumes that root types were already
+ * checked for name match. Beyond that initial root-level name check, names
+ * are completely ignored. Compatibility rules are as follows:
+ *   - any two STRUCTs/UNIONs/FWDs/ENUMs/INTs are considered compatible, but
+ *     kind should match for local and target types (i.e., STRUCT is not
+ *     compatible with UNION);
+ *   - for ENUMs, the size is ignored;
+ *   - for INT, size and signedness are ignored;
+ *   - for ARRAY, dimensionality is ignored, element types are checked for
+ *     compatibility recursively;
+ *   - CONST/VOLATILE/RESTRICT modifiers are ignored;
+ *   - TYPEDEFs/PTRs are compatible if types they pointing to are compatible;
+ *   - FUNC_PROTOs are compatible if they have compatible signature: same
+ *     number of input args and compatible return and argument types.
+ * These rules are not set in stone and probably will be adjusted as we get
+ * more experience with using BPF CO-RE relocations.
+ */
+func coreAreTypesCompatible(localType Type, targetType Type) (bool, error) {
+	var (
+		localTs, targetTs typeDeque
+		l, t              = &localType, &targetType
+		depth             = 0
+	)
+
+	for ; l != nil && t != nil; l, t = localTs.shift(), targetTs.shift() {
+		if depth >= maxTypeDepth {
+			return false, errors.New("types are nested too deep")
+		}
+
+		localType = skipQualifierAndTypedef(*l)
+		targetType = skipQualifierAndTypedef(*t)
+
+		if reflect.TypeOf(localType) != reflect.TypeOf(targetType) {
+			return false, nil
+		}
+
+		switch lv := (localType).(type) {
+		case *Void, *Struct, *Union, *Enum, *Fwd:
+			// Nothing to do here
+
+		case *Int:
+			tv := targetType.(*Int)
+			if lv.isBitfield() || tv.isBitfield() {
+				return false, nil
+			}
+
+		case *Pointer, *Array:
+			depth++
+			localType.walk(&localTs)
+			targetType.walk(&targetTs)
+
+		case *FuncProto:
+			tv := targetType.(*FuncProto)
+			if len(lv.Params) != len(tv.Params) {
+				return false, nil
+			}
+
+			depth++
+			localType.walk(&localTs)
+			targetType.walk(&targetTs)
+
+		default:
+			return false, fmt.Errorf("unsupported type %T", localType)
+		}
+	}
+
+	if l != nil {
+		return false, fmt.Errorf("dangling local type %T", *l)
+	}
+
+	if t != nil {
+		return false, fmt.Errorf("dangling target type %T", *t)
+	}
+
+	return true, nil
+}
+
+/* The comment below is from bpf_core_fields_are_compat in libbpf.c:
+ *
+ * Check two types for compatibility for the purpose of field access
+ * relocation. const/volatile/restrict and typedefs are skipped to ensure we
+ * are relocating semantically compatible entities:
+ *   - any two STRUCTs/UNIONs are compatible and can be mixed;
+ *   - any two FWDs are compatible, if their names match (modulo flavor suffix);
+ *   - any two PTRs are always compatible;
+ *   - for ENUMs, names should be the same (ignoring flavor suffix) or at
+ *     least one of enums should be anonymous;
+ *   - for ENUMs, check sizes, names are ignored;
+ *   - for INT, size and signedness are ignored;
+ *   - for ARRAY, dimensionality is ignored, element types are checked for
+ *     compatibility recursively;
+ *   - everything else shouldn't be ever a target of relocation.
+ * These rules are not set in stone and probably will be adjusted as we get
+ * more experience with using BPF CO-RE relocations.
+ */
+func coreAreMembersCompatible(localType Type, targetType Type) (bool, error) {
+	doNamesMatch := func(a, b string) bool {
+		if a == "" || b == "" {
+			// allow anonymous and named type to match
+			return true
+		}
+
+		return essentialName(a) == essentialName(b)
+	}
+
+	for depth := 0; depth <= maxTypeDepth; depth++ {
+		localType = skipQualifierAndTypedef(localType)
+		targetType = skipQualifierAndTypedef(targetType)
+
+		_, lok := localType.(composite)
+		_, tok := targetType.(composite)
+		if lok && tok {
+			return true, nil
+		}
+
+		if reflect.TypeOf(localType) != reflect.TypeOf(targetType) {
+			return false, nil
+		}
+
+		switch lv := localType.(type) {
+		case *Pointer:
+			return true, nil
+
+		case *Enum:
+			tv := targetType.(*Enum)
+			return doNamesMatch(lv.name(), tv.name()), nil
+
+		case *Fwd:
+			tv := targetType.(*Fwd)
+			return doNamesMatch(lv.name(), tv.name()), nil
+
+		case *Int:
+			tv := targetType.(*Int)
+			return !lv.isBitfield() && !tv.isBitfield(), nil
+
+		case *Array:
+			tv := targetType.(*Array)
+
+			localType = lv.Type
+			targetType = tv.Type
+
+		default:
+			return false, fmt.Errorf("unsupported type %T", localType)
+		}
+	}
+
+	return false, errors.New("types are nested too deep")
+}
+
+func skipQualifierAndTypedef(typ Type) Type {
+	result := typ
+	for depth := 0; depth <= maxTypeDepth; depth++ {
+		switch v := (result).(type) {
+		case qualifier:
+			result = v.qualify()
+		case *Typedef:
+			result = v.Type
+		default:
+			return result
+		}
+	}
+	return typ
+}
diff --git a/internal/btf/types.go b/internal/btf/types.go
index 9c75367..840424e 100644
--- a/internal/btf/types.go
+++ b/internal/btf/types.go
@@ -28,7 +28,7 @@ type Type interface {
 
 	// Enumerate all nested Types. Repeated calls must visit nested
 	// types in the same order.
-	walk(*copyStack)
+	walk(*typeDeque)
 }
 
 // namedType is a type with a name.
@@ -55,7 +55,7 @@ func (v *Void) ID() TypeID      { return 0 }
 func (v *Void) String() string  { return "void#0" }
 func (v *Void) size() uint32    { return 0 }
 func (v *Void) copy() Type      { return (*Void)(nil) }
-func (v *Void) walk(*copyStack) {}
+func (v *Void) walk(*typeDeque) {}
 
 type IntEncoding byte
 
@@ -107,12 +107,16 @@ func (i *Int) String() string {
 }
 
 func (i *Int) size() uint32    { return i.Size }
-func (i *Int) walk(*copyStack) {}
+func (i *Int) walk(*typeDeque) {}
 func (i *Int) copy() Type {
 	cpy := *i
 	return &cpy
 }
 
+func (i *Int) isBitfield() bool {
+	return i.Offset > 0
+}
+
 // Pointer is a pointer to another type.
 type Pointer struct {
 	TypeID
@@ -123,8 +127,8 @@ func (p *Pointer) String() string {
 	return fmt.Sprintf("pointer#%d[target=#%d]", p.TypeID, p.Target.ID())
 }
 
-func (p *Pointer) size() uint32       { return 8 }
-func (p *Pointer) walk(cs *copyStack) { cs.push(&p.Target) }
+func (p *Pointer) size() uint32        { return 8 }
+func (p *Pointer) walk(tdq *typeDeque) { tdq.push(&p.Target) }
 func (p *Pointer) copy() Type {
 	cpy := *p
 	return &cpy
@@ -141,7 +145,7 @@ func (arr *Array) String() string {
 	return fmt.Sprintf("array#%d[type=#%d n=%d]", arr.TypeID, arr.Type.ID(), arr.Nelems)
 }
 
-func (arr *Array) walk(cs *copyStack) { cs.push(&arr.Type) }
+func (arr *Array) walk(tdq *typeDeque) { tdq.push(&arr.Type) }
 func (arr *Array) copy() Type {
 	cpy := *arr
 	return &cpy
@@ -162,9 +166,9 @@ func (s *Struct) String() string {
 
 func (s *Struct) size() uint32 { return s.Size }
 
-func (s *Struct) walk(cs *copyStack) {
+func (s *Struct) walk(tdq *typeDeque) {
 	for i := range s.Members {
-		cs.push(&s.Members[i].Type)
+		tdq.push(&s.Members[i].Type)
 	}
 }
 
@@ -194,9 +198,9 @@ func (u *Union) String() string {
 
 func (u *Union) size() uint32 { return u.Size }
 
-func (u *Union) walk(cs *copyStack) {
+func (u *Union) walk(tdq *typeDeque) {
 	for i := range u.Members {
-		cs.push(&u.Members[i].Type)
+		tdq.push(&u.Members[i].Type)
 	}
 }
 
@@ -251,7 +255,7 @@ type EnumValue struct {
 }
 
 func (e *Enum) size() uint32    { return 4 }
-func (e *Enum) walk(*copyStack) {}
+func (e *Enum) walk(*typeDeque) {}
 func (e *Enum) copy() Type {
 	cpy := *e
 	cpy.Values = make([]EnumValue, len(e.Values))
@@ -290,7 +294,7 @@ func (f *Fwd) String() string {
 	return fmt.Sprintf("fwd#%d[%s %q]", f.TypeID, f.Kind, f.Name)
 }
 
-func (f *Fwd) walk(*copyStack) {}
+func (f *Fwd) walk(*typeDeque) {}
 func (f *Fwd) copy() Type {
 	cpy := *f
 	return &cpy
@@ -307,7 +311,7 @@ func (td *Typedef) String() string {
 	return fmt.Sprintf("typedef#%d[%q #%d]", td.TypeID, td.Name, td.Type.ID())
 }
 
-func (td *Typedef) walk(cs *copyStack) { cs.push(&td.Type) }
+func (td *Typedef) walk(tdq *typeDeque) { tdq.push(&td.Type) }
 func (td *Typedef) copy() Type {
 	cpy := *td
 	return &cpy
@@ -323,8 +327,8 @@ func (v *Volatile) String() string {
 	return fmt.Sprintf("volatile#%d[#%d]", v.TypeID, v.Type.ID())
 }
 
-func (v *Volatile) qualify() Type      { return v.Type }
-func (v *Volatile) walk(cs *copyStack) { cs.push(&v.Type) }
+func (v *Volatile) qualify() Type       { return v.Type }
+func (v *Volatile) walk(tdq *typeDeque) { tdq.push(&v.Type) }
 func (v *Volatile) copy() Type {
 	cpy := *v
 	return &cpy
@@ -340,8 +344,8 @@ func (c *Const) String() string {
 	return fmt.Sprintf("const#%d[#%d]", c.TypeID, c.Type.ID())
 }
 
-func (c *Const) qualify() Type      { return c.Type }
-func (c *Const) walk(cs *copyStack) { cs.push(&c.Type) }
+func (c *Const) qualify() Type       { return c.Type }
+func (c *Const) walk(tdq *typeDeque) { tdq.push(&c.Type) }
 func (c *Const) copy() Type {
 	cpy := *c
 	return &cpy
@@ -357,8 +361,8 @@ func (r *Restrict) String() string {
 	return fmt.Sprintf("restrict#%d[#%d]", r.TypeID, r.Type.ID())
 }
 
-func (r *Restrict) qualify() Type      { return r.Type }
-func (r *Restrict) walk(cs *copyStack) { cs.push(&r.Type) }
+func (r *Restrict) qualify() Type       { return r.Type }
+func (r *Restrict) walk(tdq *typeDeque) { tdq.push(&r.Type) }
 func (r *Restrict) copy() Type {
 	cpy := *r
 	return &cpy
@@ -375,7 +379,7 @@ func (f *Func) String() string {
 	return fmt.Sprintf("func#%d[%q proto=#%d]", f.TypeID, f.Name, f.Type.ID())
 }
 
-func (f *Func) walk(cs *copyStack) { cs.push(&f.Type) }
+func (f *Func) walk(tdq *typeDeque) { tdq.push(&f.Type) }
 func (f *Func) copy() Type {
 	cpy := *f
 	return &cpy
@@ -398,10 +402,10 @@ func (fp *FuncProto) String() string {
 	return s.String()
 }
 
-func (fp *FuncProto) walk(cs *copyStack) {
-	cs.push(&fp.Return)
+func (fp *FuncProto) walk(tdq *typeDeque) {
+	tdq.push(&fp.Return)
 	for i := range fp.Params {
-		cs.push(&fp.Params[i].Type)
+		tdq.push(&fp.Params[i].Type)
 	}
 }
 
@@ -429,7 +433,7 @@ func (v *Var) String() string {
 	return fmt.Sprintf("var#%d[%q]", v.TypeID, v.Name)
 }
 
-func (v *Var) walk(cs *copyStack) { cs.push(&v.Type) }
+func (v *Var) walk(tdq *typeDeque) { tdq.push(&v.Type) }
 func (v *Var) copy() Type {
 	cpy := *v
 	return &cpy
@@ -449,9 +453,9 @@ func (ds *Datasec) String() string {
 
 func (ds *Datasec) size() uint32 { return ds.Size }
 
-func (ds *Datasec) walk(cs *copyStack) {
+func (ds *Datasec) walk(tdq *typeDeque) {
 	for i := range ds.Vars {
-		cs.push(&ds.Vars[i].Type)
+		tdq.push(&ds.Vars[i].Type)
 	}
 }
 
@@ -552,7 +556,7 @@ func Sizeof(typ Type) (int, error) {
 func copyType(typ Type) Type {
 	var (
 		copies = make(map[Type]Type)
-		work   copyStack
+		work   typeDeque
 	)
 
 	for t := &typ; t != nil; t = work.pop() {
@@ -573,27 +577,76 @@ func copyType(typ Type) Type {
 	return typ
 }
 
-// copyStack keeps track of pointers to types which still
+// typeDeque keeps track of pointers to types which still
 // need to be visited.
-type copyStack []*Type
+type typeDeque struct {
+	types       []*Type
+	read, write uint64
+	mask        uint64
+}
 
 // push adds a type to the stack.
-func (cs *copyStack) push(t *Type) {
-	*cs = append(*cs, t)
+func (dq *typeDeque) push(t *Type) {
+	if dq.write-dq.read < uint64(len(dq.types)) {
+		dq.types[dq.write&dq.mask] = t
+		dq.write++
+		return
+	}
+
+	new := len(dq.types) * 2
+	if new == 0 {
+		new = 8
+	}
+
+	types := make([]*Type, new)
+	pivot := dq.read & dq.mask
+	n := copy(types, dq.types[pivot:])
+	n += copy(types[n:], dq.types[:pivot])
+	types[n] = t
+
+	dq.types = types
+	dq.mask = uint64(new) - 1
+	dq.read, dq.write = 0, uint64(n+1)
+}
+
+// shift returns the first element or null.
+func (dq *typeDeque) shift() *Type {
+	if dq.read == dq.write {
+		return nil
+	}
+
+	index := dq.read & dq.mask
+	t := dq.types[index]
+	dq.types[index] = nil
+	dq.read++
+	return t
 }
 
-// pop returns the topmost Type, or nil.
-func (cs *copyStack) pop() *Type {
-	n := len(*cs)
-	if n == 0 {
+// pop returns the last element or null.
+func (dq *typeDeque) pop() *Type {
+	if dq.read == dq.write {
 		return nil
 	}
 
-	t := (*cs)[n-1]
-	*cs = (*cs)[:n-1]
+	dq.write--
+	index := dq.write & dq.mask
+	t := dq.types[index]
+	dq.types[index] = nil
 	return t
 }
 
+// all returns all elements.
+//
+// The deque is empty after calling this method.
+func (dq *typeDeque) all() []*Type {
+	length := dq.write - dq.read
+	types := make([]*Type, 0, length)
+	for t := dq.shift(); t != nil; t = dq.shift() {
+		types = append(types, t)
+	}
+	return types
+}
+
 // inflateRawTypes takes a list of raw btf types linked via type IDs, and turns
 // it into a graph of Types connected via pointers.
 //


Test patch:
diff --git a/internal/btf/core_test.go b/internal/btf/core_test.go
new file mode 100644
index 0000000..69213ae
--- /dev/null
+++ b/internal/btf/core_test.go
@@ -0,0 +1,144 @@
+package btf
+
+import "testing"
+
+func TestCoreAreTypesCompatible(t *testing.T) {
+	tests := []struct {
+		a, b       Type
+		compatible bool
+	}{
+		{&Void{}, &Void{}, true},
+		{&Struct{Name: "a"}, &Struct{Name: "b"}, true},
+		{&Union{Name: "a"}, &Union{Name: "b"}, true},
+		{&Union{Name: "a"}, &Struct{Name: "b"}, false},
+		{&Enum{Name: "a"}, &Enum{Name: "b"}, true},
+		{&Fwd{Name: "a"}, &Fwd{Name: "b"}, true},
+		{&Int{Name: "a", Size: 2}, &Int{Name: "b", Size: 4}, true},
+		{&Int{Offset: 1}, &Int{}, false},
+		{&Pointer{Target: &Void{}}, &Pointer{Target: &Void{}}, true},
+		{&Pointer{Target: &Void{}}, &Void{}, false},
+		{&Array{Type: &Void{}}, &Array{Type: &Void{}}, true},
+		{&Array{Type: &Int{}}, &Array{Type: &Void{}}, false},
+		{&FuncProto{Return: &Int{}}, &FuncProto{Return: &Void{}}, false},
+		{
+			&FuncProto{Return: &Void{}, Params: []FuncParam{{Name: "a", Type: &Void{}}}},
+			&FuncProto{Return: &Void{}, Params: []FuncParam{{Name: "b", Type: &Void{}}}},
+			true,
+		},
+		{
+			&FuncProto{Return: &Void{}, Params: []FuncParam{{Type: &Void{}}}},
+			&FuncProto{Return: &Void{}, Params: []FuncParam{{Type: &Int{}}}},
+			false,
+		},
+		{
+			&FuncProto{Return: &Void{}, Params: []FuncParam{{Type: &Void{}}, {Type: &Void{}}}},
+			&FuncProto{Return: &Void{}, Params: []FuncParam{{Type: &Void{}}}},
+			false,
+		},
+		{&Typedef{Name: "a", Type: &Void{}}, &Void{}, true},
+		{&Typedef{Name: "a", Type: &Void{}}, &Int{}, false},
+		{&Const{Type: &Void{}}, &Void{}, true},
+		{&Const{Type: &Void{}}, &Int{}, false},
+		{&Volatile{Type: &Void{}}, &Void{}, true},
+		{&Volatile{Type: &Void{}}, &Int{}, false},
+		{&Restrict{Type: &Void{}}, &Void{}, true},
+		{&Restrict{Type: &Void{}}, &Int{}, false},
+	}
+
+	for _, test := range tests {
+		compatible, err := coreAreTypesCompatible(test.a, test.b)
+		if err != nil {
+			t.Errorf("Can't compare types: %s\na = %#v\nb = %#v", err, test.a, test.b)
+			continue
+		}
+
+		if compatible != test.compatible {
+			if test.compatible {
+				t.Errorf("Expected types to be compatible:\na = %#v\nb = %#v", test.a, test.b)
+			} else {
+				t.Errorf("Expected types to be incompatible:\na = %#v\nb = %#v", test.a, test.b)
+			}
+			continue
+		}
+
+		compatibleReverse, err := coreAreTypesCompatible(test.b, test.a)
+		if err != nil {
+			t.Errorf("Can't compare reversed types: %s\na = %#v\nb = %#v", err, test.a, test.b)
+			continue
+		}
+		if compatibleReverse != compatible {
+			t.Errorf("Expected the reverse comparison to be %v as well:\na = %#v\nb = %#v", compatible, test.a, test.b)
+		}
+	}
+
+	for _, invalid := range []Type{&Var{}, &Datasec{}} {
+		_, err := coreAreTypesCompatible(invalid, invalid)
+		if err == nil {
+			t.Errorf("Expected an error for %T", invalid)
+		}
+	}
+}
+
+func TestCoreAreMembersCompatible(t *testing.T) {
+	tests := []struct {
+		a, b       Type
+		compatible bool
+	}{
+		{&Struct{Name: "a"}, &Struct{Name: "b"}, true},
+		{&Union{Name: "a"}, &Union{Name: "b"}, true},
+		{&Union{Name: "a"}, &Struct{Name: "b"}, true},
+		{&Enum{Name: "a"}, &Enum{Name: "b"}, false},
+		{&Enum{Name: "a"}, &Enum{Name: "a___foo"}, true},
+		{&Enum{Name: "a"}, &Enum{Name: ""}, true},
+		{&Fwd{Name: "a"}, &Fwd{Name: "b"}, false},
+		{&Fwd{Name: "a"}, &Fwd{Name: "a___foo"}, true},
+		{&Fwd{Name: "a"}, &Fwd{Name: ""}, true},
+		{&Int{Name: "a", Size: 2}, &Int{Name: "b", Size: 4}, true},
+		{&Int{Offset: 1}, &Int{}, false},
+		{&Pointer{Target: &Void{}}, &Pointer{Target: &Void{}}, true},
+		{&Pointer{Target: &Void{}}, &Void{}, false},
+		{&Array{Type: &Int{}}, &Array{Type: &Int{}}, true},
+		{&Array{Type: &Int{}}, &Array{Type: &Void{}}, false},
+		{&Typedef{Name: "a", Type: &Int{}}, &Int{}, true},
+		{&Typedef{Name: "a", Type: &Int{}}, &Void{}, false},
+		{&Const{Type: &Int{}}, &Int{}, true},
+		{&Const{Type: &Int{}}, &Void{}, false},
+		{&Volatile{Type: &Int{}}, &Int{}, true},
+		{&Volatile{Type: &Int{}}, &Void{}, false},
+		{&Restrict{Type: &Int{}}, &Int{}, true},
+		{&Restrict{Type: &Int{}}, &Void{}, false},
+	}
+
+	for _, test := range tests {
+		compatible, err := coreAreMembersCompatible(test.a, test.b)
+		if err != nil {
+			t.Errorf("Can't compare types: %s\na = %#v\nb = %#v", err, test.a, test.b)
+			continue
+		}
+
+		if compatible != test.compatible {
+			if test.compatible {
+				t.Errorf("Expected types to be compatible:\na = %#v\nb = %#v", test.a, test.b)
+			} else {
+				t.Errorf("Expected types to be incompatible:\na = %#v\nb = %#v", test.a, test.b)
+			}
+			continue
+		}
+
+		compatibleReverse, err := coreAreMembersCompatible(test.b, test.a)
+		if err != nil {
+			t.Errorf("Can't compare reversed types: %s\na = %#v\nb = %#v", err, test.a, test.b)
+			continue
+		}
+		if compatibleReverse != compatible {
+			t.Errorf("Expected the reverse comparison to be %v as well:\na = %#v\nb = %#v", compatible, test.a, test.b)
+		}
+	}
+
+	for _, invalid := range []Type{&Void{}, &FuncProto{}, &Var{}, &Datasec{}} {
+		_, err := coreAreMembersCompatible(invalid, invalid)
+		if err == nil {
+			t.Errorf("Expected an error for %T", invalid)
+		}
+	}
+}
diff --git a/internal/btf/types_test.go b/internal/btf/types_test.go
index 08e8d43..d38164c 100644
--- a/internal/btf/types_test.go
+++ b/internal/btf/types_test.go
@@ -124,17 +124,93 @@ func TestType(t *testing.T) {
 				t.Error("Copy doesn't copy")
 			}
 
-			var first, second copyStack
+			var first, second typeDeque
 			typ.walk(&first)
 			typ.walk(&second)
 
-			if diff := cmp.Diff(first, second, compareTypes); diff != "" {
+			if diff := cmp.Diff(first.all(), second.all(), compareTypes); diff != "" {
 				t.Errorf("Walk mismatch (-want +got):\n%s", diff)
 			}
 		})
 	}
 }
 
+func TestTypeDeque(t *testing.T) {
+	a, b := new(Type), new(Type)
+
+	t.Run("pop", func(t *testing.T) {
+		var td typeDeque
+		td.push(a)
+		td.push(b)
+
+		if td.pop() != b {
+			t.Error("Didn't pop b first")
+		}
+
+		if td.pop() != a {
+			t.Error("Didn't pop a second")
+		}
+
+		if td.pop() != nil {
+			t.Error("Didn't pop nil")
+		}
+	})
+
+	t.Run("shift", func(t *testing.T) {
+		var td typeDeque
+		td.push(a)
+		td.push(b)
+
+		if td.shift() != a {
+			t.Error("Didn't shift a second")
+		}
+
+		if td.shift() != b {
+			t.Error("Didn't shift b first")
+		}
+
+		if td.shift() != nil {
+			t.Error("Didn't shift nil")
+		}
+	})
+
+	t.Run("push", func(t *testing.T) {
+		var td typeDeque
+		td.push(a)
+		td.push(b)
+		td.shift()
+
+		ts := make([]Type, 12)
+		for i := range ts {
+			td.push(&ts[i])
+		}
+
+		if td.shift() != b {
+			t.Error("Didn't shift b first")
+		}
+		for i := range ts {
+			if td.shift() != &ts[i] {
+				t.Fatal("Shifted wrong Type at pos", i)
+			}
+		}
+	})
+
+	t.Run("all", func(t *testing.T) {
+		var td typeDeque
+		td.push(a)
+		td.push(b)
+
+		all := td.all()
+		if len(all) != 2 {
+			t.Fatal("Expected 2 elements, got", len(all))
+		}
+
+		if all[0] != a || all[1] != b {
+			t.Fatal("Elements don't match")
+		}
+	})
+}
+
 func newCyclicalType(n int) Type {
 	ptr := &Pointer{}
 	prev := Type(ptr)