Last Comment Bug 673470 - Replace the sqlite safeb store with a flat file
: Replace the sqlite safeb store with a flat file
Status: RESOLVED FIXED
[MemShrink:P2]
:
Product: Toolkit
Classification: Components
Component: Safe Browsing (show other bugs)
: Trunk
: All All
: -- normal with 1 vote (vote)
: Firefox 17
Assigned To: Gian-Carlo Pascutto [:gcp]
:
Mentors:
Depends on: 725872 744993 750625 797302 825627
Blocks: 383031 441481 568893 669407
  Show dependency treegraph
 
Reported: 2011-07-22 10:53 PDT by Dave Camp (:dcamp)
Modified: 2014-05-27 12:25 PDT (History)
36 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
barely-limping WIP (197.05 KB, text/plain)
2011-07-22 10:53 PDT, Dave Camp (:dcamp)
no flags Details
Chromium license (1.55 KB, text/plain)
2011-08-01 12:06 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details
quick tool to load a complete db (4.11 KB, application/x-javascript)
2011-08-01 15:59 PDT, Dave Camp (:dcamp)
no flags Details
Patch v1. Add the SafeBrowsing store sources (75.69 KB, patch)
2011-08-11 10:35 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch v2. Excorcise SQLite (151.52 KB, patch)
2011-08-11 10:36 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch v3. Run expires (addel) first to the simple testcases still work (5.09 KB, patch)
2011-08-11 10:36 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch v4. Use PrefixSet in LookupCache (29.82 KB, patch)
2011-08-11 10:37 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch v5 Compress the chunk-id information. Cache hashcompletions. (23.52 KB, patch)
2011-08-11 10:38 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 6 Fix the sort ordering when applying/merging subs. (8.75 KB, patch)
2011-08-16 07:14 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 7 Add Copyright headers (22.17 KB, patch)
2011-08-16 07:15 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 1. Add the Safebrowsing store sources (76.48 KB, patch)
2011-09-21 10:36 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 2. Replace SQLite with a flat file store (178.77 KB, patch)
2011-09-21 10:37 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 3. Use PrefixSet for the LookupCache (97.41 KB, patch)
2011-09-21 10:38 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 4. Feed the PrefixSet cache into the Hashstore (12.23 KB, patch)
2011-09-21 10:41 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 1. Add the Safebrowsing store sources (76.46 KB, patch)
2011-10-04 09:27 PDT, Gian-Carlo Pascutto [:gcp]
tony: feedback+
Details | Diff | Review
Patch 2. Replace SQLite by a flat file (178.58 KB, patch)
2011-10-04 09:28 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 3. Use PrefixSet code in new store (143.50 KB, patch)
2011-10-04 09:29 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 3. Use PrefixSet code in new store (151.05 KB, patch)
2011-10-05 01:28 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 3. Use PrefixSet code in new store (153.38 KB, patch)
2011-10-05 12:55 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 4. Folded version of above patches, rebased (294.98 KB, patch)
2011-11-16 05:38 PST, Gian-Carlo Pascutto [:gcp]
dcamp: review-
dcamp: feedback+
Details | Diff | Review
Patch 4. Incorporate review comments (78.59 KB, patch)
2011-11-30 10:12 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 5. Folded version of all patches (314.43 KB, patch)
2011-11-30 10:14 PST, Gian-Carlo Pascutto [:gcp]
dcamp: review-
Details | Diff | Review
Patch 4. Incorporate review comments (78.17 KB, patch)
2011-12-06 08:39 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 5. Fix all style issues (112.10 KB, patch)
2011-12-06 08:41 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 6. Don't call random number generator for noise (6.47 KB, patch)
2011-12-06 08:41 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 7. Add nsCheckSumOutputStream class (24.28 KB, patch)
2011-12-06 08:43 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch. Amalgamation of all the above (335.56 KB, patch)
2011-12-06 08:43 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 1. Add the Safebrowsing store sources (181.31 KB, patch)
2012-01-30 05:56 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 2. Replace SQLite by a flat file (154.41 KB, patch)
2012-01-30 05:57 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 3. Use PrefixSet code in new store (78.39 KB, patch)
2012-01-30 05:58 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 1. Add the optimized store for SafeBrowsing. (76.54 KB, patch)
2012-01-30 06:00 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 2. Replace the SQLite SafeBrowsing store with an optimized store. (181.31 KB, patch)
2012-01-30 06:01 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 3. Use the PrefixSet code in the new LookupCache. (154.41 KB, patch)
2012-01-30 06:02 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 4. Replace the sqlite safebrowsing store with a flat file. (78.39 KB, patch)
2012-01-30 06:03 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 5. Ensure consistent style in UrlClassifier files (111.95 KB, patch)
2012-01-30 06:04 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 6. Don't use the random number generator as key order is already random. (6.54 KB, patch)
2012-01-30 06:04 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 7. Add nsCheckSummedOutputStream and use it. (18.66 KB, patch)
2012-01-30 06:05 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 8. Fixups for bitrot against m-c. (11.28 KB, patch)
2012-01-30 06:05 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch. Amalgamation of all the above (334.07 KB, patch)
2012-01-30 06:06 PST, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 7. Add nsCheckSummedOutputStream and use it. (18.30 KB, patch)
2012-01-31 12:06 PST, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 8. Fixups for bitrot against m-c. (12.34 KB, patch)
2012-01-31 12:07 PST, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch. Amalgamation of all the above (333.88 KB, patch)
2012-01-31 12:10 PST, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 9. Size input buffer to file. Cache active tables. (7.46 KB, patch)
2012-02-02 01:39 PST, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch. Backout part 1 (7.42 KB, patch)
2012-04-19 09:25 PDT, Gian-Carlo Pascutto [:gcp]
akeybl: approval‑mozilla‑aurora+
lukasblakk+bugs: approval‑mozilla‑central+
Details | Diff | Review
Patch. Backout part 2 (7.42 KB, patch)
2012-04-19 09:25 PDT, Gian-Carlo Pascutto [:gcp]
akeybl: approval‑mozilla‑aurora+
lukasblakk+bugs: approval‑mozilla‑central+
Details | Diff | Review
Patch 1. Amalgamation of all the previous patches. (335.03 KB, patch)
2012-08-08 05:26 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 2. Optimize input buffer size. Cache active tables. (8.31 KB, patch)
2012-08-08 05:27 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 3. afeBrowsing fails to update persistent PrefixSet on Windows. (3.06 KB, patch)
2012-08-08 05:29 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 4. Improve OOM handling in UrlClassifier. (2.74 KB, patch)
2012-08-08 05:30 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 5. Clear some big nsTArrays as early as possible in updates. (5.73 KB, patch)
2012-08-08 05:30 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 6. Fix broken UrlClassifier assertion. (1.32 KB, patch)
2012-08-08 05:31 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 7. Cleanup unused cache preferences. (4.27 KB, patch)
2012-08-08 05:32 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 8. Use byteslice coding for SafeBrowsing data. (9.31 KB, patch)
2012-08-08 05:33 PDT, Gian-Carlo Pascutto [:gcp]
gpascutto: review+
Details | Diff | Review
Patch 9. Fix format description in HashStore.cpp (1.47 KB, patch)
2012-08-08 05:35 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 10. Fix a small inconsistency in variable naming. (1.30 KB, patch)
2012-08-08 05:36 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 11. Remove Hash compare functions that we don't actually use. (1.49 KB, patch)
2012-08-08 05:37 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 12. Reorder SubPrefix knockouts wrt. AddCompletes. (1.52 KB, patch)
2012-08-08 05:46 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 13. Provide an option to disable per-client randomization. (25.73 KB, patch)
2012-08-08 05:50 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 14. Fix order of KeyedHash arguments. (3.77 KB, patch)
2012-08-08 05:51 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 15. Remove needless sort calls. Fix comparator bug. (7.62 KB, patch)
2012-08-08 05:58 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 16. Expire SubPrefixes that can't do anything immediately (2.36 KB, patch)
2012-08-08 06:03 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 17. Make the PrefixSet/LookupCache construction infallible again. (5.79 KB, patch)
2012-08-08 06:09 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
justin.lebar+bug: feedback+
Details | Diff | Review
Patch 18. Remove some unneeded PromiseFlatCString. (2.86 KB, patch)
2012-08-08 06:11 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 19. crash in nsUrlClassifierPrefixSet::GetPrefixes. (1.17 KB, patch)
2012-08-08 06:12 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 20. Replace NS_QuickSort use by qsort. (1.47 KB, patch)
2012-08-08 06:13 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 21. Simplify PrefixSet by removing (unneeded) thread safety. (18.27 KB, patch)
2012-08-08 06:25 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 22. Reduce peak RAM. Add slack space. (3.35 KB, patch)
2012-08-09 04:24 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 22. v2 Reduce peak RAM. Add slack space. (3.40 KB, patch)
2012-08-09 10:56 PDT, Gian-Carlo Pascutto [:gcp]
no flags Details | Diff | Review
Patch 22. Skip chunks we already have during merges (1.08 KB, patch)
2012-08-14 06:55 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 22. v2 Skip chunks we already have during merges (2.98 KB, patch)
2012-08-14 15:43 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review
Patch 23. Replace copyright headers to MPL 2.0 (19.61 KB, patch)
2012-08-14 15:44 PDT, Gian-Carlo Pascutto [:gcp]
dcamp: review+
Details | Diff | Review

Description Dave Camp (:dcamp) 2011-07-22 10:53:17 PDT
Created attachment 547744 [details]
barely-limping WIP

I spent a couple days gutting nsUrlClassifierDBService.cpp.  The attached patch starts to replace the sqlite database with store files similar to chrome's safebrowsing implementation.

Very similar - HashStore.cpp in particular is mostly a port of chrome code, and retains their copyright header as a result.  Other parts are heavily influenced.  licensing@ would need to take a look at this before it was landed.

ProtocolParser.[h,cpp] is used to build a series of TableUpdate objects that are applied by the HashStore.  LookupCache maintains a (currently stupid) lookup cache.

