1879918 - Allocating tenured dependent strings doesn't work

Status: RESOLVED FIXED

(Core :: JavaScript: GC, task, P2)

Description

[Jan de Mooij [:jandem]]

If I change the last line of js::SubstringKernel to always allocate a tenured dependent string, like this:

  return NewDependentString(cx, str, begin, len, gc::Heap::Tenured);

The following test fails:

var s = JSON.parse('["abcdefabcdefabcdefabcdefabcdefabcdefabcdef"]')[0];
var dep = s.substring(1);
minorgc();
assertEq(dep, "bcdefabcdefabcdefabcdefabcdefabcdefabcdef");

Fortunately this heap argument is currently only used by the representativeStringArray testing function.

I think the problem is that nursery GC doesn't update the tenured dependent string's chars pointer when the base is a nursery string with nursery-allocated characters.

I ran into the same issue with a patch to allocate flattened rope characters in the nursery; it hits the same issue when the root of the rope tree is nursery-allocated but with tenured sub trees.

Comment 1

[Jan de Mooij [:jandem]]

Steve, any thoughts on the best fix for this?

I was wondering about handling this in TraceWholeCell but I don't know if that always works. If the base has already been tenured, I don't know if we have enough information left to update the dependent string.

Comment 2

[Jan de Mooij [:jandem]]

Or maybe we can call relocateDependentStringChars in TraceWholeCell?

Comment 3

[Steve Fink [:sfink] [:s:]]

This is a problem. We try to make it possible for any nursery allocation to fall back to the tenured heap without triggering a minor GC, eg if in a GC suppression region, which would make this possible to trigger even without changing the heap parameter. But in practice, it is very possible that this can't happen, which would explain why this hasn't shown up in fuzzing.

It's a complicated situation. To spot-fix the problem you're seeing, we could do it in TraceWholeCell. But once ropes get involved, it would be possible to have a tenured dependent string whose base is also a tenured dependent string, whose base in a nursery string: Tdep1 -> Tdep2 -> N. In that case, Tdep2 would be in the whole cell buffer and could be fixed up, but Tdep1 would not have a nursery -> tenured edge and so would not be in any store buffer, so we would not have any way to fix up its chars pointer during tenuring.

String deduplication ran into this, and the fix was to mark any string reachable from a tenured string as non-deduplicatable to avoid the whole problem.

