RFR[S] 8210289 ArchivedKlassSubGraphInfoRecord is incomplete

[Jiangli Zhou]

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. 
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
>
>