SkFixedAlloc
Looking at SkSmallAlloc hasn't left me terribly impressed. I think we can replace it with something a lot simpler to work with.
That simpler thing's core would be something like SkFixedAlloc, which allocates objects out of a fixed sized buffer, and cleans them up when done.
If needed, we can wrap that with logic to try to allocate out of an SkFixedAlloc, falling back on mallc() when exhausted.
BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=4658
Change-Id: I8d94156ddf98802e42ec0890cff0f06b21f073b0
Reviewed-on: https://skia-review.googlesource.com/4658
Commit-Queue: Mike Klein <mtklein@chromium.org>
Reviewed-by: Mike Reed <reed@google.com>
diff --git a/gn/core.gni b/gn/core.gni
index 643b71e..80514c4 100644
--- a/gn/core.gni
+++ b/gn/core.gni
@@ -124,6 +124,8 @@
"$_src/core/SkFilterProc.cpp",
"$_src/core/SkFilterProc.h",
"$_src/core/SkFindAndPlaceGlyph.h",
+ "$_src/core/SkFixedAlloc.cpp",
+ "$_src/core/SkFixedAlloc.h",
"$_src/core/SkFlattenable.cpp",
"$_src/core/SkFlattenableSerialization.cpp",
"$_src/core/SkFont.cpp",
diff --git a/gn/tests.gni b/gn/tests.gni
index 4fa653a..fb43d79 100644
--- a/gn/tests.gni
+++ b/gn/tests.gni
@@ -62,6 +62,7 @@
"$_tests/ExifTest.cpp",
"$_tests/FillPathTest.cpp",
"$_tests/FitsInTest.cpp",
+ "$_tests/FixedAllocTest.cpp",
"$_tests/FlattenableCustomFactory.cpp",
"$_tests/FlattenableFactoryToName.cpp",
"$_tests/FlattenDrawableTest.cpp",
diff --git a/src/core/SkFixedAlloc.cpp b/src/core/SkFixedAlloc.cpp
new file mode 100644
index 0000000..133245a
--- /dev/null
+++ b/src/core/SkFixedAlloc.cpp
@@ -0,0 +1,50 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkFixedAlloc.h"
+
+SkFixedAlloc::SkFixedAlloc(void* ptr, size_t len)
+ : fBuffer((char*)ptr), fUsed(0), fLimit(len) {}
+
+void SkFixedAlloc::undo() {
+ // This function is essentially make() in reverse.
+
+ // First, read the Footer we stamped at the end.
+ Footer footer;
+ memcpy(&footer, fBuffer + fUsed - sizeof(Footer), sizeof(Footer));
+
+ // That tells us where the T starts and how to destroy it.
+ footer.dtor(fBuffer + fUsed - sizeof(Footer) - footer.len);
+
+ // We can reuse bytes that stored the Footer, the T, and any that we skipped for alignment.
+ fUsed -= sizeof(Footer) + footer.len + footer.skip;
+}
+
+void SkFixedAlloc::reset() {
+ while (fUsed) {
+ this->undo();
+ }
+}
+
+
+SkFallbackAlloc::SkFallbackAlloc(SkFixedAlloc* fixed) : fFixedAlloc(fixed) {}
+
+void SkFallbackAlloc::undo() {
+ if (fHeapAllocs.empty()) {
+ return fFixedAlloc->undo();
+ }
+ HeapAlloc alloc = fHeapAllocs.back();
+ alloc.deleter(alloc.ptr);
+ fHeapAllocs.pop_back();
+}
+
+void SkFallbackAlloc::reset() {
+ while (!fHeapAllocs.empty()) {
+ this->undo();
+ }
+ fFixedAlloc->reset();
+}
diff --git a/src/core/SkFixedAlloc.h b/src/core/SkFixedAlloc.h
new file mode 100644
index 0000000..8e2736e
--- /dev/null
+++ b/src/core/SkFixedAlloc.h
@@ -0,0 +1,102 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkFixedAlloc_DEFINED
+#define SkFixedAlloc_DEFINED
+
+#include "SkTFitsIn.h"
+#include "SkTypes.h"
+#include <new>
+#include <utility>
+#include <vector>
+
+// SkFixedAlloc allocates objects out of a fixed-size buffer and destroys them when destroyed.
+class SkFixedAlloc {
+public:
+ SkFixedAlloc(void* ptr, size_t len);
+ ~SkFixedAlloc() { this->reset(); }
+
+ // Allocates a new T in the buffer if possible. If not, returns nullptr.
+ template <typename T, typename... Args>
+ T* make(Args&&... args) {
+ auto aligned = ((uintptr_t)(fBuffer+fUsed) + alignof(T) - 1) & ~(alignof(T)-1);
+ size_t skip = aligned - (uintptr_t)(fBuffer+fUsed);
+
+ if (!SkTFitsIn<uint32_t>(skip) ||
+ !SkTFitsIn<uint32_t>(sizeof(T)) ||
+ fUsed + skip + sizeof(T) + sizeof(Footer) > fLimit) {
+ return nullptr;
+ }
+
+ // Skip ahead until our buffer is aligned for T.
+ fUsed += skip;
+
+ // Create the T.
+ auto ptr = (T*)(fBuffer+fUsed);
+ new (ptr) T{std::forward<Args>(args)...};
+ fUsed += sizeof(T);
+
+ // Stamp a footer after the T that we can use to clean it up.
+ Footer footer = { [](void* ptr) { ((T*)ptr)->~T(); }, SkToU32(skip), SkToU32(sizeof(T)) };
+ memcpy(fBuffer+fUsed, &footer, sizeof(Footer));
+ fUsed += sizeof(Footer);
+
+ return ptr;
+ }
+
+ // Destroys the last object allocated and frees its space in the buffer.
+ void undo();
+
+ // Destroys all objects and frees all space in the buffer.
+ void reset();
+
+private:
+ struct Footer {
+ void (*dtor)(void*);
+ uint32_t skip, len;
+ };
+
+ char* fBuffer;
+ size_t fUsed, fLimit;
+};
+
+class SkFallbackAlloc {
+public:
+ explicit SkFallbackAlloc(SkFixedAlloc*);
+ ~SkFallbackAlloc() { this->reset(); }
+
+ // Allocates a new T with the SkFixedAlloc if possible. If not, uses the heap.
+ template <typename T, typename... Args>
+ T* make(Args&&... args) {
+ // Once we go heap we never go back to fixed. This keeps destructor ordering sane.
+ if (fHeapAllocs.empty()) {
+ if (T* ptr = fFixedAlloc->make<T>(std::forward<Args>(args)...)) {
+ return ptr;
+ }
+ }
+ auto ptr = new T{std::forward<Args>(args)...};
+ fHeapAllocs.push_back({[](void* ptr) { delete (T*)ptr; }, ptr});
+ return ptr;
+ }
+
+ // Destroys the last object allocated and frees any space it used in the SkFixedAlloc.
+ void undo();
+
+ // Destroys all objects and frees all space in the SkFixedAlloc.
+ void reset();
+
+private:
+ struct HeapAlloc {
+ void (*deleter)(void*);
+ void* ptr;
+ };
+
+ SkFixedAlloc* fFixedAlloc;
+ std::vector<HeapAlloc> fHeapAllocs;
+};
+
+#endif//SkFixedAlloc_DEFINED
diff --git a/tests/FixedAllocTest.cpp b/tests/FixedAllocTest.cpp
new file mode 100644
index 0000000..0a00f00
--- /dev/null
+++ b/tests/FixedAllocTest.cpp
@@ -0,0 +1,113 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Test.h"
+#include "SkFixedAlloc.h"
+
+namespace {
+
+ static int created, destroyed;
+
+ struct Foo {
+ Foo(int X, float Y) : x(X), y(Y) { created++; }
+ ~Foo() { destroyed++; }
+
+ int x;
+ float y;
+ };
+
+ struct Big {
+ Big() {}
+ uint32_t array[128];
+ };
+
+}
+
+DEF_TEST(FixedAlloc, r) {
+ // Basic mechanics.
+ {
+ uint8_t buf[128];
+ SkFixedAlloc fa(buf, sizeof(buf));
+
+ Foo* foo = fa.make<Foo>(3, 4.0f);
+ REPORTER_ASSERT(r, foo);
+ REPORTER_ASSERT(r, foo->x == 3);
+ REPORTER_ASSERT(r, foo->y == 4.0f);
+ REPORTER_ASSERT(r, created == 1);
+ REPORTER_ASSERT(r, destroyed == 0);
+
+ Foo* bar = fa.make<Foo>(8, 1.0f);
+ REPORTER_ASSERT(r, bar);
+ REPORTER_ASSERT(r, bar->x == 8);
+ REPORTER_ASSERT(r, bar->y == 1.0f);
+ REPORTER_ASSERT(r, created == 2);
+ REPORTER_ASSERT(r, destroyed == 0);
+
+ fa.undo();
+ REPORTER_ASSERT(r, created == 2);
+ REPORTER_ASSERT(r, destroyed == 1);
+ }
+ REPORTER_ASSERT(r, created == 2);
+ REPORTER_ASSERT(r, destroyed == 2);
+
+ {
+ // Test alignment gurantees.
+ uint8_t buf[64];
+ SkFixedAlloc fa(buf+3, sizeof(buf)-3);
+
+ Foo* foo = fa.make<Foo>(3, 4.0f);
+ REPORTER_ASSERT(r, SkIsAlign4((uintptr_t)foo));
+ REPORTER_ASSERT(r, created == 3);
+ REPORTER_ASSERT(r, destroyed == 2);
+
+ // Might as well test reset() while we're at it.
+ fa.reset();
+ REPORTER_ASSERT(r, created == 3);
+ REPORTER_ASSERT(r, destroyed == 3);
+ }
+ REPORTER_ASSERT(r, created == 3);
+ REPORTER_ASSERT(r, destroyed == 3);
+}
+
+DEF_TEST(FallbackAlloc, r) {
+ // SkFixedAlloc will eventually fail when it runs out of space in its buffer.
+ int buf[32];
+ SkFixedAlloc fixed(buf, sizeof(buf));
+ bool fixed_failed = false;
+ for (int i = 0; i < 32; i++) {
+ // (Remember, there is some overhead to each make() call.)
+ fixed_failed = fixed_failed || (fixed.make<int>(i) == nullptr);
+ }
+ REPORTER_ASSERT(r, fixed_failed);
+
+
+ // SkFallbackAlloc will always succeed, using the heap as required.
+ fixed.reset();
+ SkFallbackAlloc fallback(&fixed);
+
+ bool fallback_failed = false;
+ for (int i = 0; i < 32; i++) {
+ fallback_failed = fallback_failed || (fallback.make<int>(i) == nullptr);
+ }
+ REPORTER_ASSERT(r, !fallback_failed);
+
+
+ // Test small, big, small allocations to make sure once we go to the heap we stay there.
+ fallback.reset();
+ auto smallA = fallback.make<int>(2);
+ auto big = fallback.make<Big>();
+ auto smallB = fallback.make<int>(3);
+
+ auto in_buf = [&](void* ptr) {
+ return (uintptr_t)(buf+0 ) <= (uintptr_t)ptr
+ && (uintptr_t)(buf+32) > (uintptr_t)ptr;
+ };
+
+ REPORTER_ASSERT(r, in_buf(smallA));
+ REPORTER_ASSERT(r, !in_buf(big));
+ REPORTER_ASSERT(r, !in_buf(smallB));
+}