[vm/ffi] Support treeshaking of FFI structs

[sjindel-google]

Update 2021-03-10: All API changes are done.

Everything except struct constructors is shaken out. Struct constructors are still retained, because the FFI trampolines creating structs (in FFI call returns, or FFI callback arguments) is not hooked up to the TFA.

Update 2021-01-05: We should make the necessary API changes introducing an Allocator interface before Flutter 2.0, the actual implementation of tree-shaking can be done later.

===============================================================================

The way FFI structs are implemented involves adding entry-point annotations to members of all generated struct classes.

This prevents any FFI structs from being tree-shaken. We should fix this.

[mkustermann]

This problem is of a more general kind: The runtime might use some members of the Dart code based on some condition. In our specific case using MyStruct as a type in the program implies we might need to access MyStruct.sizeof and MyStruct.fromPointer in the runtime (and therefore need to retain it).

One way we could do this is to support conditional entry points:

class MyStruct extends Struct<MyStruct> {
  @prama("vm:entry-point-if", EntryPointCondition.ifUsedAsType(MyStruct))
  static final field int #sizeOf = ...;

  @prama("vm:entry-point-if", EntryPointCondition.ifUsedAsType(MyStruct))
  constructor fromPointer(dynamic )
  ...
}

TFA as well as the VM's AOT compiler have a notion of a class being retained for it's type. We could build a mapping and every time a class is retained for its type we can enqueue conditional entry points.

@alexmarkov @dcharkes

[dcharkes]

Addressing #38648, together with disallowing .ref invocations on Pointer<Struct> would remove the need for a pragma on the constructor.

However, we still need it on #sizeOf. Which we can address with @mkustermann's suggestion.

We could keep the unoptimized .ref calls on Pointer<Struct> as well if we implement that solution anyway.

[alexmarkov]

@mkustermann I think it would be hard to support entry points which depend on the outcome of tree shaking due to circular nature of such entry points. We need to take entry points into account during type flow analysis, while notion of classes retained for types exists only at later tree shaking step which happens after analysis is finished.

For conditional entry points we would need to get back to analysis and probably iterate between analysis and tree shaking until reaching fixed point:

1. Entry points =>
2. Type flow analysis =>
3. Tree shaking pass 1 =>
4. Set of retained classes/types/etc =>
5. Refined set of entry points, need to go back to step 1.

---

@dcharkes Could you elaborate why we need these static #sizeOf fields at the first place? Can they be calculated at compile time and their result passed to corresponding native methods, so native methods won't need to access these fields?

If it's not possible, can we convert these static #sizeOf fields to an instance method? In such case it would be executed only if an instance of a class is created. Then, we can simply add entry point pragma on that method in base class Struct and it would be tree shaken if no instances are created, and included only for those classes which were instantiated.

At last, we can have a custom logic in NativeCodeOracle (it could be triggered by pragma annotations or it could be entirely customized). That logic would do something special to model what happens when certain native methods are detected as called by the analysis. If #sizeOf field is used by certain native methods, NativeCodeOracle could model calls to getters of #sizeOf for certain set of classes (are they passed as type arguments to those native methods?).

[dcharkes]

@alexmarkov we use it for being able to call sizeOf<T extends NativeType>(). They cannot be instance methods, because we need to know the size before we create objects. For example in allocate<T extends NativeType>() (source).

The sizeOf is mostly statically computed. The size depends on the ABI, and kernel is ABI agnostic, so it's #sizeOf => [size1, size2, size3][_abi()]; Maybe we can have a better way of passing on Map<Tuple<Type,int>,int> structSizes from the CFE to the VM. Though even if we use a different data structure, the question is also how to prune those data structures.

are they passed as type arguments to those native methods?

Yes, but sometimes generically, as in allocate<T> { sizeOf<T>() ... }.

It is also quite common that the only way objects are created in code using dart:ffi is through natives:

class Foo extends Struct { ... }

T allocateStruct<T extends Struct>(){
  Pointer<T> pointer = allocate<T>();
  T t = pointer.ref; // native entry of `.ref` manufactures an object, it calls the hidden constructor.
  return t;
}

main() {
  Foo f = allocateStruct<Foo>();
  print(f);
}

We would need to disallow generically calling .ref as suggested above, to be able to tree shake.

