1 files changed, 171 insertions, 0 deletions
diff --git a/js/src/ds/LifoAlloc.cpp b/js/src/ds/LifoAlloc.cpp
new file mode 100644
index 000000000..bd1cf7c5e
--- /dev/null
+++ b/js/src/ds/LifoAlloc.cpp
@@ -0,0 +1,171 @@
+/* -*- 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 "ds/LifoAlloc.h"
+
+#include "mozilla/MathAlgorithms.h"
+
+using namespace js;
+
+using mozilla::RoundUpPow2;
+using mozilla::tl::BitSize;
+
+namespace js {
+namespace detail {
+
+BumpChunk*
+BumpChunk::new_(size_t chunkSize)
+{
+    MOZ_ASSERT(RoundUpPow2(chunkSize) == chunkSize);
+    void* mem = js_malloc(chunkSize);
+    if (!mem)
+        return nullptr;
+    BumpChunk* result = new (mem) BumpChunk(chunkSize - sizeof(BumpChunk));
+
+    // We assume that the alignment of sAlign is less than that of
+    // the underlying memory allocator -- creating a new BumpChunk should
+    // always satisfy the sAlign alignment constraint.
+    MOZ_ASSERT(AlignPtr(result->bump) == result->bump);
+    return result;
+}
+
+void
+BumpChunk::delete_(BumpChunk* chunk)
+{
+#ifdef DEBUG
+    // Part of the chunk may have been marked as poisoned/noaccess.  Undo that
+    // before writing the 0xcd bytes.
+    size_t size = sizeof(*chunk) + chunk->bumpSpaceSize;
+    MOZ_MAKE_MEM_UNDEFINED(chunk, size);
+    memset(chunk, 0xcd, size);
+#endif
+    js_free(chunk);
+}
+
+bool
+BumpChunk::canAlloc(size_t n)
+{
+    char* aligned = AlignPtr(bump);
+    char* bumped = aligned + n;
+    return bumped <= limit && bumped > headerBase();
+}
+
+} // namespace detail
+} // namespace js
+
+void
+LifoAlloc::freeAll()
+{
+    while (first) {
+        BumpChunk* victim = first;
+        first = first->next();
+        decrementCurSize(victim->computedSizeOfIncludingThis());
+        BumpChunk::delete_(victim);
+    }
+    first = latest = last = nullptr;
+
+    // Nb: maintaining curSize_ correctly isn't easy.  Fortunately, this is an
+    // excellent sanity check.
+    MOZ_ASSERT(curSize_ == 0);
+}
+
+LifoAlloc::BumpChunk*
+LifoAlloc::getOrCreateChunk(size_t n)
+{
+    if (first) {
+        // Look for existing, unused BumpChunks to satisfy the request.
+        while (latest->next()) {
+            latest = latest->next();
+            latest->resetBump();    // This was an unused BumpChunk on the chain.
+            if (latest->canAlloc(n))
+                return latest;
+        }
+    }
+
+    size_t defaultChunkFreeSpace = defaultChunkSize_ - sizeof(BumpChunk);
+    size_t chunkSize;
+    if (n > defaultChunkFreeSpace) {
+        size_t allocSizeWithHeader = n + sizeof(BumpChunk);
+
+        // Guard for overflow.
+        if (allocSizeWithHeader < n ||
+            (allocSizeWithHeader & (size_t(1) << (BitSize<size_t>::value - 1)))) {
+            return nullptr;
+        }
+
+        chunkSize = RoundUpPow2(allocSizeWithHeader);
+    } else {
+        chunkSize = defaultChunkSize_;
+    }
+
+    // If we get here, we couldn't find an existing BumpChunk to fill the request.
+    MOZ_ASSERT(fallibleScope_, "[OOM] Cannot allocate a new chunk in an infallible scope.");
+    BumpChunk* newChunk = BumpChunk::new_(chunkSize);
+    if (!newChunk)
+        return nullptr;
+    if (!first) {
+        latest = first = last = newChunk;
+    } else {
+        MOZ_ASSERT(latest && !latest->next());
+        latest->setNext(newChunk);
+        latest = last = newChunk;
+    }
+
+    size_t computedChunkSize = newChunk->computedSizeOfIncludingThis();
+    MOZ_ASSERT(computedChunkSize == chunkSize);
+    incrementCurSize(computedChunkSize);
+
+    return newChunk;
+}
+
+void
+LifoAlloc::transferFrom(LifoAlloc* other)
+{
+    MOZ_ASSERT(!markCount);
+    MOZ_ASSERT(!other->markCount);
+
+    if (!other->first)
+        return;
+
+    incrementCurSize(other->curSize_);
+    if (other->isEmpty())
+        appendUnused(other->first, other->last);
+    else
+        appendUsed(other->first, other->latest, other->last);
+    other->first = other->last = other->latest = nullptr;
+    other->curSize_ = 0;
+}
+
+void
+LifoAlloc::transferUnusedFrom(LifoAlloc* other)
+{
+    MOZ_ASSERT(!markCount);
+    MOZ_ASSERT(latest == first);
+
+    if (other->markCount || !other->first)
+        return;
+
+    // Transfer all chunks *after* |latest|.
+
+    if (other->latest->next()) {
+        if (other->latest == other->first) {
+            // We're transferring everything except the first chunk.
+            size_t delta = other->curSize_ - other->first->computedSizeOfIncludingThis();
+            other->decrementCurSize(delta);
+            incrementCurSize(delta);
+        } else {
+            for (BumpChunk* chunk = other->latest->next(); chunk; chunk = chunk->next()) {
+                size_t size = chunk->computedSizeOfIncludingThis();
+                incrementCurSize(size);
+                other->decrementCurSize(size);
+            }
+        }
+
+        appendUnused(other->latest->next(), other->last);
+        other->latest->setNext(nullptr);
+        other->last = other->latest;
+    }
+}