RFR[S] 8210289 ArchivedKlassSubGraphInfoRecord is incomplete

[Ioi Lam]

Hi Jiangli,

Thanks for looking at the optimization of this problem. I think your 
algorithm will run into problems if (a) there is a cycle, and (b) two 
sub-graphs point to different members in the cycle.

Maybe someone familiar with graph theory can suggest a solution?

My current thinking is to first find all the cycles in the archived 
heap. The reachability of every member in the cycle is the same, so we 
can collapse each cycle into a single node. After that we have a DAG. 
Then, instead of encoding the class initialization order as multiple 
lists, we can encode it as a DAG to save space.

See 
https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph

In any case, I think this is a sufficiently difficult problem, so we 
should separate the dumping of the sub-graphs (the first part of 
HeapShared::archive_module_graph_objects() in my patch) and the 
computation of the initialization order 
(HeapShared::record_subgraph_klasses()).

Also, I think we should defer the optimization of 
record_subgraph_klasses in a future RFE. That way, we can have 
correctness now, and performance later when we actually need it. (The 
current implementation of record_subgraph_klasses() has not caused any 
perceivable delay for the current set of objects that we are archiving).

Thanks
- Ioi

On 9/1/18 7:55 PM, Jiangli Zhou wrote:
>
>> 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
>>>
>>>