buddy_allocator.h

// Copyright 2024 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#pragma once
 
#include <array>
#include <cstddef>
 
#include "pw_allocator/abstract_allocator.h"
#include "pw_allocator/block/basic.h"
#include "pw_allocator/bucket/unordered.h"
#include "pw_bytes/span.h"
#include "pw_containers/vector.h"
#include "pw_status/try.h"
 
namespace pw::allocator {
namespace internal {
 
class BuddyBlock : public BasicBlock<BuddyBlock> {
 public:
  BuddyBlock(size_t outer_size);
 
  StatusWithSize CanAlloc(Layout layout) const;
 
  BuddyBlock* Split();
 
  static BuddyBlock* Merge(BuddyBlock*&& left, BuddyBlock*&& right);
 
 private:
  // `Basic` required methods.
  using Basic = BasicBlock<BuddyBlock>;
  friend Basic;
  static constexpr size_t DefaultAlignment() { return 1; }
  static constexpr size_t BlockOverhead() { return sizeof(BuddyBlock); }
  static constexpr size_t MinInnerSize() { return sizeof(UnorderedItem); }
  constexpr size_t OuterSizeUnchecked() const { return 1U << outer_size_log2_; }
 
  uint8_t outer_size_log2_;
};
 
class GenericBuddyAllocator : public AbstractAllocator {
 public:
  static constexpr Capabilities kCapabilities =
      kImplementsGetUsableLayout | kImplementsGetAllocatedLayout |
      kImplementsGetCapacity | kImplementsRecognizes;
 
  static constexpr size_t kDefaultMinOuterSize = 16;
  static constexpr size_t kDefaultNumBuckets = 16;
 
  void InitBuckets(span<UnorderedBucket<BuddyBlock>> buckets,
                   size_t min_outer_size);
 
  void Init(ByteSpan region);
 
 protected:
  constexpr GenericBuddyAllocator() : AbstractAllocator(kCapabilities) {}
 
  void* DoAllocate(Layout layout) override;
 
  void DoDeallocate(void* ptr) override;
 
  Result<Layout> DoGetInfo(InfoType info_type, const void* ptr) const override;
 
  void CrashIfAllocated();
 
 private:
  span<UnorderedBucket<BuddyBlock>> buckets_;
  size_t min_outer_size_ = 0;
  ByteSpan region_;
};
 
}  // namespace internal
 
 
template <size_t kMinOuterSize_ =
              internal::GenericBuddyAllocator::kDefaultMinOuterSize,
          size_t kNumBuckets =
              internal::GenericBuddyAllocator::kDefaultNumBuckets>
class BuddyAllocator : public internal::GenericBuddyAllocator {
 private:
  using Base = internal::GenericBuddyAllocator;
 
 public:
  static constexpr size_t kMinOuterSize = kMinOuterSize_;
 
  static_assert((kMinOuterSize & (kMinOuterSize - 1)) == 0,
                "kMinOuterSize must be a power of 2");
 
  constexpr BuddyAllocator() { Base::InitBuckets(buckets_, kMinOuterSize); }
 
  BuddyAllocator(ByteSpan region) : BuddyAllocator() { Base::Init(region); }
 
  ~BuddyAllocator() override { Base::CrashIfAllocated(); }
 
 private:
  std::array<UnorderedBucket<internal::BuddyBlock>, kNumBuckets> buckets_;
};
 
 
}  // namespace pw::allocator