Merge "Memory allocation changes" into jb-mr1-dev

6 files changed, 125 insertions, 80 deletions

diff --git a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
index 464224a..5083222 100644
--- a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
+++ b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
@@ -43,7 +43,7 @@
 #include "wtf/HashSet.h"
 #include "wtf/StringHasher.h"
 
-#define NEW_OP(X) new (operationHeap()) GraphicsOperation::X
+#define NEW_OP(X) new (heap()) GraphicsOperation::X
 
 #define USE_CLIPPING_PAINTER true
 
@@ -133,7 +133,7 @@ public:
     ~CanvasState() {
         ALOGV("Delete %p", this);
         for (size_t i = 0; i < m_operations.size(); i++)
-            delete m_operations[i];
+            m_operations[i]->~RecordingData();
         m_operations.clear();
     }
 
@@ -202,15 +202,10 @@ private:
     // Careful, ordering matters here. Ordering is first constructed == last destroyed,
     // so we have to make sure our Heap is the first thing listed so that it is
     // the last thing destroyed.
-    LinearAllocator m_operationHeap;
-    LinearAllocator m_canvasStateHeap;
-    // Used by both PlatformGraphicsContext::State and SkPaint, as both are
-    // roughly the same size (72 bytes vs. 76 bytes, respectively)
-    LinearAllocator m_stateHeap;
+    LinearAllocator m_heap;
 public:
     RecordingImpl()
-        : m_canvasStateHeap(sizeof(CanvasState))
-        , m_stateHeap(sizeof(SkPaint))
+        : m_tree(&m_heap)
         , m_nodeCount(0)
     {
     }
@@ -225,7 +220,7 @@ public:
         StateHashSet::iterator it = m_states.find(inState);
         if (it != m_states.end())
             return (*it);
-        void* buf = m_stateHeap.alloc(sizeof(PlatformGraphicsContext::State));
+        void* buf = heap()->alloc(sizeof(PlatformGraphicsContext::State));
         PlatformGraphicsContext::State* state = new (buf) PlatformGraphicsContext::State(*inState);
         m_states.add(state);
         return state;
@@ -235,7 +230,7 @@ public:
         SkPaintHashSet::iterator it = m_paints.find(&inPaint);
         if (it != m_paints.end())
             return (*it);
-        void* buf = m_stateHeap.alloc(sizeof(SkPaint));
+        void* buf = heap()->alloc(sizeof(SkPaint));
         SkPaint* paint = new (buf) SkPaint(inPaint);
         m_paints.add(paint);
         return paint;
@@ -284,12 +279,17 @@ public:
         toState->playback(context, fromId, toId);
     }
 
-    LinearAllocator* operationHeap() { return &m_operationHeap; }
-    LinearAllocator* canvasStateHeap() { return &m_canvasStateHeap; }
+    LinearAllocator* heap() { return &m_heap; }
 
     RTree::RTree m_tree;
     int m_nodeCount;
 
