Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2006 The Android Open Source Project
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #include "SkGlyphCache.h"
      9 #include "SkGlyphCache_Globals.h"
     10 #include "SkGraphics.h"
     11 #include "SkOnce.h"
     12 #include "SkPath.h"
     13 #include "SkTemplates.h"
     14 #include "SkTraceMemoryDump.h"
     15 #include "SkTypeface.h"
     16 
     17 #include <cctype>
     18 
     19 //#define SPEW_PURGE_STATUS
     20 
     21 namespace {
     22 const char gGlyphCacheDumpName[] = "skia/sk_glyph_cache";
     23 }  // namespace
     24 
     25 // Returns the shared globals
     26 static SkGlyphCache_Globals& get_globals() {
     27     static SkOnce once;
     28     static SkGlyphCache_Globals* globals;
     29 
     30     once([]{ globals = new SkGlyphCache_Globals; });
     31     return *globals;
     32 }
     33 
     34 ///////////////////////////////////////////////////////////////////////////////
     35 
     36 SkGlyphCache::SkGlyphCache(const SkDescriptor* desc, std::unique_ptr<SkScalerContext> ctx)
     37     : fDesc(desc->copy())
     38     , fScalerContext(std::move(ctx)) {
     39     SkASSERT(desc);
     40     SkASSERT(fScalerContext);
     41 
     42     fPrev = fNext = nullptr;
     43 
     44     fScalerContext->getFontMetrics(&fFontMetrics);
     45 
     46     fMemoryUsed = sizeof(*this);
     47 }
     48 
     49 SkGlyphCache::~SkGlyphCache() {
     50     fGlyphMap.foreach([](SkGlyph* g) {
     51         if (g->fPathData) {
     52             delete g->fPathData->fPath;
     53         }
     54     });
     55 }
     56 
     57 SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(SkPackedUnicharID packedUnicharID) {
     58     if (!fPackedUnicharIDToPackedGlyphID) {
     59         fPackedUnicharIDToPackedGlyphID.reset(new CharGlyphRec[kHashCount]);
     60     }
     61 
     62     return &fPackedUnicharIDToPackedGlyphID[packedUnicharID.hash() & kHashMask];
     63 }
     64 
     65 ///////////////////////////////////////////////////////////////////////////////
     66 
     67 #ifdef SK_DEBUG
     68 #define VALIDATE()  AutoValidate av(this)
     69 #else
     70 #define VALIDATE()
     71 #endif
     72 
     73 SkGlyphID SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
     74     VALIDATE();
     75     SkPackedUnicharID packedUnicharID(charCode);
     76     CharGlyphRec* rec = this->getCharGlyphRec(packedUnicharID);
     77 
     78     if (rec->fPackedUnicharID == packedUnicharID) {
     79         // The glyph exists in the unichar to glyph mapping cache. Return it.
     80         return rec->fPackedGlyphID.code();
     81     } else {
     82         // The glyph is not in the unichar to glyph mapping cache. Insert it.
     83         rec->fPackedUnicharID = packedUnicharID;
     84         SkGlyphID glyphID = fScalerContext->charToGlyphID(charCode);
     85         rec->fPackedGlyphID = SkPackedGlyphID(glyphID);
     86         return glyphID;
     87     }
     88 }
     89 
     90 SkUnichar SkGlyphCache::glyphToUnichar(SkGlyphID glyphID) {
     91     return fScalerContext->glyphIDToChar(glyphID);
     92 }
     93 
     94 unsigned SkGlyphCache::getGlyphCount() const {
     95     return fScalerContext->getGlyphCount();
     96 }
     97 
     98 int SkGlyphCache::countCachedGlyphs() const {
     99     return fGlyphMap.count();
    100 }
    101 
    102 ///////////////////////////////////////////////////////////////////////////////
    103 
    104 const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
    105     VALIDATE();
    106     return *this->lookupByChar(charCode, kJustAdvance_MetricsType);
    107 }
    108 
    109 const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
    110     VALIDATE();
    111     SkPackedGlyphID packedGlyphID(glyphID);
    112     return *this->lookupByPackedGlyphID(packedGlyphID, kJustAdvance_MetricsType);
    113 }
    114 
    115 ///////////////////////////////////////////////////////////////////////////////
    116 
    117 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
    118     VALIDATE();
    119     return *this->lookupByChar(charCode, kFull_MetricsType);
    120 }
    121 
    122 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode, SkFixed x, SkFixed y) {
    123     VALIDATE();
    124     return *this->lookupByChar(charCode, kFull_MetricsType, x, y);
    125 }
    126 
    127 const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
    128     VALIDATE();
    129     SkPackedGlyphID packedGlyphID(glyphID);
    130     return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
    131 }
    132 
    133 const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
    134     VALIDATE();
    135     SkPackedGlyphID packedGlyphID(glyphID, x, y);
    136     return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
    137 }
    138 
    139 SkGlyph* SkGlyphCache::lookupByChar(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) {
    140     SkPackedUnicharID id(charCode, x, y);
    141     CharGlyphRec* rec = this->getCharGlyphRec(id);
    142     if (rec->fPackedUnicharID != id) {
    143         rec->fPackedUnicharID = id;
    144         rec->fPackedGlyphID = SkPackedGlyphID(fScalerContext->charToGlyphID(charCode), x, y);
    145     }
    146     return this->lookupByPackedGlyphID(rec->fPackedGlyphID, type);
    147 }
    148 
    149 SkGlyph* SkGlyphCache::lookupByPackedGlyphID(SkPackedGlyphID packedGlyphID, MetricsType type) {
    150     SkGlyph* glyph = fGlyphMap.find(packedGlyphID);
    151 
    152     if (nullptr == glyph) {
    153         glyph = this->allocateNewGlyph(packedGlyphID, type);
    154     } else {
    155         if (type == kFull_MetricsType && glyph->isJustAdvance()) {
    156            fScalerContext->getMetrics(glyph);
    157         }
    158     }
    159     return glyph;
    160 }
    161 
    162 SkGlyph* SkGlyphCache::allocateNewGlyph(SkPackedGlyphID packedGlyphID, MetricsType mtype) {
    163     fMemoryUsed += sizeof(SkGlyph);
    164 
    165     SkGlyph* glyphPtr;
    166     {
    167         SkGlyph glyph;
    168         glyph.initWithGlyphID(packedGlyphID);
    169         glyphPtr = fGlyphMap.set(glyph);
    170     }
    171 
    172     if (kJustAdvance_MetricsType == mtype) {
    173         fScalerContext->getAdvance(glyphPtr);
    174     } else {
    175         SkASSERT(kFull_MetricsType == mtype);
    176         fScalerContext->getMetrics(glyphPtr);
    177     }
    178 
    179     SkASSERT(glyphPtr->fID != SkPackedGlyphID());
    180     return glyphPtr;
    181 }
    182 
    183 const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
    184     if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
    185         if (nullptr == glyph.fImage) {
    186             size_t  size = const_cast<SkGlyph&>(glyph).allocImage(&fAlloc);
    187             // check that alloc() actually succeeded
    188             if (glyph.fImage) {
    189                 fScalerContext->getImage(glyph);
    190                 // TODO: the scaler may have changed the maskformat during
    191                 // getImage (e.g. from AA or LCD to BW) which means we may have
    192                 // overallocated the buffer. Check if the new computedImageSize
    193                 // is smaller, and if so, strink the alloc size in fImageAlloc.
    194                 fMemoryUsed += size;
    195             }
    196         }
    197     }
    198     return glyph.fImage;
    199 }
    200 
    201 const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
    202     if (glyph.fWidth) {
    203         if (glyph.fPathData == nullptr) {
    204             SkGlyph::PathData* pathData = fAlloc.make<SkGlyph::PathData>();
    205             const_cast<SkGlyph&>(glyph).fPathData = pathData;
    206             pathData->fIntercept = nullptr;
    207             SkPath* path = pathData->fPath = new SkPath;
    208             fScalerContext->getPath(glyph.getPackedID(), path);
    209             fMemoryUsed += sizeof(SkPath) + path->countPoints() * sizeof(SkPoint);
    210         }
    211     }
    212     return glyph.fPathData ? glyph.fPathData->fPath : nullptr;
    213 }
    214 
    215 #include "../pathops/SkPathOpsCubic.h"
    216 #include "../pathops/SkPathOpsQuad.h"
    217 
    218 static bool quad_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
    219     SkScalar min = SkTMin(SkTMin(pts[0], pts[2]), pts[4]);
    220     if (bounds[1] < min) {
    221         return false;
    222     }
    223     SkScalar max = SkTMax(SkTMax(pts[0], pts[2]), pts[4]);
    224     return bounds[0] < max;
    225 }
    226 
    227 static bool cubic_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
    228     SkScalar min = SkTMin(SkTMin(SkTMin(pts[0], pts[2]), pts[4]), pts[6]);
    229     if (bounds[1] < min) {
    230         return false;
    231     }
    232     SkScalar max = SkTMax(SkTMax(SkTMax(pts[0], pts[2]), pts[4]), pts[6]);
    233     return bounds[0] < max;
    234 }
    235 
    236 void SkGlyphCache::OffsetResults(const SkGlyph::Intercept* intercept, SkScalar scale,
    237                                  SkScalar xPos, SkScalar* array, int* count) {
    238     if (array) {
    239         array += *count;
    240         for (int index = 0; index < 2; index++) {
    241             *array++ = intercept->fInterval[index] * scale + xPos;
    242         }
    243     }
    244     *count += 2;
    245 }
    246 
    247 void SkGlyphCache::AddInterval(SkScalar val, SkGlyph::Intercept* intercept) {
    248     intercept->fInterval[0] = SkTMin(intercept->fInterval[0], val);
    249     intercept->fInterval[1] = SkTMax(intercept->fInterval[1], val);
    250 }
    251 
    252 void SkGlyphCache::AddPoints(const SkPoint* pts, int ptCount, const SkScalar bounds[2],
    253         bool yAxis, SkGlyph::Intercept* intercept) {
    254     for (int i = 0; i < ptCount; ++i) {
    255         SkScalar val = *(&pts[i].fY - yAxis);
    256         if (bounds[0] < val && val < bounds[1]) {
    257             AddInterval(*(&pts[i].fX + yAxis), intercept);
    258         }
    259     }
    260 }
    261 
    262 void SkGlyphCache::AddLine(const SkPoint pts[2], SkScalar axis, bool yAxis,
    263                      SkGlyph::Intercept* intercept) {
    264     SkScalar t = yAxis ? (axis - pts[0].fX) / (pts[1].fX - pts[0].fX)
    265             : (axis - pts[0].fY) / (pts[1].fY - pts[0].fY);
    266     if (0 <= t && t < 1) {   // this handles divide by zero above
    267         AddInterval(yAxis ? pts[0].fY + t * (pts[1].fY - pts[0].fY)
    268             : pts[0].fX + t * (pts[1].fX - pts[0].fX), intercept);
    269     }
    270 }
    271 
    272 void SkGlyphCache::AddQuad(const SkPoint pts[3], SkScalar axis, bool yAxis,
    273                      SkGlyph::Intercept* intercept) {
    274     SkDQuad quad;
    275     quad.set(pts);
    276     double roots[2];
    277     int count = yAxis ? quad.verticalIntersect(axis, roots)
    278             : quad.horizontalIntersect(axis, roots);
    279     while (--count >= 0) {
    280         SkPoint pt = quad.ptAtT(roots[count]).asSkPoint();
    281         AddInterval(*(&pt.fX + yAxis), intercept);
    282     }
    283 }
    284 
    285 void SkGlyphCache::AddCubic(const SkPoint pts[4], SkScalar axis, bool yAxis,
    286                       SkGlyph::Intercept* intercept) {
    287     SkDCubic cubic;
    288     cubic.set(pts);
    289     double roots[3];
    290     int count = yAxis ? cubic.verticalIntersect(axis, roots)
    291             : cubic.horizontalIntersect(axis, roots);
    292     while (--count >= 0) {
    293         SkPoint pt = cubic.ptAtT(roots[count]).asSkPoint();
    294         AddInterval(*(&pt.fX + yAxis), intercept);
    295     }
    296 }
    297 
    298 const SkGlyph::Intercept* SkGlyphCache::MatchBounds(const SkGlyph* glyph,
    299                                                     const SkScalar bounds[2]) {
    300     if (!glyph->fPathData) {
    301         return nullptr;
    302     }
    303     const SkGlyph::Intercept* intercept = glyph->fPathData->fIntercept;
    304     while (intercept) {
    305         if (bounds[0] == intercept->fBounds[0] && bounds[1] == intercept->fBounds[1]) {
    306             return intercept;
    307         }
    308         intercept = intercept->fNext;
    309     }
    310     return nullptr;
    311 }
    312 
    313 void SkGlyphCache::findIntercepts(const SkScalar bounds[2], SkScalar scale, SkScalar xPos,
    314         bool yAxis, SkGlyph* glyph, SkScalar* array, int* count) {
    315     const SkGlyph::Intercept* match = MatchBounds(glyph, bounds);
    316 
    317     if (match) {
    318         if (match->fInterval[0] < match->fInterval[1]) {
    319             OffsetResults(match, scale, xPos, array, count);
    320         }
    321         return;
    322     }
    323 
    324     SkGlyph::Intercept* intercept = fAlloc.make<SkGlyph::Intercept>();
    325     intercept->fNext = glyph->fPathData->fIntercept;
    326     intercept->fBounds[0] = bounds[0];
    327     intercept->fBounds[1] = bounds[1];
    328     intercept->fInterval[0] = SK_ScalarMax;
    329     intercept->fInterval[1] = SK_ScalarMin;
    330     glyph->fPathData->fIntercept = intercept;
    331     const SkPath* path = glyph->fPathData->fPath;
    332     const SkRect& pathBounds = path->getBounds();
    333     if (*(&pathBounds.fBottom - yAxis) < bounds[0] || bounds[1] < *(&pathBounds.fTop - yAxis)) {
    334         return;
    335     }
    336     SkPath::Iter iter(*path, false);
    337     SkPoint pts[4];
    338     SkPath::Verb verb;
    339     while (SkPath::kDone_Verb != (verb = iter.next(pts))) {
    340         switch (verb) {
    341             case SkPath::kMove_Verb:
    342                 break;
    343             case SkPath::kLine_Verb:
    344                 AddLine(pts, bounds[0], yAxis, intercept);
    345                 AddLine(pts, bounds[1], yAxis, intercept);
    346                 AddPoints(pts, 2, bounds, yAxis, intercept);
    347                 break;
    348             case SkPath::kQuad_Verb:
    349                 if (!quad_in_bounds(&pts[0].fY - yAxis, bounds)) {
    350                     break;
    351                 }
    352                 AddQuad(pts, bounds[0], yAxis, intercept);
    353                 AddQuad(pts, bounds[1], yAxis, intercept);
    354                 AddPoints(pts, 3, bounds, yAxis, intercept);
    355                 break;
    356             case SkPath::kConic_Verb:
    357                 SkASSERT(0);  // no support for text composed of conics
    358                 break;
    359             case SkPath::kCubic_Verb:
    360                 if (!cubic_in_bounds(&pts[0].fY - yAxis, bounds)) {
    361                     break;
    362                 }
    363                 AddCubic(pts, bounds[0], yAxis, intercept);
    364                 AddCubic(pts, bounds[1], yAxis, intercept);
    365                 AddPoints(pts, 4, bounds, yAxis, intercept);
    366                 break;
    367             case SkPath::kClose_Verb:
    368                 break;
    369             default:
    370                 SkASSERT(0);
    371                 break;
    372         }
    373     }
    374     if (intercept->fInterval[0] >= intercept->fInterval[1]) {
    375         intercept->fInterval[0] = SK_ScalarMax;
    376         intercept->fInterval[1] = SK_ScalarMin;
    377         return;
    378     }
    379     OffsetResults(intercept, scale, xPos, array, count);
    380 }
    381 
    382 void SkGlyphCache::dump() const {
    383     const SkTypeface* face = fScalerContext->getTypeface();
    384     const SkScalerContextRec& rec = fScalerContext->getRec();
    385     SkMatrix matrix;
    386     rec.getSingleMatrix(&matrix);
    387     matrix.preScale(SkScalarInvert(rec.fTextSize), SkScalarInvert(rec.fTextSize));
    388     SkString name;
    389     face->getFamilyName(&name);
    390 
    391     SkString msg;
    392     msg.printf("cache typeface:%x %25s:%d size:%2g [%g %g %g %g] lum:%02X devG:%d pntG:%d cntr:%d glyphs:%3d",
    393                face->uniqueID(), name.c_str(), face->style(), rec.fTextSize,
    394                matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX],
    395                matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY],
    396                rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast,
    397                fGlyphMap.count());
    398     SkDebugf("%s\n", msg.c_str());
    399 }
    400 
    401 ///////////////////////////////////////////////////////////////////////////////
    402 ///////////////////////////////////////////////////////////////////////////////
    403 
    404 size_t SkGlyphCache_Globals::getTotalMemoryUsed() const {
    405     SkAutoExclusive ac(fLock);
    406     return fTotalMemoryUsed;
    407 }
    408 
    409 int SkGlyphCache_Globals::getCacheCountUsed() const {
    410     SkAutoExclusive ac(fLock);
    411     return fCacheCount;
    412 }
    413 
    414 int SkGlyphCache_Globals::getCacheCountLimit() const {
    415     SkAutoExclusive ac(fLock);
    416     return fCacheCountLimit;
    417 }
    418 
    419 size_t SkGlyphCache_Globals::setCacheSizeLimit(size_t newLimit) {
    420     static const size_t minLimit = 256 * 1024;
    421     if (newLimit < minLimit) {
    422         newLimit = minLimit;
    423     }
    424 
    425     SkAutoExclusive ac(fLock);
    426 
    427     size_t prevLimit = fCacheSizeLimit;
    428     fCacheSizeLimit = newLimit;
    429     this->internalPurge();
    430     return prevLimit;
    431 }
    432 
    433 size_t  SkGlyphCache_Globals::getCacheSizeLimit() const {
    434     SkAutoExclusive ac(fLock);
    435     return fCacheSizeLimit;
    436 }
    437 
    438 int SkGlyphCache_Globals::setCacheCountLimit(int newCount) {
    439     if (newCount < 0) {
    440         newCount = 0;
    441     }
    442 
    443     SkAutoExclusive ac(fLock);
    444 
    445     int prevCount = fCacheCountLimit;
    446     fCacheCountLimit = newCount;
    447     this->internalPurge();
    448     return prevCount;
    449 }
    450 
    451 int SkGlyphCache_Globals::getCachePointSizeLimit() const {
    452     SkAutoExclusive ac(fLock);
    453     return fPointSizeLimit;
    454 }
    455 
    456 int SkGlyphCache_Globals::setCachePointSizeLimit(int newLimit) {
    457     if (newLimit < 0) {
    458         newLimit = 0;
    459     }
    460 
    461     SkAutoExclusive ac(fLock);
    462 
    463     int prevLimit = fPointSizeLimit;
    464     fPointSizeLimit = newLimit;
    465     return prevLimit;
    466 }
    467 
    468 void SkGlyphCache_Globals::purgeAll() {
    469     SkAutoExclusive ac(fLock);
    470     this->internalPurge(fTotalMemoryUsed);
    471 }
    472 
    473 /*  This guy calls the visitor from within the mutext lock, so the visitor
    474     cannot:
    475     - take too much time
    476     - try to acquire the mutext again
    477     - call a fontscaler (which might call into the cache)
    478 */
    479 SkGlyphCache* SkGlyphCache::VisitCache(SkTypeface* typeface,
    480                                        const SkScalerContextEffects& effects,
    481                                        const SkDescriptor* desc,
    482                                        bool (*proc)(const SkGlyphCache*, void*),
    483                                        void* context) {
    484     if (!typeface) {
    485         typeface = SkTypeface::GetDefaultTypeface();
    486     }
    487     SkASSERT(desc);
    488 
    489     // Precondition: the typeface id must be the fFontID in the descriptor
    490     SkDEBUGCODE(
    491         uint32_t length = 0;
    492         const SkScalerContext::Rec* rec = static_cast<const SkScalerContext::Rec*>(
    493             desc->findEntry(kRec_SkDescriptorTag, &length));
    494         SkASSERT(rec);
    495         SkASSERT(length == sizeof(*rec));
    496         SkASSERT(typeface->uniqueID() == rec->fFontID);
    497     )
    498 
    499     SkGlyphCache_Globals& globals = get_globals();
    500     SkGlyphCache*         cache;
    501 
    502     {
    503         SkAutoExclusive ac(globals.fLock);
    504 
    505         globals.validate();
    506 
    507         for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
    508             if (*cache->fDesc == *desc) {
    509                 globals.internalDetachCache(cache);
    510                 if (!proc(cache, context)) {
    511                     globals.internalAttachCacheToHead(cache);
    512                     cache = nullptr;
    513                 }
    514                 return cache;
    515             }
    516         }
    517     }
    518 
    519     // Check if we can create a scaler-context before creating the glyphcache.
    520     // If not, we may have exhausted OS/font resources, so try purging the
    521     // cache once and try again.
    522     {
    523         // pass true the first time, to notice if the scalercontext failed,
    524         // so we can try the purge.
    525         std::unique_ptr<SkScalerContext> ctx = typeface->createScalerContext(effects, desc, true);
    526         if (!ctx) {
    527             get_globals().purgeAll();
    528             ctx = typeface->createScalerContext(effects, desc, false);
    529             SkASSERT(ctx);
    530         }
    531         cache = new SkGlyphCache(desc, std::move(ctx));
    532     }
    533 
    534     AutoValidate av(cache);
    535 
    536     if (!proc(cache, context)) {   // need to reattach
    537         globals.attachCacheToHead(cache);
    538         cache = nullptr;
    539     }
    540     return cache;
    541 }
    542 
    543 void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
    544     SkASSERT(cache);
    545     SkASSERT(cache->fNext == nullptr);
    546 
    547     get_globals().attachCacheToHead(cache);
    548 }
    549 
    550 static void dump_visitor(const SkGlyphCache& cache, void* context) {
    551     int* counter = (int*)context;
    552     int index = *counter;
    553     *counter += 1;
    554 
    555     const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
    556 
    557     SkDebugf("[%3d] ID %3d, glyphs %3d, size %g, scale %g, skew %g, [%g %g %g %g]\n",
    558              index, rec.fFontID, cache.countCachedGlyphs(),
    559              rec.fTextSize, rec.fPreScaleX, rec.fPreSkewX,
    560              rec.fPost2x2[0][0], rec.fPost2x2[0][1], rec.fPost2x2[1][0], rec.fPost2x2[1][1]);
    561 }
    562 
    563 void SkGlyphCache::Dump() {
    564     SkDebugf("GlyphCache [     used    budget ]\n");
    565     SkDebugf("    bytes  [ %8zu  %8zu ]\n",
    566              SkGraphics::GetFontCacheUsed(), SkGraphics::GetFontCacheLimit());
    567     SkDebugf("    count  [ %8zu  %8zu ]\n",
    568              SkGraphics::GetFontCacheCountUsed(), SkGraphics::GetFontCacheCountLimit());
    569 
    570     int counter = 0;
    571     SkGlyphCache::VisitAll(dump_visitor, &counter);
    572 }
    573 
    574 static void sk_trace_dump_visitor(const SkGlyphCache& cache, void* context) {
    575     SkTraceMemoryDump* dump = static_cast<SkTraceMemoryDump*>(context);
    576 
    577     const SkTypeface* face = cache.getScalerContext()->getTypeface();
    578     const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
    579 
    580     SkString fontName;
    581     face->getFamilyName(&fontName);
    582     // Replace all special characters with '_'.
    583     for (size_t index = 0; index < fontName.size(); ++index) {
    584         if (!std::isalnum(fontName[index])) {
    585             fontName[index] = '_';
    586         }
    587     }
    588 
    589     SkString dumpName = SkStringPrintf("%s/%s_%d/%p",
    590                                        gGlyphCacheDumpName, fontName.c_str(), rec.fFontID, &cache);
    591 
    592     dump->dumpNumericValue(dumpName.c_str(), "size", "bytes", cache.getMemoryUsed());
    593     dump->dumpNumericValue(dumpName.c_str(), "glyph_count", "objects", cache.countCachedGlyphs());
    594     dump->setMemoryBacking(dumpName.c_str(), "malloc", nullptr);
    595 }
    596 
    597 void SkGlyphCache::DumpMemoryStatistics(SkTraceMemoryDump* dump) {
    598     dump->dumpNumericValue(gGlyphCacheDumpName, "size", "bytes", SkGraphics::GetFontCacheUsed());
    599     dump->dumpNumericValue(gGlyphCacheDumpName, "budget_size", "bytes",
    600                            SkGraphics::GetFontCacheLimit());
    601     dump->dumpNumericValue(gGlyphCacheDumpName, "glyph_count", "objects",
    602                            SkGraphics::GetFontCacheCountUsed());
    603     dump->dumpNumericValue(gGlyphCacheDumpName, "budget_glyph_count", "objects",
    604                            SkGraphics::GetFontCacheCountLimit());
    605 
    606     if (dump->getRequestedDetails() == SkTraceMemoryDump::kLight_LevelOfDetail) {
    607         dump->setMemoryBacking(gGlyphCacheDumpName, "malloc", nullptr);
    608         return;
    609     }
    610 
    611     SkGlyphCache::VisitAll(sk_trace_dump_visitor, dump);
    612 }
    613 
    614 void SkGlyphCache::VisitAll(Visitor visitor, void* context) {
    615     SkGlyphCache_Globals& globals = get_globals();
    616     SkAutoExclusive ac(globals.fLock);
    617     SkGlyphCache*         cache;
    618 
    619     globals.validate();
    620 
    621     for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
    622         visitor(*cache, context);
    623     }
    624 }
    625 
    626 ///////////////////////////////////////////////////////////////////////////////
    627 
    628 void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
    629     SkAutoExclusive ac(fLock);
    630 
    631     this->validate();
    632     cache->validate();
    633 
    634     this->internalAttachCacheToHead(cache);
    635     this->internalPurge();
    636 }
    637 
    638 SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const {
    639     SkGlyphCache* cache = fHead;
    640     if (cache) {
    641         while (cache->fNext) {
    642             cache = cache->fNext;
    643         }
    644     }
    645     return cache;
    646 }
    647 
    648 size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
    649     this->validate();
    650 
    651     size_t bytesNeeded = 0;
    652     if (fTotalMemoryUsed > fCacheSizeLimit) {
    653         bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit;
    654     }
    655     bytesNeeded = SkTMax(bytesNeeded, minBytesNeeded);
    656     if (bytesNeeded) {
    657         // no small purges!
    658         bytesNeeded = SkTMax(bytesNeeded, fTotalMemoryUsed >> 2);
    659     }
    660 
    661     int countNeeded = 0;
    662     if (fCacheCount > fCacheCountLimit) {
    663         countNeeded = fCacheCount - fCacheCountLimit;
    664         // no small purges!
    665         countNeeded = SkMax32(countNeeded, fCacheCount >> 2);
    666     }
    667 
    668     // early exit
    669     if (!countNeeded && !bytesNeeded) {
    670         return 0;
    671     }
    672 
    673     size_t  bytesFreed = 0;
    674     int     countFreed = 0;
    675 
    676     // we start at the tail and proceed backwards, as the linklist is in LRU
    677     // order, with unimportant entries at the tail.
    678     SkGlyphCache* cache = this->internalGetTail();
    679     while (cache != nullptr &&
    680            (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
    681         SkGlyphCache* prev = cache->fPrev;
    682         bytesFreed += cache->fMemoryUsed;
    683         countFreed += 1;
    684 
    685         this->internalDetachCache(cache);
    686         delete cache;
    687         cache = prev;
    688     }
    689 
    690     this->validate();
    691 
    692 #ifdef SPEW_PURGE_STATUS
    693     if (countFreed) {
    694         SkDebugf("purging %dK from font cache [%d entries]\n",
    695                  (int)(bytesFreed >> 10), countFreed);
    696     }
    697 #endif
    698 
    699     return bytesFreed;
    700 }
    701 
    702 void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) {
    703     SkASSERT(nullptr == cache->fPrev && nullptr == cache->fNext);
    704     if (fHead) {
    705         fHead->fPrev = cache;
    706         cache->fNext = fHead;
    707     }
    708     fHead = cache;
    709 
    710     fCacheCount += 1;
    711     fTotalMemoryUsed += cache->fMemoryUsed;
    712 }
    713 
    714 void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
    715     SkASSERT(fCacheCount > 0);
    716     fCacheCount -= 1;
    717     fTotalMemoryUsed -= cache->fMemoryUsed;
    718 
    719     if (cache->fPrev) {
    720         cache->fPrev->fNext = cache->fNext;
    721     } else {
    722         fHead = cache->fNext;
    723     }
    724     if (cache->fNext) {
    725         cache->fNext->fPrev = cache->fPrev;
    726     }
    727     cache->fPrev = cache->fNext = nullptr;
    728 }
    729 
    730 ///////////////////////////////////////////////////////////////////////////////
    731 
    732 #ifdef SK_DEBUG
    733 
    734 void SkGlyphCache::validate() const {
    735 #ifdef SK_DEBUG_GLYPH_CACHE
    736     int count = fGlyphArray.count();
    737     for (int i = 0; i < count; i++) {
    738         const SkGlyph* glyph = &fGlyphArray[i];
    739         SkASSERT(glyph);
    740         if (glyph->fImage) {
    741             SkASSERT(fGlyphAlloc.contains(glyph->fImage));
    742         }
    743     }
    744 #endif
    745 }
    746 
    747 void SkGlyphCache_Globals::validate() const {
    748     size_t computedBytes = 0;
    749     int computedCount = 0;
    750 
    751     const SkGlyphCache* head = fHead;
    752     while (head != nullptr) {
    753         computedBytes += head->fMemoryUsed;
    754         computedCount += 1;
    755         head = head->fNext;
    756     }
    757 
    758     SkASSERTF(fCacheCount == computedCount, "fCacheCount: %d, computedCount: %d", fCacheCount,
    759               computedCount);
    760     SkASSERTF(fTotalMemoryUsed == computedBytes, "fTotalMemoryUsed: %d, computedBytes: %d",
    761               fTotalMemoryUsed, computedBytes);
    762 }
    763 
    764 #endif
    765 
    766 ///////////////////////////////////////////////////////////////////////////////
    767 ///////////////////////////////////////////////////////////////////////////////
    768 
    769 #include "SkTypefaceCache.h"
    770 
    771 size_t SkGraphics::GetFontCacheLimit() {
    772     return get_globals().getCacheSizeLimit();
    773 }
    774 
    775 size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
    776     return get_globals().setCacheSizeLimit(bytes);
    777 }
    778 
    779 size_t SkGraphics::GetFontCacheUsed() {
    780     return get_globals().getTotalMemoryUsed();
    781 }
    782 
    783 int SkGraphics::GetFontCacheCountLimit() {
    784     return get_globals().getCacheCountLimit();
    785 }
    786 
    787 int SkGraphics::SetFontCacheCountLimit(int count) {
    788     return get_globals().setCacheCountLimit(count);
    789 }
    790 
    791 int SkGraphics::GetFontCacheCountUsed() {
    792     return get_globals().getCacheCountUsed();
    793 }
    794 
    795 int SkGraphics::GetFontCachePointSizeLimit() {
    796     return get_globals().getCachePointSizeLimit();
    797 }
    798 
    799 int SkGraphics::SetFontCachePointSizeLimit(int limit) {
    800     return get_globals().setCachePointSizeLimit(limit);
    801 }
    802 
    803 void SkGraphics::PurgeFontCache() {
    804     get_globals().purgeAll();
    805     SkTypefaceCache::PurgeAll();
    806 }
    807 
    808 // TODO(herb): clean up TLS apis.
    809 size_t SkGraphics::GetTLSFontCacheLimit() { return 0; }
    810 void SkGraphics::SetTLSFontCacheLimit(size_t bytes) { }
    811