158b130681db4432c4937c2cb1b2529de628c6b19Mike Klein/* 258b130681db4432c4937c2cb1b2529de628c6b19Mike Klein * Copyright 2016 Google Inc. 358b130681db4432c4937c2cb1b2529de628c6b19Mike Klein * 458b130681db4432c4937c2cb1b2529de628c6b19Mike Klein * Use of this source code is governed by a BSD-style license that can be 558b130681db4432c4937c2cb1b2529de628c6b19Mike Klein * found in the LICENSE file. 658b130681db4432c4937c2cb1b2529de628c6b19Mike Klein */ 758b130681db4432c4937c2cb1b2529de628c6b19Mike Klein 858b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#ifndef SkFixedAlloc_DEFINED 958b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#define SkFixedAlloc_DEFINED 1058b130681db4432c4937c2cb1b2529de628c6b19Mike Klein 1168521702299e092211cf7085e8544556ea9dffc7Herb Derby#include "SkRefCnt.h" 1258b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#include "SkTFitsIn.h" 1358b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#include "SkTypes.h" 140497f088bb41338b1b1400556b9b690decc846faHerb Derby#include <cstddef> 1558b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#include <new> 160497f088bb41338b1b1400556b9b690decc846faHerb Derby#include <type_traits> 1758b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#include <utility> 1858b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#include <vector> 1958b130681db4432c4937c2cb1b2529de628c6b19Mike Klein 200497f088bb41338b1b1400556b9b690decc846faHerb Derby// SkArenaAlloc allocates object and destroys the allocated objects when destroyed. It's designed 210497f088bb41338b1b1400556b9b690decc846faHerb Derby// to minimize the number of underlying block allocations. SkArenaAlloc allocates first out of an 220497f088bb41338b1b1400556b9b690decc846faHerb Derby// (optional) user-provided block of memory, and when that's exhausted it allocates on the heap, 230497f088bb41338b1b1400556b9b690decc846faHerb Derby// starting with an allocation of extraSize bytes. If your data (plus a small overhead) fits in 240497f088bb41338b1b1400556b9b690decc846faHerb Derby// the user-provided block, SkArenaAlloc never uses the heap, and if it fits in extraSize bytes, 250497f088bb41338b1b1400556b9b690decc846faHerb Derby// it'll use the heap only once. If you pass extraSize = 0, it allocates blocks for each call to 260497f088bb41338b1b1400556b9b690decc846faHerb Derby// make<T>. 270497f088bb41338b1b1400556b9b690decc846faHerb Derby// 280497f088bb41338b1b1400556b9b690decc846faHerb Derby// Examples: 290497f088bb41338b1b1400556b9b690decc846faHerb Derby// 300497f088bb41338b1b1400556b9b690decc846faHerb Derby// char block[mostCasesSize]; 310497f088bb41338b1b1400556b9b690decc846faHerb Derby// SkArenaAlloc arena(block, almostAllCasesSize); 320497f088bb41338b1b1400556b9b690decc846faHerb Derby// 330497f088bb41338b1b1400556b9b690decc846faHerb Derby// If mostCasesSize is too large for the stack, you can use the following pattern. 340497f088bb41338b1b1400556b9b690decc846faHerb Derby// 350497f088bb41338b1b1400556b9b690decc846faHerb Derby// std::unique_ptr<char[]> block{new char[mostCasesSize]}; 360497f088bb41338b1b1400556b9b690decc846faHerb Derby// SkArenaAlloc arena(block.get(), mostCasesSize, almostAllCasesSize); 370497f088bb41338b1b1400556b9b690decc846faHerb Derby// 380497f088bb41338b1b1400556b9b690decc846faHerb Derby// If the program only sometimes allocates memory, use the following. 390497f088bb41338b1b1400556b9b690decc846faHerb Derby// 400497f088bb41338b1b1400556b9b690decc846faHerb Derby// SkArenaAlloc arena(nullptr, 0, almostAllCasesSize); 410497f088bb41338b1b1400556b9b690decc846faHerb Derby// 420497f088bb41338b1b1400556b9b690decc846faHerb Derby// The storage does not necessarily need to be on the stack. Embedding the storage in a class also 430497f088bb41338b1b1400556b9b690decc846faHerb Derby// works. 440497f088bb41338b1b1400556b9b690decc846faHerb Derby// 450497f088bb41338b1b1400556b9b690decc846faHerb Derby// class Foo { 460497f088bb41338b1b1400556b9b690decc846faHerb Derby// char storage[mostCasesSize]; 470497f088bb41338b1b1400556b9b690decc846faHerb Derby// SkArenaAlloc arena (storage, almostAllCasesSize); 480497f088bb41338b1b1400556b9b690decc846faHerb Derby// }; 490497f088bb41338b1b1400556b9b690decc846faHerb Derby// 500497f088bb41338b1b1400556b9b690decc846faHerb Derby// In addition, the system is optimized to handle POD data including arrays of PODs (where 510497f088bb41338b1b1400556b9b690decc846faHerb Derby// POD is really data with no destructors). For POD data it has zero overhead per item, and a 520497f088bb41338b1b1400556b9b690decc846faHerb Derby// typical block overhead of 8 bytes. For non-POD objects there is a per item overhead of 4 bytes. 530497f088bb41338b1b1400556b9b690decc846faHerb Derby// For arrays of non-POD objects there is a per array overhead of typically 8 bytes. There is an 540497f088bb41338b1b1400556b9b690decc846faHerb Derby// addition overhead when switching from POD data to non-POD data of typically 8 bytes. 5501254bcf222a7806afbfbcb9c7fe13cc522448b3Herb Derby// 5601254bcf222a7806afbfbcb9c7fe13cc522448b3Herb Derby// If additional blocks are needed they are increased exponentially. This strategy bounds the 577dd57b6a936af923a031f21c4ca9dc1031742473Herb Derby// recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using 587dd57b6a936af923a031f21c4ca9dc1031742473Herb Derby// the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48 597dd57b6a936af923a031f21c4ca9dc1031742473Herb Derby// there are 71 allocations. 600497f088bb41338b1b1400556b9b690decc846faHerb Derbyclass SkArenaAlloc { 610497f088bb41338b1b1400556b9b690decc846faHerb Derbypublic: 620497f088bb41338b1b1400556b9b690decc846faHerb Derby SkArenaAlloc(char* block, size_t size, size_t extraSize = 0); 630497f088bb41338b1b1400556b9b690decc846faHerb Derby 640497f088bb41338b1b1400556b9b690decc846faHerb Derby template <size_t kSize> 65593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby SkArenaAlloc(char (&block)[kSize], size_t extraSize = kSize) 660497f088bb41338b1b1400556b9b690decc846faHerb Derby : SkArenaAlloc(block, kSize, extraSize) 670497f088bb41338b1b1400556b9b690decc846faHerb Derby {} 680497f088bb41338b1b1400556b9b690decc846faHerb Derby 692a0daee1afcaf781e1d7ca51656bc5edac3cfa9aHerb Derby SkArenaAlloc(size_t extraSize) 702a0daee1afcaf781e1d7ca51656bc5edac3cfa9aHerb Derby : SkArenaAlloc(nullptr, 0, extraSize) 712a0daee1afcaf781e1d7ca51656bc5edac3cfa9aHerb Derby {} 722a0daee1afcaf781e1d7ca51656bc5edac3cfa9aHerb Derby 730497f088bb41338b1b1400556b9b690decc846faHerb Derby ~SkArenaAlloc(); 740497f088bb41338b1b1400556b9b690decc846faHerb Derby 750497f088bb41338b1b1400556b9b690decc846faHerb Derby template <typename T, typename... Args> 760497f088bb41338b1b1400556b9b690decc846faHerb Derby T* make(Args&&... args) { 771bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby uint32_t size = SkTo<uint32_t>(sizeof(T)); 781bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby uint32_t alignment = SkTo<uint32_t>(alignof(T)); 790497f088bb41338b1b1400556b9b690decc846faHerb Derby char* objStart; 800497f088bb41338b1b1400556b9b690decc846faHerb Derby if (skstd::is_trivially_destructible<T>::value) { 811bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby objStart = this->allocObject(size, alignment); 821bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby fCursor = objStart + size; 830497f088bb41338b1b1400556b9b690decc846faHerb Derby } else { 841bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby objStart = this->allocObjectWithFooter(size + sizeof(Footer), alignment); 8539728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby // Can never be UB because max value is alignof(T). 8639728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 870497f088bb41338b1b1400556b9b690decc846faHerb Derby 880497f088bb41338b1b1400556b9b690decc846faHerb Derby // Advance to end of object to install footer. 891bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby fCursor = objStart + size; 900497f088bb41338b1b1400556b9b690decc846faHerb Derby FooterAction* releaser = [](char* objEnd) { 910497f088bb41338b1b1400556b9b690decc846faHerb Derby char* objStart = objEnd - (sizeof(T) + sizeof(Footer)); 920497f088bb41338b1b1400556b9b690decc846faHerb Derby ((T*)objStart)->~T(); 930497f088bb41338b1b1400556b9b690decc846faHerb Derby return objStart; 940497f088bb41338b1b1400556b9b690decc846faHerb Derby }; 950497f088bb41338b1b1400556b9b690decc846faHerb Derby this->installFooter(releaser, padding); 960497f088bb41338b1b1400556b9b690decc846faHerb Derby } 970497f088bb41338b1b1400556b9b690decc846faHerb Derby 980497f088bb41338b1b1400556b9b690decc846faHerb Derby // This must be last to make objects with nested use of this allocator work. 990497f088bb41338b1b1400556b9b690decc846faHerb Derby return new(objStart) T(std::forward<Args>(args)...); 1000497f088bb41338b1b1400556b9b690decc846faHerb Derby } 1010497f088bb41338b1b1400556b9b690decc846faHerb Derby 10268521702299e092211cf7085e8544556ea9dffc7Herb Derby template <typename T, typename... Args> 10368521702299e092211cf7085e8544556ea9dffc7Herb Derby sk_sp<T> makeSkSp(Args&&... args) { 10468521702299e092211cf7085e8544556ea9dffc7Herb Derby SkASSERT(SkTFitsIn<uint32_t>(sizeof(T))); 10568521702299e092211cf7085e8544556ea9dffc7Herb Derby 10668521702299e092211cf7085e8544556ea9dffc7Herb Derby // The arena takes a ref for itself to account for the destructor. The sk_sp count can't 10768521702299e092211cf7085e8544556ea9dffc7Herb Derby // become zero or the sk_sp will try to call free on the pointer. 10868521702299e092211cf7085e8544556ea9dffc7Herb Derby return sk_sp<T>(SkRef(this->make<T>(std::forward<Args>(args)...))); 10968521702299e092211cf7085e8544556ea9dffc7Herb Derby } 11068521702299e092211cf7085e8544556ea9dffc7Herb Derby 1110497f088bb41338b1b1400556b9b690decc846faHerb Derby template <typename T> 1120497f088bb41338b1b1400556b9b690decc846faHerb Derby T* makeArrayDefault(size_t count) { 1131bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby uint32_t safeCount = SkTo<uint32_t>(count); 1141bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby T* array = (T*)this->commonArrayAlloc<T>(safeCount); 1150497f088bb41338b1b1400556b9b690decc846faHerb Derby 1160497f088bb41338b1b1400556b9b690decc846faHerb Derby // If T is primitive then no initialization takes place. 1171bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby for (size_t i = 0; i < safeCount; i++) { 1180497f088bb41338b1b1400556b9b690decc846faHerb Derby new (&array[i]) T; 1190497f088bb41338b1b1400556b9b690decc846faHerb Derby } 1200497f088bb41338b1b1400556b9b690decc846faHerb Derby return array; 1210497f088bb41338b1b1400556b9b690decc846faHerb Derby } 1220497f088bb41338b1b1400556b9b690decc846faHerb Derby 1230497f088bb41338b1b1400556b9b690decc846faHerb Derby template <typename T> 1240497f088bb41338b1b1400556b9b690decc846faHerb Derby T* makeArray(size_t count) { 1251bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby uint32_t safeCount = SkTo<uint32_t>(count); 1261bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby T* array = (T*)this->commonArrayAlloc<T>(safeCount); 1270497f088bb41338b1b1400556b9b690decc846faHerb Derby 1280497f088bb41338b1b1400556b9b690decc846faHerb Derby // If T is primitive then the memory is initialized. For example, an array of chars will 1290497f088bb41338b1b1400556b9b690decc846faHerb Derby // be zeroed. 1301bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby for (size_t i = 0; i < safeCount; i++) { 1310497f088bb41338b1b1400556b9b690decc846faHerb Derby new (&array[i]) T(); 1320497f088bb41338b1b1400556b9b690decc846faHerb Derby } 1330497f088bb41338b1b1400556b9b690decc846faHerb Derby return array; 1340497f088bb41338b1b1400556b9b690decc846faHerb Derby } 1350497f088bb41338b1b1400556b9b690decc846faHerb Derby 1360497f088bb41338b1b1400556b9b690decc846faHerb Derby // Destroy all allocated objects, free any heap allocations. 1370497f088bb41338b1b1400556b9b690decc846faHerb Derby void reset(); 1380497f088bb41338b1b1400556b9b690decc846faHerb Derby 1390497f088bb41338b1b1400556b9b690decc846faHerb Derbyprivate: 140c4e6cfe56220fd93a7635a98a034a72817a5283bHerb Derby using Footer = int64_t; 1410497f088bb41338b1b1400556b9b690decc846faHerb Derby using FooterAction = char* (char*); 1420497f088bb41338b1b1400556b9b690decc846faHerb Derby 143593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby static char* SkipPod(char* footerEnd); 144593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby static void RunDtorsOnBlock(char* footerEnd); 145593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby static char* NextBlock(char* footerEnd); 1460497f088bb41338b1b1400556b9b690decc846faHerb Derby 14739728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby void installFooter(FooterAction* releaser, uint32_t padding); 14839728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby void installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding); 14939728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby void installPtrFooter(FooterAction* action, char* ptr, uint32_t padding); 1500497f088bb41338b1b1400556b9b690decc846faHerb Derby 1511bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby void ensureSpace(uint32_t size, uint32_t alignment); 1520497f088bb41338b1b1400556b9b690decc846faHerb Derby 1531bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby char* allocObject(uint32_t size, uint32_t alignment); 1540497f088bb41338b1b1400556b9b690decc846faHerb Derby 1551bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby char* allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment); 1560497f088bb41338b1b1400556b9b690decc846faHerb Derby 1570497f088bb41338b1b1400556b9b690decc846faHerb Derby template <typename T> 1581bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby char* commonArrayAlloc(uint32_t count) { 1590497f088bb41338b1b1400556b9b690decc846faHerb Derby char* objStart; 1601bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby uint32_t arraySize = SkTo<uint32_t>(count * sizeof(T)); 1611bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby uint32_t alignment = SkTo<uint32_t>(alignof(T)); 1620497f088bb41338b1b1400556b9b690decc846faHerb Derby 1630497f088bb41338b1b1400556b9b690decc846faHerb Derby if (skstd::is_trivially_destructible<T>::value) { 1641bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby objStart = this->allocObject(arraySize, alignment); 1650497f088bb41338b1b1400556b9b690decc846faHerb Derby fCursor = objStart + arraySize; 1660497f088bb41338b1b1400556b9b690decc846faHerb Derby } else { 1671bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby uint32_t totalSize = arraySize + sizeof(Footer) + sizeof(uint32_t); 1681bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby objStart = this->allocObjectWithFooter(totalSize, alignment); 16939728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby 17039728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby // Can never be UB because max value is alignof(T). 17139728d331a1ae2989bc1922d3c97ee1fe3289670Herb Derby uint32_t padding = SkTo<uint32_t>(objStart - fCursor); 1720497f088bb41338b1b1400556b9b690decc846faHerb Derby 1730497f088bb41338b1b1400556b9b690decc846faHerb Derby // Advance to end of array to install footer.? 1740497f088bb41338b1b1400556b9b690decc846faHerb Derby fCursor = objStart + arraySize; 175593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby this->installUint32Footer( 176593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby [](char* footerEnd) { 177593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t)); 178593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby uint32_t count; 179593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby memmove(&count, objEnd, sizeof(uint32_t)); 180593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby char* objStart = objEnd - count * sizeof(T); 181593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby T* array = (T*) objStart; 182593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby for (uint32_t i = 0; i < count; i++) { 183593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby array[i].~T(); 184593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby } 185593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby return objStart; 186593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby }, 187593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby SkTo<uint32_t>(count), 188593cb94d1ce6f68a5b616cbfe3f4b69dc70832c3Herb Derby padding); 1890497f088bb41338b1b1400556b9b690decc846faHerb Derby } 1900497f088bb41338b1b1400556b9b690decc846faHerb Derby 1910497f088bb41338b1b1400556b9b690decc846faHerb Derby return objStart; 1920497f088bb41338b1b1400556b9b690decc846faHerb Derby } 1930497f088bb41338b1b1400556b9b690decc846faHerb Derby 1941bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby char* fDtorCursor; 1951bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby char* fCursor; 1961bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby char* fEnd; 1971bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby char* const fFirstBlock; 1981bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby const uint32_t fFirstSize; 1991bf3fc74b06fcc8121322a7ae68a72eacae79a24Herb Derby const uint32_t fExtraSize; 2007dd57b6a936af923a031f21c4ca9dc1031742473Herb Derby // Use the Fibonacci sequence as the growth factor for block size. The size of the block 2017dd57b6a936af923a031f21c4ca9dc1031742473Herb Derby // allocated is fFib0 * fExtraSize. Using 2 ^ n * fExtraSize had too much slop for Android. 2027dd57b6a936af923a031f21c4ca9dc1031742473Herb Derby uint32_t fFib0 {1}, fFib1 {1}; 2030497f088bb41338b1b1400556b9b690decc846faHerb Derby}; 2040497f088bb41338b1b1400556b9b690decc846faHerb Derby 20558b130681db4432c4937c2cb1b2529de628c6b19Mike Klein#endif//SkFixedAlloc_DEFINED 206