Closed Bug 914296 (FaviconRevamp) Opened 11 years ago Closed 11 years ago

Make Favicon caching more intelligent

Categories

(Firefox for Android Graveyard :: Favicon Handling, defect)

All
Android
defect
Not set
normal

Tracking

(relnote-firefox 27+)

RESOLVED FIXED
Firefox 27
Tracking Status
relnote-firefox --- 27+

People

(Reporter: ckitching, Assigned: ckitching)

References

Details

(Whiteboard: [qa+])

Attachments

(1 file, 36 obsolete files)

129.32 KB, patch
rnewman
: review+
Details | Diff | Splinter Review
As requested, splitting the major Favicon caching overhaul out of Bug 888326 into its own bug, to facilitate easier reporting of problems it may introduce.
Attachment #801724 - Flags: review?(margaret.leibovic)
Depends on: 888326
Attachment #801724 - Flags: feedback?(bnicholson)
Fixing the bitrot caused by review changes in Bug 888326.
Attachment #801724 - Attachment is obsolete: true
Attachment #801724 - Flags: review?(margaret.leibovic)
Attachment #801724 - Flags: feedback?(bnicholson)
Attachment #801760 - Flags: review?(margaret.leibovic)
Attachment #801760 - Flags: feedback?(bnicholson)
Apologies for the spam. Spotted a bug in this patch, uploading a fix.
Attachment #801760 - Attachment is obsolete: true
Attachment #801760 - Flags: review?(margaret.leibovic)
Attachment #801760 - Flags: feedback?(bnicholson)
Attachment #802078 - Flags: review?(margaret.leibovic)
Attachment #802078 - Flags: feedback?(bnicholson)
Added more sensible URL fallback strategy (The one desktop Firefox appears to use, in fact.).
Attachment #802078 - Attachment is obsolete: true
Attachment #802078 - Flags: review?(margaret.leibovic)
Attachment #802078 - Flags: feedback?(bnicholson)
Attachment #802155 - Flags: review?(margaret.leibovic)
Attachment #802155 - Flags: feedback?(bnicholson)
Comment on attachment 802155 [details] [diff] [review]
V3 - Bugfix - Add more intelligent caching to the Favicons system.

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

I need to take a break, but I've started to look through this, and here are the comments I have so far.

I'm hoping bnicholson will help me out :)

::: mobile/android/base/BrowserApp.java
@@ +706,5 @@
>                  if (url == null || title == null) {
>                      return true;
>                  }
>  
> +                Favicons.getFaviconForSize(url, tab.getFaviconURL(), 128, LoadFaviconTask.FLAG_PERSIST,

I commented about this in your patch for bug 914027, but we can fix it here if this is going to land first... let's pull this 128 value into a constant.

@@ +1333,5 @@
>      /* Favicon methods */
>      private void loadFavicon(final Tab tab) {
>          maybeCancelFaviconLoad(tab);
>  
> +        int flags = ((tab.isPrivate() || tab.getErrorType() != Tab.ErrorType.NONE) ? 0 : LoadFaviconTask.FLAG_PERSIST);

Same thing about getting rid of the extra parens.

::: mobile/android/base/db/BrowserDB.java
@@ +241,5 @@
>      public static void removeReadingListItemWithURL(ContentResolver cr, String uri) {
>          sDb.removeReadingListItemWithURL(cr, uri);
>      }
>  
> +    public static Bitmap getFaviconForUrl(ContentResolver cr, String aFaviconURL) {

Same comment from the other bug about the a prefixes.

::: mobile/android/base/db/BrowserProvider.java
@@ +3019,5 @@
>          values.put(Favicons.DATE_CREATED, now);
>          values.put(Favicons.DATE_MODIFIED, now);
> +
> +        // Attempting to insert with no Favicon URL specified - fallback to using the page URL.
> +        // (Workaround for the odd behaviour of bundled Favicons which are added in this way.)

So this is only an issue for those bundled favicons? Can we file a follow-up to include a URL with those icons so that we don't need this workaround?

::: mobile/android/base/db/LocalBrowserDB.java
@@ +696,5 @@
>                    new String[] { String.valueOf(id) });
>      }
>  
>      @Override
> +    public Bitmap getFaviconForUrl(ContentResolver cr, String aFaviconURL) {

While you're in here, let's add some documentation about what faviconURL is.

::: mobile/android/base/favicons/Favicons.java
@@ +67,5 @@
> +     * If a result is instantly available from the cache, it is returned and the listener is invoked.
> +     * Otherwise, the result is drawn from the database or network and the listener invoked when the
> +     * result becomes available.
> +     *
> +     * @param aPageURL Page URL for which a Faviocn is desired.

Typo: favicon

@@ +76,5 @@
> +     */
> +    public static int getFaviconForSize(String aPageURL, int aTargetSize, int flags, OnFaviconLoadedListener aListener) {
> +        return getFaviconForSize(aPageURL, getFaviconUrlForPageUrl(aPageURL), aTargetSize, flags, aListener);
> +    }
> +    public static int getFaviconForSize(String aPageURL, String aFaviconURL, int aTargetSize, int flags, OnFaviconLoadedListener aListener) {

These method signatures are a bit confusing. It looks like the first one is only used in HomeFragment.

I would prefer we just continue to get the favicon URL there to pass in, and just have one method signature for getFaviconForSize.

Also, remember to add a @param comment for the faviconURL param.

@@ +221,5 @@
> +                return targetURL;
> +            }
> +        }
> +
> +        targetURL = BrowserDB.getFaviconUrlForHistoryUrl(sContext.getContentResolver(), aPageURL);

You should add a comment to the top of this method saying it performs DB operations, so should only be called in the background.

@@ +338,5 @@
> +     * @param aURL The URL of the Favicon, to be used as the cache key for the colour value.
> +     * @return The dominant colour of the provided Favicon.
> +     */
> +    public static int getFaviconColor(Bitmap image, String aURL) {
> +        Integer color = sFaviconsCache.getDominantColour(aURL);

Please use the en-US spelling of color in method/variable names to be consistent (using en-GB in comments is fine).

::: mobile/android/base/home/HomeFragment.java
@@ +240,5 @@
>                  }
>              };
>  
> +            // Fetch the largest cacheable icon size - we like nice high resolution shortcuts.
> +            Favicons.getFaviconForSize(mUrl, 128, LoadFaviconTask.FLAG_PERSIST, listener);

