The Tor Browser: comparison mobile/android/base/favicons/cache/FaviconCache.java

--1:000000000000
+:80380907da8d
+/* This Source Code Form is subject to the terms of the Mozilla Public
+* License, v. 2.0. If a copy of the MPL was not distributed with this
+* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+package org.mozilla.gecko.favicons.cache;
+import android.graphics.Bitmap;
+import android.util.Log;
+import org.mozilla.gecko.favicons.Favicons;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.Semaphore;
+import java.util.concurrent.atomic.AtomicInteger;
+/**
+* Implements a Least-Recently-Used cache for Favicons, keyed by Favicon URL.
+*
+* When a favicon at a particular URL is decoded, it will yield one or more bitmaps.
+* While in memory, these bitmaps are stored in a list, sorted in ascending order of size, in a
+* FaviconsForURL object.
+* The collection of FaviconsForURL objects currently in the cache is stored in backingMap, keyed
+* by favicon URL.
+*
+* A second map exists for permanent cache entries -- ones that are never expired. These entries
+* are assumed to be disjoint from those in the normal cache, and this map is checked first.
+*
+* 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.).
+*
+* FaviconsForURL is also responsible for storing URL-specific, as opposed to favicon-specific,
+* information. For the purposes of this cache, the simplifying assumption that the dominant colour
+* for all favicons served from a particular favicon URL shall be the same is made. (To violate this
+* would mandate serving an ICO or similar file with multiple radically different images in it - an
+* ill-advised and extremely uncommon use-case, for sure.)
+* The dominant colour information is updated as the element is being added to the cache - typically
+* on the background thread.
+* 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. (Bug 914296)
+*
+* A typical request to the cache will consist of a Favicon URL and a target size. The FaviconsForURL
+* object for that URL will be obtained, queried for a favicon matching exactly the needed size, and
+* if successful, the result is returned.
+* If unsuccessful, the object is asked to return the smallest available primary favicon larger than
+* the target size. If this step works, the result is downscaled to create a new secondary favicon,
+* which is then stored (So subsequent requests will succeed at the first step) and returned.
+* If that step fails, the object finally walks backwards through its sequence of favicons until it
+* finds the largest primary favicon smaller than the target. This is then upscaled by a maximum of
+* 2x towards the target size, and the result cached and returned as above.
+*
+* The bitmaps themselves are encapsulated inside FaviconCacheElement objects. These objects contain,
+* as well as the bitmap, a pointer to the encapsulating FaviconsForURL object (Used by the LRU
+* culler), the size of the encapsulated image, a flag indicating if this is a primary favicon, and
+* a flag indicating if the entry is invalid.
+* All FaviconCacheElement objects are tracked in the ordering LinkedList. This is used to record
+* LRU information about FaviconCacheElements. In particular, the most recently used FaviconCacheElement
+* will be at the start of the list, the least recently used at the end of the list.
+*
+* When the cache runs out of space, it removes FaviconCacheElements starting from the end of the list
+* until a sufficient amount of space has been freed.
+* When a secondary favicon is removed in this way, it is simply deleted from its parent FaviconsForURLs
+* object's list of available favicons.
+* The backpointer field on the FaviconCacheElement is used to remove the element from the encapsulating
+* FaviconsForURL object, when this is required.
+* When a primary favicon is removed, its invalid flag is set to true and its bitmap payload is set
+* to null (So it is available for freeing by the garbage collector). This reduces the memory footprint
+* of the icon to essentially zero, but keeps track of which primary favicons exist for this favicon
+* URL.
+* If a subsequent request comes in for that favicon URL, it is then known that a primary of those
+* dimensions is available, just that it is not in the cache. The system is then able to load the
+* primary back into the cache from the database (Where the entirety of the initially encapsulating
+* container-formatted image file is stored).
+* 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.
+*
+* The implementation is safe to use from multiple threads and, while is it not entirely strongly
+* consistent all of the time, you almost certainly don't care.
+* The thread-safety implementation used is approximately MRSW with semaphores. An extra semaphore
+* is used to grant mutual exclusion over reordering operations from reader threads (Who thus gain
+* a quasi-writer status to do such limited mutation as is necessary).
+*
+* Reads which race with writes are liable to not see the ongoing write. The cache may return a
+* stale or now-removed value to the caller. Returned values are never invalid, even in the face
+* of concurrent reading and culling.
+*/
+public class FaviconCache {
+private static final String LOGTAG = "FaviconCache";
+// 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 final int maxCachedWidth;
+// Retry failed favicons after 20 minutes.
+public static final long FAILURE_RETRY_MILLISECONDS = 1000 * 60 * 20;
+// 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 final ConcurrentHashMap<String, FaviconsForURL> backingMap = new ConcurrentHashMap<String, FaviconsForURL>();
+// And the same, but never evicted.
+private final ConcurrentHashMap<String, FaviconsForURL> permanentBackingMap = new ConcurrentHashMap<String, FaviconsForURL>();
+// 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> ordering = new LinkedList<FaviconCacheElement>();
+// The above structures, if used correctly, enable this cache to exhibit LRU semantics across all
+// 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).
+// Current size, in bytes, of the bitmap data present in the LRU cache.
+private final AtomicInteger currentSize = new AtomicInteger(0);
+// The maximum quantity, in bytes, of bitmap data which may be stored in the cache.
+private final int maxSizeBytes;
+// Tracks the number of ongoing read operations. Enables the first one in to lock writers out and
+// the last one out to let them in.
+private final AtomicInteger ongoingReads = new AtomicInteger(0);
+// Used to ensure transaction fairness - each txn acquires and releases this as the first operation.
+// The effect is an orderly, inexpensive ordering enforced on txns to prevent writer starvation.
+private final Semaphore turnSemaphore = new Semaphore(1);
+// A deviation from the usual MRSW solution - this semaphore is used to guard modification to the
+// ordering map. This allows for read transactions to update the most-recently-used value without
+// needing to take out the write lock.
+private final Semaphore reorderingSemaphore = new Semaphore(1);
+// The semaphore one must acquire in order to perform a write.
+private final Semaphore writeLock = new Semaphore(1);
+/**
+* Called by txns performing only reads as they start. Prevents writer starvation with a turn
+* semaphore and locks writers out if this is the first concurrent reader txn starting up.
+*/
+private void startRead() {
+turnSemaphore.acquireUninterruptibly();
+turnSemaphore.release();
+if (ongoingReads.incrementAndGet() == 1) {
+// First one in. Wait for writers to finish and lock them out.
+writeLock.acquireUninterruptibly();
+}
+}
+/**
+* Called by transactions performing only reads as they finish. Ensures that if this is the last
+* concluding read transaction then then writers are subsequently allowed in.
+*/
+private void finishRead() {
+if (ongoingReads.decrementAndGet() == 0) {
+writeLock.release();
+}
+}
+/**
+* Called by writer transactions upon start. Ensures fairness and then obtains the write lock.
+* Upon return, no other txns will be executing concurrently.
+*/
+private void startWrite() {
+turnSemaphore.acquireUninterruptibly();
+writeLock.acquireUninterruptibly();
+}
+/**
+* Called by a concluding write transaction - unlocks the structure.
+*/
+private void finishWrite() {
+turnSemaphore.release();
+writeLock.release();
+}
+public FaviconCache(int maxSize, int maxWidthToCache) {
+maxSizeBytes = maxSize;
+maxCachedWidth = maxWidthToCache;
+}
+/**
+* Determine if the provided favicon URL is marked as a failure (Has failed to load before -
+* such icons get blacklisted for a time to prevent us endlessly retrying.)
+*
+* @param faviconURL Favicon URL to check if failed in memcache.
+* @return true if this favicon is blacklisted, false otherwise.
+*/
+public boolean isFailedFavicon(String faviconURL) {
+if (faviconURL == null) {
+return true;
+}
+startRead();
+try {
+// If we don't have it in the cache, it certainly isn't a known failure.
+// Non-evictable favicons are never failed, so we don't need to
+// check permanentBackingMap.
+if (!backingMap.containsKey(faviconURL)) {
+return false;
+}
+FaviconsForURL container = backingMap.get(faviconURL);
+// If the has failed flag is not set, it's certainly not a known failure.
+if (!container.hasFailed) {
+return false;
+}
+final long failureTimestamp = container.downloadTimestamp;
+// Calculate elapsed time since the failing download.
+final long failureDiff = System.currentTimeMillis() - failureTimestamp;
+// If the expiry is still in effect, return. Otherwise, continue and unmark the failure.
+if (failureDiff < FAILURE_RETRY_MILLISECONDS) {
+return true;
+}
+} catch (Exception unhandled) {
+Log.e(LOGTAG, "FaviconCache exception!", unhandled);
+return true;
+}  finally {
+finishRead();
+}
+startWrite();
+// If the entry is no longer failed, remove the record of it from the cache.
+try {
+recordRemoved(backingMap.remove(faviconURL));
+return false;
+} finally {
+finishWrite();
+}
+}
+/**
+* Mark the indicated page URL as a failed Favicon until the provided time.
+*
+* @param faviconURL Page URL for which a Favicon load has failed.
+*/
+public void putFailed(String faviconURL) {
+startWrite();
+try {
+FaviconsForURL container = new FaviconsForURL(0, true);
+recordRemoved(backingMap.put(faviconURL, container));
+} finally {
+finishWrite();
+}
+}
+/**
+* Fetch a Favicon for the given URL as close as possible to the size provided.
+* If an icon of the given size is already in the cache, it is returned.
+* If an icon of the given size is not in the cache but a larger unscaled image does exist in
+* the cache, we downscale the larger image to the target size and cache the result.
+* If there is no image of the required size, null is returned.
+*
+* @param faviconURL The URL for which a Favicon is desired. Must not be null.
+* @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) {
+if (faviconURL == null) {
+Log.e(LOGTAG, "You passed a null faviconURL to getFaviconForDimensions. Don't.");
+return null;
+}
+boolean shouldComputeColour = false;
+boolean wasPermanent = false;
+FaviconsForURL container;
+final Bitmap newBitmap;
+startRead();
+try {
+container = permanentBackingMap.get(faviconURL);
+if (container == null) {
+container = backingMap.get(faviconURL);
+if (container == null) {
+// We don't have it!
+return null;
+}
+} else {
+wasPermanent = true;
+}
+FaviconCacheElement cacheElement;
+// If targetSize is -1, it means we want the largest possible icon.
+int cacheElementIndex = (targetSize == -1) ? -1 : container.getNextHighestIndex(targetSize);
+// cacheElementIndex now holds either the index of the next least largest bitmap from
+// targetSize, or -1 if targetSize > all bitmaps.
+if (cacheElementIndex != -1) {
+// If cacheElementIndex is not the sentinel value, then it is a valid index into favicons.
+cacheElement = container.favicons.get(cacheElementIndex);
+if (cacheElement.invalidated) {
+return null;
+}
+// If we found exactly what we wanted - we're done.
+if (cacheElement.imageSize == targetSize) {
+setMostRecentlyUsedWithinRead(cacheElement);
+return cacheElement.faviconPayload;
+}
+} else {
+// We requested an image larger than all primaries. Set the element to start the search
+// from to the element beyond the end of the array, so the search runs backwards.
+cacheElementIndex = container.favicons.size();
+}
+// We did not find exactly what we wanted, but now have set cacheElementIndex to the index
+// 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);
+if (cacheElement == null) {
+// The primary has been invalidated! Fail! Need to get it back from the database.
+return null;
+}
+if (targetSize == -1) {
+// We got the biggest primary, so that's what we'll return.
+return cacheElement.faviconPayload;
+}
+// Scaling logic...
+Bitmap largestElementBitmap = cacheElement.faviconPayload;
+int largestSize = cacheElement.imageSize;
+if (largestSize >= targetSize) {
+// The largest we have is larger than the target - downsize to target.
+newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);
+} else {
+// Our largest primary is smaller than the desired size. Upscale by a maximum of 2x.
+// largestSize now reflects the maximum size we can upscale to.
+largestSize *= 2;
+if (largestSize >= targetSize) {
+// Perfect! We can upscale by less than 2x and reach the needed size. Do it.
+newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);
+} else {
+// We don't have enough information to make the target size look nonterrible. Best effort:
+newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, largestSize, largestSize, true);
+shouldComputeColour = true;
+}
+}
+} catch (Exception unhandled) {
+// Handle any exception thrown and return the locks to a sensible state.
+// Flag to prevent finally from doubly-unlocking.
+Log.e(LOGTAG, "FaviconCache exception!", unhandled);
+return null;
+} finally {
+finishRead();
+}
+startWrite();
+try {
+if (shouldComputeColour) {
+// And since we failed, we'll need the dominant colour.
+container.ensureDominantColor();
+}
+// 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.
+FaviconCacheElement newElement = container.addSecondary(newBitmap, targetSize);
+if (!wasPermanent) {
+if (setMostRecentlyUsedWithinWrite(newElement)) {
+currentSize.addAndGet(newElement.sizeOf());
+}
+}
+} finally {
+finishWrite();
+}
+return newBitmap;
+}
+/**
+* Query the cache for the dominant colour stored for the Favicon URL provided, if any.
+*
+* @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 int getDominantColor(String key) {
+startRead();
+try {
+FaviconsForURL element = permanentBackingMap.get(key);
+if (element == null) {
+element = backingMap.get(key);
+}
+if (element == null) {
+Log.w(LOGTAG, "Cannot compute dominant color of non-cached favicon. Cache fullness " +
+currentSize.get() + '/' + maxSizeBytes);
+return 0xFFFFFF;
+}
+return element.ensureDominantColor();
+} finally {
+finishRead();
+}
+}
+/**
+* Remove all payloads stored in the given container from the LRU cache.
+* Must be called while holding the write lock.
+*
+* @param wasRemoved The container to purge from the cache.
+*/
+private void recordRemoved(FaviconsForURL wasRemoved) {
+// If there was an existing value, strip it from the insertion-order cache.
+if (wasRemoved == null) {
+return;
+}
+int sizeRemoved = 0;
+for (FaviconCacheElement e : wasRemoved.favicons) {
+sizeRemoved += e.sizeOf();
+ordering.remove(e);
+}
+currentSize.addAndGet(-sizeRemoved);
+}
+private Bitmap produceCacheableBitmap(Bitmap favicon) {
+// Never cache the default Favicon, or the null Favicon.
+if (favicon == Favicons.defaultFavicon || favicon == null) {
+return null;
+}
+// Some sites serve up insanely huge Favicons (Seen 512x512 ones...)
+// While we want to cache nice big icons, we apply a limit based on screen density for the
+// sake of space.
+if (favicon.getWidth() > maxCachedWidth) {
+return Bitmap.createScaledBitmap(favicon, maxCachedWidth, maxCachedWidth, true);
+}
+return favicon;
+}
+/**
+* Set an existing element as the most recently used element. Intended for use from read transactions. While
+* write transactions may safely use this method, it will perform slightly worse than its unsafe counterpart below.
+*
+* @param element The element that is to become the most recently used one.
+* @return true if this element already existed in the list, false otherwise. (Useful for preventing multiple-insertion.)
+*/
+private boolean setMostRecentlyUsedWithinRead(FaviconCacheElement element) {
+reorderingSemaphore.acquireUninterruptibly();
+try {
+boolean contained = ordering.remove(element);
+ordering.offer(element);
+return contained;
+} finally {
+reorderingSemaphore.release();
+}
+}
+/**
+* Functionally equivalent to setMostRecentlyUsedWithinRead, but operates without taking the reordering semaphore.
+* Only safe for use when called from a write transaction, or there is a risk of concurrent modification.
+*
+* @param element The element that is to become the most recently used one.
+* @return true if this element already existed in the list, false otherwise. (Useful for preventing multiple-insertion.)
+*/
+private boolean setMostRecentlyUsedWithinWrite(FaviconCacheElement element) {
+boolean contained = ordering.remove(element);
+ordering.offer(element);
+return contained;
+}
+/**
+* Add the provided bitmap to the cache as the only available primary for this URL.
+* Should never be called with scaled Favicons. The input is assumed to be an unscaled Favicon.
+*
+* @param faviconURL The URL of the Favicon being stored.
+* @param aFavicon The Favicon to store.
+*/
+public void putSingleFavicon(String faviconURL, Bitmap aFavicon) {
+Bitmap favicon = produceCacheableBitmap(aFavicon);
+if (favicon == null) {
+return;
+}
+// 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.
+// Currently set to the number of favicon sizes used in the UI, plus 1, at time of writing.
+// Ought to be  tuned as things change for maximal performance.
+FaviconsForURL toInsert = new FaviconsForURL(NUM_FAVICON_SIZES);
+// Create the cache element for the single element we are inserting, and configure it.
+FaviconCacheElement newElement = toInsert.addPrimary(favicon);
+startWrite();
+try {
+// Set the new element as the most recently used one.
+setMostRecentlyUsedWithinWrite(newElement);
+currentSize.addAndGet(newElement.sizeOf());
+// Update the value in the LruCache...
+FaviconsForURL wasRemoved;
+wasRemoved = backingMap.put(faviconURL, toInsert);
+recordRemoved(wasRemoved);
+} finally {
+finishWrite();
+}
+cullIfRequired();
+}
+/**
+* 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.
+* @param permanently If true, the added favicons are never subject to eviction.
+*/
+public void putFavicons(String faviconURL, Iterator<Bitmap> favicons, boolean permanently) {
+// We don't know how many icons we'll have - let's just take a guess.
+FaviconsForURL toInsert = new FaviconsForURL(5 * NUM_FAVICON_SIZES);
+int sizeGained = 0;
+while (favicons.hasNext()) {
+Bitmap favicon = produceCacheableBitmap(favicons.next());
+if (favicon == null) {
+continue;
+}
+FaviconCacheElement newElement = toInsert.addPrimary(favicon);
+sizeGained += newElement.sizeOf();
+}
+startWrite();
+try {
+if (permanently) {
+permanentBackingMap.put(faviconURL, toInsert);
+return;
+}
+for (FaviconCacheElement newElement : toInsert.favicons) {
+setMostRecentlyUsedWithinWrite(newElement);
+}
+// In the event this insertion is being made to a key that already held a value, the subsequent recordRemoved
+// call will subtract the size of the old value, preventing double-counting.
+currentSize.addAndGet(sizeGained);
+// Update the value in the LruCache...
+recordRemoved(backingMap.put(faviconURL, toInsert));
+} finally {
+finishWrite();
+}
+cullIfRequired();
+}
+/**
+* If cache too large, drop stuff from the cache to get the size back into the acceptable range.
+* Otherwise, do nothing.
+*/
+private void cullIfRequired() {
+Log.d(LOGTAG, "Favicon cache fullness: " + currentSize.get() + '/' + maxSizeBytes);
+if (currentSize.get() <= maxSizeBytes) {
+return;
+}
+startWrite();
+try {
+while (currentSize.get() > maxSizeBytes) {
+// Cull the least recently used element.
+FaviconCacheElement victim;
+victim = ordering.poll();
+currentSize.addAndGet(-victim.sizeOf());
+victim.onEvictedFromCache();
+Log.d(LOGTAG, "After cull: " + currentSize.get() + '/' + maxSizeBytes);
+}
+} finally {
+finishWrite();
+}
+}
+/**
+* Purge all elements from the FaviconCache. Handy if you want to reclaim some memory.
+*/
+public void evictAll() {
+startWrite();
+// Note that we neither clear, nor track the size of, the permanent map.
+try {
+currentSize.set(0);
+backingMap.clear();
+ordering.clear();
+} finally {
+finishWrite();
+}
+}
+}

The Tor Browser / file comparison

comparison: mobile/android/base/favicons/cache/FaviconCache.java

mobile/android/base/favicons/cache/FaviconCache.java