buddy_alloc

// vim:set ft=cpp: -*- Mode: C++ -*-
/*
 * Copyright (C) 2026 Kernkonzept GmbH.
 * Author(s): Georg Kotheimer <georg.kotheimer@kernkonzept.com>
 *
 * License: see LICENSE.spdx (in this directory or the directories above)
 */
 
#pragma once
 
#include <l4/cxx/arith>
#include <l4/cxx/minmax>
#include <l4/cxx/type_traits>
#include <l4/sys/compiler.h>
#include <l4/sys/consts.h>
#include <l4/sys/l4int.h>
 
#include <cassert>
#include <cstddef>
#include <cstdio>
 
namespace cxx
{

class Buddy_alloc
{
public:
  static constexpr bool Debug_alloc = false;
#ifdef NDEBUG
  static constexpr bool Print_warnings = false;
#else
  static constexpr bool Print_warnings = true;
#endif
 
public:
  static constexpr unsigned Min_order = L4_PAGESHIFT;
  static constexpr size_t Min_size = 1UL << Min_order;
 
  // OPTIMIZE: Use only exactly as many bits as necessary per level.
  using Order_free = l4_uint8_t;
 
  static constexpr unsigned long Invalid_node_index = 0;
  static constexpr unsigned long Root_node_index = 1;
 
  struct Node_ptr
  {
    unsigned long index; // 1-based index
    unsigned level;
 
    Node_ptr() : index(Invalid_node_index), level(0) {}
    Node_ptr(unsigned long index, unsigned level) : index(index), level(level)
    {}
 
    Node_ptr parent() const
    {
      assert(!is_root());
      return Node_ptr{index / 2, level + 1};
    }
 
    Node_ptr left_child() const
    {
      assert(!is_leaf());
      return Node_ptr{index * 2, level - 1};
    }
 
    Node_ptr right_child() const
    {
      assert(!is_leaf());
      return Node_ptr{(index * 2) + 1, level - 1};
    }
 
    bool valid() const { return index != Invalid_node_index; }
    bool is_left() const { return index % 2 == 0; }
    bool is_right() const { return index % 2 == 1; }
    bool is_root() const { return index == Root_node_index; }
    bool is_leaf() const { return level == 0; }
 
    friend constexpr bool operator==(Node_ptr const &lhs,
                                     Node_ptr const &rhs)
    { return lhs.index == rhs.index && lhs.level == rhs.level; }
 
    friend constexpr bool operator!=(Node_ptr const &lhs,
                                     Node_ptr const &rhs)
    { return !(lhs == rhs); }
  };

  static constexpr size_t metadata_bytes(l4_addr_t min_addr, l4_addr_t max_addr)
  {
    return num_tree_nodes(min_addr, max_addr) * sizeof(Order_free);
  }
 
  bool initialized() const { return _tree != nullptr; }

  void init(l4_addr_t min_addr, l4_addr_t max_addr,
            unsigned char *metadata_addr, size_t metadata_size)
  {
    assert(metadata_bytes(min_addr, max_addr) <= metadata_size);
 
    l4_uint64_t max_mem_size;
    calc_mem_range(min_addr, max_addr, &_base, &max_mem_size);
    _base = to_min_size_units(_base);
    _max_mem_size = to_min_size_units(max_mem_size);
    _max_level = cxx::arith::log2u(_max_mem_size);
    _tree = metadata_addr;
    // Initially the entire tree is unavailable.
    __builtin_memset(_tree, 0, metadata_size);
 
    if constexpr (Debug_alloc)
      {
        printf("Buddy allocator info:\n");
        printf("  Metadata size: %zu (%zu KiB)\n",
               metadata_size, metadata_size / 1024);
        printf("  Base address: %#lx\n", from_min_size_units(_base));
        printf("  Max mem size: %#llx\n", _max_mem_size * l4_uint64_t{Min_size});
        printf("  Max mem order: %u\n", _max_level + Min_order);
        printf("  Range: [%#lx, %#lx]\n", min_addr, max_addr);
        printf("  Max level: %u\n", _max_level);
        printf("  Total number of nodes: %lu\n",
               num_tree_nodes(min_addr, max_addr));
        printf("  Levels:\n");
        for (int level = _max_level; level >= 0; level--)
          {
            printf("    %2d: size=%#llx start_index=%ld, nodes=%ld\n", level,
                   block_size_for_level(level) * l4_uint64_t{Min_size},
                   level_start_index(level), nodes_in_level(level));
          }
      }
  }

  inline void add_mem(void *mem, size_t size);

  inline void *alloc(size_t size, size_t align, l4_addr_t lower = 0,
                     l4_addr_t upper = ~0UL);

  inline void *alloc_max(size_t min, size_t *max, size_t align,
                         size_t granularity, l4_addr_t lower = 0,
                         l4_addr_t upper = ~0UL);

  inline void free(void *block, size_t size);

  inline size_t avail() const;
 
  template<typename DBG>
  void dump_free(DBG &out) const;
 
private:
  struct Mem_range
  {
    l4_addr_t start;
    l4_addr_t end; // inclusive
 
    Mem_range() : start(static_cast<l4_addr_t>(-1)), end(0) {}
    Mem_range(l4_addr_t start, l4_addr_t end) : start(start), end(end)
    { assert(valid()); }
 
    bool valid() const
    { return start <= end; }
 
    size_t size() const
    { return end - start + 1; }
 
    friend bool operator < (Mem_range const &lhs, Mem_range const &rhs)
    { return lhs.end < rhs.start; }
 
    bool overlaps(Mem_range const &o) const
    { return !(*this < o) && !(o < *this); }
 
    bool contains(Mem_range const &o) const
    { return start <= o.start && end >= o.end; }
 