+    void dumpMemoryStats() {
+        static const char* PREFIX = "  ";
+        ALOGD("Heap:");
+        m_heap.dumpMemoryStats(PREFIX);
+    }
+
 private:
 
     void clearStates() {
@@ -495,12 +495,14 @@ PlatformGraphicsContextRecording::PlatformGraphicsContextRecording(Recording* re
         mRecording->setRecording(new RecordingImpl());
     mMatrixStack.append(SkMatrix::I());
     mCurrentMatrix = &(mMatrixStack.last());
-    pushStateOperation(new (canvasStateHeap()) CanvasState(0));
+    pushStateOperation(new (heap()) CanvasState(0));
 }
 
 PlatformGraphicsContextRecording::~PlatformGraphicsContextRecording()
 {
     ALOGV("RECORDING: end");
+    IF_ALOGV()
+        mRecording->recording()->dumpMemoryStats();
 }
 
 bool PlatformGraphicsContextRecording::isPaintingDisabled()
@@ -521,7 +523,7 @@ SkCanvas* PlatformGraphicsContextRecording::recordingCanvas()
 void PlatformGraphicsContextRecording::beginTransparencyLayer(float opacity)
 {
     CanvasState* parent = mRecordingStateStack.last().mCanvasState;
-    pushStateOperation(new (canvasStateHeap()) CanvasState(parent, opacity));
+    pushStateOperation(new (heap()) CanvasState(parent, opacity));
 }
 
 void PlatformGraphicsContextRecording::endTransparencyLayer()
@@ -533,7 +535,7 @@ void PlatformGraphicsContextRecording::save()
 {
     PlatformGraphicsContext::save();
     CanvasState* parent = mRecordingStateStack.last().mCanvasState;
-    pushStateOperation(new (canvasStateHeap()) CanvasState(parent));
+    pushStateOperation(new (heap()) CanvasState(parent));
     pushMatrix();
 }
 
@@ -901,7 +903,7 @@ void PlatformGraphicsContextRecording::drawPosText(const void* inText, size_t by
     FloatRect bounds = approximateTextBounds(byteLength / sizeof(uint16_t), inPos, inPaint);
     const SkPaint* paint = mRecording->recording()->getSkPaint(inPaint);
     int posSize = sizeof(SkPoint) * paint->countText(inText, byteLength);
-    void* text = operationHeap()->alloc(posSize + byteLength);
+    void* text = heap()->alloc(posSize + byteLength);
     SkPoint* pos = (SkPoint*) ((char*)text + byteLength);
     memcpy(text, inText, byteLength);
     memcpy(pos, inPos, posSize);
@@ -942,7 +944,7 @@ void PlatformGraphicsContextRecording::popStateOperation()
                 state.mCanvasState, state.mCanvasState->isTransparencyLayer());
         mRecording->recording()->removeCanvasState(state.mCanvasState);
         state.mCanvasState->~CanvasState();
-        canvasStateHeap()->rewindTo(state.mCanvasState);
+        heap()->rewindIfLastAlloc(state.mCanvasState, sizeof(CanvasState));
     } else {
         ALOGV("RECORDING: popStateOperation: %p(isLayer=%d)",
                 state.mCanvasState, state.mCanvasState->isTransparencyLayer());
@@ -1025,7 +1027,6 @@ void PlatformGraphicsContextRecording::appendDrawingOperation(
     if (ibounds.isEmpty()) {
         ALOGV("RECORDING: Operation %s() was clipped out", operation->name());
         operation->~Operation();
-        operationHeap()->rewindTo(operation);
         return;
     }
     if (operation->isOpaque()
@@ -1038,25 +1039,20 @@ void PlatformGraphicsContextRecording::appendDrawingOperation(
     }
     ALOGV("RECORDING: appendOperation %p->%s() bounds " INT_RECT_FORMAT, operation, operation->name(),
             INT_RECT_ARGS(ibounds));
-    RecordingData* data = new RecordingData(operation, mRecording->recording()->m_nodeCount++);
+    RecordingData* data = new (heap()) RecordingData(operation, mRecording->recording()->m_nodeCount++);
     mRecording->recording()->m_tree.insert(ibounds, data);
 }
 
 void PlatformGraphicsContextRecording::appendStateOperation(GraphicsOperation::Operation* operation)
 {
     ALOGV("RECORDING: appendOperation %p->%s()", operation, operation->name());
-    RecordingData* data = new RecordingData(operation, mRecording->recording()->m_nodeCount++);
+    RecordingData* data = new (heap()) RecordingData(operation, mRecording->recording()->m_nodeCount++);
     mRecordingStateStack.last().mCanvasState->adoptAndAppend(data);
 }
 
-LinearAllocator* PlatformGraphicsContextRecording::operationHeap()
-{
-    return mRecording->recording()->operationHeap();
-}
-
-LinearAllocator* PlatformGraphicsContextRecording::canvasStateHeap()
+LinearAllocator* PlatformGraphicsContextRecording::heap()
 {
-    return mRecording->recording()->canvasStateHeap();
+    return mRecording->recording()->heap();
 }
 
 }   // WebCore
diff --git a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h
index d62eb8a..b1018e7 100644
--- a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h
+++ b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h
@@ -160,8 +160,7 @@ private:
     void popMatrix();
     IntRect calculateFinalBounds(FloatRect bounds);
     IntRect calculateCoveredBounds(FloatRect bounds);
-    LinearAllocator* operationHeap();
-    LinearAllocator* canvasStateHeap();
+    LinearAllocator* heap();
 
     SkPicture* mPicture;
     SkMatrix* mCurrentMatrix;
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.cpp b/Source/WebCore/platform/graphics/android/context/RTree.cpp
index fa048b7..2e24c34 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.cpp
+++ b/Source/WebCore/platform/graphics/android/context/RTree.cpp
@@ -33,6 +33,15 @@
 #include "AndroidLog.h"
 #include "LinearAllocator.h"
 
+namespace WebCore {
+
+void* RecordingData::operator new(size_t size, LinearAllocator* allocator)
+{
+    return allocator->alloc(size);
+}
+
+}
+
 namespace RTree {
 
 #ifdef DEBUG
@@ -123,12 +132,12 @@ int computeDeltaArea(Node* node, int& minx, int& miny,
 //
 //////////////////////////////////////////////////////////////////////
 
-RTree::RTree(int M)
+RTree::RTree(WebCore::LinearAllocator* allocator, int M)
+    : m_allocator(allocator)
 {
     m_maxChildren = M;
     m_listA = new ElementList(M);
     m_listB = new ElementList(M);
-    m_allocator = new WebCore::LinearAllocator(sizeof(Node));
     m_root = Node::create(this);
 }
 
@@ -137,7 +146,6 @@ RTree::~RTree()
     delete m_listA;
     delete m_listB;
     deleteNode(m_root);
-    delete m_allocator;
 }
 
 void RTree::insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload)
@@ -263,7 +271,8 @@ Node::~Node()
     for (unsigned i = 0; i < m_nbChildren; i++)
         m_tree->deleteNode(m_children[i]);
     delete[] m_children;
-    delete m_payload;
+    if (m_payload)
+        m_payload->~RecordingData();
 }
 
 void Node::setParent(Node* node)
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.h b/Source/WebCore/platform/graphics/android/context/RTree.h
index 366e3d1..50962ef 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.h
+++ b/Source/WebCore/platform/graphics/android/context/RTree.h
@@ -46,6 +46,12 @@ public:
 
     size_t m_orderBy;
     GraphicsOperation::Operation* m_operation;
