add counting to glyphcache, and refactor some for clarity

src/core/SkGlyphCache.cpp

 
 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 #include "SkGlyphCache.h"
+#include "SkGlyphCache_Globals.h"
 #include "SkGraphics.h"
 #include "SkPaint.h"
 #include "SkPath.h"
 #include "SkTemplates.h"
 #include "SkTLS.h"
 #include "SkTypeface.h"
 
 //#define SPEW_PURGE_STATUS
 //#define RECORD_HASH_EFFICIENCY
 
 bool gSkSuppressFontCachePurgeSpew;
 
+// Returns the shared globals
+static SkGlyphCache_Globals& getSharedGlobals() {
+    // we leak this, so we don't incur any shutdown cost of the destructor
+    static SkGlyphCache_Globals* gGlobals = SkNEW_ARGS(SkGlyphCache_Globals,
+                                                       (SkGlyphCache_Globals::kYes_UseMutex));
+    return *gGlobals;
+}
+
+// Returns the TLS globals (if set), or the shared globals
+static SkGlyphCache_Globals& getGlobals() {
+    SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
+    return tls ? *tls : getSharedGlobals();
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef RECORD_HASH_EFFICIENCY
     static uint32_t gHashSuccess;
     static uint32_t gHashCollision;
 
     static void RecordHashSuccess() {
         gHashSuccess += 1;
     }
 
@@ skipping 357 matching lines @@
         rec->fProc(rec->fData);
         AuxProcRec* next = rec->fNext;
         SkDELETE(rec);
         rec = next;
     }
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 ///////////////////////////////////////////////////////////////////////////////
 
-#ifndef SK_DEFAULT_FONT_CACHE_LIMIT
-    #define SK_DEFAULT_FONT_CACHE_LIMIT     (2 * 1024 * 1024)
-#endif
-
 #include "SkThread.h"
 
