android-gc.md

Java GC bridge in .NET

Both Java and .NET are garbage collected languages. For interop scenarios between the two runtimes we need to take care of the proper garbage collection across both runtime and the interop boundary.

In the following document we will describe how the current GC bridging works on MonoVM / .NET Android, explore the potential problems, alternative solutions, and lightly touch on what would be necessary in order to bring the functionality to CoreCLR / NativeAOT runtimes.

Introduction

Problem statement

Both Java and .NET runtimes come with a garbage collector. Each of these runtimes has its own garbage collector that cannot inspect object graphs beyond the runtime foreign-function interface (FFI) boundaries.

Much like other interop scenarios, like COM or Objective-C, there are proxy objects where one object instance in .NET runtime mirrors and object instance in the Java world. Conceptually it's similar to the runtime-callable and COM callable wrappers in COM. In the rest of the document we will use the term "proxy object" to refer to object A' which is logical counterpart of object A in the other runtime. This draft also uses the term "bridge object" specifically to any .NET object which is a proxy of Java object.

We want to ensure that proxy object instances have the same observable lifetime as their counterparts in the other runtime, or in other words that if object A is not collected in one runtime then its proxy A' also needs to remain alive.

We expect to make no modification to the the Java GC. There are multiple Java runtime implementations which also ship multiple implementation of garbage collectors. We can rely only on the public API surface, specifically the Java Native Interface (JNI) handles which can keep either strong or weak reference to a Java object.

Problematic patterns, such as cycles crossing the runtime boundary or the zig-zag pattern (see examples below) need to be handled.

Example object graphs

In this section we establish several scenarios that will later be referenced in other sections.

Basic scenario

The simplest scenario is one without a cycle with just one crossing of the runtime boundary. For example, we may instantiate a Button object in the Java world, its .NET counterpart ButtonProxy. The object graph can be rooted by either runtime or both.

graph LR
    subgraph Dotnet[".NET Heap"]
        ButtonProxy
    end
    subgraph Java["Java Heap"]
        Button
    end
    ButtonProxy --> Button

Loading

Cycle

We extend the previous scenario with a callback object using an observer pattern common in the Java world. The observer object once again lives in both runtimes. In order to demonstrate a cycle we say that the .NET developer decided to keep a strong reference to the button in the observer object.

graph LR
    subgraph Dotnet[".NET Heap"]
        ButtonProxy
        ButtonCallback
    end
    subgraph Java["Java Heap"]
        Button
        ButtonCallbackProxy
    end
    ButtonProxy --> Button
    ButtonCallbackProxy --> ButtonCallback
    Button --> ButtonCallbackProxy
    ButtonCallback --> ButtonProxy

Loading

Zig-zag

Another common pattern is when the object graph crosses the runtime boundary more than once. In the example below, rooting object ButtonProxy will root object A, B, and C even though there's no direct reference linking them in the .NET heap. Likewise, the object CProxy on the Java side doesn't have a reference on the Java heap either, yet it needs to be kept alive.

graph LR
    subgraph Dotnet[".NET Heap"]
        ButtonProxy
        ButtonCallback
        A
        B
        C
    end
    subgraph Java["Java Heap"]
        Button
        ButtonCallbackProxy
        CProxy
    end
    ButtonProxy --> Button
    ButtonCallbackProxy --> ButtonCallback
    Button --> ButtonCallbackProxy
    ButtonCallback --> A
    ButtonCallback --> B
    ButtonCallback --> C
    C --> CProxy

Loading

Solutions

Given the restriction that the Java GC cannot be modified there are only two widely implemented algorithms to solve the problem.

A prerequisite to understanding the options is how the Java interop is implemented on the .NET side. Each proxy object on the .NET side holds a JNI handle to the Java object. The handle can be weak or strong and we can switch between these two. We can also invoke the System.gc() method on the Java side (analogous to System.GC.Collect() in .NET).

For example, we can check whether a Java object is alive by changing the JNI reference to a weak one, invoking Java garbage collection, and then checking whether the reference is still pointing to an object.

