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