Repository: segmentio/encoding (go)

Issue:
json: stack overflow when encoding cyclic structures
Encoding a cyclic data structure results in a stack overflow. This is an invalid operation, but the behavior here is different than the stdlib that detects it and returns an error.

---

Program to reproduce:

```go
package main

import (
	"fmt"

	"github.com/segmentio/encoding/json"
)

type Foo struct {
	Bar *Bar
}

type Bar struct {
	Foo *Foo
}

func main() {
	f := &Foo{}
	b := &Bar{}
	f.Bar = b
	b.Foo = f

	_, err := json.Marshal(f)
	fmt.Println(err)
}
```

Crash in that example:

```
$ go run main.go           
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc0201603e0 stack=[0xc020160000, 0xc040160000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x4eafe9, 0x59f520})
	/home/thomas/src/github.com/golang/go/src/runtime/panic.go:1198 +0x71
runtime.newstack()
	/home/thomas/src/github.com/golang/go/src/runtime/stack.go:1088 +0x5ac
runtime.morestack()
	/home/thomas/src/github.com/golang/go/src/runtime/asm_amd64.s:461 +0x8b

goroutine 1 [running]:
github.com/segmentio/encoding/json.encoder.encodeStruct({0x3}, {0xc002568000, 0x873eaf, 0x8ac000}, 0xc00000e030, 0xc00007e240)
	/home/thomas/pkg/mod/github.com/segmentio/encoding@v0.3.0/json/encode.go:758 +0x47a fp=0xc0201603f0 sp=0xc0201603e8 pc=0x4c185a
github.com/segmentio/encoding/json.constructStructEncodeFunc.func1({0x0}, {0xc002568000, 0x0, 0x0}, 0x0)
	/home/thomas/pkg/mod/github.com/segmentio/encoding@v0.3.0/json/codec.go:497 +0x25 fp=0xc020160430 sp=0xc0201603f0 pc=0x4ada05
github.com/segmentio/encoding/json.encoder.encodePointer({0x0}, {0xc002568000, 0x0, 0x0}, 0x0, {0x0, 0x0}, 0x0)
	/home/thomas/pkg/mod/github.com/segmentio/encoding@v0.3.0/json/encode.go:818 +0x7c fp=0xc020160470 sp=0xc020160430 pc=0x4c19fc
github.com/segmentio/encoding/json.constructPointerEncodeFunc.func1({0x0}, {0xc002568000, 0x0, 0x0}, 0x0)
	/home/thomas/pkg/mod/github.com/segmentio/encoding@v0.3.0/json/codec.go:738 +0x2a fp=0xc0201604c0 sp=0xc020160470 pc=0x4af5ea
github.com/segmentio/encoding/json.encoder.encodeStruct({0x0}, {0xc002568000, 0x873ea8, 0x0}, 0xc00000e028, 0xc00007e1e0)
	/home/thomas/pkg/mod/github.com/segmentio/encoding@v0.3.0/json/encode.go:789 +0x307 fp=0xc020160598 sp=0xc0201604c0 pc=0x4c16e7
github.com/segmentio/encoding/json.constructStructEncodeFunc.func1({0x0}, {0xc002568000, 0x0, 0x0}, 0x0)
	/home/thomas/pkg/mod/github.com/segmentio/encoding@v0.3.0/json/codec.go:497 +0x25 fp=0xc0201605d8 sp=0xc020160598 pc=0x4ada05
github.com/segmentio/encoding/json.encoder.encodePointer({0x0}, {0xc002568000, 0x0, 0x0}, 0x0, {0x0, 0x0}, 0x0)
	/home/thomas/pkg/mod/github.com/segmentio/encoding@v0.3.0/json/encode.go:818 +0x7c fp=0xc020160618 sp=0xc0201605d8 pc=0x4c19fc
...additional frames elided...
exit status 2
```

Output using stdlib's `encoding/json`:

```
$ go run main.go           
json: unsupported value: encountered a cycle via *main.Foo
```

Stdlib implementation: https://cs.opensource.google/go/go/+/refs/tags/go1.17.3:src/encoding/json/encode.go;l=784-793;drc=refs%2Ftags%2Fgo1.17.3

Pull request description:
add test for issue 107
Fixes #107 

I've added a pointer cycle check similar to the one used in the standard library, which starts detecting pointer cycles after entering the `encoderPointer` function code 1000 times, which keeps the cost of detecting the loop almost zero in most cases.

I changed the type of `json.AppendFlags` from `uint` to `uint32` so we could store the encoder depth in the other 4 bytes and keep the struct size small. There is an extra pointer we have to store in the encoder tho for the map we might use to track pointer cycles.

I changed the type of `json.ParseFlags` from `uint` to `uint32` for consistency with `json.AppendFlags`.