Reference counting

This is very similar to how the Objective-C and COM interop operates and it's recommended to read the Objective-C interoperability design document to refresh on the principles.

Let's explain the basic idea:

• Any proxy object that is alive on the .NET heap will hold a strong JNI reference to the Java counterpart so it doesn't get collected. If the object is dead on .NET heap or referenced only by weak references we use weak JNI reference.
• We treat every proxy object on the .NET side as having external reference counting by creating the RefCounted GCHandle for it. The .NET garbage collector then asks for every object (or rather the GCHandle) it finds "dead" if there's an external reference to it.
  • If the bridge object has strong JNI handle, we cannot answer this right away. We can change the JNI handle from strong to weak and say conservatively that the object is alive on the Java heap.
  • If the JNI handle is already weak, we can ask if the JNI reference is still valid and pass the answer back to the .NET GC. The .NET GC will either keep the object alive or prepare it to be finalized.
• We need to ensure that any FFI call from Java to .NET which looks up the .NET object instance changes the JNI handle to strong one.
• Care needs to be taken to handle .NET WeakReferences pointing to Java proxy objects. We'd need to ensure that resolving WeakReference.Target changes the JNI handle to strong.
• The Java GC can be run asynchronously at any point. We can trigger it for every .NET GC.

Pros:

• Incremental
• Asynchronous
• Easy to implement with no changes to CoreCLR GC

Cons:

• Cannot collect cross-runtime cycles (!)
• Collecting zig-zag pattern requires GC cycle of each runtime for each reference crossing the FFI boundary

Additional notes:

• The problem with cycles and zig-zag patern are well known. Both of them affect iOS interop and there's prior art in manually solving them with analyzers and careful use of WeakReferences to break the cycles.

Refgraph GC

This is the algorithm implemented by the MonoVM GC bridge. The term Refgraph GC was coined by a 2023 paper Collecting cyclic garbage across foreign function interfaces. While the MonoVM implementation predates the research paper by more than a decade it was never formally specified or documented.

High-level overview:

• At the end of the GC marking phase, construct a list of marked bridge objects.
• Construct a reachability graph from the list of bridge objects.
• Tell the Java peers about edges from the .NET side and mirror the relationships on the Java side.
• Switch all bridged objects from holding a JNI strong reference to the Java proxy to weak references.
• Run Java GC.
• Check which objects survived the Java GC and turn them back to strong JNI references and mark them as non-collected. Mark the rest as collectible.

Cons:

• Object held only by the Java reference will always participate in the marked list for every GC.
• Constructing the reachability graph introduces additional stage during GC which may be expensive.
• Java GC cannot collect stale references from .NET side because they are held by strong JNI refs.

Pros:

• Handles cycles split across the Java and .NET heaps.
• Can collect large object graphs crossing the Java/.NET boundary in one go.

The compressed reference graph (or forest, technically) needs to be produced efficiently. The current algorithm uses Tarjan SCC algorithm to traverse the reachable objects starting at the dead bridge objects. We can stop the recursive algorithm once any marked object is reach since those are guaranteed to be held by strong JNI handle on the Java side and don't need to be included. Post-processing then transforms the graph to eliminate edges that go through non-bridge objects. However, and this is important, it doesn't necessarily elimiate ALL non-bridge objects from the graph. For example, if bridge objects bA and bB point to array C[N] which in turn points has each element pointing to a bridge object bD[n] then object C does NOT get eliminated from the graph for sufficiently large N. If it were eliminated then we would need 2 * N edges. We only need 2 + N edges if it stays. Inclusion of the non-bridge objects in the compressed reference graph means the Java introp has to represent them by a placeholder on the Java side, typically an ArrayList<object> instance.

Implementation

MonoVM and Sgen

TODO: Describe the current interface of sgen_client_bridge_*, how it ties to SGen, and how it's exposed for Java.Interop through mono_gc_register_bridge_callbacks/mono_gc_wait_for_bridge_processing.

Experiment: Hacking sgen-tarjan-bridge to run on NativeAOT / CoreCLR GC

