Fixed-size buddy allocator implementing the MemoryResource interface. The min block size is 1 byte, the maximum is 1<<64 bytes. More...

#include <flow_buddy_memory_resource.h>

Inheritance diagram for flow::BuddyMemoryResource:

Classes
struct	BuddyBlock

Public Member Functions
	BuddyMemoryResource (void *buffer, std::size_t capacity, std::size_t alignment=alignof(std::max_align_t))
	Constructs a buddy allocator over a user-provided buffer.
virtual void *	allocateImp (std::size_t bytes, std::size_t alignment) override
virtual void	deallocateImp (void *address, std::size_t bytes, std::size_t alignment) override
Public Member Functions inherited from flow::MemoryResource
virtual	~MemoryResource ()=default
void *	allocate (std::size_t bytes, std::size_t alignment=alignof(std::max_align_t))
void	deallocate (void *address, std::size_t bytes, std::size_t alignment=alignof(std::max_align_t))

Private Member Functions
std::size_t	getLevelSize (std::size_t level) const noexcept
BuddyBlock *	popFront (std::size_t level) noexcept
void	pushFront (BuddyBlock *block, std::size_t level) noexcept
bool	isEmpty (std::size_t level) const noexcept
BuddyBlock *	getBuddy (BuddyBlock *block, std::size_t blockSize) const noexcept
bool	eraseBlock (BuddyBlock *block, std::size_t level) noexcept

Private Attributes
std::byte *	beginBuffer_
std::size_t	capacity_
BuddyBlock	freeList_ [kMaxLevel]

Static Private Attributes
static constexpr std::size_t	kMaxLevel = 64

Detailed Description

Fixed-size buddy allocator implementing the MemoryResource interface. The min block size is 1 byte, the maximum is 1<<64 bytes.

Definition at line 13 of file flow_buddy_memory_resource.h.

Constructor & Destructor Documentation

◆ BuddyMemoryResource()

flow::BuddyMemoryResource::BuddyMemoryResource	(	void *	buffer,
		std::size_t	capacity,
		std::size_t	alignment = alignof(std::max_align_t) )

inlineexplicit

Constructs a buddy allocator over a user-provided buffer.

Parameters

buffer	Pointer to buffer.
capacity	Buffer size in bytes.
alignment	Required alignment.

Exceptions

std::bad_alloc If buffer cannot satisfy alignment.

Definition at line 76 of file flow_buddy_memory_resource.h.

      : freeList_() {
 
      // Not enough capacity after alignment.
      if (!std::align(alignment, alignment, buffer, capacity)) {
        throw std::bad_alloc();
      }
      beginBuffer_ = static_cast<std::byte*>(buffer);
      capacity_ = std::bit_floor(capacity);
 
      assert(capacity_ > 0 && "buffer capacity must be non-zero after alignment");
      std::size_t level = std::countr_zero(capacity_);
      pushFront(reinterpret_cast<BuddyBlock*>(beginBuffer_), level);
    }

References beginBuffer_, capacity_, freeList_, and pushFront().

Member Function Documentation

◆ allocateImp()

virtual void * flow::BuddyMemoryResource::allocateImp	(	std::size_t	bytes,
		std::size_t	alignment )

inlineoverridevirtual

Implements flow::MemoryResource.

Definition at line 91 of file flow_buddy_memory_resource.h.

                                                                             {
      std::size_t requiredLevel = std::countr_zero(std::bit_ceil(std::max(bytes, alignment)));
 
      // Find the smallest available block.
      std::size_t level = requiredLevel;
      while (level < kMaxLevel && isEmpty(level)) {
        ++level;
      }
 
      // All blocks are not big enough.
      if (level >= kMaxLevel) {
        throw std::bad_alloc();
      }
 
      BuddyBlock* block = popFront(level);
      while (level > requiredLevel) {
        --level;
        const std::size_t levelSize = getLevelSize(level);
 
        BuddyBlock* secondHalf = reinterpret_cast<BuddyBlock*>(reinterpret_cast<std::byte*>(block) + levelSize);
        pushFront(secondHalf, level);
      }
 
      return block;
    }