Patch:
diff --git a/json/codec.go b/json/codec.go
index 381b0e7..908c3f6 100644
--- a/json/codec.go
+++ b/json/codec.go
@@ -16,13 +16,32 @@ import (
 	"github.com/segmentio/asm/keyset"
 )
 
+const (
+	// 1000 is the value used by the standard encoding/json package.
+	//
+	// https://cs.opensource.google/go/go/+/refs/tags/go1.17.3:src/encoding/json/encode.go;drc=refs%2Ftags%2Fgo1.17.3;l=300
+	startDetectingCyclesAfter = 1000
+)
+
 type codec struct {
 	encode encodeFunc
 	decode decodeFunc
 }
 
-type encoder struct{ flags AppendFlags }
-type decoder struct{ flags ParseFlags }
+type encoder struct {
+	flags AppendFlags
+	// ptrDepth tracks the depth of pointer cycles, when it reaches the value
+	// of startDetectingCyclesAfter, the ptrSeen map is allocated and the
+	// encoder starts tracking pointers it has seen as an attempt to detect
+	// whether it has entered a pointer cycle and needs to error before the
+	// goroutine runs out of stack space.
+	ptrDepth uint32
+	ptrSeen  map[unsafe.Pointer]struct{}
+}
+
+type decoder struct {
+	flags ParseFlags
+}
 
 type encodeFunc func(encoder, []byte, unsafe.Pointer) ([]byte, error)
 type decodeFunc func(decoder, []byte, unsafe.Pointer) ([]byte, error)
diff --git a/json/encode.go b/json/encode.go
index 8dd0e4b..acb3b67 100644
--- a/json/encode.go
+++ b/json/encode.go
@@ -2,6 +2,7 @@ package json
 
 import (
 	"encoding"
+	"fmt"
 	"math"
 	"reflect"
 	"sort"
@@ -815,6 +816,18 @@ func (e encoder) encodeEmbeddedStructPointer(b []byte, p unsafe.Pointer, t refle
 
 func (e encoder) encodePointer(b []byte, p unsafe.Pointer, t reflect.Type, encode encodeFunc) ([]byte, error) {
 	if p = *(*unsafe.Pointer)(p); p != nil {
+		if e.ptrDepth++; e.ptrDepth >= startDetectingCyclesAfter {
+			if _, seen := e.ptrSeen[p]; seen {
+				// TODO: reconstruct the reflect.Value from p + t so we can set
+				// the erorr's Value field?
+				return b, &UnsupportedValueError{Str: fmt.Sprintf("encountered a cycle via %s", t)}
+			}
+			if e.ptrSeen == nil {
+				e.ptrSeen = make(map[unsafe.Pointer]struct{})
+			}
+			e.ptrSeen[p] = struct{}{}
+			defer delete(e.ptrSeen, p)
+		}
 		return encode(e, b, p)
 	}
 	return e.encodeNull(b, nil)
diff --git a/json/json.go b/json/json.go
index c3e710b..9d259cc 100644
--- a/json/json.go
+++ b/json/json.go
@@ -55,7 +55,7 @@ type UnsupportedValueError = json.UnsupportedValueError
 
 // AppendFlags is a type used to represent configuration options that can be
 // applied when formatting json output.
-type AppendFlags uint
+type AppendFlags uint32
 
 const (
 	// EscapeHTML is a formatting flag used to to escape HTML in json strings.
@@ -74,7 +74,7 @@ const (
 
 // ParseFlags is a type used to represent configuration options that can be
 // applied when parsing json input.
-type ParseFlags uint
+type ParseFlags uint32
 
 func (flags ParseFlags) has(f ParseFlags) bool {
 	return (flags & f) != 0


Test patch:
diff --git a/json/json_test.go b/json/json_test.go
index 5f3f8a2..63ec861 100644
--- a/json/json_test.go
+++ b/json/json_test.go
@@ -1591,6 +1591,28 @@ func TestGithubIssue44(t *testing.T) {
 	}
 }
 
+type issue107Foo struct {
+	Bar *issue107Bar
+}
+
+type issue107Bar struct {
+	Foo *issue107Foo
+}
+
+func TestGithubIssue107(t *testing.T) {
+	f := &issue107Foo{}
+	b := &issue107Bar{}
+	f.Bar = b
+	b.Foo = f
+
+	_, err := Marshal(f) // must not crash
+	switch err.(type) {
+	case *UnsupportedValueError:
+	default:
+		t.Errorf("marshaling a cycling data structure was expected to return an unsupported value error but got %T", err)
+	}
+}
+
 type rawJsonString string
 
 func (r *rawJsonString) UnmarshalJSON(b []byte) error {