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