I mentioned above that I think you should just keep the getFaviconUrlForPageUrl in here, but if you didn't do that, you'd need to change this to make sure the onPostExecute part is still run on the main thread, not in the background (in fact, an AsyncTask wouldn't really make sense here anymore).
(In reply to :Margaret Leibovic from comment #4)
> ::: mobile/android/base/db/BrowserDB.java
> @@ +241,5 @@
> >      public static void removeReadingListItemWithURL(ContentResolver cr, String uri) {
> >          sDb.removeReadingListItemWithURL(cr, uri);
> >      }
> >  
> > +    public static Bitmap getFaviconForUrl(ContentResolver cr, String aFaviconURL) {
> 
> Same comment from the other bug about the a prefixes.

I don't think this is a good idea. The prefix convention prevents method arguments from overloading instance properties on the object, or static variables that are also in scope. Such overloading can be a cause of sublte bugs.
Not a problem for me - my IDE points out when such madness occurs - but removing the extra safety seems unwise.

Anyway, new version of the patches will remove all prefixes as requested.
 
> ::: mobile/android/base/db/BrowserProvider.java
> @@ +3019,5 @@
> >          values.put(Favicons.DATE_CREATED, now);
> >          values.put(Favicons.DATE_MODIFIED, now);
> > +
> > +        // Attempting to insert with no Favicon URL specified - fallback to using the page URL.
> > +        // (Workaround for the odd behaviour of bundled Favicons which are added in this way.)
> 
> So this is only an issue for those bundled favicons? Can we file a follow-up
> to include a URL with those icons so that we don't need this workaround?

This one is a pain. Remember how we switched from caching based on page URLs to caching based on Favicon URLs? Same rule applied to the Favicon database.
Turns out, the favicon database has fields for both page URL and favicon URL. I switched to keying favicons by favicon URL - but this breaks the default bookmark entries, because they are wrong. The default bookmark entries do not populate the favicon URL field, just the page URL one. This is exceptionally annoying, because it means queries to the favicon database have to fall back to checking page URL as well as checking Favicon URL.

This change makes the other field be populated so it hits first time. It's not clear what the proper solution is, since changing the database that's been deployed to millions of phones for a long time isn't simple.

> @@ +338,5 @@
> > +     * @param aURL The URL of the Favicon, to be used as the cache key for the colour value.
> > +     * @return The dominant colour of the provided Favicon.
> > +     */
> > +    public static int getFaviconColor(Bitmap image, String aURL) {
> > +        Integer color = sFaviconsCache.getDominantColour(aURL);
> 
> Please use the en-US spelling of color in method/variable names to be
> consistent (using en-GB in comments is fine).

Ick. I didn't even notice I'd done that. Force of habit, I guess.

> ::: mobile/android/base/home/HomeFragment.java
> @@ +240,5 @@
> >                  }
> >              };
> >  
> > +            // Fetch the largest cacheable icon size - we like nice high resolution shortcuts.
> > +            Favicons.getFaviconForSize(mUrl, 128, LoadFaviconTask.FLAG_PERSIST, listener);
> 
> I mentioned above that I think you should just keep the
> getFaviconUrlForPageUrl in here, but if you didn't do that, you'd need to
> change this to make sure the onPostExecute part is still run on the main
> thread, not in the background (in fact, an AsyncTask wouldn't really make
> sense here anymore).

Ah! These comments made me notice that it's possible to do away entirely with that async task, and also showed me a subtle bug in the favicon URL fallback logic in the new LoadFaviconTask. Well spotted!
The revised patch - fixing the issues you mentioned (And a few more weirdnesses I encountered myself, to boot.)
Attachment #802155 - Attachment is obsolete: true
Attachment #802155 - Flags: review?(margaret.leibovic)
Attachment #802155 - Flags: feedback?(bnicholson)
Attachment #802832 - Flags: review?(margaret.leibovic)
Attachment #802832 - Flags: feedback?(bnicholson)
Deorangifying.
Attachment #802832 - Attachment is obsolete: true
Attachment #802832 - Flags: review?(margaret.leibovic)
Attachment #802832 - Flags: feedback?(bnicholson)
Attachment #803264 - Flags: review?(margaret.leibovic)
One line change to prevent try from exploding about:blank was causing exceptions. No longer.
Attachment #803264 - Attachment is obsolete: true
Attachment #803264 - Flags: review?(margaret.leibovic)
Attachment #803296 - Flags: review?(margaret.leibovic)
Attachment #803296 - Flags: feedback?(bnicholson)
Comment on attachment 803296 [details] [diff] [review]
V6 - Enhance - Add more intelligent caching to the Favicons system.

I also want to get feedback from lucasr on this.
Attachment #803296 - Flags: feedback?(lucasr.at.mozilla)
Comment on attachment 803296 [details] [diff] [review]
V6 - Enhance - Add more intelligent caching to the Favicons system.

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

Drove by. Not entirely though.

::: mobile/android/base/favicons/cache/FaviconCacheKey.java
@@ +13,5 @@
> +    private final int mImageSize;
> +
> +    public FaviconCacheKey(String faviconURL, int imageSize) {
> +        if (faviconURL == null) {
> +            throw new IllegalArgumentException("Null FaviconURL in FaviconCacheKey - you're gonna have a bad time.");

Probably needs an ASCII art of joker. But that's okay! :P

@@ +17,5 @@
> +            throw new IllegalArgumentException("Null FaviconURL in FaviconCacheKey - you're gonna have a bad time.");
> +        }
> +        if (imageSize <= 0) {
> +            throw new IllegalArgumentException("Invalid imageSize:"+imageSize+" in FaviconCacheKey - you're gonna have a bad time.");
> +        }

Spaces when using " + " .

@@ +29,5 @@
> +        if (!(obj instanceof FaviconCacheKey)) {
> +            return false;
> +        }
> +
> +        FaviconCacheKey target = (FaviconCacheKey) obj;

This should probably be inside the if() part. Somehow | if (!(xxx instanceof YYY)) | doesnt feel good. Better to use | if (xxx instanceof YYY) |

::: mobile/android/base/home/HomeFragment.java
@@ +4,5 @@
>   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
>  
>  package org.mozilla.gecko.home;
>  
> +import static org.mozilla.gecko.favicons.cache.FaviconCache.LARGEST_CACHABLE_FAVICON_SIZE;

We don't generally use static imports. The code path below is not like "Math.PI". We can use it as FaviconCache.LARGEST_IDENTIFIER_I_HAVE_SEEN; ;)

::: mobile/android/base/home/TopBookmarksAdapter.java
@@ +4,5 @@
>   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
>  
>  package org.mozilla.gecko.home;
>  
> +import android.util.Log;

No logs seen.

::: mobile/android/base/home/TwoLinePageRow.java
@@ +5,5 @@
>  
>  package org.mozilla.gecko.home;
>  
> +import android.os.Build;
> +import android.util.Log;

No logs seen.

@@ +202,5 @@
> +        // bar view - this is the equivalent of getDisplayTitle() in Tab.java
> +        setTitle(TextUtils.isEmpty(title) ? url : title);
> +
> +        // Prepare the listener to receive the result of the Favicon acquisition attempt.
> +        final OnFaviconLoadedListener faviconListener = new OnFaviconLoadedListener() {

Since this is common for all, and it has no dependency on anything in this method, it's better to create this listener as a "private final" member of the class and use it. Putting it here will create this every time the method is executed.

@@ +205,5 @@
> +        // Prepare the listener to receive the result of the Favicon acquisition attempt.
> +        final OnFaviconLoadedListener faviconListener = new OnFaviconLoadedListener() {
> +            @Override
> +            public void onFaviconLoaded(String aURL, Bitmap favicon) {
> +                setFaviconWithUrl(favicon, aURL);

We don't use "aURL" in the java world. It's used only in the Gecko world (and old java world). please use "url".
Over in Bug 905685, lucasr appears to have tried to solve some of the same problems as are solved here. Chiefly, the incremental loading of Favicons.
This slightly altered edition of his patch removes a lot of now-redundant code from about:home.
Attachment #803365 - Flags: review?(margaret.leibovic)
After much, much discussion with bnicholson about this, I present a revised patch, which (Hopefully) addresses all the concerns raised (Let me know if I missed anything)

There is now set a favicon_largest_interesting_size value in dimens.xml which specifies the largest favicon size that is ever entered into the cache. Larger favicons are stored in the database, but never in the cache.
An additional function has been added, for use by methods attempting to create homescreen icons and similar, which sidesteps the cache and grabs the largest available favicon directly from the database or internet.

This change has vastly decreased the rate at which the cache fills. I left in a debug print statement that prints out the cache fullness for your amusement if you're interested in trying it out. This, plus the improved hitrate of caching based on faviconURL instead of pageURL means we now have more favicon memcache than you can shake a stick at.

It was also mentioned that the previous implementation felt fragmented and strange. A bunch of different caches and, when you think about it, not optimal LRU behaviour.
In a move that is likely to cause some disgruntlement, I've therefore completely changed how the underlying datastructures work. This new approach is considerably prettier, doesn't partition the available space like the old approach did, and, importantly, is such that it is now possible to extend it to do things like solve Bug 914058 (Something that would have been entirely impossible using the previous approach).

There is a large comment at the start of FaviconCache.java which attempts to explain in detail how the new datastructures work. Hopefully reading through this before diving in should make what's going on somewhat clearer.

Additionally, by shamelessly stealing some changes from lucasr's patches from Bug 905685, I have been able to delete a bunch of annoying functions that were used only by now-obsolete-but-thus-far-not-disentangled about:home code. That evilness goes away with this patch.

A largeish amount of cleanup and suchlike has been performed. Addressed all of sriram's complaints. Alas, the source file into which ASCII art should go has been refactored out of existence. Also of note: an entirely redundant method of an inner class which has seemingly existed for the last four iterations of this patch, did absolutely nothing, and been missed by myself and three reviewers. Whoops. :P

Finally, A two line tweak has been made to LoadFaviconTask which makes the favicon for m.bbc.co.uk load. It was issuing an HTTP 302 pointing to the real Favicon which we were ignoring. By just recursively calling tryDownload with the value of the Location header, victory is attained.
Attachment #803296 - Attachment is obsolete: true
Attachment #803365 - Attachment is obsolete: true
Attachment #803296 - Flags: review?(margaret.leibovic)
Attachment #803296 - Flags: feedback?(lucasr.at.mozilla)
Attachment #803296 - Flags: feedback?(bnicholson)
Attachment #803365 - Flags: review?(margaret.leibovic)
Attachment #803562 - Flags: review?(margaret.leibovic)
Attachment #803562 - Flags: feedback?(bnicholson)
Attachment #803562 - Flags: feedback?(sriram)
Attachment #803562 - Flags: feedback?(lucasr.at.mozilla)
Still having a look at the patch but just wanted to suggest right off to only land it in Firefox 27 after the merge next week as this is a fairly risky change to integrate at this point.

This probably means this patch should not include the changes from my patch in bug 905685 but instead be rebased to apply changes on top of it.
(In reply to Lucas Rocha (:lucasr) from comment #13)
> Still having a look at the patch but just wanted to suggest right off to
> only land it in Firefox 27 after the merge next week as this is a fairly
> risky change to integrate at this point.
> 
> This probably means this patch should not include the changes from my patch
> in bug 905685 but instead be rebased to apply changes on top of it.

I agree with this. After this lands on m-c we can see if there's any fallout, and if not, we can think about uplifting to Aurora.

Although we've lived with these problems for a long time, it would be nice to have more reliably prettier favicons when we ship the new about:home in 26.
(In reply to Lucas Rocha (:lucasr) from comment #13)
> This probably means this patch should not include the changes from my patch
> in bug 905685 but instead be rebased to apply changes on top of it.

I would have done so, but for the fact that some of your changes directly contradict a some of my changes in Bug 888326, which just landed. (So I just bitrotted you, as well. Sorry.)
In any case, my rebasing is literally going to consist of undoing a chunk of what you're doing. I was attempting to avoid this busywork.

Likewise, what sriram is doing in Bug 915347 contradicts the work here (And between the two of you we end up with three near-identical classes called LoadFaviconTask).
I guess this is a quick near-deadline bodge, but suspect that it'd have persisted for far longer had it not just happened that I was concurrently doing this work.

(In reply to :Margaret Leibovic from comment #14)
> > This probably means this patch should not include the changes from my patch
> > in bug 905685 but instead be rebased to apply changes on top of it.
> 
> I agree with this. After this lands on m-c we can see if there's any
> fallout, and if not, we can think about uplifting to Aurora.

For what it's worth:
https://tbpl.mozilla.org/?tree=Try&rev=9a1d1cdd57c9

> Although we've lived with these problems for a long time, it would be nice
> to have more reliably prettier favicons when we ship the new about:home in
> 26.

I agree - the new UI depends very heavily on favicons, and between this and the ICO decoder bug the improvement to the UI is quite significant.
(In reply to Chris Kitching [:ckitching] from comment #15)
> (In reply to Lucas Rocha (:lucasr) from comment #13)
> > This probably means this patch should not include the changes from my patch
> > in bug 905685 but instead be rebased to apply changes on top of it.
> 
> I would have done so, but for the fact that some of your changes directly
> contradict a some of my changes in Bug 888326, which just landed. (So I just
> bitrotted you, as well. Sorry.)

I can't see how bug 888326 contradicts my patch. It's just a series of refactorings on the existing API. It's just a mild bitrot, no worries ;-)

> In any case, my rebasing is literally going to consist of undoing a chunk of
> what you're doing. I was attempting to avoid this busywork.

Yeah, I understand. I would probably be ok with just doing all the changes in your patch if we weren't so late in the cycle. FWIW, I would probably have waited to land bug 888326 after the merge too just to avoid the risk of breaking m-c just before the merge.   

The reason why it's important to split the two patches here is that bug 905685 is a 26 blocker while this one is not. Which means your patch here may or may not be uplifted to Aurora next week. If it ends up in Aurora, great. If not, we still have the fix for the 26 blocker in place.

> (In reply to :Margaret Leibovic from comment #14)
> > > This probably means this patch should not include the changes from my patch
> > > in bug 905685 but instead be rebased to apply changes on top of it.
> > 
> > I agree with this. After this lands on m-c we can see if there's any
> > fallout, and if not, we can think about uplifting to Aurora.
> 
> For what it's worth:
> https://tbpl.mozilla.org/?tree=Try&rev=9a1d1cdd57c9
> 
> > Although we've lived with these problems for a long time, it would be nice
> > to have more reliably prettier favicons when we ship the new about:home in
> > 26.
> 
> I agree - the new UI depends very heavily on favicons, and between this and
> the ICO decoder bug the improvement to the UI is quite significant.

Agree. I'm all for having this patch uplifted after a few days in m-c.
(In reply to Lucas Rocha (:lucasr) from comment #16)
> Yeah, I understand. I would probably be ok with just doing all the changes
> in your patch if we weren't so late in the cycle. FWIW, I would probably
> have waited to land bug 888326 after the merge too just to avoid the risk of
> breaking m-c just before the merge.   

Very well. I'll upload a rebased version of this patch as soon as your patch lands. Followed by a rebased version of DecodeOnlyPossibles (Does Bugzilla linkify aliases, I wonder?)
Alias: FaviconRevamp
Bug 914027.

Seems I'm stuck with trying to memorise bug numbers.
Bug DecodeOnlyPossibles, perhaps?
Rebased Bug 905685 so I can rebase this on top of it.
Needless to say, you will now have to apply the patches from that bug before applying this one if you want to try it out.

This patch now more closely approximates a reasonable size.

Tagging rnewman because he seems to want to do this one..
Also tagging the usual suspects in case renwman has seen sense. :P
Attachment #806425 - Flags: review?(rnewman)
Attachment #806425 - Flags: review?(margaret.leibovic)
Attachment #806425 - Flags: feedback?(bnicholson)
*ahem*

Now less than 100kb! (Excitement!)
Attachment #803562 - Attachment is obsolete: true
Attachment #806425 - Attachment is obsolete: true
Attachment #803562 - Flags: review?(margaret.leibovic)
Attachment #803562 - Flags: feedback?(sriram)
Attachment #803562 - Flags: feedback?(lucasr.at.mozilla)
Attachment #803562 - Flags: feedback?(bnicholson)
Attachment #806425 - Flags: review?(rnewman)
Attachment #806425 - Flags: review?(margaret.leibovic)
Attachment #806425 - Flags: feedback?(bnicholson)
Attachment #806428 - Flags: review?(rnewman)
Attachment #806428 - Flags: review?(margaret.leibovic)
Attachment #806428 - Flags: feedback?(bnicholson)
Comment on attachment 806428 [details] [diff] [review]
V9 - Now with less insanity - Add more intelligent caching to the Favicons system.

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

First pass. Need to get these patches in a tree to read them properly.

::: mobile/android/base/BrowserApp.java
@@ +4,5 @@
>   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
>  
>  package org.mozilla.gecko;
>  
> +import static org.mozilla.gecko.favicons.cache.FaviconCache.LARGEST_INTERESTING_FAVICON_SIZE;

MAX_CACHED_FAVICON_SIZE?

::: mobile/android/base/favicons/LoadFaviconTask.java
@@ +38,5 @@
>   */
>  public class LoadFaviconTask extends UiAsyncTask<Void, Void, Bitmap> {
>      private static final String LOGTAG = "LoadFaviconTask";
>  
> +    private static final HashMap<String, LoadFaviconTask> loadsInFlight = new HashMap<String, LoadFaviconTask>();

Document that access to this needs to be synchronized.

@@ +59,5 @@
> +                           String pageUrl, String faviconUrl, int flags,
> +                           OnFaviconLoadedListener listener) {
> +        this(backgroundThreadHandler, pageUrl, faviconUrl, flags, listener, -1);
> +    }
> +    public LoadFaviconTask(Handler backgroundThreadHandler,

Newline between methods.

@@ +106,5 @@
> +            // Was the response a failure?
> +            int status = response.getStatusLine().getStatusCode();
> +
> +            // Handle HTTP status codes requesting a redirect.
> +            if (status >= 300 && status <= 400) {

< 400, not <=.

@@ +107,5 @@
> +            int status = response.getStatusLine().getStatusCode();
> +
> +            // Handle HTTP status codes requesting a redirect.
> +            if (status >= 300 && status <= 400) {
> +                String newURL = response.getFirstHeader("Location").getValue();

getFirstHeader can return null, so this can NPE. Check for that.

(Misconfigured web servers exist!)

@@ +111,5 @@
> +                String newURL = response.getFirstHeader("Location").getValue();
> +                if (newURL.equals(faviconURL.toString())) {
> +                    return null;
> +                }
> +                return tryDownload(new URL(newURL));

You need to handle redirect loops.

@@ +183,5 @@
> +        String storedFaviconUrl = null;
> +        boolean isUsingDefaultURL = false;
> +
> +        // Handle the case of malformed favicon URL
> +        // If favicon is empty, fallback to the stored one

The fallback is to fall back. Add the space, and full stops for each line.

@@ +184,5 @@
> +        boolean isUsingDefaultURL = false;
> +
> +        // Handle the case of malformed favicon URL
> +        // If favicon is empty, fallback to the stored one
> +        if (mFaviconUrl == null || mFaviconUrl.length() == 0) {

TextUtils.isEmpty(mFaviconUrl);

@@ +230,5 @@
> +        if (isCancelled()) {
> +            return Favicons.sDefaultFavicon;
> +        }
> +
> +        try{

Space before {.

@@ +258,5 @@
>      }
>  
>      @Override
> +    protected void onPostExecute(Bitmap image) {
> +        // Firstly, prevent others from joining the queue for this result..

Either '…' or '.', please, throughout.

@@ +275,4 @@
>          Favicons.removeLoadTask(mId);
> +
> +        // Notify listeners, scaling if required..
> +        if (mTargetSize != -1 && image.getWidth() != mTargetSize) {

mTargetWidth, surely?

::: mobile/android/base/favicons/cache/FaviconCache.java
@@ +25,5 @@
> + * FaviconsForURL provides a method for obtaining the smallest icon larger than a given size - the
> + * most appropriate icon for a particular size.
> + * It also distinguishes between "Primary" favicons (Ones that have merely been extracted from a
> + * file downloaded from the website) and "Secondary" favicons (Ones that have been computed locally
> + * as resized versions of primary favicons.

Closing paren, plus no need for capital letters (In this situation). (Only in this one.)

@@ +38,5 @@
> + * Also present here are the download timestamp and isFailed flag. Upon failure, the flag is set.
> + * A constant exists in this file to specify the maximum time permitted between failures before
> + * a retry is again permitted.
> + *
> + * TODO: Expiry of Favicons from the favicon database cache is not implemented.

File a bug.

@@ +81,5 @@
> +    private static final String LOGTAG = "FaviconCache";
> +    // Dimensions of the largest favicon to store in the cache. Everything is downscaled to this.
> +    public static int LARGEST_INTERESTING_FAVICON_SIZE;
> +
> +    // Magic number indiciating that a failed favicon shall never expire - it will always fail.

indicating

::: mobile/android/base/favicons/cache/FaviconCacheElement.java
@@ +18,5 @@
> +    Bitmap mFaviconPayload;
> +
> +    // If set, mFaviconPayload is absent. Since the underlying ICO may contain multiple primary
> +    // payloads, primary payloads are never truly deleted from the cache, but instead have their
> +    // payload deleted and this flag set on their FaviconCacheElement. That way, the cache

the cache what?

@@ +48,5 @@
> +
> +    /**
> +     * Establish an ordering on FaviconCacheElements based on size.
> +     * @param another
> +     * @return

Either useful Javadoc params, or remove.

@@ +60,5 @@
> +        if (!mInvalidated && another.mInvalidated) {
> +            return 1;
> +        }
> +
> +        if (mInvalidated) {

mInvalidated == another.mInvalidated or similar, right?
Chris (or someone else): apparently the "Depends On" field hasn't been kept up to date, so I don't know which stack of patches to apply.

Do you have:

* A git branch
* A patch stack somewhere
* A sequence of URLs that I can qimport

or another solution to the problem of actually being able to read this code?
Flags: needinfo?(ckitching)
Depends on: 905685
Flags: needinfo?(ckitching)
Ah. Indeed.

You'll want the patch from Bug 916588, then the patches from Bug 905685 in the following order (Oddly, they'rem not numbered over there):

1. https://bugzilla.mozilla.org/attachment.cgi?id=806297
2. https://bugzilla.mozilla.org/attachment.cgi?id=806377
3. https://bugzilla.mozilla.org/attachment.cgi?id=806378

That said, lucasr just claimed to have landed this, as I typed out this comment - so you may now be able to omit these.

>@@ +38,5 @@
>> + * Also present here are the download timestamp and isFailed flag. Upon failure, the flag is set.
>> + * A constant exists in this file to specify the maximum time permitted between failures before
>> + * a retry is again permitted.
>> + *
>> + * TODO: Expiry of Favicons from the favicon database cache is not implemented.
>
>File a bug.

There is already a bug for this TODO which I'll address after getting this lot landed - increasing the number of in-flight bugs further seems unwise.

>::: mobile/android/base/favicons/cache/FaviconCacheElement.java
>@@ +18,5 @@
>> +    Bitmap mFaviconPayload;
>> +
>> +    // If set, mFaviconPayload is absent. Since the underlying ICO may contain multiple primary
>> +    // payloads, primary payloads are never truly deleted from the cache, but instead have their
>> +    // payload deleted and this flag set on their FaviconCacheElement. That way, the cache
>
>the cache what?

I appear to have accidentially half a sentence.

>mInvalidated == another.mInvalidated or similar, right?

Actually no. The invalidated flag is only interesting if one is invalid and the other is not.
If A is valid and B is not, then A < B.
If both A and B are valid, then we choose based on image size.
If both A and B are invalid, then both are equivalent.

This line checks for both arguments having the invalid flag set. Because logic, when control reaches this point in the program another.mInvalidated is always true.
Attachment #806428 - Attachment is obsolete: true
Attachment #806428 - Flags: review?(rnewman)
Attachment #806428 - Flags: review?(margaret.leibovic)
Attachment #806428 - Flags: feedback?(bnicholson)
Attachment #806752 - Flags: review?(rnewman)
Attachment #806752 - Flags: review?(margaret.leibovic)
Attachment #806752 - Flags: feedback?(bnicholson)
(In reply to Chris Kitching [:ckitching] from comment #24)

> That said, lucasr just claimed to have landed this, as I typed out this
> comment - so you may now be able to omit these.

He did.

> >> + * TODO: Expiry of Favicons from the favicon database cache is not implemented.
> >
> >File a bug.
> 
> There is already a bug for this TODO which I'll address after getting this
> lot landed - increasing the number of in-flight bugs further seems unwise.

Great! Now put it in the comment.
Depends on: 916588
Blocks: 699785
(In reply to Richard Newman [:rnewman] from comment #25)

> > There is already a bug for this TODO which I'll address after getting this
> > lot landed - increasing the number of in-flight bugs further seems unwise.
> 
> Great! Now put it in the comment.

Aye. Bug 914296. Will add it to the comment with the next batch of corrections.

Also, Bug 916588 just hit fx-team, so you may not need that patch, either.
There was a conflict applying this to TwoLinePageRow.java -- looks as if very similar logic already applied.
Comment on attachment 806752 [details] [diff] [review]
V10 - Newmanified - Add more intelligent caching to the Favicons system.

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

::: mobile/android/base/favicons/Favicons.java
@@ +48,4 @@
>  
> +    // Cache to hold mappings between page URLs and Favicon URLs. Used to avoid going to the DB when
> +    // doing so is not necessary.
> +    private static final LruCache<String, String> sPageURLMappings = new LruCache<String, String>(64);

Extract that constant; we ought to tune it, or even parameterize it.

@@ +52,2 @@
>  
> +    private static final FaviconCache sFaviconsCache = new FaviconCache(1024 * 1024);

Extract magic number.

@@ +126,5 @@
> +        return null;
> +    }
> +
> +    /**
> +     * Attempts to find a Favicon for the provided page URL from either the mem cache or the database.

What does it return if it's missing? If the cache recorded a permanent failure?

@@ +144,5 @@
> +
> +        String targetURL = sPageURLMappings.get(pageURL);
> +        if (targetURL == null) {
> +            // Nope. Let's try to guess the Favicon URL - maybe we get lucky.
> +            targetURL = getDefaultFaviconURL(pageURL);

Misnamed method? "guessDefaultFaviconURL"?

@@ +172,5 @@
> +
> +                // Store the result of this query in the cache for such things, so we don't need
> +                // to go to this trouble again next time. (When we scroll up on the history view,
> +                // for example.
> +                sPageURLMappings.put(pageURL, faviconURL);

You touch this map from two threads. Make sure it's safe.

@@ +175,5 @@
> +                // for example.
> +                sPageURLMappings.put(pageURL, faviconURL);
> +
> +                // Do we have the needed icon in the memcache after all?
> +                Bitmap result = getSizedFaviconFromCache(faviconURL, targetSize);

Check whether the URL was already the default icon, and thus we can save consulting the cache?

@@ +209,5 @@
> +        } else {
> +            continuation.run();
> +        }
> +    }
> +    public static void getSizedFaviconForPageFromLocal(final String pageURL, final int targetSize, final OnFaviconLoadedListener callback) {

Newline.

@@ +217,5 @@
> +        getSizedFaviconForPageFromLocal(pageURL, sDefaultFaviconSize, callback, ThreadUtils.getBackgroundThread());
> +    }
> +    public static void getSizedFaviconForPageFromLocal(final String pageURL, final OnFaviconLoadedListener callback, final Thread targetThread) {
> +        getSizedFaviconForPageFromLocal(pageURL, sDefaultFaviconSize, callback, targetThread);
> +    }

I confess to not being a big fan of all of these overloads.

@@ +234,5 @@
> +        Tabs tabInstance = Tabs.getInstance();
> +        int tabId = tabInstance.getTabIdForUrl(pageURL);
> +        String targetURL;
> +        if (tabId != -1) {
> +            Tab theTab = tabInstance.getTab(tabId);

This strikes me as a bad idea concurrency-wise. Just reimplement getTabIdForUrl in terms of a new method, getTabForUrl. Touching Tabs.java is not a sin.

@@ +254,5 @@
> +     * Helper function to create an async job to load a Favicon which does not exist in the memcache.
> +     * Contains logic to prevent the repeated loading of Favicons which have previously failed.
> +     * There is no support for recovery from transient failures.
> +     *
> +     * @param pageUrl URL of the page for which to load a Favicon.

Can this be null?

@@ +255,5 @@
> +     * Contains logic to prevent the repeated loading of Favicons which have previously failed.
> +     * There is no support for recovery from transient failures.
> +     *
> +     * @param pageUrl URL of the page for which to load a Favicon.
> +     * @param faviconUrl The URL of the Favicon to load.

Can this be null?

@@ +268,5 @@
> +     */
> +    private static int loadUncachedFavicon(String pageUrl, String faviconUrl, int flags, OnFaviconLoadedListener listener) {
> +        return loadUncachedFavicon(pageUrl, faviconUrl, flags, -1, listener);
> +    }
> +    private static int loadUncachedFavicon(String pageUrl, String faviconUrl, int flags, int targetSize, OnFaviconLoadedListener listener) {

Newline.

@@ +269,5 @@
> +    private static int loadUncachedFavicon(String pageUrl, String faviconUrl, int flags, OnFaviconLoadedListener listener) {
> +        return loadUncachedFavicon(pageUrl, faviconUrl, flags, -1, listener);
> +    }
> +    private static int loadUncachedFavicon(String pageUrl, String faviconUrl, int flags, int targetSize, OnFaviconLoadedListener listener) {
> +        // Handle the case where page url.

"where we have no page URL."

@@ +274,1 @@
>          if (pageUrl == null || pageUrl.length() == 0) {

TextUtils.isEmpty.

::: mobile/android/base/favicons/LoadFaviconTask.java
@@ +120,5 @@
> +            int status = response.getStatusLine().getStatusCode();
> +
> +            // Handle HTTP status codes requesting a redirect.
> +            if (status >= 300 && status < 400) {
> +                String newURL = response.getFirstHeader("Location").getValue();

NPE.

@@ +131,5 @@
> +                    return null;
> +                }
> +                visited.add(newURL);
> +
> +                return tryDownloadRecurse(new URL(newURL), visited);

How many hops are we happy to try? What if the redirect loop includes a URL parameter that changes?

You need a counter, even if we also check URLs for the loop. (You can use visited to count…)

@@ +204,5 @@
> +        boolean isUsingDefaultURL = false;
> +
> +        // Handle the case of malformed favicon URL.
> +        // If favicon is empty, fall back to the stored one.
> +        if (mFaviconUrl == null || TextUtils.isEmpty(mFaviconUrl)) {

isEmpty does the null check for you.
Comment on attachment 806752 [details] [diff] [review]
V10 - Newmanified - Add more intelligent caching to the Favicons system.

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

::: mobile/android/base/favicons/cache/FaviconCache.java
@@ +76,5 @@
> + * If this were not done, then when processing requests after the culling of primary favicons it would
> + * be impossible to distinguish between the nonexistence of a primary and the nonexistence of a primary
> + * in the cache without querying the database.
> + */
> +public class FaviconCache {

This class is absolutely not thread-safe, so (a) document that, and (b) make sure none of its callers are ever calling from more than one thread.

@@ +184,5 @@
> +     * @param faviconURL The URL for which a Favicon is desired.
> +     * @param targetSize The size of the desired favicon.
> +     * @return A favicon of the requested size for the requested URL, or null if none cached.
> +     */
> +    public Bitmap getFaviconForDimensions(String faviconURL, int targetSize) {

This method seems like a fountain of ArrayIndexOutOfBounds exceptions. I'd like to see this tested, or at least reviewed by someone detail-oriented.

@@ +298,5 @@
> +        }
> +
> +        // Some sites serve up insanely huge Favicons (Seen 512x512 ones...)
> +        // While we want to cache nice big icons, 128x128 is plenty - larger just fills the cache.
> +        if (favicon.getWidth() > MAX_CACHED_FAVICON_SIZE) {

MAX_CACHED_FAVICON_WIDTH?

@@ +324,5 @@
> +        }
> +
> +        // Create a fresh container for the favicons associated with this URL. Allocate extra slots
> +        // in the underlying ArrayList in case multiple secondary favicons are later created.
> +        FaviconsForURL toInsert = new FaviconsForURL(4);

Where did that number come from? How many sizes do we need? Does it make sense to compute the main ones now? (e.g., URL bar icon, tabs tray icon?)

::: mobile/android/base/favicons/cache/FaviconCacheElement.java
@@ +11,5 @@
> + * been scaled. Unscaled bitmaps are not included in the scaled-bitmap cache's size calculation.
> + */
> +public class FaviconCacheElement implements Comparable<FaviconCacheElement> {
> +    // Was this Favicon computed via scaling another primary Favicon, or is this a primary Favicon?
> +    boolean mIsPrimary;

final.

@@ +14,5 @@
> +    // Was this Favicon computed via scaling another primary Favicon, or is this a primary Favicon?
> +    boolean mIsPrimary;
> +
> +    // The Favicon bitmap.
> +    Bitmap mFaviconPayload;

final.

@@ +31,5 @@
> +    // Used for LRU pruning.
> +    FaviconsForURL mBackpointer;
> +
> +    public int getImageSize() {
> +        return mFaviconPayload.getWidth();

NPE.

::: mobile/android/base/favicons/cache/FaviconsForURL.java
@@ +10,5 @@
> +import java.util.ArrayList;
> +import java.util.Collections;
> +
> +public class FaviconsForURL {
> +    int mDominantColour;

This isn't used in this class. Code smell alert.

Also, worth considering whether different primaries will have different dominant colors…

@@ +11,5 @@
> +import java.util.Collections;
> +
> +public class FaviconsForURL {
> +    int mDominantColour;
> +    long mDownloadTimestamp;

final.

@@ +88,5 @@
> +            FaviconCacheElement element = mFavicons.get(searchIndex);
> +
> +            if (element.mIsPrimary) {
> +                if (element.mInvalidated) {
> +                    return null;

break, not return?

@@ +96,5 @@
> +            searchIndex++;
> +        }
> +
> +        // No larger primary available. Let's look for smaller ones...
> +        searchIndex = fromIndex-1;

Nit: spaces around arithmetic operators.

@@ +109,5 @@
> +            }
> +            searchIndex--;
> +        }
> +
> +        // Somehow we have no primaries in this structure at all? This is madness!

Log.

::: mobile/android/base/home/BookmarksPage.java
@@ +575,2 @@
>                  if (!thumbnails.containsKey(url)) {
> +                    if (url == null || url.length() == 0) {

if (TextUtils.isEmpty(url)) {

@@ +580,5 @@
> +                    // Load, synchronously, any local copy of the icon we happen to have available.
> +                    Favicons.getSizedFaviconForPageFromLocal(url, new OnFaviconLoadedListener() {
> +                        @Override
> +                        public void onFaviconLoaded(String aURL, String faviconURL, Bitmap favicon) {
> +                            thumbnails.put(url, new Thumbnail(favicon, false));

Change this line:

            final Map<String, Thumbnail> thumbnails = new HashMap<String, Thumbnail>();


to initialize based on mUrls.size().

@@ +582,5 @@
> +                        @Override
> +                        public void onFaviconLoaded(String aURL, String faviconURL, Bitmap favicon) {
> +                            thumbnails.put(url, new Thumbnail(favicon, false));
> +                        }
> +                    }, Thread.currentThread());

Here's the second thread, per my earlier safety comment.

::: mobile/android/base/home/TopBookmarkItemView.java
@@ +179,5 @@
>              return;
>          }
>  
> +        if (faviconURL != null) {
> +            mFaviconURL = faviconURL;

Is this necessary, versus just assigning even if it's null? (IOW, is mFaviconURL set to something beforehand, and do we want to preserve it if we're entering this method?)

@@ +186,3 @@
>          mThumbnailView.setScaleType(ScaleType.CENTER);
>          mThumbnailView.setImageBitmap(favicon);
> +        mThumbnailView.setBackgroundColor(Favicons.getFaviconColor(favicon, mFaviconURL));

Contention: we don't need to find and set the background color if we're going to completely occlude it with a full-size favicon.

::: mobile/android/base/home/TwoLinePageRow.java
@@ +194,4 @@
>  
> +        // No point updating the below things if URL has not changed. Prevents evil Favicon flicker.
> +        if (url.equals(mPageUrl)) {
> +            return;

I think we can do better with short-circuiting here -- defaulting behaviors for favicons are based on domains, not pages, so we can either definitely or speculatively decide that the new page will have the same favicon based on host, not URL.

That might be possible in the favicon layer instead -- "hey, I'm using this favicon, got a new one for me?".
Attachment #806752 - Flags: review?(rnewman)
Attachment #806752 - Flags: review?(bnicholson)
Attachment #806752 - Flags: feedback?(bnicholson)
Attachment #806752 - Flags: feedback+
(In reply to Richard Newman [:rnewman] from comment #28)
> @@ +172,5 @@
> > +
> > +                // Store the result of this query in the cache for such things, so we don't need
> > +                // to go to this trouble again next time. (When we scroll up on the history view,
> > +                // for example.
> > +                sPageURLMappings.put(pageURL, faviconURL);
> 
> You touch this map from two threads. Make sure it's safe.

http://developer.android.com/reference/android/util/LruCache.html

"This class is thread-safe"

Since I never need to atomically perform more than one operation on the cache, synchronising on it is unnecessary.

The worst that can happen is a missed update - nobody cares - we do extra db work in this case. Certainly cheaper than to do the locking all the time.

> @@ +217,5 @@
> > +        getSizedFaviconForPageFromLocal(pageURL, sDefaultFaviconSize, callback, ThreadUtils.getBackgroundThread());
> > +    }
> > +    public static void getSizedFaviconForPageFromLocal(final String pageURL, final OnFaviconLoadedListener callback, final Thread targetThread) {
> > +        getSizedFaviconForPageFromLocal(pageURL, sDefaultFaviconSize, callback, targetThread);
> > +    }
> 
> I confess to not being a big fan of all of these overloads.

Just trying to make the API neater. Optional parameters in Java aren't well supported.

> @@ +234,5 @@
> > +        Tabs tabInstance = Tabs.getInstance();
> > +        int tabId = tabInstance.getTabIdForUrl(pageURL);
> > +        String targetURL;
> > +        if (tabId != -1) {
> > +            Tab theTab = tabInstance.getTab(tabId);
> 
> This strikes me as a bad idea concurrency-wise. Just reimplement
> getTabIdForUrl in terms of a new method, getTabForUrl. Touching Tabs.java is
> not a sin.

I see the style problem - but where's the concurrency problem?

I also renamed getTab as getTabForId, for consistency.

> @@ +254,5 @@
> > +     * Helper function to create an async job to load a Favicon which does not exist in the memcache.
> > +     * Contains logic to prevent the repeated loading of Favicons which have previously failed.
> > +     * There is no support for recovery from transient failures.
> > +     *
> > +     * @param pageUrl URL of the page for which to load a Favicon.
> 
> Can this be null?

Yes, but the call becomes a nop.

> @@ +255,5 @@
> > +     * Contains logic to prevent the repeated loading of Favicons which have previously failed.
> > +     * There is no support for recovery from transient failures.
> > +     *
> > +     * @param pageUrl URL of the page for which to load a Favicon.
> > +     * @param faviconUrl The URL of the Favicon to load.
> 
> Can this be null?

Yes - the system tries checks the db, and finally makes a guess.

Publishing new version after dealing with your next comment...
(In reply to Richard Newman [:rnewman] from comment #29)
> Comment on attachment 806752 [details] [diff] [review]
> V10 - Newmanified - Add more intelligent caching to the Favicons system.
> 
> Review of attachment 806752 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mobile/android/base/favicons/cache/FaviconCache.java
> @@ +76,5 @@
> > + * If this were not done, then when processing requests after the culling of primary favicons it would
> > + * be impossible to distinguish between the nonexistence of a primary and the nonexistence of a primary
> > + * in the cache without querying the database.
> > + */
> > +public class FaviconCache {
> 
> This class is absolutely not thread-safe, so (a) document that, and (b) make
> sure none of its callers are ever calling from more than one thread.

I now, weakly, make the claim that this class is thread safe enough to operate correctly. After sleeping, I'll check in more detail.
Notably, the cache allows for missed updates when a write races with a read - this is acceptable, and seems not to be worth the extra locking costs all the time to avoid an extra cache miss in the very rare case when this happens.

> @@ +184,5 @@
> > +     * @param faviconURL The URL for which a Favicon is desired.
> > +     * @param targetSize The size of the desired favicon.
> > +     * @return A favicon of the requested size for the requested URL, or null if none cached.
> > +     */
> > +    public Bitmap getFaviconForDimensions(String faviconURL, int targetSize) {
> 
> This method seems like a fountain of ArrayIndexOutOfBounds exceptions. I'd
> like to see this tested, or at least reviewed by someone detail-oriented.

Not in the slightest. That you've said this suggests I did a poor job commenting the quite obtuse code here.
The only case in which this might happen is if it were called with faviconURL = null - which it currently never is.

For future-proofing, I added a null check and a whinging error message.

For Newman-proofing, I added a bunch more comments. Even in the face of madly corrupted FaviconsForURL objects this method cannot throw an ArrayIndexOutOfBoundsException - how did you imagine it doing so? I guess the use of -1 as a sentinel and suchlike might make it smell ArrayIndexOutOfBoundsException-esque. I'm reluctant to make a constant field of this value, because it must never be changed or correctness may be compromised (The value must be a -ve integer).

> @@ +298,5 @@
> > +        }
> > +
> > +        // Some sites serve up insanely huge Favicons (Seen 512x512 ones...)
> > +        // While we want to cache nice big icons, 128x128 is plenty - larger just fills the cache.
> > +        if (favicon.getWidth() > MAX_CACHED_FAVICON_SIZE) {
> 
> MAX_CACHED_FAVICON_WIDTH?

Since favicons are square - do we care? It's no trouble to change the nomenclature everywhere from "Size" to "Width", but aren't the two equivalent?

> @@ +324,5 @@
> > +        }
> > +
> > +        // Create a fresh container for the favicons associated with this URL. Allocate extra slots
> > +        // in the underlying ArrayList in case multiple secondary favicons are later created.
> > +        FaviconsForURL toInsert = new FaviconsForURL(4);
> 
> Where did that number come from? How many sizes do we need? Does it make
> sense to compute the main ones now? (e.g., URL bar icon, tabs tray icon?)

This number is the number of sizes we currently use in the UI, plus the one I've forgotten.
Ideally, it should be tuned as we add more sizes in use.

Precomputing does not seem sensible - part of the idea of the cache was to reduce the amount of work needed calculating resizings of favicons - precalculating them all will be wasteful if we never use them.
That said, precomputing and doing more total work may reduce UI latency. It's unclear if the big chunk of work calculating the resizings whenever we add an icon to the cache is pointful (As-is, the compute-on-demand approach seems to be the average best case solution for all use-cases. I've gone to some effort to prevent the performance of the favicon cache from being dependant upon our UI layout. I want us to be able to rewrite the UI all over again and not have trouble with the cache. Hence the slightly excessively general and slightly over-engineered solution - in the face of mutant, organic code you need over-engineering if you want code that lasts.).


> @@ +14,5 @@
> > +    // Was this Favicon computed via scaling another primary Favicon, or is this a primary Favicon?
> > +    boolean mIsPrimary;
> > +
> > +    // The Favicon bitmap.
> > +    Bitmap mFaviconPayload;
> 
> final.

Nope.

It is necessary to be able to null this field out when evicting a primary from the cache.

Consider the scenario in which a favicon ICO contains sizes 16, 32, and 64. We load all three and stick them in the cache.

Sometime later, the 64 and 32 have been evicted from the cache to to unuse.

Now a request comes in for a 48 pixel favicon. We have the 64 pixel favicon we'd want sitting around in the database - we just need to go get it. But we do not have the information if we just deleted the FaviconCacheEntry.

Instead, the implementation evicts these primaries by setting their payload to null and setting the invalid flag. That way, when a request is satisfied by an invalid favicon we know that we have to go fetch it from the database.

Just to make reviewing this that little bit more fun, the going-and-fetching implementation does not exist in this patch, since it depends on the ICO decoder from Bug 748100. As such, you'll have to accept this over-over-engineering as something that'll help our sanity later.

If you REALLY want we can stick in a setNull method or such - but since the field only has package access this seems sufficiently encapsulated to prevent users of the API from doing anything stupid with it.

> ::: mobile/android/base/favicons/cache/FaviconsForURL.java
> @@ +10,5 @@
> > +import java.util.ArrayList;
> > +import java.util.Collections;
> > +
> > +public class FaviconsForURL {
> > +    int mDominantColour;
> 
> This isn't used in this class. Code smell alert.

This is actually set in FaviconCache (See, if you had a decent IDE then finding if something is used or not would be trivial)
It is not used in the class, no. The FaviconsForURL object simply carries this value. Again, can add a getter/setter method if you insist, but since it's of package access (And for once we actually have packages) this doesn't seem pointful.
 
> Also, worth considering whether different primaries will have different
> dominant colors…

For the purposes of this cache I make the simplifying assuption that they do not (I'm think I wrote a comment to that effect around line 30 of the file).
If you like I can add support for this, but the cost/benefit ratio didn't seem worth it. Extra computations that are usually, and ought to be, pointless.

> @@ +88,5 @@
> > +            FaviconCacheElement element = mFavicons.get(searchIndex);
> > +
> > +            if (element.mIsPrimary) {
> > +                if (element.mInvalidated) {
> > +                    return null;
> 
> break, not return?

No. What we have found is the best primary for the job - unfortunately it's not in the cache at the moment. The null return is to cause the caller to go fetch it from the database.
If we break'd here, we'd continue, find a less-appropriate primary, and use that.

> @@ +580,5 @@
> > +                    // Load, synchronously, any local copy of the icon we happen to have available.
> > +                    Favicons.getSizedFaviconForPageFromLocal(url, new OnFaviconLoadedListener() {
> > +                        @Override
> > +                        public void onFaviconLoaded(String aURL, String faviconURL, Bitmap favicon) {
> > +                            thumbnails.put(url, new Thumbnail(favicon, false));
> 
> Change this line:
> 
>             final Map<String, Thumbnail> thumbnails = new HashMap<String,
> Thumbnail>();
> 
> 
> to initialize based on mUrls.size().

You failed to account for load factor when making this suggestion.

In addition, I've been advised by my reviewer over in Bug 794981 not to bother with such things on hashmaps except in performance-sensitive code. Unclear how to proceed in the face of contradictory information.

> ::: mobile/android/base/home/TopBookmarkItemView.java
> @@ +179,5 @@
> >              return;
> >          }
> >  
> > +        if (faviconURL != null) {
> > +            mFaviconURL = faviconURL;
> 
> Is this necessary, versus just assigning even if it's null? (IOW, is
> mFaviconURL set to something beforehand, and do we want to preserve it if
> we're entering this method?)

Yes. Daft code somewhere occasionally unwisely calls us with null.

> @@ +186,3 @@
> >          mThumbnailView.setScaleType(ScaleType.CENTER);
> >          mThumbnailView.setImageBitmap(favicon);
> > +        mThumbnailView.setBackgroundColor(Favicons.getFaviconColor(favicon, mFaviconURL));
> 
> Contention: we don't need to find and set the background color if we're
> going to completely occlude it with a full-size favicon.

... But we don't have the actual size of the view at this point, and we already computed the favicon colour anyway when we added the favicon to the memcache.

> ::: mobile/android/base/home/TwoLinePageRow.java
> @@ +194,4 @@
> >  
> > +        // No point updating the below things if URL has not changed. Prevents evil Favicon flicker.
> > +        if (url.equals(mPageUrl)) {
> > +            return;
> 
> I think we can do better with short-circuiting here -- defaulting behaviors
> for favicons are based on domains, not pages, so we can either definitely or
> speculatively decide that the new page will have the same favicon based on
> host, not URL.
> 
> That might be possible in the favicon layer instead -- "hey, I'm using this
> favicon, got a new one for me?".

If it were true that "A call to getSizedFaviconForPageFromLocal implied that we were getting the default favicon" then you'd be quite right.

Unfortunately, this is not true. Websites can specify favicons on a per-page basis using a link tag. When one of these is encountered, we write the favicon URL therein to the history database.

When we call getSizedFaviconForPageFromLocal, the history database is consulted (Via a cache) to find the favicon URL for the page URL we have. Just because we haven't switched domains, doesn't mean the new page doesn't specify a favicon which will have a URL in the history database that we just don't know until we get there in the background task.

If we were before, and are now again, about to use the same default favicon then yes, we could stop. But the only way to find this out is to go all the way to the history database and find out if this new page really has no favicon set.
The caching on the pageURL->faviconURL mappings prevents us from doing this quite as often as otherwise, but otherwise, I believe we're stuck with it.

>@@ +11,5 @@
>> +import java.util.Collections;
>> +
>> +public class FaviconsForURL {
>> +    int mDominantColour;
>> +    long mDownloadTimestamp;
>
>final.

Nope. Assigned from FaviconCache:174 to implement failed cache expiry setting. *cough*get an IDE*cough* :P
Attachment #806752 - Attachment is obsolete: true
Attachment #806752 - Flags: review?(margaret.leibovic)
Attachment #806752 - Flags: review?(bnicholson)
Attachment #807641 - Flags: review?(rnewman)
Attachment #807641 - Flags: review?(margaret.leibovic)
Attachment #807641 - Flags: feedback?(bnicholson)
(In reply to Chris Kitching [:ckitching] from comment #31)

> > > +public class FaviconsForURL {
> > > +    int mDominantColour;
> > 
> > This isn't used in this class. Code smell alert.
> 
> This is actually set in FaviconCache (See, if you had a decent IDE then
> finding if something is used or not would be trivial)

...

> >> +    long mDownloadTimestamp;
> >
> >final.
> 
> Nope. Assigned from FaviconCache:174 to implement failed cache expiry
> setting. *cough*get an IDE*cough* :P

That's not the point.

This code is going to be around for, let's say, eight years, pass through the hands of perhaps fifteen developers, be reviewed in Splinter, and morph into something you might not recognize. And very soon some poor schmuck is going to have to write tests for each of these fields, along with the rest of the module.

Having non-"struct" classes host fields that are directly poked from other classes (even within the same package), with an unknown *or changing* concurrency model is a Bad Idea. Especially non-volatile longs!

Even if *you* are able to completely trace the call paths, and thus make a rock-solid assertion that these fields will never be touched from more than one thread, you're imposing on future developers a requirement to completely understand the concurrency approach in play before they can fix a bug, extend a feature, or even add tests for this.

And if you got that analysis wrong, you might have introduced an intermittent bug that'll be hell for someone else to find.

In the worst case -- the case where you must violate encapsulation and write single-threaded classes for performance reasons -- all of your classes should be thoroughly documented to explain which threads run (or can run) what, and which classes must only be instantiated and used on a single thread.

Your classes should be structured and implemented to make concurrency problems less likely. One way to do that is to avoid this particular pattern.
(In reply to Chris Kitching [:ckitching] from comment #31)

> I now, weakly, make the claim that this class is thread safe enough to
> operate correctly. After sleeping, I'll check in more detail.

Unless you're providing an interface that callers can't screw up, you need to thoroughly document what constraints apply to callers in order to maintain thread-safety.


> > > +        if (favicon.getWidth() > MAX_CACHED_FAVICON_SIZE) {
> > 
> > MAX_CACHED_FAVICON_WIDTH?
> 
> Since favicons are square - do we care? It's no trouble to change the
> nomenclature everywhere from "Size" to "Width", but aren't the two
> equivalent?

Size... you mean bytes? After all, there's more to memory usage than dimensions. Maybe you mean how many sub-items are in the icon? Width in pixels? Height?

Call the constant what you really mean. In this case it's the width in pixels, so WIDTH or WIDTH_PX is fine.


> This number is the number of sizes we currently use in the UI, plus the one
> I've forgotten.
> Ideally, it should be tuned as we add more sizes in use.

That would make a great comment.

> Precomputing does not seem sensible - part of the idea of the cache was to
> reduce the amount of work needed calculating resizings of favicons -
> precalculating them all will be wasteful if we never use them.
> That said, precomputing and doing more total work may reduce UI latency.

Great. Extra points for now having documented that in this bug. Even more extra points for filing another bug to figure out whether precomputing while we're here will improve the user experience! 


> Just to make reviewing this that little bit more fun, the going-and-fetching
> implementation does not exist in this patch, since it depends on the ICO
> decoder from Bug 748100. As such, you'll have to accept this
> over-over-engineering as something that'll help our sanity later.

Yeah, that makes reviewing this stage more difficult.


> If you REALLY want we can stick in a setNull method or such - but since the
> field only has package access this seems sufficiently encapsulated to
> prevent users of the API from doing anything stupid with it.

Not setNull: we have domain concepts to work with. "onEvictedFromCache"? How would you test the eviction logic in a way that's readable?


> No. What we have found is the best primary for the job - unfortunately it's
> not in the cache at the moment. The null return is to cause the caller to go
> fetch it from the database.
> If we break'd here, we'd continue, find a less-appropriate primary, and use
> that.

Which is what we want without your fetch-from-database part, right?


> You failed to account for load factor when making this suggestion.
> 
> In addition, I've been advised by my reviewer over in Bug 794981 not to
> bother with such things on hashmaps except in performance-sensitive code.
> Unclear how to proceed in the face of contradictory information.

By applying judgment to the specific situation :)

kats' point there is pretty much "don't speculate about initial size constants, 'cos you'll do a worse job than the defaults, and you're adding a cognitive burden to future developers for a really small win". Those are particularly true in your code generation patch.

If, however, you're doing something like initializing a map for a translation from one data structure to another, such as

  ArrayList<?> someStuff = Something.thatReturnsAnArrayList();
  Map<String, ?> someMap = new Map(someStuff.size());
  ...

then neither of these risks outweighs the potential cost of multiple rehashings if someStuff is larger than the defaults. The cognitive burden is low, the odds of the constant having to change are low, and the potential wins are nice.

If there's anything about this particular situation that _doesn't_ match that scenario -- e.g., if each item in someStuff might contribute more than one item -- then you're best sticking with kats' advice unless profiling says otherwise. But if you're creating the map right there, and it's obvious how big it should be, and the risk of future editors screwing up is low, then by all means specify the correct size.


> ... But we don't have the actual size of the view at this point, and we
> already computed the favicon colour anyway when we added the favicon to the
> memcache.

What are the odds that we'll have correct favicon sizes such that we don't need to compute the color at all? (That is, we can be lazy.)

> If we were before, and are now again, about to use the same default favicon
> then yes, we could stop. But the only way to find this out is to go all the
> way to the history database and find out if this new page really has no
> favicon set.

Why would we have to hit the database? We're loading the page right here. This is exactly my point: we know (or easily can) whether the previous page used the default favicon. We must know at this point whether the new page specifies its own favicon (so we could return it), and therefore if it should use the default. If both should use the default, and the domain is the same, we can do nothing.
Blocks: 918881
(In reply to Richard Newman [:rnewman] from comment #33)
> Unless you're providing an interface that callers can't screw up, you need
> to thoroughly document what constraints apply to callers in order to
> maintain thread-safety.

After some additional work, it should now "just work". Inspection appreciated - fine-grained locking is tricky. Since the mBackingMap is volatile, synchronising on reads is, I believe, not necessary. You'll either get null, or you'll get a reference to the value from the map.
If null, the read just looks like a cache miss, otherwise, it's a hit (Although it may prolong the life of the entry slightly after the removal of it from the map, but not in an interesting way).

Hopefully the rest of the work done here is obvious (And noninsane).

> Great. Extra points for now having documented that in this bug. Even more
> extra points for filing another bug to figure out whether precomputing while
> we're here will improve the user experience! 

Bug 918881.

> Which is what we want without your fetch-from-database part, right?

Ah yes, the joy of splitting patches more than originally planned.

> What are the odds that we'll have correct favicon sizes such that we don't
> need to compute the color at all? (That is, we can be lazy.)

Depends on what we get served - we can have the favicon system interpret the target size as "The size of the view in which this favicon will be displayed" and then only compute the dominant colour if the request can't be satisfied without unreasonable scaling.
Nice idea!

> Why would we have to hit the database? We're loading the page right here.
> This is exactly my point: we know (or easily can) whether the previous page
> used the default favicon. We must know at this point whether the new page
> specifies its own favicon (so we could return it), and therefore if it
> should use the default. If both should use the default, and the domain is
> the same, we can do nothing.

That's the problem - we don't know the favicon URL that was used last time. The TwoLinePageRow component just gets a page URL, no favicon URL. The only place the favicon URL might exist for it to use is in the history database (Or the cache thereof).
We are not necessarily loading the page at the time we're showing a reference to it in a TwoLinePageRow. For example, after starting the app and going to the history page, you see a bunch of TwoLinePageRow elements that are supposed to display favicons, but for which the page is not being loaded.
However, the page was previously loaded, so the favicon URL used is probably still in the history database - we have to go there to get it (Unless we want to actually load the page now, but this seems like a non-plan.).

Or am I just being really, really dense?

(In reply to Richard Newman [:rnewman] from comment #32)
> That's not the point.
> 
> <Huge scary comment>

Ah. I hadn't thought of that.
Cleaning this up has led to some considerable simplification of the code - putDominantColour has gone away from FaviconCache, and the lazy-computation of colours is now happening. Much niftier!
In addition, while working through that I ran into problems with TopBookmarksAdapter - the way it was independently querying the Favicon datbase when it couldn't find a thumbnail to use was thwarting this new, neater, lazier approach to dominant-colour caching.

But that it was doing this was daft anyway - it was duplicating the database access logic for Favicons and had its own cache (Bringing the total number of favicon caches I have thus far discovered and deleted up to three...)

The new approach queries the DB for thumbnails only, and doesn't set entries in the thumbnails map for favicons. The request to load favicons is in the same place it's always been, only now it's simplified and goes through the new caching scheme.

Excellent!

Since this change makes the union type "Thumbnail" become a union of one, it also seemed sensible to eliminate the class entirely - it'd literally be a class consisting of one field and a getter/setter pair for it - entirely redundant, and it doesn't add a useful abstraction here (Bitmaps in a hashmap called 'thumbnails' seem just an intuitively thumbnailesque as objects called Thumbnails holding bitmaps in such a map.
In fact, this seems much more intuitive than objects of type "Thumbnail" which held either a favicon or a thumbnail.)

Or something.

Opinions?
Attachment #807641 - Attachment is obsolete: true
Attachment #807641 - Flags: review?(rnewman)
Attachment #807641 - Flags: review?(margaret.leibovic)
Attachment #807641 - Flags: feedback?(bnicholson)
Attachment #808115 - Flags: review?(rnewman)
Attachment #808115 - Flags: review?(margaret.leibovic)
Attachment #808115 - Flags: feedback?(bnicholson)
Comment on attachment 808115 [details] [diff] [review]
V12 - More Newmanification - Add more intelligent caching to the Favicons system.

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

> Bitmaps in a hashmap
> called 'thumbnails' seem just an intuitively thumbnailesque as objects called
> Thumbnails holding bitmaps in such a map.

Sounds fair to me.

::: mobile/android/base/favicons/cache/FaviconCache.java
@@ +102,5 @@
> +    // Map relating Favicon URLs with objects representing decoded favicons.
> +    // Since favicons may be container formats holding multiple icons, the underlying type holds a
> +    // sorted list of bitmap payloads in ascending order of size. The underlying type may be queried
> +    // for the least larger payload currently present.
> +    private volatile HashMap<String, FaviconsForURL> mBackingMap = new HashMap<String, FaviconsForURL>();

`volatile` means that modifications of the `mBackingMap` *reference* are consistent. It doesn't mean that `mBackingMap`'s contents are consistent across multiple threads, even for reads.

For that, you want `ConcurrentHashMap`, or to use locking around your modifications of the members of this class. You might also benefit from

  private FaviconsForURL getFaviconsForURL(...) {

Here's a thread that gives some more background.

http://stackoverflow.com/questions/2688629/is-a-hashmap-thread-safe-for-different-keys

@@ +108,5 @@
> +    // A linked list used to implement a queue, defining the LRU properties of the cache. Elements
> +    // contained within the various FaviconsForURL objects are held here, the least recently used
> +    // of which at the end of the list. When space needs to be reclaimed, the appropriate bitmap is
> +    // culled.
> +    private final LinkedList<FaviconCacheElement> mOrdering = new LinkedList<FaviconCacheElement>();

General rule of thumb: if you have a bunch of members of a class, you need to work really hard to convince a reviewer that you're safe not locking some of them!

@@ +116,5 @@
> +    // the primary bitmap most suited to the requested size (in cases where multiple primary bitmaps
> +    // are provided by the underlying file format).
> +
> +    private int mMaxSize;
> +    private final AtomicInteger mCurrentSize = new AtomicInteger(0);

Sometimes you modify this inside a synchronized block, and sometimes outside. Inconsistency often implies incorrectness.

@@ +376,5 @@
> +
> +        // Update the value in the LruCache...
> +        FaviconsForURL wasRemoved = mBackingMap.put(faviconURL, toInsert);
> +
> +        remove(wasRemoved);

Threading bug in these two lines. If two threads get overlapping wasRemoved, then your counts will break, no?
Attachment #808115 - Flags: review?(rnewman)
Attachment #808115 - Flags: review?(margaret.leibovic)
Attachment #808115 - Flags: review-
Attachment #808115 - Flags: feedback?(bnicholson)
(In reply to Richard Newman [:rnewman] from comment #35)
> ::: mobile/android/base/favicons/cache/FaviconCache.java
> @@ +102,5 @@
> > +    // Map relating Favicon URLs with objects representing decoded favicons.
> > +    // Since favicons may be container formats holding multiple icons, the underlying type holds a
> > +    // sorted list of bitmap payloads in ascending order of size. The underlying type may be queried
> > +    // for the least larger payload currently present.
> > +    private volatile HashMap<String, FaviconsForURL> mBackingMap = new HashMap<String, FaviconsForURL>();
> 
> `volatile` means that modifications of the `mBackingMap` *reference* are
> consistent. It doesn't mean that `mBackingMap`'s contents are consistent
> across multiple threads, even for reads.

Ah yes! Braincell! There was me thinking ConcurrentHashMap was implemented as dumb synchronisation over an ordinary HashMap.
Oh the fun one might have with the Unsafe libaray on Android...

With this in mind, a few more fields make sense to volatileify. Notably the invalidation flag for cache elements, to ensure this gets writeback before the payload is set to null.

> @@ +108,5 @@
> > +    // A linked list used to implement a queue, defining the LRU properties of the cache. Elements
> > +    // contained within the various FaviconsForURL objects are held here, the least recently used
> > +    // of which at the end of the list. When space needs to be reclaimed, the appropriate bitmap is
> > +    // culled.
> > +    private final LinkedList<FaviconCacheElement> mOrdering = new LinkedList<FaviconCacheElement>();
> 
> General rule of thumb: if you have a bunch of members of a class, you need
> to work really hard to convince a reviewer that you're safe not locking some
> of them!

I'm not sure what you're getting at - access to mOrdering is synchronised - very bad things could happen otherwise.
Perhaps you mean the way I don't hold all the locks around line 380 while doing the remove call - strong consistency is not required. The counter may be incorrect by the size of all in-flight transactions, but that's okay. We only care about "Is the cache too big yet" One or two favicons either way isn't going to make enough of a difference to this decision for us to care (Unless the cache size is set extremely small)

> 
> @@ +116,5 @@
> > +    // the primary bitmap most suited to the requested size (in cases where multiple primary bitmaps
> > +    // are provided by the underlying file format).
> > +
> > +    private int mMaxSize;
> > +    private final AtomicInteger mCurrentSize = new AtomicInteger(0);
> 
> Sometimes you modify this inside a synchronized block, and sometimes
> outside. Inconsistency often implies incorrectness.

This field is just a weakly consistent counter tracking the current size of the cache accurately enough for culling to be performed. It may in fact be wrong by up to the size of all ongoing transactions - but we don't care.
It's never necessary to lock anything when this value is changed, but sometimes it is called from inside a synchronized block. This isn't necessary, and does give nonoptimal performance - so let's fix that.

> @@ +376,5 @@
> > +
> > +        // Update the value in the LruCache...
> > +        FaviconsForURL wasRemoved = mBackingMap.put(faviconURL, toInsert);
> > +
> > +        remove(wasRemoved);
> 
> Threading bug in these two lines. If two threads get overlapping wasRemoved,
> then your counts will break, no?

Unclear. Depends on implementation of put. If put is secretly implemented as a non-atomic use of get to find the return value followed by the "real" put then we have a problem.

It appears that locking on mBackingMap for calls to put that care about the return value is a way to solve this. The implementation of ConcurrentHashMap might make this really unnecessary, but let's do it anyway.

The value of the size count will be larger than it should be by the size of the old value until remove has done its work. This seems unimportant - strong consistency is expensive.

Also, this just happened:
https://www.dropbox.com/s/b2c7r8xlmzmtdpg/Skynet.png
Attachment #808115 - Attachment is obsolete: true
Attachment #808241 - Flags: review?(rnewman)
Attachment #808241 - Attachment is obsolete: true
Attachment #808241 - Flags: review?(rnewman)
Attachment #808242 - Flags: review?(rnewman)
Comment on attachment 808242 [details] [diff] [review]
V14 - Even More Newmanification - Add more intelligent caching to the Favicons system.

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

Sunday night driveby.

::: mobile/android/base/favicons/cache/FaviconCache.java
@@ +90,5 @@
> +    // The number of spaces to allocate for favicons in each node.
> +    private static final int NUM_FAVICON_SIZES = 4;
> +
> +    // Dimensions of the largest favicon to store in the cache. Everything is downscaled to this.
> +    public static int MAX_CACHED_FAVICON_WIDTH;

This isn't final and isn't set to a non-zero value within this class. That raises three questions:

 * What if you use this class before it's set? Probably sadface, no?
 * What happens when you change it at runtime? Probably some more sadface.
 * Why are you using PUBLIC_STATIC_FINAL naming convention for a non-constant?

@@ +108,5 @@
> +    // A linked list used to implement a queue, defining the LRU properties of the cache. Elements
> +    // contained within the various FaviconsForURL objects are held here, the least recently used
> +    // of which at the end of the list. When space needs to be reclaimed, the appropriate bitmap is
> +    // culled.
> +    private final LinkedList<FaviconCacheElement> mOrdering = new LinkedList<FaviconCacheElement>();

I'm not convinced by your "this doesn't need to be safe" argument. The ordering of operations on this wrt mBackingMap could cause an obvious violation of LRU semantics, right? Not to mention that separating operations on mOrdering, the `remove` method, and operations on `mBackingMap` seems error-prone.

@@ +138,5 @@
> +            return false;
> +        }
> +
> +        // If the has failed flag is not set, it's certainly not a known failure.
> +        synchronized(mBackingMap) {

Why are you synchronizing here?

@@ +157,5 @@
> +
> +        // If long enough has passed, mark it as no longer a failure.
> +        if (failureDiff > FAILURE_RETRY_MILLISECONDS) {
> +            // No longer expired.
> +            container.mHasFailed = false;

You're mutating an object inside a data structure that's subject to concurrent access. What if another thread just recorded a new failure timestamp? You'll overwrite that case between line 148 and line 161.

Later you synchronize on that object. Consider doing so here.

@@ +303,5 @@
> +     * @return The cached dominant colour, or null if none is cached.
> +     */
> +    public Integer getDominantColor(String key) {
> +        FaviconsForURL element = mBackingMap.get(key);
> +        if (element ==  null) {

Nit: double space.

@@ +313,5 @@
> +
> +        return element.getDominantColor();
> +    }
> +
> +    private void remove(FaviconsForURL wasRemoved) {

recordRemoved?
(In reply to Richard Newman [:rnewman] from comment #38)

Evening.

> ::: mobile/android/base/favicons/cache/FaviconCache.java
> @@ +90,5 @@
> > +    // The number of spaces to allocate for favicons in each node.
> > +    private static final int NUM_FAVICON_SIZES = 4;
> > +
> > +    // Dimensions of the largest favicon to store in the cache. Everything is downscaled to this.
> > +    public static int MAX_CACHED_FAVICON_WIDTH;
> 
> This isn't final and isn't set to a non-zero value within this class. That
> raises three questions:
> 
>  * What if you use this class before it's set? Probably sadface, no?
>  * What happens when you change it at runtime? Probably some more sadface.
>  * Why are you using PUBLIC_STATIC_FINAL naming convention for a
> non-constant?

This ought to be a constant, but the value used is being grabbed from the android resource system because a similar value in the old caching system was obtained this way.
This gives us the handy ability to specify this value in density-corrected pixels and have android work out the conversion for us magically. (The value is set from Favicons.attachToContext - a time when the Context we need to get resources is available.)

Unclear how to do this properly.
 
> @@ +108,5 @@
> > +    // A linked list used to implement a queue, defining the LRU properties of the cache. Elements
> > +    // contained within the various FaviconsForURL objects are held here, the least recently used
> > +    // of which at the end of the list. When space needs to be reclaimed, the appropriate bitmap is
> > +    // culled.
> > +    private final LinkedList<FaviconCacheElement> mOrdering = new LinkedList<FaviconCacheElement>();
> 
> I'm not convinced by your "this doesn't need to be safe" argument. The
> ordering of operations on this wrt mBackingMap could cause an obvious
> violation of LRU semantics, right? Not to mention that separating operations
> on mOrdering, the `remove` method, and operations on `mBackingMap` seems
> error-prone.
>
> @@ +138,5 @@
> > +            return false;
> > +        }
> > +
> > +        // If the has failed flag is not set, it's certainly not a known failure.
> > +        synchronized(mBackingMap) {
> 
> Why are you synchronizing here?
> 

Hmm. I've not thought about the concurrency of this implementation enough (Largely because I assumed it would only ever be used from one thread when I wrote it, and then bolted thread-safety on when you mentioned it  - whoops).
This won't do.

Since the old implementation also wasn't thread safe (IIRC), a heavy-handed lock-ALL-the-things approach is liable to cause performance issues - and anyway, we can do better.
The sort of complicated fine-grained locking approach I've been trying to use here is, it turns out, implemented incorrectly and, it seems, not easy to understand (Or not adaquetely documented by me, or something.)
So, even if/when I do get it right it'll be unmaintainable and awful.
That also won't do.

We don't require strong consistency. It doesn't matter if a certin request doesn't see the write that just happened if it races with it (This situation is so rare that the extra cache miss is worth less than the locking we get to not do).
Likewise, we also don't really care if the cache isn't always perfectly exhibiting LRU behaviour - as long as it's a good enough approximation.
For example, do we really care if:
A request to use the least-recently-used element races with a cull, the cull culls the element, but the element is returned (Intact) to the user anyway? (But no longer exists in the cache)
Sure, we're not really LRU any more, but the extra locking needed to deal with this horribly obscure edgecase far outweighs the benefits. As long as we never return an element that's been marked invalid and had its payload deleted this is fine.
It's a favicon cache - as long as it's fast, hits often, and doesn't eat all our memory it need not be perfectly LRU. NRU has been known to perform comparably well in some situations.

So, what's a standard solution to a standard problem that's well known, well documented, and is sufficiently close to the one we're trying to solve that we can apply it and get performance close enough to optimal without making the programmers that come after me want to hunt me down and kill me for writing unmaintainable code?

It seems that what we have here is almost but not quite entirely unlike MRSW. We lose a little bit of concurrency on writes, but it's good enough and it's dead simple.
Also, I've been stupid. I thought until recently that most of the shiny toys in the concurrency libraries for Java were implemented atop synchronisation and were thus absurdly expensive.
It turns out I am, in most implementations, completely wrong. It's like christmas!

If we apply the classic fair solution to MRSW using Semaphores, with a slight tweak, we can get safe, comprehendible thread safety that will under most circumstances probably outperform what I was trying to do earlier with fine-grained locking.
Alas, the slight tweak needed to allow readers to update the most-recently-used ordering prevents use of ReentrantReadWriteLock (At least, in a readable way). The correctness of the approach used may require some thought.

You see, an LRU cache doesn't entirely fit MRSW - readers also need to "write" in that they need to update the most-recently-used list. The obvious solution is to have all such txns be writers, but then we degrade to locking everything all the time - that's no good.

Having classified our operations as reads or writes in the obvious way, we find that mOrdering is only ever read from writer transactions. This follows - we don't care about the ordering from reader threads - we only want that when we're thinking of deleting something.
But we do want to write to the structure from reader threads, when setting the most recently used. But this is fine - it is sufficient, since we only need weak consistency, to tack on an extra semaphore ensuring mutual exclusion when doing setMostRecentlyUsed.

Does this make any approximation to sense? This hybrid two-way MRSW solution seems much more neat than the earlier attempt, and I'm finally able to convince myself of its correctness. It's also simpler, shorter, and probably usually not slower.
What do you think?
Attachment #808242 - Attachment is obsolete: true
Attachment #808242 - Flags: review?(rnewman)
Attachment #808447 - Flags: review?(rnewman)
Fixing a comment.
Attachment #808447 - Attachment is obsolete: true
Attachment #808447 - Flags: review?(rnewman)
Attachment #808449 - Flags: review?(rnewman)
Attachment #808449 - Attachment is obsolete: true
Attachment #808449 - Flags: review?(rnewman)
Attachment #808450 - Flags: review?(rnewman)
https://tbpl.mozilla.org/?tree=Try&rev=af91861829e4

Turns out that double-ended queues weren't added to Android until API level 9.
Thanks, lads.

Updating my patch to tolerate this insanity.

Try push:
https://tbpl.mozilla.org/?tree=Try&rev=3695e65fcfed
Attachment #808450 - Attachment is obsolete: true
Attachment #808450 - Flags: review?(rnewman)
Attachment #808458 - Flags: review?(rnewman)
Comment on attachment 808458 [details] [diff] [review]
V17 - Mutant-MRSW - Add more intelligent caching to the Favicons system.

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

Morning partial review.

General comment: there might be other (better?) approaches to concurrency here -- e.g., one might imagine the favicon cache as a thread-local, populated on-demand from the DB. I leave you to consider whether that would work, or whether having genuine thread-safety is a better approach. (It probably is, but that's your call.)

::: mobile/android/base/favicons/cache/FaviconCache.java
@@ +94,5 @@
> +    // The number of spaces to allocate for favicons in each node.
> +    private static final int NUM_FAVICON_SIZES = 4;
> +
> +    // Dimensions of the largest favicon to store in the cache. Everything is downscaled to this.
> +    public static int MAX_CACHED_FAVICON_WIDTH;

If this is grabbed from R by Favicons, why is it not a member+constructor param for the cache?

@@ +120,5 @@
> +    // the primary bitmap most suited to the requested size (in cases where multiple primary bitmaps
> +    // are provided by the underlying file format).
> +
> +    private final int mMaxSize;
> +    private final AtomicInteger mCurrentSize = new AtomicInteger(0);

This really needs to be labeled, and perhaps renamed -- as far as I can tell this is the aggregate pixel count of all of the cached favicon bitmaps, but that doesn't really tell us too much -- some bitmaps are 4 bytes per pixel, some 2.

http://developer.android.com/reference/android/graphics/Bitmap.Config.html

@@ +193,5 @@
> +     */
> +    public boolean isFailedFavicon(String faviconURL) {
> +        startRead();
> +
> +        FaviconsForURL container = mBackingMap.get(faviconURL);

Throws if faviconURL is null, which will lock this class permanently. Don't let that happen.

@@ +223,5 @@
> +        if (failureDiff > FAILURE_RETRY_MILLISECONDS) {
> +            // No longer expired.
> +            startWrite();
> +            container.mHasFailed = false;
> +            finishWrite();

This doesn't seem right to me. You can't finish your read [L212], do some logic (with stale values), then do a blind write -- you can still get operation interleaving. Either prove that I'm wrong in a comment, prove that it doesn't apply (e.g., every operation that will hit this case is guaranteed to come from the same thread), or address this case...

@@ +312,5 @@
> +        // where what we want should live in the list. We now request the next least larger primary
> +        // from the cache. We will downscale this to our target size.
> +
> +        // If there is no such primary, we'll upscale the next least smaller one instead.
> +        cacheElement = container.getNextPrimary(cacheElementIndex);

Everything from line 286 to line 316 should be a method on FaviconsForURL: getCacheElementForSize, perhaps. Look at the response to implement the logic in lines 301-302.

@@ +329,5 @@
> +        Bitmap newBitmap;
> +        boolean startedWrite = false;
> +        if (largestSize >= targetSize) {
> +            // The largest we have is larger than the target - downsize to target.
> +            newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);

It's hard to imagine that no parts of this broader method will throw (right here, for example), and yet doing so will leak the lock and bind up the cache.

@@ +346,5 @@
> +                finishRead();
> +                startWrite();
> +                startedWrite = true;
> +                // And since we failed, we'll need the dominant colour.
> +                container.ensureDominantColor();

I thought you were going to make color determination lazy?

@@ +412,5 @@
> +            mCurrentSize.addAndGet(-sizeRemoved);
> +        }
> +    }
> +
> +    private Bitmap prepareBitmapForCaching(Bitmap favicon) {

produceCacheableBitmap?

@@ +448,5 @@
> +     * @param faviconURL The URL of the Favicon being stored.
> +     * @param favicon The Favicon to store.
> +     */
> +    public void putSingleFavicon(String faviconURL, Bitmap favicon) {
> +        favicon = prepareBitmapForCaching(favicon);

I can't believe your IDE didn't give you a style warning about assignment to a parameter!
(In reply to Richard Newman [:rnewman] from comment #43)
> General comment: there might be other (better?) approaches to concurrency
> here -- e.g., one might imagine the favicon cache as a thread-local,
> populated on-demand from the DB. I leave you to consider whether that would
> work, or whether having genuine thread-safety is a better approach. (It
> probably is, but that's your call.)

I don't think thread-local is a good idea for the favicon cache is a good idea - we'd end up with far worse cache behaviour, particularly if we ever succeed in making our page loading more concurrent than it currently is.
Having a central cache is good for having maximal cache hits, provided we can get the locking done sanely. There certainly exist approaches more efficient than the one presented here, but this one is simple, and the others I can think of very much are not.
Can always make it horribly complicated in a followup if it is found to be too slow.

> @@ +120,5 @@
> > +    // the primary bitmap most suited to the requested size (in cases where multiple primary bitmaps
> > +    // are provided by the underlying file format).
> > +
> > +    private final int mMaxSize;
> > +    private final AtomicInteger mCurrentSize = new AtomicInteger(0);
> 
> This really needs to be labeled, and perhaps renamed -- as far as I can tell
> this is the aggregate pixel count of all of the cached favicon bitmaps, but
> that doesn't really tell us too much -- some bitmaps are 4 bytes per pixel,
> some 2.
> 
> http://developer.android.com/reference/android/graphics/Bitmap.Config.html

This is not the aggregate pixel count. This is the sum of:
Bitmap.getRowBytes() * Bitmap.getHeight()
Over all bitmaps in the cache.

Which is the android2.2-compatible way of doing Bitmap.getByteCount().

That is, the counter is ostensibly the number of bytes of bitmap data in the cache, which I think is what we want.

> @@ +223,5 @@
> > +        if (failureDiff > FAILURE_RETRY_MILLISECONDS) {
> > +            // No longer expired.
> > +            startWrite();
> > +            container.mHasFailed = false;
> > +            finishWrite();
> 
> This doesn't seem right to me. You can't finish your read [L212], do some
> logic (with stale values), then do a blind write -- you can still get
> operation interleaving. Either prove that I'm wrong in a comment, prove that
> it doesn't apply (e.g., every operation that will hit this case is
> guaranteed to come from the same thread), or address this case...

Hmm. This is stupid.
The logic for expiring failures isn't sensible.

What makes more sense is for the timestamp to be final in FaviconsForURL - it's literally a "Creation of this object" timestamp, which is close enough to "Time when we downloaded this favicon" timestamp.
Then, we implement failure expiry as usual, but just remove the madness that is FAILED_EXPIRY_NEVER. Makes no sense anyway, if we set a sensible retry delay.

This simplifies things a lot, but doesn't entirely cure the problem you highlight. I've added an upgradeReadToWrite method which safely ensures that an ongoing read can upgrade to a write when needed without other transactions being able to jump in. Should solve the problem you mentioned.

> @@ +312,5 @@
> > +        // where what we want should live in the list. We now request the next least larger primary
> > +        // from the cache. We will downscale this to our target size.
> > +
> > +        // If there is no such primary, we'll upscale the next least smaller one instead.
> > +        cacheElement = container.getNextPrimary(cacheElementIndex);
> 
> Everything from line 286 to line 316 should be a method on FaviconsForURL:
> getCacheElementForSize, perhaps. Look at the response to implement the logic
> in lines 301-302.
> 
> @@ +329,5 @@
> > +        Bitmap newBitmap;
> > +        boolean startedWrite = false;
> > +        if (largestSize >= targetSize) {
> > +            // The largest we have is larger than the target - downsize to target.
> > +            newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);
> 
> It's hard to imagine that no parts of this broader method will throw (right
> here, for example), and yet doing so will leak the lock and bind up the
> cache.

This is stupid. I should be using a try..finally block to ensure this problem doesn't exist.

> @@ +346,5 @@
> > +                finishRead();
> > +                startWrite();
> > +                startedWrite = true;
> > +                // And since we failed, we'll need the dominant colour.
> > +                container.ensureDominantColor();
> 
> I thought you were going to make color determination lazy?

This IS the lazy colour determination.
This function is the "Get me a favicon that is this big" function. But if I ask for a 128x128 pixel image and the best primary we have is 16x16 it's not going to do the unreasonable upscale. It will upscale as appropriate by a maximum of a factor of two. The code path you're highlighting is executed only in the case that the size requested is larger than the size reachable by such an upscale of the largest available primary.
If you're asking for an image larger than the best we can give you, you're going to want the dominant colour - this is the only time you'll ever want the dominant colour, so this is where the dominant colour is calculated. (Also, on the background thread, generally).

> @@ +448,5 @@
> > +     * @param faviconURL The URL of the Favicon being stored.
> > +     * @param favicon The Favicon to store.
> > +     */
> > +    public void putSingleFavicon(String faviconURL, Bitmap favicon) {
> > +        favicon = prepareBitmapForCaching(favicon);
> 
> I can't believe your IDE didn't give you a style warning about assignment to
> a parameter!

I turned that one off ;).
Actually, I thought this style was okay when used in obvious ways right at the start. Apparently not.
Attachment #808458 - Attachment is obsolete: true
Attachment #808458 - Flags: review?(rnewman)
Attachment #808942 - Flags: review?(rnewman)
Comment on attachment 808942 [details] [diff] [review]
V18 - Rigorously Mutant-MRSW - Add more intelligent caching to the Favicons system.

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

I'm pretty happy with where this is heading. I ran out of steam before thoroughly reviewing Favicons.java, but I did the rest in-depth. Next review should be perfunctory, so long as you address all of my comments!

My one remaining concern is about how/whether this has been tested. To a point I'm happy with it hitting Nightly, but backing it out would be a pain, so I'd like to make sure it's solid first... and part of that is testing.

::: mobile/android/base/BrowserApp.java
@@ +1337,4 @@
>  
> +                        // The tab might be pointing to another URL by the time the
> +                        // favicon is finally loaded, in which case we simply ignore it.
> +                        if (!tab.getURL().equals(pageUrl))

I'd go so far as to say that this is too absolute, given that this shouldn't be long after the page was loaded: we should be comparing some subset of the URL (e.g., host + path), so that a post-load event that changes the page URL (e.g., appending a #) doesn't cause our favicon to not load for a prolonged period.

If you agree, file a follow-up?

::: mobile/android/base/Tabs.java
@@ +374,5 @@
>              }
>  
>              // All other events handled below should contain a tabID property
>              int id = message.getInt("tabID");
> +            Tab tab = getTabForId(id);

Changing this method name added a lot of changes to this patch, and I don't think the increased clarity is worth the cost.

@@ +600,5 @@
>      }
>  
> +    public Tab getTabForUrl(String url) {
> +        int tabId = getTabIdForUrl(url);
> +        return getTabForId(tabId);

Safety! The point of introducing this method was to avoid a race between these two lines…

::: mobile/android/base/favicons/LoadFaviconTask.java
@@ +42,5 @@
>  public class LoadFaviconTask extends UiAsyncTask<Void, Void, Bitmap> {
>      private static final String LOGTAG = "LoadFaviconTask";
>  
> +    // Access to this map needs to be synchronized to ensure funky scheduling conditions don't allow
> +    // multiple jobs to fetch the same Favicon to coexist.

"to fetch the same favicon simultaneously.", or s/to fetch/fetching.

::: mobile/android/base/favicons/cache/FaviconCache.java
@@ +116,5 @@
> +    // favicon payloads in the system, as well as enabling the dynamic selection from the cache of
> +    // the primary bitmap most suited to the requested size (in cases where multiple primary bitmaps
> +    // are provided by the underlying file format).
> +
> +    private final int mMaxSize;

mMaxCachedElements

@@ +145,5 @@
> +    private void startRead() {
> +        mTurnSemaphore.acquireUninterruptibly();
> +        mTurnSemaphore.release();
> +
> +        if (mOngoingReads.incrementAndGet() == 1) {

By comparison to line 180, my gut tells me that the turn semaphore should be released after this is incremented.

@@ +174,5 @@
> +    /**
> +     * An alternative to startWrite to be used when in a read transaction and wanting to upgrade it
> +     * to a write transaction. Such a transaction should be terminated with finishWrite.
> +     */
> +    private void upgradeReadToWrite() {

Move this method to directly under startRead, because they are very closely coupled.

@@ +245,5 @@
> +                mBackingMap.remove(faviconURL);
> +                return false;
> +            }
> +        } finally {
> +            finishWrite();

This will execute even if `isExpired` is false, which is a bad thing. You should probably include a `return` in the `else` clause in the previous `finally` block, or ensure that all non-write paths through the previous block end in a `return`.

This gives me a hint that you're not adequately testing this code…

@@ +339,5 @@
> +                // The primary has been invalidated! Fail! Need to get it back from the database.
> +                return null;
> +            }
> +
> +            doingWrites = true;

Add a comment that all previous code paths end in a `return`, and thus we're expecting to fall through to the next `try`.

@@ +347,5 @@
> +            int largestSize = cacheElement.mImageSize;
> +
> +            if (largestSize >= targetSize) {
> +                // The largest we have is larger than the target - downsize to target.
> +                newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);

If this throws, you'll still hit the `upgradeReadToWrite` case, and then you'll bomb out with an exception. That's probably not what you want.

@@ +383,5 @@
> +            // While the image might not actually BE that size, we set the size field to the target because
> +            // this is the best image you can get for a request of that size using the Favicon information
> +            // provided by this website.
> +            // This way, subsequent requests hit straight away.
> +            newElement.mImageSize = targetSize;

Make this a constructor param and chain it through addSecondary. That way `mImageSize` can be final, and you're not elbow-deep in guts.

@@ +389,5 @@
> +            setMostRecentlyUsed(newElement);
> +
> +            mCurrentSize.addAndGet(newElement.sizeOf());
> +
> +            cullIfRequired();

Shouldn't this be called outside of the write lock? It takes the lock itself.

Actually, I would delete this line altogether. It's enough to cull when we insert new icons.

@@ +403,5 @@
> +     *
> +     * @param key The URL of the Favicon for which a dominant colour is desired.
> +     * @return The cached dominant colour, or null if none is cached.
> +     */
> +    public Integer getDominantColor(String key) {

Elsewhere you use -1 to mean no value, so return int here.

@@ +408,5 @@
> +        startRead();
> +
> +        try {
> +            if (!mBackingMap.containsKey(key)) {
> +                Log.w(LOGTAG, "Attempt to get dominant colour of uncached favicon "+key+"- this isn't going to work.");

Spaces around concatenation, and you can shorten this:

  Log.w(LOGTAG, "Cannot compute dominant color of non-cached favicon " + key);

@@ +417,5 @@
> +            FaviconsForURL element = mBackingMap.get(key);
> +
> +            element.ensureDominantColor();
> +
> +            return element.getDominantColor();

Can you just have `ensureDominantColor` return the newly computed color, and save the second call?

@@ +423,5 @@
> +            finishRead();
> +        }
> +    }
> +
> +    private void recordRemoved(FaviconsForURL wasRemoved) {

Add a comment that this should only be called inside a write lock.

@@ +425,5 @@
> +    }
> +
> +    private void recordRemoved(FaviconsForURL wasRemoved) {
> +        // If there was an existing value, strip it from the insertion-order cache.
> +        if (wasRemoved != null) {

Prefer early return:

  if (wasRemoved == null) {
      return;
  }

@@ +523,5 @@
> +        try {
> +            for (Bitmap favicon : favicons) {
> +                favicon = produceCacheableBitmap(favicon);
> +                if (favicon == null) {
> +                    continue;

We're locking out readers while we do all of this work.

Instead, make `favicons` an Iterator (so it can drop references as it goes), walk it spitting elements into toInsert and accumulating an increment value for mCurrentSize, *then* take the write lock and push toInsert into the cache, queue, and counter.

@@ +563,5 @@
> +            while (mCurrentSize.get() > mMaxSize) {
> +                // Cull the least recently used element.
> +
> +                FaviconCacheElement victim;
> +                victim = mOrdering.poll();

poll removes from the head of the list. That means you're evicting the most recently used. You really want to evict from the tail end.

Because of the specific operations you perform -- removing oldest, removing an old item and making it the newest -- you might consider reversing this list, keeping the oldest at the head. Or use a dequeue.

Furthermore, don't you need to take the reordering semaphore here? (with the same scope as the write lock)

::: mobile/android/base/favicons/cache/FaviconCacheElement.java
@@ +28,5 @@
> +
> +    volatile int mImageSize;
> +
> +    // Used for LRU pruning.
> +    FaviconsForURL mBackpointer;

This is only set in one place, immediately after construction, so make it final and a constructor param! If it's optional, you need to null check it.

@@ +84,5 @@
> +
> +    /**
> +     * Called when this element is evicted from the cache.
> +     *
> +     * If primary, drop the payload an set invalid. If secondary, just unlink from parent node.

an/and

@@ +97,5 @@
> +            mInvalidated = true;
> +            mFaviconPayload = null;
> +        } else {
> +            // Secondaries don't matter - just delete them.
> +            mBackpointer.mFavicons.remove(this);

You're trusting that someone has set mBackpointer. Null check here.

::: mobile/android/base/favicons/cache/FaviconsForURL.java
@@ +130,5 @@
> +            searchIndex--;
> +        }
> +
> +        // Somehow we have no primaries in this structure at all? This is madness!
> +        Log.e(LOGTAG, "No primaries found in Favicon cache structure. This is madness!");

Redundant comment.

@@ +145,5 @@
> +     */
> +    public void ensureDominantColor() {
> +        if (mDominantColor == -1) {
> +            mDominantColor = BitmapUtils.getDominantColor(getNextPrimary(0).mFaviconPayload);
> +        }

return mDominantColor.

::: mobile/android/base/gfx/GeckoLayerClient.java
@@ +411,5 @@
>  
>      /* This is invoked by JNI on the gecko thread */
>      DisplayPortMetrics getDisplayPort(boolean pageSizeUpdate, boolean isBrowserContentDisplayed, int tabId, ImmutableViewportMetrics metrics) {
>          Tabs tabs = Tabs.getInstance();
> +        if (tabs.isSelectedTab(tabs.getTabForId(tabId)) && isBrowserContentDisplayed) {

It would be really efficient to implement tabs.isSelectedTabById: just check mSelectedTab's ID against the input.

Also, put isBrowserContentDisplayed *first* in the conditional, 'cos it's cheap.

Follow-up is fine, 'cos this part of the diff should disappear if you undo the renaming of getTab.
Attachment #808942 - Flags: review?(rnewman) → feedback+
(In reply to Richard Newman [:rnewman] from comment #45)
> ::: mobile/android/base/BrowserApp.java
> @@ +1337,4 @@
> >  
> > +                        // The tab might be pointing to another URL by the time the
> > +                        // favicon is finally loaded, in which case we simply ignore it.
> > +                        if (!tab.getURL().equals(pageUrl))
> 
> I'd go so far as to say that this is too absolute, given that this shouldn't
> be long after the page was loaded: we should be comparing some subset of the
> URL (e.g., host + path), so that a post-load event that changes the page URL
> (e.g., appending a #) doesn't cause our favicon to not load for a prolonged
> period.
> 
> If you agree, file a follow-up?

Hmm. You're right - I think this check is quite wrong, and should instead be comparing faviconURL changes. If we switch the tab to a page with a different favicon URL, then we'll want to bin this result (And there'll be a request going through for the new result anyway). If we switch to a page with the same favicon URL and a different URL (A fresh google search, for example), then we don't really want to bin this result at all.
Seems worth a followup - perhaps have onFaviconLoaded also get the favicon URL and use that to do things more cleverly. Or something.

> @@ +600,5 @@
> >      }
> >  
> > +    public Tab getTabForUrl(String url) {
> > +        int tabId = getTabIdForUrl(url);
> > +        return getTabForId(tabId);
> 
> Safety! The point of introducing this method was to avoid a race between
> these two lines…

Tacking a synchronized keyword in there seems to do the trick, what with the methods mutating this in an interesting way also being synchronized.

> ::: mobile/android/base/favicons/cache/FaviconCache.java
> @@ +116,5 @@
> > +    // favicon payloads in the system, as well as enabling the dynamic selection from the cache of
> > +    // the primary bitmap most suited to the requested size (in cases where multiple primary bitmaps
> > +    // are provided by the underlying file format).
> > +
> > +    private final int mMaxSize;
> 
> mMaxCachedElements

Nope. This value is the maximum about of bytes of bitmap data that may be stored. mMaxSizeBytes seems more appropriate, plus a shiny new comment.

> @@ +145,5 @@
> > +    private void startRead() {
> > +        mTurnSemaphore.acquireUninterruptibly();
> > +        mTurnSemaphore.release();
> > +
> > +        if (mOngoingReads.incrementAndGet() == 1) {
> 
> By comparison to line 180, my gut tells me that the turn semaphore should be
> released after this is incremented.

The turn semaphore is simply used to ensure fairness. Readers do not need to hold it for any length of time.

This semaphore ensures that transactions start in entry-order. Without such a semaphore, writers would be starved waiting for all the readers to stop and give up the write lock.

There's no need to guard the ongoing reads counter, since it is atomic. It simply needs to ensure that the first reader to start will take the write lock and the last reader to finish will release it. The current placement of semaphores does allow for incrementing of the counter to be done in a way which violates entry order (In the case of a context switch directly after releasing the turn semaphore), we don't actually care.

I think.

I based this on the reference implementation given in last years Concurrent and Distributed Systems course at Cambridge. The relavent side deck is here:
http://www.cl.cam.ac.uk/teaching/1213/ConcDisSys/ConcurrentSystems-1B-H1.pdf
The reference MRSW implementation is on slide 47.

The reference implementation uses an additional semaphore to get mutual exclusion on the ongoing reads counter - making this counter atomic is just as good, unless you really, really care about maintaining entry-order incrementing of the counter (For, eg. Giving transactions unique ids.). We don't. I think.

> @@ +245,5 @@
> > +                mBackingMap.remove(faviconURL);
> > +                return false;
> > +            }
> > +        } finally {
> > +            finishWrite();
> 
> This will execute even if `isExpired` is false, which is a bad thing. You
> should probably include a `return` in the `else` clause in the previous
> `finally` block, or ensure that all non-write paths through the previous
> block end in a `return`.
> 
> This gives me a hint that you're not adequately testing this code…

Ah.
Sanity check: A return inside a try will run the finally block and then stop, right? It doesn't run the finally and then continue to the following code?

If so, then no return is needed in the else, as the only time we reach it is when we've returned from inside the try. We need a return true in an else on the failureDiff check, and then we can cull the if statement in the second try as it is only reachable in the case that isExpired is true (As we only ever reach it in this case.)
Returning from inside a finally should be avoided very, very strongly. It causes uncaught exceptions to silently vanish, instead of being handled by the unhandled exception handler. This can lead to astonishingly hard to debug problems, as the NPE (or such) that you really want was silently eaten by your finally-return.

> @@ +347,5 @@
> > +            int largestSize = cacheElement.mImageSize;
> > +
> > +            if (largestSize >= targetSize) {
> > +                // The largest we have is larger than the target - downsize to target.
> > +                newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);
> 
> If this throws, you'll still hit the `upgradeReadToWrite` case, and then
> you'll bomb out with an exception. That's probably not what you want.

Ah. So in this case the exception is thrown and the function returns, without going on to the next try?

So, I've added an exception handler to cases where the lock upgrading function is used that will gracefully abort without putting the locks into a bad state in case of exceptions.
In case of errors, the locks being in an inconsistent state is the least of our concerns.

> @@ +389,5 @@
> > +            setMostRecentlyUsed(newElement);
> > +
> > +            mCurrentSize.addAndGet(newElement.sizeOf());
> > +
> > +            cullIfRequired();
> 
> Shouldn't this be called outside of the write lock? It takes the lock itself.
> 
> Actually, I would delete this line altogether. It's enough to cull when we
> insert new icons.

Seems sane - we will be adding secondaries from this method, but we're also adding fresh icons sufficiently often that it'll be okay this way.

> @@ +523,5 @@
> > +        try {
> > +            for (Bitmap favicon : favicons) {
> > +                favicon = produceCacheableBitmap(favicon);
> > +                if (favicon == null) {
> > +                    continue;
> 
> We're locking out readers while we do all of this work.
> 
> Instead, make `favicons` an Iterator (so it can drop references as it goes),

Not sure what you mean by this - you want to use iterator.remove after each iteration to destroy the input list?
The for..in loop implicitly uses an iterator.

            for (Bitmap favicon : favicons) {

Compiles to exactly the same bytecode as:

            Iterator<Bitmap> i = favicons.iterator();
            while (i.hasNext()) {
                Bitmap favicon = i.next();

Still, it makes lots of sense to do the expensive downscaling in produceCacheableBitmap while not holding the lock.

> @@ +563,5 @@
> > +            while (mCurrentSize.get() > mMaxSize) {
> > +                // Cull the least recently used element.
> > +
> > +                FaviconCacheElement victim;
> > +                victim = mOrdering.poll();
> 
> poll removes from the head of the list. That means you're evicting the most
> recently used. You really want to evict from the tail end.
> 
> Because of the specific operations you perform -- removing oldest, removing
> an old item and making it the newest -- you might consider reversing this
> list, keeping the oldest at the head. Or use a dequeue.
> 
> Furthermore, don't you need to take the reordering semaphore here? (with the
> same scope as the write lock)

So this is slightly stupid. I was initially using a dequeue, but Android 2.2 doesn't support them. Seriously - they only added the support for the dequeue interface to LinkedList and friends in API level 9.
But I don't need a dequeue - an ordinary queue is sufficient. Shove most recently used elements in one end. When an element is used, find it in linear time and move it back to the start in constant time. When you want to cull, grab the element from the end of the queue.

However, I'm not sure you're right. I'm inserting elements with offer (Which puts them at the back of the line) and removing them with poll (Which removes them from the front of the line). Isn't this correct?

> @@ +97,5 @@
> > +            mInvalidated = true;
> > +            mFaviconPayload = null;
> > +        } else {
> > +            // Secondaries don't matter - just delete them.
> > +            mBackpointer.mFavicons.remove(this);
> 
> You're trusting that someone has set mBackpointer. Null check here.

This should absolutely never be called on an object that's got a null backpointer, but adding it anyway.

> ::: mobile/android/base/gfx/GeckoLayerClient.java
> @@ +411,5 @@
> >  
> >      /* This is invoked by JNI on the gecko thread */
> >      DisplayPortMetrics getDisplayPort(boolean pageSizeUpdate, boolean isBrowserContentDisplayed, int tabId, ImmutableViewportMetrics metrics) {
> >          Tabs tabs = Tabs.getInstance();
> > +        if (tabs.isSelectedTab(tabs.getTabForId(tabId)) && isBrowserContentDisplayed) {
> 
> It would be really efficient to implement tabs.isSelectedTabById: just check
> mSelectedTab's ID against the input.
> 
> Also, put isBrowserContentDisplayed *first* in the conditional, 'cos it's
> cheap.
> 
> Follow-up is fine, 'cos this part of the diff should disappear if you undo
> the renaming of getTab.

So very much not my code, and entirely out of scope, but let's do it anyway.
In general, pre-Proguard we'll also save nontrivially by making Tabs static, not singleton.

Although, pre-Proguard isn't going to be much longer, seemingly.
Attachment #808942 - Attachment is obsolete: true
Attachment #809577 - Flags: review?(rnewman)
(In reply to Chris Kitching [:ckitching] from comment #46)

> Seems worth a followup - perhaps have onFaviconLoaded also get the favicon
> URL and use that to do things more cleverly. Or something.

File it!


> Sanity check: A return inside a try will run the finally block and then
> stop, right? It doesn't run the finally and then continue to the following
> code?

Test it and see. :P

(Yes: code within a `finally` block is executed in depthwise order on return, and only the `finally` blocks will be executed.)


> We need a return true in an else on the failureDiff check

That's one possibility, as I wrote: "or ensure that all non-write paths through the previous block end in a `return`".


> Ah. So in this case the exception is thrown and the function returns,
> without going on to the next try?

Yes. An unhandled exception breaks the current flow of execution, hits `finally` blocks on the way out, and continues up the stack until caught. That you hit one `finally` which starts a 'transaction', but never continue on the flow of execution, is the problem.


> > We're locking out readers while we do all of this work.
> > 
> > Instead, make `favicons` an Iterator (so it can drop references as it goes),
> 
> Not sure what you mean by this - you want to use iterator.remove after each
> iteration to destroy the input list?

I mean (untested, but you get the idea):

    /**
     * Set the collection of primary favicons for the given URL to the provided collection of bitmaps.
     *
     * @param faviconURL The URL from which the favicons originate.
     * @param favicons A List of favicons decoded from this URL.
     */
    public void putFavicons(String faviconURL, Iterator<Bitmap> favicons) {
        // Create a fresh container for the favicons associated with this URL. Allocate extra slots
        // in the underlying ArrayList in case multiple secondary favicons are later created.
        FaviconsForURL toInsert = new FaviconsForURL(favicons.size() * NUM_FAVICON_SIZES);

        ArrayList<FaviconCacheElement> elements = new ArrayList<FaviconCacheElement>();
        int sizes = 0;
        while (favicons.hasNext()) {
            Bitmap f = produceCacheableBitmap(favicons.next());
            if (f == null) {
                continue;
            }
            FaviconCacheElement e = toInsert.addPrimary(f);
            elements.add(e);
            sizes += e.sizeOf();
        }

        startWrite();
        try {
            recordRemoved(mBackingMap.put(faviconURL, toInsert));
            mReorderingSemaphore.acquireUninterruptibly();
            try {
                for (FaviconCacheElement e : elements) {
                    // We know they're new.
                    mOrdering.offer(e);
                }
            } finally {
                mReorderingSemaphore.release();
            }
            mCurrentSize.addAndGet(sizes);
        } finally {
            finishWrite();
        }
        cullIfRequired();
    }


> However, I'm not sure you're right. I'm inserting elements with offer (Which
> puts them at the back of the line) and removing them with poll (Which
> removes them from the front of the line). Isn't this correct?

You're right; I misread the doc for `offer`. (I thought it was stupid that there were two methods to do the same insertion, but after all `poll` and `remove` are identical, so I shrugged and moved on...)


> > You're trusting that someone has set mBackpointer. Null check here.
> 
> This should absolutely never be called on an object that's got a null
> backpointer, but adding it anyway.

Welcome to production software :)


> So very much not my code, and entirely out of scope, but let's do it anyway.
> In general, pre-Proguard we'll also save nontrivially by making Tabs static,
> not singleton.

Tabs used to be somewhat static. We're deliberately moving away from that world for a number of reasons, not least being that being limited to a single collection of tabs in a browser is a very limiting move.


> Although, pre-Proguard isn't going to be much longer, seemingly.

Great news!
Blocks: 920331
(In reply to Richard Newman [:rnewman] from comment #47)
> (In reply to Chris Kitching [:ckitching] from comment #46)
> 
> > Seems worth a followup - perhaps have onFaviconLoaded also get the favicon
> > URL and use that to do things more cleverly. Or something.
> 
> File it!

Bug 920331.

> > Ah. So in this case the exception is thrown and the function returns,
> > without going on to the next try?
> 
> Yes. An unhandled exception breaks the current flow of execution, hits
> `finally` blocks on the way out, and continues up the stack until caught.
> That you hit one `finally` which starts a 'transaction', but never continue
> on the flow of execution, is the problem.

As I thought. Just checking - been a while since I did strange things with finally.

> I mean (untested, but you get the idea):

Gone a bit better than that, I think. I still don't understand why you want to take an iterator instead of a list as a parameter - this makes no difference and is just less neat since you can't use for..in?

Anyway, with the new approach we take the read lock to do the reordering and then upgrade to the write lock, briefly, to do the tiny amount of work at the end.
Attachment #809577 - Attachment is obsolete: true
Attachment #809577 - Flags: review?(rnewman)
Attachment #809601 - Flags: review?(rnewman)
Adding another bug that is solved by this patch...
Blocks: 834536
(In reply to Chris Kitching [:ckitching] from comment #48)

> Gone a bit better than that, I think. I still don't understand why you want
> to take an iterator instead of a list as a parameter - this makes no
> difference and is just less neat since you can't use for..in?

I'm trying to avoid the situation where we keep two copies of a list of bitmaps, but also minimize coupling.

In principle, the Iterator is more memory-efficient: there's no outstanding reference to items you've already processed unless the Iterator implementation keeps one.

You could achieve a similar thing by passing in an array that's intended to be mutated (only one list!), but that's tight coupling and makes it trivial to introduce mutation bugs.

You could carefully sculpt an Iterable, but pay attention to when things become garbage.
I have seen the light about iterators. Interesting idea! Apologies for my neutroniumesque prior comment.
Attachment #809601 - Attachment is obsolete: true
Attachment #809601 - Flags: review?(rnewman)
Attachment #809643 - Flags: review?(rnewman)
Attachment #809643 - Attachment is obsolete: true
Attachment #809643 - Flags: review?(rnewman)
Attachment #809644 - Flags: review?(rnewman)
Comment on attachment 809644 [details] [diff] [review]
V22 - Iterating Rigorous Mutant-MRSW - Add more intelligent caching to the Favicons system.

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

Nearly!

::: mobile/android/base/Tabs.java
@@ +270,5 @@
>          return tab != null && tab == mSelectedTab;
>      }
>  
> +    public boolean isSelectedTabById(int tabId) {
> +        return mSelectedTab != null && mSelectedTab.getId() == tabId;

One dereference.

  Tab selected = mSelectedTab;
  return selected != null && tabId == selected.getId();

::: mobile/android/base/favicons/Favicons.java
@@ +32,5 @@
> +    // Size of the favicon bitmap cache, in bytes (Counting payload only).
> +    public static final int FAVICON_CACHE_SIZE_BYTES = 1024 * 1024;
> +
> +    // Number of URL mappings from page URL to Favicon URL to cache in memory.
> +    public static final int PAGE_URL_MAPPINGS_TO_STORE = 64;

Perhaps spend ten minutes thinking about how we can tune these constants.

@@ +129,3 @@
>          }
>  
> +        return null;

Doesn't this method simplify to 

  return sFaviconsCache.getFaviconForDimensions(faviconURL, targetSize);

?

And if so, can't we just inline this in this file, and kill this method if it's not used elsewhere?

@@ +216,5 @@
> +            }
> +        };
> +
> +        // If we're already being called from the target thread, don't bother forking, else fork.
> +        if (!ThreadUtils.isOnThread(targetThread)) {

Invert these and remove the !.

@@ +363,5 @@
> +     */
> +    public static void attachToContext(Context context) {
> +        sContext = context;
> +        // Decode the default Favicon ready for use.
> +        sDefaultFavicon = BitmapFactory.decodeResource(context.getResources(), R.drawable.favicon);

This can actually return null, which would be really, really sad. Is there anything we can do to have a real live Bitmap in that case? Or is it better to NPE every time we look at the default icon?

@@ +377,5 @@
> +     */
> +    public static String guessDefaultFaviconURL(String pageURL) {
> +        // Special-casing for about: pages.
> +        if (pageURL.startsWith("about:") || pageURL.startsWith("jar:")) {
> +            return pageURL;

This doesn't make any sense at all. The favicon for about:config is "about:config"?

@@ +382,5 @@
>          }
>  
> +        try {
> +            URL pageUrl = new URL(pageURL);
> +            return new URL(pageUrl.getProtocol(), pageUrl.getAuthority(), "/favicon.ico").toString();

Oh hell no. java.net.URI, not URL!

Never, ever, ever use URL.

::: mobile/android/base/favicons/cache/FaviconCache.java
@@ +567,5 @@
> +            }
> +        } catch (Exception e) {
> +            mReorderingSemaphore.release();
> +            finishRead();
> +            abortingRead = true;

Set this first; it's the line that can't possibly throw.

::: mobile/android/base/favicons/cache/FaviconCacheElement.java
@@ +46,5 @@
> +        if (payload != null) {
> +            mImageSize = payload.getWidth();
> +        } else {
> +            mImageSize = 0;
> +        }

Chain constructors?
Attachment #809644 - Flags: review?(rnewman) → feedback+
(In reply to Richard Newman [:rnewman] from comment #53)
> ::: mobile/android/base/Tabs.java
> @@ +270,5 @@
> >          return tab != null && tab == mSelectedTab;
> >      }
> >  
> > +    public boolean isSelectedTabById(int tabId) {
> > +        return mSelectedTab != null && mSelectedTab.getId() == tabId;
> 
> One dereference.
> 
>   Tab selected = mSelectedTab;
>   return selected != null && tabId == selected.getId();

I'll do this for neatness, but this will actually produce more bytecode instructions, not fewer. If this was suggested for performance, then your way will (unless the compiler is clever) make it (Very, very slightly) slower.

So, to perform one dereference, my way, would be something like
push someConstant  (Where the constant is the field ID of mSelectedTab)
getfield           (Now mSelectedTab is atop the stack)
... invoke method, blah de blah....

Ordinarily, to access a local variable the VM also needs two instructions - push the index in the local variable table and then run the dereference instruction for it. For efficiency, the VM also provides three shortcut instructions that can in one instruction access the first 3 values in the local variable table (The instructions are just "Get the first one", "Get the second one", etc. Instead of "Get the nth one, where n is atop the stack"). For the purposes of counting local variable frame size, parameters count, too.

So, in this case, our local variable table only contains tabId and, with your suggestion, will now also contain selected. This means we can access selected with just one instruction, saving us an instruction on each dereference.

Unfortunately, we need three instructions to set selected (The two shown above plus a store). As a result, for just two references to mSelectedTab, your change actually gives us one extra bytecode instruction (1 for each of the two dereferences plus 3 to setup the local variable, as opposed to just two per dereference.)

The above applies to the stack-based JVM, of course. Things may behave somewhat differently after dexing. Certainly, though, optimising which variables end up in those first three slots and working out when it is/is not useful to do changes like your suggestion is one of the optimisations Proguard does - so I'd guess that dexing doesn't fix it, else why would they implement it?

Interesting theory aside, your way is somewhat neater, so let's do it.

> ::: mobile/android/base/favicons/Favicons.java
> @@ +32,5 @@
> > +    // Size of the favicon bitmap cache, in bytes (Counting payload only).
> > +    public static final int FAVICON_CACHE_SIZE_BYTES = 1024 * 1024;
> > +
> > +    // Number of URL mappings from page URL to Favicon URL to cache in memory.
> > +    public static final int PAGE_URL_MAPPINGS_TO_STORE = 64;
> 
> Perhaps spend ten minutes thinking about how we can tune these constants.

FAVICON_CACHE_SIZE_BYTES is the amount of bitmap bytes (Decoded) we can store in the cache, and is the same value that was used in the old cache implementation.
Assuming 24 bits per pixel, and 128x128px favicons, we can store (Assuming I can multiply correctly) 16 such images in the cache.
This isn't a huge number, but 128x128px favicons are extremely rare (And sufficiently infrequently used that they'll be the first thing to get culled from the cache when it fills, anyway).

Since the limit is the same as it was in the old cache, the increase in possible memory overheads is just that of overhead structrues and such - insignificant. Increasing this number would open us up to the possibility of talos regressions, but leaving it as it is makes us pretty safe from them.

Finally, the old cache, since it cached based on pageURL, almost never had a cache hit - so it would fill its cache up very quickly with copies of the google favicon every time you did a search, and so on. Since the new cache doesn't behave in this way, the same amount of space ought to be able to "Go further". So I'm pretty happy with this number.

The PAGE_URL_MAPPINGS_TO_STORE value represents how many mappings between page URLs and favicon URLs to store in memory for use by TwoLinePageRow (Because, for slightly annoying reasons, it still requests icons in terms of their page URL, and changing this would require a schema change for the database - something that isn't really doable at this point).
This number perhaps should be increased - since having > 64 entires in a single list of TwoLinePageRows is quite plausible. I'll double it up - smooth scrolling is nice.

> Doesn't this method simplify to 
> 
>   return sFaviconsCache.getFaviconForDimensions(faviconURL, targetSize);
> 
> ?

It does.

> And if so, can't we just inline this in this file, and kill this method if
> it's not used elsewhere?

It's used by LoadFaviconTask, so it needs to stay. It's the sort of thing that plausibly might be useful - when you just want to poll the cache and absolutely never, ever check the database or internet, so it should probably also remain public.

> @@ +363,5 @@
> > +     */
> > +    public static void attachToContext(Context context) {
> > +        sContext = context;
> > +        // Decode the default Favicon ready for use.
> > +        sDefaultFavicon = BitmapFactory.decodeResource(context.getResources(), R.drawable.favicon);
> 
> This can actually return null, which would be really, really sad. Is there
> anything we can do to have a real live Bitmap in that case? Or is it better
> to NPE every time we look at the default icon?

Wouldn't this only ever return null if we screwed up and didn't include it in the resources like we should have? If so, then crashing horribly is probably more useful for helping to find the fault than silently failing and setting a white bitmap or something. I guess I could make it return a crudely drawn, procedurally generated, bright orange sadface?

> @@ +377,5 @@
> > +     */
> > +    public static String guessDefaultFaviconURL(String pageURL) {
> > +        // Special-casing for about: pages.
> > +        if (pageURL.startsWith("about:") || pageURL.startsWith("jar:")) {
> > +            return pageURL;
> 
> This doesn't make any sense at all. The favicon for about:config is
> "about:config"?

I didn't write the database schema. It's effing awful.
about:pages sometimes provide a <link> tag to specify their favicon URL in the usual way, in which case we're happy.
Some, eg. about:home, do not, so we end up in this function.
about:home/favicon.ico isn't going to fly. It turns out that the favicon for these about:pages is bundled in the database, keyed only by page URL, hence the need to return the page URL in this case.
This could be elegantly fixed by changing the keying to suck less, but, again, deploying database schema updates to millions of users just because the bundled favicons are done strangely didn't seem to be worth the cost.

> @@ +382,5 @@
> >          }
> >  
> > +        try {
> > +            URL pageUrl = new URL(pageURL);
> > +            return new URL(pageUrl.getProtocol(), pageUrl.getAuthority(), "/favicon.ico").toString();
> 
> Oh hell no. java.net.URI, not URL!
> 
> Never, ever, ever use URL.

Seems I need to finish reading RFCs.

There are 437 other uses of java.net.URL in our codebase.

> ::: mobile/android/base/favicons/cache/FaviconCacheElement.java
> @@ +46,5 @@
> > +        if (payload != null) {
> > +            mImageSize = payload.getWidth();
> > +        } else {
> > +            mImageSize = 0;
> > +        }
> 
> Chain constructors?

Impossible to do simply, due to the finality of mImageSize.
Attachment #809644 - Attachment is obsolete: true
Attachment #810225 - Flags: review?(rnewman)
(In reply to Chris Kitching [:ckitching] from comment #54)

> > One dereference.
> > 
> I'll do this for neatness, but this will actually produce more bytecode
> instructions, not fewer. If this was suggested for performance, then your
> way will (unless the compiler is clever) make it (Very, very slightly)
> slower.

We're not doing this for performance; we're doing this to avoid a race condition on mSelectedTab.

You can also assert that mSelectedTab will never transition from non-null to null, and thus it's *OK* if we see two different consistent values here... in which case you should document that assumption and verify that it's correct!


> > Perhaps spend ten minutes thinking about how we can tune these constants.
> 
> Assuming 24 bits per pixel…

I meant something along the lines of "this is how we would attach telemetry to the operation of this class to decide if our numbers work in the real world". E.g., how would you determine, based on histograms, whether we're thrashing the cache in normal usage?


> Wouldn't this only ever return null if we screwed up and didn't include it
> in the resources like we should have? 

Or if it's somehow invalid or corrupt.

> If so, then crashing horribly is
> probably more useful for helping to find the fault than silently failing and
> setting a white bitmap or something. I guess I could make it return a
> crudely drawn, procedurally generated, bright orange sadface?

Heh.

In that case, why not throw right here if it's null?

(I practice Socratic reviewing, in case you hadn't noticed.)

> It turns out that the favicon for
> these about:pages is bundled in the database, keyed only by page URL, hence
> the need to return the page URL in this case.

Great! Put that in a comment.


> > Never, ever, ever use URL.
> 
> Seems I need to finish reading RFCs.

The reason is simple: URL is intended for network fetching, and as such it does stupid things like *RESOLVING HOSTNAMES VIA DNS WHEN COMPUTING HASHCODE*.


> There are 437 other uses of java.net.URL in our codebase.

File a bug to audit these.
Drop URL mappings on memory pressure.
Attachment #810225 - Attachment is obsolete: true
Attachment #810225 - Flags: review?(rnewman)
Attachment #810268 - Flags: review?(rnewman)
Comment on attachment 810268 [details] [diff] [review]
V24 - Memory Pressure -  Add more intelligent caching to the Favicons system.

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

OK, good enough. Now let's find the bugs: get some builds and try to break them.
Attachment #810268 - Flags: review?(rnewman) → review+
> I meant something along the lines of "this is how we would attach telemetry
> to the operation of this class to decide if our numbers work in the real
> world". E.g., how would you determine, based on histograms, whether we're
> thrashing the cache in normal usage?

Thrashing seems unlikely - we'd need a minimum of 16 large elements involved in just the wrong way to induce thrashing (Or repeated memory pressure complaints.). It may prove sensible to reduce the cache size if memory pressure is called repeatedly on the cache.

> > Wouldn't this only ever return null if we screwed up and didn't include it
> > in the resources like we should have? 
> 
> Or if it's somehow invalid or corrupt.

Adding the requested comment, throwing when no default Favicon URL available. Missed this review when submitting the last tweak - sorry about that.

> The reason is simple: URL is intended for network fetching, and as such it
> does stupid things like *RESOLVING HOSTNAMES VIA DNS WHEN COMPUTING
> HASHCODE*.

Words fail.

> > There are 437 other uses of java.net.URL in our codebase.
> 
> File a bug to audit these.

It seems my count was wrong - IDE picked up uses from in the Android source. Smooth.

Still, we use it a lot.

Bug 920855.
Attachment #810268 - Attachment is obsolete: true
Attachment #810287 - Flags: review+
Seems the other bug is going to land first. Joy. Rebasing time!
Depends on: 918917
As requested, a build with this patch:
https://www.dropbox.com/s/je7t1nfpkg1o11v/fennec-27.0a1.en-US.android-arm.apk

Go forth and break! (Or, ideally, fail to break so we can get on with landing the genuinely interesting Bug 748100 and Bug 914027.)

Try run to detect Talos screwups etc.:
https://tbpl.mozilla.org/?tree=Try&rev=acd3a8fa88c7
Status: NEW → ASSIGNED
Flags: needinfo?(margaret.leibovic)
Flags: needinfo?(aaron.train)
Rebasing atop the newest underlying patch. (Where rebasing ~~ undoing).
Attachment #810287 - Attachment is obsolete: true
Attachment #810327 - Flags: review+
Comment on attachment 810327 [details] [diff] [review]
V26 - Rebasing - Add more intelligent caching to the Favicons system.

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

Drive-by review: just had a quick look at the UI bits.

::: mobile/android/base/GeckoApp.java
@@ +1192,1 @@
>          Favicons.attachToContext(this);

nit: fix indentation here.

::: mobile/android/base/Tabs.java
@@ +269,5 @@
>      public boolean isSelectedTab(Tab tab) {
>          return tab != null && tab == mSelectedTab;
>      }
>  
> +    public boolean isSelectedTabById(int tabId) {

nit: I'd just go with isSelectedTabId() instead.

Is this method thread-safe?

::: mobile/android/base/home/BookmarksPage.java
@@ -578,5 @@
> -                        // but will at least prevent this from being too large.
> -                        thumbnails.put(url, new Thumbnail(Favicons.scaleImage(bitmap), false));
> -                    }
> -                }
> -            }

This new behaviour is not exactly what we want. Top sites thumbnails/favicons are meant to be loaded in one go. This is why both thumbnails and favicons are loaded here. With this patch, the thumbnails will load first then an async operation will be triggered to load each favicon later. This means the user will likely see the images show up at different times, which might feel a bit clunky for such a core part of the UI (especially on low-end devices).

::: mobile/android/base/home/TopBookmarkItemView.java
@@ +178,5 @@
>              displayThumbnail(R.drawable.favicon);
>              return;
>          }
>  
> +        if (faviconURL != null) {

Why would you want to keep the old value of mFaviconURL when faviconURL is null?

::: mobile/android/base/home/TopBookmarksAdapter.java
@@ +85,5 @@
>              } else {
> +                // If we have no thumbnail, attempt to show a Favicon instead.
> +                Favicons.getSizedFaviconForPageFromLocal(url, new OnFaviconLoadedListener() {
> +                    @Override
> +                    public void onFaviconLoaded(String url, String faviconURL, Bitmap favicon) {

This will likely break with view recycling given that getSizedFaviconForPageFromLocal() runs asynchronously. The target view might have been bound to another URL before the favicon finishes loading. You have to check if the view is still bound to the same URL before calling displayFavicon().

@@ +86,5 @@
> +                // If we have no thumbnail, attempt to show a Favicon instead.
> +                Favicons.getSizedFaviconForPageFromLocal(url, new OnFaviconLoadedListener() {
> +                    @Override
> +                    public void onFaviconLoaded(String url, String faviconURL, Bitmap favicon) {
> +                        view.displayFavicon(favicon, faviconURL);

The view might get detached/destroyed before the listener is called. It's probably worth checking if it's safe to call displayFavicon in this scenario. Using Loaders kinda of protected us against this.

::: mobile/android/base/home/TwoLinePageRow.java
@@ +207,2 @@
>  
> +        if (mShowIcons) {

mShowIcons is not related to favicons. It's a toggle for the bookmark/reading list icons. See removed comment.

@@ +207,5 @@
>  
> +        if (mShowIcons) {
> +            // Blank the Favicon, so we don't show the wrong Favicon if we scroll and miss DB.
> +            mFavicon.clearImage();
> +            Favicons.getSizedFaviconForPageFromLocal(url, mFaviconListener);

Given that you're not canceling obsolete requests on recycled views anymore, isn't that prone to flood the background thread with useless tasks as you scroll? This might cause a regression on perceived performance because LoadFaviconTask is an UiAsyncTask, which runs tasks serially i.e. we'd be constantly waiting for obsolete tasks to finish before loading the actually visible favicons in the list.
(In reply to Chris Kitching [:ckitching] from comment #60)
> As requested, a build with this patch:
> https://www.dropbox.com/s/je7t1nfpkg1o11v/fennec-27.0a1.en-US.android-arm.apk
> 
> Go forth and break! (Or, ideally, fail to break so we can get on with
> landing the genuinely interesting Bug 748100 and Bug 914027.)
> 
> Try run to detect Talos screwups etc.:
> https://tbpl.mozilla.org/?tree=Try&rev=acd3a8fa88c7

Can you summarize and detail what specifics have changed and what we should be looking out for here?
(In reply to Aaron Train [:aaronmt] from comment #63)
> Can you summarize and detail what specifics have changed and what we should
> be looking out for here?

Of course! Don't you fancy reading through 60 comments to work out the specifics for yourself? :P

The patches applied rather radically change the way favicons are loaded and stored. A small number of favicons will appear less pixelated or at a better size with this patch, but mostly it's a behind-the-scenes architectural change that tidies things up, fixes an assortment of minor favicon bugs, and prepares things for the more visible improvements - like the ICO decoder.
Unfortunately, the extend of the changes make it quite likely I've broken something (Or numerous somethings) - so if you run into vanishing favicons or other strange favicon behaviour then it's probably my fault.
Bug 753356, Bug 782823, Bug 813810 should also no longer be reproducible.


(In reply to Lucas Rocha (:lucasr) from comment #62)
You raise some interesting points - I'll address them in a few hours, after more sleep.

A general,vaguely related comment - your earlier patch implemented a thread pool for loading favicons so we can get better concurrency here. This is a good idea, but I think it's far too specialised. We should have a thread pool of background tasks - tasks we currently run on "the background thread" should instead be given to a thread pool and run as much in parallel as possible.
The use of multiple different thread pools in one program needs to be considered extremely carefully - it's almost never a good idea. For this reason I'm reluctant to implement a single-purpose thread pool for favicon loading tasks, as this is liable to start a trend for doing similar things elsewhere in the code, which could have a catastrpohic effect on performance on multi-cored devices. I'm holding out for the general solution (The change needed to shunt this lot over to using such a global thread pool should be fairly straightforward.)

This seemed to be something you're interested in - fancy a project?
(In reply to Chris Kitching [:ckitching] from comment #64)

> A general,vaguely related comment - your earlier patch implemented a thread
> pool for loading favicons so we can get better concurrency here. This is a
> good idea, but I think it's far too specialised. We should have a thread
> pool of background tasks - tasks we currently run on "the background thread"
> should instead be given to a thread pool and run as much in parallel as
> possible.

Big chunks of Fennec rely on sequential operation within specific threads -- e.g., queuing tasks on the background thread. Total parallelism isn't a good goal here.
Blocks: 919645
(In reply to Richard Newman [:rnewman] from comment #65)
> (In reply to Chris Kitching [:ckitching] from comment #64)
> 
> > A general,vaguely related comment - your earlier patch implemented a thread
> > pool for loading favicons so we can get better concurrency here. This is a
> > good idea, but I think it's far too specialised. We should have a thread
> > pool of background tasks - tasks we currently run on "the background thread"
> > should instead be given to a thread pool and run as much in parallel as
> > possible.
> 
> Big chunks of Fennec rely on sequential operation within specific threads --
> e.g., queuing tasks on the background thread. Total parallelism isn't a good
> goal here.

Agree. This is why I wrote a very specialized solution for the listviews in about:home (as opposed to changing the way we handle background threads in general).
(In reply to Lucas Rocha (:lucasr) from comment #66)
> Agree. This is why I wrote a very specialized solution for the listviews in
> about:home (as opposed to changing the way we handle background threads in
> general).

Ugh. This seems like a problem that'll want solving one day. But not today. I've recursively shaved too many yaks doing this.
Just to be clear: except for the "total parallelism" aspect of my comment #62, the issues I pointed out need to be either addressed as part of this bug or as follow-ups. They are not just nice-to-have improvements or something.
(In reply to Lucas Rocha (:lucasr) from comment #62)
> Comment on attachment 810327 [details] [diff] [review]
> V26 - Rebasing - Add more intelligent caching to the Favicons system.
> 
> Review of attachment 810327 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Drive-by review: just had a quick look at the UI bits.
> 
> ::: mobile/android/base/GeckoApp.java
> @@ +1192,1 @@
> >          Favicons.attachToContext(this);
> 
> nit: fix indentation here.
> 
> ::: mobile/android/base/Tabs.java
> @@ +269,5 @@
> >      public boolean isSelectedTab(Tab tab) {
> >          return tab != null && tab == mSelectedTab;
> >      }
> >  
> > +    public boolean isSelectedTabById(int tabId) {
> 
> nit: I'd just go with isSelectedTabId() instead.
> 
> Is this method thread-safe?

Yes.
Assignment to fields in java is not atomic, however the magic of `volatile` comes to our rescue.

> ::: mobile/android/base/home/BookmarksPage.java
> @@ -578,5 @@
> > -                        // but will at least prevent this from being too large.
> > -                        thumbnails.put(url, new Thumbnail(Favicons.scaleImage(bitmap), false));
> > -                    }
> > -                }
> > -            }
> 
> This new behaviour is not exactly what we want. Top sites
> thumbnails/favicons are meant to be loaded in one go. This is why both
> thumbnails and favicons are loaded here. With this patch, the thumbnails
> will load first then an async operation will be triggered to load each
> favicon later. This means the user will likely see the images show up at
> different times, which might feel a bit clunky for such a core part of the
> UI (especially on low-end devices).

The yaks. You monster.

Briefly tactfully ignoring the actual request you made here, I investigated "Why is loading favicons from the database so disturbingly slow?". It's clunky to scroll through a list of things in the History tab - madness!

Investigation found this:
http://mxr.mozilla.org/mozilla-central/source/mobile/android/base/db/LocalBrowserDB.java#715

We do,
SELECT favicon FROM combined_with_favicons WHERE url = ?

But - url is a favicon URL. Where's the favicon urls -> favicons relation? The favicons table. So why is the query hitting combined_with_favicons? (And why is it doing so in such an obtuse way - http://mxr.mozilla.org/mozilla-central/source/mobile/android/base/db/BrowserProvider.java#2652 )

Further investigation reveals the definition of this view. Approximately, it looks approximately like this:

let `combined` be given by:

    CREATE VIEW IF NOT EXISTS combined AS                                                                      
    SELECT bookmark_id, history_id, 0 AS _id, url, title, visits, display, DATE, favicon_id                    
    FROM (                                                                                                      
         SELECT bookmarks._id AS bookmark_id,                                                                  
                bookmarks.url AS url,                                                                          
                bookmarks.title AS title,                                                                      
                CASE                                                                                            
                     boookmarks.parent WHEN                                                                    
                         -2 THEN 1 ELSE                                                                        
                         0 END AS display,                                                                      
                -1 AS history_id,                                                                              
                -1 AS visits,                                                                                  
                -1 AS DATE,                                                                                    
                bookmarks.favicon_id AS favicon_id                                                              
         FROM                                                                                                  
                bookmarks                                                                                      
         WHERE                                                                                                  
                bookmarks.TYPE = 1 AND                                                                          
                bookmarks.parent <> -3 AND                                                                      
                bookmarks.deleted = 0 AND                                                                      
                bookmarks.url NOT IN (SELECT url FROM history)                                                  
         UNION ALL                                                                                              
         SELECT                                                                                                
                CASE bookmarks.deleted                                                                          
                     WHEN 0 THEN                                                                                
                         CASE bookmarks.parent                                                                  
                             WHEN -3 THEN NULL ELSE                                                            
                             bookmarks._id END                                                                  
                     ELSE NULL                                                                                  
                END                                                                                            
                AS bookmark_id,                                                                                
                history.url AS url,                                                                            
                COALESCE(bookmarks.title, history.title) AS title,                                              
                CASE bookmarks.deleted                                                                          
                     WHEN 0 THEN                                                                                
                         CASE bookmarks.parent                                                                  
                             WHEN -2 THEN 1 ELSE                                                                
                             0 END                                                                              
                     ELSE 0 END                                                                                
                AS display,                                                                                    
                history._id AS history_id,                                                                      
                history.visits AS visits,                                                                      
                history.DATE AS DATE,                                                                          
                history.favicon_id AS favicon_id                                                                
         FROM                                                                                                  
                history LEFT OUTER JOIN bookmarks                                                              
                ON bookmarks.url = history.url                                                                  
                WHERE history.url IS NOT NULL AND                                                              
                history.deleted = 0 AND                                                                        
                (bookmarks.TYPE IS NULL OR bookmarks.TYPE = 1)                                                  
         )


Then `combined_with_favicons` is given by:
	

    CREATE VIEW IF NOT EXISTS combined_with_favicons AS                        
    SELECT combined.*,                                                          
           favicons.url AS favicon_url,                                        
           favicons.DATA AS favicon,                                            
    FROM combined LEFT OUTER JOIN favicons ON                                  
        favicon_id = favicons._id


*blink*


Views are expanded as subqueries by the storage engine in use. The query required is `SELECT data FROM favicons WHERE url = ?`. The query used is, as you can see, rather more complex.
Worse - the query used is doing a left outer join across combined - it'll load the entire resultset! You're loading the entire history database every time you need one favicon! Defenestration-inducingly wasteful.

Switching over to the simpler query approach and making some associated subtle changes to make everything not cease to function has resulted in a palpable performance improvement when scrolling the lists before things hit the memcache.
Also, the favicon ID fields in the history database vs. the bookmarks database are denormalised.

So. Loading favicons from the db is now many times faster.

Having mitigated much of your concern - how do you suggest going about rigorously solving it without duplication of logic? I'd be inclined to not fix this problem - it's not significant - or is there a neat way of doing it you had in mind?

> ::: mobile/android/base/home/TopBookmarkItemView.java
> @@ +178,5 @@
> >              displayThumbnail(R.drawable.favicon);
> >              return;
> >          }
> >  
> > +        if (faviconURL != null) {
> 
> Why would you want to keep the old value of mFaviconURL when faviconURL is
> null?

A largeish number of apparently spurious calls to this method and friends are made on startup. Since these views are not recycled, once we've been set with a sane value we want to cling to it (With thumbnails being preferred over favicons).

Support for cancelation of ongoing favicon load tasks has been added in appropriate places.

For added fun, the file this change is in has been moved and radically changed since the patch you looked at was generated.

> ::: mobile/android/base/home/TopBookmarksAdapter.java
> @@ +85,5 @@
> >              } else {
> > +                // If we have no thumbnail, attempt to show a Favicon instead.
> > +                Favicons.getSizedFaviconForPageFromLocal(url, new OnFaviconLoadedListener() {
> > +                    @Override
> > +                    public void onFaviconLoaded(String url, String faviconURL, Bitmap favicon) {
> 
> This will likely break with view recycling given that
> getSizedFaviconForPageFromLocal() runs asynchronously. The target view might
> have been bound to another URL before the favicon finishes loading. You have
> to check if the view is still bound to the same URL before calling
> displayFavicon().

The new implementation uses cancelable LoadFaviconTask jobs for this. Recycling logic and allowing jobs to be canceled and partial results discarded when we no longer care about them. I believe this new approach elminates such problems?

> @@ +86,5 @@
> > +                // If we have no thumbnail, attempt to show a Favicon instead.
> > +                Favicons.getSizedFaviconForPageFromLocal(url, new OnFaviconLoadedListener() {
> > +                    @Override
> > +                    public void onFaviconLoaded(String url, String faviconURL, Bitmap favicon) {
> > +                        view.displayFavicon(favicon, faviconURL);
> 
> The view might get detached/destroyed before the listener is called. It's
> probably worth checking if it's safe to call displayFavicon in this
> scenario. Using Loaders kinda of protected us against this.

How would one do such a check? How do Loaders protect against this?

> @@ +207,5 @@
> >  
> > +        if (mShowIcons) {
> > +            // Blank the Favicon, so we don't show the wrong Favicon if we scroll and miss DB.
> > +            mFavicon.clearImage();
> > +            Favicons.getSizedFaviconForPageFromLocal(url, mFaviconListener);
> 
> Given that you're not canceling obsolete requests on recycled views anymore,
> isn't that prone to flood the background thread with useless tasks as you
> scroll? This might cause a regression on perceived performance because
> LoadFaviconTask is an UiAsyncTask, which runs tasks serially i.e. we'd be
> constantly waiting for obsolete tasks to finish before loading the actually
> visible favicons in the list.

Obsolete requests are now canceled. Sorry - didn't see the route to generalisation when I first wrote this.


Flagging for more reviewer attention due to the largeish changes brough about by the fact that many of the classes being altered vanished and some nifty new database things were added.
Attachment #810327 - Attachment is obsolete: true
Attachment #811088 - Flags: review?(rnewman)
(In reply to Chris Kitching [:ckitching] from comment #60)
> As requested, a build with this patch:
> https://www.dropbox.com/s/je7t1nfpkg1o11v/fennec-27.0a1.en-US.android-arm.apk
> 
> Go forth and break! (Or, ideally, fail to break so we can get on with
> landing the genuinely interesting Bug 748100 and Bug 914027.)
> 
> Try run to detect Talos screwups etc.:
> https://tbpl.mozilla.org/?tree=Try&rev=acd3a8fa88c7

Thanks for the .apk, I just tried running this, and I noticed it hasn't been updated to include the new-new-about-home changes, so I'd like to test out an updated build before we go ahead and landed.

However, just using it for a few minutes, I noticed that the Google favicon didn't update in the urlbar when I did a google search, and the icon was also missing from that page's history entry. Known issue?
Flags: needinfo?(margaret.leibovic)
(In reply to :Margaret Leibovic from comment #70)
> (In reply to Chris Kitching [:ckitching] from comment #60)
> > As requested, a build with this patch:
> > https://www.dropbox.com/s/je7t1nfpkg1o11v/fennec-27.0a1.en-US.android-arm.apk
> > 
> > Go forth and break! (Or, ideally, fail to break so we can get on with
> > landing the genuinely interesting Bug 748100 and Bug 914027.)
> > 
> > Try run to detect Talos screwups etc.:
> > https://tbpl.mozilla.org/?tree=Try&rev=acd3a8fa88c7
> 
> Thanks for the .apk, I just tried running this, and I noticed it hasn't been
> updated to include the new-new-about-home changes, so I'd like to test out
> an updated build before we go ahead and landed.

Of course. Here's a build of the latest version:
https://www.dropbox.com/s/je7t1nfpkg1o11v/fennec-27.0a1.en-US.android-arm.apk

I also sat down and took some measurements of the performance improvement no longer using the combined view to query favicons gives us. It's about 35% faster[1] - Yay!

[1]https://www.dropbox.com/sh/xthu03btk8llrgr/jo93KF7vwp

> However, just using it for a few minutes, I noticed that the Google favicon
> didn't update in the urlbar when I did a google search, and the icon was
> also missing from that page's history entry. Known issue?

This is unexpected. By "Not updating" you mean that it just shows the default favicon? Does this happen for all Google searches? (Can you still make it do this with the new apk?)


New patch version - added more graceful handling of sites serving up invalid or nonexistent favicons. (Thanks, Staples!)
Attachment #811088 - Attachment is obsolete: true
Attachment #811088 - Flags: review?(rnewman)
Attachment #811464 - Flags: review?(rnewman)
Flags: needinfo?(margaret.leibovic)
Depends on: 922116
Comment on attachment 811464 [details] [diff] [review]
V28 -  Add more intelligent caching to the Favicons system.

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

If I'm not mistaken, LoadFaviconTask should override .cancel() in order to remove itself from loadsInFlight etc.

::: mobile/android/base/favicons/LoadFaviconTask.java
@@ +303,5 @@
> +    protected void onPostExecute(Bitmap image) {
> +        // Firstly, prevent others from joining the queue for this result.
> +        synchronized(loadsInFlight) {
> +            loadsInFlight.remove(mFaviconUrl);
> +        }

You can fall in a crack here.

We check for the cached value, and it's not present. Then we check to see if there's a load in flight (line 253), but it's just finished.

Can we do better by keeping this task around "in flight" until it's done storing the icon in the cache? If we do that:

* We store sooner, so we narrow the window in which someone will miss the cache.
* We hang around longer, so there's a better chance of a new fetch chaining onto us, which is the best outcome (bitmap in memory).

@@ +317,1 @@
>          Favicons.removeLoadTask(mId);

Do this earlier in onPostExecute. We don't want a failure to cache to result in a failure to clean up.

@@ +348,5 @@
> +     * (Don't want to download a hundred instances of Google's Favicon at once, for example).
> +     * @param aChainee LoadFaviconTask
> +     */
> +    private void chainResults(LoadFaviconTask aChainee) {
> +        mChainee = aChainee;

Question: why not

  if (mChainee != null) {
    mChainee.chainResults(aChainee);
    return;
  }
  mChainee = aChainee;
Attachment #811464 - Flags: review?(rnewman)
I've tested this patch against current fx-team, and it seems to work fine -- no noticeable speed regression versus the current implementation, no disappearing favicons (which I see in current Nightly), and apparently correct display in cases that just shows blank right now.

Scaling large icons works, as best I can tell, as does background color computation.

Looking at the log, it seems that the awesomescreen does a lot of spamming:

09-30 13:20:58.157 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.157 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.157 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.167 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.167 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.167 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.167 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.267 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.407 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:58.427 D/FaviconCache(14649): Favicon cache fullness: 265792/1048576
09-30 13:20:58.437 D/FaviconCache(14649): Favicon cache fullness: 265792/1048576
09-30 13:20:58.497 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:59.078 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:59.078 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:59.078 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:59.088 D/GeckoFavicons(14649): Requesting cancelation of favicon load (36)
09-30 13:20:59.088 D/GeckoFavicons(14649): Cancelling favicon load (36)
09-30 13:20:59.088 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:59.088 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:20:59.088 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:08.988 I/GeckoToolbar(14649): zerdatime 443566590 - Throbber stop
09-30 13:21:08.998 W/TwoWayView(14649): Constructing LayoutParams with width FILL_PARENT does not make much sense as the view might change orientation. Falling back to WRAP_CONTENT
09-30 13:21:10.790 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:11.291 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:20.200 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:21.552 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:21.592 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:21.632 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:21.682 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:21.692 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:21.732 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)
09-30 13:21:26.968 D/GeckoFavicons(14649): Requesting cancelation of favicon load (0)


We should look at this. I would guess that it implies one of these:

* There are favicon tasks that aren't being removed from the list
* A tab's favicon load ID isn't being set to NOT_LOADING
* We shouldn't be logging so much in cancelFaviconLoad.


I'm going to file a follow-up bug for UI polish: because we asynchronously load favicons, we're pretty much guaranteed to briefly show the grey globe icon in the URL bar before, some milliseconds later, drawing the site's favicon. That looks janky, but it's not a regression against current Nightly. I imagine we know in advance whether we'll be drawing a favicon; in that case we can skip the intermediate step.
Browsed for a while. Opened home screen and *immediately* hit a top site.

https://rnewman.pastebin.mozilla.org/3173340

Not only the homepage strict mode violation (Bug 922321), but whammo, OOM and a bunch of failing tasks.

Let's do it again:

https://rnewman.pastebin.mozilla.org/3173341

Ouch. This is on an HTC One, btw.

Either our thumbnail stuff is extraordinarily memory intensive, or this patch is hammering our memory usage.
09-30 13:37:03.087 D/FaviconCache(14649): Favicon cache fullness: 535680/1048576

So half a meg of cache data before I start OOMing.
Thumbnail issue (unrelated to this bug): Bug 919768. I still want us to tune that cache size down.
(In reply to Richard Newman [:rnewman] from comment #72)
> Comment on attachment 811464 [details] [diff] [review]
> V28 -  Add more intelligent caching to the Favicons system.
> 
> Review of attachment 811464 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> If I'm not mistaken, LoadFaviconTask should override .cancel() in order to
> remove itself from loadsInFlight etc.

You'd think that - but cancel() is final.
A refresher - after cancel() is called, we will run onCancelled after we return from doInBackround (Instead of onPostExecute as we'd normally do).
So, we do this removal in onCanceled - but in principle a task could chain on this task even after it's been canceled - we probably don't want this. Adding a check to prevent it.
While adding that check, I discovered that tasks that chain don't abort their task and wait for the other one to provide the result. WHOOPS.

Chaining now actually prevents duplication of work, as intended. Instead of just making duplication of work slightly more overheadful...

> ::: mobile/android/base/favicons/LoadFaviconTask.java
> @@ +303,5 @@
> > +    protected void onPostExecute(Bitmap image) {
> > +        // Firstly, prevent others from joining the queue for this result.
> > +        synchronized(loadsInFlight) {
> > +            loadsInFlight.remove(mFaviconUrl);
> > +        }
> 
> You can fall in a crack here.
> 
> We check for the cached value, and it's not present. Then we check to see if
> there's a load in flight (line 253), but it's just finished.
> 
> Can we do better by keeping this task around "in flight" until it's done
> storing the icon in the cache? If we do that:
> 
> * We store sooner, so we narrow the window in which someone will miss the
> cache.
> * We hang around longer, so there's a better chance of a new fetch chaining
> onto us, which is the best outcome (bitmap in memory).

Good plan.

> @@ +348,5 @@
> > +     * (Don't want to download a hundred instances of Google's Favicon at once, for example).
> > +     * @param aChainee LoadFaviconTask
> > +     */
> > +    private void chainResults(LoadFaviconTask aChainee) {
> > +        mChainee = aChainee;
> 
> Question: why not
> 
>   if (mChainee != null) {
>     mChainee.chainResults(aChainee);
>     return;
>   }
>   mChainee = aChainee;

There I go assuming code is always used exactly as I'm currently using it, again.

How I wish I could use wait-notify and make all this awfulness go away...

(In reply to Richard Newman [:rnewman] from comment #73)
> We should look at this. I would guess that it implies one of these:
> 
> * There are favicon tasks that aren't being removed from the list
> * A tab's favicon load ID isn't being set to NOT_LOADING
> * We shouldn't be logging so much in cancelFaviconLoad.

This actually implies that I'm an idiot.
NOT_LOADING == 0 - so most of those lines are it reporting that it did nothing - not hugely interesting. I think I added that for debugging and never removed it.

> I'm going to file a follow-up bug for UI polish: because we asynchronously
> load favicons, we're pretty much guaranteed to briefly show the grey globe
> icon in the URL bar before, some milliseconds later, drawing the site's
> favicon. That looks janky, but it's not a regression against current
> Nightly. I imagine we know in advance whether we'll be drawing a favicon; in
> that case we can skip the intermediate step.

Aye. Feel free to assign me this - given my recent work in the area I can probably solve it faster than others.


(In reply to Richard Newman [:rnewman] from comment #74)
> Browsed for a while. Opened home screen and *immediately* hit a top site.
> 
> <Various explosions>

To check - all of the madness as of this comment is explained by Bug 919768 and not something that needs investigating here?


(In reply to Richard Newman [:rnewman] from comment #76)
> I still want us to tune that cache size down.

The cache size is the same as it was previously, only now, since it doesn't duplicate images, it's way more efficient.
That is, any reduction in size we make to the cache is effectively a reduction in our app memory footprint. How much would you like it reduced by? Cut it down to half a meg?
Attachment #811464 - Attachment is obsolete: true
Attachment #812863 - Flags: review?(rnewman)
Comment on attachment 812863 [details] [diff] [review]
V29 - Add more intelligent caching to the Favicons system.

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

::: mobile/android/base/favicons/Favicons.java
@@ +60,5 @@
> +    public static String getFaviconURLForPageURLFromCache(String pageURL) {
> +        return sPageURLMappings.get(pageURL);
> +    }
> +
> +    public static void putFaviconURLForPageURLFromCache(String pageURL, String faviconURL) {

put*IntoCache?

::: mobile/android/base/favicons/LoadFaviconTask.java
@@ +315,5 @@
> +            Favicons.putFaviconInMemCache(mFaviconUrl, image);
> +        }
> +
> +        synchronized(loadsInFlight) {
> +            loadsInFlight.remove(mFaviconUrl);

This doesn't seem right.

Every tasks' onPostExecute will remove itself from loadsInFlight.

Only the end of the chain is in there, but they all share a URL.

You only want to remove *when mChainee == null*, so that the chain persists until its last element has finished executing.

@@ +337,5 @@
> +
> +        // And if applicable, notify any other jobs that were aggregated with this one to also
> +        // notify their listeners.
> +        if (mChainee != null) {
> +            mChainee.processResult(image);

mChainee is still present in sLoadTasks, so clear the reference here to allow for simpler GC.

@@ +346,5 @@
>      protected void onCancelled() {
>          Favicons.removeLoadTask(mId);
>  
> +        synchronized(loadsInFlight) {
> +            loadsInFlight.remove(mFaviconUrl);

Same point as above for detecting the end of the chain.
Attachment #812863 - Flags: review?(rnewman)
(In reply to Chris Kitching [:ckitching] from comment #77)

> Aye. Feel free to assign me this - given my recent work in the area I can
> probably solve it faster than others.

Bug 923218.

> To check - all of the madness as of this comment is explained by Bug 919768
> and not something that needs investigating here?

Correct.

> That is, any reduction in size we make to the cache is effectively a
> reduction in our app memory footprint. How much would you like it reduced
> by? Cut it down to half a meg?

Yup. In the absence of telemetry, I'm going to go on gut feel and observation of OOMs in the log!
Blocks: 923218
(In reply to Richard Newman [:rnewman] from comment #78)
> ::: mobile/android/base/favicons/LoadFaviconTask.java
> @@ +315,5 @@
> > +            Favicons.putFaviconInMemCache(mFaviconUrl, image);
> > +        }
> > +
> > +        synchronized(loadsInFlight) {
> > +            loadsInFlight.remove(mFaviconUrl);
> 
> This doesn't seem right.
> 
> Every tasks' onPostExecute will remove itself from loadsInFlight.
> 
> Only the end of the chain is in there, but they all share a URL.
> 
> You only want to remove *when mChainee == null*, so that the chain persists
> until its last element has finished executing.

Aye, something is wonky here.
Hmm.

When a task launches and finds that another is in progress that it needs to chain on, it sets the mIsChaining flag and returns. It will now (Immediatelyish) enter onPostExecute, where it should (But doesn't currently) just do nothing.
This is annoying - a much preferable approach would be to, instead of returning, use the wait-notify mechanism to put the tasks to sleep when they want to chain and use notifyAll when a result is available, allowing all tasks waiting on a particular result to just return normally with the same result. But - that'd mandate one thread per task, which is not our threading model at the moment. We don't want to suspend the background thread waiting on the background thread- that would end badly.

So, at any moment, the one task in a chain that hasn't yet gone through onPostExecute is the first one - the one doing the "real work", as well as some number of concurrent tasks that haven't noticed yet. (Going to assume we eventually run these differently to in series on the background thread - not least because it looks like Lucas is lurking with a patch to use thread pooling here).

Actually, if he's doing what I think he's doing we might later be able to migrate this over to a nicer wait-notify system. More concurrency, less insanity. Still. One overhaul at a time.

We can't just remove if mChainee is null in onPostExecute, since that happens for all chained tasks the moment they join the queue. Instead, this needs to happen in processResult - the method which is called on each queued task in turn when the result is available.
I think this revised patch solves the problem. Updates to mChainee always happen within the loadsInFlight monitor, so holding this lock is sufficient to ensure nobody extends the chain. processResult now checks if there's a chained element to use and, if not, takes out the lock in preparation to remove the reference from the hashmap. Since we now hold the lock, we can make an authorative check of mChainee to see if it was updated in the meantime and, if necessary, continue the chaining.
Almost always, this extra check will be false and we'll just remove the element from the hashmap and continue. We've acheived thread safety of mChainee without needing to lock it everywhere.
Probably.
See what you think.

> @@ +346,5 @@
> >      protected void onCancelled() {
> >          Favicons.removeLoadTask(mId);
> >  
> > +        synchronized(loadsInFlight) {
> > +            loadsInFlight.remove(mFaviconUrl);
> 
> Same point as above for detecting the end of the chain.

The check on mChainee is added inside the monitor for reasons outlined above - this has the useful property of preventing concurrent update without additional locking.

Hopefully we'll run out of problems before we run out of integers.
Attachment #812863 - Attachment is obsolete: true
Attachment #813567 - Flags: review?(rnewman)
Attachment #813567 - Attachment is obsolete: true
Attachment #813567 - Flags: review?(rnewman)
Comment on attachment 813595 [details] [diff] [review]
V31 - Add more intelligent caching to the Favicons system.

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

Almost there!

::: mobile/android/base/BrowserApp.java
@@ +1339,5 @@
> +                    public void onFaviconLoaded(String pageUrl, String faviconURL, Bitmap favicon) {
> +                        // Leave favicon UI untouched if we failed to load the image
> +                        // for some reason.
> +                        if (favicon == null)
> +                            return;

If Bug 923218 isn't a patch that's expected to apply on top of this, remember to take that change into account.

@@ +1344,5 @@
>  
> +                        // The tab might be pointing to another URL by the time the
> +                        // favicon is finally loaded, in which case we simply ignore it.
> +                        if (!tab.getURL().equals(pageUrl))
> +                            return;

Leave a comment pointing to Bug 920331.

::: mobile/android/base/db/BrowserProvider.java
@@ +3016,5 @@
>          }
>  
> +        // If no URL is provided, insert using the default one.
> +        if (TextUtils.isEmpty(faviconUrl) && !TextUtils.isEmpty(pageUrl)) {
> +            values.put(Favicons.URL, org.mozilla.gecko.favicons.Favicons.guessDefaultFaviconURL(pageUrl));

Sidenote: this is yet another reason why I don't like singletons.

In order for BrowserProvider to call a simple static method on Favicons, it needs to do the whole class init... which includes allocating a Map and an LruCache, which it will never use. *sigh*

::: mobile/android/base/db/LocalBrowserDB.java
@@ +692,5 @@
>  
>          cr.update(mBookmarksUriWithProfile,
> +                values,
> +                Bookmarks._ID + " = ?",
> +                new String[]{String.valueOf(id)});

Fix this indenting to match what it was before. In fact, don't change these lines at all!

@@ +712,5 @@
> +            c = cr.query(mFaviconsUriWithProfile,
> +                    new String[] { Favicons.DATA },
> +                    Favicons.URL + " = ?",
> +                    new String[] { faviconURL },
> +                    null);

Fix alignment to be column-aligned.

@@ -764,5 @@
> -
> -            if (i > 0)
> -                selection.append(", ");
> -
> -            DatabaseUtils.appendEscapedSQLString(selection, url);

Glad you're killing this!

::: mobile/android/base/favicons/Favicons.java
@@ +352,5 @@
>          }
>  
> +        try {
> +            URL pageUri = new URL(pageURL);
> +            return new URL(pageUri.getProtocol(), pageUri.getAuthority(), "/favicon.ico").toString();

URI, not URL.

::: mobile/android/base/favicons/LoadFaviconTask.java
@@ +113,5 @@
> +        return tryDownloadRecurse(faviconURI, visitedLinkSet);
> +    }
> +
> +    private HttpResponse tryDownloadRecurse(URI faviconURI, HashSet<String>visited) throws URISyntaxException, IOException {
> +        if (visited.size() == MAX_REDIRECTS_TO_FOLLOW) {

This will *still* not catch redirect loops. Consider:

  x.ico -> y.ico -> x.ico -> ...

Like it or not, you need a counter (assuming we're not going to start modifying URLs).

@@ +128,5 @@
> +            // Was the response a failure?
> +            int status = response.getStatusLine().getStatusCode();
> +
> +            // Handle HTTP status codes requesting a redirect.
> +            if (status >= 300 && status < 400) {

It occurs to me that there's a hole in the handling here (not a regression), which I'd like a follow-up for. Bug number in the comment as always.

Here it is.

If we end up successfully fetching a favicon, and it's not an immediate 200, we'll be some steps removed Location-wise from where we started.

We should be recording the *fetched* favicon URL, and any 301 responses, in the DB and cache. We'll get better cache behavior as a result.

The Location header indicates the real location of the favicon, and so in fact we should look in our cache for each new location, and do the right thing with loadsInFlight -- recursing!

Any 302/303 responses are temporary, and so can be cached in a different way to essentially skip the redirect chain.

I imagine that favicon redirects are uncommon, and so this isn't super urgent, but what we do now is strictly wrong, so let's file a bug.

@@ +253,5 @@
> +        // If there is, just join the queue and wait for it to finish. If not, we carry on.
> +        synchronized(loadsInFlight) {
> +            if (loadsInFlight.containsKey(mFaviconUrl)) {
> +                // Another load of the current Favicon is already underway
> +                LoadFaviconTask existingTask = loadsInFlight.get(mFaviconUrl);

Could just use get and a null check rather than contains + get.

@@ +322,5 @@
> +        // Process the result - scale for the listener, chain if required.
> +        processResult(image);
> +    }
> +
> +    private void processResult(Bitmap image) {

Consider this alternative phrasing:

  private void processResult(Bitmap image, boolean isAlreadyScaled) {
    Bitmap scaled = image;
    if (!isAlreadyScaled) {
      if (mTargetWidth != -1 &&
          image != null &&
          image.getWidth() != mTargetWidth) {
        scaled = Favicons.getSizedFaviconFromCache(...);
      }
    }

    Favicons.dispatchResult(mPageUrl, mFaviconUrl, scaled, mListener);

    // Take a snapshot of the chainee reference.
    final LoadFaviconTask chainee = mChainee.get();

    if (chainee != null) {
      // Propagate the result along the chain.
      mChainee.set(null);
      chainee.processResult(scaled, true);
      return;
    }

    // If we find we had no chainee set, enter the monitor (Which is required to update the
    // mChainee reference) and check again. If we're still lacking a chainee, remove the
    // reference from loadsInFlight.
    synchronized(loadsInFlight) {
      if (mChainee.get() == null) {
        loadsInFlight.remove(mFaviconUrl);
        return;
      }
    }

    // Another element was added to the chain while we weren't looking...
    mChainee.get().processResult(scaled, true);
  }

Avoid the size checks and getSizedFaviconFromCache calls, uses early return.

@@ +375,5 @@
> +     * (Don't want to download a hundred instances of Google's Favicon at once, for example).
> +     *
> +     * @param aChainee LoadFaviconTask
> +     */
> +    private void chainResults(LoadFaviconTask aChainee) {

This should be called chainTasks.

@@ +382,5 @@
> +            return;
> +        }
> +
> +        // If not-null, it will not have changed since we last set it (In the above code in a prior
> +        // call). As such, it's safe to do the following.

I think what you mean by this is "chainResults is only called within a synchronized block on `loadsInFlight`".
Attachment #813595 - Flags: review?(rnewman) → feedback+
Blocks: 925878
The version number is now a power of two. That's gotta be a good sign.

(In reply to Richard Newman [:rnewman] from comment #82)
> ::: mobile/android/base/BrowserApp.java
> @@ +1339,5 @@
> > +                    public void onFaviconLoaded(String pageUrl, String faviconURL, Bitmap favicon) {
> > +                        // Leave favicon UI untouched if we failed to load the image
> > +                        // for some reason.
> > +                        if (favicon == null)
> > +                            return;
> 
> If Bug 923218 isn't a patch that's expected to apply on top of this,
> remember to take that change into account.

Bug 923218 can be independent of this one. Rebasing this one on top.

That said, the patch in that other bug no longer applies, so I've issued a new version over there. It's got a lot simpler now. Yay!

> ::: mobile/android/base/db/BrowserProvider.java
> @@ +3016,5 @@
> >          }
> >  
> > +        // If no URL is provided, insert using the default one.
> > +        if (TextUtils.isEmpty(faviconUrl) && !TextUtils.isEmpty(pageUrl)) {
> > +            values.put(Favicons.URL, org.mozilla.gecko.favicons.Favicons.guessDefaultFaviconURL(pageUrl));
> 
> Sidenote: this is yet another reason why I don't like singletons.

Oh, aye. There seem to be a few places in the code where we use singletons when static methods would be more sensible. Favicons was formerly one of these. Singletons seem to be something that get used in far more places than are really necessary. They're actually not useful all that often. 

> In order for BrowserProvider to call a simple static method on Favicons, it
> needs to do the whole class init... which includes allocating a Map and an
> LruCache, which it will never use. *sigh*

Favicons isn't a singleton, which is some mercy at least. (At least, it's less singletonesque than it once was. It's now a class of static methods.)

The allocations you mention are in a static initialiser. According to the JLS (§12.4.1) this will take place, approximately, when the class is first used.
If this call from BrowserProvider is the first ever use of the Favicons class then yes, the initialisers will run then, causing this call to be somewhat slower than it might otherwise be because it's doing allocations that this call doesn't actually need.
However, the claim that these allocations are never used isn't true unless the favicon system is never used for any other purpose than this call. A subsequent call won't run the initialisers again - we're not allocating and deallocating the cache each time we make this call. We're merely doing the one-time-only allocation the first time the class is used, which might be earlier than we actually *need* to. Most uses of the favicon system do make use of these data structures, and they persist for the entire duratoin of the program.
We could factor utility functions out of Favicons into a FaviconUtils class to avoid this, but I decided the improvement didn't justify the extra fragmentation. The favicon system is always needed when using the browser. The only use-case that seems to suffer from this situation is unit tests that touch this part of browser provider (And the cost of a single extra allocation isn't a hugely big deal in any case. I don't have handy figures comparing that cost to the cost of loading an extra class).

Should I do the proposed refactor anyway?

> @@ -764,5 @@
> > -
> > -            if (i > 0)
> > -                selection.append(", ");
> > -
> > -            DatabaseUtils.appendEscapedSQLString(selection, url);
> 
> Glad you're killing this!

There might actually be an argument in the not-too-distant future for bringing this (Or something slightly like it) back. Batch-fetching icons from the database to prefill the in-memory cache might be a more performant way of making scrolling smoother. Still. That's for a followup (And Sriram/Lucas seem set on using Smoothie for this purpose anyway, and I've already had far too much firsthand experience of how annoying race conditions between developers trying to solve the same problem can be :P)

> ::: mobile/android/base/favicons/LoadFaviconTask.java
> @@ +113,5 @@
> > +        return tryDownloadRecurse(faviconURI, visitedLinkSet);
> > +    }
> > +
> > +    private HttpResponse tryDownloadRecurse(URI faviconURI, HashSet<String>visited) throws URISyntaxException, IOException {
> > +        if (visited.size() == MAX_REDIRECTS_TO_FOLLOW) {
> 
> This will *still* not catch redirect loops. Consider:
> 
>   x.ico -> y.ico -> x.ico -> ...
> 
> Like it or not, you need a counter (assuming we're not going to start
> modifying URLs).

Not so.
Immediately before the recursive call, line 147(ish) checks if the URL we're about to redirect to is in the set already. If it is, we abort (Irrespective of how many hops we've made).
If it's not, it's added to the set and we recurse. As a result, the set size always grows by one each time there is a recursive call, so we never exceed MAX_REDIRECTS_TO_FOLLOW recursions before giving up. (And this way if there is a redirect loop shorter than MAX_REDIRECTS_TO_FOLLOW steps we stop sooner and save time.)
In the stupid case of a redirect loop with changing GET parameters, we're saved by the set size growth and abort on the line you tagged.

Hopefully that clarifies things and didn't miss the point..

> @@ +128,5 @@
> > +            // Was the response a failure?
> > +            int status = response.getStatusLine().getStatusCode();
> > +
> > +            // Handle HTTP status codes requesting a redirect.
> > +            if (status >= 300 && status < 400) {
> 
> It occurs to me that there's a hole in the handling here (not a regression),
> which I'd like a follow-up for. Bug number in the comment as always.
> 
> Here it is.
> 
> If we end up successfully fetching a favicon, and it's not an immediate 200,
> we'll be some steps removed Location-wise from where we started.
> 
> We should be recording the *fetched* favicon URL, and any 301 responses, in
> the DB and cache. We'll get better cache behavior as a result.
> 
> The Location header indicates the real location of the favicon, and so in
> fact we should look in our cache for each new location, and do the right
> thing with loadsInFlight -- recursing!
> 
> Any 302/303 responses are temporary, and so can be cached in a different way
> to essentially skip the redirect chain.

This is an interesting edgecase.
Our database schema gets in the way a little here. What would be a neat solution to this would be to allow multiple favicon URLs to map to the same favicon (So every time we're 302/303'd we just add the new URL to the set of URLs that point to the same local favicon.)
That's not difficult to do in the memory cache, but is unrepresentable in the database (Without a dirty hack like "Making favicons.url be a comma-seperated list of urls" or something).

We could have an in-memory only cache of redirection results, but we'd probably want to keep the actual URL given in the <link> tag as the key to the database (So if a website consistently uses a particular URL that happens to redirect as its favicon then we always hit without needing to go through the redirect).

Recursing on the cache as we go is also an interesting thought. It'd only be helpful in some quite bizzaire scenarios, but is still worth doing.

Bug 925878.
 
> I imagine that favicon redirects are uncommon, and so this isn't super
> urgent, but what we do now is strictly wrong, so let's file a bug.

Redirects of this sort seem to not be as uncommon as sanity would suggest. Some sites seem to send mobiles to "m.somesite.com" and then 302 their favicon from "m.somesite.com/favicon.ico" to "somesite.com/favicon.ico"
m.bbc.co.uk does this, and the lack of support for redirects is why there's no favicon there on current nightly.

> @@ +322,5 @@
> > +        // Process the result - scale for the listener, chain if required.
> > +        processResult(image);
> > +    }
> > +
> > +    private void processResult(Bitmap image) {
> 
> Consider this alternative phrasing:
> 
>   private void processResult(Bitmap image, boolean isAlreadyScaled) {
>     Bitmap scaled = image;
>     if (!isAlreadyScaled) {
>       if (mTargetWidth != -1 &&
>           image != null &&
>           image.getWidth() != mTargetWidth) {
>         scaled = Favicons.getSizedFaviconFromCache(...);
>       }
>     }
> 
>     Favicons.dispatchResult(mPageUrl, mFaviconUrl, scaled, mListener);
> 
>     // Take a snapshot of the chainee reference.
>     final LoadFaviconTask chainee = mChainee.get();
> 
>     if (chainee != null) {
>       // Propagate the result along the chain.
>       mChainee.set(null);
>       chainee.processResult(scaled, true);
>       return;
>     }
> 
>     // If we find we had no chainee set, enter the monitor (Which is
> required to update the
>     // mChainee reference) and check again. If we're still lacking a
> chainee, remove the
>     // reference from loadsInFlight.
>     synchronized(loadsInFlight) {
>       if (mChainee.get() == null) {
>         loadsInFlight.remove(mFaviconUrl);
>         return;
>       }
>     }
> 
>     // Another element was added to the chain while we weren't looking...
>     mChainee.get().processResult(scaled, true);
>   }
> 
> Avoid the size checks and getSizedFaviconFromCache calls, uses early return.

Nice cleanup suggestions, I'll pilfer those.

Unfortunately, we can't pass a prescaled bitmap down the chain without causing problems.

Tasks chain if they are fetching the same remote favicon. They don't, however, have to match on target size.
So, each chained task is after the same downloaded bitmap, but each of them might want to downscale it to a different size. Doing the scaling via the getSizedFaviconFromCache call ensures we never compute each resizing more than once, but we can't get away with scaling the bitmap to the size the first task wants and then passing it to all subsequent tasks - they wouldn't get the size they were seeking.

> @@ +382,5 @@
> > +            return;
> > +        }
> > +
> > +        // If not-null, it will not have changed since we last set it (In the above code in a prior
> > +        // call). As such, it's safe to do the following.
> 
> I think what you mean by this is "chainResults is only called within a
> synchronized block on `loadsInFlight`".

... Correct. Me fail english? That's unpossible.

Also of note - someone sneakily changed the semantics of getTabIdForUrl to care about privacy. Wrote an adapter method that I think brings back a close enough approximation to what I want.
Attachment #813595 - Attachment is obsolete: true
Attachment #816071 - Flags: review?(rnewman)
(In reply to Chris Kitching [:ckitching] from comment #83)

Replies, not review comments:


> However, the claim that these allocations are never used isn't true unless
> the favicon system is never used for any other purpose than this call.

Consider that BrowserProvider handles calls from Sync (and system searches, and ...), which indeed don't end up using the other features of Favicons.


> We could factor utility functions out of Favicons into a FaviconUtils class
> to avoid this, but I decided the improvement didn't justify the extra
> fragmentation.

Yes, I agree, which is why I didn't suggest it.

Eventually a lot of this static state (pseudo-singletons) will go away and -- correctly -- be encapsulated by GeckoView.


> There might actually be an argument in the not-too-distant future for
> bringing this (Or something slightly like it) back.

And if we do, we'll rewrite it in better style :)


> Immediately before the recursive call, line 147(ish) checks if the URL we're
> about to redirect to is in the set already. If it is, we abort (Irrespective
> of how many hops we've made).

Ah! Checking before the next call, rather than at the top of the recursive method. You defeat my top-to-bottom reviewing pass.


> That's not difficult to do in the memory cache, but is unrepresentable in
> the database (Without a dirty hack like "Making favicons.url be a
> comma-seperated list of urls" or something).

We will need a favicon schema change at some point. That point probably coincides with not using a relational database to store blobs.


> Redirects of this sort seem to not be as uncommon as sanity would suggest.
> Some sites seem to send mobiles to "m.somesite.com" and then 302 their
> favicon from "m.somesite.com/favicon.ico" to "somesite.com/favicon.ico"
> m.bbc.co.uk does this, and the lack of support for redirects is why there's
> no favicon there on current nightly.

Well, shit. File a follow-up.


> Unfortunately, we can't pass a prescaled bitmap down the chain without
> causing problems.
> 
> Tasks chain if they are fetching the same remote favicon. They don't,
> however, have to match on target size.

Ah, shit. You're right. I suspect we can do better here, but we won't be chaining too much, so never mind.
(In reply to Richard Newman [:rnewman] from comment #84)
> > However, the claim that these allocations are never used isn't true unless
> > the favicon system is never used for any other purpose than this call.
> 
> Consider that BrowserProvider handles calls from Sync (and system searches,
> and ...), which indeed don't end up using the other features of Favicons.

Ah. I now share your sentiments of "Ugh" with more enthusiasm.

> > That's not difficult to do in the memory cache, but is unrepresentable in
> > the database (Without a dirty hack like "Making favicons.url be a
> > comma-seperated list of urls" or something).
> 
> We will need a favicon schema change at some point. That point probably
> coincides with not using a relational database to store blobs.

Aye. Blobs in SQLite is a mildly horrible idea.
In the shorter term, some lesser victory might be had by shifting the blobs into their own table. That way, the table you're doing most querying on isn't fragmented by the big blobs in it.

I have done no measurements to support this statement. It ought to reduce fragmentation, but the extra overheads might make it not worthwhile.

> > Redirects of this sort seem to not be as uncommon as sanity would suggest.
> > Some sites seem to send mobiles to "m.somesite.com" and then 302 their
> > favicon from "m.somesite.com/favicon.ico" to "somesite.com/favicon.ico"
> > m.bbc.co.uk does this, and the lack of support for redirects is why there's
> > no favicon there on current nightly.
> 
> Well, shit. File a follow-up.

No need for a followup on that particular comment - this patch solves that problem. The followup is for the tricky edgecase of redirections you spotted, and that's Bug 925878. 

> Ah, shit. You're right. I suspect we can do better here, but we won't be
> chaining too much, so never mind.

Aye, chaining is sufficiently rare that doing extra work in the non-chaining case isn't worthwhile to make chaining easier, but not chaining isn't wise because network IO is the most expensive thing.
Probably.
Sorry for the abrupt change. Mucked up the rebase. Should be good now.
Attachment #816071 - Attachment is obsolete: true
Attachment #816071 - Flags: review?(rnewman)
Attachment #816118 - Flags: review?(rnewman)
Comment on attachment 816071 [details] [diff] [review]
V32 - Add more intelligent caching to the Favicons system.

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

I think this is good. I'm going to fix nits locally and test as best I can.

::: mobile/android/base/BrowserApp.java
@@ +712,5 @@
> +                Favicons.getFaviconForSize(url, tab.getFaviconURL(), Integer.MAX_VALUE, LoadFaviconTask.FLAG_PERSIST,
> +                        new OnFaviconLoadedListener() {
> +                            @Override
> +                            public void onFaviconLoaded(String pageUrl, String faviconURL, Bitmap favicon) {
> +                                GeckoAppShell.createShortcut(title, url, url, favicon == null ? null : favicon, "");

favicon == null ? null : favicon

…

@@ +1328,5 @@
>      /* Favicon methods */
>      private void loadFavicon(final Tab tab) {
>          maybeCancelFaviconLoad(tab);
>  
> +        final int tabFaviconSize = getResources().getDimensionPixelSize(R.dimen.browser_toolbar_favicon_size);

Tell me that this is cheap and shouldn't be cached.

::: mobile/android/base/favicons/Favicons.java
@@ +31,5 @@
>  public class Favicons {
>      private static final String LOGTAG = "GeckoFavicons";
>  
> +    // Size of the favicon bitmap cache, in bytes (Counting payload only).
> +    public static final int FAVICON_CACHE_SIZE_BYTES = 1024 * 1024;

We were going to drop this to 512.

@@ +348,5 @@
> +            URI u = new URI(pageURL);
> +            return new URI(u.getScheme(),
> +                    u.getAuthority(),
> +                    "/favicon.ico", null,
> +                    null).toString();

Column-align.

::: mobile/android/base/favicons/LoadFaviconTask.java
@@ +336,5 @@
> +        final LoadFaviconTask chainee = mChainee.get();
> +
> +        if (chainee != null) {
> +            // Propagate the result along the chain.
> +            chainee.processResult(image);

// Note that we don't pass the scaled image -- the chainee might not want
// the same size that this task's listener does.
Attachment #816071 - Attachment is obsolete: false
Attachment #816118 - Flags: review?(rnewman) → review+
Attachment #816071 - Attachment is obsolete: true
Applying nit fixes.

(In reply to Richard Newman [:rnewman] from comment #87)
> I think this is good. I'm going to fix nits locally and test as best I can.
> 
> ::: mobile/android/base/BrowserApp.java
> @@ +712,5 @@
> > +                Favicons.getFaviconForSize(url, tab.getFaviconURL(), Integer.MAX_VALUE, LoadFaviconTask.FLAG_PERSIST,
> > +                        new OnFaviconLoadedListener() {
> > +                            @Override
> > +                            public void onFaviconLoaded(String pageUrl, String faviconURL, Bitmap favicon) {
> > +                                GeckoAppShell.createShortcut(title, url, url, favicon == null ? null : favicon, "");
> 
> favicon == null ? null : favicon
> 
> …

Not my code!
Only in my diff because of silly auto-indent.

Also, KILL IT WITH FIRE. (added to patch)

> 
> @@ +1328,5 @@
> >      /* Favicon methods */
> >      private void loadFavicon(final Tab tab) {
> >          maybeCancelFaviconLoad(tab);
> >  
> > +        final int tabFaviconSize = getResources().getDimensionPixelSize(R.dimen.browser_toolbar_favicon_size);
> 
> Tell me that this is cheap and shouldn't be cached.

Unclear. Probably. It's the pattern used for resource usage in the rest of the app.
Attachment #816118 - Attachment is obsolete: true
Attachment #816134 - Flags: review?(rnewman)
(In reply to Chris Kitching [:ckitching] from comment #88)
> Created attachment 816134 [details] [diff] [review]
> V34 - Add more intelligent caching to the Favicons system.
> 
> Applying nit fixes.

> 
> > 
> > @@ +1328,5 @@
> > >      /* Favicon methods */
> > >      private void loadFavicon(final Tab tab) {
> > >          maybeCancelFaviconLoad(tab);
> > >  
> > > +        final int tabFaviconSize = getResources().getDimensionPixelSize(R.dimen.browser_toolbar_favicon_size);
> > 
> > Tell me that this is cheap and shouldn't be cached.
> 
> Unclear. Probably. It's the pattern used for resource usage in the rest of
> the app.

Drive-by: Earlier we used to have different url-bar sizes and favicon sizes in it. So it was necessary to fetch the value depending on when it's updated. Now there is just one favicon size overall. I guess it can be cached. Even otherwise, this is not expensive.
No longer blocks: 923218
Depends on: 923218
Comment on attachment 816134 [details] [diff] [review]
V34 - Add more intelligent caching to the Favicons system.

Let's hope it sticks!

https://hg.mozilla.org/integration/fx-team/rev/c83b4d9555bc
Attachment #816134 - Flags: review?(rnewman) → review+
Whiteboard: [fixed in fx-team][qa+]
Target Milestone: --- → Firefox 27
Depends on: 926129
Blocks: 926139
https://hg.mozilla.org/mozilla-central/rev/c83b4d9555bc
Status: ASSIGNED → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Whiteboard: [fixed in fx-team][qa+] → [qa+]
Flags: needinfo?(margaret.leibovic)
Flags: needinfo?(aaron.train)
Depends on: 926430
Depends on: 926497
Depends on: 926646
Depends on: 927109
No longer depends on: 927109
Depends on: 927186
Depends on: 929010
Depends on: 929025
Blocks: 933992
Depends on: 940049
Depends on: 933420
Component: Theme and Visual Design → Favicon Handling
Hardware: ARM → All
No longer depends on: 926646
Product: Firefox for Android → Firefox for Android Graveyard
You need to log in before you can comment on or make changes to this bug.