1875030 - Marking object elements may be quadratic if there are shifted elements

Status: RESOLVED FIXED

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

Description

[Jon Coppeard (:jonco)]

I found a bug in the way we handle indexes into object element ranges when accounting for shifted elements and this may lead to quadratic marking time for those elements.

The mark stack mark hold indexes into object elements to track the progress of marking those elements. The mutator may shift these elements which would invalidate any index we hold. The idea is that we fix and of these indexes by subtracting the shifted elements count.

Unfortunately however this is not performed once at the start of marking but every time we read the range off the mark stack. Since we use depth first traversal for marking this can happen for every element. This causes us to loop over these elements repeatedly as we reset the index to zero every time. We check whether the GC things are already marked so this does not cause to loop forever. Also, the number of elements we loop over is limited by the number of shifted elements, so this is not likely to be a big problem in practice.

Comment 1

[Jon Coppeard (:jonco)]

Test case to reproduce the issue:

const size = 1000000;

gc();

let a = new Array(size);

for (let i = 0; i < size; i++) {
  if (i < size / 2) {
    a[i] = 0;
  } else {
    a[i] = { x: i };
  }
}
for (i = 0; i < size / 2; i++) {
  a.shift();
}

let start = performance.now();
gc();
let end = performance.now();
print(`Time: ${end - start} ms`);

Current result: 543.41 ms
Result with patch: 8.02 ms

Comment 2

[Jon Coppeard (:jonco)]

Attachment: Bug 1875030 - Update element ranges on the mark stack before and after marking to take account of shifted elements r?sfink

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/27ddbf31966b
Update element ranges on the mark stack before and after marking to take account of shifted elements r=sfink,jandem

Comment 4

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/27ddbf31966b

Comment 5

[Jon Coppeard (:jonco)]

Attachment: Bug 1875030 - Update element ranges on the mark stack before and after marking to take account of shifted elements (ESR115) r=sfink,jandem

Comment 6

[Jon Coppeard (:jonco)]

Attachment: Bug 1875030 - Update element ranges on the mark stack before and after marking to take account of shifted elements (ESR115)

Comment 7

[Jon Coppeard (:jonco)]

Comment on attachment 9403465 [details]
Bug 1875030 - Update element ranges on the mark stack before and after marking to take account of shifted elements (ESR115)

ESR Uplift Approval Request

• If this is not a sec:{high,crit} bug, please state case for ESR consideration: Requesting uplift as this is a dependency of bug 1889355, which is sec-high.
• User impact if declined: Bug 1889355: Possible crash / security vulnerability.
• Fix Landed on Version: 124
• Risk to taking this patch: Low
• Why is the change risky/not risky? (and alternatives if risky): The fix has been on central for 4 months without regressions.

Comment 8

[BugBot [:suhaib / :marco]]

A patch has been attached on this bug, which was already closed. Filing a separate bug will ensure better tracking. If this was not by mistake and further action is needed, please alert the appropriate party. (Or: if the patch doesn't change behavior -- e.g. landing a test case, or fixing a typo -- then feel free to disregard this message)

Comment 9

[Ryan VanderMeulen [:RyanVM]]

Comment on attachment 9403465 [details]
Bug 1875030 - Update element ranges on the mark stack before and after marking to take account of shifted elements (ESR115)

Approved for 115.12esr.

Comment 10

[Pulsebot]

https://hg.mozilla.org/releases/mozilla-esr115/rev/6f9454132cc1