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 35 matching lines @@
     // init with 0xFF so that the charCode field will be -1, which is invalid
     memset(fCharToGlyphHash, 0xFF, sizeof(fCharToGlyphHash));
 
     fMemoryUsed = sizeof(*this);
 
     fGlyphArray.setReserve(kMinGlyphCount);
 
     fMetricsCount = 0;
     fAdvanceCount = 0;
     fAuxProcList = NULL;
+    
+    getGlobals().registerCache(this);
 }
 
 SkGlyphCache::~SkGlyphCache() {
 #if 0
     {
         size_t ptrMem = fGlyphArray.count() * sizeof(SkGlyph*);
         size_t glyphAlloc = fGlyphAlloc.totalCapacity();
         size_t glyphHashUsed = 0;
         size_t uniHashUsed = 0;
         for (int i = 0; i < kHashCount; ++i) {
@@ skipping 19 matching lines @@
     while (gptr < stop) {
         SkPath* path = (*gptr)->fPath;
         if (path) {
             SkDELETE(path);
         }
         gptr += 1;
     }
     SkDescriptor::Free(fDesc);
     SkDELETE(fScalerContext);
     this->invokeAndRemoveAuxProcs();
+
+    getGlobals().unregisterCache(this);
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
 #define VALIDATE()  AutoValidate av(this)
 #else
 #define VALIDATE()
 #endif
 
@@ skipping 263 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;
     }
 
-    size_t prevLimit = fFontCacheLimit;
-    fFontCacheLimit = newLimit;
+    SkAutoMutexAcquire    ac(fMutex);
 
-    size_t currUsed = fTotalMemoryUsed;
-    if (currUsed > newLimit) {
-        SkAutoMutexAcquire    ac(fMutex);
-        SkGlyphCache::InternalFreeCache(this, currUsed - newLimit);
-    }
+    size_t prevLimit = fCacheSizeLimit;
+    fCacheSizeLimit = newLimit;
+    this->internalPurge();
     return prevLimit;
 }
 
 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();
 
@@ skipping 73 matching lines @@
         }
         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().attachCache(cache);
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 SkGlyphCache* SkGlyphCache::FindTail(SkGlyphCache* cache) {
     if (cache) {
         while (cache->fNext) {
             cache = cache->fNext;
         }
     }
     return cache;
 }
 
