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