RFR[S] 8210289 ArchivedKlassSubGraphInfoRecord is incomplete

[Jiangli Zhou]

> On Sep 1, 2018, at 7:25 PM, Jiangli Zhou <jiangli.zhou at oracle.com> wrote:
> 
> Hi Ioi,
> 
> Thanks for finding the bug. To address the incomplete class list issue, the original algorithm can be augmented while remaining as an O(N) solution.
> 
> As each node (object) in an archived subgraph is a root of a sub-subgraph, the class-initialization-list associated with a specific node (within an existing archived sub-graph) is also a sub-list of the enclosing sub-graph's class-initialization-list. For example,
> 
> Sub-graph1:
> 
>             O1(k1)
>           /         \
>     O2(k2)       O5(k5)
>     /       \
> O3(k3)   O4(k4)
> 
> 
> Klass-init-list: K1, K2, K3, K4, K5
> 
> 
> Sub-graph2:
> 
>     O2(k2)
>     /       \
> O3(k3)   O4(k4)
> 
> Klass-init-list: K2, K3, K4
> 
> During the sub-graph walking and archiving process for sub-graph2, if O2 has been previously archived in another sub-graph, we can find the other sub-graph's class list and take the sub-list starting from the klass (k2), without re-walking each nodes again. To do that, we only need to walk the existing recorded class-initialization-list. If K2 is found in any of the existing list, we can take the sub-list starting from K2 and append the list to the current one.
> 
> With the approach, K5 would also be included if O5 is walked after O2 in sub-graph1. However, O5 is not part of O2's sub-graph. So that would introduce overhead at runtime. To avoid such problem, we can remember the sub-graph level (which is already built as part of the existing graph walking algorithm) for each K in the class-initialization-list. The ending indication of the sub-list would be the first K with the same level as the starting K. So we would have:
> 
>    K1(1), K2(2), K3(3), K4(4), K5(2)
> 
> The K2 level is 2, the sub-list would end before K2 who's level is 2.

Typo. The second K2 above should be k5:

The K2 level is 2, the sub-list would end before K5, who's level is 2.

Thanks,
Jiangli 


> This part is not currently implemented yet but is not difficult to add.
> 
> Thanks,
> 
> Jiangli
> 
> 
>> On 9/1/18 6:08 PM, Ioi Lam wrote:
>> https://bugs.openjdk.java.net/browse/JDK-8210289
>> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v01/ 
>> 
>> Description
>> ===========
>> 
>> I found this bug while trying to merge my code for CDS support of Lambda
>> classes (JDK-8198698).
>> 
>> When heapShared.cpp dumps a sub-graph of heap objects, it attempts to
>> record all the classes of all the objects that are referenced by
>> this sub-graph. However, if one of these objects have already been visited
>> while a previous sub-graph was dumped, then this object's class is not
>> recorded in the current sub-graph.
>> 
>> At runtime, if the current sub-graph is restored before any other
>> sub-graphs, we will end up with a live object in the Java heap with
>> an uninitialized class.
>> 
>> Fix
>> ===
>> 
>> Now I create the sub-graph's klasses list after all sub-graphs have dumped.
>> 
>> For each class that has archived sub-graph(s), I do a heap walk to discover
>> all klasses that are reachable from this archived fields of this class.
>> 
>> This is sub-optimal but suffice for now because we just have a very small
>> number of sub-graphs. The worst case its O(N^2) where N is the number of
>> objects in the archived heap.
>> 
>> In the future, we might need to implement a more efficient algorithm that
>> walks the heap once and computes all the klasses lists of all the
>> sub-graphs at the same time.
>> 
>> Testing
>> =======
>> 
>> hs-tier[1,2,3]
>> 
>> Thanks
>> - Ioi
>> 
>> 
>