Bug 1074961 - Part 14: Make the ChunkPool list doubly-linked; r=sfink
authorTerrence Cole <terrence@mozilla.com>
Wed, 29 Oct 2014 13:32:22 -0700
changeset 216569 80ca3115ec1c20ed804b0d410504541682af23e6
parent 216568 3b98db519502fd775ea756112bf94c254180d2d7
child 216570 a4441b5f5de82eb144a4f195368ab1e1c8905c9d
push idunknown
push userunknown
push dateunknown
reviewerssfink
bugs1074961
milestone36.0a1
Bug 1074961 - Part 14: Make the ChunkPool list doubly-linked; r=sfink
js/src/gc/GCRuntime.h
js/src/jsapi-tests/moz.build
js/src/jsapi-tests/testGCChunkPool.cpp
js/src/jsgc.cpp
--- a/js/src/gc/GCRuntime.h
+++ b/js/src/gc/GCRuntime.h
@@ -48,32 +48,46 @@ class ChunkPool
     size_t count_;
 
   public:
     ChunkPool() : head_(nullptr), count_(0) {}
 
     size_t count() const { return count_; }
 
     /* Must be called with the GC lock taken. */
-    inline Chunk *get(JSRuntime *rt);
+    Chunk *pop();
 
     /* Must be called either during the GC or with the GC lock taken. */
-    inline void put(Chunk *chunk);
+    void push(Chunk *chunk);
+
+    /* Must be called with the GC lock taken. */
+    Chunk *remove(Chunk *chunk);
+
+#ifdef DEBUG
+    bool contains(Chunk *chunk) const;
+    bool verify() const;
+#endif
 
     class Enum {
       public:
         explicit Enum(ChunkPool &pool) : pool(pool), chunkp(&pool.head_) {}
         bool empty() { return !*chunkp; }
         Chunk *front();
-        inline void popFront();
-        inline void removeAndPopFront();
+        void popFront();
+        void removeAndPopFront();
       private:
         ChunkPool &pool;
         Chunk **chunkp;
     };
