Determine the frame structure

Now we can finally put all the pieces together and pass the frame structure into libadblockplus.

Note that there's a big TODO left, but I'm not sure how to best address it: We need to garbage collect and possibly persist referrer mappings.

Garbage collection of some sort is probably necessary so we don't run out of memory with a long-running proxy. I was thinking of a simple priority queue that prioritises long referrer chains over short ones.

I believe that persistence is necessary because clients will cache some requests, therefore we won't be able to build the full referrer chain if ABP restarted in the mean time (that's actually a reproducible problem).

Thoughts?

[Wladimir Palant, 2013-11-25 10:24:41]

Why not use an LRU approach to the referrer mapping?

IMHO, you are overcomplicating. We cannot have 100% precision here. So
persistence is only something I would consider if we determine that it is worth
doing. Also, see comment below.

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
src/org/adblockplus/android/AdblockPlus.java:380: referrers.add(referrer);
Do you think that this is really necessary? We aren't doing exact science here,
it's a heuristic that should work in *most* cases. In other words, a simple
string => string mapping should do, we can overwrite the referrer if we get a
new one.

[Felix Dahlke, 2013-11-27 12:19:32]

Yes, an LRU should definitely do for now.

I don't think we'll get around persisting this in the long term. The cache will
get purged when the app is restarted, while browsers keep caching requests far
beyond that.

Anyway, this should do for now. Deep referrer chains where requests in the
middle get cached are theoretically possible, but I'm not sure how realistic
they are in practice.

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
src/org/adblockplus/android/AdblockPlus.java:380: referrers.add(referrer);
On 2013/11/25 10:24:41, Wladimir Palant wrote:
> Do you think that this is really necessary? We aren't doing exact science
here,
> it's a heuristic that should work in *most* cases. In other words, a simple
> string => string mapping should do, we can overwrite the referrer if we get a
> new one.

Yes, I think it makes sense to not have a single chain per referrer, frames by
ad providers are supposedly used on several sites.

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/jni/...
File jni/abpEngine.cpp (right):

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/jni/...
jni/abpEngine.cpp:45: JNIEnv *env, jobject object);
This and the other changes in this file are unrelated, caused by rebasing.

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
File src/org/adblockplus/android/ABPEngine.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
src/org/adblockplus/android/ABPEngine.java:96: 
This change is unrelated, caused by rebasing.

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
src/org/adblockplus/android/AdblockPlus.java:98: private static final int
MAX_SIZE = 2;
Note that I've set this to 5000, not 2. I'd rather not upload a new patch set
for this since I already added a bunch of comments.

As to how I arrived at 5000: I assumed that each referrer mapping takes on
average around 512 bytes of memory. With 5000 of these, we're at around 2.5 MB
and possibly a little overhead. Seems reasonable.

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
src/org/adblockplus/android/AdblockPlus.java:334: return
preferences.getBoolean("notified_about_acceptable_ads", false);
This change is unrelated, caused by rebasing.

[Wladimir Palant, 2013-11-27 12:59:01]

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
src/org/adblockplus/android/AdblockPlus.java:380: referrers.add(referrer);
On 2013/11/27 12:19:32, Felix H. Dahlke wrote:
> Yes, I think it makes sense to not have a single chain per referrer, frames by
> ad providers are supposedly used on several sites.

Not with the same parameters - they have to know somehow who needs to get paid,
referrers aren't reliable enough for that. IMHO frames with identical URLs
embedded from different websites that are open at the same time should be a very
rare edge case not worth complicating the code over.

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
src/org/adblockplus/android/AdblockPlus.java:98: private static final int
MAX_SIZE = 2;
On 2013/11/27 12:19:33, Felix H. Dahlke wrote:
> As to how I arrived at 5000: I assumed that each referrer mapping takes on
> average around 512 bytes of memory. With 5000 of these, we're at around 2.5 MB
> and possibly a little overhead. Seems reasonable.

I think that "how much memory can we sacrifice" is the wrong logic here. The
question is rather "how many referrer chains can be relevant at any given time?"
Here "relevant" means that the corresponding website is open and might still
load new content into a frame. UI limitations of Android browsers make lots of
open tabs rather unlikely. Also, the web content embedded in Android apps
doesn't tend to have a complicated structure. So if we assume 50 open web
contexts (tabs or apps) each having on average five referrer chains we get 250
as size of this cache - and that's already a very generous estimate. I would
limit the cache to 500 entries, just to be on the safe side. Anything beyond
that doesn't seem to be justified.