+
+    void* operator new(size_t size, LinearAllocator* allocator);
+
+    // Purposely not implemented - use a LinearAllocator please
+    void* operator new(size_t size);
+    void operator delete(void* ptr);
 };
 
 } // namespace WebCore
@@ -58,7 +64,7 @@ class Node;
 class RTree {
 public:
     // M -- max number of children per node
-    RTree(int M = 10);
+    RTree(WebCore::LinearAllocator* allocator, int M = 10);
     ~RTree();
 
     void insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload);
diff --git a/Source/WebCore/platform/graphics/android/utils/LinearAllocator.cpp b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.cpp
index 8aa1616..b945944 100644
--- a/Source/WebCore/platform/graphics/android/utils/LinearAllocator.cpp
+++ b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.cpp
@@ -33,17 +33,16 @@
 
 namespace WebCore {
 
-// The ideal size of a page allocation
-#define TARGET_PAGE_SIZE 16384 // 16kb
-
-// our pool needs to big enough to hold at least this many items
-#define MIN_OBJECT_COUNT 4
+// The ideal size of a page allocation (these need to be multiples of 4)
+#define INITIAL_PAGE_SIZE ((size_t)4096) // 4kb
+#define MAX_PAGE_SIZE ((size_t)131072) // 128kb
 
 // The maximum amount of wasted space we can have per page
 // Allocations exceeding this will have their own dedicated page
 // If this is too low, we will malloc too much
 // Too high, and we may waste too much space
-#define MAX_WASTE_SIZE ((size_t)256)
+// Must be smaller than INITIAL_PAGE_SIZE
+#define MAX_WASTE_SIZE ((size_t)1024)
 
 #define ALIGN(x) (x + (x % sizeof(int)))
 
@@ -98,21 +97,17 @@ private:
     Page* m_nextPage;
 };
 