-#ifdef SK_DEBUG
-void SkGlyphCache_Globals::validate() const {
-    size_t computed = 0;
+///////////////////////////////////////////////////////////////////////////////
 
-    const SkGlyphCache* head = fHead;
-    while (head != NULL) {
-        computed += head->fMemoryUsed;
-        head = head->fNext;
+void SkGlyphCache_Globals::attachCache(SkGlyphCache* cache) {
+    SkAutoMutexAcquire    ac(fMutex);
+
+    this->validate();
+    cache->validate();
+
+    cache->attachToHead(&fHead);
+    fTotalMemoryUsed += cache->fMemoryUsed;
+
+    this->internalPurge();
+}
+
+size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
+    this->validate();
+
+    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 = SkGlyphCache::FindTail(fHead);
+    while (cache != NULL &&
+           (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
         SkGlyphCache* prev = cache->fPrev;
         bytesFreed += cache->fMemoryUsed;
+        countFreed += 1;
 
-        cache->detach(&globals->fHead);
+        cache->detach(&fHead);
         SkDELETE(cache);
         cache = prev;
-        count += 1;
     }
 
-    SkASSERT(bytesFreed <= globals->fTotalMemoryUsed);
-    globals->fTotalMemoryUsed -= bytesFreed;
-    globals->validate();
+    SkASSERT(bytesFreed <= fTotalMemoryUsed);
+    SkASSERT(countFreed <= fCacheCount);
+
+    fTotalMemoryUsed -= bytesFreed;
+    fCacheCount -= countFreed;
+    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::registerCache(SkGlyphCache*) {
+    sk_atomic_inc(&fCacheCount);

[bungeman-skia, 2013/09/25 14:46:07]

This is going to set off the chromium tsan bots. Our atomic increment provides
no memory barriers, so the next read of fCacheCount on another thread is going
to be flagged (correctly) as a race.

I'm not sure why this is here and in the constructor/destructor and not instead
handled like fTotalMemoryUsed. I understand that we could 'float above' our
total limit, but this is already true of fTotalMemoryUsed. We don't tend to
detach for long, and when we do it's pretty much only one per thread anyway.
This also means that you don't have to introduce some new memory barriers to
make this work.

[reed1, 2013/09/25 17:30:31]

Help me understand what you're saying. We use sk_atomic_inc all over the place.
Why is this use case different?
To make it easy to ensure that I don't miss-count, I thought having the inc/dec
calls inside the constructor/destructor was the least error prone.
TotalMemoryUsed varies in lots of diff ways, but how many caches we have in play
only really changes in those two places.

 I understand that we could 'float above' our
Again, please help me understand why what I am doing is worse than the other
places we use inc/dec.

[mtklein, 2013/09/25 18:15:25]

I'm confused too.

Memory barriers are about preventing reordering, by the compiler and more
saliently by the CPU.  We can ask for basically every variant of "make sure the
reads and/or writes before this line are visible to the reads and/or writes past
it".  They're largely unknown because x86 provides very strong ordering
guarantees about this all the time, but platforms like ARM don't.  Does that
capture your understanding of the purpose of memory barriers, or am I confused?

As long as you're only using atomic inc/dec operations, you've got a full memory
barrier on that memory you're incrementing and decrementing.  They're atomic
operations, so there's nothing there that _can_ reorder.  But once you start
adding in other operations, like a non-atomic read or a non-atomic subtract,
there's no guarantee about what you'll see.

The only problem I see here is that fCacheCount is being used non-atomically
inside internalPurge.  If it's not possible for there to make concurrent calls
to internalPurge and to registerCache or unregisterCache, we're safe.  If calls
can be made concurrently, then that code definitely is not safe.  There are at
least 5 places where we're asking for the value of fCacheCount, and they could
all return different values.

The typical case where atomics need extra memory barriers I'm aware of is when
you're using them to indicate something about non-atomic memory.  E.g. you could
imagine you have a producer thread generating data by storing it
(non-atomically) into a shared array and then increment an atomic which
represents the last index in the array that's valid, to be consumed by another
consumer thread.

producer:
  while (not done):
    fill the next spot in the array
    atomically increment last_valid_index

consumer:
   last_consumed_index = -1
   while (last_consumed_index != the_end) {
     if (atomically check last_valid_index and assign to last_consumed_index if
not equal) {
        read the array at last_consumed_index and do something with that data
     }
   }

As I understand it, this code needs a memory barrier between the two lines in
the producer.  Without it, the processor is free to reorder the atomic increment
before we write to memory, and the consumer can then read junk.  (Caveat: this
is a sketch for example only; I'm sure the consumer is broken in tons of little
ways.)

My rule of thumb here is, use a mutex unless you're really, really, really sure
it's too slow.  If there's one thing that you can reason about safely with
concurrency (and I'm not sure there is), it's certainly a mutex.  Admittedly,
this particular code is just about the most likely place in Skia to be an
exception where we really need to be clever because the mutex is killing our
performance, but we should make sure we've got a way of measuring that and that
we have measured it.

[bungeman-skia, 2013/09/25 22:37:08]

This use case probably isn't that different from other places where it may also
be used incorrectly. It seems to be used for reference counts like here (and I
can only state the the actual SkRefCnt/SkWeakCnt are mostly correct, I haven't
reviewed the others) and ids (those seem ok).
See https://codereview.chromium.org/24644003/#msg1 for a similar race reported
by tsan.

+}
+
+// call when SkGlyphCache is destroyed
+void SkGlyphCache_Globals::unregisterCache(SkGlyphCache*) {
+    sk_atomic_dec(&fCacheCount);
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 #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;
+    
+    const SkGlyphCache* head = fHead;
+    while (head != NULL) {
+        computedBytes += head->fMemoryUsed;
+        head = head->fNext;
+    }
+    
+    SkASSERT(fTotalMemoryUsed == computedBytes);
+}
+
 #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;
 }
 
 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) {

[bungeman-skia, 2013/09/25 14:46:07]

I realize that this isn't part of this change, but I find this so confusing,
that this needs to be called in order to get the thread local setup. It looks
like (from the name) it's just setting the limit, but there's no default like
there is with the similarly named SkGraphics::SetFontCacheLimit. The fact that
when you set this you also start hiding (or revealing, when setting to 0) the
process wide version is also rather surprising.

[reed1, 2013/09/25 17:30:31]

Agreed, we should rename/document this "feature" better. I suggest I don't
tackle that change in this same CL, but lets write up a bug for it.

     if (0 == bytes) {
         SkGlyphCache_Globals::DeleteTLS();
     } else {
-        SkGlyphCache_Globals::GetTLS().setFontCacheLimit(bytes);
+        SkGlyphCache_Globals::GetTLS().setCacheSizeLimit(bytes);
     }
 }