    Mem_range intersect(Mem_range const &o) const
    {
      if (!overlaps(o))
        return Mem_range();
 
      return Mem_range{start > o.start ? start : o.start,
                       end < o.end ? end : o.end};
    }
  };

  template<typename T>
  static constexpr T ceil_power_of_two(T val)
  {
    return T{1} << cxx::arith::log2u_ceil(val);
  }
 
  template<typename T>
  static constexpr T trunc_power_of_two(T val)
  {
    return T{1} << cxx::arith::log2u(val);
  }
 
  template<typename T>
  static constexpr bool is_power_of_two(T val)
  {
    return val > 0 && (val & (val - 1)) == 0;
  }
 
  template<typename T, typename B>
  static constexpr T ceil_to(T val, B boundary)
  {
    assert(is_power_of_two(boundary));
    return (val + boundary - 1) & ~T{boundary - 1};
  }
 
  template<typename T, typename B>
  static constexpr T trunc_to(T val, B boundary)
  {
    assert(is_power_of_two(boundary));
    return val & ~T{boundary - 1};
  }
 
  template<typename T, typename B>
  static constexpr bool is_aligned_to(T val, B boundary)
  {
    return trunc_to(val, boundary) == val;
  }
 
  static constexpr unsigned trailing_zeroes(unsigned val)
  {
    return val ? __builtin_ctz(val) : sizeof(unsigned) * 8;
  }
 
  static constexpr unsigned trailing_zeroes(unsigned long val)
  {
    return val ? __builtin_ctzl(val) : sizeof(unsigned long) * 8;
  }

  template<typename T>
  static constexpr T to_min_size_units(T val)
  {
    assert(is_aligned_to(val, Min_size));
    return val / Min_size;
  }

  template<typename T>
  static constexpr T from_min_size_units(T val)
  {
    assert((val * Min_size) / Min_size == val);
    return val * Min_size;
  }

  static constexpr void calc_mem_range(l4_addr_t min_addr, l4_addr_t max_addr,
                                       l4_addr_t *base_addr,
                                       l4_uint64_t *max_size)
  {
    assert(min_addr < max_addr);
    l4_uint64_t raw_size = max_addr - min_addr + l4_uint64_t{1};
    assert(raw_size >= Min_size);
 
    *max_size = ceil_power_of_two(raw_size);
    *base_addr = trunc_to(l4_uint64_t{min_addr}, *max_size);
    // Adjust max block size and base address, until they cover the entire
    // requested memory area.
    // The covered range is [base_addr, base_addr + max_size - 1], thus
    // `max_addr` is only included if `max_size > max_addr - base_addr`.
    while (*max_size <= max_addr - *base_addr)
      {
        // Max address not included after alignment, use next power of two.
        assert(*max_size < (l4_uint64_t{1} << 63));
        *max_size *= 2;
        *base_addr = trunc_to(l4_uint64_t{min_addr}, *max_size);
      }
  }
 
  static constexpr unsigned long num_tree_nodes(l4_addr_t min_addr,
                                                l4_addr_t max_addr)
  {
    l4_addr_t base_addr = 0;
    l4_uint64_t max_mem_size = 0;
    calc_mem_range(min_addr, max_addr, &base_addr, &max_mem_size);
    // OPTIMIZE: Only allocate tree storage for the memory between min_range and
    //           max_range.
    auto actual_nodes = ((2 * max_mem_size) - 1) / Min_size;
    // The tree uses 1-based indexes for efficient parent/child navigation. For
    // simplicity the node at index 0 is unused.
    return actual_nodes + 1;
  }
 
  unsigned long nodes_in_level(unsigned level) const
  {
    return 1UL << (_max_level - level);
  }
 
  unsigned long level_start_index(unsigned level) const
  {
    return nodes_in_level(level);
  }
 
  static unsigned level_for_block_size(size_t size)
  {
    assert(is_power_of_two(size)); // power of two, so a block size.
    return cxx::arith::log2u(size);
  }

  static l4_size_t block_size_for_level(unsigned level)
  {
    return l4_size_t{1} << level;
  }
 
  Node_ptr node_for_block_level(l4_addr_t addr, unsigned level) const
  {
    size_t node_size = block_size_for_level(level);
 
    assert(addr >= _base);
    assert(addr + node_size > addr);
    assert(addr + node_size <= _base + _max_mem_size);
    assert(is_aligned_to(addr, node_size));
 
    unsigned long index = level_start_index(level) + ((addr - _base) / node_size);
    return Node_ptr{index, level};
  }
 
  Node_ptr node_for_block(l4_addr_t addr, size_t node_size) const
  {
    assert(addr >= _base);
    assert(addr + node_size > addr);
    assert(addr + node_size <= _base + _max_mem_size);
    assert(is_aligned_to(addr, node_size));
 
    unsigned level = level_for_block_size(node_size);
    unsigned long index = level_start_index(level) + ((addr - _base) / node_size);
    return Node_ptr{index, level};
  }
 
  l4_addr_t block_start_addr(Node_ptr node) const
  {
    size_t size = block_size_for_level(node.level);
    size_t offset = (node.index - level_start_index(node.level)) * size;
    return _base + offset;
  }
 
  l4_addr_t block_end_addr(Node_ptr node) const
  {
    l4_addr_t block_start = block_start_addr(node);
    size_t block_size = block_size_for_level(node.level);
    return block_start + block_size - 1;
  }
 
  Mem_range block_range(Node_ptr node) const
  {
    return Mem_range{block_start_addr(node), block_end_addr(node)};
  }
 
  static bool fits_level(Order_free node_order, unsigned level)
  {
    // Because 0 marks allocated nodes, the largest free order of node is stored
    // as level+1.
    return node_order > level;
  }