-LinearAllocator::LinearAllocator(size_t averageAllocSize)
-    : m_next(0)
+LinearAllocator::LinearAllocator()
+    : m_pageSize(INITIAL_PAGE_SIZE)
+    , m_maxAllocSize(MAX_WASTE_SIZE)
+    , m_next(0)
     , m_currentPage(0)
     , m_pages(0)
+    , m_totalAllocated(0)
+    , m_wastedSpace(0)
+    , m_pageCount(0)
+    , m_dedicatedPageCount(0)
 {
-    if (averageAllocSize) {
-        int usable_page_size = TARGET_PAGE_SIZE - sizeof(LinearAllocator::Page);
-        int pcount = usable_page_size / averageAllocSize;
-        if (pcount < MIN_OBJECT_COUNT)
-            pcount = MIN_OBJECT_COUNT;
-        m_pageSize = pcount * averageAllocSize + sizeof(LinearAllocator::Page);
-    } else
-        m_pageSize = TARGET_PAGE_SIZE;
-    m_pageSize = ALIGN(m_pageSize);
-    m_maxAllocSize = std::min(MAX_WASTE_SIZE, (m_pageSize - sizeof(LinearAllocator::Page)));
 }
 
 LinearAllocator::~LinearAllocator(void)
@@ -136,11 +131,21 @@ void* LinearAllocator::end(Page* p)
     return ((char*)p) + m_pageSize;
 }
 
+bool LinearAllocator::fitsInCurrentPage(size_t size)
+{
+    return m_next && ((char*)m_next + size) <= end(m_currentPage);
+}
+
 void LinearAllocator::ensureNext(size_t size)
 {
-    if (m_next && ((char*)m_next + size) <= end(m_currentPage))
+    if (fitsInCurrentPage(size))
         return;
-    Page* p = newPage();
+    if (m_currentPage && m_pageSize < MAX_PAGE_SIZE) {
+        m_pageSize = std::min(MAX_PAGE_SIZE, m_pageSize * 2);
+        m_pageSize = ALIGN(m_pageSize);
+    }
+    m_wastedSpace += m_pageSize;
+    Page* p = newPage(m_pageSize);
     if (m_currentPage)
         m_currentPage->setNext(p);
     m_currentPage = p;
@@ -149,25 +154,14 @@ void LinearAllocator::ensureNext(size_t size)
     m_next = start(m_currentPage);
 }
 
