VisitEntries should decrease the length of mEntries the optimal amount

RESOLVED FIXED in Firefox 57

Status

()

Core
XPCOM
RESOLVED FIXED
4 months ago
4 months ago

People

(Reporter: smaug, Assigned: smaug)

Tracking

(Blocks: 1 bug)

unspecified
mozilla57
Points:
---

Firefox Tracking Flags

(firefox57 fixed)

Details

Attachments

(2 attachments, 3 obsolete attachments)

(Assignee)

Description

4 months ago
Created attachment 8908965 [details] [diff] [review]
visitentries_fix.diff

Currently it may lead to leaks if we end up clearing the whole purple buffer when newLength > oldLength.

The issue clearly happens very rarely (and I haven't even proved it can in practice happen ever currently) since PopLastN would assert in debug builds.

Thanks Adam for noticing this!
Attachment #8908965 - Flags: review?(continuation)
(Assignee)

Comment 1

4 months ago
Created attachment 8908966 [details] [diff] [review]
visitentries_fix.diff
Attachment #8908965 - Attachment is obsolete: true
Attachment #8908965 - Flags: review?(continuation)
Attachment #8908966 - Flags: review?(continuation)
(Assignee)

Comment 2

4 months ago
Comment on attachment 8908966 [details] [diff] [review]
visitentries_fix.diff

Or I guess we just don't want to ++newLength;
since we know we had (oldLength - newLength) empty entries which will be moved to end.
Attachment #8908966 - Attachment is obsolete: true
Attachment #8908966 - Flags: review?(continuation)
(Assignee)

Comment 3

4 months ago
Created attachment 8908967 [details] [diff] [review]
visitentries_fix.diff

remote: View your change here:
remote:   https://hg.mozilla.org/try/rev/f26966d7044e60f09ef2abd7e4cef5750546a6b9
remote: 
remote: Follow the progress of your build on Treeherder:
remote:   https://treeherder.mozilla.org/#/jobs?repo=try&revision=f26966d7044e60f09ef2abd7e4cef5750546a6b9
remote: recorded changegroup in replication log in 0.022s
Attachment #8908967 - Flags: review?(continuation)
Attachment #8908967 - Flags: review?(continuation) → review+
(Assignee)

Updated

4 months ago
Summary: VisitEntries should check not too many new entries were added → VisitEntries should decrease the length of mEntries the optimal amount
Comment on attachment 8908967 [details] [diff] [review]
visitentries_fix.diff

Review of attachment 8908967 [details] [diff] [review]:
-----------------------------------------------------------------

I should look over this more thoroughly...
Attachment #8908967 - Flags: review+ → review?(continuation)
(Assignee)

Comment 5

4 months ago
Created attachment 8909689 [details] [diff] [review]
Same as previous patch, but with commit message
Attachment #8908967 - Attachment is obsolete: true
Attachment #8908967 - Flags: review?(continuation)
Comment on attachment 8909689 [details] [diff] [review]
Same as previous patch, but with commit message

Review of attachment 8909689 [details] [diff] [review]:
-----------------------------------------------------------------

I don't think this patch is correct. We still need to increase newLength if there are entries that were added during traversal. We could not have visited these new entries because we bail out of the previous loop if |&e == &revIter.Get()|, so they have not been included in newLength.

I believe the problematic scenario Adam is pointing out is when our compacting removes, say, 4 entries, but during traversal we added 10 entries, so we end up with a net increase of 6 entries, and so newLength > oldLength.

I believe the correct fix is to change
  mEntries.PopLastN(oldLength - newLength);
into
  if (newLength < oldLength) {
    mEntries.PopLastN(oldLength - newLength);
  }
Attachment #8909689 - Flags: review-
Ok, so, Olli explained this to me over IRC. The issue with my suggestion is that if we remove some entries, but add even more, than the array has even more than newLength entries in it, and we're not shrinking those away. What we'd kind of need is a setLength() API that does something clever.

Also, the reason that Olli's patch is okay is because newLength isn't actually the new length of the array any more, it is the number of entries that were in the buffer at the start, and haven't been removed. So, it is okay to remove the increment in the second loop, because those are new entries, not kept entries. We also don't have to worry about underflow because the number of kept entries can never exceed the initial number of entries. It doesn't end up with extra entries, because oldLength - keptLength is the number of entries we deleted. We never delete new entries.
Comment on attachment 8909689 [details] [diff] [review]
Same as previous patch, but with commit message

Review of attachment 8909689 [details] [diff] [review]:
-----------------------------------------------------------------

Please rename newLength to keptLength or something along those lines. Thanks for explaining this.
Attachment #8909689 - Flags: review- → review+
Also, we should really split this up into a separate data structure that we can write C++ unit tests for! This compacting iteration is quite tricky, with lots of edge cases.
(Assignee)

Comment 10

4 months ago
Created attachment 8910185 [details] [diff] [review]
visitentries_2.diff

Comment 11

4 months ago
Pushed by opettay@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/0ff539e59fb1
VisitEntries should decrease the length of mEntries the optimal amount, r=mccr8

Comment 12

4 months ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/0ff539e59fb1
Status: NEW → RESOLVED
Last Resolved: 4 months ago
status-firefox57: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla57
You need to log in before you can comment on or make changes to this bug.