SkArenaAlloc.h 8.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240
  1. /*
  2. * Copyright 2016 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #ifndef SkArenaAlloc_DEFINED
  8. #define SkArenaAlloc_DEFINED
  9. #include "include/private/SkTFitsIn.h"
  10. #include <cassert>
  11. #include <cstddef>
  12. #include <cstdint>
  13. #include <cstdlib>
  14. #include <cstring>
  15. #include <limits>
  16. #include <new>
  17. #include <type_traits>
  18. #include <utility>
  19. #include <vector>
  20. // SkArenaAlloc allocates object and destroys the allocated objects when destroyed. It's designed
  21. // to minimize the number of underlying block allocations. SkArenaAlloc allocates first out of an
  22. // (optional) user-provided block of memory, and when that's exhausted it allocates on the heap,
  23. // starting with an allocation of firstHeapAllocation bytes. If your data (plus a small overhead)
  24. // fits in the user-provided block, SkArenaAlloc never uses the heap, and if it fits in
  25. // firstHeapAllocation bytes, it'll use the heap only once. If 0 is specified for
  26. // firstHeapAllocation, then blockSize is used unless that too is 0, then 1024 is used.
  27. //
  28. // Examples:
  29. //
  30. // char block[mostCasesSize];
  31. // SkArenaAlloc arena(block, mostCasesSize);
  32. //
  33. // If mostCasesSize is too large for the stack, you can use the following pattern.
  34. //
  35. // std::unique_ptr<char[]> block{new char[mostCasesSize]};
  36. // SkArenaAlloc arena(block.get(), mostCasesSize, almostAllCasesSize);
  37. //
  38. // If the program only sometimes allocates memory, use the following pattern.
  39. //
  40. // SkArenaAlloc arena(nullptr, 0, almostAllCasesSize);
  41. //
  42. // The storage does not necessarily need to be on the stack. Embedding the storage in a class also
  43. // works.
  44. //
  45. // class Foo {
  46. // char storage[mostCasesSize];
  47. // SkArenaAlloc arena (storage, mostCasesSize);
  48. // };
  49. //
  50. // In addition, the system is optimized to handle POD data including arrays of PODs (where
  51. // POD is really data with no destructors). For POD data it has zero overhead per item, and a
  52. // typical per block overhead of 8 bytes. For non-POD objects there is a per item overhead of 4
  53. // bytes. For arrays of non-POD objects there is a per array overhead of typically 8 bytes. There
  54. // is an addition overhead when switching from POD data to non-POD data of typically 8 bytes.
  55. //
  56. // If additional blocks are needed they are increased exponentially. This strategy bounds the
  57. // recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using
  58. // the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48
  59. // there are 71 allocations.
  60. class SkArenaAlloc {
  61. public:
  62. SkArenaAlloc(char* block, size_t blockSize, size_t firstHeapAllocation);
  63. explicit SkArenaAlloc(size_t firstHeapAllocation)
  64. : SkArenaAlloc(nullptr, 0, firstHeapAllocation)
  65. {}
  66. ~SkArenaAlloc();
  67. template <typename T, typename... Args>
  68. T* make(Args&&... args) {
  69. uint32_t size = ToU32(sizeof(T));
  70. uint32_t alignment = ToU32(alignof(T));
  71. char* objStart;
  72. if (std::is_trivially_destructible<T>::value) {
  73. objStart = this->allocObject(size, alignment);
  74. fCursor = objStart + size;
  75. } else {
  76. objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment);
  77. // Can never be UB because max value is alignof(T).
  78. uint32_t padding = ToU32(objStart - fCursor);
  79. // Advance to end of object to install footer.
  80. fCursor = objStart + size;
  81. FooterAction* releaser = [](char* objEnd) {
  82. char* objStart = objEnd - (sizeof(T) + sizeof(Footer));
  83. ((T*)objStart)->~T();
  84. return objStart;
  85. };
  86. this->installFooter(releaser, padding);
  87. }
  88. // This must be last to make objects with nested use of this allocator work.
  89. return new(objStart) T(std::forward<Args>(args)...);
  90. }
  91. template <typename T>
  92. T* makeArrayDefault(size_t count) {
  93. AssertRelease(SkTFitsIn<uint32_t>(count));
  94. uint32_t safeCount = ToU32(count);
  95. T* array = (T*)this->commonArrayAlloc<T>(safeCount);
  96. // If T is primitive then no initialization takes place.
  97. for (size_t i = 0; i < safeCount; i++) {
  98. new (&array[i]) T;
  99. }
  100. return array;
  101. }
  102. template <typename T>
  103. T* makeArray(size_t count) {
  104. AssertRelease(SkTFitsIn<uint32_t>(count));
  105. uint32_t safeCount = ToU32(count);
  106. T* array = (T*)this->commonArrayAlloc<T>(safeCount);
  107. // If T is primitive then the memory is initialized. For example, an array of chars will
  108. // be zeroed.
  109. for (size_t i = 0; i < safeCount; i++) {
  110. new (&array[i]) T();
  111. }
  112. return array;
  113. }
  114. // Only use makeBytesAlignedTo if none of the typed variants are impractical to use.
  115. void* makeBytesAlignedTo(size_t size, size_t align) {
  116. AssertRelease(SkTFitsIn<uint32_t>(size));
  117. auto objStart = this->allocObject(ToU32(size), ToU32(align));
  118. fCursor = objStart + size;
  119. return objStart;
  120. }
  121. // Destroy all allocated objects, free any heap allocations.
  122. void reset();
  123. private:
  124. static void AssertRelease(bool cond) { if (!cond) { ::abort(); } }
  125. static uint32_t ToU32(size_t v) {
  126. assert(SkTFitsIn<uint32_t>(v));
  127. return (uint32_t)v;
  128. }
  129. using Footer = int64_t;
  130. using FooterAction = char* (char*);
  131. static char* SkipPod(char* footerEnd);
  132. static void RunDtorsOnBlock(char* footerEnd);
  133. static char* NextBlock(char* footerEnd);
  134. void installFooter(FooterAction* releaser, uint32_t padding);
  135. void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding);
  136. void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding);
  137. void ensureSpace(uint32_t size, uint32_t alignment);
  138. char* allocObject(uint32_t size, uint32_t alignment) {
  139. uintptr_t mask = alignment - 1;
  140. uintptr_t alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
  141. uintptr_t totalSize = size + alignedOffset;
  142. AssertRelease(totalSize >= size);
  143. if (totalSize > static_cast<uintptr_t>(fEnd - fCursor)) {
  144. this->ensureSpace(size, alignment);
  145. alignedOffset = (~reinterpret_cast<uintptr_t>(fCursor) + 1) & mask;
  146. }
  147. return fCursor + alignedOffset;
  148. }
  149. char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment);
  150. template <typename T>
  151. char* commonArrayAlloc(uint32_t count) {
  152. char* objStart;
  153. AssertRelease(count <= std::numeric_limits<uint32_t>::max() / sizeof(T));
  154. uint32_t arraySize = ToU32(count * sizeof(T));
  155. uint32_t alignment = ToU32(alignof(T));
  156. if (std::is_trivially_destructible<T>::value) {
  157. objStart = this->allocObject(arraySize, alignment);
  158. fCursor = objStart + arraySize;
  159. } else {
  160. constexpr uint32_t overhead = sizeof(Footer) + sizeof(uint32_t);
  161. AssertRelease(arraySize <= std::numeric_limits<uint32_t>::max() - overhead);
  162. uint32_t totalSize = arraySize + overhead;
  163. objStart = this->allocObjectWithFooter(totalSize, alignment);
  164. // Can never be UB because max value is alignof(T).
  165. uint32_t padding = ToU32(objStart - fCursor);
  166. // Advance to end of array to install footer.?
  167. fCursor = objStart + arraySize;
  168. this->installUint32Footer(
  169. [](char* footerEnd) {
  170. char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t));
  171. uint32_t count;
  172. memmove(&count, objEnd, sizeof(uint32_t));
  173. char* objStart = objEnd - count * sizeof(T);
  174. T* array = (T*) objStart;
  175. for (uint32_t i = 0; i < count; i++) {
  176. array[i].~T();
  177. }
  178. return objStart;
  179. },
  180. ToU32(count),
  181. padding);
  182. }
  183. return objStart;
  184. }
  185. char* fDtorCursor;
  186. char* fCursor;
  187. char* fEnd;
  188. char* const fFirstBlock;
  189. const uint32_t fFirstSize;
  190. const uint32_t fFirstHeapAllocationSize;
  191. // Use the Fibonacci sequence as the growth factor for block size. The size of the block
  192. // allocated is fFib0 * fFirstHeapAllocationSize. Using 2 ^ n * fFirstHeapAllocationSize
  193. // had too much slop for Android.
  194. uint32_t fFib0 {1}, fFib1 {1};
  195. };
  196. // Helper for defining allocators with inline/reserved storage.
  197. // For argument declarations, stick to the base type (SkArenaAlloc).
  198. template <size_t InlineStorageSize>
  199. class SkSTArenaAlloc : public SkArenaAlloc {
  200. public:
  201. explicit SkSTArenaAlloc(size_t firstHeapAllocation = InlineStorageSize)
  202. : INHERITED(fInlineStorage, InlineStorageSize, firstHeapAllocation) {}
  203. private:
  204. char fInlineStorage[InlineStorageSize];
  205. using INHERITED = SkArenaAlloc;
  206. };
  207. #endif // SkArenaAlloc_DEFINED