| orphan: |
|---|
Contents
This proposal describes a new implementation for nominal type metadata which will enable out-of-process heap inspection, intended for use by debugging tools for detecting leaks and cycles. This implementation will subsume the existing reflection support for Mirrors, enabling out-of-process usage while also reducing generated binary size.
Radars tracking this work:
- rdar://problem/15617914
- rdar://problem/17019505
- rdar://problem/20771693
We wish to do post-mortem debugging of memory allocations in a Swift program. Debugging tools can already introspect the memory allocator to identify all live memory allocations in the program's heap.
If the compiler were to emit the necessary metadata, the layout of most allocations can be ascertained, and in particular we can identify any references inside the heap object. This metadata can be used together with the core dump of a program to build a graph of objects.
We have to be able to get all the necessary information without executing any code in the address space of the target, since it may be dead or otherwise in a funny state.
In order to identify strong retain cycles, we need to know for each reference if it is strong, weak, or unowned.
We wish to be able to opt out of metadata selectively. For secrecy, we might want to strip out field names, but keep metadata about which fields contain references. For release builds, we might want to strip out most of the field metadata altogether, except where explicitly required for code that relies on reflection for functionality.
It would be better if the new functionality subsumes some of the existing metadata, instead of adding a whole new set of structures that the compiler and runtime must keep in sync.
While this should have zero runtime overhead when not in use, it is OK if introspection requires some additional computation, especially if it can be front-loaded or memoized.
It is OK if in rare cases the metadata is not precise -- for some allocations, we might not be able to figure out the runtime type of the contained value. Also we will not attempt to verify the "roots" of the object graph by walking the stack for pointers.
There are several types of heap allocations in Swift. We mostly concern ourselves with class instances for now, but in the fullness of time we would like to have accurate metadata for all heap allocations.
These have an isa pointer that points to a class metadata record.
These also have an isa pointer, but the class metadata record has the Objective-C bit set.
These are used for heap-allocating mutable values captured in closures, for indirect enum cases, and for Error existential values. They have an identifying isa pointer and reference count, but the isa pointer is shared by all boxes and thus does not describe the heap layout of the box.
The context for a thick function is laid out like a tuple consisting of the captured values. Currently, the only aspect of the layout that is needed by the runtime is knowledge of which captured values are heap pointers. A unique isa pointer is created for each possible layout here.
Blocks are similar to contexts but have a common header and package the function pointer and captured values in a single retainable heap object.
Runtime-allocated metatypes will appear in the malloc heap. They themselves cannot contain heap references though.
These come up when a value is too large to fit inside of an existential's inline storage, for example. They do not have a header, so we will not attempt to introspect them at first -- eventually, we could identify pointers to buffers where the existential is itself inside of a heap-allocated object.
Swift already has a lot of reflective features and much of the groundwork for this exists in some form or another, but each one is lacking in at least one important respect.
The isa pointer of an object points to a metadata record. For instances of generic class types, the metadata is lazily instantiated from the generic metadata template together with the concrete types that are bound to generic parameters.
Generic type metadata is instantiated for generic classes with live instances, and for metatype records of value types which are explicitly referenced from source.
When the compiler needs to emit a generic type metadata record, it uses one of several strategies depending on the type being referenced. For concrete non-generic types, a direct call to a lazy accessor can be generated. For bound generic types T<P1, ..., Pn>, we recursively emit metadata references for the generic parameters Pn, then call the getter for the bound type T. For archetypes -- that is, generic type parameters which are free variables in the function body being compiled -- the metadata is passed in as a value, so the compiler simply emits a copy of that.
Generic type metadata tells us the size of each heap allocation, but does not by itself tell us the types of the fields or what references they contain.
The implementation of Mirrors uses runtime primitives which introspect the fields of an opaque value by looking at the NominalTypeDescriptor embedded in a type's metadata record.
For structures and classes, the NominalTypeDescriptor contains a function pointer which returns an array of field types. The function pointer points to a "field type metadata function" emitted by the compiler. This function emits metadata record references for each field type and collects them in an array. Since the isa pointer of a class instance points at an instantiated type, the field types of such a NominalTypeDescriptor are also all concrete types.
NominalTypeDescriptors record field names, in addition to types. Right now, all of this information is stored together, without any way of stripping it out. Also, NominalTypeDescriptors do not record whether a reference is strong, weak or unowned, but that would be simple to fix.
A bigger problem is that we have to call a function to lazily generate the field type metadata. While a NominalTypeDescriptor for every instantiated class type appears in a crashed process, the field types do not, because only a call to the field type function will instantiate them.
The Objective-C runtime keeps track of the types of instance variables of classes, and there is enough information here to identify pointers in instances of concrete types, however there's no support for generic types. We could have generic type metadata instantiation also clone and fill in templates for Objective-C instance variables, but this would add a runtime cost to a feature that is primarily intended for debugging.
IRGen emits some minimal amount of DWARF metadata for non-generic types, but makes no attempt to describe generic type layout to the debugger in this manner.
However, DWARF has the advantage that it can be introspected without running code, and stripped out.
The main limitation of all of the above is either an inability to reason about generic types, or the requirement to run code in the target.
Suppose T is a generic type, and S is some set of substitutions.
The compiler conceptually implements an operation G(T, S) which returns a lazily-instantiated type descriptor for the given input parameters. However, its really performing a partial evaluation G(T)(S), with the "G(T)" part happening at compile time.
Similarly, we can think of the field type access function as an operation F(T, S) which returns the types of the fields of T, with T again fixed at compile time.
What we really want here is to build an "interpreter" -- or really, a parser for a simple serialized graph -- which understands how to parse uninstantiated generic metadata, keep track of substitutions, and calculate field offsets, sizes, and locations of references.
This "interpreter" has to be able to find metadata for leaf types "from scratch", and calculate field sizes and offsets in the same way that generic type metadata instantiation calculates object sizes.
The "interpreter" will take the form of a library for understanding field type metadata records and symbolic type references. This will be a C++ library and it needs to support the following use cases:
- In-process reflection, for backing the current Mirrors in the standard library
- Out-of-process reflection, for heap debugging tools
- Out-of-process reflection, for a new remote Mirrors feature in the library (optional)
The API will be somewhat similar to Mirrors as they are in the stdlib today.
The details are described below.
Since we're operating on uninstantiated generic metadata, we need some way to describe compositions of types. Instead of using metadata record pointers, which are now insufficient, we use type references written in a mini-language.
A symbolic type reference is a recursive structure describing an arbitrary Swift AST type in terms of nominal types, generic type parameters, and compositions of them, such as tuple types.
For each AST type, we can distinguish between the minimum information we need to identify heap references therein, and the full type for reflection. The former could be retained while the latter could be stripped out in certain builds.
We already have a very similar encoding -- parameter type mangling in SIL. It would be good to re-use this encoding, but for completeness, the full format of a type reference is described below:
- A built-in type reference. Special tokens can be used to refer to various built-in types that have runtime support.
- A concrete type reference. This can either be a mangled name of a type, or a GOT offset in the target.
- A heap reference. This consists of:
- strong, weak or unowned
- (optional) a reference to the class type itself
- A bound generic type. This consists of:
- A concrete or built-in type reference
- A nested symbolic type reference for each generic parameter
- A tuple type. This consists of:
- A recursive sequence of symbolic type references.
- A function type. This consists of:
- A representation,
- (optional) input and output types
- A protocol composition type. This consists of:
- A flag indicating if any of the protocols are class-constrained, which changes the representation
- The number of non-@objc protocols in the composition
- (optional) references to all protocols in the composition
- A metatype. This consists of:
- (optional) a type reference to the instance type
- there's no required information -- a metatype is always a single pointer to a heap object which itself does not reference any other heap objects.
- An existential metatype. This consists of:
- The number of protocols in the composition.
- (optional) type references to the protocol members.
- A generic parameter. Within the field types of a generic type, references to generic parameters can appear. Generic parameters are uniquely identifiable by an index here (and once we add nested generic types, a depth).
You can visualize type references as if they are written in an S-expression format -- but in reality, it would be serialized in a compact binary form:
(tuple_type
(bound_generic_type
(concrete_type "Array")
(concrete_type "Int"))
(bound_generic_type
(builtin_type "Optional")
(generic_type_parameter_type index=0)))
We will provide a library of standalone routines for decoding, encoding and manipulating symbolic type references.
We introduce a new type of metadata, stored in its own section so that it can be stripped out, called "field type metadata". For each nominal type, we emit a record containing the following:
- the name of the nominal type,
- the number of generic parameters,
- type references, written in the mini-language above, for each of its field types.
- field names, if enabled.
Field type metadata is linked together so that it can be looked up by name, post-mortem by introspecting the core dump.
We add a new field to the NominalTypeDescriptor to store a pointer to field type metadata for this nominal type. In "new-style" NominalTypeDescriptors that contain this field, the existing field type function will point to a common field type function, defined in the runtime, which instantiates the field type metadata. This allows for backward compatibility with old code, if desired.
First, given an isa pointer in the target, we need to build the symbolic type reference by walking backwards from instantiated to uninstantiated metadata, collecting generic parameters. This operation is lazy, caching the result for each isa pointer.
enum SymbolicTypeReference {
case Concrete(String)
case BoundGeneric(String, [SymbolicTypeReference])
case Tuple([SymbolicTypeReference])
...
}
func getSymbolicTypeOfObject(_ isa: void*) -> SymbolicTypeReference
Next, we define an "instantiation" operation, which takes a completely substituted symbolic type reference, and returns a list of concrete field types and offsets.
This operation will need to recursively visit field metadata records and keep track of generic parameter substitutions in order to correctly calculate all field offsets and sizes.
The result of instantiating metadata for each given SymbolicTypeReference can be cached for faster lookup.
This library has to be careful when following any pointers in the target, to properly handle partially-initialized objects, runtime bugs that led to memory corruption, or malicious code, without crashing or exploiting the debugging tools.
enum FieldLayout {
// the field contains a heap reference
case Strong, Weak, Unowned
// the field is an opaque binary blob, contents unknown.
case Opaque
// the field is a value type -- look inside recursively.
case ValueType(indirect field: FieldDescriptor)
}
struct FieldDescriptor {
let size: UInt
let align: UInt
let offset: UInt
let layout: FieldLayout
}
func instantiateSymbolicType(_ ref: SymbolicTypeReference) -> [FieldTypeDescriptor]
Field type metadata can have circular references -- for example, consider two classes which contain optionals of each other. In order to calculate field offsets correctly, we need to break cycles when we know something is a class type, and use a work-list algorithm instead of unbounded recursion to ensure forward progress.
For enums, the field metadata record will also need to contain enough information about the spare bits and tag bits of the payload types that we can at runtime determine the case of an enum and project the payload, again without running code in the target.
This will allow us to remove a pair of value witness functions generated purely for reflection, since they don't seem to be performance-critical.
For closure contexts and blocks, it would be nice to emit metadata, too.
There are several levels of metadata we can choose to emit here:
- For code that requires runtime for functional purposes, or for the standard library in debug builds, we can have a protocol conformance or compiler flag enable unconditional emission of all metadata.
- For system frameworks, we can omit field names and replace class names with unique identifiers, but keep the type metadata to help users debug memory leaks where framework classes are retaining instances of user classes.
- For release builds, we can strip out all the metadata except where explicitly required in 1).
This probably requires putting the required metadata in a different section from the debug metadata. Perhaps field names should be separate from symbolic type references too.
Since the field type metadata instantiation only happens once per isa pointer, mirrors will not suffer a performance impact beyond the initial warm-up time. Once the field type descriptor has been constructed, reflective access of fields will proceed as before.
There might also be a marginal performance gain from removing all the field type functions from the text segment, where they're currently interspersed with other code, and replacing them with read only data containing no relocations, which won't get paged in until needed.
We may choose to implement the new metadata facility after stabilizing the ABI. In this case, we should front-load some engineering work on NominalTypeDescriptors first, to make them more amenable to future extension.
We need to carefully review the new metadata format and make sure it is flexible enough to support future language features, such as bound generic existentials, which may further complicate heap layout.
As described above, it is possible to introduce this change in a backwards-compatible manner. We keep the field type function field in the NominalTypeDescriptor, but for "new-style" records, set it to point to a common function, defined in the runtime, which parses the new metadata and returns an array of field types that can be used by old clients.
By transitioning mirrors to use the new metadata, existing tests can be used to verify behavior. Additional tests can be developed to perform various allocations and assert properties of the resulting object graph, either from in- or out-of-process.
If we go with the gradual approach where we have both field type functions and field type metadata, we can also instantiate the former and compare it against the result of invoking the latter, for all types in the system, as a means of validating the field type metadata.