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 #include <span> 18 19 #include "pw_containers/vector.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 implementation for an allocator. 28 // This implementation buckets by chunk size, with a list of user-provided 29 // buckets. Each bucket is a linked list of storage chunks. Because this 30 // freelist uses the added chunks themselves as list nodes, there is lower bound 31 // of sizeof(FreeList.FreeListNode) bytes for chunks which can be added to this 32 // freelist. There is also an implicit bucket for "everything else", for chunks 33 // which do not fit into a bucket. 34 // 35 // Each added chunk will be added to the smallest bucket under which it fits. If 36 // 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 sizes 40 // {64, 128, 256 and 512} bytes. The internal state may look like the following. 41 // 42 // bucket[0] (64B) --> chunk[12B] --> chunk[42B] --> chunk[64B] --> NULL 43 // bucket[1] (128B) --> chunk[65B] --> chunk[72B] --> NULL 44 // bucket[2] (256B) --> NULL 45 // bucket[3] (512B) --> chunk[312B] --> chunk[512B] --> chunk[416B] --> NULL 46 // bucket[4] (implicit) --> chunk[1024B] --> chunk[513B] --> NULL 47 // 48 // Note that added chunks should be aligned to a 4-byte boundary. 49 // 50 // This class is split into two parts; FreeList implements all of the 51 // logic, and takes in pointers for two pw::Vector instances for its storage. 52 // This prevents us from having to specialise this class for every kMaxSize 53 // parameter for the vector. FreeListBuffer then provides the storage for these 54 // two pw::Vector instances and instantiates FreeListInternal. 55 class FreeList { 56 public: 57 // Remove copy/move ctors 58 FreeList(const FreeList& other) = delete; 59 FreeList(FreeList&& other) = delete; 60 FreeList& operator=(const FreeList& other) = delete; 61 FreeList& operator=(FreeList&& other) = delete; 62 63 // Adds a chunk to this freelist. Returns: 64 // OK: The chunk was added successfully 65 // OUT_OF_RANGE: The chunk could not be added for size reasons (e.g. if 66 // the chunk is too small to store the FreeListNode). 67 Status AddChunk(std::span<std::byte> chunk); 68 69 // Finds an eligible chunk for an allocation of size `size`. Note that this 70 // will return the first allocation possible within a given bucket, it does 71 // not currently optimize for finding the smallest chunk. Returns a std::span 72 // representing the chunk. This will be "valid" on success, and will have size 73 // = 0 on failure (if there were no chunks available for that allocation). 74 std::span<std::byte> FindChunk(size_t size) const; 75 76 // Remove a chunk from this freelist. Returns: 77 // OK: The chunk was removed successfully 78 // NOT_FOUND: The chunk could not be found in this freelist. 79 Status RemoveChunk(std::span<std::byte> chunk); 80 81 private: 82 // For a given size, find which index into chunks_ the node should be written 83 // to. 84 size_t FindChunkPtrForSize(size_t size, bool non_null) const; 85 86 private: 87 template <size_t kNumBuckets> 88 friend class FreeListBuffer; 89 90 struct FreeListNode { 91 // TODO: Double-link this? It'll make removal easier/quicker. 92 FreeListNode* next; 93 size_t size; 94 }; 95 FreeList(Vector<FreeListNode * > & chunks,Vector<size_t> & sizes)96 constexpr FreeList(Vector<FreeListNode*>& chunks, Vector<size_t>& sizes) 97 : chunks_(chunks), sizes_(sizes) {} 98 99 Vector<FreeListNode*>& chunks_; 100 Vector<size_t>& sizes_; 101 }; 102 103 // Holder for FreeList's storage. 104 template <size_t kNumBuckets> 105 class FreeListBuffer : public FreeList { 106 public: 107 // These constructors are a little hacky because of the initialization order. 108 // Because FreeList has a trivial constructor, this is safe, however. FreeListBuffer(std::initializer_list<size_t> sizes)109 explicit FreeListBuffer(std::initializer_list<size_t> sizes) 110 : FreeList(chunks_, sizes_), sizes_(sizes), chunks_(kNumBuckets + 1, 0) {} FreeListBuffer(std::array<size_t,kNumBuckets> sizes)111 explicit FreeListBuffer(std::array<size_t, kNumBuckets> sizes) 112 : FreeList(chunks_, sizes_), 113 sizes_(sizes.begin(), sizes.end()), 114 chunks_(kNumBuckets + 1, 0) {} 115 116 private: 117 Vector<size_t, kNumBuckets> sizes_; 118 Vector<FreeList::FreeListNode*, kNumBuckets + 1> chunks_; 119 }; 120 121 } // namespace pw::allocator 122