1102687 - Review memory allocation patterns in safebrowsing code

Status: RESOLVED FIXED

(Toolkit :: Safe Browsing, defect)

Description

[(Away)]

Despite some recent improvements, the safebrowsing code is still the top source of Large OOM crashes. 

I see a lot of code that copies large arrays between callee and caller. In some cases these could be improved such that the caller takes over the callee's data. The arrays that remain should use the SegmentedArray class with segments less than 1MB.

Here are some things I noticed:

Classifier::ApplyTableUpdates
* This function gets an array from LookupCache::GetPrefixes, and (via AugmentAdds) copies the array data to |store|
* Does |store| really need to be heap-allocated?

Classifier::ReadNoiseEntries
* This function gets an array from LookupCache::GetPrefixes, and copies the array data to its out-parameter |aNoiseEntries|

LookupCache::GetPrefixes
* This function gets a C-style array from nsUrlClassifierPrefixSet::GetPrefixes and copies its nsTArray out-parameter. If nsUrlClassifierPrefixSet::GetPrefixes were changed to use an nsTArray, then LookupCache::GetPrefixes could simply pass the array through. (Even better, a SegmentedArray for both)

nsUrlClassifierPrefixSet::LoadFromFd
* If indexSize == 0, we don't clear mIndexDeltas or mIndexPrefixes. Is that intentional? (I can't tell whether LoadFromFd can be called several times)
* Would it help to do a single mIndexDeltas.SetLength() instead of AppendElement() in the for loop? (The recent exponential growth change probably mitigates it)
* Each mIndexDeltas[i] could definitely use a SegmentedArray as their SetLength is a popular OOM site

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: Cumulative heap allocations relating to safebrowsing

Here is some data from downloading the whole safebrowsing database when starting the browser with a new profile. The __GI_qsort_r ones are out of our control -- when you call qsort() glibc apparently does a merge sort, requiring extra space -- and will vary across platforms. But some of the others look like good candidates for improvement, and probably align with dmajor's observations in comment 0.

Comment 2

[Gian-Carlo Pascutto [:gcp]]

>* Does |store| really need to be heap-allocated?

No, but what alternative is there? It's a transient object with unknown-size-in-advance that only exists during an update.

>* This function gets an array from LookupCache::GetPrefixes, and copies the
>array data to its out-parameter |aNoiseEntries|

No, that's not correct. The out-parameter is an empty array that's allocated in the caller.

>LookupCache::GetPrefixes
>* This function gets a C-style array from nsUrlClassifierPrefixSet::GetPrefixes and copies its nsTArray 
>out-parameter. If nsUrlClassifierPrefixSet::GetPrefixes were changed to use an nsTArray, then 
>LookupCache::GetPrefixes could simply pass the array through. (Even better, a SegmentedArray for both)

The fact that it has to call GetPrefixes is unfortunate, but complicated to solve. The fact that GetPrefixes keeps two copies of the array might be an easier win. 

http://dxr.mozilla.org/mozilla-central/source/toolkit/components/url-classifier/LookupCache.cpp#698
Can we do some sort of transfer-of-ownership of the raw data into the nsTArray? I didn't see any way to do that, though.

Changing GetPrefixes to use an nsTArray is AFAIK not possible because it's exposed to JS. I checked and the only user are our tests, so an alternative is to make the "native" function use nsTArray and do the copying in the JS exposed one.

>* If indexSize == 0, we don't clear mIndexDeltas or mIndexPrefixes. Is that intentional? (I can't tell whether LoadFromFd can be called several times)

It's only once (for as long as the objects exist).

>* Would it help to do a single mIndexDeltas.SetLength() instead of AppendElement() in the for loop?

Yes, that's an easy win now that the size is known in advance.

>* Each mIndexDeltas[i] could definitely use a SegmentedArray as their SetLength is a popular OOM site

They're 120 x 2 byte arrays! Are you sure your profiling is right? See https://bugzilla.mozilla.org/show_bug.cgi?id=1046038

Comment 3

[Nicholas Nethercote [inactive]]

> Can we do some sort of transfer-of-ownership of the raw data into the
> nsTArray? I didn't see any way to do that, though.

I don't think you can do that with nsTArray, but if you were to switch to mozilla::Vector you can use the replaceRawBuffer() method.