+
+  private:
+    // ChunkPool controls external resources with interdependencies on the
+    // JSRuntime and related structs, so must not be copied.
+    ChunkPool(const ChunkPool &) MOZ_DELETE;
+    ChunkPool operator=(const ChunkPool &) MOZ_DELETE;
 };
 
 // Performs extra allocation off the main thread so that when memory is
 // required on the main thread it will already be available and waiting.
 class BackgroundAllocTask : public GCParallelTask
 {
     // Guarded by the GC lock.
     JSRuntime *runtime;
--- a/js/src/jsapi-tests/moz.build
+++ b/js/src/jsapi-tests/moz.build
@@ -29,16 +29,17 @@ UNIFIED_SOURCES += [
     'testException.cpp',
     'testExternalStrings.cpp',
     'testFindSCCs.cpp',
     'testForOfIterator.cpp',
     'testFreshGlobalEvalRedefinition.cpp',
     'testFuncCallback.cpp',
     'testFunctionProperties.cpp',
     'testGCAllocator.cpp',
+    'testGCChunkPool.cpp',
     'testGCExactRooting.cpp',
     'testGCFinalizeCallback.cpp',
     'testGCHeapPostBarriers.cpp',
     'testGCMarking.cpp',
     'testGCOutOfMemory.cpp',
     'testGCStoreBufferRemoval.cpp',
     'testHashTable.cpp',
     'testHashTableInit.cpp',
new file mode 100644
--- /dev/null
+++ b/js/src/jsapi-tests/testGCChunkPool.cpp
@@ -0,0 +1,70 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+* vim: set ts=8 sts=4 et sw=4 tw=99:
+*/
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/Move.h"
+
+#include "gc/GCRuntime.h"
+#include "gc/Heap.h"
+
+#include "jsapi-tests/tests.h"
+
+BEGIN_TEST(testGCChunkPool)
+{
+    const int N = 10;
+    js::gc::ChunkPool pool;
+
+    // Create.
+    for (int i = 0; i < N; ++i) {
+        js::gc::Chunk *chunk = js::gc::Chunk::allocate(rt);
+        CHECK(chunk);
+        pool.push(chunk);
+    }
+    MOZ_ASSERT(pool.verify());
+
+    // Iterate.
+    uint32_t i = 0;
+    for (js::gc::ChunkPool::Enum e(pool); !e.empty(); e.popFront(), ++i)
+        CHECK(e.front());
+    CHECK(i == pool.count());
+    MOZ_ASSERT(pool.verify());
+
+    // Push/Pop.
+    for (int i = 0; i < N; ++i) {
+        js::gc::Chunk *chunkA = pool.pop();
+        js::gc::Chunk *chunkB = pool.pop();
+        js::gc::Chunk *chunkC = pool.pop();
+        pool.push(chunkA);
+        pool.push(chunkB);
+        pool.push(chunkC);
+    }
+    MOZ_ASSERT(pool.verify());
+
+    // Remove.
+    js::gc::Chunk *chunk = nullptr;
+    int offset = N / 2;
+    for (js::gc::ChunkPool::Enum e(pool); !e.empty(); e.popFront(), --offset) {
+        if (offset == 0) {
+            chunk = pool.remove(e.front());
+            break;
+        }
+    }
+    CHECK(chunk);
+    MOZ_ASSERT(!pool.contains(chunk));
+    MOZ_ASSERT(pool.verify());
+    pool.push(chunk);
+
+    // Destruct.
+    js::AutoLockGC lock(rt);
+    for (js::gc::ChunkPool::Enum e(pool); !e.empty();) {
+        js::gc::Chunk *chunk = e.front();
+        e.removeAndPopFront();
+        js::gc::UnmapPages(chunk, js::gc::ChunkSize);
+    }
+
+    return true;
+}
+END_TEST(testGCChunkPool)
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -659,57 +659,117 @@ AllocChunk(JSRuntime *rt)
 
 static inline void
 FreeChunk(JSRuntime *rt, Chunk *p)
 {
     UnmapPages(static_cast<void *>(p), ChunkSize);
 }
 
 /* Must be called with the GC lock taken. */
-inline Chunk *
-ChunkPool::get(JSRuntime *rt)
-{
-    Chunk *chunk = head_;
-    if (!chunk) {
-        MOZ_ASSERT(!count_);
+Chunk *
+ChunkPool::pop()
+{
+    MOZ_ASSERT(bool(head_) == bool(count_));
+    if (!count_)
         return nullptr;
-    }
-
-    MOZ_ASSERT(count_);
-    head_ = chunk->info.next;
-    --count_;
-    return chunk;
+    return remove(head_);
 }
 
 /* Must be called either during the GC or with the GC lock taken. */
-inline void
-ChunkPool::put(Chunk *chunk)
-{
+void
+ChunkPool::push(Chunk *chunk)
+{
+    MOZ_ASSERT(!chunk->info.next);
+    MOZ_ASSERT(!chunk->info.prevp);
+    MOZ_ASSERT_IF(head_, head_->info.prevp == &head_);
+
     chunk->info.age = 0;
     chunk->info.next = head_;
+    chunk->info.prevp = &head_;
+    if (head_)
+        head_->info.prevp = &chunk->info.next;
     head_ = chunk;
-    count_++;
-}
-
-inline Chunk *
+    ++count_;
+
+    MOZ_ASSERT(verify());
+}
+
+/* Must be called with the GC lock taken. */
+Chunk *
+ChunkPool::remove(Chunk *chunk)
+{
+    MOZ_ASSERT(count_ > 0);
+    MOZ_ASSERT(contains(chunk));
+
+    *chunk->info.prevp = chunk->info.next;
+    if (chunk->info.next) {
+        MOZ_ASSERT(chunk->info.next->info.prevp == &chunk->info.next);
+        chunk->info.next->info.prevp = chunk->info.prevp;
+    }
+    chunk->info.next = nullptr;
+    chunk->info.prevp = nullptr;
+    --count_;
+
+    MOZ_ASSERT(count_ >= 0);
+    MOZ_ASSERT(verify());
+    return chunk;
+}
+
+#ifdef DEBUG
+bool
+ChunkPool::contains(Chunk *chunk) const
+{
+    Chunk *const *prevp = &head_;
+    Chunk *cursor = head_;
+    while (cursor) {
+        MOZ_ASSERT(cursor->info.prevp == prevp);
+        if (cursor == chunk)
+            return true;
+        prevp = &cursor->info.next;
+        cursor = cursor->info.next;
+    }
+    return false;
+}
+
+bool
+ChunkPool::verify() const
+{
+    uint32_t count = 0;
+    Chunk *const *expected_prevp = &head_;
+    Chunk *cursor = head_;
+    while (cursor) {
+        MOZ_ASSERT(cursor->info.prevp);
+        MOZ_ASSERT(cursor->info.prevp == expected_prevp);
+        MOZ_ASSERT(*cursor->info.prevp == cursor);
+        MOZ_ASSERT_IF(cursor->info.next, cursor->info.next->info.prevp == &cursor->info.next);
+        expected_prevp = &cursor->info.next;
+        cursor = cursor->info.next;
+        ++count;
+    }
+    MOZ_ASSERT(count_ == count);
+    return true;
+}
+#endif
+
+Chunk *
 ChunkPool::Enum::front()
 {
     Chunk *chunk = *chunkp;
     MOZ_ASSERT_IF(chunk, pool.count() != 0);
     return chunk;
 }
 
-inline void
+void
 ChunkPool::Enum::popFront()
 {
     MOZ_ASSERT(!empty());
     chunkp = &front()->info.next;
 }
 
-inline void
+void
 ChunkPool::Enum::removeAndPopFront()
 {
     MOZ_ASSERT(!empty());
     *chunkp = front()->info.next;
     --pool.count_;
 }
 
 Chunk *
@@ -782,17 +842,17 @@ Chunk::allocate(JSRuntime *rt)
     if (!chunk)
         return nullptr;
     chunk->init(rt);
     rt->gc.stats.count(gcstats::STAT_NEW_CHUNK);
     return chunk;
 }
 
 /* Must be called with the GC lock taken. */
-inline void
+void
 GCRuntime::releaseChunk(Chunk *chunk)
 {
     MOZ_ASSERT(chunk);
     prepareToFreeChunk(chunk->info);
     FreeChunk(rt, chunk);
 }
 
 inline void
@@ -835,16 +895,18 @@ Chunk::init(JSRuntime *rt)
     /*
      * Decommit the arenas. We do this after poisoning so that if the OS does
      * not have to recycle the pages, we still get the benefit of poisoning.
      */
     decommitAllArenas(rt);
 
     /* Initialize the chunk info. */
     info.age = 0;
+    info.next = nullptr;
+    info.prevp = nullptr;
     info.trailer.storeBuffer = nullptr;
     info.trailer.location = ChunkLocationBitTenuredHeap;
     info.trailer.runtime = rt;
 
     /* The rest of info fields are initialized in pickChunk. */
 }
 
 inline Chunk **
@@ -1020,17 +1082,17 @@ Chunk::releaseArena(JSRuntime *rt, Arena
 }
 
 void
 GCRuntime::moveChunkToFreePool(Chunk *chunk, const AutoLockGC &lock)
 {
     MOZ_ASSERT(chunk->unused());
     MOZ_ASSERT(chunkSet.has(chunk));
     chunkSet.remove(chunk);
-    emptyChunks(lock).put(chunk);
+    emptyChunks(lock).push(chunk);
 }
 
 inline bool
 GCRuntime::wantBackgroundAllocation(const AutoLockGC &lock) const
 {
     // To minimize memory waste, we do not want to run the background chunk
     // allocation if we already have some empty chunks or when the runtime has
     // a small heap size (and therefore likely has a small growth rate).
@@ -1079,17 +1141,17 @@ Chunk *
 GCRuntime::pickChunk(const AutoLockGC &lock,
                      AutoMaybeStartBackgroundAllocation &maybeStartBackgroundAllocation)
 {
     Chunk **listHeadp = getAvailableChunkList();
     Chunk *chunk = *listHeadp;
     if (chunk)
         return chunk;
 
-    chunk = emptyChunks(lock).get(rt);
+    chunk = emptyChunks(lock).pop();
     if (!chunk) {
         chunk = Chunk::allocate(rt);
         if (!chunk)
             return nullptr;
         MOZ_ASSERT(chunk->info.numArenasFreeCommitted == 0);
     }
 
     MOZ_ASSERT(chunk->unused());
@@ -3649,17 +3711,17 @@ BackgroundAllocTask::run()
     while (!cancel_ && runtime->gc.wantBackgroundAllocation(lock)) {
         Chunk *chunk;
         {
             AutoUnlockGC unlock(runtime);
             chunk = Chunk::allocate(runtime);
             if (!chunk)
                 break;
         }
-        chunkPool_.put(chunk);
+        chunkPool_.push(chunk);
     }
 }
 
 void
 GCHelperState::startBackgroundSweep()
 {
     MOZ_ASSERT(CanUseExtraThreads());