• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2015 Google Inc.
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 #ifndef GrDrawOpAtlas_DEFINED
9 #define GrDrawOpAtlas_DEFINED
10 
11 #include <cmath>
12 #include <vector>
13 
14 #include "include/core/SkSize.h"
15 #include "src/core/SkGlyphRunPainter.h"
16 #include "src/core/SkIPoint16.h"
17 #include "src/core/SkTInternalLList.h"
18 
19 #include "src/gpu/GrRectanizerSkyline.h"
20 #include "src/gpu/ops/GrDrawOp.h"
21 
22 class GrOnFlushResourceProvider;
23 
24 
25 /**
26  * This class manages one or more atlas textures on behalf of GrDrawOps. The draw ops that use the
27  * atlas perform texture uploads when preparing their draws during flush. The class provides
28  * facilities for using GrDrawOpUploadToken to detect data hazards. Op's uploads are performed in
29  * "ASAP" mode until it is impossible to add data without overwriting texels read by draws that
30  * have not yet executed on the gpu. At that point, the atlas will attempt to allocate a new
31  * atlas texture (or "page") of the same size, up to a maximum number of textures, and upload
32  * to that texture. If that's not possible, the uploads are performed "inline" between draws. If a
33  * single draw would use enough subimage space to overflow the atlas texture then the atlas will
34  * fail to add a subimage. This gives the op the chance to end the draw and begin a new one.
35  * Additional uploads will then succeed in inline mode.
36  *
37  * When the atlas has multiple pages, new uploads are prioritized to the lower index pages, i.e.,
38  * it will try to upload to page 0 before page 1 or 2. To keep the atlas from continually using
39  * excess space, periodic garbage collection is needed to shift data from the higher index pages to
40  * the lower ones, and then eventually remove any pages that are no longer in use. "In use" is
41  * determined by using the GrDrawUploadToken system: After a flush each subarea of the page
42  * is checked to see whether it was used in that flush; if it is not, a counter is incremented.
43  * Once that counter reaches a threshold that subarea is considered to be no longer in use.
44  *
45  * Garbage collection is initiated by the GrDrawOpAtlas's client via the compact() method. One
46  * solution is to make the client a subclass of GrOnFlushCallbackObject, register it with the
47  * GrContext via addOnFlushCallbackObject(), and the client's postFlush() method calls compact()
48  * and passes in the given GrDrawUploadToken.
49  */
50 class GrDrawOpAtlas {
51 private:
52     static constexpr auto kMaxMultitexturePages = 4;
53 
54 
55 public:
56     /** Is the atlas allowed to use more than one texture? */
57     enum class AllowMultitexturing : bool { kNo, kYes };
58 
59     static constexpr int kMaxPlots = 32; // restricted by the fPlotAlreadyUpdated bitfield
60                                          // in BulkUseTokenUpdater
61 
62     /**
63      * A PlotLocator specifies the plot and is analogous to a directory path:
64      *    page/plot/plotGeneration
65      *
66      * In fact PlotLocator is a portion of a glyph image location in the atlas fully specified by:
67      * format/atlasGeneration/page/plot/plotGeneration/(u,v)
68      */
69     typedef uint64_t PlotLocator;
70     static const uint64_t kInvalidPlotLocator = 0;
71     static const uint64_t kInvalidAtlasGeneration = 0;
72 
73     /**
74      * An interface for eviction callbacks. Whenever GrDrawOpAtlas evicts a
75      * specific PlotLocator, it will call all of the registered listeners so they can process the
76      * eviction.
77      */
78     class EvictionCallback {
79     public:
80         virtual ~EvictionCallback() = default;
81         virtual void evict(PlotLocator plotLocator) = 0;
82     };
83 
84     /**
85      * Keep track of generation number for Atlases and Plots.
86      */
87     class GenerationCounter {
88     public:
89         static constexpr uint64_t kInvalidGeneration = 0;
next()90         uint64_t next() {
91             return fGeneration++;
92         }
93 
94     private:
95         uint64_t fGeneration{1};
96     };
97 
98     /**
99      * Returns a GrDrawOpAtlas. This function can be called anywhere, but the returned atlas
100      * should only be used inside of GrMeshDrawOp::onPrepareDraws.
101      *  @param GrColorType      The colorType which this atlas will store
102      *  @param width            width in pixels of the atlas
103      *  @param height           height in pixels of the atlas
104      *  @param numPlotsX        The number of plots the atlas should be broken up into in the X
105      *                          direction
106      *  @param numPlotsY        The number of plots the atlas should be broken up into in the Y
107      *                          direction
108      *  @param atlasGeneration  a pointer to the context's generation counter.
109      *  @param allowMultitexturing Can the atlas use more than one texture.
110      *  @param evictor          A pointer to an eviction callback class.
111      *
112      *  @return                 An initialized GrDrawOpAtlas, or nullptr if creation fails
113      */
114     static std::unique_ptr<GrDrawOpAtlas> Make(GrProxyProvider*,
115                                                const GrBackendFormat& format,
116                                                GrColorType,
117                                                int width, int height,
118                                                int plotWidth, int plotHeight,
119                                                GenerationCounter* generationCounter,
120                                                AllowMultitexturing allowMultitexturing,
121                                                EvictionCallback* evictor);
122 
123     /**
124      * Packs a texture atlas page index into the uint16 texture coordinates.
125      *  @param u      U texture coordinate
126      *  @param v      V texture coordinate
127      *  @param pageIndex   index of the texture these coordinates apply to.
128                            Must be in the range [0, 3].
129      *  @return    The new u and v coordinates with the packed value
130      */
131     static std::pair<uint16_t, uint16_t> PackIndexInTexCoords(uint16_t u, uint16_t v,
132                                                               int pageIndex);
133     /**
134      * Unpacks a texture atlas page index from uint16 texture coordinates.
135      *  @param u      Packed U texture coordinate
136      *  @param v      Packed V texture coordinate
137      *  @return    The unpacked u and v coordinates with the page index.
138      */
139     static std::tuple<uint16_t, uint16_t, int> UnpackIndexFromTexCoords(uint16_t u, uint16_t v);
140 
141     /**
142      * Adds a width x height subimage to the atlas. Upon success it returns 'kSucceeded' and returns
143      * the ID and the subimage's coordinates in the backing texture. 'kTryAgain' is returned if
144      * the subimage cannot fit in the atlas without overwriting texels that will be read in the
145      * current draw. This indicates that the op should end its current draw and begin another
146      * before adding more data. Upon success, an upload of the provided image data will have
147      * been added to the GrDrawOp::Target, in "asap" mode if possible, otherwise in "inline" mode.
148      * Successive uploads in either mode may be consolidated.
149      * 'kError' will be returned when some unrecoverable error was encountered while trying to
150      * add the subimage. In this case the op being created should be discarded.
151      *
152      * NOTE: When the GrDrawOp prepares a draw that reads from the atlas, it must immediately call
153      * 'setUseToken' with the currentToken from the GrDrawOp::Target, otherwise the next call to
154      * addToAtlas might cause the previous data to be overwritten before it has been read.
155      */
156 
157     enum class ErrorCode {
158         kError,
159         kSucceeded,
160         kTryAgain
161     };
162 
163     ErrorCode addToAtlas(GrResourceProvider*, PlotLocator*, GrDeferredUploadTarget*,
164                          int width, int height,
165                          const void* image, SkIPoint16* loc);
166 
getViews()167     const GrSurfaceProxyView* getViews() const { return fViews; }
168 
atlasGeneration()169     uint64_t atlasGeneration() const { return fAtlasGeneration; }
170 
hasID(PlotLocator plotLocator)171     bool hasID(PlotLocator plotLocator) {
172         if (kInvalidPlotLocator == plotLocator) {
173             return false;
174         }
175 
176         uint32_t plot = GetPlotIndexFromID(plotLocator);
177         uint32_t page = GetPageIndexFromID(plotLocator);
178         uint64_t plotGeneration = fPages[page].fPlotArray[plot]->genID();
179         uint64_t locatorGeneration = GetGenerationFromID(plotLocator);
180         return plot < fNumPlots && page < fNumActivePages && plotGeneration == locatorGeneration;
181     }
182 
183     /** To ensure the atlas does not evict a given entry, the client must set the last use token. */
setLastUseToken(PlotLocator plotLocator,GrDeferredUploadToken token)184     void setLastUseToken(PlotLocator plotLocator, GrDeferredUploadToken token) {
185         SkASSERT(this->hasID(plotLocator));
186         uint32_t plotIdx = GetPlotIndexFromID(plotLocator);
187         SkASSERT(plotIdx < fNumPlots);
188         uint32_t pageIdx = GetPageIndexFromID(plotLocator);
189         SkASSERT(pageIdx < fNumActivePages);
190         Plot* plot = fPages[pageIdx].fPlotArray[plotIdx].get();
191         this->makeMRU(plot, pageIdx);
192         plot->setLastUseToken(token);
193     }
194 
numActivePages()195     uint32_t numActivePages() { return fNumActivePages; }
196 
197     /**
198      * A class which can be handed back to GrDrawOpAtlas for updating last use tokens in bulk.  The
199      * current max number of plots per page the GrDrawOpAtlas can handle is 32. If in the future
200      * this is insufficient then we can move to a 64 bit int.
201      */
202     class BulkUseTokenUpdater {
203     public:
BulkUseTokenUpdater()204         BulkUseTokenUpdater() {
205             memset(fPlotAlreadyUpdated, 0, sizeof(fPlotAlreadyUpdated));
206         }
BulkUseTokenUpdater(const BulkUseTokenUpdater & that)207         BulkUseTokenUpdater(const BulkUseTokenUpdater& that)
208             : fPlotsToUpdate(that.fPlotsToUpdate) {
209             memcpy(fPlotAlreadyUpdated, that.fPlotAlreadyUpdated, sizeof(fPlotAlreadyUpdated));
210         }
211 
add(PlotLocator plotLocator)212         bool add(PlotLocator plotLocator) {
213             int index = GrDrawOpAtlas::GetPlotIndexFromID(plotLocator);
214             int pageIdx = GrDrawOpAtlas::GetPageIndexFromID(plotLocator);
215             if (this->find(pageIdx, index)) {
216                 return false;
217             }
218             this->set(pageIdx, index);
219             return true;
220         }
221 
reset()222         void reset() {
223             fPlotsToUpdate.reset();
224             memset(fPlotAlreadyUpdated, 0, sizeof(fPlotAlreadyUpdated));
225         }
226 
227         struct PlotData {
PlotDataPlotData228             PlotData(int pageIdx, int plotIdx) : fPageIndex(pageIdx), fPlotIndex(plotIdx) {}
229             uint32_t fPageIndex;
230             uint32_t fPlotIndex;
231         };
232 
233     private:
find(int pageIdx,int index)234         bool find(int pageIdx, int index) const {
235             SkASSERT(index < kMaxPlots);
236             return (fPlotAlreadyUpdated[pageIdx] >> index) & 1;
237         }
238 
set(int pageIdx,int index)239         void set(int pageIdx, int index) {
240             SkASSERT(!this->find(pageIdx, index));
241             fPlotAlreadyUpdated[pageIdx] |= (1 << index);
242             fPlotsToUpdate.push_back(PlotData(pageIdx, index));
243         }
244 
245         static constexpr int kMinItems = 4;
246         SkSTArray<kMinItems, PlotData, true> fPlotsToUpdate;
247         uint32_t fPlotAlreadyUpdated[kMaxMultitexturePages]; // TODO: increase this to uint64_t
248                                                              //       to allow more plots per page
249 
250         friend class GrDrawOpAtlas;
251     };
252 
setLastUseTokenBulk(const BulkUseTokenUpdater & updater,GrDeferredUploadToken token)253     void setLastUseTokenBulk(const BulkUseTokenUpdater& updater, GrDeferredUploadToken token) {
254         int count = updater.fPlotsToUpdate.count();
255         for (int i = 0; i < count; i++) {
256             const BulkUseTokenUpdater::PlotData& pd = updater.fPlotsToUpdate[i];
257             // it's possible we've added a plot to the updater and subsequently the plot's page
258             // was deleted -- so we check to prevent a crash
259             if (pd.fPageIndex < fNumActivePages) {
260                 Plot* plot = fPages[pd.fPageIndex].fPlotArray[pd.fPlotIndex].get();
261                 this->makeMRU(plot, pd.fPageIndex);
262                 plot->setLastUseToken(token);
263             }
264         }
265     }
266 
267     void compact(GrDeferredUploadToken startTokenForNextFlush);
268 
GetPageIndexFromID(PlotLocator plotLocator)269     static uint32_t GetPageIndexFromID(PlotLocator plotLocator) {
270         return plotLocator & 0xff;
271     }
272 
273     void instantiate(GrOnFlushResourceProvider*);
274 
maxPages()275     uint32_t maxPages() const {
276         return fMaxPages;
277     }
278 
279     int numAllocated_TestingOnly() const;
280     void setMaxPages_TestingOnly(uint32_t maxPages);
281 
282 private:
283     GrDrawOpAtlas(GrProxyProvider*, const GrBackendFormat& format, GrColorType, int width,
284                   int height, int plotWidth, int plotHeight, GenerationCounter* generationCounter,
285                   AllowMultitexturing allowMultitexturing);
286 
287     /**
288      * The backing GrTexture for a GrDrawOpAtlas is broken into a spatial grid of Plots. The Plots
289      * keep track of subimage placement via their GrRectanizer. A Plot manages the lifetime of its
290      * data using two tokens, a last use token and a last upload token. Once a Plot is "full" (i.e.
291      * there is no room for the new subimage according to the GrRectanizer), it can no longer be
292      * used unless the last use of the Plot has already been flushed through to the gpu.
293      */
294     class Plot : public SkRefCnt {
295         SK_DECLARE_INTERNAL_LLIST_INTERFACE(Plot);
296 
297     public:
298         /** index() is a unique id for the plot relative to the owning GrAtlas and page. */
index()299         uint32_t index() const { return fPlotIndex; }
300         /**
301          * genID() is incremented when the plot is evicted due to a atlas spill. It is used to know
302          * if a particular subimage is still present in the atlas.
303          */
genID()304         uint64_t genID() const { return fGenID; }
plotLocator()305         GrDrawOpAtlas::PlotLocator plotLocator() const {
306             SkASSERT(GrDrawOpAtlas::kInvalidPlotLocator != fPlotLocator);
307             return fPlotLocator;
308         }
309         SkDEBUGCODE(size_t bpp() const { return fBytesPerPixel; })
310 
311         bool addSubImage(int width, int height, const void* image, SkIPoint16* loc);
312 
313         /**
314          * To manage the lifetime of a plot, we use two tokens. We use the last upload token to
315          * know when we can 'piggy back' uploads, i.e. if the last upload hasn't been flushed to
316          * the gpu, we don't need to issue a new upload even if we update the cpu backing store. We
317          * use lastUse to determine when we can evict a plot from the cache, i.e. if the last use
318          * has already flushed through the gpu then we can reuse the plot.
319          */
lastUploadToken()320         GrDeferredUploadToken lastUploadToken() const { return fLastUpload; }
lastUseToken()321         GrDeferredUploadToken lastUseToken() const { return fLastUse; }
setLastUploadToken(GrDeferredUploadToken token)322         void setLastUploadToken(GrDeferredUploadToken token) { fLastUpload = token; }
setLastUseToken(GrDeferredUploadToken token)323         void setLastUseToken(GrDeferredUploadToken token) { fLastUse = token; }
324 
325         void uploadToTexture(GrDeferredTextureUploadWritePixelsFn&, GrTextureProxy*);
326         void resetRects();
327 
flushesSinceLastUsed()328         int flushesSinceLastUsed() { return fFlushesSinceLastUse; }
resetFlushesSinceLastUsed()329         void resetFlushesSinceLastUsed() { fFlushesSinceLastUse = 0; }
incFlushesSinceLastUsed()330         void incFlushesSinceLastUsed() { fFlushesSinceLastUse++; }
331 
332     private:
333         Plot(int pageIndex, int plotIndex, GenerationCounter* generationCounter,
334              int offX, int offY, int width, int height, GrColorType colorType);
335 
336         ~Plot() override;
337 
338         /**
339          * Create a clone of this plot. The cloned plot will take the place of the current plot in
340          * the atlas
341          */
clone()342         Plot* clone() const {
343             return new Plot(
344                 fPageIndex, fPlotIndex, fGenerationCounter, fX, fY, fWidth, fHeight, fColorType);
345         }
346 
CreatePlotLocator(uint32_t pageIdx,uint32_t plotIdx,uint64_t generation)347         static GrDrawOpAtlas::PlotLocator CreatePlotLocator(
348                 uint32_t pageIdx, uint32_t plotIdx, uint64_t generation) {
349             SkASSERT(pageIdx < (1 << 8));
350             SkASSERT(pageIdx < kMaxMultitexturePages);
351             SkASSERT(plotIdx < (1 << 8));
352             SkASSERT(generation < ((uint64_t)1 << 48));
353             return generation << 16 | plotIdx << 8 | pageIdx;
354         }
355 
356         GrDeferredUploadToken fLastUpload;
357         GrDeferredUploadToken fLastUse;
358         // the number of flushes since this plot has been last used
359         int                   fFlushesSinceLastUse;
360 
361         struct {
362             const uint32_t fPageIndex : 16;
363             const uint32_t fPlotIndex : 16;
364         };
365         GenerationCounter* const fGenerationCounter;
366         uint64_t fGenID;
367         GrDrawOpAtlas::PlotLocator fPlotLocator;
368         unsigned char* fData;
369         const int fWidth;
370         const int fHeight;
371         const int fX;
372         const int fY;
373         GrRectanizerSkyline fRectanizer;
374         const SkIPoint16 fOffset;  // the offset of the plot in the backing texture
375         const GrColorType fColorType;
376         const size_t fBytesPerPixel;
377         SkIRect fDirtyRect;
378         SkDEBUGCODE(bool fDirty);
379 
380         friend class GrDrawOpAtlas;
381 
382         typedef SkRefCnt INHERITED;
383     };
384 
385     typedef SkTInternalLList<Plot> PlotList;
386 
GetPlotIndexFromID(PlotLocator plotLocator)387     static uint32_t GetPlotIndexFromID(PlotLocator plotLocator) {
388         return (plotLocator >> 8) & 0xff;
389     }
390 
391     // top 48 bits are reserved for the generation ID
GetGenerationFromID(PlotLocator plotLocator)392     static uint64_t GetGenerationFromID(PlotLocator plotLocator) {
393         return (plotLocator >> 16) & 0xffffffffffff;
394     }
395 
396     inline bool updatePlot(GrDeferredUploadTarget*, PlotLocator*, Plot*);
397 
makeMRU(Plot * plot,int pageIdx)398     inline void makeMRU(Plot* plot, int pageIdx) {
399         if (fPages[pageIdx].fPlotList.head() == plot) {
400             return;
401         }
402 
403         fPages[pageIdx].fPlotList.remove(plot);
404         fPages[pageIdx].fPlotList.addToHead(plot);
405 
406         // No MRU update for pages -- since we will always try to add from
407         // the front and remove from the back there is no need for MRU.
408     }
409 
410     bool uploadToPage(const GrCaps&, unsigned int pageIdx, PlotLocator* plotLocator,
411                       GrDeferredUploadTarget* target, int width, int height, const void* image,
412                       SkIPoint16* loc);
413 
414     bool createPages(GrProxyProvider*, GenerationCounter*);
415     bool activateNewPage(GrResourceProvider*);
416     void deactivateLastPage();
417 
418     void processEviction(PlotLocator);
processEvictionAndResetRects(Plot * plot)419     inline void processEvictionAndResetRects(Plot* plot) {
420         this->processEviction(plot->plotLocator());
421         plot->resetRects();
422     }
423 
424     GrBackendFormat       fFormat;
425     GrColorType           fColorType;
426     int                   fTextureWidth;
427     int                   fTextureHeight;
428     int                   fPlotWidth;
429     int                   fPlotHeight;
430     unsigned int          fNumPlots;
431 
432     GenerationCounter* const fGenerationCounter;
433     uint64_t                 fAtlasGeneration;
434 
435     // nextTokenToFlush() value at the end of the previous flush
436     GrDeferredUploadToken fPrevFlushToken;
437 
438     std::vector<EvictionCallback*> fEvictionCallbacks;
439 
440     struct Page {
441         // allocated array of Plots
442         std::unique_ptr<sk_sp<Plot>[]> fPlotArray;
443         // LRU list of Plots (MRU at head - LRU at tail)
444         PlotList fPlotList;
445     };
446     // proxies kept separate to make it easier to pass them up to client
447     GrSurfaceProxyView fViews[kMaxMultitexturePages];
448     Page fPages[kMaxMultitexturePages];
449     uint32_t fMaxPages;
450 
451     uint32_t fNumActivePages;
452 };
453 
454 // There are three atlases (A8, 565, ARGB) that are kept in relation with one another. In
455 // general, the A8 dimensions are 2x the 565 and ARGB dimensions with the constraint that an atlas
456 // size will always contain at least one plot. Since the ARGB atlas takes the most space, its
457 // dimensions are used to size the other two atlases.
458 class GrDrawOpAtlasConfig {
459 public:
460     // The capabilities of the GPU define maxTextureSize. The client provides maxBytes, and this
461     // represents the largest they want a single atlas texture to be. Due to multitexturing, we
462     // may expand temporarily to use more space as needed.
463     GrDrawOpAtlasConfig(int maxTextureSize, size_t maxBytes);
464 
465     // For testing only - make minimum sized atlases -- a single plot for ARGB, four for A8
GrDrawOpAtlasConfig()466     GrDrawOpAtlasConfig() : GrDrawOpAtlasConfig(kMaxAtlasDim, 0) {}
467 
468     SkISize atlasDimensions(GrMaskFormat type) const;
469     SkISize plotDimensions(GrMaskFormat type) const;
470 
471 private:
472     // On some systems texture coordinates are represented using half-precision floating point,
473     // which limits the largest atlas dimensions to 2048x2048.
474     // For simplicity we'll use this constraint for all of our atlas textures.
475     // This can be revisited later if we need larger atlases.
476     static constexpr int kMaxAtlasDim = 2048;
477 
478     SkISize fARGBDimensions;
479     int     fMaxTextureSize;
480 };
481 
482 #endif
483