Marking bridge objects

In order to efficiently recognize bridge objects, we can employ the same strategy as the Objective-C interop and introduce an attribute that marks the bridge object. The expectation is that this attibute will be placed on Java.Interop.JavaObject and Java.Interop.JavaException. It's also expected that any of the objects with this new attribute have a finalizer.

This allows efficiently marking the objects with a flag in the method table. For NativeAOT it's done at compile time, for CoreCLR during the runtime method table construction. For the hack I used IsJavaPeerableFlag = 0x800 in extended flags. This is a prominent place that's still free but extremely fast to access.

Handles vs. finalization queue

We have generally two ways to track the list of bridge objects. We can either create GCHandles for them, or rely solely on their presence in the finalization queue.

Neither of those approaches currently provides the right abstraction in the CoreCLR GC in terms of callbacks in the GCtoEE interface. For GCHandles we can get early callbacks that would allow us to get list of "dead" bridge objects that we can process it in the DFS pass. Such pass would then run in the AfterGcScanRoots callback and it would once again need to recheck the list to see if the object are still dead since other handles (or objects references by those handles) can mark them alive. Also, we don't have an interface to call Promote on these objects afterwards. That will eventually happen later when the finalization queue is processed but that poses a different problem for WeakReferences. More on that below.

Using the finalization queue is possible but it may need an extra ScanForFinalization-like pass (see below). We would also need to handle bridge object resurrection while processing the finalization queue, eg. in RhpGetNextFinalizableObject. Bridge objects that are currently resurrected for processing through cross_references should not get their finalizer called and we would need to call RegisterForFinalization on them to make sure they participate in the next GC cycle.

Additional things to consider: GCHandle allows us to track objects across compaction. This may be useful property for storing the compressed reference graph between its creation and the processing in cross_references. The Jave.Interop needs to keep a weak dictionary for mapping Java object handles/identities back to .NET objects. Maybe the GCHandles would be reusable for that purpose? Lastly, it could also help with the distincion of unreferenced objects that are still participating in the GC bridge processing and those that were already deemed dead by cross_references. We can say that only the objects with live GCHandle are participating in the briding, while for dead objects we can call GCHandle.Free and let the regular finalization proceed.

Stop the world

In the stop-the-world phase we need to detect non-promoted bridge objects on the finalization queue. We place those objects on a list and then process them with DFS pass to generate strongly connected components (SCC) using the Tarjan algorithm, and at the same time produce the edges of the compressed object graph. After the compressed graph is produced we need to mark the whole object graph reachable from the finalized objects as promoted so its alive until Java GC is complete and we can determine the real liveness of the objects.

There are several key observations:

• Walking the finalization queue is already implemented in CoreCLR GC, and the promotion of the objects on the finalization queue is also part of the standard processing. Unfortunately, we don't get a callback between these two stages here. The DFS pass needs to run while the bridge object graph is still not marked so we can accurately traverse only the dead part of the object graph that is reachable from the bridge objects and that needs to be mirrored on the Java GC side. Another issue with running the bridge object processing in the current CFinalize::ScanForFinalization pass is that it runs after the short weak references were already set to point to null. We would either need to make another pass earlier, or special case GCScan::GcShortWeakPtrScan to understand that bridge objects.
• The implementation of the DFS pass in processing_stw_step needs to store additional data for each traversed node. In order to do so efficiently it relies on implementation details of the object layout to mark objects as "visited" and to attach an auxiliary data structure to the visited nodes. On MonoVM this works by overriding the method table pointer with a sentinel value and overriding the lock word with pointer to the auxilary data. Both of these values are restored at the end of the DFS pass. While it's safe to modify the object headers at this point because the world is stopped and they are non-promoted on the .NET side it makes the implementation fragile and not easily portable. CoreCLR requires the method table pointer to be untouched for the duration of the DFS walk in order to check type-specific flags. Toughts on solving the issue:
  • GC_MARKED, bit 1 in method table pointer, is guaranteed not to be set for the dead part of graph we are inspecting. We cannot use it at the sole marker for visited nodes because it's also set for the marked nodes in the graph where we need to stop the DFS pass. However, if we stored the pointers to auxiliary data in a hash table on the side, then GC_MARKED could be used together with the hash table lookup. Visited nodes would get GC_MARKED set and an entry in the hash table. Live objects would have just the GC_MARKED bit set.
  • Bit BIT_SBLK_UNUSED in the lock word is also currently unused. For the hacked prototype I used a scheme where BIT_SBLK_UNUSED is used to mark a visited node and the rest of the lock word is used to store the auxiliary data pointer. Since the pointer is guaranteed to be aligned I can abuse the bottom bit to store the value at the BIT_SBLK_UNUSED marker bit. That way all the information can be compressed inside the lock word which is otherwise unused by the DFS pass.