  static unsigned min_level_required_for_size(size_t size)
  {
    // The intuition for this computation comes from looking at the worst case.
    // In the following example 1 unit corresponds to Min_size.
    // The "worst" placement that avoids an aligned block of size B is:
    //   - Start 1 unit after a block boundary.
    //   - End 1 unit before the block boundary after the next block.
    // The interval spanned by these two almost complete blocks is `B - 1` each,
    // so `2B - 2` in total. From that we can derive that each span with a
    // length `n > 2B - 2` or `n >= 2B - 1` must contain an aligned block of
    // size B. Solve for B, and arrive at: `min_B = (n + 1) / 2`
    return cxx::arith::log2u((size + 1) / 2);
  }
 
  Order_free node_get(Node_ptr node) const
  {
    assert(node.valid());
    return _tree[node.index];
  }
 
  void node_set(Node_ptr node, Order_free largest_order)
  {
    _tree[node.index] = largest_order;
  }

  bool node_is_free(Node_ptr node) const
  {
    return node_get(node) == node.level + 1;
  }

  bool node_is_used(Node_ptr node) const { return node_get(node) == 0; }
 
  void node_set_free(Node_ptr node) { node_set(node, node.level + 1); }
  void node_set_used(Node_ptr node) { node_set(node, 0); }
 
  Node_ptr root_node() const { return Node_ptr{Root_node_index, _max_level}; }
 
  bool node_is_seperately_allocated(Node_ptr node)
  {
    // If both children of the node are marked as used, the node was not
    // allocated as a whole, but rather both child nodes separately by
    // two independent allocations. Freeing it as a single node would leave
    // the children behind as used and thus corrupt the tree.
    return !node.is_leaf() && node_is_used(node.left_child())
           && node_is_used(node.right_child());
  }
 
  enum class Walk_dir
  {
    Descend, // Descend into the children of the node.
    Next,    // Go to next node (sibling, or up through parent chain).
    Stop,    // Stop tree walk.
  };

  template<typename CB>
  bool tree_walk(CB const &cb, Node_ptr root) const
  {
    // Invokes callback and returns whether tree walk should descend further.
    auto handle_node = [&cb](Node_ptr &node)
      {
        Walk_dir dir = cb(node);
        if (dir == Walk_dir::Descend && node.is_leaf())
          dir = Walk_dir::Next;
        return dir;
      };
 
    if (handle_node(root) != Walk_dir::Descend)
      return true;
 
    Node_ptr cur = root.left_child();
    for (;;)
      {
        auto dir = handle_node(cur);
        if (dir == Walk_dir::Stop)
          return false;
 
        if (dir == Walk_dir::Descend)
          {
            cur = cur.left_child();
            continue;
          }
 
        // Walk_dir::Next
        if (cur.is_left())
          cur = cur.parent().right_child();
        else if (cur.is_right())
          {
            // Bubble up chain of parents to determine next node.
            Node_ptr parent = cur.parent();
            while (parent != root && parent.is_right())
              parent = parent.parent();
            if (parent == root)
              return true; // walk done
            cur = parent.parent().right_child();
          }
      }
  }

  template<typename CB>
  void tree_walk_free(CB const &cb) const
  {
    tree_walk([this, &cb](Node_ptr const &node)
      {
        if (node_is_free(node))
          {
            cb(node);
            return Walk_dir::Next; // encountered free node, bubble up
          }
 
        // Descend only if node is split.
        return node_is_used(node) ? Walk_dir::Next : Walk_dir::Descend;
      }, root_node());
  }

  Node_ptr find_bounded_root(unsigned desired_level,
                             Mem_range const &alloc_range)
  {
    Node_ptr node = root_node();
    while (node.level > desired_level)
      {
        // Must not descend into subtree shadowed by an allocated node.
        if (node_is_used(node))
          break;
 
        auto left = node.left_child();
        auto right = node.right_child();
        if (block_range(left).contains(alloc_range))
          node = left; // Left child contains range.
        else if (block_range(right).contains(alloc_range))
          node = right; // Rights child contains range.
        else
          break; // Parent node contains range (or is the root of the tree).
      }
    return node;
  }
 
  static Node_ptr next_node(Node_ptr node, Node_ptr root)
  {
    assert(node.valid());
    if (L4_UNLIKELY(node == root))
      return Node_ptr();
 
    if (node.is_left())
      node = node.parent().right_child();
    else if (node.is_right())
      {
        // Bubble up chain of parents to determine next node.
        Node_ptr parent = node.parent();
        while (parent != root && parent.is_right())
          parent = parent.parent();
        if (parent == root)
          return Node_ptr();
        node = parent.parent().right_child();
      }
    return node;
  }
 
  static Node_ptr prev_node(Node_ptr node, Node_ptr root)
  {
    assert(node.valid());
    if (L4_UNLIKELY(node == root))
      return Node_ptr();
 
    if (node.is_right())
      node = node.parent().left_child();
    else if (node.is_left())
      {
        // Bubble up chain of parents to determine next node.
        Node_ptr parent = node.parent();
        while (parent != root && parent.is_left())
          parent = parent.parent();
        if (parent == root)
          return Node_ptr();
        node = parent.parent().left_child();
      }
    return node;
  }
 
  Node_ptr next_adjacent_free(Node_ptr node, Node_ptr root)
  {
    Node_ptr next = next_node(node, root);
    if (!next.valid())
      return Node_ptr();
 
    while (!node_is_free(next))
      {
        if (next.is_leaf() || node_is_used(next))
          return Node_ptr();
        next = next.left_child();
      }
    return next;
  }
 
