RFR[S] 8210289 ArchivedKlassSubGraphInfoRecord is incomplete
Jiangli Zhou
jiangli.zhou at oracle.com
Tue Sep 11 01:35:54 UTC 2018
On 9/10/18 4:10 PM, Ioi Lam wrote:
> On 9/10/2018 1:00 PM, Jiangli Zhou wrote:
>
>> Hi Ioi,
>>
>> Thanks for another updated webrev. Please see comments (minor) below.
>>
>>>> *From:* Ioi Lam <ioi.lam at oracle.com <mailto:ioi.lam at oracle.com>>
>>>> *Date:* September 9, 2018 at 12:11:42 PM PDT
>>>> *To:* Jiangli Zhou <jiangli.zhou at oracle.com
>>>> <mailto:jiangli.zhou at oracle.com>>,
>>>> hotspot-runtime-dev at openjdk.java.net
>>>> <mailto:hotspot-runtime-dev at openjdk.java.net>
>>>> *Subject:* *Re: RFR[S] 8210289 ArchivedKlassSubGraphInfoRecord is
>>>> incomplete*
>>>>
>>>> Hi Jiangli,
>>>>
>>>> Thanks again for the review. I've updated the patch:
>>>>
>>>> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v05/
>>>> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v05-delta/
>>>>
>>>> More comments inline
>>>>
>>>> On 9/8/18 2:37 PM, Jiangli Zhou wrote:
>>>>> Hi Ioi,
>>>>>
>>>>> The updated webrev looks great. Here are some additional comments.
>>>>>
>>>>> - Thanks for answering my question about the two loops. If we want
>>>>> to solve the klass list issue as a general problem, we also need
>>>>> to allow the cases where the entry fields from the same class are
>>>>> not specified consecutively. The 'break' in the inner loop should
>>>>> be a 'continue'. Currently, all the entry fields from a single
>>>>> class are specified together as we are doing it manually. When we
>>>>> enhance the mechanism by adding the other half API that enables
>>>>> registering the entry fields from java code automatically, we
>>>>> might see fields from different classes are in mixed orders.
>>>>>
>>>>> 657 while (j < num_archivable_static_fields) {
>>>>> 658 ArchivableStaticFieldInfo* f =
>>>>> &archivable_static_fields[j];
>>>>> 659 if (f->klass_name == klass_name) {
>>>>> 660 archive_reachable_objects_from_static_field(f->klass,
>>>>> f->klass_name,
>>>>> 661 f->offset, f->field_name, CHECK);
>>>>> 662 j++;
>>>>> 663 } else {
>>>>> 664 break; <<<<<<<
>>>>> 665 }
>>>>> 666 }
>>>>>
>>>>
>>>> It's actually OK now to not order the archivable_static_fields[]
>>>> array by class name. The inner loop is just for optimization. I've
>>>> updated the code and added comments to make this clear.
>>>>
>>>> I tested by reordering the archivable_static_fields[] array (move
>>>> the "archivedModuleFinder" line to the end of the table). It shows:
>>>>
>>>> Performed subgraph records = 7 times
>>>> Walked 3610 objects
>>>> Archived 2127 objects
>>>> Recorded 33 klasses
>>>>
>>>> With the original (sorted) table, it's faster with fewer walks, but
>>>> that doesn't change the number of archived objects or recorded klasses:
>>>>
>>>> Performed subgraph records = 6 times
>>>> Walked 2141 objects
>>>> Archived 2127 objects
>>>> Recorded 33 klasses
>>>>
>> The seen_objects_table resets when you see a klass_name that's
>> different. When the entry fields from different classes are mixed,
>> you might record an object klass that's already seen early for the
>> same containing class. That is not incorrect, but adds overhead
>> (although very small) to runtime. For following entry fields sequence:
>>
>> A.f1
>> A.f2
>> B.f1
>> A.f3
>>
>> For example, K1 is recorded for A.f1, A.f2 subgraphs. When archiving
>> A.f3 subgraph, K1 is encountered, K1 would be recorded again for A.f3
>> because a different seen_objects_table is used. We can fix the logic
>> here or add a post process to eliminate any duplication in the klass
>> lists belonging to the same containing klass. The post process seems
>> to be an overkill.
>
> There's no duplication in the _subgraph_object_klasses list because we
> add it to only when needed:
>
> _subgraph_object_klasses->append_if_missing(relocated_k);
>
> So there's no runtime impact. (You can also see that with the same
> "Recorded 33 klasses" from the log above.)
This indeed has no issue. I forgot that I built a single
subgraph_info_record for each containing klass, but not for each entry
field. :(
One containing klass may have multiple subgraphs referenced from
multiple entry points. Since there is no separate info_record for each
entry field from the same containing klass, then there is no duplicates
for the recorded object_klass. Sorry for the confusion! Thank you being
patient with me.
Thanks,
Jiangli
>
>
>>>>
>>>>> - In order to make sure subgraphs are archived correctly, we need
>>>>> to do proper state propagation and checks/asserts, including the
>>>>> record_klasses_only state. When we see record_klasses_only becomes
>>>>> true, we need to verify all reachable object from the current one
>>>>> must have existing archived copies already. That helps to confirm
>>>>> that an earlier archived subgraph is complete, especially if the
>>>>> current walk enters an sub-subgraph from a different node. For
>>>>> your current scope of changes, resetting the record_klasses_only
>>>>> state based on if there is an existing archived copy is ok. We can
>>>>> enhance it separately.
>>>>>
>>>>
>>>> I added a separate pass to verify these -- for each root (orig_obj)
>>>> of an archived subgraph:
>>>>
>>>> // (1) Verify that all objects reachable from orig_obj are archived.
>>>> // (2) Verify that all objects reachable from the archived copy
>>>> of orig_obj
>>>> // can only point to archived objects.
>>>>
>>>> I think that's sufficient to ensure that you have correctly
>>>> archived everything you need.
>>
>> The verify code is good to have. (2) is not necessary as that's
>> already done by the archiving verification code in GC. There is more
>> fine grained region verification implemented for archived objects in
>> G1 and (2) is already done for all objects in open archive heap
>> regions at dump time.
>>
>
> Thanks for letting me know. I've replaced (2) with this comment.
>
> // Note: we could also verify that all objects reachable from the
> archived
> // copy of orig_obj can only point to archived objects, with:
> // init_seen_objects_table();
> // verify_reachable_objects_from(archived_obj, true);
> // init_seen_objects_table();
> // but that's already done in G1HeapVerifier::verify_archive_regions
> so we
> // won't do it here.
>
>
>
>>>>
>>>>> Please also test all tier1-tier6 for your changes with the default
>>>>> CDS archive patch.
>>>>>
>>>> I just submitted a job for hs-tier1~6 using your latest patch
>>>> http://mail.openjdk.java.net/pipermail/build-dev/2018-September/023146.html
>>
>
> My test jobs passed with no new failures, so I'll push now.
>
> Thanks
> - Ioi
>
>
>> Thanks,
>> Jiangli
>>>>
>>>> Thanks
>>>> - Ioi
>>>>
>>>>> Thanks,
>>>>> Jiangli
>>>>>
>>>>> On 9/7/18 5:58 PM, Ioi Lam wrote:
>>>>>>
>>>>>> Hi Jiangli,
>>>>>>
>>>>>> Thanks for the review!
>>>>>>
>>>>>> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v04/
>>>>>> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v04-delta/
>>>>>>
>>>>>>
>>>>>> On 9/6/2018 4:28 PM, Jiangli Zhou wrote:
>>>>>>> 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 _subgraph_klasses?
>>>>>>>
>>>>>>
>>>>>> I just wanted to shorten the names to be the same as
>>>>>> ArchivedKlassSubGraphInfoRecord::subgraph_klasses, but I agree
>>>>>> with you for the naming.
>>>>>>
>>>>>> So instead, I've renamed
>>>>>> ArchivedKlassSubGraphInfoRecord::subgraph_klasses ->
>>>>>> subgraph_object_klasses to make the code consistent. What do you
>>>>>> think?
>>>>>>
>>>>>>> - 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) {}
>>>>>>>
>>>>>>
>>>>>> The 2 space indent is for the C++ field initializer list. HotSpot
>>>>>> style guide doesn't mention this
>>>>>> (https://wiki.openjdk.java.net/display/HotSpot/StyleGuide) so I
>>>>>> just used emacs's default indentation.
>>>>>>
>>>>>>> - (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.
>>>>>>>
>>>>>>
>>>>>> I changed it to
>>>>>>
>>>>>> // (2) If orig_obj has not been seen yet (since
>>>>>> start_recording_subgraph() was called),
>>>>>> // trace all 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 fixed.
>>>>>>>
>>>>>>> 417 // Strings are already archived in closed archive. No
>>>>>>> need to walk it
>>>>>>>
>>>>>>
>>>>>> I changed to
>>>>>>
>>>>>> if (java_lang_String::is_instance(orig_obj) && archived_obj !=
>>>>>> NULL) {
>>>>>> // To save time, don't walk strings that are already
>>>>>> archived. They just contain
>>>>>> // pointers to a type array, whose klass doesn't need to be
>>>>>> recorded.
>>>>>> return archived_obj;
>>>>>> }
>>>>>>
>>>>>>
>>>>>>> - 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; ) {
>>>>>>>
>>>>>>> 650
>>>>>>> 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 }
>>>>>>> 665
>>>>>>
>>>>>> That's because you can archive multiple fields in the same klass:
>>>>>>
>>>>>> // If you add new entries to this table, you should know what
>>>>>> you're doing!
>>>>>> static ArchivableStaticFieldInfo archivable_static_fields[] = {
>>>>>> {"jdk/internal/module/ArchivedModuleGraph",
>>>>>> "archivedSystemModules"},
>>>>>> {"jdk/internal/module/ArchivedModuleGraph",
>>>>>> "archivedModuleFinder"},
>>>>>> {"jdk/internal/module/ArchivedModuleGraph", "archivedMainModule"},
>>>>>> {"jdk/internal/module/ArchivedModuleGraph",
>>>>>> "archivedConfiguration"},
>>>>>> {"java/util/ImmutableCollections$ListN", "EMPTY_LIST"},
>>>>>>
>>>>>> Note that start/done_recording_subgraph are called in the i loop
>>>>>> and not the j loop.
>>>>>>
>>>>>>> - 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.
>>>>>>
>>>>>> I actually started to write to code exactly as you suggested, by
>>>>>> passing record_klasses_only down, and then I found out that it's
>>>>>> unnecessary, and having it will require me to add complicated
>>>>>> asserts that was beyond my ability to get right.
>>>>>>
>>>>>> As I understand, you worry about about correctness (termination
>>>>>> of the algorithm), and performance.
>>>>>>
>>>>>> I believe the logic of the current code is correct, and the
>>>>>> algorithm will terminate:
>>>>>>
>>>>>> oop archived_obj =
>>>>>> MetaspaceShared::find_archived_heap_object(orig_obj);
>>>>>> ....
>>>>>> if (has_been_seen_during_subgraph_recording(orig_obj)) {
>>>>>> // orig_obj has already been archived and traced. Nothing
>>>>>> more to do.
>>>>>> return archived_obj;
>>>>>> }
>>>>>> ...
>>>>>> WalkOopAndArchiveClosure walker(level, record_klasses_only,
>>>>>> subgraph_info, orig_obj, archived_obj, THREAD);
>>>>>> orig_obj->oop_iterate(&walker); // recurse
>>>>>>
>>>>>> HeapShared::archive_reachable_objects_from will recurse ONLY if
>>>>>> you call this function with an object that has not need seen, so
>>>>>> eventually the recursion will stop because all objects in the
>>>>>> subgraph has been seen.
>>>>>>
>>>>>> To make the code easier to understand, I rewrote it like this:
>>>>>>
>>>>>> if (has_been_seen_during_subgraph_recording(orig_obj)) {
>>>>>> // orig_obj has already been archived and traced. Nothing
>>>>>> more to do.
>>>>>> return archived_obj;
>>>>>> } else {
>>>>>> set_has_been_seen_during_subgraph_recording(orig_obj);
>>>>>> }
>>>>>>
>>>>>> For performance, the logic for deciding record_klasses_only is this:
>>>>>>
>>>>>> oop archived_obj =
>>>>>> MetaspaceShared::find_archived_heap_object(orig_obj);
>>>>>> ...
>>>>>> bool record_klasses_only = (archived_obj != NULL);
>>>>>>
>>>>>> You have to call find_archived_heap_object anyway, so that's
>>>>>> unavoidable. The cost of computing record_klasses_only is very
>>>>>> simple. For performance, there's no need for the it to be tracked
>>>>>> in the recursive calls. That makes the code simpler, and easier
>>>>>> to maintain.
>>>>>>
>>>>>> Otherwise we may need to think about whether the caller and the
>>>>>> callee have different opinion on record_klasses_only:
>>>>>>
>>>>>> - if this could happen, what would cause this to happen, and
>>>>>> how should we handle it?
>>>>>> - if this could never happen, how would you write an assertion
>>>>>> to validate that?
>>>>>>
>>>>>> Writing those asserts turned out to be too complicated.
>>>>>>
>>>>>>>
>>>>>>> - Could add explanation in the comment?
>>>>>>>
>>>>>>> 438 // See
>>>>>>> runtime/appcds/cacheObject/ArchivedIntegerCacheTest.java
>>>>>>>
>>>>>>
>>>>>> I changed it to
>>>>>>
>>>>>> if (level == 1) {
>>>>>> // Don't archive a subgraph root that's too big. For
>>>>>> archives static fields, that's OK
>>>>>> // as the Java code will take care of initializing this
>>>>>> field dynamically.
>>>>>> return NULL;
>>>>>> }
>>>>>>
>>>>>>> - 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 Klasses
>>>>>>> 467 // for loading and initialzing before any object in the
>>>>>>> archived graph can
>>>>>>> 468 // be accessed at runtime.
>>>>>>> 469 //
>>>>>>>
>>>>>>
>>>>>> Done. Sorry I removed it by mistake.
>>>>>>
>>>>>>> - The HeapShared::archive_module_graph_objects() can take a more
>>>>>>> general name now, if you want to do it as part of your change.
>>>>>>>
>>>>>>>
>>>>>> I renamed it to archive_static_fields(). I also removed/fixed a
>>>>>> few comments about "Currently there is only one class mirror
>>>>>> (ArchivedModuleGraph) with archived sub-graphs."
>>>>>>
>>>>>>> Could you please also send a sample of the changed cds+heap
>>>>>>> debug log output?
>>>>>>>
>>>>>> See
>>>>>> http://cr.openjdk.java.net/~iklam/jdk12/8210289-subgraph-record-incomplete.v04/logs/
>>>>>>
>>>>>> Thanks
>>>>>> - Ioi
>>>>>>
>>>>>>> Thanks!
>>>>>>>
>>>>>>> Jiangli
>>>>>>>
>>>>>>> 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