-class SkGlyphCache_Globals {
-public:
-    enum UseMutex {
-        kNo_UseMutex,  // thread-local cache
-        kYes_UseMutex  // shared cache
-    };
-
-    SkGlyphCache_Globals(UseMutex um) {
-        fHead = NULL;
-        fTotalMemoryUsed = 0;
-        fFontCacheLimit = SK_DEFAULT_FONT_CACHE_LIMIT;
-        fMutex = (kYes_UseMutex == um) ? SkNEW(SkMutex) : NULL;
-    }
-
-    ~SkGlyphCache_Globals() {
-        SkGlyphCache* cache = fHead;
-        while (cache) {
-            SkGlyphCache* next = cache->fNext;
-            SkDELETE(cache);
-            cache = next;
-        }
-
-        SkDELETE(fMutex);
-    }
-
-    SkMutex*        fMutex;
-    SkGlyphCache*   fHead;
-    size_t          fTotalMemoryUsed;
-
-#ifdef SK_DEBUG
-    void validate() const;
-#else
-    void validate() const {}
-#endif
-
-    size_t  getFontCacheLimit() const { return fFontCacheLimit; }
-    size_t  setFontCacheLimit(size_t limit);
-    void    purgeAll(); // does not change budget
-
-    // can return NULL
-    static SkGlyphCache_Globals* FindTLS() {
-        return (SkGlyphCache_Globals*)SkTLS::Find(CreateTLS);
-    }
-
-    static SkGlyphCache_Globals& GetTLS() {
-        return *(SkGlyphCache_Globals*)SkTLS::Get(CreateTLS, DeleteTLS);
-    }
-
-    static void DeleteTLS() { SkTLS::Delete(CreateTLS); }
-
-private:
-    size_t  fFontCacheLimit;
-
-    static void* CreateTLS() {
-        return SkNEW_ARGS(SkGlyphCache_Globals, (kNo_UseMutex));
-    }
-
-    static void DeleteTLS(void* ptr) {
-        SkDELETE((SkGlyphCache_Globals*)ptr);
-    }
-};
-
-size_t SkGlyphCache_Globals::setFontCacheLimit(size_t newLimit) {
+size_t SkGlyphCache_Globals::setCacheSizeLimit(size_t newLimit) {
     static const size_t minLimit = 256 * 1024;
     if (newLimit < minLimit) {
         newLimit = minLimit;
     }
+    
+    SkAutoMutexAcquire    ac(fMutex);
+    
+    size_t prevLimit = fCacheSizeLimit;
+    fCacheSizeLimit = newLimit;
+    this->internalPurge();
+    return prevLimit;
+}
 
-    size_t prevLimit = fFontCacheLimit;
-    fFontCacheLimit = newLimit;
-
-    size_t currUsed = fTotalMemoryUsed;
-    if (currUsed > newLimit) {
-        SkAutoMutexAcquire    ac(fMutex);
-        SkGlyphCache::InternalFreeCache(this, currUsed - newLimit);
+int SkGlyphCache_Globals::setCacheCountLimit(int newCount) {
+    if (newCount < 0) {
+        newCount = 0;
     }
-    return prevLimit;
+    
+    SkAutoMutexAcquire    ac(fMutex);
+    
+    int prevCount = fCacheCountLimit;
+    fCacheCountLimit = newCount;
+    this->internalPurge();
+    return prevCount;
 }
 
 void SkGlyphCache_Globals::purgeAll() {
     SkAutoMutexAcquire    ac(fMutex);
-    SkGlyphCache::InternalFreeCache(this, fTotalMemoryUsed);
-}
-
-// Returns the shared globals
-static SkGlyphCache_Globals& getSharedGlobals() {
-    // we leak this, so we don't incur any shutdown cost of the destructor
-    static SkGlyphCache_Globals* gGlobals = SkNEW_ARGS(SkGlyphCache_Globals,
-                                       (SkGlyphCache_Globals::kYes_UseMutex));
-    return *gGlobals;
-}
-
-// Returns the TLS globals (if set), or the shared globals
-static SkGlyphCache_Globals& getGlobals() {
-    SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
-    return tls ? *tls : getSharedGlobals();
+    this->internalPurge(fTotalMemoryUsed);
 }
 
 void SkGlyphCache::VisitAllCaches(bool (*proc)(SkGlyphCache*, void*),
                                   void* context) {
     SkGlyphCache_Globals& globals = getGlobals();
     SkAutoMutexAcquire    ac(globals.fMutex);
     SkGlyphCache*         cache;
 
     globals.validate();
 
-    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
+    for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
         if (proc(cache, context)) {
             break;
         }
     }
 
     globals.validate();
 }
 
 /*  This guy calls the visitor from within the mutext lock, so the visitor
     cannot:
@@ skipping 10 matching lines @@
     }
     SkASSERT(desc);
 
     SkGlyphCache_Globals& globals = getGlobals();
     SkAutoMutexAcquire    ac(globals.fMutex);
     SkGlyphCache*         cache;
     bool                  insideMutex = true;
 
     globals.validate();
 
-    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
+    for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
         if (cache->fDesc->equals(*desc)) {
-            cache->detach(&globals.fHead);
+            globals.internalDetachCache(cache);
             goto FOUND_IT;
         }
     }
 
     /* Release the mutex now, before we create a new entry (which might have
         side-effects like trying to access the cache/mutex (yikes!)
     */
     ac.release();           // release the mutex now
     insideMutex = false;    // can't use globals anymore
 
     // Check if we can create a scaler-context before creating the glyphcache.
     // If not, we may have exhausted OS/font resources, so try purging the
     // cache once and try again.
     {
         // pass true the first time, to notice if the scalercontext failed,
         // so we can try the purge.
         SkScalerContext* ctx = typeface->createScalerContext(desc, true);
         if (!ctx) {
             getSharedGlobals().purgeAll();
             ctx = typeface->createScalerContext(desc, false);
             SkASSERT(ctx);
         }
         cache = SkNEW_ARGS(SkGlyphCache, (typeface, desc, ctx));
     }
 
 FOUND_IT:
 
     AutoValidate av(cache);
 
-    if (proc(cache, context)) {   // stay detached
+    if (!proc(cache, context)) {   // need to reattach
         if (insideMutex) {
-            SkASSERT(globals.fTotalMemoryUsed >= cache->fMemoryUsed);
-            globals.fTotalMemoryUsed -= cache->fMemoryUsed;
-        }
-    } else {                        // reattach
-        if (insideMutex) {
-            cache->attachToHead(&globals.fHead);
+            globals.internalAttachCacheToHead(cache);
         } else {
-            AttachCache(cache);
+            globals.attachCacheToHead(cache);
         }
         cache = NULL;
     }
     return cache;
 }
 
 void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
     SkASSERT(cache);
     SkASSERT(cache->fNext == NULL);
 
-    SkGlyphCache_Globals& globals = getGlobals();
-    SkAutoMutexAcquire    ac(globals.fMutex);
-
-    globals.validate();
-    cache->validate();
-
-    // if we have a fixed budget for our cache, do a purge here
-    {
-        size_t allocated = globals.fTotalMemoryUsed + cache->fMemoryUsed;
-        size_t budgeted = globals.getFontCacheLimit();
-        if (allocated > budgeted) {
-            (void)InternalFreeCache(&globals, allocated - budgeted);
-        }
-    }
-
-    cache->attachToHead(&globals.fHead);
-    globals.fTotalMemoryUsed += cache->fMemoryUsed;
-
-    globals.validate();
+    getGlobals().attachCacheToHead(cache);
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
-SkGlyphCache* SkGlyphCache::FindTail(SkGlyphCache* cache) {
+void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
+    SkAutoMutexAcquire    ac(fMutex);
+
+    this->validate();
+    cache->validate();
+
+    this->internalAttachCacheToHead(cache);
+    this->internalPurge();
+}
+
+SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const {
+    SkGlyphCache* cache = fHead;
     if (cache) {
         while (cache->fNext) {
             cache = cache->fNext;
         }
     }
     return cache;
 }
 
-#ifdef SK_DEBUG
-void SkGlyphCache_Globals::validate() const {
-    size_t computed = 0;
+size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
+    this->validate();
 
-    const SkGlyphCache* head = fHead;
-    while (head != NULL) {
-        computed += head->fMemoryUsed;
-        head = head->fNext;
+    size_t bytesNeeded = 0;
+    if (fTotalMemoryUsed > fCacheSizeLimit) {
+        bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit;
+    }
+    bytesNeeded = SkMax32(bytesNeeded, minBytesNeeded);
+    if (bytesNeeded) {
+        // no small purges!
+        bytesNeeded = SkMax32(bytesNeeded, fTotalMemoryUsed >> 2);
     }
 
-    if (fTotalMemoryUsed != computed) {
-        printf("total %d, computed %d\n", (int)fTotalMemoryUsed, (int)computed);
+    int countNeeded = 0;
+    if (fCacheCount > fCacheCountLimit) {
+        countNeeded = fCacheCount - fCacheCountLimit;
+        // no small purges!
+        countNeeded = SkMax32(countNeeded, fCacheCount >> 2);
     }
-    SkASSERT(fTotalMemoryUsed == computed);
-}
-#endif
 
-size_t SkGlyphCache::InternalFreeCache(SkGlyphCache_Globals* globals,
-                                       size_t bytesNeeded) {
-    globals->validate();
+    // early exit
+    if (!countNeeded && !bytesNeeded) {
+        return 0;
+    }
 
     size_t  bytesFreed = 0;
-    int     count = 0;
+    int     countFreed = 0;
 
-    // don't do any "small" purges
-    size_t minToPurge = globals->fTotalMemoryUsed >> 2;
-    if (bytesNeeded < minToPurge)
-        bytesNeeded = minToPurge;
-
-    SkGlyphCache* cache = FindTail(globals->fHead);
-    while (cache != NULL && bytesFreed < bytesNeeded) {
+    // we start at the tail and proceed backwards, as the linklist is in LRU
+    // order, with unimportant entries at the tail.
+    SkGlyphCache* cache = this->internalGetTail();
+    while (cache != NULL &&
+           (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
         SkGlyphCache* prev = cache->fPrev;
         bytesFreed += cache->fMemoryUsed;
+        countFreed += 1;
 
-        cache->detach(&globals->fHead);
+        this->internalDetachCache(cache);
         SkDELETE(cache);
         cache = prev;
-        count += 1;
     }
 
-    SkASSERT(bytesFreed <= globals->fTotalMemoryUsed);
-    globals->fTotalMemoryUsed -= bytesFreed;
-    globals->validate();
+    this->validate();
 
 #ifdef SPEW_PURGE_STATUS
-    if (count && !gSkSuppressFontCachePurgeSpew) {
+    if (countFreed && !gSkSuppressFontCachePurgeSpew) {
         SkDebugf("purging %dK from font cache [%d entries]\n",
-                 (int)(bytesFreed >> 10), count);
+                 (int)(bytesFreed >> 10), countFreed);
     }
 #endif
 
     return bytesFreed;
 }
 
+void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) {
+    SkASSERT(NULL == cache->fPrev && NULL == cache->fNext);
+    if (fHead) {
+        fHead->fPrev = cache;
+        cache->fNext = fHead;
+    }
+    fHead = cache;
+    
+    fCacheCount += 1;
+    fTotalMemoryUsed += cache->fMemoryUsed;
+}
+
+void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
+    SkASSERT(fCacheCount > 0);
+    fCacheCount -= 1;
+    fTotalMemoryUsed -= cache->fMemoryUsed;
+
+    if (cache->fPrev) {
+        cache->fPrev->fNext = cache->fNext;
+    } else {
+        fHead = cache->fNext;
+    }
+    if (cache->fNext) {
+        cache->fNext->fPrev = cache->fPrev;
+    }
+    cache->fPrev = cache->fNext = NULL;
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
+
 void SkGlyphCache::validate() const {
 #ifdef SK_DEBUG_GLYPH_CACHE
     int count = fGlyphArray.count();
     for (int i = 0; i < count; i++) {
         const SkGlyph* glyph = fGlyphArray[i];
         SkASSERT(glyph);
         SkASSERT(fGlyphAlloc.contains(glyph));
         if (glyph->fImage) {
             SkASSERT(fGlyphAlloc.contains(glyph->fImage));
         }
     }
 #endif
 }
+
+void SkGlyphCache_Globals::validate() const {
+    size_t computedBytes = 0;
+    int computedCount = 0;
+    
+    const SkGlyphCache* head = fHead;
+    while (head != NULL) {
+        computedBytes += head->fMemoryUsed;
+        computedCount += 1;
+        head = head->fNext;
+    }
+    
+    SkASSERT(fTotalMemoryUsed == computedBytes);
+    SkASSERT(fCacheCount == computedCount);
+}
+
 #endif
 
 ///////////////////////////////////////////////////////////////////////////////
 ///////////////////////////////////////////////////////////////////////////////
 
 #include "SkTypefaceCache.h"
 
 size_t SkGraphics::GetFontCacheLimit() {
-    return getSharedGlobals().getFontCacheLimit();
+    return getSharedGlobals().getCacheSizeLimit();
 }
 
 size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
-    return getSharedGlobals().setFontCacheLimit(bytes);
+    return getSharedGlobals().setCacheSizeLimit(bytes);
 }
 
 size_t SkGraphics::GetFontCacheUsed() {
-    return getSharedGlobals().fTotalMemoryUsed;
+    return getSharedGlobals().getTotalMemoryUsed();
+}
+
+int SkGraphics::GetFontCacheCountLimit() {
+    return getSharedGlobals().getCacheCountLimit();
+}
+
+int SkGraphics::SetFontCacheCountLimit(int count) {
+    return getSharedGlobals().setCacheCountLimit(count);
+}
+
+int SkGraphics::GetFontCacheCountUsed() {
+    return getSharedGlobals().getCacheCountUsed();
 }
 
 void SkGraphics::PurgeFontCache() {
     getSharedGlobals().purgeAll();
     SkTypefaceCache::PurgeAll();
 }
 
 size_t SkGraphics::GetTLSFontCacheLimit() {
     const SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
-    return tls ? tls->getFontCacheLimit() : 0;
+    return tls ? tls->getCacheSizeLimit() : 0;
 }
 
 void SkGraphics::SetTLSFontCacheLimit(size_t bytes) {
     if (0 == bytes) {
         SkGlyphCache_Globals::DeleteTLS();
     } else {
-        SkGlyphCache_Globals::GetTLS().setFontCacheLimit(bytes);
+        SkGlyphCache_Globals::GetTLS().setCacheSizeLimit(bytes);
     }
 }