RFR[S] 8210289 ArchivedKlassSubGraphInfoRecord is incomplete

[Jiangli Zhou]

Hi Ioi,

On 9/1/18 8:58 PM, Ioi Lam wrote:
> 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.

I think such issue can be solved by tracking the original K (in the 
K-list, short for the class-initialization-list) for each archived 
object. If an encountered object is already archived (within the current 
sub-graph) and is associated with K1 within the current K-list (must be 
in this case). We can update the sub-K-list between K1 and the K 
associated with the referencing object of the current object, so their 
level are the same. We can also add a flag to the K-list elements to tag 
each K within the cycle. It may not be what we need to do currently.

Can you please describe the specific class that you ran into with the 
bug in your sub-graph?
>
> 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()).
Our current K-lists are quite small. If the number of sub-graphs grows 
in the future and there are many duplicates in the K-lists, we can 
explore using a single K-list, with each sub-graph-info recording the 
[start-index, end-index] pairs of the sub-K-lists.

To avoid any confusion to others, I want to point out that the order of 
the elements in the K-list is not the initialization order of the 
classes that happens at dump time. The order of the K-list elements is 
determined by how we walk the graph. It works for our purpose because we 
are not doing general-purpose object graph archiving (at least 
currently), and all classes in the targeted sub-graph for archiving must 
not have any dependencies on runtime context. When we add more 
sub-graphs to the archive in the future, we can examine our existing 
assumptions and lift limitations case by case with enhancements.
>
> 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).
We probably don't need to do what I described in the above for now. I've 
looked at your changes, I think we can choose a middle-ground approach 
that's more efficient than your current change, but could still be 
O(N*M) in the worst case (N is the number of nodes, M is the number of 
sub-graphs). It also avoid duplicating the logic between the 
archiving_walk closure and the new RecordKlassesClosure.

In the middle-ground approach,  WalkOopAndArchiveClosure can take a new 
boolean flag, 'record_klass_only'. We can use a separate table to track 
the objects we have seen in the current sub-graph as you are doing in 
the webrev. If the there is an existing archived copy of the current 
object, we check the other table to determine if it's already in the 
current sub-graph. If yes, no additional work is needed. If no, 
recursively enter the closure but do 'record_klass_only'.

       oop archived = MetaspaceShared::find_archived_heap_object(obj);
       if (archived != NULL) {
         if (has_seen_in_the_current_graph) {
             // no work
         } else {
             // walk the object but record klass only
         }
         return;
       }

With that, we can avoid duplicating the logic in RecordKlassesClosure 
and also avoid walking the sub-graph objects twice in most cases. What 
do you think?

Thanks,
Jiangli
>
> 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
>>>>
>>>>
>