-unsigned LinearAllocator::memusage()
-{
-    unsigned memusage = 0;
-    Page* p = m_pages;
-    while (p) {
-        memusage += m_pageSize;
-        p = p->next();
-    }
-    return memusage;
-}
-
 void* LinearAllocator::alloc(size_t size)
 {
     size = ALIGN(size);
-    if (size > m_maxAllocSize) {
+    if (size > m_maxAllocSize && !fitsInCurrentPage(size)) {
+        ALOGV("Exceeded max size %d > %d", size, m_maxAllocSize);
         // Allocation is too large, create a dedicated page for the allocation
-        ADD_ALLOCATION(size);
-        void* buf = malloc(size + sizeof(LinearAllocator::Page));
-        Page* page = new (buf) Page();
+        Page* page = newPage(size);
+        m_dedicatedPageCount++;
         page->setNext(m_pages);
         m_pages = page;
         if (!m_currentPage)
@@ -177,21 +171,55 @@ void* LinearAllocator::alloc(size_t size)
     ensureNext(size);
     void* ptr = m_next;
     m_next = ((char*)m_next) + size;
+    m_wastedSpace -= size;
     return ptr;
 }
 
-void LinearAllocator::rewindTo(void* ptr)
+void LinearAllocator::rewindIfLastAlloc(void* ptr, size_t allocSize)
 {
     // Don't bother rewinding across pages
-    if (ptr >= start(m_currentPage) && ptr < end(m_currentPage))
+    if (ptr >= start(m_currentPage) && ptr < end(m_currentPage)
+            && ptr == ((char*)m_next - allocSize)) {
+        m_totalAllocated -= allocSize;
+        m_wastedSpace += allocSize;
         m_next = ptr;
+    }
 }
 
-LinearAllocator::Page* LinearAllocator::newPage()
+LinearAllocator::Page* LinearAllocator::newPage(size_t pageSize)
 {
-    ADD_ALLOCATION(m_pageSize);
-    void* buf = malloc(m_pageSize);
+    pageSize += sizeof(LinearAllocator::Page);
+    ADD_ALLOCATION(pageSize);
+    m_totalAllocated += pageSize;
+    m_pageCount++;
+    void* buf = malloc(pageSize);
     return new (buf) Page();
 }
 
+static const char* toSize(size_t value, float& result)
+{
+    if (value < 2000) {
+        result = value;
+        return "B";
+    }
+    if (value < 2000000) {
+        result = value / 1024.0f;
+        return "KB";
+    }
+    result = value / 1048576.0f;
+    return "MB";
+}
+
+void LinearAllocator::dumpMemoryStats(const char* prefix)
+{
+    float prettySize;
+    const char* prettySuffix;
+    prettySuffix = toSize(m_totalAllocated, prettySize);
+    ALOGD("%sTotal allocated: %.2f%s", prefix, prettySize, prettySuffix);
+    prettySuffix = toSize(m_wastedSpace, prettySize);
+    ALOGD("%sWasted space: %.2f%s (%.1f%%)", prefix, prettySize, prettySuffix,
+          (float) m_wastedSpace / (float) m_totalAllocated * 100.0f);
+    ALOGD("%sPages %d (dedicated %d)", prefix, m_pageCount, m_dedicatedPageCount);
+}
+
 } // namespace WebCore
diff --git a/Source/WebCore/platform/graphics/android/utils/LinearAllocator.h b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.h
index 1f3265c..8cabf7c 100644
--- a/Source/WebCore/platform/graphics/android/utils/LinearAllocator.h
+++ b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.h
@@ -31,29 +31,36 @@ namespace WebCore {
 class LinearAllocator
 {
 public:
-    LinearAllocator(size_t averageAllocSize = 0);
+    LinearAllocator();
     ~LinearAllocator();
 
     void* alloc(size_t size);
-    void rewindTo(void*);
+    void rewindIfLastAlloc(void* ptr, size_t allocSize);
+
+    void dumpMemoryStats(const char* prefix = "");
 
 private:
     LinearAllocator(const LinearAllocator& other);
 
     class Page;
 
-    Page* newPage();
+    Page* newPage(size_t pageSize);
+    bool fitsInCurrentPage(size_t size);
     void ensureNext(size_t size);
     void* start(Page *p);
     void* end(Page* p);
 
-    unsigned memusage();
-
     size_t m_pageSize;
     size_t m_maxAllocSize;
     void* m_next;
     Page* m_currentPage;
     Page* m_pages;
+
+    // Memory usage tracking
+    size_t m_totalAllocated;
+    size_t m_wastedSpace;
+    size_t m_pageCount;
+    size_t m_dedicatedPageCount;
 };
 
 } // namespace WebCore