Oh, wait. This must have been introduced (or at least exacerbated) by allocating string buffers in the nursery. Because without that, then you'd only need to do fixups if you had a dependent string pointing to chars actually living in the nursery, and that isn't supposed to happen. (If the string is short enough to allocate inline, then a dependent string should be copying the chars instead of pointing into a Cell. If the chars are not allocated inline, then they won't move during tenuring.) Rereading, that's what you said already:

I think the problem is that nursery GC doesn't update the tenured dependent string's chars pointer when the base is a nursery string with nursery-allocated characters.

Comment 4

[BugBot [:suhaib / :marco/ :calixte]]

Set release status flags based on info from the regressing bug 1853907

Comment 5

[Donal Meehan [:dmeehan]]

Too late for Fx122.
This has not been triaged yet for severity, but do we need to follow a fix as a ride-along in an Fx123 dot release or can it wait for a later release?

Comment 6

[Steve Fink [:sfink] [:s:]]

Oops. Now I see why jandem didn't file this as a defect.

As far as we currently know, this is not possible to hit with the current code. There are a couple of places that come close, but no known path (and the fuzzers haven't found anything either).

Comment 7

[Steve Fink [:sfink] [:s:]]

We could almost hit a similar case when flattening ropes: if you have a tenured rope with a nursery left child (with nursery chars), and flatten it, then if the left child's buffer were reused by the root then you'd end with a tenured string holding nursery chars. That would confuse everything. But this won't happen, because only extensible strings are reused, and strings with nursery-allocated chars aren't extensible.

Comment 8

[Steve Fink [:sfink] [:s:]]

The Tdep1 -> Tdep2 -> N situation can't currently arise because it requires the root node to have once been a rope node that stole the buffer from its leftmost child—but in that case, it could not have inherited nursery-allocated characters because that optimization only applies to extensible strings.

Comment 9

[Steve Fink [:sfink] [:s:]]

Looking at this makes me speculate that in some situations it would be better if flattening a rope would create dependent strings of not just interior rope nodes, but also leaves. Then again, that would introduce all kinds of problems (some similar to the ones here) because they couldn't just free their original data; there might be dependent strings using it. It would require some sort of whole-Zone dependent string marking tricks.

Comment 10

[Steve Fink [:sfink] [:s:]]

I'm not seeing an easy way to do the update in TraceWholeCell(.., JSString*) because it gets called early in the minor GC, most likely before its base has been traced. Which means that it can't update the chars yet; it needs to defer until there are chars to update to.

There is a similar mechanism in place already, a string fixup list that will be scanned at the end of the minor GC to update things. Unfortunately, it can only contain nursery cells (the list pointers are actually stored in nursery string cells after their data has been forwarded elsewhere), and the thing that needs to be fixed up in this case is the tenured dependent string. Or rather, all tenured dependent strings that use the nursery base string.

I could create a separate list for them, though that would require allocating memory during the minor GC, which is kind of unfortunate.

These are stored in the whole cell buffer, so I could re-scan the whole buffer for dependent strings at the end, but that seems expensive for a rare problem. I guess I could only clear the non-dependent string bits in the ArenaCellSets for the whole cell buffer on the first pass, then empty them all out on the second pass. Kind of complicated, though.

The most straightforward solution is to forbid tenured dependent string -> nursery buffer edges. If you tried to create one, it would malloc and copy the data instead. It does mean that if you were to flatten a nursery rope with a tenured interior node (or tenured leftmost extensible string leaf), that you'd have to switch to copying in the middle of a flattening operation, which could get hairy.

Comment 11

[Jan de Mooij [:jandem]]

(In reply to Steve Fink [:sfink] [:s:] from comment #10)

The most straightforward solution is to forbid tenured dependent string -> nursery buffer edges. If you tried to create one, it would malloc and copy the data instead. It does mean that if you were to flatten a nursery rope with a tenured interior node (or tenured leftmost extensible string leaf), that you'd have to switch to copying in the middle of a flattening operation, which could get hairy.

Yeah. To avoid that we could scan the rope tree beforehand to see if it has any tenured ropes. That adds a bit of work at the beginning of rope flattening, but if it lets us avoid the malloc in most cases it would likely be a reasonable trade-off. We would only do this scan for ropes that are short enough to qualify for nursery chars and that also puts an upper bound on the rope tree size/depth.

Comment 12

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1879918 - Allow tenured dependent strings of nursery base strings.

When tracing strings in the whole cell buffer, track all tenured dependent -> nursery string edges for later sweeping, and update the characters pointer if the base string's chars move out of the nursery.

Comment 13

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1879918 - Remove uses of the nondeduplicatable bit that are no longer needed now that tenured -> nursery dependent string edges are swept.

Comment 14

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1879918 - Move NON_DEDUP_BIT to bit 15 to free up a bit

Comment 15

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1879918 - Whole cell buffer tracing is no longer order-dependent between strings and non-strings

Comment 16

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/2e089790b421
Allow tenured dependent strings of nursery base strings. r=jandem,jonco
https://hg.mozilla.org/integration/autoland/rev/bb37d06bb381
Remove some uses of the nondeduplicatable bit r=jandem,jonco
https://hg.mozilla.org/integration/autoland/rev/7bafcd113e34
Move NON_DEDUP_BIT to bit 15 to free up a bit r=jandem
https://hg.mozilla.org/integration/autoland/rev/5a052a933f60
Whole cell buffer tracing is no longer order-dependent between strings and non-strings r=jonco

Comment 17

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/2e089790b421
https://hg.mozilla.org/mozilla-central/rev/bb37d06bb381
https://hg.mozilla.org/mozilla-central/rev/7bafcd113e34
https://hg.mozilla.org/mozilla-central/rev/5a052a933f60

Comment 18

[BugBot [:suhaib / :marco/ :calixte]]

Since the status is marked as fixed for nightly and as unaffected for release, is it fixed or unaffected for beta?
For more information, please visit BugBot documentation.

Comment 19

[Iulian Moraru]

Backed out 4 changesets (bug 1879918) for causing javascript crashes (bug 1887914).

• Push that was backed out

• Backout link

Comment 20

[Iulian Moraru]

Backout merged to central: https://hg.mozilla.org/mozilla-central/rev/9c775a9ffddc

Comment 21

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/30a0033ff0f4
Allow tenured dependent strings of nursery base strings. r=jandem,jonco
https://hg.mozilla.org/integration/autoland/rev/21ff3db39873
Remove uses of the nondeduplicatable bit that are no longer needed now that tenured -> nursery dependent string edges are swept. r=jandem,jonco
https://hg.mozilla.org/integration/autoland/rev/ad5643af47e1
Move NON_DEDUP_BIT to bit 15 to free up a bit r=jandem
https://hg.mozilla.org/integration/autoland/rev/e3c9c90141d0
Whole cell buffer tracing is no longer order-dependent between strings and non-strings r=jonco

Comment 22

[tszentpeteri]

https://hg.mozilla.org/mozilla-central/rev/30a0033ff0f4
https://hg.mozilla.org/mozilla-central/rev/21ff3db39873
https://hg.mozilla.org/mozilla-central/rev/ad5643af47e1
https://hg.mozilla.org/mozilla-central/rev/e3c9c90141d0