list_alloc

// vim:set ft=cpp: -*- Mode: C++ -*-
/*
 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
 *               Torsten Frenzel <frenzel@os.inf.tu-dresden.de>
 *     economic rights: Technische Universität Dresden (Germany)
 *
 * 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/consts.h>
 
#ifdef CXX_LIST_ALLOC_SANITY
#include <l4/cxx/iostream>
#endif
 
namespace cxx {

class List_alloc
{
private:
  friend class List_alloc_sanity_guard;
 
  struct Mem_block
  {
    Mem_block *next;
    unsigned long size;
  };
 
  Mem_block *_first;
 
  inline void check_overlap(void *, unsigned long) const;
  inline void sanity_check_list(char const *, char const *,
                                bool unmerged) const;
  inline void merge(Mem_block *, Mem_block *);
 
public:

  List_alloc() : _first(0) {}

  inline void free(void *block, unsigned long size, bool initial_free = false);

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

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

  inline unsigned long avail() const;
 
  template <typename DBG>
  void dump_free_list(DBG &out) const;
};
 
#if !defined (CXX_LIST_ALLOC_SANITY)
class List_alloc_sanity_guard
{
public:
  List_alloc_sanity_guard(List_alloc const *, char const *, bool)
  {}
 
};
 
 
void
List_alloc::check_overlap(void *, unsigned long) const
{}
 
void
List_alloc::sanity_check_list(char const *, char const *, bool) const
{}
 
#else
 
class List_alloc_sanity_guard
{
private:
  List_alloc const *a;
  char const *func;
 
public:
  List_alloc_sanity_guard(List_alloc const *a, char const *func, bool unmerged)
  : a(a), func(func)
  { a->sanity_check_list(func, "entry", unmerged); }
 
  ~List_alloc_sanity_guard()
  { a->sanity_check_list(func, "exit", false); }
};
 
void
List_alloc::check_overlap(void *b, unsigned long s) const
{
  unsigned long const mb_align = (1UL << arith::Ld<sizeof(Mem_block)>::value) - 1;
  if ((unsigned long)b & mb_align)
    {
      L4::cerr << "List_alloc(FATAL): trying to free unaligned memory: "
               << b << " align=" << arith::Ld<sizeof(Mem_block)>::value << "\n";
    }
 
  Mem_block const *c = _first;
  for (;c ; c = c->next)
    {
      unsigned long x_s = (unsigned long)b;
      unsigned long x_e = x_s + s;
      unsigned long b_s = (unsigned long)c;
      unsigned long b_e = b_s + c->size;
 
      if ((x_s >= b_s && x_s < b_e)
          || (x_e > b_s && x_e <= b_e)
          || (b_s >= x_s && b_s < x_e)
          || (b_e > x_s && b_e <= x_e))
      {
        L4::cerr << "List_alloc(FATAL): trying to free memory that "
                    "is already free: \n  ["
                 << (void*)x_s << '-' << (void*)x_e << ") overlaps ["
                 << (void*)b_s << '-' << (void*)b_e << ")\n";
      }
    }
}
 
void
List_alloc::sanity_check_list(char const *func, char const *info,
                              bool unmerged) const
{
  Mem_block const *c = _first;
  for (;c ; c = c->next)
    {
      if (c->next)
        {
          if (c >= c->next)
            {
              L4::cerr << "List_alloc(FATAL): " << func << '(' << info
                       << "): list order violation\n";
            }
 
          unsigned long c_end = reinterpret_cast<unsigned long>(c) + c->size;
          unsigned long n_start = reinterpret_cast<unsigned long>(c->next);
          if (c_end > n_start || (c_end == n_start && !unmerged))
            {
              L4::cerr << "List_alloc(FATAL): " << func << '(' << info
                       << "): list order violation\n";
            }
        }
    }
}
 
#endif

void
List_alloc::merge(Mem_block *prev, Mem_block *c)
{
  // We allow the list to not be merged in the beginning.
  List_alloc_sanity_guard __attribute__((unused)) guard(this, __func__, true);
  int iters = 1;
  if (prev)
    {
      c = prev;
      // If we have a predecessor, we might need to merge twice.
      iters = 2;
    }
 
  while (c && c->next && iters--)
    {
      unsigned long f_start = reinterpret_cast<unsigned long>(c);
      unsigned long f_end   = f_start + c->size;
      unsigned long n_start = reinterpret_cast<unsigned long>(c->next);
 
      if (f_end == n_start)
        {
          c->size += c->next->size;
          c->next = c->next->next;
          continue;
        }
 
      c = c->next;
    }
}
 
void
List_alloc::free(void *block, unsigned long size, bool initial_free)
{
  List_alloc_sanity_guard __attribute__((unused)) guard(this, __func__, false);
 
  unsigned long const mb_align = (1UL << arith::Ld<sizeof(Mem_block)>::value) - 1;
 
  if (initial_free)
    {
      // enforce alignment constraint on initial memory
      unsigned long nblock = (reinterpret_cast<unsigned long>(block) + mb_align)
                             & ~mb_align;
      size = (size - (nblock - reinterpret_cast<unsigned long>(block)))
             & ~mb_align;
      block = reinterpret_cast<void*>(nblock);
    }
  else
    // blow up size to the minimum aligned size
    size = (size + mb_align) & ~mb_align;
 
  check_overlap(block, size);
 
  Mem_block *prev = 0;
  Mem_block **c = &_first;
  Mem_block *next = 0;
 
  if (*c)
    {
      while (*c && *c < block)
        {
          prev = *c;
          c = &prev->next;
        }
 
      next = *c;
    }
 
  *c = reinterpret_cast<Mem_block*>(block);
 
  (*c)->next = next;
  (*c)->size = size;
 
  merge(prev, *c);
}
 
void *
List_alloc::alloc_max(unsigned long min, unsigned long *max, unsigned long align,
                      unsigned granularity, unsigned long lower,
                      unsigned long upper)
{
  List_alloc_sanity_guard __attribute__((unused)) guard(this, __func__, false);
 
  unsigned char const mb_bits = arith::Ld<sizeof(Mem_block)>::value;
  unsigned long const mb_align = (1UL << mb_bits) - 1;
 
  // blow minimum up to at least the minimum aligned size of a Mem_block
  min = l4_round_size(min, mb_bits);
  // truncate maximum to at least the size of a Mem_block
  *max = l4_trunc_size(*max, mb_bits);
  // truncate maximum size according to granularity
  *max = *max & ~(granularity - 1UL);
 
  if (min > *max)
    return 0;
 
  unsigned long almask = align ? (align - 1UL) : 0;
 
  // minimum alignment is given by the size of a Mem_block
  if (almask < mb_align)
    almask = mb_align;
 
  Mem_block **c = &_first;
  Mem_block **fit = 0;
  unsigned long max_fit = 0;
  unsigned long a_lower = (lower + almask) & ~almask;
 
  for (; *c; c = &(*c)->next)
    {
      // address of free memory block
      unsigned long n_start = reinterpret_cast<unsigned long>(*c);
 
      // block too small, next
      // XXX: maybe we can skip this and just do the test below
      if ((*c)->size < min)
        continue;
 
      // block outside region, next
      if (upper < n_start || a_lower > n_start + (*c)->size)
        continue;
 
      // aligned start address within the free block
      unsigned long a_start = (n_start + almask) & ~almask;
 
      // check if aligned start address is behind the block, next
      if (a_start - n_start >= (*c)->size)
        continue;
 
      a_start = a_start < a_lower ? a_lower : a_start;
 
      // end address would overflow, next
      if (min > ~0UL - a_start)
        continue;
 
      // block outside region, next
      if (a_start + min - 1UL > upper)
        continue;
 
      // remaining size after subtracting the padding for the alignment
      unsigned long r_size = (*c)->size - a_start + n_start;
 
      // upper limit can limit maximum size
      if (a_start + r_size - 1UL > upper)
        r_size = upper - a_start + 1UL;
 
      // round down according to granularity
      r_size &= ~(granularity - 1UL);
 
      // block too small
      if (r_size < min)
        continue;
 
      if (r_size >= *max)
        {
          fit = c;
          max_fit = *max;
          break;
        }
 
      if (r_size > max_fit)
        {
          max_fit = r_size;
          fit = c;
        }
    }
 
  if (fit)
    {
      unsigned long n_start = reinterpret_cast<unsigned long>(*fit);
      unsigned long a_lower = (lower + almask) & ~almask;
      unsigned long a_start = (n_start + almask) & ~almask;
      a_start = a_start < a_lower ? a_lower : a_start;
      unsigned long r_size = (*fit)->size - a_start + n_start;
 
      if (a_start > n_start)
        {
          (*fit)->size -= r_size;
          fit = &(*fit)->next;
        }
      else
        *fit = (*fit)->next;
 
      *max = max_fit;
      if (r_size == max_fit)
        return reinterpret_cast<void *>(a_start);
 
      Mem_block *m = reinterpret_cast<Mem_block*>(a_start + max_fit);
      m->next = *fit;
      m->size = r_size - max_fit;
      *fit = m;
      return reinterpret_cast<void *>(a_start);
    }
 
  return 0;
}
 
void *
List_alloc::alloc(unsigned long size, unsigned long align, unsigned long lower,
                  unsigned long upper)
{
  List_alloc_sanity_guard __attribute__((unused)) guard(this, __func__, false);
 
  unsigned long const mb_align
    = (1UL << arith::Ld<sizeof(Mem_block)>::value) - 1;
 
  // blow up size to the minimum aligned size
  size = (size + mb_align) & ~mb_align;
 
  unsigned long almask = align ? (align - 1UL) : 0;
 
  // minimum alignment is given by the size of a Mem_block
  if (almask < mb_align)
    almask = mb_align;
 
  Mem_block **c = &_first;
  unsigned long a_lower = (lower + almask) & ~almask;
 
  for (; *c; c=&(*c)->next)
    {
      // address of free memory block
      unsigned long n_start = reinterpret_cast<unsigned long>(*c);
 
      // block too small, next
      // XXX: maybe we can skip this and just do the test below
      if ((*c)->size < size)
        continue;
 
      // block outside region, next
      if (upper < n_start || a_lower > n_start + (*c)->size)
        continue;
 
      // aligned start address within the free block
      unsigned long a_start = (n_start + almask) & ~almask;
 
      // block too small after alignment, next
      if (a_start - n_start >= (*c)->size)
        continue;
 
      a_start = a_start < a_lower ? a_lower : a_start;
 
      // end address would overflow, next
      if (size > ~0UL - a_start)
        continue;
 
      // block outside region, next
      if (a_start + size - 1UL > upper)
        continue;
 
      // remaining size after subtracting the padding
      // for the alignment
      unsigned long r_size = (*c)->size - a_start + n_start;
 
      // block too small
      if (r_size < size)
        continue;
 
      if (a_start > n_start)
        {
          // have free space before the allocated block
          // shrink the block and set c to the next pointer of that
          // block
          (*c)->size -= r_size;
          c = &(*c)->next;
        }
      else
        // drop the block, c remains the next pointer of the
        // previous block
        *c = (*c)->next;
 
      // allocated the whole remaining space
      if (r_size == size)
        return reinterpret_cast<void*>(a_start);
 
      // add a new free block behind the allocated block
      Mem_block *m = reinterpret_cast<Mem_block*>(a_start + size);
      m->next = *c;
      m->size = r_size - size;
      *c = m;
      return reinterpret_cast<void *>(a_start);
    }
 
  return 0;
}
 
unsigned long
List_alloc::avail() const
{
  List_alloc_sanity_guard
    __attribute__((unused)) guard(this, __FUNCTION__, false);
  Mem_block const *c = _first;
  unsigned long a = 0;
  while (c)
    {
      a += c->size;
      c = c->next;
    }
 
  return a;
}
 
template <typename DBG>
void
List_alloc::dump_free_list(DBG &out) const
{
  Mem_block const *c = _first;
  while (c)
    {
      static constexpr char const *const unitstr[4] =
      { "Byte", "KiB", "MiB", "GiB" };
 
      unsigned sz = c->size;
      unsigned i;
      for (i = 0; i < cxx::array_size(unitstr) && sz > 8 << 10; ++i)
        sz >>= 10;
 
      out.printf("%12p - %12p (%u %s)\n",
                 c, reinterpret_cast<char const *>(c) + c->size - 1, sz, unitstr[i]);
 
      c = c->next;
    }
}
 
}