  Node_ptr prev_adjacent_free(Node_ptr node, Node_ptr root)
  {
    Node_ptr prev = prev_node(node, root);
    if (!prev.valid())
      return Node_ptr();
 
    while (!node_is_free(prev))
      {
        if (prev.is_leaf() || node_is_used(prev))
          return Node_ptr();
        prev = prev.right_child();
      }
    return prev;
  }

  Node_ptr next_node_in_range(l4_addr_t cur_addr, l4_size_t remaining_size)
  {
    unsigned next_level = cxx::min(
      trailing_zeroes(cur_addr),
      trailing_zeroes(trunc_power_of_two(remaining_size)));
    return node_for_block_level(cur_addr, next_level);
  }
 
  [[nodiscard]] static bool normalize_size_align(size_t &size, size_t &align)
  {
    size = ceil_to(size, Min_size);
    if (L4_UNLIKELY(size == 0))
      return false; // Either size was zero, or too large and ceil overflowed.
 
    if (L4_UNLIKELY(!is_power_of_two(align) || align > size))
      return false;
    align = ceil_to(align, Min_size);
    return true;
  }
 
  [[nodiscard]] static bool normalize_bounds(l4_addr_t &lower, l4_addr_t &upper,
                                             size_t size, size_t align)
  {
    // Ceil lower bound to alignment.
    l4_addr_t aligned_lower = ceil_to(lower, align);
    if (L4_UNLIKELY(aligned_lower < lower))
      return false; // Overflow, no aligned address within the bounds.
    lower = aligned_lower;
 
    // Truncate upper bound to alignment.
    if (L4_UNLIKELY(upper < Min_size - 1))
      return false;
    // Note that upper + 1 can wrap to zero, still the result is correct.
    upper = trunc_to(upper + 1, Min_size) - 1;
 
    if (L4_UNLIKELY(lower > upper))
      return false;
 
    return upper - lower >= size - 1;
  }
 
  class Alloc_walk
  {
  public:
    Alloc_walk(Buddy_alloc &a, l4_size_t min_size, l4_size_t max_size,
               l4_size_t align, Mem_range alloc_bounds, Node_ptr base_node)
    : a(a),
      min_size(min_size),
      max_size(max_size),
      align(align),
      alloc_bounds(alloc_bounds),
      base_node(base_node),
      min_anchor_level(min_level_required_for_size(min_size))
    {}
 
    Buddy_alloc &a;
    l4_size_t const min_size;
    l4_size_t const max_size;
    l4_size_t const align;
    Mem_range const alloc_bounds;
    Node_ptr const base_node;
    unsigned min_anchor_level;
    Node_ptr start_node;
    // The following members are only valid if start_node is valid.
    Node_ptr end_node;
    unsigned max_level = 0;
    Mem_range free_range;
 
    [[nodiscard]] bool add_free_node(Node_ptr const &node,
                                     Mem_range const &intersect)
    {
      if (!start_node.valid())
        {
          // Apply alignment constraints.
          auto aligned_start = ceil_to(intersect.start, align);
          if (aligned_start > intersect.end)
            // Aligned start after end of node.
            return false;
 
          start_node = node;
          end_node = Node_ptr();
          free_range.start = aligned_start;
          free_range.end = intersect.end;
          max_level = node.level;
        }
      else
        {
          end_node = node;
          assert(free_range.end + 1 == intersect.start);
          free_range.end = intersect.end;
          max_level = cxx::max(max_level, node.level);
        }
      return true;
    }
 
    void reset_free_range()
    {
      start_node = Node_ptr();
      max_level = 0;
    }

    template<typename CB>
    void search(CB const &eval_alloc);

    inline bool try_alloc();
 
  private:
    static bool may_align(unsigned cur_level, l4_size_t align)
    {
      return block_size_for_level(cur_level) > align;
    }
 
    inline void expand_start();
    inline void expand_back();
  };
 

  inline void *alloc_size_aligned(Node_ptr const &root, unsigned alloc_level);
 
  [[nodiscard]] void *alloc_single_node(Node_ptr node)
  {
    assert(node_is_free(node));
    node_set_used(node);
    update_parents_after_alloc(node);
    return reinterpret_cast<void *>(from_min_size_units(block_start_addr(node)));
  }

  void *alloc_partial(Node_ptr node, l4_size_t partial_size)
  {
    assert(node_is_free(node));
    Node_ptr cur_node = node;
    l4_size_t remaining_size = partial_size;
    for (;;)
      {
        l4_size_t node_size = block_size_for_level(cur_node.level);
        // Covers entire node.
        if (remaining_size == node_size)
          {
            node_set_used(cur_node);
            remaining_size -= node_size;
            update_parents_after_alloc(cur_node);
            break;
          }
        // Covers entire left child of node.
        else if (remaining_size > node_size / 2)
          {
            node_set_used(cur_node.left_child());
            remaining_size -= node_size / 2;
            cur_node = cur_node.right_child();
          }
        // Covers part of left child of node.
        else
          cur_node = cur_node.left_child();
      }
    return reinterpret_cast<void *>(from_min_size_units(block_start_addr(node)));
  }

  [[nodiscard]] void *alloc_node_range(Node_ptr node, l4_size_t size)
  {
    void *result = nullptr;
    l4_addr_t cur_addr = block_start_addr(node);
    l4_size_t remaining_size = size;
    while (remaining_size > 0)
      {
        assert(node_is_free(node));
        assert(cur_addr == block_start_addr(node));
        l4_size_t node_size = block_size_for_level(node.level);
        assert(node_size <= remaining_size);
 
        void *node_ptr = alloc_single_node(node);
        if (result == nullptr)
          result = node_ptr;
 
        cur_addr += node_size;
        remaining_size -= node_size;
        if (remaining_size == 0)
          break;
 
        node = next_node_in_range(cur_addr, remaining_size);
      }
    return result;
  }

