pkg/state/encode.go - third_party/gvisor.dev/gvisor/netstack - Git at Google

 // Copyright 2018 The gVisor Authors.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 package state

 import (
 	"container/list"
 	"context"
 	"encoding/binary"
 	"fmt"
 	"io"
 	"reflect"
 	"sort"

 	"github.com/golang/protobuf/proto"
 	pb "gvisor.dev/gvisor/pkg/state/object_go_proto"
 )

 // queuedObject is an object queued for encoding.
 type queuedObject struct {
 	id   uint64
 	obj  reflect.Value
 	path recoverable
 }

 // encodeState is state used for encoding.
 //
 // The encoding process is a breadth-first traversal of the object graph. The
 // inherent races and dependencies are much simpler than the decode case.
 type encodeState struct {
 	// ctx is the encode context.
 	ctx context.Context

 	// lastID is the last object ID.
 	//
 	// See idsByObject for context. Because of the special zero encoding
 	// used for reference values, the first ID must be 1.
 	lastID uint64

 	// idsByObject is a set of objects, indexed via:
 	//
 	//	reflect.ValueOf(x).UnsafeAddr
 	//
 	// This provides IDs for objects.
 	idsByObject map[uintptr]uint64

 	// values stores values that span the addresses.
 	//
 	// addrSet is a a generated type which efficiently stores ranges of
 	// addresses. When encoding pointers, these ranges are filled in and
 	// used to check for overlapping or conflicting pointers. This would
 	// indicate a pointer to an field, or a non-type safe value, neither of
 	// which are currently decodable.
 	//
 	// See the usage of values below for more context.
 	values addrSet

 	// w is the output stream.
 	w io.Writer

 	// pending is the list of objects to be serialized.
 	//
 	// This is a set of queuedObjects.
 	pending list.List

 	// done is the a list of finished objects.
 	//
 	// This is kept to prevent garbage collection and address reuse.
 	done list.List

 	// stats is the passed stats object.
 	stats *Stats

 	// recoverable is the panic recover facility.
 	recoverable
 }

 // register looks up an ID, registering if necessary.
 //
 // If the object was not previously registered, it is enqueued to be serialized.
 // See the documentation for idsByObject for more information.
 func (es *encodeState) register(obj reflect.Value) uint64 {
 	// It is not legal to call register for any non-pointer objects (see
 	// below), so we panic with a recoverable error if this is a mismatch.
 	if obj.Kind() != reflect.Ptr && obj.Kind() != reflect.Map {
 		panic(fmt.Errorf("non-pointer %#v registered", obj.Interface()))
 	}

 	addr := obj.Pointer()
 	if obj.Kind() == reflect.Ptr && obj.Elem().Type().Size() == 0 {
 		// For zero-sized objects, we always provide a unique ID.
 		// That's because the runtime internally multiplexes pointers
 		// to the same address. We can't be certain what the intent is
 		// with pointers to zero-sized objects, so we just give them
 		// all unique identities.
 	} else if id, ok := es.idsByObject[addr]; ok {
 		// Already registered.
 		return id
 	}

 	// Ensure that the first ID given out is one. See note on lastID. The
 	// ID zero is used to indicate nil values.
 	es.lastID++
 	id := es.lastID
 	es.idsByObject[addr] = id
 	if obj.Kind() == reflect.Ptr {
 		// Dereference and treat as a pointer.
 		es.pending.PushBack(queuedObject{id: id, obj: obj.Elem(), path: es.recoverable.copy()})

 		// Register this object at all addresses.
 		typ := obj.Elem().Type()
 		if size := typ.Size(); size > 0 {
 			r := addrRange{addr, addr + size}
 			if !es.values.IsEmptyRange(r) {
 				old := es.values.LowerBoundSegment(addr).Value().Interface().(recoverable)
 				panic(fmt.Errorf("overlapping objects: [new object] %#v [existing object path] %s", obj.Interface(), old.path()))
 			}
 			es.values.Add(r, reflect.ValueOf(es.recoverable.copy()))
 		}
 	} else {
 		// Push back the map itself; when maps are encoded from the
 		// top-level, forceMap will be equal to true.
 		es.pending.PushBack(queuedObject{id: id, obj: obj, path: es.recoverable.copy()})
 	}

 	return id
 }

 // encodeMap encodes a map.
 func (es *encodeState) encodeMap(obj reflect.Value) *pb.Map {
 	var (
 		keys   []*pb.Object
 		values []*pb.Object
 	)
 	for i, k := range obj.MapKeys() {
 		v := obj.MapIndex(k)
 		kp := es.encodeObject(k, false, ".(key %d)", i)
 		vp := es.encodeObject(v, false, "[%#v]", k.Interface())
 		keys = append(keys, kp)
 		values = append(values, vp)
 	}
 	return &pb.Map{Keys: keys, Values: values}
 }

 // encodeStruct encodes a composite object.
 func (es *encodeState) encodeStruct(obj reflect.Value) *pb.Struct {
 	// Invoke the save.
 	m := Map{newInternalMap(es, nil, nil)}
 	defer internalMapPool.Put(m.internalMap)
 	if !obj.CanAddr() {
 		// Force it to a * type of the above; this involves a copy.
 		localObj := reflect.New(obj.Type())
 		localObj.Elem().Set(obj)
 		obj = localObj.Elem()
 	}
 	fns, ok := registeredTypes.lookupFns(obj.Addr().Type())
 	if ok {
 		// Invoke the provided saver.
 		fns.invokeSave(obj.Addr(), m)
 	} else if obj.NumField() == 0 {
 		// Allow unregistered anonymous, empty structs.
 		return &pb.Struct{}
 	} else {
 		// Propagate an error.
 		panic(fmt.Errorf("unregistered type %T", obj.Interface()))
 	}

 	// Sort the underlying slice, and check for duplicates. This is done
 	// once instead of on each add, because performing this sort once is
 	// far more efficient.
 	if len(m.data) > 1 {
 		sort.Slice(m.data, func(i, j int) bool {
 			return m.data[i].name < m.data[j].name
 		})
 		for i := range m.data {
 			if i > 0 && m.data[i-1].name == m.data[i].name {
 				panic(fmt.Errorf("duplicate name %s", m.data[i].name))
 			}
 		}
 	}

 	// Encode the resulting fields.
 	fields := make([]*pb.Field, 0, len(m.data))
 	for _, e := range m.data {
 		fields = append(fields, &pb.Field{
 			Name:  e.name,
 			Value: e.object,
 		})
 	}

 	// Return the encoded object.
 	return &pb.Struct{Fields: fields}
 }

 // encodeArray encodes an array.
 func (es *encodeState) encodeArray(obj reflect.Value) *pb.Array {
 	var (
 		contents []*pb.Object
 	)
 	for i := 0; i < obj.Len(); i++ {
 		entry := es.encodeObject(obj.Index(i), false, "[%d]", i)
 		contents = append(contents, entry)
 	}
 	return &pb.Array{Contents: contents}
 }

 // encodeInterface encodes an interface.
 //
 // Precondition: the value is not nil.
 func (es *encodeState) encodeInterface(obj reflect.Value) *pb.Interface {
 	// Check for the nil interface.
 	obj = reflect.ValueOf(obj.Interface())
 	if !obj.IsValid() {
 		return &pb.Interface{
 			Type:  "", // left alone in decode.
 			Value: &pb.Object{Value: &pb.Object_RefValue{0}},
 		}
 	}
 	// We have an interface value here. How do we save that? We
 	// resolve the underlying type and save it as a dispatchable.
 	typName, ok := registeredTypes.lookupName(obj.Type())
 	if !ok {
 		panic(fmt.Errorf("type %s is not registered", obj.Type()))
 	}

 	// Encode the object again.
 	return &pb.Interface{
 		Type:  typName,
 		Value: es.encodeObject(obj, false, ".(%s)", typName),
 	}
 }

 // encodeObject encodes an object.
 //
 // If mapAsValue is true, then a map will be encoded directly.
 func (es *encodeState) encodeObject(obj reflect.Value, mapAsValue bool, format string, param interface{}) (object *pb.Object) {
 	es.push(false, format, param)
 	es.stats.Add(obj)
 	es.stats.Start(obj)

 	switch obj.Kind() {
 	case reflect.Bool:
 		object = &pb.Object{Value: &pb.Object_BoolValue{obj.Bool()}}
 	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
 		object = &pb.Object{Value: &pb.Object_Int64Value{obj.Int()}}
 	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
 		object = &pb.Object{Value: &pb.Object_Uint64Value{obj.Uint()}}
 	case reflect.Float32, reflect.Float64:
 		object = &pb.Object{Value: &pb.Object_DoubleValue{obj.Float()}}
 	case reflect.Array:
 		switch obj.Type().Elem().Kind() {
 		case reflect.Uint8:
 			object = &pb.Object{Value: &pb.Object_ByteArrayValue{pbSlice(obj).Interface().([]byte)}}
 		case reflect.Uint16:
 			// 16-bit slices are serialized as 32-bit slices.
 			// See object.proto for details.
 			s := pbSlice(obj).Interface().([]uint16)
 			t := make([]uint32, len(s))
 			for i := range s {
 				t[i] = uint32(s[i])
 			}
 			object = &pb.Object{Value: &pb.Object_Uint16ArrayValue{&pb.Uint16S{Values: t}}}
 		case reflect.Uint32:
 			object = &pb.Object{Value: &pb.Object_Uint32ArrayValue{&pb.Uint32S{Values: pbSlice(obj).Interface().([]uint32)}}}
 		case reflect.Uint64:
 			object = &pb.Object{Value: &pb.Object_Uint64ArrayValue{&pb.Uint64S{Values: pbSlice(obj).Interface().([]uint64)}}}
 		case reflect.Uintptr:
 			object = &pb.Object{Value: &pb.Object_UintptrArrayValue{&pb.Uintptrs{Values: pbSlice(obj).Interface().([]uint64)}}}
 		case reflect.Int8:
 			object = &pb.Object{Value: &pb.Object_Int8ArrayValue{&pb.Int8S{Values: pbSlice(obj).Interface().([]byte)}}}
 		case reflect.Int16:
 			// 16-bit slices are serialized as 32-bit slices.
 			// See object.proto for details.
 			s := pbSlice(obj).Interface().([]int16)
 			t := make([]int32, len(s))
 			for i := range s {
 				t[i] = int32(s[i])
 			}
 			object = &pb.Object{Value: &pb.Object_Int16ArrayValue{&pb.Int16S{Values: t}}}
 		case reflect.Int32:
 			object = &pb.Object{Value: &pb.Object_Int32ArrayValue{&pb.Int32S{Values: pbSlice(obj).Interface().([]int32)}}}
 		case reflect.Int64:
 			object = &pb.Object{Value: &pb.Object_Int64ArrayValue{&pb.Int64S{Values: pbSlice(obj).Interface().([]int64)}}}
 		case reflect.Bool:
 			object = &pb.Object{Value: &pb.Object_BoolArrayValue{&pb.Bools{Values: pbSlice(obj).Interface().([]bool)}}}
 		case reflect.Float32:
 			object = &pb.Object{Value: &pb.Object_Float32ArrayValue{&pb.Float32S{Values: pbSlice(obj).Interface().([]float32)}}}
 		case reflect.Float64:
 			object = &pb.Object{Value: &pb.Object_Float64ArrayValue{&pb.Float64S{Values: pbSlice(obj).Interface().([]float64)}}}
 		default:
 			object = &pb.Object{Value: &pb.Object_ArrayValue{es.encodeArray(obj)}}
 		}
 	case reflect.Slice:
 		if obj.IsNil() || obj.Cap() == 0 {
 			// Handled specially in decode; store as nil value.
 			object = &pb.Object{Value: &pb.Object_RefValue{0}}
 		} else {
 			// Serialize a slice as the array plus length and capacity.
 			object = &pb.Object{Value: &pb.Object_SliceValue{&pb.Slice{
 				Capacity: uint32(obj.Cap()),
 				Length:   uint32(obj.Len()),
 				RefValue: es.register(arrayFromSlice(obj)),
 			}}}
 		}
 	case reflect.String:
 		object = &pb.Object{Value: &pb.Object_StringValue{[]byte(obj.String())}}
 	case reflect.Ptr:
 		if obj.IsNil() {
 			// Handled specially in decode; store as a nil value.
 			object = &pb.Object{Value: &pb.Object_RefValue{0}}
 		} else {
 			es.push(true /* dereference */, "", nil)
 			object = &pb.Object{Value: &pb.Object_RefValue{es.register(obj)}}
 			es.pop()
 		}
 	case reflect.Interface:
 		// We don't check for IsNil here, as we want to encode type
 		// information. The case of the empty interface (no type, no
 		// value) is handled by encodeInteface.
 		object = &pb.Object{Value: &pb.Object_InterfaceValue{es.encodeInterface(obj)}}
 	case reflect.Struct:
 		object = &pb.Object{Value: &pb.Object_StructValue{es.encodeStruct(obj)}}
 	case reflect.Map:
 		if obj.IsNil() {
 			// Handled specially in decode; store as a nil value.
 			object = &pb.Object{Value: &pb.Object_RefValue{0}}
 		} else if mapAsValue {
 			// Encode the map directly.
 			object = &pb.Object{Value: &pb.Object_MapValue{es.encodeMap(obj)}}
 		} else {
 			// Encode a reference to the map.
 			//
 			// Remove the map object count here to avoid double
 			// counting, as this object will be counted again when
 			// it gets processed later. We do not add a reference
 			// count as the reference is artificial.
 			es.stats.Remove(obj)
 			object = &pb.Object{Value: &pb.Object_RefValue{es.register(obj)}}
 		}
 	default:
 		panic(fmt.Errorf("unknown primitive %#v", obj.Interface()))
 	}

 	es.stats.Done()
 	es.pop()
 	return
 }

 // Serialize serializes the object state.
 //
 // This function may panic and should be run in safely().
 func (es *encodeState) Serialize(obj reflect.Value) {
 	es.register(obj.Addr())

 	// Pop off the list until we're done.
 	for es.pending.Len() > 0 {
 		e := es.pending.Front()

 		// Extract the queued object.
 		qo := e.Value.(queuedObject)
 		es.stats.Start(qo.obj)

 		es.pending.Remove(e)

 		es.from = &qo.path
 		o := es.encodeObject(qo.obj, true, "", nil)

 		// Emit to our output stream.
 		if err := es.writeObject(qo.id, o); err != nil {
 			panic(err)
 		}

 		// Mark as done.
 		es.done.PushBack(e)
 		es.stats.Done()
 	}

 	// Write a zero-length terminal at the end; this is a sanity check
 	// applied at decode time as well (see decode.go).
 	if err := WriteHeader(es.w, 0, false); err != nil {
 		panic(err)
 	}
 }

 // WriteHeader writes a header.
 //
 // Each object written to the statefile should be prefixed with a header. In
 // order to generate statefiles that play nicely with debugging tools, raw
 // writes should be prefixed with a header with object set to false and the
 // appropriate length. This will allow tools to skip these regions.
 func WriteHeader(w io.Writer, length uint64, object bool) error {
 	// The lowest-order bit encodes whether this is a valid object. This is
 	// a purely internal convention, but allows the object flag to be
 	// returned from ReadHeader.
 	length = length << 1
 	if object {
 		length |= 0x1
 	}

 	// Write a header.
 	var hdr [32]byte
 	encodedLen := binary.PutUvarint(hdr[:], length)
 	for done := 0; done < encodedLen; {
 		n, err := w.Write(hdr[done:encodedLen])
 		done += n
 		if n == 0 && err != nil {
 			return err
 		}
 	}

 	return nil
 }

 // writeObject writes an object to the stream.
 func (es *encodeState) writeObject(id uint64, obj *pb.Object) error {
 	// Marshal the proto.
 	buf, err := proto.Marshal(obj)
 	if err != nil {
 		return err
 	}

 	// Write the object header.
 	if err := WriteHeader(es.w, uint64(len(buf)), true); err != nil {
 		return err
 	}

 	// Write the object.
 	for done := 0; done < len(buf); {
 		n, err := es.w.Write(buf[done:])
 		done += n
 		if n == 0 && err != nil {
 			return err
 		}
 	}

 	return nil
 }

 // addrSetFunctions is used by addrSet.
 type addrSetFunctions struct{}

 func (addrSetFunctions) MinKey() uintptr {
 	return 0
 }

 func (addrSetFunctions) MaxKey() uintptr {
 	return ^uintptr(0)
 }

 func (addrSetFunctions) ClearValue(val *reflect.Value) {
 }

 func (addrSetFunctions) Merge(_ addrRange, val1 reflect.Value, _ addrRange, val2 reflect.Value) (reflect.Value, bool) {
 	return val1, val1 == val2
 }

 func (addrSetFunctions) Split(_ addrRange, val reflect.Value, _ uintptr) (reflect.Value, reflect.Value) {
 	return val, val
 }
	// Copyright 2018 The gVisor Authors.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	package state

	import (
	"container/list"
	"context"
	"encoding/binary"
	"fmt"
	"io"
	"reflect"
	"sort"

	"github.com/golang/protobuf/proto"
	pb "gvisor.dev/gvisor/pkg/state/object_go_proto"
	)

	// queuedObject is an object queued for encoding.
	type queuedObject struct {
	id uint64
	obj reflect.Value
	path recoverable
	}

	// encodeState is state used for encoding.
	//
	// The encoding process is a breadth-first traversal of the object graph. The
	// inherent races and dependencies are much simpler than the decode case.
	type encodeState struct {
	// ctx is the encode context.
	ctx context.Context

	// lastID is the last object ID.
	//
	// See idsByObject for context. Because of the special zero encoding
	// used for reference values, the first ID must be 1.
	lastID uint64

	// idsByObject is a set of objects, indexed via:
	//
	// reflect.ValueOf(x).UnsafeAddr
	//
	// This provides IDs for objects.
	idsByObject map[uintptr]uint64

	// values stores values that span the addresses.
	//
	// addrSet is a a generated type which efficiently stores ranges of
	// addresses. When encoding pointers, these ranges are filled in and
	// used to check for overlapping or conflicting pointers. This would
	// indicate a pointer to an field, or a non-type safe value, neither of
	// which are currently decodable.
	//
	// See the usage of values below for more context.
	values addrSet

	// w is the output stream.
	w io.Writer

	// pending is the list of objects to be serialized.
	//
	// This is a set of queuedObjects.
	pending list.List

	// done is the a list of finished objects.
	//
	// This is kept to prevent garbage collection and address reuse.
	done list.List

	// stats is the passed stats object.
	stats *Stats

	// recoverable is the panic recover facility.
	recoverable
	}

	// register looks up an ID, registering if necessary.
	//
	// If the object was not previously registered, it is enqueued to be serialized.
	// See the documentation for idsByObject for more information.
	func (es *encodeState) register(obj reflect.Value) uint64 {
	// It is not legal to call register for any non-pointer objects (see
	// below), so we panic with a recoverable error if this is a mismatch.
	if obj.Kind() != reflect.Ptr && obj.Kind() != reflect.Map {
	panic(fmt.Errorf("non-pointer %#v registered", obj.Interface()))
	}

	addr := obj.Pointer()
	if obj.Kind() == reflect.Ptr && obj.Elem().Type().Size() == 0 {
	// For zero-sized objects, we always provide a unique ID.
	// That's because the runtime internally multiplexes pointers
	// to the same address. We can't be certain what the intent is
	// with pointers to zero-sized objects, so we just give them
	// all unique identities.
	} else if id, ok := es.idsByObject[addr]; ok {
	// Already registered.
	return id
	}

	// Ensure that the first ID given out is one. See note on lastID. The
	// ID zero is used to indicate nil values.
	es.lastID++
	id := es.lastID
	es.idsByObject[addr] = id
	if obj.Kind() == reflect.Ptr {
	// Dereference and treat as a pointer.
	es.pending.PushBack(queuedObject{id: id, obj: obj.Elem(), path: es.recoverable.copy()})

	// Register this object at all addresses.
	typ := obj.Elem().Type()
	if size := typ.Size(); size > 0 {
	r := addrRange{addr, addr + size}
	if !es.values.IsEmptyRange(r) {
	old := es.values.LowerBoundSegment(addr).Value().Interface().(recoverable)
	panic(fmt.Errorf("overlapping objects: [new object] %#v [existing object path] %s", obj.Interface(), old.path()))
	}
	es.values.Add(r, reflect.ValueOf(es.recoverable.copy()))
	}
	} else {
	// Push back the map itself; when maps are encoded from the
	// top-level, forceMap will be equal to true.
	es.pending.PushBack(queuedObject{id: id, obj: obj, path: es.recoverable.copy()})
	}

	return id
	}

	// encodeMap encodes a map.
	func (es encodeState) encodeMap(obj reflect.Value) pb.Map {
	var (
	keys []*pb.Object
	values []*pb.Object
	)
	for i, k := range obj.MapKeys() {
	v := obj.MapIndex(k)
	kp := es.encodeObject(k, false, ".(key %d)", i)
	vp := es.encodeObject(v, false, "[%#v]", k.Interface())
	keys = append(keys, kp)
	values = append(values, vp)
	}
	return &pb.Map{Keys: keys, Values: values}
	}

	// encodeStruct encodes a composite object.
	func (es encodeState) encodeStruct(obj reflect.Value) pb.Struct {
	// Invoke the save.
	m := Map{newInternalMap(es, nil, nil)}
	defer internalMapPool.Put(m.internalMap)
	if !obj.CanAddr() {
	// Force it to a * type of the above; this involves a copy.
	localObj := reflect.New(obj.Type())
	localObj.Elem().Set(obj)
	obj = localObj.Elem()
	}
	fns, ok := registeredTypes.lookupFns(obj.Addr().Type())
	if ok {
	// Invoke the provided saver.
	fns.invokeSave(obj.Addr(), m)
	} else if obj.NumField() == 0 {
	// Allow unregistered anonymous, empty structs.
	return &pb.Struct{}
	} else {
	// Propagate an error.
	panic(fmt.Errorf("unregistered type %T", obj.Interface()))
	}

	// Sort the underlying slice, and check for duplicates. This is done
	// once instead of on each add, because performing this sort once is
	// far more efficient.
	if len(m.data) > 1 {
	sort.Slice(m.data, func(i, j int) bool {
	return m.data[i].name < m.data[j].name
	})
	for i := range m.data {
	if i > 0 && m.data[i-1].name == m.data[i].name {
	panic(fmt.Errorf("duplicate name %s", m.data[i].name))
	}
	}
	}

	// Encode the resulting fields.
	fields := make([]*pb.Field, 0, len(m.data))
	for _, e := range m.data {
	fields = append(fields, &pb.Field{
	Name: e.name,
	Value: e.object,
	})
	}

	// Return the encoded object.
	return &pb.Struct{Fields: fields}
	}

	// encodeArray encodes an array.
	func (es encodeState) encodeArray(obj reflect.Value) pb.Array {
	var (
	contents []*pb.Object
	)
	for i := 0; i < obj.Len(); i++ {
	entry := es.encodeObject(obj.Index(i), false, "[%d]", i)
	contents = append(contents, entry)
	}
	return &pb.Array{Contents: contents}
	}

	// encodeInterface encodes an interface.
	//
	// Precondition: the value is not nil.
	func (es encodeState) encodeInterface(obj reflect.Value) pb.Interface {
	// Check for the nil interface.
	obj = reflect.ValueOf(obj.Interface())
	if !obj.IsValid() {
	return &pb.Interface{
	Type: "", // left alone in decode.
	Value: &pb.Object{Value: &pb.Object_RefValue{0}},
	}
	}
	// We have an interface value here. How do we save that? We
	// resolve the underlying type and save it as a dispatchable.
	typName, ok := registeredTypes.lookupName(obj.Type())
	if !ok {
	panic(fmt.Errorf("type %s is not registered", obj.Type()))
	}

	// Encode the object again.
	return &pb.Interface{
	Type: typName,
	Value: es.encodeObject(obj, false, ".(%s)", typName),
	}
	}

	// encodeObject encodes an object.
	//
	// If mapAsValue is true, then a map will be encoded directly.
	func (es encodeState) encodeObject(obj reflect.Value, mapAsValue bool, format string, param interface{}) (object pb.Object) {
	es.push(false, format, param)
	es.stats.Add(obj)
	es.stats.Start(obj)

	switch obj.Kind() {
	case reflect.Bool:
	object = &pb.Object{Value: &pb.Object_BoolValue{obj.Bool()}}
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
	object = &pb.Object{Value: &pb.Object_Int64Value{obj.Int()}}
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
	object = &pb.Object{Value: &pb.Object_Uint64Value{obj.Uint()}}
	case reflect.Float32, reflect.Float64:
	object = &pb.Object{Value: &pb.Object_DoubleValue{obj.Float()}}
	case reflect.Array:
	switch obj.Type().Elem().Kind() {
	case reflect.Uint8:
	object = &pb.Object{Value: &pb.Object_ByteArrayValue{pbSlice(obj).Interface().([]byte)}}
	case reflect.Uint16:
	// 16-bit slices are serialized as 32-bit slices.
	// See object.proto for details.
	s := pbSlice(obj).Interface().([]uint16)
	t := make([]uint32, len(s))
	for i := range s {
	t[i] = uint32(s[i])
	}
	object = &pb.Object{Value: &pb.Object_Uint16ArrayValue{&pb.Uint16S{Values: t}}}
	case reflect.Uint32:
	object = &pb.Object{Value: &pb.Object_Uint32ArrayValue{&pb.Uint32S{Values: pbSlice(obj).Interface().([]uint32)}}}
	case reflect.Uint64:
	object = &pb.Object{Value: &pb.Object_Uint64ArrayValue{&pb.Uint64S{Values: pbSlice(obj).Interface().([]uint64)}}}
	case reflect.Uintptr:
	object = &pb.Object{Value: &pb.Object_UintptrArrayValue{&pb.Uintptrs{Values: pbSlice(obj).Interface().([]uint64)}}}
	case reflect.Int8:
	object = &pb.Object{Value: &pb.Object_Int8ArrayValue{&pb.Int8S{Values: pbSlice(obj).Interface().([]byte)}}}
	case reflect.Int16:
	// 16-bit slices are serialized as 32-bit slices.
	// See object.proto for details.
	s := pbSlice(obj).Interface().([]int16)
	t := make([]int32, len(s))
	for i := range s {
	t[i] = int32(s[i])
	}
	object = &pb.Object{Value: &pb.Object_Int16ArrayValue{&pb.Int16S{Values: t}}}
	case reflect.Int32:
	object = &pb.Object{Value: &pb.Object_Int32ArrayValue{&pb.Int32S{Values: pbSlice(obj).Interface().([]int32)}}}
	case reflect.Int64:
	object = &pb.Object{Value: &pb.Object_Int64ArrayValue{&pb.Int64S{Values: pbSlice(obj).Interface().([]int64)}}}
	case reflect.Bool:
	object = &pb.Object{Value: &pb.Object_BoolArrayValue{&pb.Bools{Values: pbSlice(obj).Interface().([]bool)}}}
	case reflect.Float32:
	object = &pb.Object{Value: &pb.Object_Float32ArrayValue{&pb.Float32S{Values: pbSlice(obj).Interface().([]float32)}}}
	case reflect.Float64:
	object = &pb.Object{Value: &pb.Object_Float64ArrayValue{&pb.Float64S{Values: pbSlice(obj).Interface().([]float64)}}}
	default:
	object = &pb.Object{Value: &pb.Object_ArrayValue{es.encodeArray(obj)}}
	}
	case reflect.Slice:
	if obj.IsNil() \|\| obj.Cap() == 0 {
	// Handled specially in decode; store as nil value.
	object = &pb.Object{Value: &pb.Object_RefValue{0}}
	} else {
	// Serialize a slice as the array plus length and capacity.
	object = &pb.Object{Value: &pb.Object_SliceValue{&pb.Slice{
	Capacity: uint32(obj.Cap()),
	Length: uint32(obj.Len()),
	RefValue: es.register(arrayFromSlice(obj)),
	}}}
	}
	case reflect.String:
	object = &pb.Object{Value: &pb.Object_StringValue{[]byte(obj.String())}}
	case reflect.Ptr:
	if obj.IsNil() {
	// Handled specially in decode; store as a nil value.
	object = &pb.Object{Value: &pb.Object_RefValue{0}}
	} else {
	es.push(true /* dereference */, "", nil)
	object = &pb.Object{Value: &pb.Object_RefValue{es.register(obj)}}
	es.pop()
	}
	case reflect.Interface:
	// We don't check for IsNil here, as we want to encode type
	// information. The case of the empty interface (no type, no
	// value) is handled by encodeInteface.
	object = &pb.Object{Value: &pb.Object_InterfaceValue{es.encodeInterface(obj)}}
	case reflect.Struct:
	object = &pb.Object{Value: &pb.Object_StructValue{es.encodeStruct(obj)}}
	case reflect.Map:
	if obj.IsNil() {
	// Handled specially in decode; store as a nil value.
	object = &pb.Object{Value: &pb.Object_RefValue{0}}
	} else if mapAsValue {
	// Encode the map directly.
	object = &pb.Object{Value: &pb.Object_MapValue{es.encodeMap(obj)}}
	} else {
	// Encode a reference to the map.
	//
	// Remove the map object count here to avoid double
	// counting, as this object will be counted again when
	// it gets processed later. We do not add a reference
	// count as the reference is artificial.
	es.stats.Remove(obj)
	object = &pb.Object{Value: &pb.Object_RefValue{es.register(obj)}}
	}
	default:
	panic(fmt.Errorf("unknown primitive %#v", obj.Interface()))
	}

	es.stats.Done()
	es.pop()
	return
	}

	// Serialize serializes the object state.
	//
	// This function may panic and should be run in safely().
	func (es *encodeState) Serialize(obj reflect.Value) {
	es.register(obj.Addr())

	// Pop off the list until we're done.
	for es.pending.Len() > 0 {
	e := es.pending.Front()

	// Extract the queued object.
	qo := e.Value.(queuedObject)
	es.stats.Start(qo.obj)

	es.pending.Remove(e)

	es.from = &qo.path
	o := es.encodeObject(qo.obj, true, "", nil)

	// Emit to our output stream.
	if err := es.writeObject(qo.id, o); err != nil {
	panic(err)
	}

	// Mark as done.
	es.done.PushBack(e)
	es.stats.Done()
	}

	// Write a zero-length terminal at the end; this is a sanity check
	// applied at decode time as well (see decode.go).
	if err := WriteHeader(es.w, 0, false); err != nil {
	panic(err)
	}
	}

	// WriteHeader writes a header.
	//
	// Each object written to the statefile should be prefixed with a header. In
	// order to generate statefiles that play nicely with debugging tools, raw
	// writes should be prefixed with a header with object set to false and the
	// appropriate length. This will allow tools to skip these regions.
	func WriteHeader(w io.Writer, length uint64, object bool) error {
	// The lowest-order bit encodes whether this is a valid object. This is
	// a purely internal convention, but allows the object flag to be
	// returned from ReadHeader.
	length = length << 1
	if object {
	length \|= 0x1
	}

	// Write a header.
	var hdr [32]byte
	encodedLen := binary.PutUvarint(hdr[:], length)
	for done := 0; done < encodedLen; {
	n, err := w.Write(hdr[done:encodedLen])
	done += n
	if n == 0 && err != nil {
	return err
	}
	}

	return nil
	}

	// writeObject writes an object to the stream.
	func (es encodeState) writeObject(id uint64, obj pb.Object) error {
	// Marshal the proto.
	buf, err := proto.Marshal(obj)
	if err != nil {
	return err
	}

	// Write the object header.
	if err := WriteHeader(es.w, uint64(len(buf)), true); err != nil {
	return err
	}

	// Write the object.
	for done := 0; done < len(buf); {
	n, err := es.w.Write(buf[done:])
	done += n
	if n == 0 && err != nil {
	return err
	}
	}

	return nil
	}

	// addrSetFunctions is used by addrSet.
	type addrSetFunctions struct{}

	func (addrSetFunctions) MinKey() uintptr {
	return 0
	}

	func (addrSetFunctions) MaxKey() uintptr {
	return ^uintptr(0)
	}

	func (addrSetFunctions) ClearValue(val *reflect.Value) {
	}

	func (addrSetFunctions) Merge(_ addrRange, val1 reflect.Value, _ addrRange, val2 reflect.Value) (reflect.Value, bool) {
	return val1, val1 == val2
	}

	func (addrSetFunctions) Split(_ addrRange, val reflect.Value, _ uintptr) (reflect.Value, reflect.Value) {
	return val, val
	}