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