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[2], 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[3], 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 void SkGlyphCache_Globals::purgeAll() {
    452     SkAutoExclusive ac(fLock);
    453     this->internalPurge(fTotalMemoryUsed);
    454 }
    455 
    456 /*  This guy calls the visitor from within the mutext lock, so the visitor
    457     cannot:
    458     - take too much time
    459     - try to acquire the mutext again
    460     - call a fontscaler (which might call into the cache)
    461 */
    462 SkGlyphCache* SkGlyphCache::VisitCache(SkTypeface* typeface,
    463                                        const SkScalerContextEffects& effects,
    464                                        const SkDescriptor* desc,
    465                                        bool (*proc)(const SkGlyphCache*, void*),
    466                                        void* context) {
    467     if (!typeface) {
    468         typeface = SkTypeface::GetDefaultTypeface();
    469     }
    470     SkASSERT(desc);
    471 
    472     // Precondition: the typeface id must be the fFontID in the descriptor
    473     SkDEBUGCODE(
    474         uint32_t length = 0;
    475         const SkScalerContext::Rec* rec = static_cast<const SkScalerContext::Rec*>(
    476             desc->findEntry(kRec_SkDescriptorTag, &length));
    477         SkASSERT(rec);
    478         SkASSERT(length == sizeof(*rec));
    479         SkASSERT(typeface->uniqueID() == rec->fFontID);
    480     )
    481 
    482     SkGlyphCache_Globals& globals = get_globals();
    483     SkGlyphCache*         cache;
    484 
    485     {
    486         SkAutoExclusive ac(globals.fLock);
    487 
    488         globals.validate();
    489 
    490         for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
    491             if (*cache->fDesc == *desc) {
    492                 globals.internalDetachCache(cache);
    493                 if (!proc(cache, context)) {
    494                     globals.internalAttachCacheToHead(cache);
    495                     cache = nullptr;
    496                 }
    497                 return cache;
    498             }
    499         }
    500     }
    501 
    502     // Check if we can create a scaler-context before creating the glyphcache.
    503     // If not, we may have exhausted OS/font resources, so try purging the
    504     // cache once and try again.
    505     {
    506         // pass true the first time, to notice if the scalercontext failed,
    507         // so we can try the purge.
    508         std::unique_ptr<SkScalerContext> ctx = typeface->createScalerContext(effects, desc, true);
    509         if (!ctx) {
    510             get_globals().purgeAll();
    511             ctx = typeface->createScalerContext(effects, desc, false);
    512             SkASSERT(ctx);
    513         }
    514         cache = new SkGlyphCache(desc, std::move(ctx));
    515     }
    516 
    517     AutoValidate av(cache);
    518 
    519     if (!proc(cache, context)) {   // need to reattach
    520         globals.attachCacheToHead(cache);
    521         cache = nullptr;
    522     }
    523     return cache;
    524 }
    525 
    526 void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
    527     SkASSERT(cache);
    528     SkASSERT(cache->fNext == nullptr);
    529 
    530     get_globals().attachCacheToHead(cache);
    531 }
    532 
    533 static void dump_visitor(const SkGlyphCache& cache, void* context) {
    534     int* counter = (int*)context;
    535     int index = *counter;
    536     *counter += 1;
    537 
    538     const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
    539 
    540     SkDebugf("[%3d] ID %3d, glyphs %3d, size %g, scale %g, skew %g, [%g %g %g %g]\n",
    541              index, rec.fFontID, cache.countCachedGlyphs(),
    542              rec.fTextSize, rec.fPreScaleX, rec.fPreSkewX,
    543              rec.fPost2x2[0][0], rec.fPost2x2[0][1], rec.fPost2x2[1][0], rec.fPost2x2[1][1]);
    544 }
    545 
    546 void SkGlyphCache::Dump() {
    547     SkDebugf("GlyphCache [     used    budget ]\n");
    548     SkDebugf("    bytes  [ %8zu  %8zu ]\n",
    549              SkGraphics::GetFontCacheUsed(), SkGraphics::GetFontCacheLimit());
    550     SkDebugf("    count  [ %8zu  %8zu ]\n",
    551              SkGraphics::GetFontCacheCountUsed(), SkGraphics::GetFontCacheCountLimit());
    552 
    553     int counter = 0;
    554     SkGlyphCache::VisitAll(dump_visitor, &counter);
    555 }
    556 
    557 static void sk_trace_dump_visitor(const SkGlyphCache& cache, void* context) {
    558     SkTraceMemoryDump* dump = static_cast<SkTraceMemoryDump*>(context);
    559 
    560     const SkTypeface* face = cache.getScalerContext()->getTypeface();
    561     const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
    562 
    563     SkString fontName;
    564     face->getFamilyName(&fontName);
    565     // Replace all special characters with '_'.
    566     for (size_t index = 0; index < fontName.size(); ++index) {
    567         if (!std::isalnum(fontName[index])) {
    568             fontName[index] = '_';
    569         }
    570     }
    571 
    572     SkString dumpName = SkStringPrintf("%s/%s_%d/%p",
    573                                        gGlyphCacheDumpName, fontName.c_str(), rec.fFontID, &cache);
    574 
    575     dump->dumpNumericValue(dumpName.c_str(), "size", "bytes", cache.getMemoryUsed());
    576     dump->dumpNumericValue(dumpName.c_str(), "glyph_count", "objects", cache.countCachedGlyphs());
    577     dump->setMemoryBacking(dumpName.c_str(), "malloc", nullptr);
    578 }
    579 
    580 void SkGlyphCache::DumpMemoryStatistics(SkTraceMemoryDump* dump) {
    581     dump->dumpNumericValue(gGlyphCacheDumpName, "size", "bytes", SkGraphics::GetFontCacheUsed());
    582     dump->dumpNumericValue(gGlyphCacheDumpName, "budget_size", "bytes",
    583                            SkGraphics::GetFontCacheLimit());
    584     dump->dumpNumericValue(gGlyphCacheDumpName, "glyph_count", "objects",
    585                            SkGraphics::GetFontCacheCountUsed());
    586     dump->dumpNumericValue(gGlyphCacheDumpName, "budget_glyph_count", "objects",
    587                            SkGraphics::GetFontCacheCountLimit());
    588 
    589     if (dump->getRequestedDetails() == SkTraceMemoryDump::kLight_LevelOfDetail) {
    590         dump->setMemoryBacking(gGlyphCacheDumpName, "malloc", nullptr);
    591         return;
    592     }
    593 
    594     SkGlyphCache::VisitAll(sk_trace_dump_visitor, dump);
    595 }
    596 
    597 void SkGlyphCache::VisitAll(Visitor visitor, void* context) {
    598     SkGlyphCache_Globals& globals = get_globals();
    599     SkAutoExclusive ac(globals.fLock);
    600     SkGlyphCache*         cache;
    601 
    602     globals.validate();
    603 
    604     for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
    605         visitor(*cache, context);
    606     }
    607 }
    608 
    609 ///////////////////////////////////////////////////////////////////////////////
    610 
    611 void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
    612     SkAutoExclusive ac(fLock);
    613 
    614     this->validate();
    615     cache->validate();
    616 
    617     this->internalAttachCacheToHead(cache);
    618     this->internalPurge();
    619 }
    620 
    621 SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const {
    622     SkGlyphCache* cache = fHead;
    623     if (cache) {
    624         while (cache->fNext) {
    625             cache = cache->fNext;
    626         }
    627     }
    628     return cache;
    629 }
    630 
    631 size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
    632     this->validate();
    633 
    634     size_t bytesNeeded = 0;
    635     if (fTotalMemoryUsed > fCacheSizeLimit) {
    636         bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit;
    637     }
    638     bytesNeeded = SkTMax(bytesNeeded, minBytesNeeded);
    639     if (bytesNeeded) {
    640         // no small purges!
    641         bytesNeeded = SkTMax(bytesNeeded, fTotalMemoryUsed >> 2);
    642     }
    643 
    644     int countNeeded = 0;
    645     if (fCacheCount > fCacheCountLimit) {
    646         countNeeded = fCacheCount - fCacheCountLimit;
    647         // no small purges!
    648         countNeeded = SkMax32(countNeeded, fCacheCount >> 2);
    649     }
    650 
    651     // early exit
    652     if (!countNeeded && !bytesNeeded) {
    653         return 0;
    654     }
    655 
    656     size_t  bytesFreed = 0;
    657     int     countFreed = 0;
    658 
    659     // we start at the tail and proceed backwards, as the linklist is in LRU
    660     // order, with unimportant entries at the tail.
    661     SkGlyphCache* cache = this->internalGetTail();
    662     while (cache != nullptr &&
    663            (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
    664         SkGlyphCache* prev = cache->fPrev;
    665         bytesFreed += cache->fMemoryUsed;
    666         countFreed += 1;
    667 
    668         this->internalDetachCache(cache);
    669         delete cache;
    670         cache = prev;
    671     }
    672 
    673     this->validate();
    674 
    675 #ifdef SPEW_PURGE_STATUS
    676     if (countFreed) {
    677         SkDebugf("purging %dK from font cache [%d entries]\n",
    678                  (int)(bytesFreed >> 10), countFreed);
    679     }
    680 #endif
    681 
    682     return bytesFreed;
    683 }
    684 
    685 void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) {
    686     SkASSERT(nullptr == cache->fPrev && nullptr == cache->fNext);
    687     if (fHead) {
    688         fHead->fPrev = cache;
    689         cache->fNext = fHead;
    690     }
    691     fHead = cache;
    692 
    693     fCacheCount += 1;
    694     fTotalMemoryUsed += cache->fMemoryUsed;
    695 }
    696 
    697 void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
    698     SkASSERT(fCacheCount > 0);
    699     fCacheCount -= 1;
    700     fTotalMemoryUsed -= cache->fMemoryUsed;
    701 
    702     if (cache->fPrev) {
    703         cache->fPrev->fNext = cache->fNext;
    704     } else {
    705         fHead = cache->fNext;
    706     }
    707     if (cache->fNext) {
    708         cache->fNext->fPrev = cache->fPrev;
    709     }
    710     cache->fPrev = cache->fNext = nullptr;
    711 }
    712 
    713 ///////////////////////////////////////////////////////////////////////////////
    714 
    715 #ifdef SK_DEBUG
    716 
    717 void SkGlyphCache::validate() const {
    718 #ifdef SK_DEBUG_GLYPH_CACHE
    719     int count = fGlyphArray.count();
    720     for (int i = 0; i < count; i++) {
    721         const SkGlyph* glyph = &fGlyphArray[i];
    722         SkASSERT(glyph);
    723         if (glyph->fImage) {
    724             SkASSERT(fGlyphAlloc.contains(glyph->fImage));
    725         }
    726     }
    727 #endif
    728 }
    729 
    730 void SkGlyphCache_Globals::validate() const {
    731     size_t computedBytes = 0;
    732     int computedCount = 0;
    733 
    734     const SkGlyphCache* head = fHead;
    735     while (head != nullptr) {
    736         computedBytes += head->fMemoryUsed;
    737         computedCount += 1;
    738         head = head->fNext;
    739     }
    740 
    741     SkASSERTF(fCacheCount == computedCount, "fCacheCount: %d, computedCount: %d", fCacheCount,
    742               computedCount);
    743     SkASSERTF(fTotalMemoryUsed == computedBytes, "fTotalMemoryUsed: %d, computedBytes: %d",
    744               fTotalMemoryUsed, computedBytes);
    745 }
    746 
    747 #endif
    748 
    749 ///////////////////////////////////////////////////////////////////////////////
    750 ///////////////////////////////////////////////////////////////////////////////
    751 
    752 #include "SkTypefaceCache.h"
    753 
    754 size_t SkGraphics::GetFontCacheLimit() {
    755     return get_globals().getCacheSizeLimit();
    756 }
    757 
    758 size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
    759     return get_globals().setCacheSizeLimit(bytes);
    760 }
    761 
    762 size_t SkGraphics::GetFontCacheUsed() {
    763     return get_globals().getTotalMemoryUsed();
    764 }
    765 
    766 int SkGraphics::GetFontCacheCountLimit() {
    767     return get_globals().getCacheCountLimit();
    768 }
    769 
    770 int SkGraphics::SetFontCacheCountLimit(int count) {
    771     return get_globals().setCacheCountLimit(count);
    772 }
    773 
    774 int SkGraphics::GetFontCacheCountUsed() {
    775     return get_globals().getCacheCountUsed();
    776 }
    777 
    778 void SkGraphics::PurgeFontCache() {
    779     get_globals().purgeAll();
    780     SkTypefaceCache::PurgeAll();
    781 }
    782 
    783 // TODO(herb): clean up TLS apis.
    784 size_t SkGraphics::GetTLSFontCacheLimit() { return 0; }
    785 void SkGraphics::SetTLSFontCacheLimit(size_t bytes) { }
    786