Use a linear allocator for the RTree

Change-Id: I5e04c28a0c65378a26b1b99bcfeed4331591e265

5 files changed, 301 insertions, 63 deletions

diff --git a/Source/WebCore/Android.mk b/Source/WebCore/Android.mk
index a1914c5..98c1a63 100644
--- a/Source/WebCore/Android.mk
+++ b/Source/WebCore/Android.mk
@@ -698,7 +698,8 @@ LOCAL_SRC_FILES := $(LOCAL_SRC_FILES) \
 	platform/graphics/android/rendering/TilesProfiler.cpp \
 	platform/graphics/android/rendering/TransferQueue.cpp \
 	\
-	platform/graphics/android/utils/ClassTracker.cpp
+	platform/graphics/android/utils/ClassTracker.cpp \
+	platform/graphics/android/utils/LinearAllocator.cpp
 
 ifeq ($(ENABLE_SVG), true)
 LOCAL_SRC_FILES := $(LOCAL_SRC_FILES) \
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.cpp b/Source/WebCore/platform/graphics/android/context/RTree.cpp
index 5ba4622..fef30b3 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.cpp
+++ b/Source/WebCore/platform/graphics/android/context/RTree.cpp
@@ -29,11 +29,15 @@
 #include "config.h"
 
 #include "RTree.h"
+
 #include "AndroidLog.h"
+#include "LinearAllocator.h"
 
 namespace RTree {
 
+#ifdef DEBUG
 static unsigned gID = 0;
+#endif
 
 class Element;
 
@@ -124,20 +128,22 @@ RTree::RTree(int M)
     m_maxChildren = M;
     m_listA = new ElementList(M);
     m_listB = new ElementList(M);
-    m_root = new Node(this);
+    m_allocator = new WebCore::LinearAllocator(sizeof(Node));
+    m_root = Node::create(this);
 }
 
 RTree::~RTree()
 {
     delete m_listA;
     delete m_listB;
-    delete m_root;
+    deleteNode(m_root);
+    delete m_allocator;
 }
 
 void RTree::insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload)
 {
-    Element* e = new Element(this, bounds.x(), bounds.y(),
-                             bounds.maxX(), bounds.maxY(), payload);
+    Node* e = Node::create(this, bounds.x(), bounds.y(),
+                           bounds.maxX(), bounds.maxY(), payload);
     m_root->insert(e);
 }
 
@@ -153,7 +159,22 @@ void RTree::remove(WebCore::IntRect& clip)
 
 void RTree::display()
 {
+#ifdef DEBUG
     m_root->drawTree();
+#endif
+}
+
+void* RTree::allocateNode()
+{
+    return m_allocator->alloc();
+}
+
+void RTree::deleteNode(Node* n)
+{
+    if (n) {
+        n->~Node();
+        m_allocator->dealloc(n);
+    }
 }
 
 //////////////////////////////////////////////////////////////////////
@@ -205,32 +226,40 @@ void ElementList::removeAll()
 }
 
 void ElementList::display() {
+#ifdef DEBUG
     for (unsigned int i = 0; i < m_nbChildren; i++)
         m_children[i]->display(0);
+#endif
 }
 
 //////////////////////////////////////////////////////////////////////
 // Node
 
-Node::Node(RTree* t)
+Node::Node(RTree* t, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload)
     : m_tree(t)
     , m_parent(0)
     , m_children(0)
     , m_nbChildren(0)
-    , m_minX(0)
-    , m_minY(0)
-    , m_maxX(0)
-    , m_maxY(0)
+    , m_payload(payload)
+    , m_minX(minx)
+    , m_minY(miny)
+    , m_maxX(maxx)
+    , m_maxY(maxy)
 #ifdef DEBUG
     , m_tid(gID++)
 #endif
 {
+#ifdef DEBUG
     ALOGV("-> New Node %d", m_tid);
+#endif
 }
 
 Node::~Node()
 {
+    for (unsigned i = 0; i < m_nbChildren; i++)
+        m_tree->deleteNode(m_children[i]);
     delete[] m_children;
+    delete m_payload;
 }
 
 void Node::setParent(Node* node)
