The font cache evicts inactive font data too aggressively when not under memory pressure
[WebKit-https.git] / Source / WebCore / platform / graphics / FontCache.cpp
1 /*
2  * Copyright (C) 2006, 2008 Apple Inc. All rights reserved.
3  * Copyright (C) 2007 Nicholas Shanks <webkit@nickshanks.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1.  Redistributions of source code must retain the above copyright
10  *     notice, this list of conditions and the following disclaimer. 
11  * 2.  Redistributions in binary form must reproduce the above copyright
12  *     notice, this list of conditions and the following disclaimer in the
13  *     documentation and/or other materials provided with the distribution. 
14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15  *     its contributors may be used to endorse or promote products derived
16  *     from this software without specific prior written permission. 
17  *
18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #include "config.h"
31 #include "FontCache.h"
32
33 #include "Font.h"
34 #include "FontFallbackList.h"
35 #include "FontPlatformData.h"
36 #include "FontSelector.h"
37 #include "OpenTypeVerticalData.h"
38 #include "WebKitFontFamilyNames.h"
39 #include <wtf/HashMap.h>
40 #include <wtf/ListHashSet.h>
41 #include <wtf/StdLibExtras.h>
42 #include <wtf/text/AtomicStringHash.h>
43 #include <wtf/text/StringHash.h>
44
45 using namespace WTF;
46
47 namespace WebCore {
48
49 FontCache* fontCache()
50 {
51     DEFINE_STATIC_LOCAL(FontCache, globalFontCache, ());
52     return &globalFontCache;
53 }
54
55 FontCache::FontCache()
56     : m_purgePreventCount(0)
57 {
58 }
59
60 struct FontPlatformDataCacheKey {
61     WTF_MAKE_FAST_ALLOCATED;
62 public:
63     FontPlatformDataCacheKey(const AtomicString& family = AtomicString(), unsigned size = 0, unsigned weight = 0, bool italic = false,
64                              bool isPrinterFont = false, FontRenderingMode renderingMode = NormalRenderingMode, FontOrientation orientation = Horizontal,
65                              TextOrientation textOrientation = TextOrientationVerticalRight, FontWidthVariant widthVariant = RegularWidth)
66         : m_size(size)
67         , m_weight(weight)
68         , m_family(family)
69         , m_italic(italic)
70         , m_printerFont(isPrinterFont)
71         , m_renderingMode(renderingMode)
72         , m_orientation(orientation)
73         , m_textOrientation(textOrientation)
74         , m_widthVariant(widthVariant)
75     {
76     }
77
78     FontPlatformDataCacheKey(HashTableDeletedValueType) : m_size(hashTableDeletedSize()) { }
79     bool isHashTableDeletedValue() const { return m_size == hashTableDeletedSize(); }
80
81     bool operator==(const FontPlatformDataCacheKey& other) const
82     {
83         return equalIgnoringCase(m_family, other.m_family) && m_size == other.m_size && 
84                m_weight == other.m_weight && m_italic == other.m_italic && m_printerFont == other.m_printerFont &&
85                m_renderingMode == other.m_renderingMode && m_orientation == other.m_orientation && m_textOrientation == other.m_textOrientation && m_widthVariant == other.m_widthVariant;
86     }
87
88     unsigned m_size;
89     unsigned m_weight;
90     AtomicString m_family;
91     bool m_italic;
92     bool m_printerFont;
93     FontRenderingMode m_renderingMode;
94     FontOrientation m_orientation;
95     TextOrientation m_textOrientation;
96     FontWidthVariant m_widthVariant;
97
98 private:
99     static unsigned hashTableDeletedSize() { return 0xFFFFFFFFU; }
100 };
101
102 inline unsigned computeHash(const FontPlatformDataCacheKey& fontKey)
103 {
104     unsigned hashCodes[5] = {
105         CaseFoldingHash::hash(fontKey.m_family),
106         fontKey.m_size,
107         fontKey.m_weight,
108         fontKey.m_widthVariant,
109         static_cast<unsigned>(fontKey.m_textOrientation) << 4 | static_cast<unsigned>(fontKey.m_orientation) << 3 | static_cast<unsigned>(fontKey.m_italic) << 2 | static_cast<unsigned>(fontKey.m_printerFont) << 1 | static_cast<unsigned>(fontKey.m_renderingMode)
110     };
111     return StringHasher::hashMemory<sizeof(hashCodes)>(hashCodes);
112 }
113
114 struct FontPlatformDataCacheKeyHash {
115     static unsigned hash(const FontPlatformDataCacheKey& font)
116     {
117         return computeHash(font);
118     }
119          
120     static bool equal(const FontPlatformDataCacheKey& a, const FontPlatformDataCacheKey& b)
121     {
122         return a == b;
123     }
124
125     static const bool safeToCompareToEmptyOrDeleted = true;
126 };
127
128 struct FontPlatformDataCacheKeyTraits : WTF::SimpleClassHashTraits<FontPlatformDataCacheKey> { };
129
130 typedef HashMap<FontPlatformDataCacheKey, FontPlatformData*, FontPlatformDataCacheKeyHash, FontPlatformDataCacheKeyTraits> FontPlatformDataCache;
131
132 static FontPlatformDataCache* gFontPlatformDataCache = 0;
133
134 static const AtomicString& alternateFamilyName(const AtomicString& familyName)
135 {
136     // Alias Courier <-> Courier New
137     DEFINE_STATIC_LOCAL(AtomicString, courier, ("Courier"));
138     DEFINE_STATIC_LOCAL(AtomicString, courierNew, ("Courier New"));
139     if (equalIgnoringCase(familyName, courier))
140         return courierNew;
141 #if !OS(WINDOWS)
142     // On Windows, Courier New (truetype font) is always present and
143     // Courier is a bitmap font. So, we don't want to map Courier New to
144     // Courier.
145     if (equalIgnoringCase(familyName, courierNew))
146         return courier;
147 #endif
148
149     // Alias Times and Times New Roman.
150     DEFINE_STATIC_LOCAL(AtomicString, times, ("Times"));
151     DEFINE_STATIC_LOCAL(AtomicString, timesNewRoman, ("Times New Roman"));
152     if (equalIgnoringCase(familyName, times))
153         return timesNewRoman;
154     if (equalIgnoringCase(familyName, timesNewRoman))
155         return times;
156     
157     // Alias Arial and Helvetica
158     DEFINE_STATIC_LOCAL(AtomicString, arial, ("Arial"));
159     DEFINE_STATIC_LOCAL(AtomicString, helvetica, ("Helvetica"));
160     if (equalIgnoringCase(familyName, arial))
161         return helvetica;
162     if (equalIgnoringCase(familyName, helvetica))
163         return arial;
164
165 #if OS(WINDOWS)
166     // On Windows, bitmap fonts are blocked altogether so that we have to 
167     // alias MS Sans Serif (bitmap font) -> Microsoft Sans Serif (truetype font)
168     DEFINE_STATIC_LOCAL(AtomicString, msSans, ("MS Sans Serif"));
169     DEFINE_STATIC_LOCAL(AtomicString, microsoftSans, ("Microsoft Sans Serif"));
170     if (equalIgnoringCase(familyName, msSans))
171         return microsoftSans;
172
173     // Alias MS Serif (bitmap) -> Times New Roman (truetype font). There's no 
174     // 'Microsoft Sans Serif-equivalent' for Serif. 
175     static AtomicString msSerif("MS Serif");
176     if (equalIgnoringCase(familyName, msSerif))
177         return timesNewRoman;
178 #endif
179
180     return emptyAtom;
181 }
182
183 FontPlatformData* FontCache::getCachedFontPlatformData(const FontDescription& fontDescription,
184                                                        const AtomicString& passedFamilyName,
185                                                        bool checkingAlternateName)
186 {
187 #if OS(WINDOWS) && ENABLE(OPENTYPE_VERTICAL)
188     // Leading "@" in the font name enables Windows vertical flow flag for the font.
189     // Because we do vertical flow by ourselves, we don't want to use the Windows feature.
190     // IE disregards "@" regardless of the orientatoin, so we follow the behavior.
191     const AtomicString& familyName = (passedFamilyName.isEmpty() || passedFamilyName[0] != '@') ?
192         passedFamilyName : AtomicString(passedFamilyName.impl()->substring(1));
193 #else
194     const AtomicString& familyName = passedFamilyName;
195 #endif
196
197     if (!gFontPlatformDataCache) {
198         gFontPlatformDataCache = new FontPlatformDataCache;
199         platformInit();
200     }
201
202     FontPlatformDataCacheKey key(familyName, fontDescription.computedPixelSize(), fontDescription.weight(), fontDescription.italic(),
203                                  fontDescription.usePrinterFont(), fontDescription.renderingMode(), fontDescription.orientation(),
204                                  fontDescription.textOrientation(), fontDescription.widthVariant());
205     FontPlatformData* result = 0;
206     bool foundResult;
207     FontPlatformDataCache::iterator it = gFontPlatformDataCache->find(key);
208     if (it == gFontPlatformDataCache->end()) {
209         result = createFontPlatformData(fontDescription, familyName);
210         gFontPlatformDataCache->set(key, result);
211         foundResult = result;
212     } else {
213         result = it->value;
214         foundResult = true;
215     }
216
217     if (!foundResult && !checkingAlternateName) {
218         // We were unable to find a font.  We have a small set of fonts that we alias to other names, 
219         // e.g., Arial/Helvetica, Courier/Courier New, etc.  Try looking up the font under the aliased name.
220         const AtomicString& alternateName = alternateFamilyName(familyName);
221         if (!alternateName.isEmpty())
222             result = getCachedFontPlatformData(fontDescription, alternateName, true);
223         if (result)
224             gFontPlatformDataCache->set(key, new FontPlatformData(*result)); // Cache the result under the old name.
225     }
226
227     return result;
228 }
229
230 #if ENABLE(OPENTYPE_VERTICAL)
231 typedef HashMap<FontCache::FontFileKey, OwnPtr<OpenTypeVerticalData>, WTF::IntHash<FontCache::FontFileKey>, WTF::UnsignedWithZeroKeyHashTraits<FontCache::FontFileKey> > FontVerticalDataCache;
232
233 FontVerticalDataCache& fontVerticalDataCacheInstance()
234 {
235     DEFINE_STATIC_LOCAL(FontVerticalDataCache, fontVerticalDataCache, ());
236     return fontVerticalDataCache;
237 }
238
239 OpenTypeVerticalData* FontCache::getVerticalData(const FontFileKey& key, const FontPlatformData& platformData)
240 {
241     FontVerticalDataCache& fontVerticalDataCache = fontVerticalDataCacheInstance();
242     FontVerticalDataCache::iterator result = fontVerticalDataCache.find(key);
243     if (result != fontVerticalDataCache.end())
244         return result.get()->value.get();
245
246     OpenTypeVerticalData* verticalData = new OpenTypeVerticalData(platformData);
247     if (!verticalData->isOpenType()) {
248         delete verticalData;
249         verticalData = 0; // Put 0 in cache to mark that this isn't an OpenType font.
250     }
251     fontVerticalDataCache.set(key, adoptPtr(verticalData));
252     return verticalData;
253 }
254 #endif
255
256 struct FontDataCacheKeyHash {
257     static unsigned hash(const FontPlatformData& platformData)
258     {
259         return platformData.hash();
260     }
261          
262     static bool equal(const FontPlatformData& a, const FontPlatformData& b)
263     {
264         return a == b;
265     }
266
267     static const bool safeToCompareToEmptyOrDeleted = true;
268 };
269
270 struct FontDataCacheKeyTraits : WTF::GenericHashTraits<FontPlatformData> {
271     static const bool emptyValueIsZero = true;
272     static const bool needsDestruction = true;
273     static const FontPlatformData& emptyValue()
274     {
275         DEFINE_STATIC_LOCAL(FontPlatformData, key, (0.f, false, false));
276         return key;
277     }
278     static void constructDeletedValue(FontPlatformData& slot)
279     {
280         new (NotNull, &slot) FontPlatformData(HashTableDeletedValue);
281     }
282     static bool isDeletedValue(const FontPlatformData& value)
283     {
284         return value.isHashTableDeletedValue();
285     }
286 };
287
288 typedef HashMap<FontPlatformData, pair<RefPtr<SimpleFontData>, unsigned>, FontDataCacheKeyHash, FontDataCacheKeyTraits> FontDataCache;
289
290 static FontDataCache* gFontDataCache = 0;
291
292 #if PLATFORM(CHROMIUM) && !OS(ANDROID)
293 const int cMaxInactiveFontData = 250;
294 const int cTargetInactiveFontData = 200;
295 #else
296 const int cMaxInactiveFontData = 225;
297 const int cTargetInactiveFontData = 200;
298 #endif
299 static ListHashSet<RefPtr<SimpleFontData> >* gInactiveFontData = 0;
300
301 PassRefPtr<SimpleFontData> FontCache::getCachedFontData(const FontDescription& fontDescription, const AtomicString& family, bool checkingAlternateName, ShouldRetain shouldRetain)
302 {
303     FontPlatformData* platformData = getCachedFontPlatformData(fontDescription, family, checkingAlternateName);
304     if (!platformData)
305         return 0;
306
307     return getCachedFontData(platformData, shouldRetain);
308 }
309
310 PassRefPtr<SimpleFontData> FontCache::getCachedFontData(const FontPlatformData* platformData, ShouldRetain shouldRetain)
311 {
312     if (!platformData)
313         return 0;
314
315 #if !ASSERT_DISABLED
316     if (shouldRetain == DoNotRetain)
317         ASSERT(m_purgePreventCount);
318 #endif
319
320     if (!gFontDataCache) {
321         gFontDataCache = new FontDataCache;
322         gInactiveFontData = new ListHashSet<RefPtr<SimpleFontData> >;
323     }
324
325     FontDataCache::iterator result = gFontDataCache->find(*platformData);
326     if (result == gFontDataCache->end()) {
327         pair<RefPtr<SimpleFontData>, unsigned> newValue(SimpleFontData::create(*platformData), shouldRetain == Retain ? 1 : 0);
328         gFontDataCache->set(*platformData, newValue);
329         if (shouldRetain == DoNotRetain)
330             gInactiveFontData->add(newValue.first);
331         return newValue.first.release();
332     }
333
334     if (!result.get()->value.second) {
335         ASSERT(gInactiveFontData->contains(result.get()->value.first));
336         gInactiveFontData->remove(result.get()->value.first);
337     }
338
339     if (shouldRetain == Retain)
340         result.get()->value.second++;
341     else if (!result.get()->value.second) {
342         // If shouldRetain is DoNotRetain and count is 0, we want to remove the fontData from 
343         // gInactiveFontData (above) and re-add here to update LRU position.
344         gInactiveFontData->add(result.get()->value.first);
345     }
346
347     return result.get()->value.first;
348 }
349
350 SimpleFontData* FontCache::getNonRetainedLastResortFallbackFont(const FontDescription& fontDescription)
351 {
352     return getLastResortFallbackFont(fontDescription, DoNotRetain).leakRef();
353 }
354
355 void FontCache::releaseFontData(const SimpleFontData* fontData)
356 {
357     ASSERT(gFontDataCache);
358     ASSERT(!fontData->isCustomFont());
359
360     FontDataCache::iterator it = gFontDataCache->find(fontData->platformData());
361     ASSERT(it != gFontDataCache->end());
362
363     ASSERT(it->value.second);
364     if (!--it->value.second)
365         gInactiveFontData->add(it->value.first);
366 }
367
368 void FontCache::purgeInactiveFontDataIfNeeded()
369 {
370     if (gInactiveFontData && !m_purgePreventCount && gInactiveFontData->size() > cMaxInactiveFontData)
371         purgeInactiveFontData(gInactiveFontData->size() - cTargetInactiveFontData);
372 }
373
374 void FontCache::purgeInactiveFontData(int count)
375 {
376     if (!gInactiveFontData || m_purgePreventCount)
377         return;
378
379     static bool isPurging;  // Guard against reentry when e.g. a deleted FontData releases its small caps FontData.
380     if (isPurging)
381         return;
382
383     isPurging = true;
384
385     Vector<RefPtr<SimpleFontData>, 20> fontDataToDelete;
386     ListHashSet<RefPtr<SimpleFontData> >::iterator end = gInactiveFontData->end();
387     ListHashSet<RefPtr<SimpleFontData> >::iterator it = gInactiveFontData->begin();
388     for (int i = 0; i < count && it != end; ++it, ++i) {
389         RefPtr<SimpleFontData>& fontData = *it.get();
390         gFontDataCache->remove(fontData->platformData());
391         // We should not delete SimpleFontData here because deletion can modify gInactiveFontData. See http://trac.webkit.org/changeset/44011
392         fontDataToDelete.append(fontData);
393     }
394
395     if (it == end) {
396         // Removed everything
397         gInactiveFontData->clear();
398     } else {
399         for (int i = 0; i < count; ++i)
400             gInactiveFontData->remove(gInactiveFontData->begin());
401     }
402
403     fontDataToDelete.clear();
404
405     if (gFontPlatformDataCache) {
406         Vector<FontPlatformDataCacheKey> keysToRemove;
407         keysToRemove.reserveInitialCapacity(gFontPlatformDataCache->size());
408         FontPlatformDataCache::iterator platformDataEnd = gFontPlatformDataCache->end();
409         for (FontPlatformDataCache::iterator platformData = gFontPlatformDataCache->begin(); platformData != platformDataEnd; ++platformData) {
410             if (platformData->value && !gFontDataCache->contains(*platformData->value))
411                 keysToRemove.append(platformData->key);
412         }
413         
414         size_t keysToRemoveCount = keysToRemove.size();
415         for (size_t i = 0; i < keysToRemoveCount; ++i)
416             delete gFontPlatformDataCache->take(keysToRemove[i]);
417     }
418
419 #if ENABLE(OPENTYPE_VERTICAL)
420     FontVerticalDataCache& fontVerticalDataCache = fontVerticalDataCacheInstance();
421     if (!fontVerticalDataCache.isEmpty()) {
422         // Mark & sweep unused verticalData
423         FontVerticalDataCache::iterator verticalDataEnd = fontVerticalDataCache.end();
424         for (FontVerticalDataCache::iterator verticalData = fontVerticalDataCache.begin(); verticalData != verticalDataEnd; ++verticalData) {
425             if (verticalData->value)
426                 verticalData->value->m_inFontCache = false;
427         }
428         FontDataCache::iterator fontDataEnd = gFontDataCache->end();
429         for (FontDataCache::iterator fontData = gFontDataCache->begin(); fontData != fontDataEnd; ++fontData) {
430             OpenTypeVerticalData* verticalData = const_cast<OpenTypeVerticalData*>(fontData->value.first->verticalData());
431             if (verticalData)
432                 verticalData->m_inFontCache = true;
433         }
434         Vector<FontFileKey> keysToRemove;
435         keysToRemove.reserveInitialCapacity(fontVerticalDataCache.size());
436         for (FontVerticalDataCache::iterator verticalData = fontVerticalDataCache.begin(); verticalData != verticalDataEnd; ++verticalData) {
437             if (!verticalData->value || !verticalData->value->m_inFontCache)
438                 keysToRemove.append(verticalData->key);
439         }
440         for (size_t i = 0, count = keysToRemove.size(); i < count; ++i)
441             fontVerticalDataCache.take(keysToRemove[i]);
442     }
443 #endif
444
445     isPurging = false;
446 }
447
448 size_t FontCache::fontDataCount()
449 {
450     if (gFontDataCache)
451         return gFontDataCache->size();
452     return 0;
453 }
454
455 size_t FontCache::inactiveFontDataCount()
456 {
457     if (gInactiveFontData)
458         return gInactiveFontData->size();
459     return 0;
460 }
461
462 PassRefPtr<FontData> FontCache::getFontData(const Font& font, int& familyIndex, FontSelector* fontSelector)
463 {
464     RefPtr<FontData> result;
465
466     int startIndex = familyIndex;
467     const FontFamily* startFamily = &font.fontDescription().family();
468     for (int i = 0; startFamily && i < startIndex; i++)
469         startFamily = startFamily->next();
470     const FontFamily* currFamily = startFamily;
471     while (currFamily && !result) {
472         familyIndex++;
473         if (currFamily->family().length()) {
474             if (fontSelector)
475                 result = fontSelector->getFontData(font.fontDescription(), currFamily->family());
476
477             if (!result)
478                 result = getCachedFontData(font.fontDescription(), currFamily->family());
479         }
480         currFamily = currFamily->next();
481     }
482
483     if (!currFamily)
484         familyIndex = cAllFamiliesScanned;
485
486     if (!result)
487         // We didn't find a font. Try to find a similar font using our own specific knowledge about our platform.
488         // For example on OS X, we know to map any families containing the words Arabic, Pashto, or Urdu to the
489         // Geeza Pro font.
490         result = getSimilarFontPlatformData(font);
491
492     if (!result && startIndex == 0) {
493         // If it's the primary font that we couldn't find, we try the following. In all other cases, we will
494         // just use per-character system fallback.
495
496         if (fontSelector) {
497             // Try the user's preferred standard font.
498             if (RefPtr<FontData> data = fontSelector->getFontData(font.fontDescription(), standardFamily))
499                 return data.release();
500         }
501
502         // Still no result.  Hand back our last resort fallback font.
503         result = getLastResortFallbackFont(font.fontDescription());
504     }
505     return result.release();
506 }
507
508 static HashSet<FontSelector*>* gClients;
509
510 void FontCache::addClient(FontSelector* client)
511 {
512     if (!gClients)
513         gClients = new HashSet<FontSelector*>;
514
515     ASSERT(!gClients->contains(client));
516     gClients->add(client);
517 }
518
519 void FontCache::removeClient(FontSelector* client)
520 {
521     ASSERT(gClients);
522     ASSERT(gClients->contains(client));
523
524     gClients->remove(client);
525 }
526
527 static unsigned short gGeneration = 0;
528
529 unsigned short FontCache::generation()
530 {
531     return gGeneration;
532 }
533
534 void FontCache::invalidate()
535 {
536     if (!gClients) {
537         ASSERT(!gFontPlatformDataCache);
538         return;
539     }
540
541     if (gFontPlatformDataCache) {
542         deleteAllValues(*gFontPlatformDataCache);
543         delete gFontPlatformDataCache;
544         gFontPlatformDataCache = new FontPlatformDataCache;
545     }
546
547     gGeneration++;
548
549     Vector<RefPtr<FontSelector> > clients;
550     size_t numClients = gClients->size();
551     clients.reserveInitialCapacity(numClients);
552     HashSet<FontSelector*>::iterator end = gClients->end();
553     for (HashSet<FontSelector*>::iterator it = gClients->begin(); it != end; ++it)
554         clients.append(*it);
555
556     ASSERT(numClients == clients.size());
557     for (size_t i = 0; i < numClients; ++i)
558         clients[i]->fontCacheInvalidated();
559
560     purgeInactiveFontData();
561 }
562
563 } // namespace WebCore