Bug 1083101 - Add a memory arena to Moz2D. r=jrmuizel
authorNicolas Silva <nsilva@mozilla.com>
Thu, 24 Sep 2015 17:34:43 +0200
changeset 264229 2fd5cfcea4e567fa9dc3e200c7b675b19d97c290
parent 264228 e2149155361cd5050a3d77e989d34b41989fb564
child 264230 bba6f89ab775a38e7b8af462b18c2e6375267109
push id65565
push usernsilva@mozilla.com
push dateThu, 24 Sep 2015 15:36:03 +0000
treeherdermozilla-inbound@c20fd7506bb7 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjrmuizel
bugs1083101
milestone44.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 1083101 - Add a memory arena to Moz2D. r=jrmuizel
gfx/2d/IterableArena.h
gfx/2d/moz.build
gfx/tests/gtest/TestArena.cpp
gfx/tests/gtest/moz.build
new file mode 100644
--- /dev/null
+++ b/gfx/2d/IterableArena.h
@@ -0,0 +1,193 @@
+/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * 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/. */
+
+#ifndef MOZILLA_GFX_ITERABLEARENA_H_
+#define MOZILLA_GFX_ITERABLEARENA_H_
+
+#include "mozilla/Move.h"
+#include "mozilla/Assertions.h"
+#include "mozilla/gfx/Logging.h"
+
+#include <string.h>
+#include <vector>
+#include <stdint.h>
+#include <stdio.h>
+
+namespace mozilla {
+namespace gfx {
+
+/// A simple pool allocator for plain data structures.
+///
+/// Beware that the pool will not attempt to run the destructors. It is the
+/// responsibility of the user of this class to either use objects with no
+/// destructor or to manually call the allocated objects destructors.
+/// If the pool is growable, its allocated objects must be safely moveable in
+/// in memory (through memcpy).
+class IterableArena {
+protected:
+  struct Header
+  {
+    size_t mBlocSize;
+  };
+public:
+  enum ArenaType {
+    FIXED_SIZE,
+    GROWABLE
+  };
+
+  IterableArena(ArenaType aType, size_t aStorageSize)
+  : mSize(aStorageSize)
+  , mCursor(0)
+  , mIsGrowable(aType == GROWABLE)
+  {
+    if (mSize == 0) {
+      mSize = 128;
+    }
+
+    mStorage = (uint8_t*)malloc(mSize);
+    if (mStorage == nullptr) {
+      gfxCriticalError() << "Not enough Memory allocate a memory pool of size " << aStorageSize;
+      MOZ_CRASH();
+    }
+  }
+
+  ~IterableArena()
+  {
+    free(mStorage);
+  }
+
+  /// Constructs a new item in the pool and returns a positive offset in case of
+  /// success.
+  ///
+  /// The offset never changes even if the storage is reallocated, so users
+  /// of this class should prefer storing offsets rather than direct pointers
+  /// to the allocated objects.
+  /// Alloc can cause the storage to be reallocated if the pool was initialized
+  /// with IterableArena::GROWABLE.
+  /// If for any reason the pool fails to allocate enough space for the new item
+  /// Alloc returns a negative offset and the object's constructor is not called.
+  template<typename T, typename... Args>
+  ptrdiff_t
+  Alloc(Args&&... aArgs)
+  {
+    void* storage = nullptr;
+    auto offset = AllocRaw(sizeof(T), &storage);
+    if (offset < 0) {
+      return offset;
+    }
+    new (storage) T(Forward<Args>(aArgs)...);
+    return offset;
+  }
+
+  ptrdiff_t AllocRaw(size_t aSize, void** aOutPtr = nullptr)
+  {
+    const size_t blocSize = AlignedSize(sizeof(Header) + aSize);
+
+    if (AlignedSize(mCursor + blocSize) > mSize) {
+      if (!mIsGrowable) {
+        return -1;
+      }
+
+      size_t newSize = mSize * 2;
+      while (AlignedSize(mCursor + blocSize) > newSize) {
+        newSize *= 2;
+      }
+
+      uint8_t* newStorage = (uint8_t*)realloc(mStorage, newSize);
+      if (!newStorage) {
+         gfxCriticalError() << "Not enough Memory to grow the memory pool, size: " << newSize;
+        return -1;
+      }
+
+      mStorage = newStorage;
+      mSize = newSize;
+    }
+    ptrdiff_t offset = mCursor;
+    GetHeader(offset)->mBlocSize = blocSize;
+    mCursor += blocSize;
+    if (aOutPtr) {
+        *aOutPtr = GetStorage(offset);
+    }
+    return offset;
+  }
+
+  /// Get access to an allocated item at a given offset (only use offsets returned
+  /// by Alloc or AllocRaw).
+  ///
+  /// If the pool is growable, the returned pointer is only valid temporarily. The
+  /// underlying storage can be reallocated in Alloc or AllocRaw, so do not keep
+  /// these pointers around and store the offset instead.
+  void* GetStorage(ptrdiff_t offset = 0)
+  {
+    MOZ_ASSERT(offset >= 0);
+    MOZ_ASSERT(offset < mCursor);
+    return offset >= 0 ? mStorage + offset + sizeof(Header) : nullptr;
+  }
+
+  /// Clears the storage without running any destructor and without deallocating it.
+  void Clear()
+  {
+    mCursor = 0;
+  }
+
+  /// Iterate over the elements allocated in this pool.
+  ///
+  /// Takes a lambda or function object accepting a void* as parameter.
+  template<typename Func>
+  void ForEach(Func cb)
+  {
+    Iterator it;
+    while (void* ptr = it.Next(this)) {
+      cb(ptr);
+    }
+  }
+
+  /// A simple iterator over an arena.
+  class Iterator {
+  public:
+    Iterator()
+    : mCursor(0)
+    {}
+
+    void* Next(IterableArena* aArena)
+    {
+      if (mCursor >= aArena->mCursor) {
+        return nullptr;
+      }
+      void* result = aArena->GetStorage(mCursor);
+      const size_t blocSize = aArena->GetHeader(mCursor)->mBlocSize;
+      MOZ_ASSERT(blocSize != 0);
+      mCursor += blocSize;
+      return result;
+    }
+
+  private:
+    ptrdiff_t mCursor;
+  };
+
+protected:
+  Header* GetHeader(ptrdiff_t offset)
+  {
+    return (Header*) (mStorage + offset);
+  }
+
+  size_t AlignedSize(size_t aSize) const
+  {
+    const size_t alignment = sizeof(uintptr_t);
+    return aSize + (alignment - (aSize % alignment)) % alignment;
+  }
+
+  uint8_t* mStorage;
+  uint32_t mSize;
+  ptrdiff_t mCursor;
+  bool mIsGrowable;
+
+  friend class Iterator;
+};
+
+} // namespace
+} // namespace
+
+#endif
--- a/gfx/2d/moz.build
+++ b/gfx/2d/moz.build
@@ -20,16 +20,17 @@ EXPORTS.mozilla.gfx += [
     'Blur.h',
     'BorrowedContext.h',
     'Coord.h',
     'DataSurfaceHelpers.h',
     'DrawTargetTiled.h',
     'Filters.h',
     'Helpers.h',
     'HelpersCairo.h',
+    'IterableArena.h',
     'Logging.h',
     'Matrix.h',
     'NumericTools.h',
     'PathHelpers.h',
     'PatternHelpers.h',
     'Point.h',
     'Quaternion.h',
     'Rect.h',
new file mode 100644
--- /dev/null
+++ b/gfx/tests/gtest/TestArena.cpp
@@ -0,0 +1,188 @@
+/* vim:set ts=2 sw=2 sts=2 et: */
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+#include "gtest/gtest.h"
+#include "gmock/gmock.h"
+
+#include "mozilla/gfx/IterableArena.h"
+#include <string>
+
+using namespace mozilla;
+using namespace mozilla::gfx;
+
+#ifdef A
+#undef A
+#endif
+
+#ifdef B
+#undef B
+#endif
+
+// to avoid having symbols that collide easily like A and B in the global namespace
+namespace test_arena {
+
+class A;
+class B;
+
+class Base {
+public:
+  virtual ~Base() {}
+  virtual A* AsA() { return nullptr; }
+  virtual B* AsB() { return nullptr; }
+};
+
+static int sDtorItemA = 0;
+static int sDtorItemB = 0;
+
+class A : public Base {
+public:
+  virtual A* AsA() override { return this; }
+
+  explicit A(uint64_t val) : mVal(val) {}
+  ~A() { ++sDtorItemA; }
+
+  uint64_t mVal;
+};
+
+class B : public Base {
+public:
+  virtual B* AsB() override { return this; }
+
+  explicit B(const string& str) : mVal(str) {}
+  ~B() { ++sDtorItemB; }
+
+  std::string mVal;
+};
+
+struct BigStruct {
+  uint64_t mVal;
+  uint8_t data[120];
+
+  explicit BigStruct(uint64_t val) : mVal(val) {}
+};
+
+void TestArenaAlloc(IterableArena::ArenaType aType)
+{
+  sDtorItemA = 0;
+  sDtorItemB = 0;
+  IterableArena arena(aType, 256);
+
+  // An empty arena has no items to iterate over.
+  {
+    int iterations = 0;
+    arena.ForEach([&](void* item){
+      iterations++;
+    });
+    ASSERT_EQ(iterations, 0);
+  }
+
+  auto a1 = arena.Alloc<A>(42);
+  auto b1 = arena.Alloc<B>("Obladi oblada");
+  auto a2 = arena.Alloc<A>(1337);
+  auto b2 = arena.Alloc<B>("Yellow submarine");
+  auto b3 = arena.Alloc<B>("She's got a ticket to ride");
+
+  // Alloc returns a non-negative offset if the allocation succeeded.
+  ASSERT_TRUE(a1 >= 0);
+  ASSERT_TRUE(a2 >= 0);
+  ASSERT_TRUE(b1 >= 0);
+  ASSERT_TRUE(b2 >= 0);
+  ASSERT_TRUE(b3 >= 0);
+
+  ASSERT_TRUE(arena.GetStorage(a1) != nullptr);
+  ASSERT_TRUE(arena.GetStorage(a2) != nullptr);
+  ASSERT_TRUE(arena.GetStorage(b1) != nullptr);
+  ASSERT_TRUE(arena.GetStorage(b2) != nullptr);
+  ASSERT_TRUE(arena.GetStorage(b3) != nullptr);
+
+  ASSERT_TRUE(((Base*)arena.GetStorage(a1))->AsA() != nullptr);
+  ASSERT_TRUE(((Base*)arena.GetStorage(a2))->AsA() != nullptr);
+
+  ASSERT_TRUE(((Base*)arena.GetStorage(b1))->AsB() != nullptr);
+  ASSERT_TRUE(((Base*)arena.GetStorage(b2))->AsB() != nullptr);
+  ASSERT_TRUE(((Base*)arena.GetStorage(b3))->AsB() != nullptr);
+
+  ASSERT_EQ(((Base*)arena.GetStorage(a1))->AsA()->mVal, (uint64_t)42);
+  ASSERT_EQ(((Base*)arena.GetStorage(a2))->AsA()->mVal, (uint64_t)1337);
+
+  ASSERT_EQ(((Base*)arena.GetStorage(b1))->AsB()->mVal, std::string("Obladi oblada"));
+  ASSERT_EQ(((Base*)arena.GetStorage(b2))->AsB()->mVal, std::string("Yellow submarine"));
+  ASSERT_EQ(((Base*)arena.GetStorage(b3))->AsB()->mVal, std::string("She's got a ticket to ride"));
+
+  {
+    int iterations = 0;
+    arena.ForEach([&](void* item){
+      iterations++;
+    });
+    ASSERT_EQ(iterations, 5);
+  }
+
+  // Typically, running the destructors of the elements in the arena will is done
+  // manually like this:
+  arena.ForEach([](void* item){
+    ((Base*)item)->~Base();
+  });
+  arena.Clear();
+  ASSERT_EQ(sDtorItemA, 2);
+  ASSERT_EQ(sDtorItemB, 3);
+
+  // An empty arena has no items to iterate over (we just cleared it).
+  {
+    int iterations = 0;
+    arena.ForEach([&](void* item){
+      iterations++;
+    });
+    ASSERT_EQ(iterations, 0);
+  }
+
+}
+
+void TestArenaLimit(IterableArena::ArenaType aType, bool aShouldReachLimit)
+{
+  IterableArena arena(aType, 128);
+
+  // A non-growable arena should return a negative offset when running out
+  // of space, without crashing.
+  // We should not run out of space with a growable arena (unless the os is
+  // running out of memory but this isn't expected for this test).
+  bool reachedLimit = false;
+  for (int i = 0; i < 100; ++i) {
+    auto offset = arena.Alloc<A>(42);
+    if (offset < 0) {
+      reachedLimit = true;
+      break;
+    }
+  }
+  ASSERT_EQ(reachedLimit, aShouldReachLimit);
+}
+
+} // namespace test_arena
+
+using namespace test_arena;
+
+TEST(Moz2D, FixedArena) {
+  TestArenaAlloc(IterableArena::FIXED_SIZE);
+  TestArenaLimit(IterableArena::FIXED_SIZE, true);
+}
+
+TEST(Moz2D, GrowableArena) {
+  TestArenaAlloc(IterableArena::GROWABLE);
+  TestArenaLimit(IterableArena::GROWABLE, false);
+
+  IterableArena arena(IterableArena::GROWABLE, 16);
+  // sizeof(BigStruct) is more than twice the initial capacity, make sure that
+  // this doesn't blow everything up, since the arena doubles its storage size each
+  // time it grows (until it finds a size that fits).
+  auto a = arena.Alloc<BigStruct>(1);
+  auto b = arena.Alloc<BigStruct>(2);
+  auto c = arena.Alloc<BigStruct>(3);
+
+  // Offsets should also still point to the appropriate values after reallocation.
+  ASSERT_EQ(((BigStruct*)arena.GetStorage(a))->mVal, (uint64_t)1);
+  ASSERT_EQ(((BigStruct*)arena.GetStorage(b))->mVal, (uint64_t)2);
+  ASSERT_EQ(((BigStruct*)arena.GetStorage(c))->mVal, (uint64_t)3);
+
+  arena.Clear();
+}
--- a/gfx/tests/gtest/moz.build
+++ b/gfx/tests/gtest/moz.build
@@ -3,16 +3,17 @@
 # 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/.
 
 UNIFIED_SOURCES += [
     'gfxSurfaceRefCountTest.cpp',
     # Disabled on suspicion of causing bug 904227
     #'gfxWordCacheTest.cpp',
+    'TestArena.cpp',
     'TestBufferRotation.cpp',
     'TestColorNames.cpp',
     'TestCompositor.cpp',
     'TestGfxPrefs.cpp',
     'TestGfxWidgets.cpp',
     'TestLayers.cpp',
     'TestMoz2D.cpp',
     'TestQcms.cpp',