  inline void *alloc_from_search_range(Node_ptr start_node, Node_ptr end_node,
                                       Mem_range free_range, l4_size_t size);
 
  [[nodiscard]] bool free_single_node(Node_ptr node)
  {
    // Double-free or free at different level than alloc.
    if (L4_UNLIKELY(!node_is_used(node) || node_is_seperately_allocated(node)))
      return false;
 
    // Mark node as free.
    node_set_free(node);
    update_parents_after_free(node);
    return true;
  }

  void update_parents_after_alloc(Node_ptr node)
  {
    Node_ptr cur = node;
    while (!cur.is_root())
      {
        Node_ptr parent = cur.parent();
        Order_free largest_order_left = node_get(parent.left_child());
        Order_free largest_order_right = node_get(parent.right_child());
        Order_free new_largest_order = cxx::max(largest_order_left,
                                                largest_order_right);
        if (new_largest_order == node_get(parent))
          // Parent largest order unchanged, we can stop.
          break;
        node_set(parent, new_largest_order);
        cur = parent;
      }
  }

  void update_parents_after_free(Node_ptr node)
  {
    Node_ptr cur = node;
    // Update parents in tree.
    while (!cur.is_root())
      {
        Node_ptr parent = cur.parent();
        Order_free largest_order_left = node_get(parent.left_child());
        Order_free largest_order_right = node_get(parent.right_child());
        bool left_free = largest_order_left == cur.level + 1;
        if (largest_order_left == largest_order_right && left_free)
          {
            // Both children are free, so mark the parent as free.
            node_set_free(parent);
          }
        else
          {
            Order_free new_largest_order = cxx::max(largest_order_left,
                                                    largest_order_right);
            if (new_largest_order == node_get(parent))
              // Parent largest order unchanged, we can stop.
              break;
            node_set(parent, new_largest_order);
          }
        cur = parent;
      }
  }

  void mark_subtree_free(Node_ptr node)
  {
    // The nodes of a level are stored consecutively, thus the descendants of a
    // node are stored as contiguous range on every level.
    unsigned long first_index = node.index;
    unsigned long nodes_in_level = 1;
    for (unsigned level = node.level;; --level)
      {
        __builtin_memset(&_tree[first_index], level + 1, nodes_in_level);
        if (level == 0)
          break;
        first_index *= 2;
        nodes_in_level *= 2;
      }
 
    update_parents_after_free(node);
  }
 
