Does GC guarantee that cleared References are enqueued to ReferenceQueue in topological order?

Question

Say there are two objects, A and B, and there is a pointer A.x --> B, and we create, say, WeakReferences to both A and B, with an associated ReferenceQueue.

Assume that both A and B become unreachable. Intuitively B cannot be considered unreachable before A is. In such a case, do we somehow get a guarantee that the respective references will be enqueued in the intuitive (topological when there are no cycles) order in the ReferenceQueue? I.e. ref(A) before ref(B). I don't know - what if the GC marked a bunch of objects as unreachable, and then enqueued them in no particular order?

I was reviewing Finalizer.java of guava, seeing this snippet:

private void cleanUp(Reference<?> reference) throws ShutDown {
  ...
  if (reference == frqReference) {
    /*
     * The client no longer has a reference to the
     * FinalizableReferenceQueue. We can stop.
     */
    throw new ShutDown();
  }

frqReference is a PhantomReference to the used ReferenceQueue, so if this is GC'ed, no Finalizable{Weak, Soft, Phantom}References can be alive, since they reference the queue. So they have to be GC'ed before the queue itself can be GC'ed - but still, do we get the guarantee that these references will be enqueued to the ReferenceQueue at the order they get "garbage collected" (as if they get GC'ed one by one)? The code implies that there is some kind of guarantee, otherwise unprocessed references could theoretically remain in the queue.

Thanks

Answer 1

There is no ordering guarantee. In the case of Finalizer.java, the thread can be shut down before all references are processed. See the docs for FinalizableReferenceQueue:

• Keep a strong reference to this object until all of the associated

• referents have been finalized. If this object is garbage collected earlier,
• the backing thread will not invoke {@code finalizeReferent()} on the
• remaining references.

This is intentional behavior. For example, we use FRQ to clean up map entries when references to the keys and/or values are cleared. If the user no longer has a reference to the map, and in turn no longer has a reference to the FRQ, there's no point in processing those references.

Answer 2

I'm pretty sure that the answer is no.

The JVM spec says this about finalizer methods:

The Java virtual machine imposes no ordering on finalize method calls. Finalizers may be called in any order or even concurrently. (JVM spec 2.17.7)

From this I infer that there are no guarantees that references are queued in topological order.

Answer 3

I think there is no such guarantee. The GC itself does not have a complete and immediate view of the RAM (it cannot, since the GC runs on the CPU which can only look at a few bytes at a time). In your example, assuming a basic "mark & sweep" GC, chances are that A and B will be declared unreachable in the same mark phase, and swept together in no particular order. Maintaining topological order would probably be expensive.

As for Finalizer, it seems that it is meant to be used through a FinalizableReferenceQueue instance only, which does some classloader-related magic. The Finalizer uses its own facilities to detect when the FinalizableReferenceQueue from which it functionally depends becomes itself unreachable; this is the point when the thread which runs Finalizer knows that it should exit. From what I understand, if the application lets the GC reclaim the FRQ, then the finalizer thread will exit, and any references enqueued "after" the FRQ reference will not be processed. This depends on topological order or lack thereof, but I cannot decide whether this is a problem or not. I think that the application is not supposed to drop its FRQ as long as processing of reclaimed referenced objects is important.