Some behavior improvements:
* Updates are a Lot Quicker with this code than the sqlite database - a complete load of the db takes about 30 seconds with this code (mostly network-bound, haven't done tests against local copies of the protocol data yet) vs. 1m:30s with the old code (mostly sqlite-bound).  Haven't done real measurements yet, just wall clock stuff.
* Updates take a lot less memory.  Again, no solid measurements yet but glancing at an xpcshell instance running an entire empty-to-full update shaved 10ish megs off the process.  This is with the very stupid lookup cache (see below), and there are probably other quick wins too.
* The backing storage is completely dumped out of memory after an update, leaving only the lookup cache implementation (similar to the work in bug 669410).
* Backing store is a lot smaller, and is not subject to the whims of sqlite fragmentation.
* Ignores host keys entirely (in the store and in the lookup cache).  I suspect the wins in simplicity and storage here outweigh the benefits of the hostkey cache, but we can revisit.

Things that aren't finished:
* Gethash result caching isn't finished yet.
* My fast-lookup cache is dumb, should use the prefix tree implementation from 669410.
* Haven't run tests lately
* There are quite a few XXX comments that will need to be dealt with.  In particular, ActiveTables() is completely stupid.
* Probably a lot of things are stupid, this is all done hastily.
* Haven't ported checksumming storage files when they are read, that's important.
* All lookups are sent to the worker thread.  It should be pretty easy to send NO lookups to the worker thread, with proper locking around the LookupCache.
* Finally, the documentation suuucks.

Generally, thinks are a bit of a mess.  I hope to fix a few of these in future updates (particularly the documentation thing), but I have some other responsibilities and impending paternity leave.  I wanted to dump this here in case someone wants to pick it up (or pull individual pieces out of it for other work).
Comment 1 Gian-Carlo Pascutto [:gcp] 2011-08-01 12:06:09 PDT
Created attachment 549882 [details]
Chromium license

License applicable to the parts from Chrome.
Comment 2 Dave Camp (:dcamp) 2011-08-01 15:59:34 PDT
Created attachment 549954 [details]
quick tool to load a complete db

I've been using this script to exercise the update code.  Set TESTPROF=[path to a directory] and run under xpcshell to start an update.  It ignores backoff, just keeps asking google for the next update until it gets an empty update.
Comment 3 Dave Camp (:dcamp) 2011-08-01 16:00:04 PDT
The script doesn't clear the profile or db on each run, you'll need to manually delete store files to start from scratch.
Comment 4 Gian-Carlo Pascutto [:gcp] 2011-08-11 10:35:32 PDT
Created attachment 552424 [details] [diff] [review]
Patch v1. Add the SafeBrowsing store sources
Comment 5 Gian-Carlo Pascutto [:gcp] 2011-08-11 10:36:16 PDT
Created attachment 552425 [details] [diff] [review]
Patch v2. Excorcise SQLite
Comment 6 Gian-Carlo Pascutto [:gcp] 2011-08-11 10:36:51 PDT
Created attachment 552426 [details] [diff] [review]
Patch v3. Run expires (addel) first to the simple testcases still work
Comment 7 Gian-Carlo Pascutto [:gcp] 2011-08-11 10:37:21 PDT
Created attachment 552427 [details] [diff] [review]
Patch v4. Use PrefixSet in LookupCache
Comment 8 Gian-Carlo Pascutto [:gcp] 2011-08-11 10:38:24 PDT
Created attachment 552428 [details] [diff] [review]
Patch v5 Compress the chunk-id information. Cache hashcompletions.
Comment 9 Gian-Carlo Pascutto [:gcp] 2011-08-11 11:06:20 PDT
Alright, here is my work in progress. Memory usage is down to 1.9M, and disk usage down to 5.5M for SafeBrowsing. There's a zillion issues still to deal with, but the code works, and should make it usable on Mobile. These need to be applied on top of the patches in bug 669410, v3.

Issues fixed compared to the first WIP:
- Fixed URL parsing so updates using a MAC work.
- Fixed the LookupCache code so it doesn't give a false positive and hence hashcomplete to Google for every single lookup :-)
- Changed the order of processing an update so expires (adddel/subdel) are handled first. This makes the canonical testcase of "ad:1\na:1:32:xxx" not delete itself.
- Rewrote the LookupCache to only store completions and delegate to PrefixSet for everything else.
- Changed the HashStore to deinterleave (yuck!) the prefixes/chunk-ids, and zip the chunk-ids before storing to disk. They have a lot of redundancy so this is a massive saving. The prefixes should be encoded as a PrefixSet, but the code for that needs some extra helpers to be usable here.
- Implemented caching of successful completions, by executing an update that simulates an add. This required some tweaking to the update-handling code to not skip already known chunks, and avoid duplicating hashes within a chunk. An update rebuilds the entire LookupCache, so the old GetHash cache is gone now.
- Slightly better handling of corrupted stores.

Known issues remaining:
- Hundreds of XXX in the code
- All of what Dave said minus what is fixed in the above paragraph
- HashStore should save prefixes in prefix order (instead of chunk) when going to disk, and use PrefixSet for compressing them. Chunks can stay with zlib but will likely lose some compression from not being in chunk order. Should still be better than the other way around.
- mTableUpdates is duplicated in DBService(Worker) and ProtocolParser, I think.
- TableFreshness seems disabled. We prolly need to audit the entire code wrt to the Protocol spec.
- Hashcomplete misses aren't cached. This is important without hostkeys, see the explanation in bug 669407.
- Hashcompletion noise entries are disabled.
- We need to get all the testcases to work again, minus the wrong ones.
- Did I mention there's still lots of XXX in the code?

The very good news is that this splits up a 4000+ line C++ file with 10 or so different classes handling everything, into smaller, much more manageable pieces. But that's not my responsibility, blame :dcamp instead!
Comment 10 Gervase Markham [:gerv] 2011-08-15 09:16:36 PDT
Please put the full Chrome license header at the top of the file. Other than that, this is fine. You'll need a small patch to about:license adding the name of the file (whatever it ends up as) to the list of files covered by the Chrome license copy which is already present there.

Gerv
Comment 11 Gian-Carlo Pascutto [:gcp] 2011-08-16 05:15:12 PDT
>Please put the full Chrome license header at the top of the file. Other than 
>that, this is fine.

What is the "full license header"? Is it this:

// Copyright (c) 2011 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

Should there be a regular Mozilla copyright header, too? (I expect to heavily edit, expand, and perhaps mostly rewrite this file)
Comment 12 Gian-Carlo Pascutto [:gcp] 2011-08-16 07:14:26 PDT
Created attachment 553462 [details] [diff] [review]
Patch 6 Fix the sort ordering when applying/merging subs.

I traced an issue in the new code that was causing the database sizes to differ from the old code. It turns out that all of the code is keeping prefixes sorted by add-chunk, so routines like knockoutsubs and removing matching add prefixes by subs works correctly.

Unfortunately, when taking an update containing subs, adding these new subs to the list of subs has to go by sub-chunk, and the code assumes the entries are sorted. But they're actually sorted by add-chunk, not sub-chunk. This was causing sub updates to go lost, causing our database to be too large and still contain entries that should have been removed.

Attached patch fixes this by taking an alternate sort order before processing sub chunks, and resorting back to add-chunk order afterwards.

Later on, we probably want to keep all lists in prefix order and modify the code to work from that assumption. This would remove the need to sort and resort continuously, as well as integrating better with PrefixSet, which needs prefix order.
Comment 13 Gian-Carlo Pascutto [:gcp] 2011-08-16 07:15:00 PDT
Created attachment 553463 [details] [diff] [review]
Patch 7 Add Copyright headers

Add copyright headers to the new source files.
Comment 14 Gian-Carlo Pascutto [:gcp] 2011-09-21 10:36:22 PDT
Created attachment 561512 [details] [diff] [review]
Patch 1. Add the Safebrowsing store sources
Comment 15 Gian-Carlo Pascutto [:gcp] 2011-09-21 10:37:30 PDT
Created attachment 561513 [details] [diff] [review]
Patch 2. Replace SQLite with a flat file store
Comment 16 Gian-Carlo Pascutto [:gcp] 2011-09-21 10:38:28 PDT
Created attachment 561514 [details] [diff] [review]
Patch 3. Use PrefixSet for the LookupCache
Comment 17 Gian-Carlo Pascutto [:gcp] 2011-09-21 10:41:52 PDT
Created attachment 561515 [details] [diff] [review]
Patch 4. Feed the PrefixSet cache into the Hashstore
Comment 18 Gian-Carlo Pascutto [:gcp] 2011-09-21 10:57:14 PDT
- Fixed an issue in the original protocol parser code that caused SubChunks to have swapped prefixes vs chunk numbers.
- Reworked the sort order to be prefix based and updated the code. This avoids resorting for subs on each update.
- Removed the Add prefixes from the hash store and have the Classifier fetch & forward them from the PrefixSet.

Total size of the (current) store is now 5.3M. 

I'm pondering if maybe the PrefixSet interaction should go directly into HashStore, avoiding that Classifier has to know about it and forward the data as it does now. LookupCache would then only serve as a completion cache. The HashStore would need to be ordered so that the PrefixSet goes to disk first and we only load that on startup. Due to the latter, it might not actually be that much cleaner than what is here now. But it would allow compressing SubPrefixes for some small extra savings.

There's still many XXX's and remarks made above to address, but the functionality is now pretty much complete (save for caching Completion misses), so throwing it out there for a first feedback round.
Comment 19 Gian-Carlo Pascutto [:gcp] 2011-10-04 09:27:31 PDT
Created attachment 564581 [details] [diff] [review]
Patch 1. Add the Safebrowsing store sources
Comment 20 Gian-Carlo Pascutto [:gcp] 2011-10-04 09:28:34 PDT
Created attachment 564583 [details] [diff] [review]
Patch 2. Replace SQLite by a flat file
Comment 21 Gian-Carlo Pascutto [:gcp] 2011-10-04 09:29:43 PDT
Created attachment 564584 [details] [diff] [review]
Patch 3. Use PrefixSet code in new store
Comment 22 Gian-Carlo Pascutto [:gcp] 2011-10-05 01:28:33 PDT
Created attachment 564765 [details] [diff] [review]
Patch 3. Use PrefixSet code in new store

I forgot that I had "temporarily" commented out some tests. This uncomments them, fixes the bugs, and adds back telemetry.
Comment 23 Gian-Carlo Pascutto [:gcp] 2011-10-05 01:55:26 PDT
What remains to be done:

- Noise. That is a Mozilla extension, so I'd rather have this reviewed first and add it separately afterwards.
- There is a number of XXX which I believe aren't critical, such as hashing the store to check for corruption. The SQLite solution didn't do this either, and we do checksum part of them through zlib CRCs.
- I left some XXX's from Dave where I'm not sure what he was referring to, or where I wasn't sure of the best way to clean things up.
- A number of tests are commented out because I believe they're wrong.
- We don't use host caches or fragment caches, and all lookups are in the background thread. We should profile to see which, if any, are worthwhile.
Comment 24 Gian-Carlo Pascutto [:gcp] 2011-10-05 12:55:10 PDT
Created attachment 564966 [details] [diff] [review]
Patch 3. Use PrefixSet code in new store

Fix build issues in optimized mode and on win32. Fix mochitest-5 failures.

https://tbpl.mozilla.org/?tree=Try&usebuildbot=1&rev=ad7f27d16993
Comment 25 Gian-Carlo Pascutto [:gcp] 2011-10-05 12:56:18 PDT
Comment on attachment 564966 [details] [diff] [review]
Patch 3. Use PrefixSet code in new store

This should be the last update for a while, until review comments come in.
Comment 26 James May [:fowl] 2011-10-18 01:00:36 PDT
Is the old urlclassifier3.sqlite supposed to stick after an upgrade? 

I'm running 2011-10-16's nightly and a have both that and urlclassifier.pset.
Comment 27 Gian-Carlo Pascutto [:gcp] 2011-10-18 09:15:54 PDT
None of the patches have been reviewed yet, so they are not in a Nightly.

Even if it did, I'm not clear if we should clean up the old database (yet). See for example bug 499362.
Comment 28 James May [:fowl] 2011-10-19 01:18:07 PDT
Oh. Where did %localappdata%\Mozilla\Firefox\Profiles\xxxxxxx.default\urlclassifier.pset come from then?
Comment 29 Gian-Carlo Pascutto [:gcp] 2011-10-19 06:19:59 PDT
It's from bug 669410.
Comment 30 Dietrich Ayala (:dietrich) 2011-10-31 14:44:05 PDT
Reviewers, what's the ETA on getting to this patch? If it's going to be a while, is there anyone you can suggest for a feedback-r pass first?
Comment 31 Tony Chang (Google) 2011-10-31 16:52:55 PDT
Comment on attachment 564581 [details] [diff] [review]
Patch 1. Add the Safebrowsing store sources

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

This is a lot of code; I wasn't able to do a very thorough review of it.  At a high level, it seems OK.

For new on disk file formats, it would be good to document what the format is supposed to be.  This makes it easier to verify a file correct vs whether there's a bug in the code.  You don't want to be like the mork file format :)  I'm not sure if the best place for this type of documentation is on a web page or in a comment.

