Add rewind capability to SkChunkAlloc

Split off from https://codereview.chromium.org/940533003/ (Decrease GrInOrderDrawBuffer::Cmd's reliance on GrInOrderDrawBuffer)

Review URL: https://codereview.chromium.org/967553003

4 files changed, 178 insertions, 34 deletions

diff --git a/include/core/SkChunkAlloc.h b/include/core/SkChunkAlloc.h
index e13e2b99c6..9699842e6b 100644
--- a/include/core/SkChunkAlloc.h
+++ b/include/core/SkChunkAlloc.h
@@ -22,6 +22,11 @@ public:
      *  pointers.
      */
     void reset();
+    /**
+     *  Reset to 0 used bytes preserving as much memory as possible.
+     *  This invalidates all returned pointers.
+     */
+    void rewind();
 
     enum AllocFailType {
         kReturnNil_AllocFailType,
@@ -43,7 +48,8 @@ public:
 
     size_t totalCapacity() const { return fTotalCapacity; }
     size_t totalUsed() const { return fTotalUsed; }
-    int blockCount() const { return fBlockCount; }
+    SkDEBUGCODE(int blockCount() const { return fBlockCount; })
+    SkDEBUGCODE(size_t totalLost() const { return fTotalLost; })
 
     /**
      *  Returns true if the specified address is within one of the chunks, and
@@ -60,9 +66,13 @@ private:
     size_t  fChunkSize;
     size_t  fTotalCapacity;
     size_t  fTotalUsed;     // will be <= fTotalCapacity
-    int     fBlockCount;
+    SkDEBUGCODE(int     fBlockCount;)
+    SkDEBUGCODE(size_t  fTotalLost;)     // will be <= fTotalCapacity
 
     Block* newBlock(size_t bytes, AllocFailType ftype);
+    Block* addBlockIfNecessary(size_t bytes, AllocFailType ftype);
+
+    SkDEBUGCODE(void validate();)
 };
 
 #endif
diff --git a/src/core/SkChunkAlloc.cpp b/src/core/SkChunkAlloc.cpp
index 62cdf1532f..4a71c2d2c4 100644
--- a/src/core/SkChunkAlloc.cpp
+++ b/src/core/SkChunkAlloc.cpp
@@ -23,6 +23,18 @@ struct SkChunkAlloc::Block {
     char*   fFreePtr;
     // data[] follows
 
+    size_t blockSize() { 
+        char* start = this->startOfData();
+        size_t bytes = fFreePtr - start;
+        return fFreeSize + bytes;
+    }
+
+    void reset() {
+        fNext = NULL;
+        fFreeSize = this->blockSize();
+        fFreePtr = this->startOfData();
+    }
+
     char* startOfData() {
         return reinterpret_cast<char*>(this + 1);
     }
@@ -53,7 +65,8 @@ SkChunkAlloc::SkChunkAlloc(size_t minSize) {
     fChunkSize = fMinSize;
     fTotalCapacity = 0;
     fTotalUsed = 0;
-    fBlockCount = 0;
+    SkDEBUGCODE(fTotalLost = 0;)
+    SkDEBUGCODE(fBlockCount = 0;)
 }
 
 SkChunkAlloc::~SkChunkAlloc() {
@@ -66,7 +79,40 @@ void SkChunkAlloc::reset() {
     fChunkSize = fMinSize;  // reset to our initial minSize
     fTotalCapacity = 0;
     fTotalUsed = 0;
-    fBlockCount = 0;
+    SkDEBUGCODE(fTotalLost = 0;)
+    SkDEBUGCODE(fBlockCount = 0;)
+}
+
+void SkChunkAlloc::rewind() {
+    SkDEBUGCODE(this->validate();)
+
+    Block* largest = fBlock;
+
+    if (largest) {
+        Block* next;
+        for (Block* cur = largest->fNext; cur; cur = next) {
+            next = cur->fNext;
+            if (cur->blockSize() > largest->blockSize()) {
+                sk_free(largest);
+                largest = cur;
+            } else {
+                sk_free(cur);
+            }
+        }
+
+        largest->reset();
+        fTotalCapacity = largest->blockSize();
+        SkDEBUGCODE(fBlockCount = 1;)
+    } else {
+        fTotalCapacity = 0;
+        SkDEBUGCODE(fBlockCount = 0;)
+    }
+
+    fBlock = largest;
+    fChunkSize = fMinSize;  // reset to our initial minSize
+    fTotalUsed = 0;
+    SkDEBUGCODE(fTotalLost = 0;)
+    SkDEBUGCODE(this->validate();)
 }
 
 SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) {
@@ -79,43 +125,60 @@ SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) {
                         ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0);
 
     if (block) {
-        //    block->fNext = fBlock;
         block->fFreeSize = size;
         block->fFreePtr = block->startOfData();
 
         fTotalCapacity += size;
-        fBlockCount += 1;
+        SkDEBUGCODE(fBlockCount += 1;)
 
         fChunkSize = increase_next_size(fChunkSize);
     }
     return block;
 }
 
-void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) {
-    fTotalUsed += bytes;
-
-    bytes = SkAlign4(bytes);
-
-    Block* block = fBlock;
+SkChunkAlloc::Block* SkChunkAlloc::addBlockIfNecessary(size_t bytes, AllocFailType ftype) {
+    SkASSERT(SkIsAlign4(bytes));
 
-    if (block == NULL || bytes > block->fFreeSize) {
-        block = this->newBlock(bytes, ftype);
-        if (NULL == block) {
+    if (!fBlock || bytes > fBlock->fFreeSize) {
+        Block* block = this->newBlock(bytes, ftype);
+        if (!block) {
             return NULL;
         }
+#ifdef SK_DEBUG
+        if (fBlock) {
+            fTotalLost += fBlock->fFreeSize;
+        }
+#endif
         block->fNext = fBlock;
         fBlock = block;
     }
 
-    SkASSERT(block && bytes <= block->fFreeSize);
+    SkASSERT(fBlock && bytes <= fBlock->fFreeSize);
+    return fBlock;
+}
+
+void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) {
+    SkDEBUGCODE(this->validate();)
+
+    bytes = SkAlign4(bytes);
+
+    Block* block = this->addBlockIfNecessary(bytes, ftype);
+    if (!block) {
+        return NULL;
+    }
+
     char* ptr = block->fFreePtr;
 
+    fTotalUsed += bytes;
     block->fFreeSize -= bytes;
     block->fFreePtr = ptr + bytes;
+    SkDEBUGCODE(this->validate();)
     return ptr;
 }
 
 size_t SkChunkAlloc::unalloc(void* ptr) {
+    SkDEBUGCODE(this->validate();)
+
     size_t bytes = 0;
     Block* block = fBlock;
     if (block) {
@@ -123,10 +186,12 @@ size_t SkChunkAlloc::unalloc(void* ptr) {
         char* start = block->startOfData();
         if (start <= cPtr && cPtr < block->fFreePtr) {
             bytes = block->fFreePtr - cPtr;
+            fTotalUsed -= bytes;
             block->fFreeSize += bytes;
             block->fFreePtr = cPtr;
         }
     }
+    SkDEBUGCODE(this->validate();)
     return bytes;
 }
 
@@ -140,3 +205,31 @@ bool SkChunkAlloc::contains(const void* addr) const {
     }
     return false;
 }
+
+#ifdef SK_DEBUG
+void SkChunkAlloc::validate() {
+    int numBlocks = 0;
+    size_t totCapacity = 0;
+    size_t totUsed = 0;
+    size_t totLost = 0;
+    size_t totAvailable = 0;
+
+    for (Block* temp = fBlock; temp; temp = temp->fNext) {
+        ++numBlocks;
+        totCapacity += temp->blockSize();
+        totUsed += temp->fFreePtr - temp->startOfData();
+        if (temp == fBlock) {
+            totAvailable += temp->fFreeSize;
+        } else {
+            totLost += temp->fFreeSize;
+        }
+    }
+
+    SkASSERT(fBlockCount == numBlocks);
+    SkASSERT(fTotalCapacity == totCapacity);
+    SkASSERT(fTotalUsed == totUsed);
+    SkASSERT(fTotalLost == totLost);
+    SkASSERT(totCapacity == totUsed + totLost + totAvailable);
+}
+#endif
+
diff --git a/src/utils/SkDeferredCanvas.cpp b/src/utils/SkDeferredCanvas.cpp
index 7da8532716..8fe9f8a4b5 100644
--- a/src/utils/SkDeferredCanvas.cpp
+++ b/src/utils/SkDeferredCanvas.cpp
@@ -68,7 +68,7 @@ public:
     void* requestBlock(size_t minRequest, size_t* actual) SK_OVERRIDE;
     void notifyWritten(size_t bytes) SK_OVERRIDE;
     void playback(bool silent);
-    bool hasPendingCommands() const { return fAllocator.blockCount() != 0; }
+    bool hasPendingCommands() const { return fAllocator.totalUsed() != 0; }
     size_t storageAllocatedForRecording() const { return fAllocator.totalCapacity(); }
 private:
     enum {
diff --git a/tests/MemsetTest.cpp b/tests/MemsetTest.cpp
index ee6aaea94e..1e1378b4ad 100644
--- a/tests/MemsetTest.cpp
+++ b/tests/MemsetTest.cpp
@@ -9,32 +9,73 @@
 #include "SkUtils.h"
 #include "Test.h"
 
+static void check_alloc(skiatest::Reporter* reporter, const SkChunkAlloc& alloc,
+                        size_t capacity, size_t used, int numBlocks) {
+    REPORTER_ASSERT(reporter, alloc.totalCapacity() >= capacity);
+    REPORTER_ASSERT(reporter, alloc.totalUsed() == used);
+    SkDEBUGCODE(REPORTER_ASSERT(reporter, alloc.blockCount() == numBlocks);)
+}
+
+static void* simple_alloc(skiatest::Reporter* reporter, SkChunkAlloc* alloc, size_t size) {
+    void* ptr = alloc->allocThrow(size);
+    check_alloc(reporter, *alloc, size, size, 1);
+    REPORTER_ASSERT(reporter, alloc->contains(ptr));
+    return ptr;
+}
+                        
 static void test_chunkalloc(skiatest::Reporter* reporter) {
-    size_t min = 256;
-    SkChunkAlloc alloc(min);
+    static const size_t kMin = 1024;
+    SkChunkAlloc alloc(kMin);
 
-    REPORTER_ASSERT(reporter, 0 == alloc.totalCapacity());
-    REPORTER_ASSERT(reporter, 0 == alloc.totalUsed());
-    REPORTER_ASSERT(reporter, 0 == alloc.blockCount());
+    //------------------------------------------------------------------------
+    // check empty
+    check_alloc(reporter, alloc, 0, 0, 0);
     REPORTER_ASSERT(reporter, !alloc.contains(NULL));
     REPORTER_ASSERT(reporter, !alloc.contains(reporter));
 
+    // reset on empty allocator
     alloc.reset();
-    REPORTER_ASSERT(reporter, 0 == alloc.totalCapacity());
-    REPORTER_ASSERT(reporter, 0 == alloc.totalUsed());
-    REPORTER_ASSERT(reporter, 0 == alloc.blockCount());
-
-    size_t size = min >> 1;
-    void* ptr = alloc.allocThrow(size);
-    REPORTER_ASSERT(reporter, alloc.totalCapacity() >= size);
-    REPORTER_ASSERT(reporter, alloc.totalUsed() == size);
-    REPORTER_ASSERT(reporter, alloc.blockCount() > 0);
-    REPORTER_ASSERT(reporter, alloc.contains(ptr));
+    check_alloc(reporter, alloc, 0, 0, 0);
+
+    // rewind on empty allocator
+    alloc.rewind();
+    check_alloc(reporter, alloc, 0, 0, 0);
+
+    //------------------------------------------------------------------------
+    // test reset when something is allocated
+    size_t size = kMin >> 1;
+    void* ptr = simple_alloc(reporter, &alloc, size);
+
+    alloc.reset();
+    check_alloc(reporter, alloc, 0, 0, 0);
+    REPORTER_ASSERT(reporter, !alloc.contains(ptr));
+
+    //------------------------------------------------------------------------
+    // test rewind when something is allocated
+    ptr = simple_alloc(reporter, &alloc, size);
+
+    alloc.rewind();
+    check_alloc(reporter, alloc, size, 0, 1);
+    REPORTER_ASSERT(reporter, !alloc.contains(ptr));
 
+    // use the available block
+    ptr = simple_alloc(reporter, &alloc, size);
     alloc.reset();
+
+    //------------------------------------------------------------------------
+    // test out allocating a second block
+    ptr = simple_alloc(reporter, &alloc, size);
+
+    ptr = alloc.allocThrow(kMin);
+    check_alloc(reporter, alloc, 2*kMin, size+kMin, 2);
+    REPORTER_ASSERT(reporter, alloc.contains(ptr));
+
+    //------------------------------------------------------------------------
+    // test out unalloc
+    size_t freed = alloc.unalloc(ptr);
+    REPORTER_ASSERT(reporter, freed == kMin);
+    check_alloc(reporter, alloc, 2*kMin, size, 2);
     REPORTER_ASSERT(reporter, !alloc.contains(ptr));
-    REPORTER_ASSERT(reporter, 0 == alloc.totalCapacity());
-    REPORTER_ASSERT(reporter, 0 == alloc.totalUsed());
 }
 
 ///////////////////////////////////////////////////////////////////////////////