@@ -241,8 +270,10 @@ void Node::setParent(Node* node)
 void Node::insert(Node* node)
 {
     Node* N = findNode(node);
+#ifdef DEBUG
     ALOGV("-> Insert Node %d (%d, %d) in node %d",
           node->m_tid, node->m_minX, node->m_minY, N->m_tid);
+#endif
     N->add(node);
 }
 
@@ -363,8 +394,10 @@ Node* Node::split()
         elementB = m_children[m_nbChildren - 1];
     }
 
+#ifdef DEBUG
     ALOGV("split Node %d, dx: %d dy: %d elem A is %d, elem B is %d",
         m_tid, dx, dy, elementA->m_tid, elementB->m_tid);
+#endif
 
     // Let's use some temporary lists to do the split
     ElementList* listA = m_tree->m_listA;
@@ -401,7 +434,7 @@ Node* Node::split()
     for (unsigned int i = 0; i < listA->m_nbChildren; i++)
         add(listA->m_children[i]);
 
-    Node* NN = new Node(m_tree);
+    Node* NN = Node::create(m_tree);
     for (unsigned int i = 0; i < listB->m_nbChildren; i++)
         NN->add(listB->m_children[i]);
 
@@ -417,8 +450,10 @@ void Node::adjustTree(Node* N, Node* NN)
 {
     if (N->isRoot() && NN) {
         // build new root
-        Node* root = new Node(m_tree);
+        Node* root = Node::create(m_tree);
+#ifdef DEBUG
         ALOGV("-> node %d created as new root", root->m_tid);
+#endif
         root->add(N);
         root->add(NN);
         m_tree->m_root = root;
@@ -437,15 +472,14 @@ static int gNbNodes = 0;
 static int gNbElements = 0;
 #endif
 
+#ifdef DEBUG
 void Node::drawTree(int level)
 {
     if (level == 0) {
         ALOGV("\n*** show tree ***\n");
-#ifdef DEBUG
         gMaxLevel = 0;
         gNbNodes = 0;
         gNbElements = 0;
-#endif
     }
 
     display(level);
@@ -454,7 +488,6 @@ void Node::drawTree(int level)
         m_children[i]->drawTree(level + 1);
     }
 
-#ifdef DEBUG
     if (gMaxLevel < level)
         gMaxLevel = level;
 
@@ -470,14 +503,16 @@ void Node::drawTree(int level)
                gNbNodes, gNbNodes * sizeof(Node), sizeof(Node),
                gNbElements, gNbElements * sizeof(Element), sizeof(Element));
     }
-#endif
 }
+#endif
 
+#ifdef DEBUG
 void Node::display(int level)
 {
     ALOGV("%*sNode %d - %d, %d, %d, %d (%d x %d)",
       2*level, "", m_tid, m_minX, m_minY, m_maxX, m_maxY, m_maxX - m_minX, m_maxY - m_minY);
 }
+#endif
 
 bool Node::overlap(int minx, int miny, int maxx, int maxy)
 {
@@ -490,7 +525,7 @@ bool Node::overlap(int minx, int miny, int maxx, int maxy)
 void Node::search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list)
 {
     if (isElement() && overlap(minx, miny, maxx, maxy))
-        list.append(((Element*)this)->m_payload);
+        list.append(this->m_payload);
 
     for (unsigned int i = 0; i < m_nbChildren; i++) {
         if (m_children[i]->overlap(minx, miny, maxx, maxy))
@@ -516,30 +551,4 @@ void Node::remove(int minx, int miny, int maxx, int maxy)
     }
 }
 
-//////////////////////////////////////////////////////////////////////
-// Element
-
-Element::Element(RTree* tree, int pminx, int pminy, int pmaxx, int pmaxy, WebCore::RecordingData* p)
-    : Node(tree)
-    , m_payload(p)
-{
-    m_minX = pminx;
-    m_minY = pminy;
-    m_maxX = pmaxx;
-    m_maxY = pmaxy;
-    ALOGV("-> New element %d (%d, %d) - (%d x %d)",
-          m_tid, m_minX, m_minY, m_maxX - m_minX, m_maxY - m_minY);
-}
-
-Element::~Element()
-{
-    delete m_payload;
-}
-
-void Element::display(int level)
-{
-    ALOGV("%*selement %d (%d, %d, %d, %d) - (%d x %d)", 2*level, "",
-          m_tid, m_minX, m_minY, m_maxX, m_maxY, m_maxX - m_minX, m_maxY - m_minY);
-}
-
-}
+} // Namespace RTree
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.h b/Source/WebCore/platform/graphics/android/context/RTree.h
index d7df750..6b53d55 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.h
+++ b/Source/WebCore/platform/graphics/android/context/RTree.h
@@ -32,6 +32,8 @@
 
 namespace WebCore {
 
+class LinearAllocator;
+
 class RecordingData {
 public:
     RecordingData(GraphicsOperation::Operation* ops, int orderBy)
@@ -46,7 +48,7 @@ public:
     GraphicsOperation::Operation* m_operation;
 };
 
-}
+} // namespace WebCore
 
 namespace RTree {
 
@@ -67,12 +69,16 @@ public:
     void remove(WebCore::IntRect& clip);
     void display();
 
+    void* allocateNode();
+    void deleteNode(Node* n);
+
 private:
 
     Node* m_root;
     unsigned m_maxChildren;
     ElementList* m_listA;
     ElementList* m_listB;
+    WebCore::LinearAllocator* m_allocator;
 
     friend class Node;
 };
@@ -104,16 +110,26 @@ class Node {
 public:
     static Node* gRoot;
 
-    Node(RTree* t);
-    virtual ~Node();
+    static Node* create(RTree* tree) {
+        return create(tree, 0, 0, 0, 0, 0);
+    }
+
+    static Node* create(RTree* tree, int minx, int miny, int maxx, int maxy,
+                        WebCore::RecordingData* payload) {
+        return new (tree->allocateNode()) Node(tree, minx, miny, maxx, maxy, payload);
+    }
+
+    ~Node();
 
     void insert(Node* n);
     void search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list);
     void remove(int minx, int miny, int maxx, int maxy);
-    void drawTree(int level = 0);
-    virtual void display(int level = 0);
+
+    // Intentionally not implemented as Node* is custom allocated, we don't want to use this
+    void operator delete(void*);
 
 private:
+    Node(RTree* tree, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload);
 
     void setParent(Node* n);
     Node* findNode(Node* n);
@@ -129,7 +145,7 @@ private:
     bool overlap(int minx, int miny, int maxx, int maxy);
     bool inside(int minx, int miny, int maxx, int maxy);
 
-    virtual bool isElement() { return false; }
+    bool isElement() { return m_payload; }
     bool isRoot();
 
 private:
@@ -140,6 +156,8 @@ private:
     Node** m_children;
     unsigned m_nbChildren;
 
+    WebCore::RecordingData* m_payload;
+
 public:
 
     int m_minX;
@@ -148,22 +166,12 @@ public:
     int m_maxY;
 
 #ifdef DEBUG
+    void drawTree(int level = 0);
+    void display(int level = 0);
     unsigned m_tid;
 #endif
 };
 
-class Element : public Node {
-public:
-
-    Element(RTree* tree, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload);
-    virtual ~Element();
-    virtual bool isElement() { return true; }
-
-    virtual void display(int level = 0);
-
-    WebCore::RecordingData* m_payload;
-};
-
-}
+} // namespace RTree
 
 #endif // RTree_h
diff --git a/Source/WebCore/platform/graphics/android/utils/LinearAllocator.cpp b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.cpp
new file mode 100644
index 0000000..bd63c38
--- /dev/null
+++ b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.cpp
@@ -0,0 +1,158 @@
+/*
+ * Copyright 2012, The Android Open Source Project
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *  * Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#define LOG_TAG "LinearAllocator"
+#define LOG_NDEBUG 0
+
+#include "config.h"
+
+#include "LinearAllocator.h"
+
+#include "AndroidLog.h"
+
+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
+
+class LinearAllocator::Page {
+public:
+    Page* next() { return m_nextPage; }
+    void setNext(Page* next) { m_nextPage = next; }
+
+    Page()
+        : m_nextPage(0)
+    {}
+
+    void* start()
+    {
+        return (void*) (((unsigned)this) + sizeof(LinearAllocator::Page));
+    }
+
+    void* end(int pageSize)
+    {
+        return (void*) (((unsigned)start()) + pageSize);
+    }
+
+private:
+    Page(const Page& other) {}
+    Page* m_nextPage;
+};
+
+LinearAllocator::LinearAllocator(size_t allocSize)
+    : m_allocSize(allocSize)
+    , m_allocCount(0)
+    , m_next(0)
+    , m_currentPage(0)
+    , m_pages(0)
+{
+    int usable_page_size = TARGET_PAGE_SIZE - sizeof(LinearAllocator::Page);
+    int pcount = usable_page_size / allocSize;
+    if (pcount < MIN_OBJECT_COUNT)
+        pcount = MIN_OBJECT_COUNT;
+    m_pageSize = pcount * allocSize + sizeof(LinearAllocator::Page);
+}
+
+LinearAllocator::~LinearAllocator(void)
+{
+    if (m_allocCount)
+        ALOGW("Leaked allocations!");
+    IF_ALOGV()
+        ALOGV("Freeing to %dkb", memusage() >> 10);
+    Page* p = m_pages;
+    while (p) {
+        Page* next = p->next();
+        delete p;
+        p = next;
+    }
+}
+
+void* LinearAllocator::start(Page* p)
+{
+    return ((char*)p) + sizeof(Page);
+}
+
+void* LinearAllocator::end(Page* p)
+{
+    return ((char*)p) + m_pageSize;
+}
+
+void LinearAllocator::ensureNext()
+{
+    if (m_next && m_next < end(m_currentPage))
+        return;
+    Page* p = newPage();
+    if (m_currentPage)
+        m_currentPage->setNext(p);
+    m_currentPage = p;
+    if (!m_pages)
+        m_pages = m_currentPage;
+    m_next = start(m_currentPage);
+
+    IF_ALOGV()
+        ALOGV("Allocator grew to %dkb", memusage() >> 10);
+}
+
+unsigned LinearAllocator::memusage()
+{
+    unsigned memusage = 0;
+    Page* p = m_pages;
+    while (p) {
+        memusage += m_pageSize;
+        p = p->next();
+    }
+    return memusage;
+}
+
+void* LinearAllocator::alloc()
+{
+    m_allocCount++;
+    ensureNext();
+    void* ptr = m_next;
+    m_next = ((char*)m_next) + m_allocSize;
+    return ptr;
+}
+
+void LinearAllocator::dealloc(void* ptr)
+{
+    m_allocCount--;
+    if (m_next > start(m_currentPage)) {
+        // If this happened to be the previous allocation, just rewind m_next
+        void* prev = ((char*)m_next) - m_allocSize;
+        if (ptr == prev)
+            m_next = prev;
+    }
+}
+
+LinearAllocator::Page* LinearAllocator::newPage()
+{
+    void* buf = malloc(m_pageSize);
+    return new (buf) Page();
+}
+
+} // namespace WebCore
diff --git a/Source/WebCore/platform/graphics/android/utils/LinearAllocator.h b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.h
new file mode 100644
index 0000000..b0c584b
--- /dev/null
+++ b/Source/WebCore/platform/graphics/android/utils/LinearAllocator.h
@@ -0,0 +1,62 @@
+/*
+ * Copyright 2012, The Android Open Source Project
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *  * Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef LinearAllocator_h
+#define LinearAllocator_h
+
+namespace WebCore {
+
+class LinearAllocator
+{
+public:
+    LinearAllocator(size_t allocSize);
+    ~LinearAllocator();
+
+    void* alloc();
+    void dealloc(void*);
+
+private:
+    LinearAllocator(const LinearAllocator& other);
+
+    class Page;
+
+    Page* newPage();
+    void ensureNext();
+    void* start(Page *p);
+    void* end(Page* p);
+
+    unsigned memusage();
+
+    size_t m_allocSize;
+    size_t m_allocCount;
+    size_t m_pageSize;
+    void* m_next;
+    Page* m_currentPage;
+    Page* m_pages;
+};
+
+} // namespace WebCore
+
+#endif // LinearAllocator_h