1 files changed, 426 insertions, 0 deletions
diff --git a/js/src/ds/LifoAlloc.cpp b/js/src/ds/LifoAlloc.cpp
new file mode 100644
index 0000000000..c1e4869ba2
--- /dev/null
+++ b/js/src/ds/LifoAlloc.cpp
@@ -0,0 +1,426 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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/Likely.h"
+#include "mozilla/MathAlgorithms.h"
+
+#include <algorithm>
+
+#ifdef LIFO_CHUNK_PROTECT
+#  include "gc/Memory.h"
+#endif
+
+using namespace js;
+
+using mozilla::RoundUpPow2;
+using mozilla::tl::BitSize;
+
+namespace js {
+namespace detail {
+
+/* static */
+UniquePtr<BumpChunk> BumpChunk::newWithCapacity(size_t size) {
+  MOZ_DIAGNOSTIC_ASSERT(size >= sizeof(BumpChunk));
+  void* mem = js_malloc(size);
+  if (!mem) {
+    return nullptr;
+  }
+
+  UniquePtr<BumpChunk> result(new (mem) BumpChunk(size));
+
+  // We assume that the alignment of LIFO_ALLOC_ALIGN is less than that of the
+  // underlying memory allocator -- creating a new BumpChunk should always
+  // satisfy the LIFO_ALLOC_ALIGN alignment constraint.
+  MOZ_ASSERT(AlignPtr(result->begin()) == result->begin());
+  return result;
+}
+
+#ifdef LIFO_CHUNK_PROTECT
+
+static uint8_t* AlignPtrUp(uint8_t* ptr, uintptr_t align) {
+  MOZ_ASSERT(mozilla::IsPowerOfTwo(align));
+  uintptr_t uptr = uintptr_t(ptr);
+  uintptr_t diff = uptr & (align - 1);
+  diff = (align - diff) & (align - 1);
+  uptr = uptr + diff;
+  return (uint8_t*)uptr;
+}
+
+static uint8_t* AlignPtrDown(uint8_t* ptr, uintptr_t align) {
+  MOZ_ASSERT(mozilla::IsPowerOfTwo(align));
+  uintptr_t uptr = uintptr_t(ptr);
+  uptr = uptr & ~(align - 1);
+  return (uint8_t*)uptr;
+}
+
+void BumpChunk::setReadOnly() {
+  uintptr_t pageSize = gc::SystemPageSize();
+  // The allocated chunks might not be aligned on page boundaries. This code
+  // is used to ensure that we are changing the memory protection of pointers
+  // which are within the range of the BumpChunk, or that the range formed by
+  // [b .. e] is empty.
+  uint8_t* b = base();
+  uint8_t* e = capacity_;
+  b = AlignPtrUp(b, pageSize);
+  e = AlignPtrDown(e, pageSize);
+  if (e <= b) {
+    return;
+  }
+  gc::MakePagesReadOnly(b, e - b);
+}
+
+void BumpChunk::setReadWrite() {
+  uintptr_t pageSize = gc::SystemPageSize();
+  // The allocated chunks might not be aligned on page boundaries. This code
+  // is used to ensure that we are changing the memory protection of pointers
+  // which are within the range of the BumpChunk, or that the range formed by
+  // [b .. e] is empty.
+  uint8_t* b = base();
+  uint8_t* e = capacity_;
+  b = AlignPtrUp(b, pageSize);
+  e = AlignPtrDown(e, pageSize);
+  if (e <= b) {
+    return;
+  }
+  gc::UnprotectPages(b, e - b);
+}
+
+#endif
+
+}  // namespace detail
+}  // namespace js
+
+void LifoAlloc::reset(size_t defaultChunkSize) {
+  MOZ_ASSERT(mozilla::IsPowerOfTwo(defaultChunkSize));
+
+  while (!chunks_.empty()) {
+    chunks_.popFirst();
+  }
+  while (!oversize_.empty()) {
+    oversize_.popFirst();
+  }
+  while (!unused_.empty()) {
+    unused_.popFirst();
+  }
+  defaultChunkSize_ = defaultChunkSize;
+  oversizeThreshold_ = defaultChunkSize;
+  markCount = 0;
+  curSize_ = 0;
+  smallAllocsSize_ = 0;
+}
+
+void LifoAlloc::freeAll() {
+  // When free-ing all chunks, we can no longer determine which chunks were
+  // transferred and which were not, so simply clear the heuristic to zero
+  // right away.
+  smallAllocsSize_ = 0;
+
+  while (!chunks_.empty()) {
+    UniqueBumpChunk bc = chunks_.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+  while (!oversize_.empty()) {
+    UniqueBumpChunk bc = oversize_.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+  while (!unused_.empty()) {
+    UniqueBumpChunk bc = unused_.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+
+  // Nb: maintaining curSize_ correctly isn't easy.  Fortunately, this is an
+  // excellent sanity check.
+  MOZ_ASSERT(curSize_ == 0);
+}
+
+// Round at the same page granularity used by malloc.
+static size_t MallocGoodSize(size_t aSize) {
+#if defined(MOZ_MEMORY)
+  return malloc_good_size(aSize);
+#else
+  return aSize;
+#endif
+}
+
+// Heuristic to choose the size of the next BumpChunk for small allocations.
+// `start` is the size of the first chunk. `used` is the total size of all
+// BumpChunks in this LifoAlloc so far.
+static size_t NextSize(size_t start, size_t used) {
+  // Double the size, up to 1 MB.
+  const size_t mb = 1 * 1024 * 1024;
+  if (used < mb) {
+    return std::max(start, used);
+  }
+
+  // After 1 MB, grow more gradually, to waste less memory.
+  // The sequence (in megabytes) begins:
+  // 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, ...
+  return RoundUp(used / 8, mb);
+}
+
+LifoAlloc::UniqueBumpChunk LifoAlloc::newChunkWithCapacity(size_t n,
+                                                           bool oversize) {
+  MOZ_ASSERT(fallibleScope_,
+             "[OOM] Cannot allocate a new chunk in an infallible scope.");
+
+  // Compute the size which should be requested in order to be able to fit |n|
+  // bytes in a newly allocated chunk, or default to |defaultChunkSize_|.
+
+  size_t minSize;
+  if (MOZ_UNLIKELY(!detail::BumpChunk::allocSizeWithRedZone(n, &minSize) ||
+                   (minSize & (size_t(1) << (BitSize<size_t>::value - 1))))) {
+    return nullptr;
+  }
+
+  // Note: When computing chunkSize growth, we only are interested in chunks
+  // used for small allocations. This excludes unused chunks, oversized chunks,
+  // and chunks transferred in from another LifoAlloc.
+  MOZ_ASSERT(curSize_ >= smallAllocsSize_);
+  const size_t chunkSize = (oversize || minSize > defaultChunkSize_)
+                               ? MallocGoodSize(minSize)
+                               : NextSize(defaultChunkSize_, smallAllocsSize_);
+
+  // Create a new BumpChunk, and allocate space for it.
+  UniqueBumpChunk result = detail::BumpChunk::newWithCapacity(chunkSize);
+  if (!result) {
+    return nullptr;
+  }
+  MOZ_ASSERT(result->computedSizeOfIncludingThis() == chunkSize);
+  return result;
+}
+
+LifoAlloc::UniqueBumpChunk LifoAlloc::getOrCreateChunk(size_t n) {
+  // Look for existing unused BumpChunks to satisfy the request, and pick the
+  // first one which is large enough, and move it into the list of used
+  // chunks.
+  if (!unused_.empty()) {
+    if (unused_.begin()->canAlloc(n)) {
+      return unused_.popFirst();
+    }
+
+    BumpChunkList::Iterator e(unused_.end());
+    for (BumpChunkList::Iterator i(unused_.begin()); i->next() != e.get();
+         ++i) {
+      detail::BumpChunk* elem = i->next();
+      MOZ_ASSERT(elem->empty());
+      if (elem->canAlloc(n)) {
+        BumpChunkList temp = unused_.splitAfter(i.get());
+        UniqueBumpChunk newChunk = temp.popFirst();
+        unused_.appendAll(std::move(temp));
+        return newChunk;
+      }
+    }
+  }
+
+  // Allocate a new BumpChunk with enough space for the next allocation.
+  UniqueBumpChunk newChunk = newChunkWithCapacity(n, false);
+  if (!newChunk) {
+    return newChunk;
+  }
+  incrementCurSize(newChunk->computedSizeOfIncludingThis());
+  return newChunk;
+}
+
+void* LifoAlloc::allocImplColdPath(size_t n) {
+  void* result;
+  UniqueBumpChunk newChunk = getOrCreateChunk(n);
+  if (!newChunk) {
+    return nullptr;
+  }
+
+  // This new chunk is about to be used for small allocations.
+  smallAllocsSize_ += newChunk->computedSizeOfIncludingThis();
+
+  // Since we just created a large enough chunk, this can't fail.
+  chunks_.append(std::move(newChunk));
+  result = chunks_.last()->tryAlloc(n);
+  MOZ_ASSERT(result);
+  return result;
+}
+
+void* LifoAlloc::allocImplOversize(size_t n) {
+  void* result;
+  UniqueBumpChunk newChunk = newChunkWithCapacity(n, true);
+  if (!newChunk) {
+    return nullptr;
+  }
+  incrementCurSize(newChunk->computedSizeOfIncludingThis());
+
+  // Since we just created a large enough chunk, this can't fail.
+  oversize_.append(std::move(newChunk));
+  result = oversize_.last()->tryAlloc(n);
+  MOZ_ASSERT(result);
+  return result;
+}
+
+bool LifoAlloc::ensureUnusedApproximateColdPath(size_t n, size_t total) {
+  for (detail::BumpChunk& bc : unused_) {
+    total += bc.unused();
+    if (total >= n) {
+      return true;
+    }
+  }
+
+  UniqueBumpChunk newChunk = newChunkWithCapacity(n, false);
+  if (!newChunk) {
+    return false;
+  }
+  incrementCurSize(newChunk->computedSizeOfIncludingThis());
+  unused_.pushFront(std::move(newChunk));
+  return true;
+}
+
+LifoAlloc::Mark LifoAlloc::mark() {
+  markCount++;
+  Mark res;
+  if (!chunks_.empty()) {
+    res.chunk = chunks_.last()->mark();
+  }
+  if (!oversize_.empty()) {
+    res.oversize = oversize_.last()->mark();
+  }
+  return res;
+}
+
+void LifoAlloc::release(Mark mark) {
+  markCount--;
+#ifdef DEBUG
+  auto assertIsContained = [](const detail::BumpChunk::Mark& m,
+                              BumpChunkList& list) {
+    if (m.markedChunk()) {
+      bool contained = false;
+      for (const detail::BumpChunk& chunk : list) {
+        if (&chunk == m.markedChunk() && chunk.contains(m)) {
+          contained = true;
+          break;
+        }
+      }
+      MOZ_ASSERT(contained);
+    }
+  };
+  assertIsContained(mark.chunk, chunks_);
+  assertIsContained(mark.oversize, oversize_);
+#endif
+
+  BumpChunkList released;
+  auto cutAtMark = [&released](const detail::BumpChunk::Mark& m,
+                               BumpChunkList& list) {
+    // Move the blocks which are after the mark to the set released chunks.
+    if (!m.markedChunk()) {
+      released = std::move(list);
+    } else {
+      released = list.splitAfter(m.markedChunk());
+    }
+
+    // Release everything which follows the mark in the last chunk.
+    if (!list.empty()) {
+      list.last()->release(m);
+    }
+  };
+
+  // Release the content of all the blocks which are after the marks, and keep
+  // blocks as unused.
+  cutAtMark(mark.chunk, chunks_);
+  for (detail::BumpChunk& bc : released) {
+    bc.release();
+
+    // Chunks moved from (after a mark) in chunks_ to unused_ are no longer
+    // considered small allocations.
+    smallAllocsSize_ -= bc.computedSizeOfIncludingThis();
+  }
+  unused_.appendAll(std::move(released));
+
+  // Free the content of all the blocks which are after the marks.
+  cutAtMark(mark.oversize, oversize_);
+  while (!released.empty()) {
+    UniqueBumpChunk bc = released.popFirst();
+    decrementCurSize(bc->computedSizeOfIncludingThis());
+  }
+}
+
+void LifoAlloc::steal(LifoAlloc* other) {
+  MOZ_ASSERT(!other->markCount);
+  MOZ_DIAGNOSTIC_ASSERT(unused_.empty());
+  MOZ_DIAGNOSTIC_ASSERT(chunks_.empty());
+  MOZ_DIAGNOSTIC_ASSERT(oversize_.empty());
+
+  // Copy everything from |other| to |this| except for |peakSize_|, which
+  // requires some care.
+  chunks_ = std::move(other->chunks_);
+  oversize_ = std::move(other->oversize_);
+  unused_ = std::move(other->unused_);
+  markCount = other->markCount;
+  defaultChunkSize_ = other->defaultChunkSize_;
+  oversizeThreshold_ = other->oversizeThreshold_;
+  curSize_ = other->curSize_;
+  peakSize_ = std::max(peakSize_, other->peakSize_);
+  smallAllocsSize_ = other->smallAllocsSize_;
+#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
+  fallibleScope_ = other->fallibleScope_;
+#endif
+
+  other->reset(defaultChunkSize_);
+}
+
+void LifoAlloc::transferFrom(LifoAlloc* other) {
+  MOZ_ASSERT(!markCount);
+  MOZ_ASSERT(!other->markCount);
+
+  // Transferred chunks are not counted as part of |smallAllocsSize| as this
+  // could introduce bias in the |NextSize| heuristics, leading to
+  // over-allocations in *this* LifoAlloc. As well, to avoid interference with
+  // small allocations made with |this|, the last chunk of the |chunks_| list
+  // should remain the last chunk. Therefore, the transferred chunks are
+  // prepended to the |chunks_| list.
+  incrementCurSize(other->curSize_);
+
+  appendUnused(std::move(other->unused_));
+  chunks_.prependAll(std::move(other->chunks_));
+  oversize_.prependAll(std::move(other->oversize_));
+  other->curSize_ = 0;
+  other->smallAllocsSize_ = 0;
+}
+
+void LifoAlloc::transferUnusedFrom(LifoAlloc* other) {
+  MOZ_ASSERT(!markCount);
+
+  size_t size = 0;
+  for (detail::BumpChunk& bc : other->unused_) {
+    size += bc.computedSizeOfIncludingThis();
+  }
+
+  appendUnused(std::move(other->unused_));
+  incrementCurSize(size);
+  other->decrementCurSize(size);
+}
+
+#ifdef LIFO_CHUNK_PROTECT
+void LifoAlloc::setReadOnly() {
+  for (detail::BumpChunk& bc : chunks_) {
+    bc.setReadOnly();
+  }
+  for (detail::BumpChunk& bc : oversize_) {
+    bc.setReadOnly();
+  }
+  for (detail::BumpChunk& bc : unused_) {
+    bc.setReadOnly();
+  }
+}
+
+void LifoAlloc::setReadWrite() {
+  for (detail::BumpChunk& bc : chunks_) {
+    bc.setReadWrite();
+  }
+  for (detail::BumpChunk& bc : oversize_) {
+    bc.setReadWrite();
+  }
+  for (detail::BumpChunk& bc : unused_) {
+    bc.setReadWrite();
+  }
+}
+#endif