::: toolkit/components/url-classifier/ChunkSet.cpp
@@ +40,5 @@
> +
> +nsresult
> +ChunkSet::Unset(uint32 chunk)
> +{
> +  mChunks.RemoveElementSorted(chunk);

If there are duplicates, will they all be removed?  Maybe Set() and Merge() should check for duplicates?

::: toolkit/components/url-classifier/ChunkSet.h
@@ +9,5 @@
> +namespace mozilla {
> +namespace safebrowsing {
> +
> +/**
> + * This is an awful implementation.

Nit: Can you remove this comment or be specific about why it's awful (maybe with suggestions on how to improve it).?

::: toolkit/components/url-classifier/Classifier.cpp
@@ +21,5 @@
> +}
> +
> +Classifier::~Classifier()
> +{
> +}

Nit: Should this call DropStores()?

::: toolkit/components/url-classifier/Classifier.h
@@ +28,5 @@
> +  /**
> +   * Get the list of active tables and their chunks in a format
> +   * suitable for an update request.
> +   */
> +  void TableRequest(nsACString &result);

Nit: In some files you use pointers for out params and in others you pass by ref.  Would be nice to be consistent.

::: toolkit/components/url-classifier/Entries.h
@@ +115,5 @@
> +  uint32 addChunk;
> +  union {
> +    Prefix prefix;
> +    Completion complete;
> +  } hash;

What does this get initialized to?  Where are Prefix and Completion defined?

@@ +117,5 @@
> +    Prefix prefix;
> +    Completion complete;
> +  } hash;
> +
> +  AddComplete() : addChunk(0) {};

Nit: ; is not needed

::: toolkit/components/url-classifier/HashStore.cpp
@@ +394,5 @@
> +  rv = storeFile->AppendNative(mTableName + NS_LITERAL_CSTRING(".sbstore"));
> +  NS_ENSURE_SUCCESS(rv, rv);
> +
> +  nsCOMPtr<nsIOutputStream> out;
> +  rv = NS_NewSafeLocalFileOutputStream(getter_AddRefs(out), storeFile,

Is this safe against power outage during writes?  Would it be safer to write to a temp file and then rename the temp file over the old file?

::: toolkit/components/url-classifier/LookupCache.h
@@ +33,5 @@
> +
> +  // True if we have a complete match for this hash in the table.
> +  bool mComplete;
> +
> +  // True if this is a noise entry. XXX: explain what that is

Nit: Can you do this XXX now?

@@ +46,5 @@
> +};
> +
> +typedef nsTArray<LookupResult> LookupResultArray;
> +
> +// XXX: Inconsistent

Can you elaborate on this more?

::: toolkit/components/url-classifier/ProtocolParser.h
@@ +6,5 @@
> +
> +namespace mozilla {
> +namespace safebrowsing {
> +
> +struct ForwardedUpdate {

Nit: Can we declare this in the class?
Comment 32 Nicholas Nethercote [:njn] (on vacation until July 11) 2011-10-31 17:42:12 PDT
> I'm not sure if the best place for this type of documentation is on a
> web page or in a comment.

If it's in a web page, there should be a comment giving the link to the web page.
Comment 33 Dietrich Ayala (:dietrich) 2011-10-31 17:47:09 PDT
(In reply to Tony Chang (Google) from comment #31)

Thanks for your time on this Tony!

> For new on disk file formats, it would be good to document what the format
> is supposed to be.  This makes it easier to verify a file correct vs whether
> there's a bug in the code.  You don't want to be like the mork file format
> :)  I'm not sure if the best place for this type of documentation is on a
> web page or in a comment.

My preference would be for it to be documented in a comment, as close to the relevant code as is possible. Web pages for things like this tend to age poorly.
Comment 34 Nicholas Nethercote [:njn] (on vacation until July 11) 2011-11-12 12:03:53 PST
dcamp, tony:  you have review/feedback requests here that are over 5 weeks old.  Could you do them this week, please?
Comment 35 Dave Camp (:dcamp) 2011-11-15 15:06:20 PST
I started looking at this, but it would be a lot easier as one big patch (I'm realizing a lot of problems in the first patch are solved in the second and third patches).  The second patch isn't applying cleanly at all for me.  Gian Carlo, could I please get one big megapatch that applies against m-c?
Comment 36 Gian-Carlo Pascutto [:gcp] 2011-11-16 05:38:02 PST
Created attachment 574884 [details] [diff] [review]
Patch 4. Folded version of above patches, rebased
Comment 37 Dave Camp (:dcamp) 2011-11-16 14:51:42 PST
(In reply to Tony Chang (Google) from comment #31)

> > +  nsCOMPtr<nsIOutputStream> out;
> > +  rv = NS_NewSafeLocalFileOutputStream(getter_AddRefs(out), storeFile,
> 
> Is this safe against power outage during writes?  Would it be safer to write
> to a temp file and then rename the temp file over the old file?

SafeLocalFileOutputStream takes care of that, renames the temp file after a successful close.
Comment 38 Dave Camp (:dcamp) 2011-11-16 15:11:27 PST
Comment on attachment 574884 [details] [diff] [review]
Patch 4. Folded version of above patches, rebased

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

Looking good - Tony's comments need to be addressed in addition to the ones I'm adding below:

This patch hasn't reimplemented gethash noise, I think we decided in the security review that we needed to keep that?

::: toolkit/components/url-classifier/ChunkSet.cpp
@@ +72,5 @@
> +
> +nsresult
> +ChunkSet::Set(uint32 chunk)
> +{
> +  mChunks.InsertElementSorted(chunk);

I think this needs to check for duplicates.

::: toolkit/components/url-classifier/ChunkSet.h
@@ +49,5 @@
> +namespace safebrowsing {
> +
> +/**
> + * This is an awful implementation.
> + */

To elaborate a bit here, this implementation just stores chunks as an array of integers, which is wasteful if you have a lot of contiguous chunks.  Should file a followup to improve that.

::: toolkit/components/url-classifier/Classifier.cpp
@@ +70,5 @@
> +}
> +
> +nsresult
> +Classifier::InitKey()
> +{

Can you document what this key is for?

@@ +438,5 @@
> +
> +nsresult
> +Classifier::ApplyTableUpdates(nsTArray<TableUpdate*> &updates,
> +                              const nsACString &table)
> +{

Should document that this consumes/deletes the updates that it applies.

@@ +531,5 @@
> +
> +  // At this point the store is updated and written out to disk, but
> +  // the data is still in memory.  Build our quick-lookup table here.
> +  rv = prefixSet->Build(store->AddPrefixes(), store->AddCompletes());
> +  // XXXnewstore: Deal with failure correctly here.

Does this still need addressing?  If Build() fails what happens (and what should happen?)

@@ +534,5 @@
> +  rv = prefixSet->Build(store->AddPrefixes(), store->AddCompletes());
> +  // XXXnewstore: Deal with failure correctly here.
> +  NS_ENSURE_SUCCESS(rv, rv);
> +#if defined(DEBUG) && defined(PR_LOGGING)
> +  prefixSet->Dump();

Probably want to wrap this with if (LOG_ENABLED())

::: toolkit/components/url-classifier/HashStore.cpp
@@ +1,5 @@
> +//* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
> +// Based on chrome stuff:
> +// Copyright (c) 2010 The Chromium Authors. All rights reserved.
> +// Use of this source code is governed by a BSD-style license that can be
> +// found in the LICENSE file.

I think Comment 11 is still waiting on an answer?

@@ +27,5 @@
> +
> +const uint32 STORE_MAGIC = 0x1231af3b;
> +const uint32 CURRENT_VERSION = 1;
> +
> +Timer::Timer(const char *name) : mName(name) {

Can probably dump this little wall clock test I was doing, particularly if we have good telemetry probes.

@@ +275,5 @@
> +  }
> +
> +  nsCOMPtr<nsISeekableStream> seekable = do_QueryInterface(mInputStream);
> +
> +  // XXX: md5sum

I think we need to do some sort of integrity check here before landing.

::: toolkit/components/url-classifier/LookupCache.cpp
@@ +138,5 @@
> +void
> +LookupCache::Dump()
> +{
> +  if (!LOG_ENABLED())
> +    return;

Oh, I see Dump() takes care of the LOG_ENABLED(), ignore that other comment.

@@ +199,5 @@
> +                                       -1, -1, 0);
> +  NS_ENSURE_SUCCESS(rv, rv);
> +
> +  UpdateHeader();
> +  // XXX: md5sum

Same here, integrity checking is important.

@@ +266,5 @@
> +                                  &buffer,
> +                                  sizeof(Header));
> +  NS_ENSURE_SUCCESS(rv, rv);
> +
> +  // XXX: Sanity check.

Should do this (at least a magic/version check).

::: toolkit/components/url-classifier/LookupCache.h
@@ +54,5 @@
> +
> +#define MAX_HOST_COMPONENTS 5
> +#define MAX_PATH_COMPONENTS 4
> +
> +// XXX: Pretty sure we can clean this up quite a bit.

This comment should either be removed if it's no longer true, or a followup should be filed.

::: toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ +454,5 @@
>  void
>  nsUrlClassifierDBServiceWorker::ResetStream()
>  {
> +  LOG(("ResetStream"));
> +  //XXXnewstore: Audit this

This comment should be removed.

@@ +693,5 @@
>  nsUrlClassifierDBServiceWorker::CancelUpdate()
>  {
> +  LOG(("nsUrlClassifierDBServiceWorker::CancelUpdate"));
> +
> +  // XXXnewstore: fix this.

It looks like CancelUpdate() works now, this XXX can be removed.

@@ +703,4 @@
>      mUpdateObserver->UpdateError(mUpdateStatus);
> +    // XXX: See no point in removing TableFreshness here
> +    // it's not as if its info becomes invalid?
> +    // This does break tests which check this specifically.

iirc we were asked to do this.  If they block a valid site and need to unblock it and updates are failing, they'll be blocking legitimate sites longer (45 minutes rather than the usual 30 minute update latency).

@@ +996,5 @@
> +    // thread.
> +    mDBService->CacheCompletions(mCacheResults.forget());
> +  } else if (mResults->Length() > 0) {
> +    // XXX: this doesn't work with our noise - noise might generate
> +    // hits even if the main hash doesn't.

This will need to be dealth with (once noise is added back)

::: toolkit/components/url-classifier/tests/unit/test_addsub.js
@@ +481,5 @@
>      testSubPartiallyMatches2,
>      testSubsDifferentChunks,
>      testSubsDifferentChunksSameHostId,
>      testExpireLists,
> +    // Chrome's implementation doesn't get these right, we won't either.

Should probably just remove these tests rather than commenting them out.

::: toolkit/components/url-classifier/tests/unit/test_partial.js
@@ +818,5 @@
>        testMixedSizesDifferentDomains,
>        testInvalidHashSize,
> +      // XXX: Changed how caching works with unexpected tables
> +      // testWrongTable,
> +      // XXX: No idea why the current behavior would be wrong

Does this need further investigation?
Comment 39 Tony Chang (Google) 2011-11-16 15:16:11 PST
(In reply to Gian-Carlo Pascutto (:gcp) from comment #11)
> >Please put the full Chrome license header at the top of the file. Other than 
> >that, this is fine.
> 
> What is the "full license header"? Is it this:
> 
> // Copyright (c) 2011 The Chromium Authors. All rights reserved.
> // Use of this source code is governed by a BSD-style license that can be
> // found in the LICENSE file.

The full license is what is found in LICENSE, which is here:
http://git.chromium.org/gitweb/?p=chromium/chromium.git;a=blob;f=LICENSE;h=a6e0dcfbc54451334e1ad2ee859aa2bffaa08692;hb=HEAD
Comment 40 Gian-Carlo Pascutto [:gcp] 2011-11-21 12:09:47 PST
>Does this need further investigation?

testWrongChunk does the following test: it adds an URL to the database, then lets the classifier fire a completion for that URL, and lets the completion server return a hit but with a different chunk number than the database knows. The old test checks if this result is not cached. I see no reason for this behavior in the spec (on the contrary...), but it was likely a limitation in the old database that probably had to "fill in" the completion in the same database row as the original prefix, or something like that. As far as I can tell we should behave correctly in that we'll report owning the chunk back to the server, and it can be expired or subbed by the server as needed. So I think this test is probably wrong.

testWrongTable does something similar, but instead of the wrong chunk it lets the completer reply with a different table. I kept this one, fixed a small bug in my code (a wrong table shouldn't "confirm" a prefix, i.e. if a user has some lists disabled, a completion hit in a non-checked list when probing a checked one shouldn't block the page) but changed the test somewhat too (the completer result will now always be cached and this changes the behavior of the second probe). 

Anyway, I *think* we're fine here.
Comment 41 Dave Camp (:dcamp) 2011-11-21 12:31:41 PST
Yeah, ok I'm agreed.  We should just remove those tests then.
Comment 42 Gian-Carlo Pascutto [:gcp] 2011-11-30 10:12:48 PST
Created attachment 578004 [details] [diff] [review]
Patch 4. Incorporate review comments
Comment 43 Gian-Carlo Pascutto [:gcp] 2011-11-30 10:14:01 PST
Created attachment 578005 [details] [diff] [review]
Patch 5. Folded version of all patches
Comment 44 Gian-Carlo Pascutto [:gcp] 2011-11-30 10:57:44 PST
Incorporated review comments in the 4th patch. Some comments:

>For new on disk file formats, it would be good to document what the format is 
>supposed to be.  This makes it easier to verify a file correct vs whether there's 
>a bug in the code.  You don't want to be like the mork file format :)  I'm not 
>sure if the best place for this type of documentation is on a web page or in a 
>comment.

I added comments about the expected fileformat inside the the LookupCache and HashStore. I didn't document the PrefixSet, as it's in practise defined by the actual datastructure, so this made less sense.

>To elaborate a bit here, this implementation just stores chunks as an array of 
>integers, which is wasteful if you have a lot of contiguous chunks.  Should file a 
>followup to improve that.

We're talking about 50-100k RAM here, only used during updates, so I think we don't need to care about it.

>Nit: In some files you use pointers for out params and in others you pass by ref.  
>Would be nice to be consistent.

There's a discussion on this issue going on right now at:
news://news.mozilla.org/mozilla.dev.platform
As far as I understand, out parameters should be pointers, unless they're strings(?).

There is also some inconsistency in parameters, i.e. my code was mostly aParam but dcamp's code doesn't use that (Dave, is your code simply reflecting what is a more modern style in Mozilla code, or should it be "fixed"). And some files use "type * varname", some "type* varname".

I cleaned *some* of this but there's much inconsistency left. Maybe I should just clean all that up mechanically in a last patch.

>What does this get initialized to?  Where are Prefix and Completion defined?

Note sure about the question here. They're defined right above.

>>Is this safe against power outage during writes?  Would it be safer to write to a temp 
>>file and then rename the temp file over the old file?
>SafeLocalFileOutputStream takes care of that, renames the temp file after a successful close.

I seem to have run into a problem with this and it's causing xpcshell test failures on Windows, so I had to remove the usages. Will file follow-up bugs. Code is XXX'ed.

>> +// XXX: Inconsistent
>Can you elaborate on this more?

This was dcamp's comment, and given that he didn't say anything about it, I just removed it.

>This patch hasn't reimplemented gethash noise, I think we decided in the security review that 
>we needed to keep that?

Implemented this. I ran into an issue. The old noise code would randomly take some hashes from right before and after the hash that hit. I figured that this still allows you to detect the true URL being queried if you can intercept enough of different users, because the true URL is simply the one being probed most. 
A solution I wanted to implement is to fix the prefixes being probed, for example, by rounding the index to the nearest multiple of 4 (instead of making it random) and then requesting those 4 URLs, causing all users to request the same noise URLs, and making the larger scale analysis much more difficult.

Unfortunately, we encode the prefixes with a per-user key to avoid them from colliding on the same sites. But this also means that the prefixes have a different order for every user, so this technique cannot work.

So we can't do anything more than add some random prefixes. You can't say for sure which URL a user requested, but you can still make an educated guess if you can observe enough users.

>Does this still need addressing?  If Build() fails what happens (and what should happen?)

Build() can't really fail, unless it OOM's or whatever, at which point recovery is a mess anyway :-P

>I think we need to do some sort of integrity check here before landing.

Too late :-/

https://bugzilla.mozilla.org/show_bug.cgi?id=702217
https://bugzilla.mozilla.org/show_bug.cgi?id=706049

I figured the following:
- LookupCache needs to protect its header. Corruption in the actual data can't cause crashes and will only cause visible problems on a SHA-256 collision. So it doesn't need further checks.
- HashStore needs MD5s. Unfortunately, integrity checking on an nsIOutputStream on the fly is quite difficult, and I think I'd have needed to rework a lot of code for that. So instead I wrote the code to checksum the file right after writing, and then append the checksum to the file. This doesn't prevent the case where the file gets corrupted between the data being in memory and written out to disk, and the checksum being calculated, but due to how modern OS's work, that seems quite unlikely anyway.
- PrefixSet only sanity checks its header, though it will detect a lot of data corruption because it crosschecks its data with the checksumed HashStore. Right now it can cause a crash if it tries to load corrupted data. This should be fixed for bug 706049 independent of this bug, so that isn't included in the patches here.

I added Telemetry for the completions cached as requested in the security review. 
More stats on completions requested/failed are a bit more complicated, I didn't see
how to do that with current Telemetry. Can file follow up bugs if its deemed important.
Comment 45 Gian-Carlo Pascutto [:gcp] 2011-11-30 23:15:24 PST
https://tbpl.mozilla.org/?tree=Try&rev=9b347db3e3b3
Comment 46 Dave Camp (:dcamp) 2011-12-01 14:44:58 PST
(In reply to Gian-Carlo Pascutto (:gcp) from comment #44)

> >To elaborate a bit here, this implementation just stores chunks as an array of 
> >integers, which is wasteful if you have a lot of contiguous chunks.  Should file a 
> >followup to improve that.
> 
> We're talking about 50-100k RAM here, only used during updates, so I think
> we don't need to care about it.

Yeah, it's not a big deal.

> There's a discussion on this issue going on right now at:
> news://news.mozilla.org/mozilla.dev.platform
> As far as I understand, out parameters should be pointers, unless they're
> strings(?).

Yeah, should follow the recommendations in that thread re: out pointers.

> There is also some inconsistency in parameters, i.e. my code was mostly
> aParam but dcamp's code doesn't use that (Dave, is your code simply
> reflecting what is a more modern style in Mozilla code, or should it be
> "fixed"). And some files use "type * varname", some "type* varname".

No, it's not reflecting a more modern style.  Feel free to fix up new code to aStyle.

> >>Is this safe against power outage during writes?  Would it be safer to write to a temp 
> >>file and then rename the temp file over the old file?
> >SafeLocalFileOutputStream takes care of that, renames the temp file after a successful close.
> 
> I seem to have run into a problem with this and it's causing xpcshell test
> failures on Windows, so I had to remove the usages. Will file follow-up
> bugs. Code is XXX'ed.

I bet it needs some help from the dummy directory provider in the xpcshell tests.  I'll take a look at the Safe LocalFileOutputStream impl and figure out what the tests need to do differently...

> >This patch hasn't reimplemented gethash noise, I think we decided in the security review that 
> >we needed to keep that?
> 
> Implemented this. I ran into an issue. The old noise code would randomly
> take some hashes from right before and after the hash that hit. I figured
> that this still allows you to detect the true URL being queried if you can
> intercept enough of different users, because the true URL is simply the one
> being probed most. 
> A solution I wanted to implement is to fix the prefixes being probed, for
> example, by rounding the index to the nearest multiple of 4 (instead of
> making it random) and then requesting those 4 URLs, causing all users to
> request the same noise URLs, and making the larger scale analysis much more
> difficult.
> 
> Unfortunately, we encode the prefixes with a per-user key to avoid them from
> colliding on the same sites. But this also means that the prefixes have a
> different order for every user, so this technique cannot work.
> 
> So we can't do anything more than add some random prefixes. You can't say
> for sure which URL a user requested, but you can still make an educated
> guess if you can observe enough users.

Yeah, that's a pretty general problem with the noise strategy.  Even with an ideal noise solution, they can still correlate against chrome users to make an educated guess.  Let me think about this for a bit.

> I figured the following:
> - LookupCache needs to protect its header. Corruption in the actual data
> can't cause crashes and will only cause visible problems on a SHA-256

> collision. So it doesn't need further checks.
> - HashStore needs MD5s. Unfortunately, integrity checking on an
> nsIOutputStream on the fly is quite difficult, and I think I'd have needed
> to rework a lot of code for that. So instead I wrote the code to checksum
> the file right after writing, and then append the checksum to the file. This
> doesn't prevent the case where the file gets corrupted between the data
> being in memory and written out to disk, and the checksum being calculated,
> but due to how modern OS's work, that seems quite unlikely anyway.

That's a fairly hefty chunk of extra IO.  How much work would it be to just add a ChecksumWrite(data, length, outputstream, digest) helper?

> - PrefixSet only sanity checks its header, though it will detect a lot of
> data corruption because it crosschecks its data with the checksumed
> HashStore. Right now it can cause a crash if it tries to load corrupted
> data. This should be fixed for bug 706049 independent of this bug, so that
> isn't included in the patches here.

It doesn't crosscheck during lookup though, right?  It's regenerated with each database update though, so maybe that's not as important...
Comment 47 Dave Camp (:dcamp) 2011-12-01 16:59:52 PST
Comment on attachment 578005 [details] [diff] [review]
Patch 5. Folded version of all patches

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

A few quick comments, in addition to the ones above.  Looking good.

r-'ing for the following stuff:

* Fixing SafeLocalFileOutputStream would be nice if possible, let's see if there's a quick fix.
* Same with checksumming as we write the store, rather than as a separate pass.  If that's troublesome we can do it as a followup, but if we decide to do that I need to do one more review pass on that code.
* gcp and I discussed some changes to the noise implementation on IRC, so I didn't review this implementation [will post a summary in a followup comment]/
* InitKey() question below.

::: toolkit/components/url-classifier/Classifier.cpp
@@ +79,5 @@
> + * https://bugzilla.mozilla.org/show_bug.cgi?id=669407#c10
> + */
> +nsresult
> +Classifier::InitKey()
> +{

If this file is corrupt/missing, we need to throw away the prefixset, right?

::: toolkit/components/url-classifier/ProtocolParser.h
@@ +53,5 @@
> +public:
> +  struct ForwardedUpdate {
> +    nsCString table;
> +    nsCString url;
> +  nsCString mac;

Tiny nit, indendation is off here.
Comment 48 Dave Camp (:dcamp) 2011-12-01 17:05:06 PST
The noise change we discussed was:

gcp wanted to use a multiple-of-4 sliding window for choosing noise entries.  He decided that wouldn't work as well as hoped, because each user has an individual hash that mixes up the hash order.  So he fell back to random numbers.  But now he's thinking that the multiple-of-4 sliding window would work as well as random numbers.

I'm not really comfortable r+ing a change to the character of the noise without getting a bit of feedback from the security team.  But given the limited usefulness of the noise to begin with, I don't think we should worry too much about it.
Comment 49 Gian-Carlo Pascutto [:gcp] 2011-12-06 08:39:56 PST
Created attachment 579307 [details] [diff] [review]
Patch 4. Incorporate review comments
Comment 50 Gian-Carlo Pascutto [:gcp] 2011-12-06 08:41:10 PST
Created attachment 579310 [details] [diff] [review]
Patch 5. Fix all style issues
Comment 51 Gian-Carlo Pascutto [:gcp] 2011-12-06 08:41:45 PST
Created attachment 579311 [details] [diff] [review]
Patch 6. Don't call random number generator for noise
Comment 52 Gian-Carlo Pascutto [:gcp] 2011-12-06 08:43:03 PST
Created attachment 579312 [details] [diff] [review]
Patch 7. Add nsCheckSumOutputStream class
Comment 53 Gian-Carlo Pascutto [:gcp] 2011-12-06 08:43:46 PST
Created attachment 579316 [details] [diff] [review]
Patch. Amalgamation of all the above
Comment 54 Gian-Carlo Pascutto [:gcp] 2011-12-06 09:25:59 PST
>No, it's not reflecting a more modern style.  Feel free to fix up new code to 
>aStyle.

I reworked all the affected code to be consistent there, also with in/out parameters (references in, pointers for inout, strings always by reference but const if not modified) as per the style discussion in the newsgroups.

>I bet it needs some help from the dummy directory provider in the xpcshell tests.  
>I'll take a look at the Safe LocalFileOutputStream impl and figure out what the 
>tests need to do differently...

FWIW, the directory seems to exist (I already checked this by logging it and verifying that it was created). I don't know what the problem with that code is.

>That's a fairly hefty chunk of extra IO.  How much work would it be to just add a 
>ChecksumWrite(data, length, outputstream, digest) helper?

There's no simple way to construct such a helper that I can see (that doesn't cause the extra IO, otherwise it's exactly what the first patch did).

It's possible to create a wrapper class that checksums output streams on-the-fly, which I just did now with nsCheckSummingOutputStream. I'm not sure if this is very clean because it directly extends nsFileOutputStream, so it must It must find the nsFileStream headers through a ../../... Maybe we can put this nsCheckSummingOutputStream right into the netwerk/... tree and avoid that? Is this even a real issue?

But on input, it's necessary to first read in the file entirely before you can verify the checksum, and you want to do this before you pass the data on. So you must go over the file twice. The cleanest solution here looked like simply wrapping the input into a nsBufferedStream with a 6Mb buffer, which uses more memory but avoids the duplicate IO altogether. 

>It doesn't crosscheck during lookup though, right?  It's regenerated with each 
>database update though, so maybe that's not as important..

The corruption can't exist for more than 45 minutes (at which point all databases are considered stale), typically can't exist more than 30 minutes (update happens), and is safe because the nsPrefixSet code was audited for bug 706049 to not misbehave even if the underlying data is completely bogus.

>gcp wanted to use a multiple-of-4 sliding window for choosing noise entries.  He decided that wouldn't 
>work as well as hoped, because each user has an individual hash that mixes up the hash order.  So he fell 
>back to random numbers.  But now he's thinking that the multiple-of-4 sliding window would work as well as 
>random numbers.

To elaborate on comment 44, I concluded that we can do no better than send random entries, because there is no concept of "neighboring entries" with each user having randomized prefixes (due to rehashing with a specific per-user key), so the order between each user differs.

However, we had problems with bug 706740, which means that we want to avoid generating random numbers in the nsUrlClassifierDBServiceWorker thread. So I implemented the multiple-of-4 window anyway, in the knowledge that this is equivalent to random picks to an outside attacker/observer, but avoids the need to call the random number generator.

> InitKey() question below.

Good catch, fixed. I also found and fixed a case where the LookupCache detects corruption and resets - it needs to tell this upwards to Classifier, which needs to pass it down to HashStore. This is necessary because the data sits split between LookupCache and HashStore, and having a HashStore without LookupCache causes problems.

I added Telemetry for the number of Prefixes, which seems to expose a bug in LINEAR Histograms :-P

I think I have everything from the review, aside from the nsISafeOutputStream thing.

One thing to investigate in the future: the old nsUrlClassifierPrefix had code to handle lookups on the main thread and wait until the PrefixSet gets loaded (in the worker thread) if necessary. This complicated the code and given that the main thread lookups are entirely gone, we might be able to axe that if we don't plan to reinstate "probe on the main thread". (There is Telemetry included to track the performance of the actual lookup in the worker vs the observed delay in the main thread, including thread ping-pong)
Comment 55 Dave Camp (:dcamp) 2011-12-06 11:23:52 PST
If we want to export the checksumming output stream for xpcom consumers, it probably belongs in netwerk or something rather than url-classifier.  Rather than block this bug on a new exposed api, maybe it would be best to not export a contractid.  You can create it manually with operator new rather than do_CreateInstance).

You can file a followup to export this functionality somewhere more appropriate.
Comment 56 Gian-Carlo Pascutto [:gcp] 2012-01-30 05:56:45 PST
Created attachment 592678 [details] [diff] [review]
Patch 1. Add the Safebrowsing store sources
Comment 57 Gian-Carlo Pascutto [:gcp] 2012-01-30 05:57:18 PST
Created attachment 592679 [details] [diff] [review]
Patch 2. Replace SQLite by a flat file
Comment 58 Gian-Carlo Pascutto [:gcp] 2012-01-30 05:58:30 PST
Created attachment 592680 [details] [diff] [review]
Patch 3. Use PrefixSet code in new store
Comment 59 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:00:19 PST
Created attachment 592682 [details] [diff] [review]
Patch 1. Add the optimized store for SafeBrowsing.
Comment 60 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:01:39 PST
Created attachment 592683 [details] [diff] [review]
Patch 2. Replace the SQLite SafeBrowsing store with an optimized store.
Comment 61 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:02:17 PST
Created attachment 592684 [details] [diff] [review]
Patch 3. Use the PrefixSet code in the new LookupCache.
Comment 62 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:03:16 PST
Created attachment 592686 [details] [diff] [review]
Patch 4. Replace the sqlite safebrowsing store with a flat file.
Comment 63 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:04:02 PST
Created attachment 592687 [details] [diff] [review]
Patch 5. Ensure consistent style in UrlClassifier files
Comment 64 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:04:41 PST
Created attachment 592688 [details] [diff] [review]
Patch 6. Don't use the random number generator as key order is already random.
Comment 65 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:05:23 PST
Created attachment 592690 [details] [diff] [review]
Patch 7. Add nsCheckSummedOutputStream and use it.
Comment 66 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:05:59 PST
Created attachment 592691 [details] [diff] [review]
Patch 8. Fixups for bitrot against m-c.
Comment 67 Gian-Carlo Pascutto [:gcp] 2012-01-30 06:06:49 PST
Created attachment 592692 [details] [diff] [review]
Patch. Amalgamation of all the above
Comment 68 Gian-Carlo Pascutto [:gcp] 2012-01-31 12:06:27 PST
Created attachment 593174 [details] [diff] [review]
Patch 7. Add nsCheckSummedOutputStream and use it.
Comment 69 Gian-Carlo Pascutto [:gcp] 2012-01-31 12:07:14 PST
Created attachment 593175 [details] [diff] [review]
Patch 8. Fixups for bitrot against m-c.
Comment 70 Gian-Carlo Pascutto [:gcp] 2012-01-31 12:10:27 PST
Created attachment 593177 [details] [diff] [review]
Patch. Amalgamation of all the above
Comment 71 Gian-Carlo Pascutto [:gcp] 2012-01-31 12:22:05 PST
I think I'm done for now.

Changes
1) Unbitrot the patches to the changes on m-c (PrefixSet OOM, Memory Reporter).
1) Fixes so the nsISafeOutputStream usage works on Windows.
2) NS_GetSpecialDirectory should run on the main thread, because it causes an enumeration of Directory reporters.
3) I had some occasional orange based on freeing callbacks on the wrong thread. Fixed this with an NS_ReleaseProxy. As far as I can tell this has *always* been broken.

Try run: https://tbpl.mozilla.org/?tree=Try&rev=e75426a42c3e
(The oth orange is telemetry, not due to this patch.)
Comment 72 Dave Camp (:dcamp) 2012-01-31 19:09:05 PST
Comment on attachment 593174 [details] [diff] [review]
Patch 7. Add nsCheckSummedOutputStream and use it.

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

As discussed on IRC, can you file a followup to implement this as a stream that wraps another stream, rather than deriving from the file stream please?
Comment 73 Dave Camp (:dcamp) 2012-01-31 19:14:12 PST
(In reply to Gian-Carlo Pascutto (:gcp) from comment #54)

> But on input, it's necessary to first read in the file entirely before you
> can verify the checksum, and you want to do this before you pass the data
> on. So you must go over the file twice. The cleanest solution here looked
> like simply wrapping the input into a nsBufferedStream with a 6Mb buffer,
> which uses more memory but avoids the duplicate IO altogether. 

If we added an ChecksummingInputStream along the lines of the ChecksummingOutputStream, and added a bailout after reading in all the data the first time, couldn't that work?

As it stands this patch should significantly reduce IO, so I wouldn't hold off landing over that.
Comment 74 Dave Camp (:dcamp) 2012-01-31 19:19:21 PST
Comment on attachment 593177 [details] [diff] [review]
Patch. Amalgamation of all the above

This is a *giant* patch.

With this most recent version I've been through this patch a few times, and I'm pretty confident that it's a solid improvement over our current implementation.   Let's file followups for the checksumming questions I had and get it landed early in the 12 cycle.

Thanks for your hard work on this, Gian-Carlo.
Comment 75 Johnathan Nightingale [:johnath] 2012-02-01 07:11:09 PST
(In reply to Dave Camp (:dcamp) from comment #74)
> Let's file followups for the checksumming questions I had
> and get it landed early in the 12 cycle.

(* early in the 13 cycle - 12 is aurora now. The trains, they run evermore.)
Comment 76 Gian-Carlo Pascutto [:gcp] 2012-02-01 08:57:42 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/44a0dc4fb9ff
Comment 77 Gian-Carlo Pascutto [:gcp] 2012-02-01 09:13:12 PST
File bug 723146 for nsCheckSummedOutputStream improvements.
Comment 78 Gian-Carlo Pascutto [:gcp] 2012-02-01 09:27:23 PST
Filed bug 723153 for cleaning up the old database.
Comment 79 Gian-Carlo Pascutto [:gcp] 2012-02-01 11:15:11 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/ae2d52111205

Regression  Trace Malloc MaxHeap increase 20.3% on CentOS release 5 (Final) Mozilla-Inbound
---------------------------------------------------------------------------------------------
    Previous: avg 26145933.333 stddev 5968.211 of 30 runs up to revision 66fcee339e32
    New     : avg 31442740.000 stddev 21819.555 of 5 runs since revision 44a0dc4fb9ff
    Change  : +5296806.667 (20.3% / z=887.503)
    Graph   : http://mzl.la/xJXSES


I suspect this is the fixed-size 6M buffer in nsBufferedInputStream. Will add a patch to make it dependent on the actual file size.
Comment 80 Gian-Carlo Pascutto [:gcp] 2012-02-02 01:39:36 PST
Created attachment 593756 [details] [diff] [review]
Patch 9. Size input buffer to file. Cache active tables.

The Talos memory use regression almost certainly comes from the fixed size 6M buffer used for avoiding the double read. Now sizing it exactly right.

Performance regressions are trickier because there are multiple potential causes. The worst I found was that we rescan the filesystem on each probe to see which databases are present. This patch checks once on startup and after every update, and caches elsewhere.

From comparing the try run with other try runs I think the regression is gone or reduced.

https://tbpl.mozilla.org/?tree=Try&rev=e102f89a5cf8
Comment 81 Ed Morley [:emorley] 2012-02-02 07:30:47 PST
https://hg.mozilla.org/mozilla-central/rev/44a0dc4fb9ff
Comment 82 Gian-Carlo Pascutto [:gcp] 2012-02-02 07:36:26 PST
This was backed out by
https://hg.mozilla.org/mozilla-central/rev/ae2d52111205
Comment 83 Ed Morley [:emorley] 2012-02-02 07:39:11 PST
Sorry yeah realised as soon as I pressed submit, that the backout was in the same 96 cset merge :-)
Comment 84 Alfred Kayser 2012-02-02 08:22:26 PST
About using mmap?
Comment 85 Gian-Carlo Pascutto [:gcp] 2012-02-02 08:37:54 PST
What would the upsides be? Doesn't give any more guarantee the result is cached, and certainly not faster than regular reads for the purely serial access we do. Obvious downside: not available in a streaming API, so requires a bunch more code to be written.
Comment 88 Jo Hermans 2012-02-05 03:38:28 PST
I noticed that the old url3classifier3.sqlite database wasn't removed when the new folder was added. Also, I see that the files for 'test' provider are always present, next to the ones form Google.

I see that one of the tests (head_urlclassifier.js) has a cleanup procedure - it's exactly that what is missing.
Comment 89 Gian-Carlo Pascutto [:gcp] 2012-02-05 22:11:21 PST
>I noticed that the old url3classifier3.sqlite database wasn't removed when the new 
>folder was added.

See comment 78.

>Also, I see that the files for 'test' provider are always present, next to the 
>ones form Google.

Working as designed, see for example Bug 693389.
Comment 90 Ed Morley [:emorley] 2012-02-08 04:00:52 PST
For those following along, who may not have seen gcp's excellent summary post :-)
http://www.morbo.org/2012/02/new-safebrowsing-backend.html
Comment 91 neil@parkwaycc.co.uk 2012-02-25 10:17:11 PST
Comment on attachment 592682 [details] [diff] [review]
Patch 1. Add the optimized store for SafeBrowsing.

>+  LOG(("Applied %d update(s) to %s.", applied, PromiseFlatCString(store->TableName()).get()));
You call PromiseFlatCString a number of times on store->TableName() which is already flat, so you're in the best case you're just exercising the compiler's PGO code...
Comment 92 Gian-Carlo Pascutto [:gcp] 2012-04-19 09:25:08 PDT
Created attachment 616616 [details] [diff] [review]
Patch. Backout part 1

[Approval Request Comment]
Backout due to bug 744993:

a01cf079ee0b Bug 730247
1a6d008acb4f Bug 729928
f8bf3795b851 Bug 729640
35bf0d62cc30 Bug 726002
a010dcf1a973 Bug 726002
e9291f227d63 Bug 725597
db52b4916cde Bug 673470
173f90d397a8 Bug 673470
Comment 93 Gian-Carlo Pascutto [:gcp] 2012-04-19 09:25:46 PDT
Created attachment 616618 [details] [diff] [review]
Patch. Backout part 2
Comment 94 :Gavin Sharp [email: gavin@gavinsharp.com] 2012-04-19 12:08:35 PDT
This isn't actually on beta yet, is it? Didn't this land in the 13 cycle?
Comment 95 :Gavin Sharp [email: gavin@gavinsharp.com] 2012-04-19 12:09:41 PDT
Sorry, misread the approval flags - nevermind!
Comment 98 Ryan VanderMeulen [:RyanVM] 2012-04-22 11:08:50 PDT
When this re-lands, please also pick up the toolkit/components/url-classifier/Entries.h fix from bug 738533. The patch will be landing without it.
Comment 99 Alex Keybl [:akeybl] 2012-04-24 07:10:57 PDT
Comment on attachment 616616 [details] [diff] [review]
Patch. Backout part 1

Sorry - thought this bug was reopened because the backout was backed out. My mistake. Approved for Aurora 13 (or Beta 13 if the merge occurs before we land).
Comment 101 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:26:02 PDT
Created attachment 650036 [details] [diff] [review]
Patch 1. Amalgamation of all the previous patches.

Carrying forward review. Only changes are rebasing.
Comment 102 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:27:23 PDT
Created attachment 650037 [details] [diff] [review]
Patch 2. Optimize input buffer size. Cache active tables.

Fixes the performance regression seen on the initial landing. Already reviewed => rebased.
Comment 103 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:29:02 PDT
Created attachment 650038 [details] [diff] [review]
Patch 3. afeBrowsing fails to update persistent PrefixSet on Windows.

Originally landed in bug 725597, already reviewed.
Comment 104 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:30:05 PDT
Created attachment 650039 [details] [diff] [review]
Patch 4. Improve OOM handling in UrlClassifier.

Originally landed in bug 726002. Rebased.
Comment 105 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:30:59 PDT
Created attachment 650040 [details] [diff] [review]
Patch 5. Clear some big nsTArrays as early as possible in updates.

Originally landed in 726002, already reviewed, rebased.
Comment 106 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:31:56 PDT
Created attachment 650041 [details] [diff] [review]
Patch 6. Fix broken UrlClassifier assertion.

Bug 729640, already reviewed, rebased.
Comment 107 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:32:49 PDT
Created attachment 650042 [details] [diff] [review]
Patch 7. Cleanup unused cache preferences.

Bug 729928, already reviewed, rebased.
Comment 108 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:33:56 PDT
Created attachment 650044 [details] [diff] [review]
Patch 8. Use byteslice coding for SafeBrowsing data.

Bug 730247, already reviewed, rebased.
Comment 109 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:35:47 PDT
Created attachment 650045 [details] [diff] [review]
Patch 9. Fix format description in HashStore.cpp

The comments describing the sbstore/HashStore on-disk format were erroneous.  This mistakes were found when writing a Python tool to analyze the databases: https://github.com/gcp/sbdbdump
Comment 110 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:36:42 PDT
Created attachment 650046 [details] [diff] [review]
Patch 10. Fix a small inconsistency in variable naming.
Comment 111 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:37:43 PDT
Created attachment 650047 [details] [diff] [review]
Patch 11. Remove Hash compare functions that we don't actually use.
Comment 112 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:46:40 PDT
Created attachment 650049 [details] [diff] [review]
Patch 12. Reorder SubPrefix knockouts wrt. AddCompletes.

We knock out addprefixes that match received subs, but this function also deletes the sub that caused the knockout. If we have previously had a hit on a malware/phishing site, and store an addcomplete for it, we need to knock out that addcomplete. 

Because we use per-client randomization, this is done by generating both randomized and non-randomized subs, where we assign the non-randomized subs to subchunk 0.

This reorders/cleans up the ProcessSubs function to do the Complete removals based on matching prefixes first, clean up the fake Subs (which can only be in SubPrefixes), and then do the normal knockout afterwards (which now only needs to check half as much data).
Comment 113 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:50:08 PDT
Created attachment 650052 [details] [diff] [review]
Patch 13. Provide an option to disable per-client randomization.

Add an option to disable the per-client randomization. This is useful for debugging the protocol and running tests, as it makes the database behavior reproducible.
Comment 114 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:51:45 PDT
Created attachment 650053 [details] [diff] [review]
Patch 14. Fix order of KeyedHash arguments.

In one instance the order of arguments to the per-client randomization function were reversed, causing about half of the prefixes in the database to be wrong. This happens even if per-client randomization is disabled.
Comment 115 Gian-Carlo Pascutto [:gcp] 2012-08-08 05:58:08 PDT
Created attachment 650056 [details] [diff] [review]
Patch 15. Remove needless sort calls. Fix comparator bug.

There were many superfluous sort calls in the existing code. We only need to sort the prefixes once: directly after they have been gone through a Merge() call. (Note that in that function, we could quicksort the new prefixes, and then mergesort them into the already sorted database, but we probably don't need to care for such further optimization right now)

Add assertions and some functions that confirm that all the other code maintains the sorted order of the list, when running in debug mode.

>return *((uint32*)a) - *((uint32*)b);

Dave, this doesn't work :)

None of the sorts were working, causing subprefix knockouts (among others) to be entirely broken.

This also cleans up another part of the file format documentation being wrong.
Comment 116 Gian-Carlo Pascutto [:gcp] 2012-08-08 06:03:33 PDT
Created attachment 650069 [details] [diff] [review]
Patch 16. Expire SubPrefixes that can't do anything immediately

If we receive a SubPrefix that refers to an addChunk that we already have, but the SubPrefix survives the Knockout phase, this must mean the update server already optimized the AddPrefix the Sub was referring to away in order to save bandwidth. The SubPrefix obviously can't ever do anything in this case.

Detect such Prefixes and remove then after the Knockout phase.

It should be noted that the old Firefox Safebrowing code was also doing this optimization. (rv = mPendingSubStore.ExpireAddChunk(tableId, chunkNum);)
Comment 117 Gian-Carlo Pascutto [:gcp] 2012-08-08 06:09:53 PDT
Created attachment 650079 [details] [diff] [review]
Patch 17. Make the PrefixSet/LookupCache construction infallible again.

At some point we made the PrefixSet code be fallible wrt OOM situations. This was possible because the old SQLite backed store could always fall back to just doing disk lookups with SQLite in case there wasn't enough memory to construct our in-memory database.

Because SQLite is gone, and the PrefixSet is now the sole place where the essential AddPrefixes are stored, this fallback is no longer available.

We now apply "Security or DEATH" (again) by making the PrefixSet crash rather than OOM.

The new code only needs to manipulate a dataset half as large as the previous implementation, and generally tries to avoid allocating more memory than necessary. On top of that, our diagnostics for Firefox crashes caused by OOM have improved, so we should be better able to understand and fix things if this happens again.
Comment 118 Gian-Carlo Pascutto [:gcp] 2012-08-08 06:11:00 PDT
Created attachment 650082 [details] [diff] [review]
Patch 18. Remove some unneeded PromiseFlatCString.

Minor code cleanup pointed out in this bug.
Comment 119 Gian-Carlo Pascutto [:gcp] 2012-08-08 06:12:09 PDT
Created attachment 650083 [details] [diff] [review]
Patch 19. crash in nsUrlClassifierPrefixSet::GetPrefixes.

Fixes bug 750625
Comment 120 Gian-Carlo Pascutto [:gcp] 2012-08-08 06:13:38 PDT
Created attachment 650084 [details] [diff] [review]
Patch 20. Replace NS_QuickSort use by qsort.

See notes in this bug and Bug 738533. There's no reason to use NS_QuickSort over qsort, and it simplifies the code.
Comment 121 Gian-Carlo Pascutto [:gcp] 2012-08-08 06:25:34 PDT
Created attachment 650088 [details] [diff] [review]
Patch 21. Simplify PrefixSet by removing (unneeded) thread safety.

The PrefixSet we have now is quite threadsafe and is safe to use (and with minimal blocking) while database updates are in progress. This was a complicated but useful thing to have when we still had an SQLite backend, as it allowed almost every query to be resolved immediately in the main thread without ever blocking or hitting disk (though it might defer a lookup if we are still loading the prefixset from disk).

This patch removes the multithread handling entirely from PrefixSet. This has several advantages: it's both simpler, it supports empty prefixsets without the ugly hacks, and *it cuts the maximum memory requirement in half*. 

The new SafeBrowsing code is more modular, and splits the database into a prefixset per safebrowsing list. It hasn't ever supported probing from within the main thread, and when it originally landed no performance regressions were reported for this, so the complications in prefixset are no longer useful.

In case we ever do need to accelerate lookups by doing them from the main thread, I'd advise to use a seperate, simpler, LRU-style cache for fragments or prefixes, similar to what the code had before we added PrefixSets.
Comment 122 Justin Lebar (not reading bugmail) 2012-08-08 10:26:12 PDT
> We now apply "Security or DEATH" (again) by making the PrefixSet crash rather than OOM.

What's the maximum amount of memory allocated here?
Comment 123 Dave Camp (:dcamp) 2012-08-08 15:30:38 PDT
Comment on attachment 650052 [details] [diff] [review]
Patch 13. Provide an option to disable per-client randomization.

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

If the pref changes, won't databases built before the pref change break silently?
Comment 124 Dave Camp (:dcamp) 2012-08-08 15:31:33 PDT
How are you testing these changes?  Can we get something automated to catch these problems if they spring up again?
Comment 125 Gian-Carlo Pascutto [:gcp] 2012-08-09 00:11:55 PDT
>If the pref changes, won't databases built before the pref change break silently?

Yes. It's meant for debugging, in the "don't toggle this unless you know what you're doing" style.

>How are you testing these changes?  Can we get something automated to catch these 
>problems if they spring up again?

There's a tracking bug for improving the tests to actually test the real protocol:
https://bugzilla.mozilla.org/show_bug.cgi?id=750751

But, what I *really* did here to debug this was to use the tool I linked earlier: https://github.com/gcp/sbdbdump

I compile 2 Firefoxen, one with the old code, one with the new code, both with per-client randomization disabled, and launch them both at the same time pointing to different profiles. I then use the sbdbdump tool to compare the databases from time to time. They should not differ greatly or start to diverge, though they can obviously differ a little due to collisions or the server not sending 100% the same data.

I've simply kept fixing bugs and using the tool to analyze the remaining differences until I can receive and process the entire current set without any unexpected divergence. The current patchset seems to do this, i.e. it will produce the same database contents as the old code.

Based on this, I'm quite confident there are no serious bugs remaining, perhaps more so than if we'd just pass a static set of tests, and I'd consider landing the current code before we have bug 750751. We can keep monitoring the divergence for a few more weeks manually and react if needed. 

I do think bug 727370 should land reasonably soon after, and in the same versions, as this one lands.
Comment 126 Gian-Carlo Pascutto [:gcp] 2012-08-09 01:08:37 PDT
>What's the maximum amount of memory allocated here?

The biggest single set is 400K add prefixes + 170k sub prefixes.

Classifier calls BeginUpdate which calls ReadEntireStore. This means we will have the entire store in RAM at this time:

400k * (uint32 prefix, uint32 chunk)
170k * (uint32 prefix, uint32 chunk, uint32 chunk)

3.2M + 2.0M = 5.2M

ReadSubPrefixes temporarily keeps two copies of the data live during reading (this is fixable). It SetCapacities the nsTArray so there's no loss from that. So peak is 3.2M + 2.0M*2 = 7.2M

It will then call GetPrefixes followed by AugmentAdds, which will load only the add prefixes. So another 400k * uint32 = 1.6M. We might be able to save that by making GetPrefixes aware of the datastructure it's filling into, though that'd make the code uglier. The extra storage is freed immediately at this point. (Peak = 5.2M + 1.6M = 6.8M)

While applying an update, we do an nsTArray AppendElements onto the existing database. I suppose that at worst this can double the memory usage if the nsTArray's capacity needs to resize. So new peak = 6.4M (3.2M*2) + 2.0M = 8.4M, resident = 5.2M

After this point, we could free the SubPrefixes part of the data already, lowering peak and resident by 2.0M (We don't do this right now!)

We then call Build->ConstructPrefixSet. This needs to make a temporary uint32 array, so peak = 5.2M + 1.6M = 6.8M, but it frees the AddPrefixes immediately after (6.8M-3.2M => 3.6M). SetPrefixes/MakePrefixSet then get called, which will allocate 2 uint32 arrays and 1 uint16 one. The worst case is a bit hard to analyze here because it's dependent on the compression, and we're guaranteed to get compression if the data is big. The unrealistic worst case is 400k * (uint32 + uint32) = 3.2M, realistically it'll be closer to 1M (400k * uint16). New peak = 3.6M + 3.2M = 6.8M. Realistic peak = 3.6M + 1M = 4.6M

Because the PrefixSet is resident, I'm doing a Compact() call at this point. This could, worst case, temporarily double the memory usage for one of the uint32 arrays. Peak = 6.8M + 1.6M = 8.4M. (Realistic = 4.6M + 2M = 6.6M)

So, the peak memory usage at 2 points is 8.4M. Because the second occurrence (during PrefixSet construction) is less realistic, the real peak will always happen when we have the data resident and are merging more data into the biggest nsTArray, potentially causing a realloc. 

Fixing this might be possible by adding slack space to process the update at the very beginning. Most updates seem to be <100k entries, so if we allocate that slack space (100k/400k=25%), we would turn that 8.4M peak into 3.2M * 1.25 + 2.0M = 6.0M

The next remaining thing is then 7.2M, requiring fixing ReadSubPrefixes, and 6.8M, requiring GetPrefixes to work with the AddPrefixArray data-structure directly. 

But I'd hope we are able to temporarily allocate 8.4M.
Comment 127 Gian-Carlo Pascutto [:gcp] 2012-08-09 04:24:46 PDT
Created attachment 650503 [details] [diff] [review]
Patch 22. Reduce peak RAM. Add slack space.

This implements the ideas from the previous comment, and should cut the peak memory usage from 8.4M to ~7.5M.  This also avoids a lot of reallocation when merging updates. Unfortunately the "slack" space we preallocate is a magic number, as the only way to know it is to see what Google's servers are actually sending out. It also isn't possible to make it depend on the size of the DB, as the update size you receive isn't correlated to that. 

This means that this patch will cause Mr. Talos to complain to me that we regress MaxHeap by 1.8M, which is quite annoying. (Even though the MaxHeap of a real installation would lowered).

What do you think?
Comment 128 Gian-Carlo Pascutto [:gcp] 2012-08-09 05:15:18 PDT
Relevant (sadly): https://bugzilla.mozilla.org/show_bug.cgi?id=736947
Comment 129 Gian-Carlo Pascutto [:gcp] 2012-08-09 10:56:48 PDT
Created attachment 650619 [details] [diff] [review]
Patch 22. v2 Reduce peak RAM. Add slack space.

Oops.
Comment 130 Justin Lebar (not reading bugmail) 2012-08-09 17:30:16 PDT
> [...]
> But I'd hope we are able to temporarily allocate 8.4M.

Wow, that was impressive.  You earned this f+.  :)
Comment 131 Justin Lebar (not reading bugmail) 2012-08-09 17:33:07 PDT
Comment on attachment 650079 [details] [diff] [review]
Patch 17. Make the PrefixSet/LookupCache construction infallible again.

f=me, but perhaps you want to accumulate (URLCLASSIFIER_PS_FAILURE, 0)?  Otherwise it's hard to tell whether an uptick in failures is due to an uptick in usage or a regression.
Comment 132 Justin Lebar (not reading bugmail) 2012-08-09 17:46:21 PDT
Comment on attachment 650619 [details] [diff] [review]
Patch 22. v2 Reduce peak RAM. Add slack space.

I haven't read the other 21 patches in this bug, so I don't feel comfortable reviewing this.

It's not clear to me that this is completely right, but I have more questions than answers.  There are clownshoes issues -- is 150,000 the right number of elements to expand, or will that leave a bunch of the allocated space unused?  (Maybe nsTArray should just use malloc_usable_size.  In fact, it probably should.)

Also, suppose we go over the additional 150,000 elements.  Now nsTArray will double its already-large size.  This is perhaps worse than the original behavior.  How confident are you that we'll stay within the 150,000 elements?  Is it worth adding telemetry for this?

I'll take another look in the morning, perhaps with all the patches applied to my tree so I have some idea what the heck is going on.  :)
Comment 133 Gian-Carlo Pascutto [:gcp] 2012-08-09 22:26:55 PDT
>There are clownshoes issues -- is 150,000 the right number of elements to expand, 
>or will that leave a bunch of the allocated space unused?  

For most updates, that will leave part of that space unused. For the test databases, it will leave 149999 of them ununsed, hence the expected Talos regression in our tests.

>Also, suppose we go over the additional 150,000 elements.  Now nsTArray will 
>double its already-large size.

Unless I misread the nsTArray source, that won't happen. The array is added to via AppendElement*s* calls, which does a single, up-front SetCapacity to the size of both arrays added. So the behavior shouldn't be worse than what we have.

>How confident are you that we'll stay within the 150,000 elements?  Is it worth 
>adding telemetry for this?

Might be a good idea.

I don't have a large attachment to this patch because I agree it's not particularly elegant. For what it's worth, Chrome switched to deque's recently: http://src.chromium.org/viewvc/chrome/trunk/src/chrome/browser/safe_browsing/safe_browsing_store.cc?revision=107415&view=markup

But as far as I know such modern STL functionality is not available in our codebase?
Comment 134 Dave Camp (:dcamp) 2012-08-10 08:28:12 PDT
Would it make sense to handle patch 22 (maybe alongside patch 17) as a separate bug?
Comment 135 Gian-Carlo Pascutto [:gcp] 2012-08-10 08:32:15 PDT
I'd take 17 with this one (it's made possible by the rewrite). Patch 22 is optional, we can revisit it if we see OOMs.

Looks like we're ready to land? I'll keep the database compare running over the weekend. Meanwhile we can see if Google replies regarding the per-client randomization. If we can get rid of that, I'd do it here too, as it simplifies many of the code that this adds.
Comment 136 Dave Camp (:dcamp) 2012-08-10 08:34:31 PDT
(In reply to Gian-Carlo Pascutto (:gcp) from comment #125)
> Based on this, I'm quite confident there are no serious bugs remaining,
> perhaps more so than if we'd just pass a static set of tests, and I'd
> consider landing the current code before we have bug 750751. We can keep
> monitoring the divergence for a few more weeks manually and react if needed. 

This isn't ideal, but: this patch doesn't regress the poor testing state of the safebrowsing code, it's a better basis on which to build testing code, and it's a pretty big overall win.  I do hope we can get attention on bug 750751 sooner rather than later though.

> I do think bug 727370 should land reasonably soon after, and in the same
> versions, as this one lands.

Agreed.

(In reply to Gian-Carlo Pascutto (:gcp) from comment #135)
> I'd take 17 with this one (it's made possible by the rewrite). Patch 22 is
> optional, we can revisit it if we see OOMs.

OK.  We should probably open a followup bug, easy for a patch on this bug to get lost in the noise.

> Looks like we're ready to land? 

I think so.
Comment 137 Justin Lebar (not reading bugmail) 2012-08-10 09:05:07 PDT
Tackling patch 22 in a separate bug sounds good to me.  I'll follow up once it's filed.
Comment 138 :Gavin Sharp [email: gavin@gavinsharp.com] 2012-08-11 21:44:26 PDT
(In reply to Gian-Carlo Pascutto (:gcp) from comment #135)
> Meanwhile we can see if Google replies regarding the per-client
> randomization. If we can get rid of that, I'd do it here too, as it
> simplifies many of the code that this adds.

I must be missing some context, but talk of getting rid of the randomization seems surprising. I'd like to hear more about this (ideally in a new bug). Seems like we're straying pretty far away from the summary at this point, so I think you should move as much work as you can into new bugs.
Comment 139 Gian-Carlo Pascutto [:gcp] 2012-08-12 02:33:48 PDT
The randomization is much harder to deal with in the new code because we don't store the non-randomized hashes any more, so it's closely related to this bug. Likewise, removing the randomization will require blowing all the databases away a second time, because we can't recover the original data.

For this reason, it should preferably land at the same time as this bug, even though we can certainly track it in a separate bug.
Comment 140 Justin Lebar (not reading bugmail) 2012-08-13 20:53:26 PDT
Comment on attachment 650619 [details] [diff] [review]
Patch 22. v2 Reduce peak RAM. Add slack space.

Clearing f?, since we're going to handle this in a separate bug (right?).

(I had another look at the relevant tarray code, and I think this is basically fine, btw.)
Comment 141 Gian-Carlo Pascutto [:gcp] 2012-08-14 06:55:32 PDT
Created attachment 651753 [details] [diff] [review]
Patch 22. Skip chunks we already have during merges

It's potentially possible to get an empty chunk (optimized away) in one update, and get it another time (not empty) in an older update. This means that we can both a) store information that is unneeded b) because we drop SubPrefix entries belonging to an addchunk we have, after we finish knockout, we potentially won't have the SubPrefixes to knock out the now useless data when we receive that addchunk again.

Skip processing chunks we already have. It's a performance optimization, too.

The old code also had this behavior, in this snippet:

  if (!InsertChunkId(mCachedAddChunks, chunkNum)) {
    LOG(("Ignoring duplicate add chunk %d in table %d", chunkNum, tableId));
    return NS_OK;
  }

With this patch, after several days, I still get a 100% match on the phishing database, one single missing AddPrefix in the malware database (no idea what causes that one...collision?), and 36 missing SubPrefixes that all refer to an AddChunk so old that the clients can never receive it. The latter looks to me like one client got a slightly more recent update than the other one, where those subs were already optimized away. 

I'm slightly puzzled by that one missing Prefix, but this doesn't look problematic enough that it'd stop me from landing. (And I think isolating that difference *will* likely need Bug 750751 to get 100% reproducible updates)
Comment 142 :Gavin Sharp [email: gavin@gavinsharp.com] 2012-08-14 11:40:52 PDT
(In reply to Gian-Carlo Pascutto (:gcp) from comment #139)
> The randomization

Sorry, I think I was just confused about what you meant when you referred to "randomization". I thought you were referring to the gethashnoise code, but it sounds like you're referring to something else entirely.
Comment 143 Gian-Carlo Pascutto [:gcp] 2012-08-14 15:43:19 PDT
Created attachment 651920 [details] [diff] [review]
Patch 22. v2 Skip chunks we already have during merges

There was a bug in the previous patch wrt to Completes: they will appear with the chunk of the corresponding Prefix set (which we will have), but they should not be skipped.
Comment 144 Gian-Carlo Pascutto [:gcp] 2012-08-14 15:44:31 PDT
Created attachment 651922 [details] [diff] [review]
Patch 23. Replace copyright headers to MPL 2.0

Last one before landing.

Try run of all the above:
https://tbpl.mozilla.org/?tree=Try&rev=2dd3c6ca79f3
Comment 146 Gian-Carlo Pascutto [:gcp] 2012-08-15 00:32:11 PDT
Bug 782887, bug 723153, bug 727370 and bug 750751 will contain the further development in this feature (if this doesn't get backed out - which I truly hope won't)
Comment 147 :Ms2ger 2012-08-15 09:01:05 PDT
uint32? :/
Comment 150 Ed Morley [:emorley] 2012-08-15 09:59:55 PDT
On this bug and some of the dependants that landed at the same time, the target milestone was still set to mozilla13. Please can you check when landing on inbound that the milestone is correct (or else leave it blank and the new merge tool will choose the current milestone) :-)

Note You need to log in before you can comment on or make changes to this bug.