Bug 969417 - Reduce insanity in favicon cache concurrency. r=rnewman
authorChris Kitching <chriskitching@linux.com>
Wed, 12 Mar 2014 16:20:36 +0000
changeset 191499 ff0f9cf36fabbccb51c6150599855c35b59e3b89
parent 191498 7c458c70cd5cfe1238bfe0ee6615273cccaebdcb
child 191500 3a186598d35ec680f2f79634cece42ee6f607d82
push id474
push userasasaki@mozilla.com
push dateMon, 02 Jun 2014 21:01:02 +0000
treeherdermozilla-release@967f4cf1b31c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersrnewman
bugs969417
milestone30.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 969417 - Reduce insanity in favicon cache concurrency. r=rnewman
mobile/android/base/favicons/cache/FaviconCache.java
mobile/android/base/favicons/cache/FaviconsForURL.java
--- a/mobile/android/base/favicons/cache/FaviconCache.java
+++ b/mobile/android/base/favicons/cache/FaviconCache.java
@@ -155,28 +155,16 @@ public class FaviconCache {
 
         if (mOngoingReads.incrementAndGet() == 1) {
             // First one in. Wait for writers to finish and lock them out.
             mWriteLock.acquireUninterruptibly();
         }
     }
 
     /**
-     * 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() {
-        mTurnSemaphore.acquireUninterruptibly();
-        if (mOngoingReads.decrementAndGet() == 0) {
-            mWriteLock.release();
-        }
-        mWriteLock.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 (mOngoingReads.decrementAndGet() == 0) {
             mWriteLock.release();
         }
     }
@@ -212,19 +200,16 @@ public class FaviconCache {
      */
     public boolean isFailedFavicon(String faviconURL) {
         if (faviconURL == null) {
             return true;
         }
 
         startRead();
 
-        boolean isExpired = false;
-        boolean isAborting = false;
-
         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 mPermanentBackingMap.
             if (!mBackingMap.containsKey(faviconURL)) {
                 return false;
             }
 
@@ -235,66 +220,52 @@ public class FaviconCache {
                 return false;
             }
 
             final long failureTimestamp = container.mDownloadTimestamp;
 
             // Calculate elapsed time since the failing download.
             final long failureDiff = System.currentTimeMillis() - failureTimestamp;
 
-            // If long enough has passed, mark it as no longer a failure.
-            if (failureDiff > FAILURE_RETRY_MILLISECONDS) {
-                isExpired = true;
-            } else {
+            // If the expiry is still in effect, return. Otherwise, continue and unmark the failure.
+            if (failureDiff < FAILURE_RETRY_MILLISECONDS) {
                 return true;
             }
         } catch (Exception unhandled) {
-            // Handle any exception thrown and return the locks to a sensible state.
-            finishRead();
-
-            // Flag to prevent finally from doubly-unlocking.
-            isAborting = true;
             Log.e(LOGTAG, "FaviconCache exception!", unhandled);
             return true;
         }  finally {
-            if (!isAborting) {
-                if (isExpired) {
-                    // No longer expired.
-                    upgradeReadToWrite();
-                } else {
-                    finishRead();
-                }
-            }
+            finishRead();
         }
 
+        startWrite();
+
+        // If the entry is no longer failed, remove the record of it from the cache.
         try {
-            recordRemoved(mBackingMap.get(faviconURL));
-            mBackingMap.remove(faviconURL);
+            recordRemoved(mBackingMap.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();
 
-        if (mBackingMap.containsKey(faviconURL)) {
-            recordRemoved(mBackingMap.get(faviconURL));
+        try {
+            FaviconsForURL container = new FaviconsForURL(0, true);
+            recordRemoved(mBackingMap.put(faviconURL, container));
+        } finally {
+            finishWrite();
         }
-
-        FaviconsForURL container = new FaviconsForURL(0, true);
-        mBackingMap.put(faviconURL, container);
-
-        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.
@@ -304,19 +275,17 @@ public class FaviconCache {
      * @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 doingWrites = false;
         boolean shouldComputeColour = false;
-        boolean isAborting = false;
         boolean wasPermanent = false;
         FaviconsForURL container;
         final Bitmap newBitmap;
 
         startRead();
 
         try {
             container = mPermanentBackingMap.get(faviconURL);
@@ -342,17 +311,17 @@ public class FaviconCache {
                 cacheElement = container.mFavicons.get(cacheElementIndex);
 
                 if (cacheElement.mInvalidated) {
                     return null;
                 }
 
                 // If we found exactly what we wanted - we're done.
                 if (cacheElement.mImageSize == targetSize) {
-                    setMostRecentlyUsed(cacheElement);
+                    setMostRecentlyUsedWithinRead(cacheElement);
                     return cacheElement.mFaviconPayload;
                 }
             } 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.mFavicons.size();
             }
 
@@ -368,21 +337,16 @@ public class FaviconCache {
                 return null;
             }
 
             if (targetSize == -1) {
                 // We got the biggest primary, so that's what we'll return.
                 return cacheElement.mFaviconPayload;
             }
 
-            // Having got this far, we'll be needing to write the new secondary to the cache, which
-            // involves us falling through to the next try block. This flag lets us do this (Other
-            // paths prior to this end in returns.)
-            doingWrites = true;
-
             // Scaling logic...
             Bitmap largestElementBitmap = cacheElement.mFaviconPayload;
             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);
             } else {
@@ -396,49 +360,42 @@ public class FaviconCache {
                 } 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) {
-            isAborting = true;
-
             // Handle any exception thrown and return the locks to a sensible state.
-            finishRead();
 
             // Flag to prevent finally from doubly-unlocking.
             Log.e(LOGTAG, "FaviconCache exception!", unhandled);
             return null;
         } finally {
-            if (!isAborting) {
-                if (doingWrites) {
-                    upgradeReadToWrite();
-                } else {
-                    finishRead();
-                }
-            }
+            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) {
-                setMostRecentlyUsed(newElement);
-                mCurrentSize.addAndGet(newElement.sizeOf());
+                if (setMostRecentlyUsedWithinWrite(newElement)) {
+                    mCurrentSize.addAndGet(newElement.sizeOf());
+                }
             }
         } finally {
             finishWrite();
         }
 
         return newBitmap;
     }
 
@@ -459,26 +416,25 @@ public class FaviconCache {
 
             if (element == null) {
                 Log.w(LOGTAG, "Cannot compute dominant color of non-cached favicon. Cache fullness " +
                               mCurrentSize.get() + '/' + mMaxSizeBytes);
                 finishRead();
                 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.
+     * 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;
         }
@@ -500,30 +456,49 @@ public class FaviconCache {
         }
 
         // 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() > mMaxCachedWidth) {
             return Bitmap.createScaledBitmap(favicon, mMaxCachedWidth, mMaxCachedWidth, true);
         }
+
         return favicon;
     }
 
     /**
-     * Set an existing element as the most recently used element. May be called from either type of
-     * transaction.
+     * 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 void setMostRecentlyUsed(FaviconCacheElement element) {
+    private boolean setMostRecentlyUsedWithinRead(FaviconCacheElement element) {
         mReorderingSemaphore.acquireUninterruptibly();
-        mOrdering.remove(element);
+        try {
+            boolean contained = mOrdering.remove(element);
+            mOrdering.offer(element);
+            return contained;
+        } finally {
+            mReorderingSemaphore.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 = mOrdering.remove(element);
         mOrdering.offer(element);
-        mReorderingSemaphore.release();
+        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.
@@ -541,17 +516,17 @@ public class FaviconCache {
         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.
-            setMostRecentlyUsed(newElement);
+            setMostRecentlyUsedWithinWrite(newElement);
 
             mCurrentSize.addAndGet(newElement.sizeOf());
 
             // Update the value in the LruCache...
             FaviconsForURL wasRemoved;
             wasRemoved = mBackingMap.put(faviconURL, toInsert);
 
             recordRemoved(wasRemoved);
@@ -579,52 +554,33 @@ public class FaviconCache {
             if (favicon == null) {
                 continue;
             }
 
             FaviconCacheElement newElement = toInsert.addPrimary(favicon);
             sizeGained += newElement.sizeOf();
         }
 
-        startRead();
-
-        boolean abortingRead = false;
-
-        // Not using setMostRecentlyUsed, because the elements are known to be new. This can be done
-        // without taking the write lock, via the magic of the reordering semaphore.
-        mReorderingSemaphore.acquireUninterruptibly();
-        try {
-            if (!permanently) {
-                for (FaviconCacheElement newElement : toInsert.mFavicons) {
-                    mOrdering.offer(newElement);
-                }
-            }
-        } catch (Exception e) {
-            abortingRead = true;
-            mReorderingSemaphore.release();
-            finishRead();
-
-            Log.e(LOGTAG, "Favicon cache exception!", e);
-            return;
-        } finally {
-            if (!abortingRead) {
-                mReorderingSemaphore.release();
-                upgradeReadToWrite();
-            }
-        }
-
+        startWrite();
         try {
             if (permanently) {
                 mPermanentBackingMap.put(faviconURL, toInsert);
-            } else {
-                mCurrentSize.addAndGet(sizeGained);
+                return;
+            }
+
+            for (FaviconCacheElement newElement : toInsert.mFavicons) {
+                setMostRecentlyUsedWithinWrite(newElement);
+            }
 
-                // Update the value in the LruCache...
-                recordRemoved(mBackingMap.put(faviconURL, toInsert));
-            }
+            // 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.
+            mCurrentSize.addAndGet(sizeGained);
+
+            // Update the value in the LruCache...
+            recordRemoved(mBackingMap.put(faviconURL, toInsert));
         } finally {
             finishWrite();
         }
 
         cullIfRequired();
     }
 
     /**
--- a/mobile/android/base/favicons/cache/FaviconsForURL.java
+++ b/mobile/android/base/favicons/cache/FaviconsForURL.java
@@ -39,22 +39,26 @@ public class FaviconsForURL {
         return addInternal(favicon, true, favicon.getWidth());
     }
 
     private FaviconCacheElement addInternal(Bitmap favicon, boolean isPrimary, int imageSize) {
         FaviconCacheElement c = new FaviconCacheElement(favicon, isPrimary, imageSize, this);
 
         int index = Collections.binarySearch(mFavicons, c);
 
+        // We've already got an equivalent one. We don't care about this new one. This only occurs in certain obscure
+        // case conditions.
+        if (index >= 0) {
+            return mFavicons.get(index);
+        }
+
         // binarySearch returns -x - 1 where x is the insertion point of the element. Convert
         // this to the actual insertion point..
-        if (index < 0) {
-            index++;
-            index = -index;
-        }
+        index++;
+        index = -index;
         mFavicons.add(index, c);
 
         return c;
     }
 
     /**
      * Get the index of the smallest image in this collection larger than or equal to
      * the given target size.