• A tighter integration of the GC code could allow merging the DFS pass with the marking pass.

For the purpose of a quick hack, we used DiagWalkObject2 to traverse the bridge object graph in DFS fashion. That seems to work just fine at this stage.

The compressed object graph we produce in the STW step is currently represented by pointers to objects and their relative edges. Storing pointers to objects is problematic since the compacting GC can later relocate them and we would need to account for that. Thought: We are transferring the compressed object graph to the Java side, so what we really need by that point are the JNI handles. It may be worth exploring whether we really need to keep the .NET object pointers or whether we want to store somethine more immutable.

Async processing

NOTE: Consistency of the compressed object graph is guaranteed by the Java interop stopping the threads with mono_gc_wait_for_bridge_processing barrier. Resurrection of Java object via FFI call from Java to .NET employs this barrier to stop the thread from introducing any changes to the compressed object graph until the Java GC processing is finished.

Open questions

• What about concurrent GCs and other type of GCs not present in MonoVM? Side note: COM/Objective-C interop objects don't participate in the concurrent GCs. Perhaps it's fine to just say the bridge objects don't participate either. They should be held be the finalization queue so they are not going to be collected. There may be potential issue with compaction and parallel run of the cross_references callback.

• What happens if another GC starts while the previous cross_references processing didn't finish yet? Presumably we can pretend that all bridge objects survived and prevent the mono_gc_wait_for_bridge_processing barrier from being signalled. The async processing should finish at some point and all the threads calling into Java.Interop would be kept stopped so they cannot be resurrecting objects. Another option is to simply block the GC until the previous processing is done.

• Do we want to allow implementations of cross_references in managed code? It's tempting to allow that but we need to be aware that there's still a possibility of stop-the-world event from GC or event tracing. This is not necessarily problematic but it may introduce some extra delays. On CoreCLR it may be tricky to ensure that the callback is pre-JITed and there's no prior art like RestrictedCallouts in NativeAOT.

Java.Interop and MonoVM API usage

One particular thing about the current implementation of the java-interop native code is that it relies on certain Mono embedding APIs, such as mono_class_from_mono_type, mono_class_get_field_from_name, mono_object_get_class, mono_class_is_subclass_of, mono_field_get_value and mono_field_set_value. The reason is that there are two bridagable types - JavaObject and JavaException. Additionally, in Android, there are two more - Java.Lang.Object and Java.Lang.Throwable. All of them can have subclasses and all of them have attached bridge data (handle, handle_type, and refs_added). For each bridge object passed in the cross_references callback it determines the root bridge type, hence mono_object_get_class and mono_class_is_subclass_of. It then accesses the respective fields on the base type.

We can split this into two individual problems. Firstly, we can wrap all the necessary bridge data in a structure with fixed layout, share the layout between managed and native code, and make sure that the same structure is used by any interop object. Secondly, we need to find a location of this bridge data within a specific object (the relative offset of the data is different between JavaObject and JavaException because JavaException inherits from Exception).

Thoughts: We can just walk up the class inheritance until the topmost bridge object and pass that to information to the Java.Interop. The interop could then compare that to its known 2/4 method tables / RuntimeTypeHandles and keep its own field offset mapping. The mapping can be constructed in the managed part of the code by existing Unsafe or reflection API.