1 /* Copyright 2019 Google LLC. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #ifndef RUY_RUY_ALLOCATOR_H_ 17 #define RUY_RUY_ALLOCATOR_H_ 18 19 #include <cstddef> 20 #include <cstdint> 21 #include <memory> 22 #include <vector> 23 24 namespace ruy { 25 26 // Specialized allocator designed to converge to a steady-state where all 27 // allocations are bump-ptr allocations from an already-allocated buffer. 28 // 29 // To support these constraints, this allocator only supports two 30 // operations. 31 // - AllocateBytes/Allocate<Pointer>: allocates a pointer to storage of a 32 // specified size, which will be aligned to kMinimumBlockAlignment. 33 // - FreeAll: frees all previous allocations (but retains the internal 34 // buffer to minimize future calls into the system allocator). 35 // 36 // This class is specialized for supporting just those two operations 37 // under this specific steady-state usage pattern. Extending this class 38 // with new allocation interfaces that don't fit that pattern is probably not 39 // the right choice. Instead, build a new class on top of 40 // SystemAlignedAlloc/SystemAlignedFree. 41 // 42 // All operations happen on aligned blocks for simplicity. 43 // 44 // Theory of operation: 45 // 46 // - ptr_, current_, and size_ implement a basic bump-ptr allocator. 47 // 48 // - in AllocateBytes, the fast path is just a bump-ptr 49 // allocation. If our bump-ptr allocator doesn't have enough space for an 50 // allocation, then we allocate a block from the system allocator to 51 // service the allocation request. We save that block in fallback_blocks_ 52 // and track the total size of the fallback blocks in 53 // fallback_blocks_total_size_. 54 // 55 // - in FreeAll, the fast path just resets the bump-ptr allocator. If 56 // there are any fallback blocks, we free them and reallocate the 57 // bump-ptr allocator's buffer so that the next sequence of allocations 58 // will hopefully not need any fallback blocks. 59 class Allocator final { 60 public: 61 ~Allocator(); 62 63 // Allocate a buffer. 64 void* AllocateBytes(std::ptrdiff_t num_bytes); 65 // Allocate a buffer, trying to avoid having its address close to aliasing 66 // the specified `to_avoid` in the L1D cache. 67 void* AllocateBytesAvoidingAliasingWith(std::ptrdiff_t num_bytes, 68 const void* to_avoid); 69 // Allocate an array of `count` elements of type T. 70 template <typename T> Allocate(std::ptrdiff_t count)71 T* Allocate(std::ptrdiff_t count) { 72 return static_cast<T*>(AllocateBytes(count * sizeof(T))); 73 } 74 // Allocate an array of `count` elements of the given `Pointer` type's 75 // element_type. 76 template <typename Pointer> Allocate(std::ptrdiff_t count,Pointer * out)77 void Allocate(std::ptrdiff_t count, Pointer* out) { 78 using T = typename std::pointer_traits<Pointer>::element_type; 79 *out = Allocate<T>(count); 80 } 81 82 // Free all allocated blocks. Internally consolidate allocated buffers as 83 // explained in the class comment. 84 void FreeAll(); 85 86 private: 87 void operator=(const Allocator&) = delete; 88 void* AllocateFast(std::ptrdiff_t num_bytes); 89 void* AllocateSlow(std::ptrdiff_t num_bytes); 90 91 void* ptr_ = nullptr; 92 std::ptrdiff_t current_ = 0; 93 std::ptrdiff_t size_ = 0; 94 std::vector<void*> fallback_blocks_; 95 std::ptrdiff_t fallback_blocks_total_size_ = 0; 96 }; 97 98 } // namespace ruy 99 100 #endif // RUY_RUY_ALLOCATOR_H_ 101