Safe-browsing SBAddPrefix from vector to deque.

Safe-browsing SBAddPrefix from vector to deque.

During updates, a large vector of SBAddPrefix is used to make things
more efficient.  This may also be leading to memory fragmentation,
because the vector for most users will be around 5MB.

This converts std::vector<SBAddPrefix> uses to std::deque<SBAddPrefix>.
SBAddPrefixContainer is used to make this indirect.  The major bits of
this are:
 - safe_browsing_store.cc helper functions templated on abstract
   containers rather than vectors of abstract items.
 - safe_browsing_store_file.cc I/O functions generalized to abstract
   containers rather than vectors of abstract items.  [It also works
   for sets!]
 - Convert appropriate cases of iteration-by-index to iterators.

Also revert the following two debuggin changes:
r104974: Histogram large realloc in safe-browsing update.
r105419: Precalculate total size for safe-browsing add_prefixes.

BUG=99056
TEST=Tests, and monitor crash server.


Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=107415

[Scott Hess - ex-Googler, 2011-10-18 22:11:35]

I tried to give a good description for consulting during the review.  For the
most part everything is replacing one thing with an identical something else,
with the only change meant to be material being the definition of
SBAddPrefixContainer.  Since without that change the other changes are just
playing around, I figured it wasn't worth smaller CLs which would make the
noop-ness of things apparent.

[Scott Hess - ex-Googler, 2011-10-20 01:01:21]

I can't figure out the mac_valgrind failure.  They're all in gl* and cg*
functions (drawing code), and seem to change from run to run.  Given where this
code lives, I'm inclined to trust linux_valgrind and not lose any sleep over it.

[Scott Hess - ex-Googler, 2011-10-21 18:23:16]

On 2011/10/18 22:11:35, shess wrote:
> I tried to give a good description for consulting during the review.  For the
> most part everything is replacing one thing with an identical something else,
> with the only change meant to be material being the definition of
> SBAddPrefixContainer.  Since without that change the other changes are just
> playing around, I figured it wasn't worth smaller CLs which would make the
> noop-ness of things apparent.

Ping?  If it would make things easier I can break it down into orthogonal noop
changes.

[jar (doing other things), 2011-10-21 19:10:45]

Mostly nits... but one real question.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_database.cc (right):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_database.cc:1143:
SBAddPrefixContainer prefixes;
Use of SB as a part of the name actually tricked me... I understand it now...
but can look at the style guide and suggest you not use abreviations.  Besides,
the type is only defined in the SafeBrowsing class... so heck... lets drop the
SB.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_database.cc:1173:
SBAddPrefixContainer add_prefixes_result;
It might even be the case that the type name should simply be:
Prefixes

I like using plural to denote a container ;-).

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_database.cc:1352:
browse_store_->GetAddPrefixes(&add_prefixes);
I won't push for all teh names changed to be readable.... but I think this stuff
should be:

GetAdditionalPrefixes(&additional_prefixes).

The word "Add" seems like a verb, but I *think* you need a noun or noun phrase
(...and as I said... you don't have to fix this... but it often makes code more
readable, an susceptible to spotting bugs ;-) )

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store.cc (left):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store.cc:38: typename
std::vector<A>::iterator add_iter = adds->begin();
I'm *not* an expert on templates... but can't you pass in the template type 
std::vector
and then get all the generality you want?

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store.cc (right):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store.cc:21: template <typename CS,
typename CA, typename PredAS, typename PredSA>
I really didn't like these two letter names. The were bad as one letter names...
and this hurt my mind worse.

I also hated the other names PredAS and PredSA, <sigh>, but at least you weren't
changing that code... so perhaps a different CL would be better for them (some
day).

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store_file.cc (left):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store_file.cc:550:
add_prefixes.reserve(add_prefixes_added_);
What happened to this line?

FWIW: I had a heck of a time matching curlies... and think it maps with the if
in line 500.  If it does... it sure we be nice to flip the if vs else around,
and get this tiny guy out of the way first.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store_file.cc (right):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store_file.cc:96:
values->insert(values->end(), value);
It might be clearer to:
values->push_back(value);

[Scott Hess - ex-Googler, 2011-10-21 23:39:32]

This is just a quick high-level response, I'll circle back and make the
SBAddPrefixes change over the weekend or something.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_database.cc (right):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_database.cc:1143:
SBAddPrefixContainer prefixes;
On 2011/10/21 19:10:45, jar wrote:
> Use of SB as a part of the name actually tricked me... I understand it now...
> but can look at the style guide and suggest you not use abreviations. 
Besides,
> the type is only defined in the SafeBrowsing class... so heck... lets drop the
> SB.

