1/* Copyright 2019 Google LLC. All Rights Reserved.
2
3Licensed under the Apache License, Version 2.0 (the "License");
4you may not use this file except in compliance with the License.
5You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9Unless required by applicable law or agreed to in writing, software
10distributed under the License is distributed on an "AS IS" BASIS,
11WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12See the License for the specific language governing permissions and
13limitations 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
24namespace 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.
59class 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>
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>
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