Comment 4

[(Away)]

(In reply to Gian-Carlo Pascutto [:gcp] from comment #2)
> >* Does |store| really need to be heap-allocated?
> 
> No, but what alternative is there? It's a transient object with
> unknown-size-in-advance that only exists during an update.

Can you not say: HashStore store(aTable, mStoreDirectory);
It's probably minor but it stuck out while I was reading.
 
> >* This function gets an array from LookupCache::GetPrefixes, and copies the
> >array data to its out-parameter |aNoiseEntries|
> 
> No, that's not correct. The out-parameter is an empty array that's allocated
> in the caller.

The spirit is the same: for some period of time, there are two copies of the array.

> Changing GetPrefixes to use an nsTArray is AFAIK not possible because it's
> exposed to JS.

Sorry, my DXR searches didn't see that caller because of the upper/lowercase IDL conversion :(

> >* Each mIndexDeltas[i] could definitely use a SegmentedArray as their SetLength is a popular OOM site
> 
> They're 120 x 2 byte arrays! Are you sure your profiling is right? See
> https://bugzilla.mozilla.org/show_bug.cgi?id=1046038

I'm only going by crash reports. The crashes on that line must be from the 33 release, and the bug you linked says mozilla34. If it's fixed already, that's great!

Comment 5

[Gian-Carlo Pascutto [:gcp]]

https://tbpl.mozilla.org/?tree=Try&rev=1587b0148f08

Comment 6

[Gian-Carlo Pascutto [:gcp]]

Attachment: Presize the urlclassifier PrefixSet delta array on loading. r=

Comment 7

[Gian-Carlo Pascutto [:gcp]]

Attachment: Avoid copying and allocating 3 times in GetPrefixes. r=

Comment 8

[Gian-Carlo Pascutto [:gcp]]

Attachment: Do transient Classifier/HashStore object allocations on the stack. r=

Comment 9

[Gian-Carlo Pascutto [:gcp]]

Attachment: Remove legacy includes from nsUrlClassifierPrefixSet and friends

Comment 10

[(Away)]

I want to spend some extra time walking through part 2. I'll take a closer look on NZ Monday.

Comment 11

[Gian-Carlo Pascutto [:gcp]]

(In reply to David Major [:dmajor] (UTC+13) from comment #4)

> > >* This function gets an array from LookupCache::GetPrefixes, and copies the
> > >array data to its out-parameter |aNoiseEntries|
> > 
> > No, that's not correct. The out-parameter is an empty array that's allocated
> > in the caller.
> 
> The spirit is the same: for some period of time, there are two copies of the
> array.

The out parameter is an empty array in which a very limited number (count param) of specific entries from the return value from GetPrefixes are copied. Either there's a bug in my code which I'm blind to, we're talking about different things, or you misunderstood that.

Comment 12

[(Away)]

Ah, I see. It wasn't obvious from the code that aCount is significantly smaller than the size of the other array. Thanks for the clarification.

Comment 13

[(Away)]

Comment on attachment 8526771 [details] [diff] [review]
Avoid copying and allocating 3 times in GetPrefixes. r=

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

::: toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp
@@ +187,2 @@
>  
>    *aCount = itemCount;

I'm surprised the compiler doesn't complain about assigning uint64_t to uint32_t*.

Comment 14

[Gian-Carlo Pascutto [:gcp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/86048e13f7d7
https://hg.mozilla.org/integration/mozilla-inbound/rev/b1bf9bfbfdc8
https://hg.mozilla.org/integration/mozilla-inbound/rev/24469463b02a
https://hg.mozilla.org/integration/mozilla-inbound/rev/c9a0d4535544

Comment 15

[Gian-Carlo Pascutto [:gcp]]

There's a bunch of extra things we can address once Bug 1102525 lands.

Comment 16

[Gian-Carlo Pascutto [:gcp]]

Let's follow up in:
https://bugzilla.mozilla.org/show_bug.cgi?id=1103857

Comment 17

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/86048e13f7d7
https://hg.mozilla.org/mozilla-central/rev/b1bf9bfbfdc8
https://hg.mozilla.org/mozilla-central/rev/24469463b02a
https://hg.mozilla.org/mozilla-central/rev/c9a0d4535544