Closed Bug 1400520 Opened 7 years ago Closed 7 years ago

VisitEntries should decrease the length of mEntries the optimal amount

Categories

(Core :: XPCOM, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla57
Tracking Status
firefox57 --- fixed

People

(Reporter: smaug, Assigned: smaug)

References

Details

Attachments

(2 files, 3 obsolete files)

Attached patch visitentries_fix.diff (obsolete) — Splinter Review
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)
Attached patch visitentries_fix.diff (obsolete) — Splinter Review
Attachment #8908965 - Attachment is obsolete: true
Attachment #8908965 - Flags: review?(continuation)
Attachment #8908966 - Flags: review?(continuation)
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)
Attached patch visitentries_fix.diff (obsolete) — Splinter Review
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+
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)
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.
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
https://hg.mozilla.org/mozilla-central/rev/0ff539e59fb1
Status: NEW → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla57
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: