[oilpan]: optimize the way we allocate persistent handles in wrappers.

Source/platform/heap/Handle.h

Index: Source/platform/heap/Handle.h
diff --git a/Source/platform/heap/Handle.h b/Source/platform/heap/Handle.h
index 62c7734053274e02f73723c59bfffb6f39cc9841..5e17013c7faf82ed97e745fffa887dd862ed4d49 100644
--- a/Source/platform/heap/Handle.h
+++ b/Source/platform/heap/Handle.h
@@ -150,6 +150,207 @@ private:
     friend class ThreadState;
 };
 
+
+const int wrapperPersistentsPerRegion = 256;
+const size_t wrapperPersistentOffsetMask = ~static_cast<size_t>(3);
+const size_t wrapperPersistentLiveBitMask = 1;
+
+class WrapperPersistentNode {
+public:
+    explicit WrapperPersistentNode(const WrapperPersistentNode& otherref)
+    {
+        WrapperPersistentNode* other = const_cast<WrapperPersistentNode*>(&otherref);
+        m_raw = other->m_raw;
+        m_offset = other->m_offset;
+    }
+
+    bool isAlive() { return m_offset & wrapperPersistentLiveBitMask; }
+
+    WrapperPersistentRegion* region()
+    {
+        return reinterpret_cast<WrapperPersistentRegion*>(
+            reinterpret_cast<Address>(this) - (m_offset & wrapperPersistentOffsetMask));
+    }
+
+    virtual ~WrapperPersistentNode()
+    {
+        m_offset &= ~wrapperPersistentLiveBitMask;
+    }
+
+    virtual void trace(Visitor* visitor) { }

[haraken, 2014/09/02 05:22:05]

You won't need this. You can just define non-virtual trace method in
WrapperPersistent.

[wibling-chromium, 2014/09/02 11:19:37]

I do need this, since I am calling m_entries[i].trace(visitor) which is a
WrapperPersistentNode and I want it to dispatch to the instantiated
WrapperPersistent<T> subclass in order to cast it to the correct type before
calling mark.

+
+protected:
+    WrapperPersistentNode() : m_raw(0), m_offset(0) { }
+
+    explicit WrapperPersistentNode(void* raw)
+    {

[haraken, 2014/09/02 05:22:05]

Can we add ASSERT(!m_raw) ?

[wibling-chromium, 2014/09/02 11:19:37]

Done.

+        m_raw = raw;
+        m_offset |= wrapperPersistentLiveBitMask;

[zerny-chromium, 2014/09/01 14:13:37]

m_offset is uninitialized here. Maybe just m_offset = wrapper...

[wibling-chromium, 2014/09/02 11:19:37]

m_offset has already been initialized here to have an offset to the base of the
region. This happens in the WrapperPersistentRegion's constructor which calls
the below constructor to set up the fixed offset and the pointer to the next
free entry.
I agree this is a bit confusing, ie. that we essentially call a constructor to
setup free entry and a second constructor when the entry is used by a wrapper. I
have changed it such that the WrapperPersistentRegion's constructor calls an
initSlot method to setup the entry and the constructor is only called when the
entry is allocated/constructed by a wrapper. 

+    }
+
+    WrapperPersistentNode(size_t offset, WrapperPersistentNode* nextFree)
+    {
+        ASSERT(!(offset & ~wrapperPersistentOffsetMask));
+        m_raw = reinterpret_cast<void*>(nextFree);
+        m_offset = offset;
+    }
+
+protected:
+    void* m_raw;

[Mads Ager (chromium), 2014/09/01 13:52:46]

Add a comment that m_raw is used to chain freelist entries? Maybe add some
helper methods for when m_raw is used as a freelist entry to make the code
easier to read: setNextFree, nextFree?

[wibling-chromium, 2014/09/02 11:19:38]

Done.

+
+private:
+    size_t m_offset;

[haraken, 2014/09/02 05:22:05]

m_offset => m_region or m_regionHead

[haraken, 2014/09/02 05:22:05]

Add a comment about the memory structure of m_offset.

[wibling-chromium, 2014/09/02 11:19:37]

Changed it to m_regionOffset.

[wibling-chromium, 2014/09/02 11:19:37]

Done.

+
+    friend class WrapperPersistentRegion;
+};
+
+template<typename T>
+class WrapperPersistent : public WrapperPersistentNode {

[haraken, 2014/09/02 05:22:05]

Add FINAL.

[wibling-chromium, 2014/09/02 11:19:37]

Done.

+public:
+    WrapperPersistent() : WrapperPersistentNode(0) { }
+    WrapperPersistent(std::nullptr_t) : WrapperPersistentNode(0) { }
+    WrapperPersistent(T* raw) : WrapperPersistentNode(raw) { }
+    WrapperPersistent(T& raw) : WrapperPersistentNode(&raw) { }
+
+    void* operator new(size_t);
+    void operator delete(void*);
+
+    virtual void trace(Visitor* visitor) { visitor->mark(static_cast<T*>(m_raw)); }
+};
+
+class WrapperPersistentRegion {
+public:
+    WrapperPersistentRegion()
+    {
+        WrapperPersistentNode* nextFree = 0;
+        for (int i = wrapperPersistentsPerRegion-1; i >= 0; --i) {

[Mads Ager (chromium), 2014/09/01 13:52:46]

Nit: space around '-'

[wibling-chromium, 2014/09/02 11:19:37]

Done.

+            size_t offset = reinterpret_cast<Address>(&m_entries[i]) - reinterpret_cast<Address>(this);
+            new (&m_entries[i]) WrapperPersistentNode(offset, nextFree);
+            nextFree = &m_entries[i];
+        }
+        m_prev = 0;
+        m_next = 0;
+        m_free = nextFree;
+        m_count = 0;
+    }
+
+    void* allocate()

[Erik Corry, 2014/09/01 13:40:41]

I think you want this to be inlined, and you expect the 'if' to be almost always
true.

I would suggest

if (!m_free)
  return out_of_line_function(); // Define this in the C++ file so it is not
inlined.
...

[wibling-chromium, 2014/09/02 11:19:38]

Done.

+    {
+        if (m_free) {
+            // We have a free persistent in this region.
+            WrapperPersistentNode* free = m_free;
+            m_free = reinterpret_cast<WrapperPersistentNode*>(free->m_raw);

[Mads Ager (chromium), 2014/09/01 13:52:46]

Maybe wrap this in a method: free->nextFree().

Then we can have an assert in nextFree that the live bit is not set on the
WrapperPersistentNode* that is returned?

[wibling-chromium, 2014/09/02 11:19:37]

I have added a takeSlot and freeSlot method in addition to the initSlot method I
described above.

+            free->m_raw = 0;
+            m_count++;
+            return reinterpret_cast<void*>(free);
+        }
+        // Otherwise try next region if one exists.
+        if (m_next)
+            return m_next->allocate();

[Mads Ager (chromium), 2014/09/01 13:52:46]

Can we use iteration iteration from the outside instead of recursion? Maybe I
should trust the compiler more to do tail-call optimization?

[wibling-chromium, 2014/09/02 11:19:37]

Done.

+        return 0;
+    }
+
+    void free(WrapperPersistentNode* object)
+    {
+        ASSERT(object);
+        ASSERT(!object->isAlive());
+        object->m_raw = m_free;
+        m_free = object;
+        m_count--;
+        if (!m_count)
+            ThreadState::current()->removeWrapperPersistentRegion(this);
+    }
+
+    void trace(Visitor* visitor)
+    {
+        size_t live = 0;
+        for (int i = 0; i < wrapperPersistentsPerRegion && live < m_count; ++i) {
+            if (m_entries[i].isAlive()) {
+                m_entries[i].trace(visitor);
+                live++;
+            }
+        }
+        if (m_next)
+            m_next->trace(visitor);

[Mads Ager (chromium), 2014/09/01 13:52:46]

Can we use iteration from the outside instead of recursion?

for (WrapperPersistentRegion* current = ...; current; current = current->next())
{
  current->trace();
}

With a block size of 256 we can probably get a lot of blocks (at least on
artificial benchmarks). Maybe I'm too old fashioned. I'm worried that the
compiler will not perform tail call optimization here and that we have a risk of
blowing out the stack.

[wibling-chromium, 2014/09/02 11:19:37]

Done.

+    }
+
+    size_t count() const { return m_count; }
+
+    bool removeIfNotLast(WrapperPersistentRegion** headPtr)

[haraken, 2014/09/02 05:22:05]

Shall we move not-performance-sensitive methods to cpp files? It's not nice to
increase Handle.h :)

[wibling-chromium, 2014/09/02 11:19:38]

Done.

+    {
+        // We are the last region in the list if both the region's m_prev and
+        // m_next are 0.
+        if (m_prev == 0 && m_next == 0)
+            return false;
+        if (m_prev) {

[haraken, 2014/09/02 05:22:05]

Can we just call removeHead() here?

[wibling-chromium, 2014/09/02 11:19:37]

No, that is always removing the head entry via the threadState head pointer.

+            m_prev->m_next = m_next;
+        } else {
+            ASSERT(*headPtr == this);
+            *headPtr = m_next;
+        }
+        if (m_next)
+            m_next->m_prev = m_prev;
+        m_prev = 0;
+        m_next = 0;
+        return true;
+    }
+
+    static void insertHead(WrapperPersistentRegion** headPtr, WrapperPersistentRegion* newHead)
+    {
+        ASSERT(headPtr);
+        WrapperPersistentRegion* oldHead = *headPtr;
+        if (oldHead) {
+            ASSERT(!oldHead->m_prev);
+            oldHead->m_prev = newHead;
+        }
+        newHead->m_prev = 0;
+        newHead->m_next = oldHead;
+        *headPtr = newHead;
+    }
+
+    static WrapperPersistentRegion* removeHead(WrapperPersistentRegion** headPtr)
+    {
+        // We only call this if there is at least one element in the list.
+        ASSERT(headPtr && *headPtr);
+        WrapperPersistentRegion* oldHead = *headPtr;
+        ASSERT(!oldHead->m_prev);
+        *headPtr = oldHead->m_next;
+        oldHead->m_next = 0;
+        ASSERT(!(*headPtr) || (*headPtr)->m_prev == oldHead);
+        if (*headPtr)
+            (*headPtr)->m_prev = 0;
+        return oldHead;
+    }
+
+private:
+    WrapperPersistentRegion* m_prev;
+    WrapperPersistentRegion* m_next;

[haraken, 2014/09/02 05:22:05]

Shall we override 'operator new=' in a private section? If it's used, we'll end
up breaking the doubly-linked list unexpectedly.

[wibling-chromium, 2014/09/02 11:19:37]

Are you referring to the assignment operator? If so I have made both the
WrapperPersistentRegion and WrapperPersistentNode non-copyable.

+    WrapperPersistentNode* m_free;
+    size_t m_count;
+    WrapperPersistentNode m_entries[wrapperPersistentsPerRegion];
+};
+
+template<typename T>
+void* WrapperPersistent<T>::operator new(size_t size)
+{
+    ThreadState* state = ThreadState::current();
+    WrapperPersistentRegion* region = state->wrapperRoots();
+    void* persistent = region->allocate();
+    if (!persistent) {
+        region = state->addWrapperPersistentRegion();
+        persistent = region->allocate();
+    }
+    ASSERT(persistent);
+    return persistent;
+}
+
+template<typename T>
+void WrapperPersistent<T>::operator delete(void* object)
+{
+    WrapperPersistentNode* persistent = static_cast<WrapperPersistentNode*>(object);
+    persistent->region()->free(persistent);
+}
+
 // RootsAccessor for Persistent that provides access to thread-local list
 // of persistent handles. Can only be used to create handles that
 // are constructed and destructed on the same thread.