RFR[S] 8210289 ArchivedKlassSubGraphInfoRecord is incomplete

Jiangli Zhou jiangli.zhou at oracle.com
Thu Sep 6 23:28:33 UTC 2018

Hi Ioi,

Sorry for the delay. It took me a while to get back to this. Thanks for 
folding the closures together. It cuts the cost by almost half. Here are 
my detailed comments.

- _subgraph_object_klasses renaming

The reason that I choose _subgraph_object_klasses was to disambiguate 
between the klass containing a subgraph and the klass of an object 
included in a subgraph. Is there a specific reason to rename the term to 

- Could you please align the lines at 358 - 360.

  355   WalkOopAndArchiveClosure(int level, bool record_klasses_only,
  356                            KlassSubGraphInfo* subgraph_info,
  357                            oop orig, oop archived, TRAPS) :
  358     _level(level), _record_klasses_only(record_klasses_only),
  359     _subgraph_info(subgraph_info),
  360     _orig_referencing_obj(orig), _archived_referencing_obj(archived),
  361     _thread(THREAD) {}

- (2) should be only applied to object that's not seen within the 
current subgraph. Please clarify it in the comment.

  401 // (2) If orig_obj has not been seen yet, trace all
  402 //     objects that are reachable from it, and make sure these 
objects are archived.

- Some Strings (such as "") are not archived in the closed archive heap 
region. In that case, the String object is automatically archived in the 
open archive heap region. The following comment should be clarified and 

  417     // Strings are already archived in closed archive. No need to 
walk it

- HeapShared::archive_reachable_objects_from() should take a 
'_record_klasses_only' argument from caller, which decides if it only 
needs to record the klass list.

As we walk all reachable objects from an entry point (a static field) 
during walk&archive process, at the end of it we obtain a complete and 
closed archived subgraph. Every object is also the root of a 
sub-subgraph that's reachable from it. In a subsequent subgraph 
archiving process from a different entry point, if we encounter an 
object that is already archived, then every objects contained within the 
sub-subgraph reachable from that root are already archived also. So, 
'_record_klasses_only' should be a inherited flag from the root and 
passed to all HeapShared::archive_reachable_objects_from() calls for 
processing objects within a sub-subgraph.

During the walk, '_record_klasses_only' should be false initially. Once 
it sees an object that already has an archived copy (but not seen in the 
current subgraph), the '_record_klasses_only' needs to become true and 
be propagated to all sub-walking processes. '_record_klasses_only' 
should never go back to false state.

With that, we can guarantee to build a correct archived subgraph without 
the risk of infinite cycles. It also reduces overhead for the 
walk&archive process.

- Could add explanation in the comment?

438         // See runtime/appcds/cacheObject/ArchivedIntegerCacheTest.java

- Please add the step 5) comment back to the walk&archive description.

  466 // 5) The Klass of the current java object is added to the list of 
  467 // for loading and initialzing before any object in the archived 
graph can
  468 // be accessed at runtime.
  469 //

- The HeapShared::archive_module_graph_objects() can take a more general 
name now, if you want to do it as part of your change.

- Could you please explain the reason for using two loops here? 
Shouldn't one loop be sufficient?

  646   for (int i = 0; i < num_archivable_static_fields; ) {

  651     int j = i;
  652     while (j < num_archivable_static_fields) {
  653       ArchivableStaticFieldInfo* f = &archivable_static_fields[j];
  654       if (f->klass_name == klass_name) {
  655 archive_reachable_objects_from_static_field(f->klass, f->klass_name,
  656 f->offset, f->field_name, CHECK);
  657         j++;
  658       } else {
  659         break;
  660       }
  661     }
  663     i = j;
  664   }

Could you please also send a sample of the changed cds+heap debug log 



On 9/5/18 3:56 PM, Ioi Lam wrote:
> I updated the patch:
> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v03/ 
> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v03-delta/ 
> 1. No need to walk String objects during subgraph recording.
> 2. Print put statistics:
> =========================
> jdk/internal/module/ArchivedModuleGraph: walked 1871 objs, archived 
> 1871 new objs, recorded 28 classes
> java/util/ImmutableCollections$ListN: walked 2 objs, archived 0 new 
> objs, recorded 0 classes
> java/util/ImmutableCollections$MapN: walked 2 objs, archived 0 new 
> objs, recorded 0 classes
> java/util/ImmutableCollections$SetN: walked 2 objs, archived 0 new 
> objs, recorded 0 classes
> java/lang/Integer$IntegerCache: walked 257 objs, archived 256 new 
> objs, recorded 2 classes
> java/lang/module/Configuration: walked 7 objs, archived 0 new objs, 
> recorded 3 classes
> Performed subgraph records = 6 times
> Walked 2141 objects
> Archived 2127 objects
> Recorded 33 klasses
> ========
> So, at least for now, we don't need to worry about the performance of 
> WalkOopAndArchiveClosure.
> Once I get some statistics of Lambda archiving, I'll post them as well.
> So, with the bug fix, the subgraph recording should be both correct 
> and faster than before (no more String walking).
> Thanks
> - Ioi
> On 9/3/2018 1:02 AM, Ioi Lam wrote:
>> Hi Jiangli,
>> I think your suggestion of combining of combining 
>> RecordKlassesClosure and WalkOopAndArchiveClosure is a good idea. I 
>> have updated the webrev:
>> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v02/ 
>> This also supersedes my other patch for JDK-8210295 Refactor 
>> HeapShared::archive_reachable_objects_from_static_field
>> More comments below on future optimizations.
>> On 9/2/18 6:07 PM, Jiangli Zhou wrote:
>>> 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?
>> I found the bug by code examination. It's also during this time that 
>> I realized that it's not a simple problem to optimize, because of 
>> cycles in the graph. There's been tons of established research in 
>> this area (as in "Tarjan's algorithm is one of Donald Knuth's 
>> favorite implementations"),  so I don't think we should reinvent the 
>> wheel. For future optimization, let's just apply an existing algorithm.
>>>> 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.
>> Sorry for the confusion. I wanted to avoid using the word "list" -- I 
>> think the most space efficient representation will be a DAG instead 
>> of a list -- I should have used "set" instead.
>> Thanks again for spending time on this topic.
>> - Ioi
>>> 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

More information about the hotspot-runtime-dev mailing list