1 // Copyright 2020 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://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, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <array> 17 18 #include "pw_containers/vector.h" 19 #include "pw_span/span.h" 20 #include "pw_status/status.h" 21 22 namespace pw::allocator { 23 24 template <size_t kNumBuckets> 25 class FreeListBuffer; 26 27 /// Basic [freelist](https://en.wikipedia.org/wiki/Free_list) implementation 28 /// for an allocator. This implementation buckets by chunk size, with a list 29 /// of user-provided buckets. Each bucket is a linked list of storage chunks. 30 /// Because this freelist uses the added chunks themselves as list nodes, there 31 /// is a lower bound of `sizeof(FreeList.FreeListNode)` bytes for chunks which 32 /// can be added to this freelist. There is also an implicit bucket for 33 /// "everything else", for chunks which do not fit into a bucket. 34 /// 35 /// Each added chunk will be added to the smallest bucket under which it fits. 36 /// If it does not fit into any user-provided bucket, it will be added to the 37 /// default bucket. 38 /// 39 /// As an example, assume that the `FreeList` is configured with buckets of 40 /// sizes {64, 128, 256, and 512} bytes. The internal state may look like the 41 /// following: 42 /// 43 /// @code{.unparsed} 44 /// bucket[0] (64B) --> chunk[12B] --> chunk[42B] --> chunk[64B] --> NULL 45 /// bucket[1] (128B) --> chunk[65B] --> chunk[72B] --> NULL 46 /// bucket[2] (256B) --> NULL 47 /// bucket[3] (512B) --> chunk[312B] --> chunk[512B] --> chunk[416B] --> NULL 48 /// bucket[4] (implicit) --> chunk[1024B] --> chunk[513B] --> NULL 49 /// @endcode 50 /// 51 /// Note that added chunks should be aligned to a 4-byte boundary. 52 /// 53 /// This class is split into two parts: 54 /// * `FreeList` implements all of the logic, and takes in pointers for two 55 /// `pw::Vector` instances for its storage. This prevents us from having to 56 /// specialise this class for every `kMaxSize` parameter for the vector. 57 /// * `FreeListBuffer` then provides the storage for these two `pw::Vector` 58 /// instances and instantiates `FreeListInternal`. 59 class FreeList { 60 public: 61 // Remove copy/move ctors 62 FreeList(const FreeList& other) = delete; 63 FreeList(FreeList&& other) = delete; 64 FreeList& operator=(const FreeList& other) = delete; 65 FreeList& operator=(FreeList&& other) = delete; 66 67 /// Adds a chunk to this freelist. 68 /// 69 /// @returns @rst 70 /// 71 /// .. pw-status-codes:: 72 /// 73 /// OK: The chunk was added successfully. 74 /// 75 /// OUT_OF_RANGE: The chunk could not be added for size reasons (e.g. the 76 /// chunk is too small to store the ``FreeListNode``). 77 /// 78 /// @endrst 79 Status AddChunk(span<std::byte> chunk); 80 81 /// Finds an eligible chunk for an allocation of size `size`. 82 /// 83 /// @note This returns the first allocation possible within a given bucket; 84 /// It does not currently optimize for finding the smallest chunk. 85 /// 86 /// @returns 87 /// * On success - A span representing the chunk. 88 /// * On failure (e.g. there were no chunks available for that allocation) - 89 /// A span with a size of 0. 90 span<std::byte> FindChunk(size_t size) const; 91 92 /// Removes a chunk from this freelist. 93 /// 94 /// @returns @rst 95 /// 96 /// .. pw-status-codes:: 97 /// 98 /// OK: The chunk was removed successfully. 99 /// 100 /// NOT_FOUND: The chunk could not be found in this freelist. 101 /// 102 /// @endrst 103 Status RemoveChunk(span<std::byte> chunk); 104 105 private: 106 // For a given size, find which index into chunks_ the node should be written 107 // to. 108 unsigned short FindChunkPtrForSize(size_t size, bool non_null) const; 109 110 private: 111 template <size_t kNumBuckets> 112 friend class FreeListBuffer; 113 114 struct FreeListNode { 115 // TODO(jgarside): Double-link this? It'll make removal easier/quicker. 116 FreeListNode* next; 117 size_t size; 118 }; 119 FreeList(Vector<FreeListNode * > & chunks,Vector<size_t> & sizes)120 constexpr FreeList(Vector<FreeListNode*>& chunks, Vector<size_t>& sizes) 121 : chunks_(chunks), sizes_(sizes) {} 122 123 Vector<FreeListNode*>& chunks_; 124 Vector<size_t>& sizes_; 125 }; 126 127 // Holder for FreeList's storage. 128 template <size_t kNumBuckets> 129 class FreeListBuffer : public FreeList { 130 public: 131 // These constructors are a little hacky because of the initialization order. 132 // Because FreeList has a trivial constructor, this is safe, however. FreeListBuffer(std::initializer_list<size_t> sizes)133 explicit FreeListBuffer(std::initializer_list<size_t> sizes) 134 : FreeList(chunks_, sizes_), sizes_(sizes), chunks_(kNumBuckets + 1, 0) {} FreeListBuffer(std::array<size_t,kNumBuckets> sizes)135 explicit FreeListBuffer(std::array<size_t, kNumBuckets> sizes) 136 : FreeList(chunks_, sizes_), 137 sizes_(sizes.begin(), sizes.end()), 138 chunks_(kNumBuckets + 1, 0) {} 139 140 private: 141 Vector<size_t, kNumBuckets> sizes_; 142 Vector<FreeList::FreeListNode*, kNumBuckets + 1> chunks_; 143 }; 144 145 } // namespace pw::allocator 146