[runtime] sort transition array after it grows beyond linear search size [v8/v8 : main]
Joyee Cheung (Gerrit)
Joyee Cheung added 1 comment![]( "Open in Gerrit")
PTAL, thanks, we found this during the V8 update in Node.js
Related details
- Igor Sheludko
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Igor Sheludko (Gerrit)
Igor Sheludko added 1 comment![]( "Open in Gerrit")
Thanks for fixing this!
looks good, but could you please create a regression test for this issue?
Related details
- Joyee Cheung
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Igor Sheludko (Gerrit)
Igor Sheludko added 1 comment![]( "Open in Gerrit")
SLOW_DCHECK(array->IsSortedNoDuplicates());BTW, do these checks catch the issue?
Related details
- Joyee Cheung
Code-Owners
Code-Review
No-Unresolved-Comments
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Joyee Cheung (Gerrit)
Joyee Cheung added 2 comments![]( "Open in Gerrit")
Thanks for fixing this!
looks good, but could you please create a regression test for this issue?
I tried to add a test, but it doesn't seem to be crashing without the patch. From what I can tell from the Node.js reproduction, it involves one special transition (with the frozen symbol), though it's a bit tricky to track down what was inserted in that reproduction which is fairly huge. I'll try to see if I can trace what exactly was inserted in that faulting object and in what order..
BTW, do these checks catch the issue?
From testing the Node.js built, the check caught it when there were duplicates, and the fix here was enough for me to turn these two into DCHECK and still pass the entire Node.js test suite.
Related details
- Igor Sheludko
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Joyee Cheung (Gerrit)
Joyee Cheung voted and added 1 comment![]( "Open in Gerrit")
Votes added by Joyee Cheung
| Commit-Queue | +1 |
1 comment
I looked into the reproduction a bit more and worked out a reproducing test. It basically goes like this:
1. During snapshot creation, Node.js grows the transitions of the cached map
2. After a round of snapshot serialization/deserialization, the transitions gets rehashed, so it's "shuffled" in terms of ordering based on the hash (in this case, it's an array of size 27)
3. TransitionAccessor:InsertHelper() assumes that the array is always sorted even if it's below the kMaxElementsForLinearSearch, and after rehashing that assumption gets broken. So once the insertion grows the size to 32 that broken assumption start to show.
Another fix might be to update `HeapObject::RehashBasedOnMap` so that it always sort the transition arrays even if their size is below the linear search size, though I feel that the current fix still seems more robust as it seems a bit shaky to assume the array must always be sorted even when it's below kMaxElementsForLinearSearch, and maintaining the sorting regardless of size also defeats the purpose of having this threshold.
Related details
- Igor Sheludko
- Joyee Cheung
Code-Owners
Code-Review
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |