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