Note that the memory overhead is very significant if you store sets rather than
single strings (which you shouldn't, see other comment).

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
src/org/adblockplus/android/AdblockPlus.java:102: super(MAX_SIZE, 0.75f, true);
I think that the first parameter should be MAX_SIZE + 1 here. When the cache is
already full a new entry will be inserted first and only then the least recently
used entry will be evicted.

[Felix Dahlke, 2013-11-27 13:38:59]

Issues addressed/commented.

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5668600916475904/src/...
src/org/adblockplus/android/AdblockPlus.java:380: referrers.add(referrer);
On 2013/11/27 12:59:01, Wladimir Palant wrote:
> On 2013/11/27 12:19:32, Felix H. Dahlke wrote:
> > Yes, I think it makes sense to not have a single chain per referrer, frames
by
> > ad providers are supposedly used on several sites.
> 
> Not with the same parameters - they have to know somehow who needs to get
paid,
> referrers aren't reliable enough for that. IMHO frames with identical URLs
> embedded from different websites that are open at the same time should be a
very
> rare edge case not worth complicating the code over.

Alright, didn't think of that. Makes the code much simpler indeed.

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
src/org/adblockplus/android/AdblockPlus.java:98: private static final int
MAX_SIZE = 2;
On 2013/11/27 12:59:01, Wladimir Palant wrote:
> The
> question is rather "how many referrer chains can be relevant at any given
time?"
> Here "relevant" means that the corresponding website is open and might still
> load new content into a frame.

I think we're still not on the same page here. IMO, we need to cache as many
referrer mappings as possible, simply because browsers will cache intermediate
requests and not make them again in the near future. That's the same reason why
I want to persist these mappings.

http://codereview.adblockplus.org/5172657418928128/diff/5757334940811264/src/...
src/org/adblockplus/android/AdblockPlus.java:102: super(MAX_SIZE, 0.75f, true);
On 2013/11/27 12:59:01, Wladimir Palant wrote:
> I think that the first parameter should be MAX_SIZE + 1 here. When the cache
is
> already full a new entry will be inserted first and only then the least
recently
> used entry will be evicted.

Done.

[Wladimir Palant, 2013-11-27 14:00:29]

http://codereview.adblockplus.org/5172657418928128/diff/5071437253574656/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5071437253574656/src/...
src/org/adblockplus/android/AdblockPlus.java:413: }
Please don't use recursive algorithms where they don't make sense. Note how this
code can allocate an unlimited number of lists, in addition to potentially
overflowing the stack. The iterative approach:

while (url != null)
{
  referrerChain.add(url);
  url = referrerMapping.get(url);
}

However, this is still a DoS vulnerability - a website can easily make us go
into an endless loop (make sure http://example.com/foo.html is recorded as
referrer of http://example.com/bar.html and http://example.com/bar.html as
referrer of http://example.com/foo.html). Limiting the size of referrerChain to
10 entries (?) should be the simplest solution, adding it to the loop condition
will do.

[Felix Dahlke, 2013-11-27 14:47:31]

Issues addressed.

http://codereview.adblockplus.org/5172657418928128/diff/5071437253574656/src/...
File src/org/adblockplus/android/AdblockPlus.java (right):

http://codereview.adblockplus.org/5172657418928128/diff/5071437253574656/src/...
src/org/adblockplus/android/AdblockPlus.java:413: }
On 2013/11/27 14:00:30, Wladimir Palant wrote:
> Please don't use recursive algorithms where they don't make sense. Note how
this
> code can allocate an unlimited number of lists, in addition to potentially
> overflowing the stack. The iterative approach:
> 
> while (url != null)
> {
>   referrerChain.add(url);
>   url = referrerMapping.get(url);
> }
> 
> However, this is still a DoS vulnerability - a website can easily make us go
> into an endless loop (make sure http://example.com/foo.html is recorded as
> referrer of http://example.com/bar.html and http://example.com/bar.html as
> referrer of http://example.com/foo.html). Limiting the size of referrerChain
to
> 10 entries (?) should be the simplest solution, adding it to the loop
condition
> will do.

Valid points, fixed.

[Wladimir Palant, 2013-11-27 15:01:12]

LGTM

[Felix Dahlke, 2013-11-27 15:06:40]

Here's the follow-up for persisting the cache:
https://trello.com/c/FKaiTjta/344-persist-cached-referrer-mappings