However, when adding structs by value (#36730) we would introduce the same problem again, because then the return type of a native function could be that struct.

Currently, already Pointer can be returned from a trampoline. So we had to prevent Pointer from being tree shaken to prevent the VM from crashing in that case.

But this seems to be a general pattern, that the FFI can create objects without the constructors in the user code.

[alexmarkov]

Can we require type argument of sizeOf<T extends NativeType>() be known at compile time? Then, we can replace sizeOf<Foo>() calls with Foo.#sizeOf in the FFI transformation, which would make reference to Foo.#sizeOf expressed in Dart code and such reference would be handled well by tree shaker without extra pragmas.

Similarly, if we can require T in allocate<T>() to be a type known at compile time, then we can replace allocate<Foo>() calls with a pattern of code which would create an instance of Foo in Dart (e.g. new Foo.#hidden), calling native method only to allocate raw memory.

Generally speaking, an ability to create instances of arbitrary classes in native methods is not working well with tree shaking. This is one of the reasons why dart:mirrors are not compatible with closed-world AOT compilation / tree shaking. To work around this, we can come up with some approximations, like "include all classes which extend Struct" (used currently), or "include all classes which extend Struct and mentioned in types in reachable code" (what @mkustermann suggested). But these are still just conservative approximations. If possible, I would suggest to avoid creation of instances of arbitrary classes in native methods.

[dcharkes]

allocate is a user-defined function. If we require the T in sizeOf<T> to be known statically, the signature would change. This would be less ergonomic.

However, it would also properly make reasoning about size orthogonal to allocating the memory.

@mkustermann and I discussed a design a while back that would separate allocation and sizing:

class FooStruct extends Struct {
  // Struct fields.

  Pointer<FooStruct> allocate(Allocator a, int count) {
    a.allocate(sizeOf<FooStruct>() * count).cast().
  }
}

In this design allocate has no type argument at all, it always returns Pointer<Void> to the amount of bytes.

[ds84182]

@dcharkes

I like the Struct.allocate approach, since it resembles C++ allocators (and somewhat resembles C++ placement new). Another good example is how Rust handles this with the Alloc trait and Layouts: https://doc.rust-lang.org/alloc/alloc/trait.Alloc.html

Essentially your API surface for allocation becomes:

// Represents how much memory to allocate, and the alignment requirements.
// Abstracts over computing things like repeating size (for arrays).
class Layout {
  final int size, alignment;
  const Layout(this.size, this.alignment);
  // Assuming alignment is a power of 2.
  // Equivalent to alloc::Layout::pad_to_align() in Rust
  int get alignedSize => (size + (alignment - 1)) & ~(alignment - 1);
  // Equivalent to alloc::Layout::repeat() in Rust
  Layout repeat(int count) => Layout(alignedSize * count, alignment);
}

abstract class Allocator {
  // Equivalent to alloc::Alloc::alloc in Rust
  Pointer<Uint8> allocate(Layout layout);
  // Equivalent to alloc::Alloc::dealloc in Rust
  void free(Pointer<Uint8> ptr, Layout layout);
}

// Specialized to a constant T.#layout if T is statically known.
Layout layoutOf<T extends Struct>() => ...;

class MyStruct extends Struct {
  // Generated static method
  Pointer<MyStruct> allocate(Allocator alloc, int count) => alloc.allocate(layoutOf<MyStruct>().repeat(count)).cast();
}

Then package:ffi can expose:

class _Malloc extends Allocator { ... }

// Can also be final
const Allocator malloc = _Malloc();

And allocation becomes:

MyStruct.allocate(malloc); // (with or without optional count)

You can also introduce the concept of global allocators, but I feel that explicit allocators are a cleaner design. There are many situations where you'd want to avoid allocating from heap (like a bump allocation scheme for temporary objects, or the stack) and having the concept of allocators in dart:ffi gives a pretty nice starting point for library authors to jump off of.

[dcharkes]

That's an excellent design. It would also work well with the Pool resource management code samples/ffi/resource_management.

We still have to refine the design to support that.

Option 1: Merge Allocator and ResourceManager

We could split up the Allocator to not have free if it's managed:

abstract class Allocator {
  // Equivalent to alloc::Alloc::alloc in Rust
  Pointer<Uint8> allocate(Layout layout);
}

abstract class UnmanagedAllocator extends Allocator {
  // Equivalent to alloc::Alloc::dealloc in Rust
  void free(Pointer<Uint8> ptr, Layout layout);
}

abstract class ManagedAllocator extends Allocator {
  // ..
}

However, this conflates allocating/freeing with resource management in the same class hierarchy. One could have a malloc Allocator, but also another one such as OPENSSL_malloc and want to use both with a Pool or with manual management. That would create 4 implementations in this situation.

Pro:

• simple
• concise

Con:

• No separation of concerns.

Option 2: Make the ResourceManager take an Allocator as argument

Alternatively, we should make the ResourceManager a separate class that takes an Allocator as argument.

Pro:

• Better separation of concerns.

Cons:

• More verbose, instantiating 2 classes.
• Should the MyStruct.allocate then take a ResourceManager as argument?

[ds84182]

I think it's perfectly fine to have a single Allocator class with allocate and free. At the end of the day, free is just a hint to the allocator that the piece of memory referenced by ptr isn't going to be used by the application anymore. If free does nothing, the application will continue to function, but it may run out of memory after a while.

For example, this bump allocation library https://crates.io/crates/bump_alloc, which does nothing on free. https://github.com/sheredom/bump_alloc/blob/master/src/lib.rs#L106

As far as Struct is concerned, it just needs something that is "layout in, pointer out". Other usages of Allocator (like a resizable vector) need a free, and maybe even a reallocate. Pool can totally extend Allocator, it just has to have an empty implementation of free.

[jonasfj]

Quick note: I've found Pool from samples/ffi/resource_management to be very useful. It might be interesting to give it a pool.move(ptr) -> ptr method that move a pointer outside the Pool.

This have been useful for me when I needed something like:

try {
  ptr = pool.allocate();
  ...;
  return pool.move(ptr); // remove ptr from pool
} finally {
  pool.releaseAll();
}

This avoid having to write } catch (_) { free(ptr); rethrow; }

[dcharkes]

As discussed in today's meeting we should separate allocation from sizeof calculation (similar to C code) for code size / tree shake reasons and performance reasons. We could use an API such as

// In "dart:ffi"
abstract class Allocator {
  Pointer<Void> allocate(int numBytes);
  void free(Pointer<Void> pointer);
}

// In "dart:ffi"
extern Pointer<T> allocate<T extends Struct>(Allocator allocator);

// In "package:ffi/ffi.dart"
class MallocAllocator extends Allocator { ... }
class ZoneAllocator extends Allocator { ... }

final malloc = MallocAllocator();

// User code:
void main() {
  Pointer<Foo> foop = allocate<Foo>(malloc);
  ...
  free<Foo>(foop, malloc);
}
// User code (lowered to kernel):
void main() {
  Pointer<Foo> foop = malloc.allocate(sizeOf<Foo>() /* <-- or rather it's lowered form */).cast<Foo>();
  ...
  malloc.free(foop.cast<Void>());
}

So we'll

• Make CL to demonstrate these changes
• Make breaking change request with this information and motivation for it (treeshake-ability, performance)
• Discuss API in next meeting
• Possible make old API deprecated before Flutter 2.0 / FFI 1.0

Originally posted by @mkustermann in #44454 (comment)

[ds84182]

It's also useful to pass alignment into the allocator. Right now, if you want to write a proper bump pointer allocator, small types (for ex, Uint8) will have size overhead of the largest supported type alignment (8 bytes). Additionally a type like Float32x4 or Int32x4 would have different alignment requirements due to SIMD loads and stores.

[dcharkes]

It's also useful to pass alignment into the allocator. Right now, if you want to write a proper bump pointer allocator, small types (for ex, Uint8) will have size overhead of the largest supported type alignment (8 bytes). Additionally a type like Float32x4 or Int32x4 would have different alignment requirements due to SIMD loads and stores.

Then we would 'invoke' both sizeOf<T>() and alignmentOf<T>() (the latter one we still have to introduce #39964) in allocate.

If we would omit an alignment argument now, we would break all existing subtypes of Allocator later when we introduce it. So we should add it to the API.

[mkustermann]

To make this forwards compatible, we might want to make the Allocator class take the alignment:

abstract class Allocator {
  Pointer<Void> allocate(int numBytes, int alignment);
  void free(Pointer<Void> pointer);
}

[dcharkes]

Landing the breaking change (#44621) is part of the milestone, not this. Removing milestone.

[dcharkes]

Update: Everything except struct constructors is shaken out. Struct constructors are still retained, because the FFI trampolines creating structs (in FFI call returns, or FFI callback arguments) is not hooked up to the TFA yet.

[a-siva]

Per discussion in the VM sync meeting this morning this last piece is not critical for the March milestone and hence removing the milestone tag.