SBAddPrefixContainer is defined in global scope in safe_browsing_store.h. 
Someone needs to cover the code and namespace the heck out of it.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_database.cc:1173:
SBAddPrefixContainer add_prefixes_result;
On 2011/10/21 19:10:45, jar wrote:
> It might even be the case that the type name should simply be:
> Prefixes
> 
> I like using plural to denote a container ;-).

I'm reasonable with s/SBAddPrefixContainer/SBAddPrefixes/.  I think I was too
much in the mode of meta-container.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_database.cc:1352:
browse_store_->GetAddPrefixes(&add_prefixes);
On 2011/10/21 19:10:45, jar wrote:
> I won't push for all teh names changed to be readable.... but I think this
stuff
> should be:
> 
> GetAdditionalPrefixes(&additional_prefixes).
> 
> The word "Add" seems like a verb, but I *think* you need a noun or noun phrase
> (...and as I said... you don't have to fix this... but it often makes code
more
> readable, an susceptible to spotting bugs ;-) )

Unfortunately ... sigh.  I hate this code.

The "add" here describes the type of prefix.  These are not additional prefixes,
it is the complete set of prefixes of type "add", which came from an "add"
chunk.  There are also "sub" chunks.  There are also deletions of add chunks and
sub chunks, just to make things more enjoyable.

Perhaps most importantly, the safe-browsing protocol docs use the terms "add"
chunk and "sub" chunk.

At root, the server is sending a set of edits to a database of prefixes.  The
edits are first-class, so you can't simply apply them and move on, because the
server may later say "Delete all the edits I sent in the past" and now you get a
different database of prefixes.  It's terribly mysterious.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store.cc (left):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store.cc:38: typename
std::vector<A>::iterator add_iter = adds->begin();
On 2011/10/21 19:10:45, jar wrote:
> I'm *not* an expert on templates... but can't you pass in the template type 
> std::vector
> and then get all the generality you want?

I don't understand the question.  Sometimes a container of add-prefixes is a
vector, sometimes it's a deque.  The subs container doesn't have those
restraints, but I thought it looked better to be consistent.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store.cc (right):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store.cc:21: template <typename CS,
typename CA, typename PredAS, typename PredSA>
On 2011/10/21 19:10:45, jar wrote:
> I really didn't like these two letter names. The were bad as one letter
names...
> and this hurt my mind worse.
> 
> I also hated the other names PredAS and PredSA, <sigh>, but at least you
weren't
> changing that code... so perhaps a different CL would be better for them (some
> day).

Yeah, I just couldn't think of anything quality to use.  |SubsContainerT|? 
Plain old |Subs| would mean that I shouldn't probably call the parameter of that
type |subs|.  |SubsT|?

Though I suppose I have PredAS and predAS.  PredicateAddSubT?  Sigh.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store_file.cc (left):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store_file.cc:550:
add_prefixes.reserve(add_prefixes_added_);
On 2011/10/21 19:10:45, jar wrote:
> What happened to this line?
> 
> FWIW: I had a heck of a time matching curlies... and think it maps with the if
> in line 500.  If it does... it sure we be nice to flip the if vs else around,
> and get this tiny guy out of the way first.

The reserve() was my earlier change to have the vector pre-sized so no
allocations.  deque does not implement reserve(), because it doesn't make sense.

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
File chrome/browser/safe_browsing/safe_browsing_store_file.cc (right):

http://codereview.chromium.org/8349018/diff/1/chrome/browser/safe_browsing/sa...
chrome/browser/safe_browsing/safe_browsing_store_file.cc:96:
values->insert(values->end(), value);
On 2011/10/21 19:10:45, jar wrote:
> It might be clearer to:
> values->push_back(value);

That is the magic which allows the function to work for vectors and sets (sets
don't have push_back(), but insert(iter, val) inserts at iter if iter is where
it belongs, else falls back to insert(val)).

[Scott Hess - ex-Googler, 2011-10-25 19:54:12]

Oops, turns out if you don't upload, nobody sees it.  I tweaked some of the type
names you had concerns about.

[jar (doing other things), 2011-10-25 21:57:24]

The names are better... I still don't like them much... but perhaps it will
"grow on me" (or make sense if I lived and slept these names).

...and I'm psyched to see how this plays on the canary.

LGTM

[commit-bot: I haz the power, 2011-10-26 18:32:10]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/shess@chromium.org/8349018/10001

[commit-bot: I haz the power, 2011-10-26 19:44:40]

Change committed as 107415