Ephemerons

[Peter Levart]

Hi Mandy,

Thanks for noticing this post. I think Ephemerons would be a nice tool 
that would solve some "memory leak" problems people have when using data 
structures with weak references.

On 01/20/2016 05:20 PM, Mandy Chung wrote:
> Hi Peter,
>
> This is interesting and useful for cases when key/value in a reference chain cycle.  This seems worth exploring for a future release.  I don’t have any cycle to study this in depth and begin any discussion unfortunately at this time.
>
> Have you tried prototype Ephemerons with WeakReference for the key and PhantomReference for the value?  Would that satisfy your cases - it would not work if SoftReference is part of the chain - just wondering if you have explored that?

I don't know exactly what you mean by that. I think there's no way to 
"simulate" the semantics of Ephemeron with any combination of existing 
Reference types, because the reachabilities of their referents are 
defined to be unconditional, if that was what you were asking. If you 
are just referring to the desired "reachability" of the Ephemeron's key 
and value, then let me explain a bit about it...

1st, the phantom-reachability of the Ephemeron's value wouldn't have 
much sense, because then the Ephemeron's value would have to be 
unretrievable (like PhantomReference's referent) in order to preserve 
the semantics of existing PhantomReferences which guarantee that once a 
referent becomes phantom-reachable, it can never be made more strongly 
reachable again. The whole point of Ephemeron is it's ability to 
retrieve the value until it has been cleared.

Ephemeron's key can be compared with any existing Java Reference's 
referent. When it becomes xxx-reachable, GC will clear the XxxReference 
atomically with all other XxxReferences of the same type that refer to 
the same referent. The strength of xxx-reachability determines when that 
happens relative to YyyReference(s) of other types when they refer to 
the same referent. For example:

Object referent = new Object() {
   protected void finalize() {
     System.out.println("finalized");
   }
};
SoftReference<Object> softRef = new SoftReference<>(referent);
WeakReference<Object> weakRef = new WeakReference<>(referent);
PhantomReference<Object> phantomRef = new PhantomReference<>(referent);
referent = null;

...

In above example, phantomRef will never be cleared before finalize() is 
called and filalize() will never be called before weakRef is cleared and 
weakRef will never be cleared before softRef.

In my prototyle, Ephemeron's key behaves as though there was a 5th 
strength positioned between WeakReference and finalization 
(FinalReference). Ephemeron could be specified to have exactly the same 
strength for it's key as WeakReference has for it's referent, for 
example, but I choose to introduce another strength so that Ephemeron 
can not influence classical WeakReference behaviour - and it's also 
easier to explain the behavior that way and reason about it. So for the 
purpose of this prototype, an Object is defined to be 
ephemeraly-reachable if it is neither weakly, softly nor strongly 
reachable but can be reached through the Ephemeron by following it's key 
(or sometimes also the value as we'll see later).

The "weak" reachabilities table, from the strongest to the weakest:

softly-reachable
weakly-reachable
ephemeraly-reachable
final-reachable (finalizable)
phantom-reachable

Unlike the Ephemeron's key, it's value is something that can't be 
compared with the referents of existing Reference types. It's 
reachability is "conditional". As with all definitions that contain 
recursion, one has to be careful to not construct a paradox. The 
prototype defines the reachability of Ephemeron's value as:

- an object is ephemerally-reachable if it is neither weakly, softly nor 
strongly reachable, but can be reached through the Ephemeron by 
following it's value while the Ephemeron's key is at most 
ephemeraly-reachable
- an object is weakly-reachable if it is neither softly nor strongly 
reachable, but can be reached through the Ephemeron by following it's 
value while the Ephemeron's key is at least weakly-reachable

The value's reachability is therefore dependent on the key's 
reachability. The above definition is sound because there's no paradox 
when other definitions of reachabilities are taken into account. Here's 
the complete definition of all reachabilities for the prototype:

  * <li> An object is <em>strongly reachable</em> if it can be reached
  * by some thread without traversing any reference objects.  A
  * newly-created object is strongly reachable by the thread that
  * created it.

  * <li> An object is <em>softly reachable</em> if it is not strongly
  * reachable but can be reached by traversing a soft reference.

  * <li> An object is <em>weakly reachable</em> if it is neither
  * strongly nor softly reachable but can be reached by traversing a
  * weak reference or by traversing an ephemeron through it's value while
  * the ephemeron's key is at least weakly reachable.

  * <li> An object is <em>ephemerally reachable</em> if it is neither
  * strongly, softly nor weakly reachable but can be reached by 
traversing an
  * ephemeron through it's key or by traversing an ephemeron through 
it's value
  * while it's key is at most ephemerally reachable. When the ephemerons 
that
  * refer to ephemerally reachable key object are cleared, the key 
object becomes
  * eligible for finalization.

  * <li> An object is <em>phantom reachable</em> if it is neither
  * strongly, softly, weakly nor ephemerally reachable, it has been 
finalized,
  * and some phantom reference refers to it.

  * <li> Finally, an object is <em>unreachable</em>, and therefore
  * eligible for reclamation, when it is not reachable in any of the
  * above ways.

In General, if an object can only be reached through the Epehemron by 
traversing the value, it can never be defined to be more strongly 
reachable than the Ephemeron's key at the same time, because a value can 
refer to the key. So a possible alternative to the prototype would be 
for Ephemeron's value to follow exactly the reachability of Ephemeron's 
key until the Ephemeron gets cleared because it's key reaches certain 
level of reachability.

As one might have noticed, the algorithm to process Ephemerons is 
iterative, with complexity O(n*(d+1)) where "n" is the number of 
discovered Ephemerons and "d" is the maximum number of "hops" in object 
graph where a "hop" is defined as a point in chain where the value of 
some ephemeron refers directly or indirectly to the key of some other 
ephemeron and the value if that other ephemeron continues the chain. In 
practical data structures, d is rarely > 1 and mostly very low. The 
algorithm in the prototype also reduces the number of outer iterations 
to less than 'd' in many situations.

In the prototype where the reachability of the value has an upper bound 
(weakly-reachable), "n" can be reduced to the number of discovered 
Ephemerons. If the reachability of value followed exactly the 
reachability of key, then "n" would have to count the number of 
discovered Ephemerons + WeakReferences + SoftReferences together. Such 
implementation is therefore possible, but has a cost.

Regards, Peter

> Mandy
>
>> On Jan 17, 2016, at 10:18 AM, Peter Levart<peter.levart at gmail.com>  wrote:
>>
>> 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 refe
>> rence 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.
>>