References getLevelSize(), isEmpty(), kMaxLevel, popFront(), and pushFront().

◆ deallocateImp()

virtual void flow::BuddyMemoryResource::deallocateImp	(	void *	address,
		std::size_t	bytes,
		std::size_t	alignment )

inlineoverridevirtual

Implements flow::MemoryResource.

Definition at line 117 of file flow_buddy_memory_resource.h.

                                                                                             {
      if (!address) {
        return;
      }
 
      std::size_t level = std::countr_zero(std::bit_ceil(std::max(bytes, alignment)));
      for (; level < kMaxLevel; ++level) {
        BuddyBlock* buddy = getBuddy(static_cast<BuddyBlock*>(address), getLevelSize(level));
        if (buddy && eraseBlock(buddy, level)) {
          // Coalesce two blocks.
          address = std::min(address, static_cast<void*>(buddy));
        } else {
          // Push it to the free list.
          pushFront(static_cast<BuddyBlock*>(address), level);
          break;
        }
      }
    }

References eraseBlock(), getBuddy(), getLevelSize(), kMaxLevel, and pushFront().

◆ eraseBlock()

bool flow::BuddyMemoryResource::eraseBlock	(	BuddyBlock *	block,
		std::size_t	level )

inlineprivatenoexcept

Definition at line 56 of file flow_buddy_memory_resource.h.

                                                                 {
      BuddyBlock* curr = &freeList_[level];
      while (curr->next) {
        BuddyBlock* child = curr->next;
        if (child == block) {
          curr->next = child->next;
          return true;
        }
        curr = child;
      }
      return false;
    }

References freeList_, and flow::BuddyMemoryResource::BuddyBlock::next.

Referenced by deallocateImp().

◆ getBuddy()

BuddyBlock * flow::BuddyMemoryResource::getBuddy	(	BuddyBlock *	block,
		std::size_t	blockSize ) const

inlineprivatenoexcept

Definition at line 45 of file flow_buddy_memory_resource.h.

                                                                                {
      std::size_t index = reinterpret_cast<std::byte*>(block) - beginBuffer_;
      std::size_t buddyIndex = index ^ blockSize;
      if (buddyIndex >= capacity_) {
        return nullptr;
      }
 
      BuddyBlock* buddyBlock = reinterpret_cast<BuddyBlock*>(beginBuffer_ + buddyIndex);
      return buddyBlock;
    }

References beginBuffer_, and capacity_.

Referenced by deallocateImp().

◆ getLevelSize()

std::size_t flow::BuddyMemoryResource::getLevelSize ( std::size_t level ) const

inlineprivatenoexcept

Definition at line 24 of file flow_buddy_memory_resource.h.

                                                           {
      return 1ull << level;
    }

Referenced by allocateImp(), and deallocateImp().

◆ isEmpty()

bool flow::BuddyMemoryResource::isEmpty ( std::size_t level ) const

inlineprivatenoexcept

Definition at line 41 of file flow_buddy_memory_resource.h.

                                                 {
      return !freeList_[level].next;
    }

References freeList_.

Referenced by allocateImp().

◆ popFront()

BuddyBlock * flow::BuddyMemoryResource::popFront ( std::size_t level )

inlineprivatenoexcept

Definition at line 28 of file flow_buddy_memory_resource.h.

                                                   {
      assert(freeList_[level].next != nullptr && "pop front from an empty list");
      BuddyBlock* block = freeList_[level].next;
      freeList_[level].next = block->next;
      return block;
    }

References freeList_, and flow::BuddyMemoryResource::BuddyBlock::next.

Referenced by allocateImp().

◆ pushFront()

void flow::BuddyMemoryResource::pushFront	(	BuddyBlock *	block,
		std::size_t	level )

inlineprivatenoexcept

Definition at line 35 of file flow_buddy_memory_resource.h.

                                                                {
      assert(level < kMaxLevel && "level is larger than the maximum possible level");
      block->next = freeList_[level].next;
      freeList_[level].next = block;
    }