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 240883 80ca3115ec1c20ed804b0d410504541682af23e6
parent 240882 3b98db519502fd775ea756112bf94c254180d2d7
child 240884 a4441b5f5de82eb144a4f195368ab1e1c8905c9d
push id4311
push userraliiev@mozilla.com
push dateMon, 12 Jan 2015 19:37:41 +0000
treeherdermozilla-beta@150c9fed433b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1074961
milestone36.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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());