  l4_addr_t _base;         // in Min_size units
  l4_size_t _max_mem_size; // in Min_size units
  unsigned _max_level;
  l4_uint8_t *_tree = nullptr;
};
 
template<typename CB>
void
Buddy_alloc::Alloc_walk::search(CB const &eval_alloc)
{
  bool completed = a.tree_walk([this, &eval_alloc](Node_ptr &node)
    {
      if (!a.node_is_free(node))
        {
          // Encountered non-free node, evaluate alloc.
          if (start_node.valid())
            {
              if (eval_alloc())
                return Walk_dir::Stop;
 
              if (end_node.valid())
                {
                  // Skip free nodes discovered during try_alloc().
                  node = end_node;
                  return Walk_dir::Next;
                }
            }
 
          if (!fits_level(a.node_get(node), min_anchor_level))
            return Walk_dir::Next;
 
          return Walk_dir::Descend;
        }
 
      Mem_range node_range = a.block_range(node);
      Mem_range intersect = alloc_bounds.intersect(node_range);
      if (!intersect.valid()
          || intersect.size() < block_size_for_level(min_anchor_level))
        return Walk_dir::Next; // out of bounds
 
      if (!add_free_node(node, intersect))
        return Walk_dir::Next;
 
      if (intersect.end < node_range.end)
        {
          // The end of the node lies outside the alloc range, we reached the end.
          eval_alloc();
          return Walk_dir::Stop;
        }
 
      if (free_range.size() >= max_size)
        {
          if (eval_alloc())
            return Walk_dir::Stop;
 
          if (end_node.valid())
            // Skip free nodes discovered during try_alloc().
            node = end_node;
        }
 
      return Walk_dir::Next;
 
      // OPTIMIZE:
      // Try to not fragment too much, only x-levels below anchor_level.
      // Take remaining size in relation to min_anchor size into consideration.
      // Introduce a fragmentation / wasted memory threshold that decides
      // whether to try size align alloc, or descend further.
    }, base_node);
 
  // In case the walk stopped because it reached the end of the tree, we need to
  // evaluate a pending free range.
  if (completed && start_node.valid())
    eval_alloc();
}
 
bool
Buddy_alloc::Alloc_walk::try_alloc()
{
  assert(start_node.valid());
 
  // OPTIMIZE:
  // How to best position the allocation?
  // Idea could be to try size-aligned allocation for start and end node to avoid unnecessary splitting.
  // Or some limits relative to max_level / min_anchor_level.
  // So in other words, expand start_node and end_node in multiple phases, with different conditions.
  // 1. Only nodes greater/equal min_anchor_level, front and then back if necessary.
  // 2. Only nodes greater/equal min_anchor_level - 1, front and then back if necessary.
  // 3. ...
  // (if the level available at the front is larger than at the back, but
  // the later is sufficient to serve the allocation, prefer it)
 
  // Need to search before (searches for nodes below min_anchor_level).
  expand_start();
  assert(is_aligned_to(free_range.start, align));
  expand_back();
 
  if (free_range.size() < min_size)
    {
      // Failed to alloc...
      reset_free_range();
      return false;
    }
 
  return true;
}
 
void
Buddy_alloc::Alloc_walk::expand_start()
{
  while (free_range.size() < max_size
         && free_range.start == a.block_start_addr(start_node))
    {
      // Searching further back does not make sense, since we know
      // everything we might find will not align.
      if (!may_align(start_node.level, align))
        break;
 
      // OPTIMIZE: Since we only search levels below min_anchor_level, we
      // can do some lower bound calculation to figure out if search even
      // makes sense.
      Node_ptr prev = a.prev_adjacent_free(start_node, base_node);
      if (!prev.valid())
        break;
 
      Mem_range intersect = alloc_bounds.intersect(a.block_range(prev));
      if (!intersect.valid())
        break;
 
      auto aligned_start = ceil_to(intersect.start, align);
      if (aligned_start > intersect.end)
        // Aligned start after end of node.
        break;
 
      if (!end_node.valid())
        end_node = start_node;
 
      start_node = prev;
      max_level = cxx::max(max_level, prev.level);
      free_range.start = aligned_start;
    }
}
 
void
Buddy_alloc::Alloc_walk::expand_back()
{
  while (free_range.size() < max_size
         && (!end_node.valid() || free_range.end == a.block_end_addr(end_node)))
    {
      Node_ptr next = a.next_adjacent_free(
        !end_node.valid() ? start_node : end_node, base_node);
      if (!next.valid())
        break;
 
      Mem_range intersect = alloc_bounds.intersect(a.block_range(next));
      if (!intersect.valid())
        break;
 
      end_node = next;
      max_level = cxx::max(max_level, next.level);
      free_range.end = intersect.end;
    }
}
 
void *
Buddy_alloc::alloc_size_aligned(Node_ptr const &root, unsigned alloc_level)
{
  // Check the largest free order of the root node, mostly to prevent descending
  // to children shadowed by a fully allocated root node, but also as an early
  // exit in case it cannot fulfill the allocation.
  if (!fits_level(node_get(root), alloc_level))
    return nullptr; // out of memory
 
  Node_ptr node = root;
  while (node.level > alloc_level)
    {
      auto left = node.left_child();
      auto right = node.right_child();
      Order_free largest_order_left = node_get(left);
      Order_free largest_order_right = node_get(right);
      if (fits_level(largest_order_left, alloc_level))
        {
          if (largest_order_left > largest_order_right
              && fits_level(largest_order_right, alloc_level))
            node = right;
          else
            node = left;
        }
      else if (largest_order_right > alloc_level)
        node = right;
      else
        break;
    }
 
  if (!fits_level(node_get(node), alloc_level))
    return nullptr; // out of memory
 
  return alloc_single_node(node);
}
 
void *
Buddy_alloc::alloc_from_search_range(Node_ptr start_node, Node_ptr end_node,
                                     Mem_range free_range, l4_size_t size)
{
  if (free_range.start == block_start_addr(start_node) && !end_node.valid())
    // Allocate from a single node.
    return alloc_partial(start_node, size);
 
 
  // Find actual start node, taking intersect into account.
  while (free_range.start != block_start_addr(start_node))
    {
      start_node = block_start_addr(start_node.right_child()) > free_range.start
                     ? start_node.left_child()
                     : start_node.right_child();
    }
 
  // Allocate multiple nodes, which are descendants of the single original
  // start_node.
  if (!end_node.valid())
    {
      // Find actual start node, in case the start node is still larger than the
      // requested size.
      while (block_size_for_level(start_node.level) > size)
        start_node = start_node.left_child();
 
      return alloc_node_range(start_node, size);
    }
 
  // Find actual end node, taking intersect into account.
  while (free_range.end != block_end_addr(end_node))
    end_node = block_end_addr(end_node.left_child()) >= free_range.end
                 ? end_node.left_child()
                 : end_node.right_child();
 
  assert(free_range.start == block_start_addr(start_node));
  // min() in case we decided to only allocate a sub-range of the detected
  // range, for example because of granularity constraints.
  l4_size_t front_size =
    cxx::min<l4_size_t>(block_start_addr(end_node) - free_range.start, size);
  void *mem = alloc_node_range(start_node, front_size);
 
  // The above alloc_free_range() could take the entire range, including the
  // tail, but alloc_partial is more efficient due to less
  // update_parents_after_alloc() calls.
  if (front_size != size)
    alloc_partial(end_node, size - front_size);
  return mem;
}
 
void
Buddy_alloc::add_mem(void *mem, size_t size)
{
  assert(initialized());
 
  l4_addr_t start = reinterpret_cast<l4_addr_t>(mem);
  l4_addr_t aligned_start = ceil_to(start, Min_size);
  // Block at address zero must never be handed out by alloc(), because nullptr
  // represents a failed allocation.
  if (aligned_start == 0)
    aligned_start = Min_size;
 
  size_t skipped_size = aligned_start - start;
  if (size <= skipped_size)
    return;
  size = trunc_to(size - skipped_size, Min_size);
 
  aligned_start = to_min_size_units(aligned_start);
  size = to_min_size_units(size);
 
  while (size > 0)
    {
      // Add the largest size-aligned block that fits the remaining size and
      // mark its entire subtree as free. The naive way of adding Min_size
      // blocks bottom up, is slow due to the frequent parent updates.
      Node_ptr node = next_node_in_range(aligned_start, size);
      size_t block_size = block_size_for_level(node.level);
 
      if (L4_UNLIKELY(!node_is_used(node)))
        {
          // The node is free or split, i.e. at least parts of the memory were
          // already added before.
          if constexpr (Print_warnings)
            printf("Detected addition of already available memory at %#lx (size=%#zx).\n",
                   from_min_size_units(aligned_start), from_min_size_units(block_size));
          return;
        }
      mark_subtree_free(node);
 
      aligned_start += block_size;
      size -= block_size;
    }
}
 
void *
Buddy_alloc::alloc(size_t size, size_t align, l4_addr_t lower, l4_addr_t upper)
{
  if (L4_UNLIKELY(!initialized()))
    return nullptr;
 
  if (L4_UNLIKELY(!normalize_size_align(size, align)))
    return nullptr;
 
  if (L4_UNLIKELY(!normalize_bounds(lower, upper, size, align)))
    return nullptr;
 
  // Convert arguments to Min_size units.
  size = to_min_size_units(size);
  align = to_min_size_units(align);
  lower = to_min_size_units(lower);
  upper = upper / Min_size; // inclusive, thus not aligned, truncation is fine.
 
  unsigned size_aligned_level = level_for_block_size(ceil_power_of_two(size));
  Mem_range alloc_range(lower, upper);
  Node_ptr base_node = find_bounded_root(size_aligned_level, alloc_range);
 
  // In case the alloc range contains the base node, so either larger then the
  // root node or exactly aligning with a subnode, we can use the unbounded
  // allocation algorithm on the subtree spanned by the base node.
  if (alloc_range.contains(block_range(base_node)) && is_power_of_two(size))
    {
      if (void *block = alloc_size_aligned(base_node, size_aligned_level);
          L4_LIKELY(block != nullptr))
        return block;
 
      if (size == align)
        return nullptr;
 
      // Search for non-size-aligned allocation opportunity...
    }
 
  Alloc_walk walk(*this, size, size, align, alloc_range, base_node);
  // OPTIMIZE ideas:
  //   - Special case for small sizes, where min_anchor_block_size==size.
  //   - For smaller sizes just try to find a perfect aligned fit. And only if
  //     that fails try harder.
  //   - For larger sizes above e.g. 64 MB try harder, with Alloc_walk.
  //   - If the block we split is much larger than our target size, maybe
  //     continue searching?
  walk.search([&]() { return walk.try_alloc(); });
  if (!walk.start_node.valid())
    return nullptr;
 
  return alloc_from_search_range(walk.start_node, walk.end_node,
                                 walk.free_range, walk.min_size);
}
 
void *
Buddy_alloc::alloc_max(size_t min, size_t *max, size_t align,
                       size_t granularity, l4_addr_t lower, l4_addr_t upper)
{
  if (L4_UNLIKELY(!initialized()))
    return nullptr;
 
  if (L4_UNLIKELY(!is_power_of_two(granularity) || granularity > align))
    return nullptr;
  granularity = ceil_to(granularity, Min_size);
 
  if (L4_UNLIKELY(!normalize_size_align(min, align)))
    return nullptr;
 
  // The allocation size is truncated to a multiple of the granularity in the
  // end. Thus also the minimum size must be a multiple of the granularity.
  // Otherwise the truncation could yield a size below minimum size.
  min = ceil_to(min, granularity);
  if (L4_UNLIKELY(min == 0))
    return nullptr; // Too large, overflow.
 
  l4_size_t max_ = trunc_to(*max, granularity);
  if (L4_UNLIKELY(min > max_))
    return nullptr;
 
  if (L4_UNLIKELY(!normalize_bounds(lower, upper, min, align)))
    return nullptr;
 
  // Convert arguments to Min_size units.
  min = to_min_size_units(min);
  max_ = to_min_size_units(max_);
  align = to_min_size_units(align);
  granularity = to_min_size_units(granularity);
  lower = to_min_size_units(lower);
  upper = upper / Min_size; // inclusive, thus not aligned, truncation is fine.
 
  unsigned size_aligned_max_level = level_for_block_size(trunc_power_of_two(max_));
  Mem_range alloc_range(lower, upper);
  Node_ptr base_node = find_bounded_root(size_aligned_max_level, alloc_range);
  if (alloc_range.contains(block_range(base_node)) && is_power_of_two(max_))
    {
      if (void *block = alloc_size_aligned(base_node, size_aligned_max_level);
          L4_LIKELY(block != nullptr))
        {
          *max = from_min_size_units(max_);
          return block;
        }
 
      // Search for smaller or non-size-aligned allocation opportunity...
    }
 
  // Tree walk that only considers nodes within [lower, upper] to search for
  // suitable free node.
 
  Node_ptr best_start_node;
  Node_ptr best_end_node;
  Mem_range best_free_range;
 
  Alloc_walk walk(*this, min, max_, align, alloc_range, base_node);
  walk.search([&]()
    {
      if (!walk.try_alloc())
        return false;
 
      // OPTIMIZE: Take into account other parameters, such as wasted memory /
      // splitting of larger blocks.
      if (!best_start_node.valid()
          || walk.free_range.size() > best_free_range.size())
        {
          best_start_node = walk.start_node;
          best_end_node = walk.end_node;
          best_free_range = walk.free_range;
 
          if (best_free_range.size() >= max_)
            return true; // found area that can provide max
 
          // Raise the min_anchor_level dynamically.
          walk.min_anchor_level = min_level_required_for_size(
            best_free_range.size());
        }
 
      // Continue the scan until we find a range >= max_ or reach the end.
      walk.reset_free_range();
      return false;
    });
 
  if (!best_start_node.valid())
    return nullptr;
 
  max_ = cxx::min(walk.max_size, best_free_range.size());
  max_ = trunc_to(max_, granularity);
  *max = from_min_size_units(max_);
  return alloc_from_search_range(best_start_node, best_end_node,
                                 best_free_range, max_);
}
 
void
Buddy_alloc::free(void *block, size_t size)
{
  if (L4_UNLIKELY(!initialized()))
    return;
 
  size = ceil_to(size, Min_size);
  if (L4_UNLIKELY(size == 0))
    return; // Either zero size or too large and ceil overflowed.
 
  if (L4_UNLIKELY(block == nullptr))
    {
      // alloc() never hands out a block address of zero.
      if constexpr (Print_warnings)
        printf("Invalid free of nullptr (size=%#zx).\n", size);
      return;
    }
 
  l4_addr_t block_addr = reinterpret_cast<l4_addr_t>(block);
  if (L4_UNLIKELY(!is_aligned_to(block_addr, Min_size)))
    {
      if constexpr (Print_warnings)
        printf("Invalid free of misaligned address %#lx (size=%#zx).\n",
               block_addr, size);
      return;
    }
 
  // Convert arguments to Min_size units.
  size = to_min_size_units(size);
  block_addr = to_min_size_units(block_addr);
 
  // Reject blocks outside of the memory area managed by the.
  if (L4_UNLIKELY(block_addr < _base || size > _max_mem_size
                  || block_addr - _base > _max_mem_size - size))
    {
      if constexpr (Print_warnings)
        printf("Invalid free of %#lx (size=%#zx) outside of the managed area.\n",
               from_min_size_units(block_addr), from_min_size_units(size));
      return;
    }
 
  // Single size-aligned block.
  if (is_power_of_two(size) && is_aligned_to(block_addr, size))
    {
      Node_ptr node = node_for_block(block_addr, size);
      if (!free_single_node(node))
        if constexpr (Print_warnings)
          printf("Double free of %#lx (size=%#zx) or free with different size.\n",
                 from_min_size_units(block_addr), from_min_size_units(size));
      return;
    }
 
  // From the alignment of the start address we figure out an upper bound level,
  // from which we search left until we find a used block at the given address.
  unsigned base_level = cxx::min(trailing_zeroes(block_addr), _max_level);
  // Since used nodes never can be shadowed (only free nodes can), it is safe to
  // start at an arbitrary level of the tree. If we encounter a used node, we
  // can be sure that it is actually used.
  Node_ptr node = node_for_block_level(block_addr, base_level);
 
  // Descend from "upper bound level" to node at the same address marked as used.
  while (!node_is_used(node) || node_is_seperately_allocated(node))
    {
      if (L4_UNLIKELY(node.is_leaf()))
        {
          if constexpr (Print_warnings)
            printf("Double free of %#lx (size=%#zx).\n",
                   from_min_size_units(block_addr), from_min_size_units(size));
          return;
        }
 
      node = node.left_child();
    }
 
  // Now we have the first block of the allocation, now we iterate until we
  // reached end of allocation.
  l4_addr_t cur_addr = block_addr;
  size_t remaining_size = size;
  for (;;)
    {
      l4_size_t block_size = block_size_for_level(node.level);
      if (L4_UNLIKELY(block_size > remaining_size))
        {
          if constexpr (Print_warnings)
            printf("Free of %#lx with wrong size (block_size=%#zx vs. remaining_size=%#zx).\n",
                   from_min_size_units(block_addr),
                   from_min_size_units(block_size),
                   from_min_size_units(remaining_size));
          return;
        }
 
      // OPTIMIZE: Batch the parent update_parents_after_free() calls?
      if (!free_single_node(node))
        if constexpr (Print_warnings)
          printf("Double free of %#lx (size=%#zx) or free with different size.\n",
                 from_min_size_units(block_addr), from_min_size_units(size));
 
      cur_addr += block_size;
      remaining_size -= block_size;
      if (remaining_size == 0)
        break; // we are done :)
 
      node = next_node_in_range(cur_addr, remaining_size);
    }
}

size_t
Buddy_alloc::avail() const
{
  if (L4_UNLIKELY(!initialized()))
    return 0;
 
  size_t avail = 0;
  tree_walk_free([&avail](Node_ptr const &node)
    { avail += block_size_for_level(node.level); });
  return from_min_size_units(avail);
}
 
template<typename DBG>
void
Buddy_alloc::dump_free(DBG &out) const
{
  if (L4_UNLIKELY(!initialized()))
    {
      out.printf("Buddy_alloc [UNITIALIZED]\n");
      return;
    }
 
  l4_uint64_t total = 0;
  out.printf("Buddy_alloc [%zu,%u]\n", Min_size, _max_level);
 
  // Stack-allocate entries to cover the maximum possible number of levels.
  size_t levels_avail[(sizeof(l4_addr_t) * 8) - Min_order + 1] = {};
  assert(_max_level < cxx::array_size(levels_avail));
  tree_walk_free([&levels_avail](Node_ptr const &node)
    { levels_avail[node.level] += 1; });
 
  auto format_size = [](l4_uint64_t *size, unsigned threshold) -> char const *
    {
      static_assert(Min_size >= 1024); // 2^64 == 16 EiB
      static constexpr char const *const unitstr[7] =
        { "Byte", "KiB", "MiB", "GiB", "TiB", "PiB", "EiB" };
 
      unsigned i;
      for (i = 0; i + 1 < cxx::array_size(unitstr) && *size > (threshold << 10); ++i)
        *size >>= 10;
      return unitstr[i];
    };
 
  for (unsigned level = 0; level <= _max_level; level++)
    {
      l4_uint64_t level_size = block_size_for_level(level) * l4_uint64_t{Min_size};
      l4_uint64_t size = level_size;
      char const *unit = format_size(&size, 2);
      out.printf("  %2u: [%4llu %s]", level, size, unit);
 
      l4_uint64_t avail = levels_avail[level] * level_size;
      size_t avail_blocks = levels_avail[level];
      size = avail;
      unit = format_size(&size, 8);
      out.cprintf(" %zu free blocks == %4llu %-4s (%llu bytes)\n",
                  avail_blocks, size, unit, avail);
 
      total += avail;
    }
 
  l4_uint64_t size = total;
  char const *unit = format_size(&size, 8);
  out.printf("sum of available memory: %llu %s (%llu bytes)\n",
             size, unit, total);
}
 
} // namespace cxx