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