58695 2011-04-15 14:36:50 -0700 Creating copy of ContainerNode's when inserting or removing is inefficient 2011-04-22 16:11:50 -0700 1 1 1 Unclassified WebKit WebCore JavaScript 528+ (Nightly build) All OS X 10.5 RESOLVED FIXED P2 Normal --- 1 msaboff msaboff abarth ap dglazkov eric inferno jschuh oldest_to_newest 386943 0 msaboff 2011-04-15 14:36:50 -0700 Two separate but possibly related changes to Source/WebCore/dom/ContainerNode.cpp involve copying nodes as a way to ensure integrity. This is inefficient over appropriate uses of RefPtr. The original changes are from https://bugs.webkit.org/show_bug.cgi?id=49237 and https://bugs.webkit.org/show_bug.cgi?id=57265. 386948 1 89857 msaboff 2011-04-15 14:41:09 -0700 Created attachment 89857 Patch to re-implement Node handling without making copies 386951 2 89857 eric 2011-04-15 14:43:47 -0700 Comment on attachment 89857 Patch to re-implement Node handling without making copies View in context: https://bugs.webkit.org/attachment.cgi?id=89857&action=review > Source/WebCore/dom/ContainerNode.cpp:371 > + for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling()) > + child->willRemove(); What will happen to the 3rd child, if calling willRemove on the 1st removes the 2nd? Won't it get left out in the cold? (aka, never get a willRemove()?) 386956 3 89857 abarth 2011-04-15 14:48:04 -0700 Comment on attachment 89857 Patch to re-implement Node handling without making copies Is there are particular benchmark you're optimizing? The pattern you're introducing in this patch is much more dangerous than the existing code. I suspect this patch introduces security vulnerabilities, but I don't have a proof-of-concept exploit to demonstrate that belief. 386959 4 abarth 2011-04-15 14:50:12 -0700 +dglazkov b/c he's had fun exploring these sorts of tree-integrity issues before. 386982 5 jschuh 2011-04-15 15:24:10 -0700 Yeah, we've had numerous issues in ContainerNode where reentrant manipulation of siblings or children resulted in a variety of stale pointer conditions. So, I'm apprehensive about any patch that would move us back in the other direction. But, offhand the only thing that jumps out at me is is the case Eric pointed out. 387076 6 msaboff 2011-04-15 17:28:51 -0700 The benchmark in question is dromaeo?dom. The proposed patch is worth ~2% overall due to a ~4% speed up in dom-modify. I accept Eric's contention that there is an issue with in the third child case. The proposed willRemove() code does need a check like: if (child->parentNode() != this) // Check for child being removed from subtree while reparenting. break; This stops the handling of the next sibling through a deleted sibling node is a safe way. Let me suggest that the current code is incorrect as well. The proposed patch doesn't call "willRemove()" or "insertedIntoDocument()" for nodes after deleted nodes, but the current code calls those methods for nodes even if they have been deleted. Therefore the proposed patch (or a slight modification) has better performance and is arguably just as correct for this corner case. A more correct solution would be to queue up all modifying actions (e.g. run script) to be handled after the tree has been notified of the removals or insertions and then immediately process those actions. This is similar to "attach" processing. This would simplify the handling of side effects and provide a "correct" implementation. I would like to proceed at this point with the faster "not necessarily correct" version of the current slower "but not correct" version. And then work on the longer term version. 387082 7 abarth 2011-04-15 17:32:55 -0700 > Therefore the proposed patch (or a slight modification) has better performance and is arguably just as correct for this corner case. Please add a test for this case. > I would like to proceed at this point with the faster "not necessarily correct" version of the current slower "but not correct" version. And then work on the longer term version. That's fine as long as we can convince ourselves that the (potential) correctness issues in the new version don't include security vulnerabilities. 387367 8 89857 abarth 2011-04-17 10:03:54 -0700 Comment on attachment 89857 Patch to re-implement Node handling without making copies View in context: https://bugs.webkit.org/attachment.cgi?id=89857&action=review > Source/WebCore/dom/ContainerNode.cpp:368 > + RefPtr<Node> protect = this; This protect is new in this code, right? Does that mean we're fixing a crash? Have you looked at all callers of this function to make sure they understand that |this| might be deleted after this operation? > Source/WebCore/dom/ContainerNode.cpp:743 > + // NOTE: Since insertedIntoDocument can cause arbitrary changes to the > + // document, we need to guard our data with RefPtrs and guard each operation > + // with checks for mutation. > + RefPtr<Node> protect = this; Same question here. If we're fixing crashes, we should have tests that document that. 387368 9 89857 abarth 2011-04-17 10:07:10 -0700 Comment on attachment 89857 Patch to re-implement Node handling without making copies View in context: https://bugs.webkit.org/attachment.cgi?id=89857&action=review >> Source/WebCore/dom/ContainerNode.cpp:371 >> + for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling()) >> + child->willRemove(); > > What will happen to the 3rd child, if calling willRemove on the 1st removes the 2nd? Won't it get left out in the cold? (aka, never get a willRemove()?) What will happen if one of these nodes gets moved to another parent during this operation? It seems like we'll call willRemove on nodes that aren't actually going to be removed. > Source/WebCore/dom/ContainerNode.cpp:752 > + if (child->parentNode() != this) // Check for child being removed from subtree while reparenting. > + break; What if child N gets moved to the first or last sibling position during this operation? It seems like we'll either call insertedIntoDocument too many or too few times in that case, which could cause problems. 390542 10 90652 msaboff 2011-04-21 19:09:43 -0700 Created attachment 90652 Updated patch This patch adds the "child's parent not me" check to willRemove(). Concerning various questions raised with the initial patch: > > Therefore the proposed patch (or a slight modification) has better performance and is arguably just as correct for this corner case. > > Please add a test for this case. As I stated above, the existing code and proposed code have similar correctness issues. In both cases the correctness issues happen when the tree is modified during the insertion or removal. The existing code notifies nodes that are (will be) no longer part of the tree that they are being inserted. The proposed code stops notifying later sibling nodes when it encounters a node that has been removed as a side effect. Existing tests verify the correctness and no regression on the earlier crashing problems. > > I would like to proceed at this point with the faster "not necessarily correct" version of the current slower "but not correct" version. And then work on the longer term version. > > That's fine as long as we can convince ourselves that the (potential) correctness issues in the new version don't include security vulnerabilities. Given that we use RefPtr's as well as other sanity checks we solved for the original use after free issues. This is as evident by removing these safeguards and running tests added with the earlier fixes and seeing the crashes. We Ref a parent node, which will has the side effect of holding a ref to the chain of children which allows us to safely traverse them. > > Source/WebCore/dom/ContainerNode.cpp:368 > > + RefPtr<Node> protect = this; > > This protect is new in this code, right? Does that mean we're fixing a crash? Have you looked at all callers of this function to make sure they understand that |this| might be deleted after this operation? > > > Source/WebCore/dom/ContainerNode.cpp:743 > > + // NOTE: Since insertedIntoDocument can cause arbitrary changes to the > > + // document, we need to guard our data with RefPtrs and guard each operation > > + // with checks for mutation. > > + RefPtr<Node> protect = this; > > Same question here. If we're fixing crashes, we should have tests that document that. These ref's allows us to safely access the parent node and its children. It wasn't add to fix a crash, but to prevent one. > >> Source/WebCore/dom/ContainerNode.cpp:371 > >> + for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling()) > >> + child->willRemove(); > > > > What will happen to the 3rd child, if calling willRemove on the 1st removes the 2nd? Won't it get left out in the cold? (aka, never get a willRemove()?) > > What will happen if one of these nodes gets moved to another parent during this operation? It seems like we'll call willRemove on nodes that aren't actually going to be removed. > > > Source/WebCore/dom/ContainerNode.cpp:752 > > + if (child->parentNode() != this) // Check for child being removed from subtree while reparenting. > > + break; > > What if child N gets moved to the first or last sibling position during this operation? It seems like we'll either call insertedIntoDocument too many or too few times in that case, which could cause problems. The current code calls insertedIntoDocument too many times while the proposed patch could call too few times. Both behaviors are incorrect. We need to deal with the correctness issue by queueing up the notify calls while traversing the tree and then making the notify calls in order. I will be filing a separate bug for the correctness issue with an outline of the proposed fix. 390594 11 90652 mjs 2011-04-21 20:56:30 -0700 Comment on attachment 90652 Updated patch View in context: https://bugs.webkit.org/attachment.cgi?id=90652&action=review r=me but please consider the style comments and ideally explain why the guards here are safe and sufficient. > Source/WebCore/dom/ContainerNode.cpp:372 > + RefPtr<Node> protect = this; I suggest the following as the more common WebKit idiom: RefPtr<Node> protect(this); > Source/WebCore/dom/ContainerNode.cpp:378 > + for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling()) { > + if (child->parentNode() != this) // Check for child being removed from subtree while removing. > + break; > + child->willRemove(); > + } Won't this possibly change behavior for nodes inserted into the subtree while removing? Is that ok? Doesn't seem like the old code is particularly sensible either). Also, is it really correct that we won't send willRemove() for any other children if one has been removed? That seems like it could be problematic. > Source/WebCore/dom/ContainerNode.cpp:755 > + // NOTE: Since insertedIntoDocument can cause arbitrary changes to the > + // document, we need to guard our data with RefPtrs and guard each operation > + // with checks for mutation. > + RefPtr<Node> protect = this; Again I suggest RefPtr<Node> protect(this); Also, it might be nice to abbreviate the comment a little. The self-protecting RefPtr is a common WebKit idiom, it is not necessary to explain the idiom, just briefly note why self-destruction is possible. The guard after each operation is also already explained below. > Source/WebCore/dom/ContainerNode.cpp:764 > + if (child->parentNode() != this) // Check for child being removed from subtree while reparenting. > + break; Is it really right that we won't call insertedIntoDocument() on any subsequent children if even one has been removed? 391193 12 msaboff 2011-04-22 16:11:50 -0700 Committed r84701: <http://trac.webkit.org/changeset/84701> 89857 2011-04-15 14:41:09 -0700 2011-04-21 19:09:43 -0700 Patch to re-implement Node handling without making copies 58695.patch text/plain 3132 msaboff SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDg0MDMzKQorKysgU291cmNlL1dlYkNvcmUvQ2hhbmdl TG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMjIgQEAKKzIwMTEtMDQtMTUgIE1pY2hhZWwg U2Fib2ZmICA8bXNhYm9mZkBhcHBsZS5jb20+CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZ IChPT1BTISkuCisKKyAgICAgICAgQ3JlYXRpbmcgY29weSBvZiBDb250YWluZXJOb2RlJ3Mgd2hl biBpbnNlcnRpbmcgb3IgcmVtb3ZpbmcgaXMgaW5lZmZpY2llbnQKKyAgICAgICAgaHR0cHM6Ly9i dWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTU4Njk1CisKKyAgICAgICAgRWxpbWluYXRl ZCBub2RlIGNvcHlpbmcgaW4gd2lsbFJlbW92ZSgpIGFuZCBpbnNlcnRlZEludG9Eb2N1bWVudCgp LgorCisgICAgICAgIE5vIG5ldyB0ZXN0cyBhcyB0aGlzIGlzIGEgbW9yZSBlZmZpY2llbnQgaW1w bGVtZW50YXRpb24gb2YKKyAgICAgICAgZXhpc3RpbmcgY29kZSB0aGF0IGlzIGNvdmVyZWQgYnkg ZXhpc3RpbmcgdGVzdHMuCisKKyAgICAgICAgKiBkb20vQ29udGFpbmVyTm9kZS5jcHA6CisgICAg ICAgIChXZWJDb3JlOjpDb250YWluZXJOb2RlOjp3aWxsUmVtb3ZlKTogQ2hhbmdlZCBtZXRob2Qg dG8gdXNlCisgICAgICAgIFJlZlB0cjw+IHRvIHByb3RlY3QgYWdhaW5zdCBtb2RpZmljYXRpb24g ZHVyaW5nIHJlbW92YWwuCisgICAgICAgIChXZWJDb3JlOjpDb250YWluZXJOb2RlOjppbnNlcnRl ZEludG9Eb2N1bWVudCk6IENoYW5nZWQgbWV0aG9kIHRvIHVzZQorICAgICAgICBSZWZQdHI8PiBh bmQgdHdvIG90aGVyIGRlbGV0aW9uIGNoZWNrcyB0byBwcm90ZWN0IGFnYWluc3QgCisgICAgICAg IG1vZGlmaWNhdGlvbiBkdXJpbmcgaW5zZXJ0aW9uLgorCiAyMDExLTA0LTE1ICBTYW0gV2Vpbmln ICA8c2FtQHdlYmtpdC5vcmc+CiAKICAgICAgICAgUmV2aWV3ZWQgYnkgQWRhbSBSb2Jlbi4KSW5k ZXg6IFNvdXJjZS9XZWJDb3JlL2RvbS9Db250YWluZXJOb2RlLmNwcAo9PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBT b3VyY2UvV2ViQ29yZS9kb20vQ29udGFpbmVyTm9kZS5jcHAJKHJldmlzaW9uIDg0MDI5KQorKysg U291cmNlL1dlYkNvcmUvZG9tL0NvbnRhaW5lck5vZGUuY3BwCSh3b3JraW5nIGNvcHkpCkBAIC0z NjIsMTIgKzM2MiwxMyBAQCBib29sIENvbnRhaW5lck5vZGU6OnJlcGxhY2VDaGlsZChQYXNzUmVm CiAKIHZvaWQgQ29udGFpbmVyTm9kZTo6d2lsbFJlbW92ZSgpCiB7Ci0gICAgVmVjdG9yPFJlZlB0 cjxOb2RlPiwgMTA+IG5vZGVzOwotICAgIG5vZGVzLnJlc2VydmVJbml0aWFsQ2FwYWNpdHkoY2hp bGROb2RlQ291bnQoKSk7Ci0gICAgZm9yIChOb2RlKiBuID0gbV9sYXN0Q2hpbGQ7IG47IG4gPSBu LT5wcmV2aW91c1NpYmxpbmcoKSkKLSAgICAgICAgbm9kZXMuYXBwZW5kKG4pOwotICAgIGZvciAo OyBub2Rlcy5zaXplKCk7IG5vZGVzLnJlbW92ZUxhc3QoKSkKLSAgICAgICAgbm9kZXMubGFzdCgp LmdldCgpLT53aWxsUmVtb3ZlKCk7CisgICAgLy8gTk9URTogU2luY2Ugd2lsbFJlbW92ZSBjYW4g Y2F1c2UgYXJiaXRyYXJ5IGNoYW5nZXMgdG8gdGhlIGRvY3VtZW50LAorICAgIC8vIHdlIG5lZWQg dG8gZ3VhcmQgb3VyIGRhdGEgd2l0aCBSZWZQdHJzIGFuZCBndWFyZCBlYWNoIG9wZXJhdGlvbiB3 aXRoIAorICAgIC8vIGNoZWNrIGZvciBtdXRhdGlvbi4KKyAgICBSZWZQdHI8Tm9kZT4gcHJvdGVj dCA9IHRoaXM7CisKKyAgICBmb3IgKFJlZlB0cjxOb2RlPiBjaGlsZCA9IGZpcnN0Q2hpbGQoKTsg Y2hpbGQ7IGNoaWxkID0gY2hpbGQtPm5leHRTaWJsaW5nKCkpCisgICAgICAgIGNoaWxkLT53aWxs UmVtb3ZlKCk7CiAgICAgTm9kZTo6d2lsbFJlbW92ZSgpOwogfQogCkBAIC03MzYsMTYgKzczNywx OSBAQCB2b2lkIENvbnRhaW5lck5vZGU6OmRldGFjaCgpCiAKIHZvaWQgQ29udGFpbmVyTm9kZTo6 aW5zZXJ0ZWRJbnRvRG9jdW1lbnQoKQogeworICAgIC8vIE5PVEU6IFNpbmNlIGluc2VydGVkSW50 b0RvY3VtZW50IGNhbiBjYXVzZSBhcmJpdHJhcnkgY2hhbmdlcyB0byB0aGUgCisgICAgLy8gZG9j dW1lbnQsIHdlIG5lZWQgdG8gZ3VhcmQgb3VyIGRhdGEgd2l0aCBSZWZQdHJzIGFuZCBndWFyZCBl YWNoIG9wZXJhdGlvbgorICAgIC8vIHdpdGggY2hlY2tzIGZvciBtdXRhdGlvbi4KKyAgICBSZWZQ dHI8Tm9kZT4gcHJvdGVjdCA9IHRoaXM7CiAgICAgTm9kZTo6aW5zZXJ0ZWRJbnRvRG9jdW1lbnQo KTsKICAgICBpbnNlcnRlZEludG9UcmVlKGZhbHNlKTsKIAotICAgIC8vIERldGVybWluZSBzZXQg b2YgY2hpbGRyZW4gYmVmb3JlIG9wZXJhdGluZyBvbiBhbnkgb2YgdGhlbS4KLSAgICBOb2RlVmVj dG9yIGNoaWxkcmVuOwotICAgIGNvbGxlY3ROb2Rlcyh0aGlzLCBjaGlsZHJlbik7Ci0KLSAgICBO b2RlVmVjdG9yOjppdGVyYXRvciBpdDsKLSAgICBmb3IgKGl0ID0gY2hpbGRyZW4uYmVnaW4oKTsg aXQgIT0gY2hpbGRyZW4uZW5kKCkgJiYgaW5Eb2N1bWVudCgpOyArK2l0KSB7Ci0gICAgICAgIE5v ZGUqIGNoaWxkID0gaXQtPmdldCgpOworICAgIGZvciAoUmVmUHRyPE5vZGU+IGNoaWxkID0gbV9m aXJzdENoaWxkOyBjaGlsZDsgY2hpbGQgPSBjaGlsZC0+bmV4dFNpYmxpbmcoKSkgeworICAgICAg ICAvLyBHdWFyZCBhZ2FpbnN0IG11dGF0aW9uIGR1cmluZyByZS1wYXJlbnRpbmcuCisgICAgICAg IGlmICghaW5Eb2N1bWVudCgpKSAvLyBDaGVjayBmb3Igc2VsZiBiZWluZyByZW1vdmVkIGZyb20g ZG9jdW1lbnQgd2hpbGUgcmVwYXJlbnRpbmcuCisgICAgICAgICAgICBicmVhazsKKyAgICAgICAg aWYgKGNoaWxkLT5wYXJlbnROb2RlKCkgIT0gdGhpcykgLy8gQ2hlY2sgZm9yIGNoaWxkIGJlaW5n IHJlbW92ZWQgZnJvbSBzdWJ0cmVlIHdoaWxlIHJlcGFyZW50aW5nLgorICAgICAgICAgICAgYnJl YWs7CiAgICAgICAgIGNoaWxkLT5pbnNlcnRlZEludG9Eb2N1bWVudCgpOwogICAgIH0KIH0K 90652 2011-04-21 19:09:43 -0700 2011-04-21 20:56:30 -0700 Updated patch 58695-1.patch text/plain 3279 msaboff SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDg0NTg2KQorKysgU291cmNlL1dlYkNvcmUvQ2hhbmdl TG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMjIgQEAKKzIwMTEtMDQtMjEgIE1pY2hhZWwg U2Fib2ZmICA8bXNhYm9mZkBhcHBsZS5jb20+CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZ IChPT1BTISkuCisKKyAgICAgICAgQ3JlYXRpbmcgY29weSBvZiBDb250YWluZXJOb2RlJ3Mgd2hl biBpbnNlcnRpbmcgb3IgcmVtb3ZpbmcgaXMgaW5lZmZpY2llbnQKKyAgICAgICAgaHR0cHM6Ly9i dWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTU4Njk1CisKKyAgICAgICAgRWxpbWluYXRl ZCBub2RlIGNvcHlpbmcgaW4gd2lsbFJlbW92ZSgpIGFuZCBpbnNlcnRlZEludG9Eb2N1bWVudCgp LgorCisgICAgICAgIE5vIG5ldyB0ZXN0cyBhcyB0aGlzIGlzIGEgbW9yZSBlZmZpY2llbnQgaW1w bGVtZW50YXRpb24gb2YKKyAgICAgICAgZXhpc3RpbmcgY29kZSB0aGF0IGlzIGNvdmVyZWQgYnkg ZXhpc3RpbmcgdGVzdHMuCisKKyAgICAgICAgKiBkb20vQ29udGFpbmVyTm9kZS5jcHA6CisgICAg ICAgIChXZWJDb3JlOjpDb250YWluZXJOb2RlOjp3aWxsUmVtb3ZlKTogQ2hhbmdlZCBtZXRob2Qg dG8gdXNlCisgICAgICAgIFJlZlB0cjw+IHRvIHByb3RlY3QgYWdhaW5zdCBtb2RpZmljYXRpb24g ZHVyaW5nIHJlbW92YWwuCisgICAgICAgIChXZWJDb3JlOjpDb250YWluZXJOb2RlOjppbnNlcnRl ZEludG9Eb2N1bWVudCk6IENoYW5nZWQgbWV0aG9kIHRvIHVzZQorICAgICAgICBSZWZQdHI8PiBh bmQgdHdvIG90aGVyIGRlbGV0aW9uIGNoZWNrcyB0byBwcm90ZWN0IGFnYWluc3QgCisgICAgICAg IG1vZGlmaWNhdGlvbiBkdXJpbmcgaW5zZXJ0aW9uLgorCiAyMDExLTA0LTIxICBNaWNoYWVsIFNh Ym9mZiAgPG1zYWJvZmZAYXBwbGUuY29tPgogCiAgICAgICAgIFJldmlld2VkIGJ5IE1hY2llaiBT dGFjaG93aWFrLgpJbmRleDogU291cmNlL1dlYkNvcmUvZG9tL0NvbnRhaW5lck5vZGUuY3BwCj09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT0KLS0tIFNvdXJjZS9XZWJDb3JlL2RvbS9Db250YWluZXJOb2RlLmNwcAkocmV2aXNp b24gODQ1ODUpCisrKyBTb3VyY2UvV2ViQ29yZS9kb20vQ29udGFpbmVyTm9kZS5jcHAJKHdvcmtp bmcgY29weSkKQEAgLTM2NiwxMiArMzY2LDE2IEBAIGJvb2wgQ29udGFpbmVyTm9kZTo6cmVwbGFj ZUNoaWxkKFBhc3NSZWYKIAogdm9pZCBDb250YWluZXJOb2RlOjp3aWxsUmVtb3ZlKCkKIHsKLSAg ICBWZWN0b3I8UmVmUHRyPE5vZGU+LCAxMD4gbm9kZXM7Ci0gICAgbm9kZXMucmVzZXJ2ZUluaXRp YWxDYXBhY2l0eShjaGlsZE5vZGVDb3VudCgpKTsKLSAgICBmb3IgKE5vZGUqIG4gPSBtX2xhc3RD aGlsZDsgbjsgbiA9IG4tPnByZXZpb3VzU2libGluZygpKQotICAgICAgICBub2Rlcy5hcHBlbmQo bik7Ci0gICAgZm9yICg7IG5vZGVzLnNpemUoKTsgbm9kZXMucmVtb3ZlTGFzdCgpKQotICAgICAg ICBub2Rlcy5sYXN0KCkuZ2V0KCktPndpbGxSZW1vdmUoKTsKKyAgICAvLyBOT1RFOiBTaW5jZSB3 aWxsUmVtb3ZlIGNhbiBjYXVzZSBhcmJpdHJhcnkgY2hhbmdlcyB0byB0aGUgZG9jdW1lbnQsCisg ICAgLy8gd2UgbmVlZCB0byBndWFyZCBvdXIgZGF0YSB3aXRoIFJlZlB0cnMgYW5kIGd1YXJkIGVh Y2ggb3BlcmF0aW9uIHdpdGggCisgICAgLy8gY2hlY2sgZm9yIG11dGF0aW9uLgorICAgIFJlZlB0 cjxOb2RlPiBwcm90ZWN0ID0gdGhpczsKKworICAgIGZvciAoUmVmUHRyPE5vZGU+IGNoaWxkID0g Zmlyc3RDaGlsZCgpOyBjaGlsZDsgY2hpbGQgPSBjaGlsZC0+bmV4dFNpYmxpbmcoKSkgeworICAg ICAgICBpZiAoY2hpbGQtPnBhcmVudE5vZGUoKSAhPSB0aGlzKSAvLyBDaGVjayBmb3IgY2hpbGQg YmVpbmcgcmVtb3ZlZCBmcm9tIHN1YnRyZWUgd2hpbGUgcmVtb3ZpbmcuCisgICAgICAgICAgICBi cmVhazsKKyAgICAgICAgY2hpbGQtPndpbGxSZW1vdmUoKTsKKyAgICB9CiAgICAgTm9kZTo6d2ls bFJlbW92ZSgpOwogfQogCkBAIC03NDUsMTYgKzc0OSwxOSBAQCB2b2lkIENvbnRhaW5lck5vZGU6 OmRldGFjaCgpCiAKIHZvaWQgQ29udGFpbmVyTm9kZTo6aW5zZXJ0ZWRJbnRvRG9jdW1lbnQoKQog eworICAgIC8vIE5PVEU6IFNpbmNlIGluc2VydGVkSW50b0RvY3VtZW50IGNhbiBjYXVzZSBhcmJp dHJhcnkgY2hhbmdlcyB0byB0aGUgCisgICAgLy8gZG9jdW1lbnQsIHdlIG5lZWQgdG8gZ3VhcmQg b3VyIGRhdGEgd2l0aCBSZWZQdHJzIGFuZCBndWFyZCBlYWNoIG9wZXJhdGlvbgorICAgIC8vIHdp dGggY2hlY2tzIGZvciBtdXRhdGlvbi4KKyAgICBSZWZQdHI8Tm9kZT4gcHJvdGVjdCA9IHRoaXM7 CiAgICAgTm9kZTo6aW5zZXJ0ZWRJbnRvRG9jdW1lbnQoKTsKICAgICBpbnNlcnRlZEludG9UcmVl KGZhbHNlKTsKIAotICAgIC8vIERldGVybWluZSBzZXQgb2YgY2hpbGRyZW4gYmVmb3JlIG9wZXJh dGluZyBvbiBhbnkgb2YgdGhlbS4KLSAgICBOb2RlVmVjdG9yIGNoaWxkcmVuOwotICAgIGNvbGxl Y3ROb2Rlcyh0aGlzLCBjaGlsZHJlbik7Ci0KLSAgICBOb2RlVmVjdG9yOjppdGVyYXRvciBpdDsK LSAgICBmb3IgKGl0ID0gY2hpbGRyZW4uYmVnaW4oKTsgaXQgIT0gY2hpbGRyZW4uZW5kKCkgJiYg aW5Eb2N1bWVudCgpOyArK2l0KSB7Ci0gICAgICAgIE5vZGUqIGNoaWxkID0gaXQtPmdldCgpOwor ICAgIGZvciAoUmVmUHRyPE5vZGU+IGNoaWxkID0gbV9maXJzdENoaWxkOyBjaGlsZDsgY2hpbGQg PSBjaGlsZC0+bmV4dFNpYmxpbmcoKSkgeworICAgICAgICAvLyBHdWFyZCBhZ2FpbnN0IG11dGF0 aW9uIGR1cmluZyByZS1wYXJlbnRpbmcuCisgICAgICAgIGlmICghaW5Eb2N1bWVudCgpKSAvLyBD aGVjayBmb3Igc2VsZiBiZWluZyByZW1vdmVkIGZyb20gZG9jdW1lbnQgd2hpbGUgcmVwYXJlbnRp bmcuCisgICAgICAgICAgICBicmVhazsKKyAgICAgICAgaWYgKGNoaWxkLT5wYXJlbnROb2RlKCkg IT0gdGhpcykgLy8gQ2hlY2sgZm9yIGNoaWxkIGJlaW5nIHJlbW92ZWQgZnJvbSBzdWJ0cmVlIHdo aWxlIHJlcGFyZW50aW5nLgorICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgIGNoaWxkLT5pbnNl cnRlZEludG9Eb2N1bWVudCgpOwogICAgIH0KIH0K