Ephemerons

[Peter Levart]

Hi,

Ephemerons are special kind of references described by Barry Hayes [1]. 
In the simple variant, they contain two "referents". One is called the 
key, which can be viewed as a "weak" referent in the style of Java 
reference types (SoftReference, WeakReference, PhantomReference), the 
other is called the value, which is also treated specially by GC. It's 
reachability is dependent on the reachability of the key.

Ephemerons solve the problem seen for example in the 
java.util.WeakHashMap when a value in this map directly or indirectly 
refers to it's key. Such entry will never be purged as the value is 
always reachable from the WeakHashMap instance and through the value, 
it's key is reachable too. There are other places where Ephemerons could 
be used - for example in ClassValue API. Try googling for "java 
ephemeron" (without quotes) to find out other situations where 
Ephemerons would be beneficial.

If one was to implement Ephemerons in Java, the main question he would 
be asking is how Ephemeron(s) were supposed to interact with existing 
Java reference types. Hayes only defines their behavior in isolation, 
but Java already has 4 "weak" reference types with different 
"strengths": SoftReference, WeakReference, FinalReference (for 
implementing finalization) and PhantomReference. In the prototype I 
choose to define Ephemerons as a new reference type with it's own 
"strength" for the key referent positioned between WeakReference and 
FinalReference. It would be possible to merge it with an existing 
reference type like WeakReference or position it between SoftReference 
and WeakReference or even entirely "on the top" of the strength list, 
but I think it would not be wise to position it below FinalReference or 
even PhantomReference. What's best is an open question. What is also not 
so obvious is how to define the reachability of the Ephemeron's value 
and it's interaction with existing reference types. I think I defined it 
soundly (see the reachability types in the javadoc of [4]). The reason 
for defining the reachability of the value to alternate between 
ephemeraly-reachable and weakly-reachable and not between 
ephemeraly-reachable and strongly-reachable, while theoretically 
possible, is the desire to have a separate phase of processing for each 
reachability strength, like it is done currently, and which doesn't 
affect the performance of processing of existing reference types.

Having skimmed through the reference processing code in the VM for a 
couple of times, I thought it should not be too complicated to implement 
another type of "weak" reference. Encouraged by how little changes were 
needed to remove the sun.misc.Cleaner special type of reference [2], I 
began experimenting and came up with a prototype that seems to work [3]. 
Luckily most of the logic to process Reference objects in VM is 
encapsulated in the ReferenceProcessor class and this logic is invoked 
from various GC implementations of the hotspot. Changes needed are 
therefore mostly localized to this class. The webrev also contains 
recent changes from JDK-8143847 [2] that have not yet propagated to the 
jdk9-dev repo. When they do, I will prepare a rebased webrev without 
those changes.

I'm publishing this prototype here to get the answer to the main 
question: Is there an interest to have Ephemeron reference type in Java?

Given that there was interest, I would also like to initiate a 
discussion about:
- What would be the most appropriate "strength" of reachabillity for 
Epehmeron referents (key and value) and the desired interactions with 
existing reachabilities.
- The prototype itself. Since I'm new to this part of code (that's my 
1st not so shallow dive into the VM), I surely must have missed places 
that should be changed. Although the prototype seems to work, I have not 
created extensive tests for the functionality and have not exposed it to 
all the various GC algorithms and situations yet. I could use some 
advise on how to exercise all GC algorithm combinations possible in the 
VM (what flags to use, for example).

Regards, Peter

[1] 
https://static.aminer.org/pdf/PDF/000/522/273/ephemerons_a_new_finalization_mechanism.pdf
[2] https://bugs.openjdk.java.net/browse/JDK-8143847
[3] http://cr.openjdk.java.net/~plevart/misc/Ephemeron/
[4] 
http://cr.openjdk.java.net/~plevart/misc/Ephemeron/webrev.jdk.01/src/java.base/share/classes/java/lang/ref/Ephemeron.java.html

P.S.

To wet some appetite, with the above prototype (applied to current 
jdk9-dev), it is possible to run the following example:

import java.lang.ref.Ephemeron;
import java.util.ArrayList;
import java.util.List;

public class EphemeronTest {

     static class Key {
         final int i;

         Key(int i) {
             this.i = i;
         }

         @Override
         public String toString() {
             return "k" + i;
         }
     }

     static class Value {
         final Key key;

         Value(Key key) {
             this.key = key;
         }

         @Override
         public String toString() {
             return "v(" + key + ")";
         }
     }

     static class Eph extends Ephemeron<Key, Value> {
         public Eph(Key key, Value value) {
             super(key, value);
         }

         @Override
         public String toString() {
             return getKey() + "=" + getValue();
         }
     }

     static void test(int size, boolean forwardChaining) throws Exception {
         System.out.println();
         System.out.println((forwardChaining ? "Forward" : "Backward") +
                            " chaining of value->key ...");
         System.out.println();
         List<Eph> ephs = new ArrayList<>(size);

         Key k1 = new Key(1);
         {
             Key kp = k1;
             for (int i = 2; i <= size; i++) {
                 Key ki = new Key(i);
                 ephs.add(
                     forwardChaining
                     ? new Eph(kp, new Value(ki))
                     : new Eph(ki, new Value(kp))
                 );
                 kp = ki;
             }
             ephs.add(
                 forwardChaining
                 ? new Eph(kp, new Value(k1))
                 : new Eph(k1, new Value(kp))
             );
             kp = null;
         }

         System.gc();
         System.out.println("1: " + ephs);
         k1.getClass(); // reachabilityFence

         k1 = null;
         System.gc();
         System.out.println("2: " + ephs);
     }

     public static void main(String[] args) throws Exception {

         int size = (args.length < 1)
                    ? 5
                    : Math.max(2, Integer.parseInt(args[0]));

         test(size, true);
         test(size, false);
     }
}


Which prints:

Forward chaining of value->key ...

1: [k1=v(k2), k2=v(k3), k3=v(k4), k4=v(k5), k5=v(k1)]
2: [null=null, null=null, null=null, null=null, null=null]

Backward chaining of value->key ...

1: [k2=v(k1), k3=v(k2), k4=v(k3), k5=v(k4), k1=v(k5)]
2: [null=null, null=null, null=null, null=null, null=null]


If you compile the JDK with --enable-debug and use the following VM 
switches when running: -XX:+PrintGCDetails -XX:+TraceReferenceGC, you 
can also observe the inner workings of the reference processing, 
including Ephemerons.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/hotspot-gc-dev/attachments/20160117/44e97316/attachment.htm>