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_alignment/alignment.h"
#include "pw_allocator/allocator.h"
#include "pw_allocator/bucket.h"
#include "pw_bytes/span.h"
#include "pw_containers/vector.h"
#include "pw_status/try.h"
 
namespace pw::allocator {
namespace internal {
 
class GenericBuddyAllocator final {
 public:
  static constexpr Capabilities kCapabilities =
      kImplementsGetUsableLayout | kImplementsGetAllocatedLayout |
      kImplementsGetCapacity | kImplementsRecognizes;
 
  GenericBuddyAllocator(span<Bucket> buckets, size_t min_chunk_size);
 
  void Init(ByteSpan region);
 
  void* Allocate(Layout layout);
 
  void Deallocate(void* ptr);
 
  size_t GetCapacity() const { return region_.size(); }
 
  Result<Layout> GetLayout(const void* ptr) const;
 
  void CrashIfAllocated();
 
 private:
  span<Bucket> buckets_;
  ByteSpan region_;
};
 
}  // namespace internal
 
template <size_t kMinChunkSize, size_t kNumBuckets>
class BuddyAllocator : public Allocator {
 public:
  static_assert((kMinChunkSize & (kMinChunkSize - 1)) == 0,
                "kMinChunkSize must be a power of 2");
 
  BuddyAllocator() : impl_(buckets_, kMinChunkSize) {}
 
  BuddyAllocator(ByteSpan region) : BuddyAllocator() { Init(region); }
 
  void Init(ByteSpan region) { impl_.Init(region); }
 
  ~BuddyAllocator() override { impl_.CrashIfAllocated(); }
 
 private:
  void* DoAllocate(Layout layout) override {
    // Reserve one byte to save the bucket index.
    return impl_.Allocate(layout.Extend(1));
  }
 
  void DoDeallocate(void* ptr) override { impl_.Deallocate(ptr); }
 
  Result<Layout> DoGetInfo(InfoType info_type, const void* ptr) const override {
    switch (info_type) {
      case InfoType::kUsableLayoutOf: {
        Layout layout;
        PW_TRY_ASSIGN(layout, impl_.GetLayout(ptr));
        return Layout(layout.size() - 1, layout.alignment());
      }
      case InfoType::kAllocatedLayoutOf:
        return impl_.GetLayout(ptr);
      case InfoType::kCapacity:
        return Layout(impl_.GetCapacity(), kMinChunkSize);
      case InfoType::kRecognizes: {
        Layout layout;
        PW_TRY_ASSIGN(layout, impl_.GetLayout(ptr));
        return Layout();
      }
      case InfoType::kRequestedLayoutOf:
      default:
        return Status::Unimplemented();
    }
  }
 
  std::array<internal::Bucket, kNumBuckets> buckets_;
  internal::GenericBuddyAllocator impl_;
};
 
}  // namespace pw::allocator