third_party/pigweed/repo/pw_allocator/public/pw_allocator/freelist.h

   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 num_buckets>
  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 num_buckets>
  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
  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 num_buckets>
 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.
 109   explicit FreeListBuffer(std::initializer_list<size_t> sizes)
 110       : FreeList(chunks_, sizes_), sizes_(sizes), chunks_(num_buckets + 1, 0) {}
 111   explicit FreeListBuffer(std::array<size_t, num_buckets> sizes)
 112       : FreeList(chunks_, sizes_),
 113         sizes_(sizes.begin(), sizes.end()),
 114         chunks_(num_buckets + 1, 0) {}
 115
 116  private:
 117   Vector<size_t, num_buckets> sizes_;
 118   Vector<FreeList::FreeListNode*, num_buckets + 1> chunks_;
 119 };
 120
 121 }  // namespace pw::allocator