debug/dwarf: fix nil pointer dereference in cyclic type structures

Currently readType simultaneously constructs a type graph and resolves
the sizes of the types. However, these two operations are
fundamentally at odds: the order we parse a cyclic structure in may be
different than the order we need to resolve type sizes in. As a
result, it's possible that when readType attempts to resolve the size
of a typedef, it may dereference a nil Type field of another typedef
retrieved from the type cache that's only partially constructed.

To fix this, we delay resolving typedef sizes until the end of the
readType recursion, when the full type graph is constructed.

Fixes #13039.

Change-Id: I9889af37fb3be5437995030fdd61e45871319d07
Reviewed-on: https://go-review.googlesource.com/18459
Reviewed-by: Russ Cox <rsc@golang.org>
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

5 files changed, 69 insertions, 8 deletions

diff --git a/src/debug/dwarf/testdata/cycle.c b/src/debug/dwarf/testdata/cycle.c
new file mode 100644
index 0000000000..a0b53dfe74
--- /dev/null
+++ b/src/debug/dwarf/testdata/cycle.c
@@ -0,0 +1,7 @@
+typedef struct aaa *AAA;
+typedef AAA BBB;
+struct aaa { BBB val; };
+
+AAA x(void) {
+    return (AAA)0;
+}
diff --git a/src/debug/dwarf/testdata/cycle.elf b/src/debug/dwarf/testdata/cycle.elf
new file mode 100644
index 0000000000..e0b66caa63
--- /dev/null
+++ b/src/debug/dwarf/testdata/cycle.elf
diff --git a/src/debug/dwarf/type.go b/src/debug/dwarf/type.go
index a5daa1d0bb..c76a472d78 100644
--- a/src/debug/dwarf/type.go
+++ b/src/debug/dwarf/type.go
@@ -275,12 +275,14 @@ type typeReader interface {
 
 // Type reads the type at off in the DWARF ``info'' section.
 func (d *Data) Type(off Offset) (Type, error) {
-	return d.readType("info", d.Reader(), off, d.typeCache)
+	return d.readType("info", d.Reader(), off, d.typeCache, nil)
 }
 
-// readType reads a type from r at off of name using and updating a
-// type cache.
-func (d *Data) readType(name string, r typeReader, off Offset, typeCache map[Offset]Type) (Type, error) {
+// readType reads a type from r at off of name. It adds types to the
+// type cache, appends new typedef types to typedefs, and computes the
+// sizes of types. Callers should pass nil for typedefs; this is used
+// for internal recursion.
+func (d *Data) readType(name string, r typeReader, off Offset, typeCache map[Offset]Type, typedefs *[]*TypedefType) (Type, error) {
 	if t, ok := typeCache[off]; ok {
 		return t, nil
 	}
@@ -294,9 +296,24 @@ func (d *Data) readType(name string, r typeReader, off Offset, typeCache map[Off
 		return nil, DecodeError{name, off, "no type at offset"}
 	}
 
+	// If this is the root of the recursion, prepare to resolve
+	// typedef sizes once the recursion is done. This must be done
+	// after the type graph is constructed because it may need to
+	// resolve cycles in a different order than readType
+	// encounters them.
+	if typedefs == nil {
+		var typedefList []*TypedefType
+		defer func() {
+			for _, t := range typedefList {
+				t.Common().ByteSize = t.Type.Size()
+			}
+		}()
+		typedefs = &typedefList
+	}
+
 	// Parse type from Entry.
 	// Must always set typeCache[off] before calling
-	// d.Type recursively, to handle circular types correctly.
+	// d.readType recursively, to handle circular types correctly.
 	var typ Type
 
 	nextDepth := 0
@@ -345,7 +362,7 @@ func (d *Data) readType(name string, r typeReader, off Offset, typeCache map[Off
 		var t Type
 		switch toff := tval.(type) {
 		case Offset:
-			if t, err = d.readType(name, r.clone(), toff, typeCache); err != nil {
+			if t, err = d.readType(name, r.clone(), toff, typeCache, typedefs); err != nil {
 				return nil
 			}
 		case uint64:
@@ -674,7 +691,10 @@ func (d *Data) readType(name string, r typeReader, off Offset, typeCache map[Off
 			b = -1
 			switch t := typ.(type) {
 			case *TypedefType:
-				b = t.Type.Size()
+				// Record that we need to resolve this
+				// type's size once the type graph is
+				// constructed.
+				*typedefs = append(*typedefs, t)
 			case *PtrType:
 				b = int64(addressSize)
 			}
diff --git a/src/debug/dwarf/type_test.go b/src/debug/dwarf/type_test.go
index 2cb85e74bb..ad6308deba 100644
--- a/src/debug/dwarf/type_test.go
+++ b/src/debug/dwarf/type_test.go
@@ -120,3 +120,37 @@ func testTypedefs(t *testing.T, d *Data, kind string) {
 		}
 	}
 }
+
+func TestTypedefCycle(t *testing.T) {
+	// See issue #13039: reading a typedef cycle starting from a
+	// different place than the size needed to be computed from
+	// used to crash.
+	//
+	// cycle.elf built with GCC 4.8.4:
+	//    gcc -g -c -o cycle.elf cycle.c
+	d := elfData(t, "testdata/cycle.elf")
+	r := d.Reader()
+	offsets := []Offset{}
+	for {
+		e, err := r.Next()
+		if err != nil {
+			t.Fatal("r.Next:", err)
+		}
+		if e == nil {
+			break
+		}
+		switch e.Tag {
+		case TagBaseType, TagTypedef, TagPointerType, TagStructType:
+			offsets = append(offsets, e.Offset)
+		}
+	}
+
+	// Parse each type with a fresh type cache.
+	for _, offset := range offsets {
+		d := elfData(t, "testdata/cycle.elf")
+		_, err := d.Type(offset)
+		if err != nil {
+			t.Fatalf("d.Type(0x%x): %s", offset, err)
+		}
+	}
+}
diff --git a/src/debug/dwarf/typeunit.go b/src/debug/dwarf/typeunit.go
index 9cfb4a8b25..0f4e07ebf7 100644
--- a/src/debug/dwarf/typeunit.go
+++ b/src/debug/dwarf/typeunit.go
@@ -101,7 +101,7 @@ func (d *Data) sigToType(sig uint64) (Type, error) {
 
 	b := makeBuf(d, tu, tu.name, tu.off, tu.data)
 	r := &typeUnitReader{d: d, tu: tu, b: b}
-	t, err := d.readType(tu.name, r, Offset(tu.toff), make(map[Offset]Type))
+	t, err := d.readType(tu.name, r, Offset(tu.toff), make(map[Offset]Type), nil)
 	if err != nil {
 		return nil, err
 	}