1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef MINIKIN_LAYOUT_CACHE_H
18 #define MINIKIN_LAYOUT_CACHE_H
19 
20 #include "minikin/Layout.h"
21 
22 #include <mutex>
23 
24 #include <utils/JenkinsHash.h>
25 #include <utils/LruCache.h>
26 
27 namespace minikin {
28 
29 // Layout cache datatypes
30 class LayoutCacheKey {
31 public:
LayoutCacheKey(const U16StringPiece & text,const Range & range,const MinikinPaint & paint,bool dir,StartHyphenEdit startHyphen,EndHyphenEdit endHyphen)32     LayoutCacheKey(const U16StringPiece& text, const Range& range, const MinikinPaint& paint,
33                    bool dir, StartHyphenEdit startHyphen, EndHyphenEdit endHyphen)
34             : mChars(text.data()),
35               mNchars(text.size()),
36               mStart(range.getStart()),
37               mCount(range.getLength()),
38               mId(paint.font->getId()),
39               mStyle(paint.fontStyle),
40               mSize(paint.size),
41               mScaleX(paint.scaleX),
42               mSkewX(paint.skewX),
43               mLetterSpacing(paint.letterSpacing),
44               mWordSpacing(paint.wordSpacing),
45               mPaintFlags(paint.paintFlags),
46               mLocaleListId(paint.localeListId),
47               mFamilyVariant(paint.familyVariant),
48               mStartHyphen(startHyphen),
49               mEndHyphen(endHyphen),
50               mIsRtl(dir),
51               mHash(computeHash()) {}
52 
53     bool operator==(const LayoutCacheKey& o) const {
54         return mId == o.mId && mStart == o.mStart && mCount == o.mCount && mStyle == o.mStyle &&
55                mSize == o.mSize && mScaleX == o.mScaleX && mSkewX == o.mSkewX &&
56                mLetterSpacing == o.mLetterSpacing && mWordSpacing == o.mWordSpacing &&
57                mPaintFlags == o.mPaintFlags && mLocaleListId == o.mLocaleListId &&
58                mFamilyVariant == o.mFamilyVariant && mStartHyphen == o.mStartHyphen &&
59                mEndHyphen == o.mEndHyphen && mIsRtl == o.mIsRtl && mNchars == o.mNchars &&
60                !memcmp(mChars, o.mChars, mNchars * sizeof(uint16_t));
61     }
62 
hash()63     android::hash_t hash() const { return mHash; }
64 
copyText()65     void copyText() {
66         uint16_t* charsCopy = new uint16_t[mNchars];
67         memcpy(charsCopy, mChars, mNchars * sizeof(uint16_t));
68         mChars = charsCopy;
69     }
freeText()70     void freeText() {
71         delete[] mChars;
72         mChars = NULL;
73     }
74 
doLayout(Layout * layout,const MinikinPaint & paint)75     void doLayout(Layout* layout, const MinikinPaint& paint) const {
76         layout->mAdvances.resize(mCount, 0);
77         layout->mExtents.resize(mCount);
78         layout->doLayoutRun(mChars, mStart, mCount, mNchars, mIsRtl, paint, mStartHyphen,
79                             mEndHyphen);
80     }
81 
getMemoryUsage()82     uint32_t getMemoryUsage() const { return sizeof(LayoutCacheKey) + sizeof(uint16_t) * mNchars; }
83 
84 private:
85     const uint16_t* mChars;
86     size_t mNchars;
87     size_t mStart;
88     size_t mCount;
89     uint32_t mId;  // for the font collection
90     FontStyle mStyle;
91     float mSize;
92     float mScaleX;
93     float mSkewX;
94     float mLetterSpacing;
95     float mWordSpacing;
96     int32_t mPaintFlags;
97     uint32_t mLocaleListId;
98     FontFamily::Variant mFamilyVariant;
99     StartHyphenEdit mStartHyphen;
100     EndHyphenEdit mEndHyphen;
101     bool mIsRtl;
102     // Note: any fields added to MinikinPaint must also be reflected here.
103     // TODO: language matching (possibly integrate into style)
104     android::hash_t mHash;
105 
computeHash()106     android::hash_t computeHash() const {
107         uint32_t hash = android::JenkinsHashMix(0, mId);
108         hash = android::JenkinsHashMix(hash, mStart);
109         hash = android::JenkinsHashMix(hash, mCount);
110         hash = android::JenkinsHashMix(hash, android::hash_type(mStyle.identifier()));
111         hash = android::JenkinsHashMix(hash, android::hash_type(mSize));
112         hash = android::JenkinsHashMix(hash, android::hash_type(mScaleX));
113         hash = android::JenkinsHashMix(hash, android::hash_type(mSkewX));
114         hash = android::JenkinsHashMix(hash, android::hash_type(mLetterSpacing));
115         hash = android::JenkinsHashMix(hash, android::hash_type(mWordSpacing));
116         hash = android::JenkinsHashMix(hash, android::hash_type(mPaintFlags));
117         hash = android::JenkinsHashMix(hash, android::hash_type(mLocaleListId));
118         hash = android::JenkinsHashMix(hash,
119                                        android::hash_type(static_cast<uint8_t>(mFamilyVariant)));
120         hash = android::JenkinsHashMix(
121                 hash,
122                 android::hash_type(static_cast<uint8_t>(packHyphenEdit(mStartHyphen, mEndHyphen))));
123         hash = android::JenkinsHashMix(hash, android::hash_type(mIsRtl));
124         hash = android::JenkinsHashMixShorts(hash, mChars, mNchars);
125         return android::JenkinsHashWhiten(hash);
126     }
127 };
128 
129 class LayoutCache : private android::OnEntryRemoved<LayoutCacheKey, Layout*> {
130 public:
clear()131     void clear() {
132         std::lock_guard<std::mutex> lock(mMutex);
133         mCache.clear();
134     }
135 
136     // Do not use LayoutCache inside the callback function, otherwise dead-lock may happen.
137     template <typename F>
getOrCreate(const U16StringPiece & text,const Range & range,const MinikinPaint & paint,bool dir,StartHyphenEdit startHyphen,EndHyphenEdit endHyphen,F & f)138     void getOrCreate(const U16StringPiece& text, const Range& range, const MinikinPaint& paint,
139                      bool dir, StartHyphenEdit startHyphen, EndHyphenEdit endHyphen, F& f) {
140         LayoutCacheKey key(text, range, paint, dir, startHyphen, endHyphen);
141         if (paint.skipCache()) {
142             Layout layoutForWord;
143             key.doLayout(&layoutForWord, paint);
144             f(layoutForWord);
145             return;
146         }
147 
148         mRequestCount++;
149         {
150             std::lock_guard<std::mutex> lock(mMutex);
151             Layout* layout = mCache.get(key);
152             if (layout != nullptr) {
153                 mCacheHitCount++;
154                 f(*layout);
155                 return;
156             }
157         }
158         // Doing text layout takes long time, so releases the mutex during doing layout.
159         // Don't care even if we do the same layout in other thred.
160         key.copyText();
161         std::unique_ptr<Layout> layout = std::make_unique<Layout>();
162         key.doLayout(layout.get(), paint);
163         f(*layout);
164         {
165             std::lock_guard<std::mutex> lock(mMutex);
166             mCache.put(key, layout.release());
167         }
168     }
169 
dumpStats(int fd)170     void dumpStats(int fd) {
171         std::lock_guard<std::mutex> lock(mMutex);
172         dprintf(fd, "\nLayout Cache Info:\n");
173         dprintf(fd, "  Usage: %zd/%zd entries\n", mCache.size(), kMaxEntries);
174         float ratio = (mRequestCount == 0) ? 0 : mCacheHitCount / (float)mRequestCount;
175         dprintf(fd, "  Hit ratio: %d/%d (%f)\n", mCacheHitCount, mRequestCount, ratio);
176     }
177 
getInstance()178     static LayoutCache& getInstance() {
179         static LayoutCache cache(kMaxEntries);
180         return cache;
181     }
182 
183 protected:
LayoutCache(uint32_t maxEntries)184     LayoutCache(uint32_t maxEntries) : mCache(maxEntries), mRequestCount(0), mCacheHitCount(0) {
185         mCache.setOnEntryRemovedListener(this);
186     }
187 
188 private:
189     // callback for OnEntryRemoved
operator()190     void operator()(LayoutCacheKey& key, Layout*& value) {
191         key.freeText();
192         delete value;
193     }
194 
195     android::LruCache<LayoutCacheKey, Layout*> mCache GUARDED_BY(mMutex);
196 
197     int32_t mRequestCount;
198     int32_t mCacheHitCount;
199 
200     // static const size_t kMaxEntries = LruCache<LayoutCacheKey, Layout*>::kUnlimitedCapacity;
201 
202     // TODO: eviction based on memory footprint; for now, we just use a constant
203     // number of strings
204     static const size_t kMaxEntries = 5000;
205 
206     std::mutex mMutex;
207 };
208 
hash_type(const LayoutCacheKey & key)209 inline android::hash_t hash_type(const LayoutCacheKey& key) {
210     return key.hash();
211 }
212 
213 }  // namespace minikin
214 #endif  // MINIKIN_LAYOUT_CACHE_H
215