/*

 * Memory area functionality.

 *

 * Copyright (C) 2022, 2023 Paul Boddie <paul@boddie.org.uk>

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License as

 * published by the Free Software Foundation; either version 2 of

 * the License, or (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor,

 * Boston, MA  02110-1301, USA

 */

#include <l4/re/c/rm.h>

#include <mem/memory_utils.h>

#include "mapped_region.h"

/* Copy an area. */

MemoryArea *MemoryArea::copy()

{

  return new MemoryArea(_start, _end);

}

/* In general, a region cannot support other regions. */

long MemoryArea::add(MemoryArea &area)

{

  (void) area;

  return -L4_EPERM;

}

long MemoryArea::remove(MemoryArea &area)

{

  (void) area;

  return -L4_EPERM;

}

/* In general, a region supports a memory access within its bounds. */

long MemoryArea::find(address_t addr, MemoryArea **area, MemoryArea **parent)

{

  /* The parent is merely propagated through this method, but is present for

     conformance to the generic method signature. */

  (void) parent;

  if ((addr >= _start) && (addr < _end))

  {

    *area = this;

    return L4_EOK;

  }

  else

    return -L4_ENOMEM;

}

/* In general, a region does not support the identification of a location for

   region insertion. */

long MemoryArea::find(address_t *start, address_t *size, map_flags_t flags,

                      unsigned char align, MemoryArea **area)

{

  (void) start; (void) size; (void) flags; (void) align; (void) area;

  return -L4_ENOMEM;

}

/* Copy a reserved area. */

MemoryArea *ReservedMemoryArea::copy()

{

  return new ReservedMemoryArea(_start, _end);

}

/* A reserved area does not support any memory access. */

long ReservedMemoryArea::find(address_t addr, MemoryArea **area,

                              MemoryArea **parent)

{

  (void) addr; (void) area; (void) parent;

  return -L4_ENOMEM;

}

/* Discard all allocated areas. */

AvailableMemoryArea::~AvailableMemoryArea()

{

  MemoryAreas::iterator it;

  for (it = _allocated.begin(); it != _allocated.end(); it++)

    delete *it;

  _allocated.clear();

}

/* Copy an unused available memory area. */

MemoryArea *AvailableMemoryArea::copy()

{

  return new AvailableMemoryArea(_start, _end);

}

/* Add an area. */

long AvailableMemoryArea::add(MemoryArea &area)

{

  MemoryArea *a = area.copy();

  _areas[area.area_start()] = a;

  _allocated.insert(a);

  return L4_EOK;

}

/* Remove an area. */

long AvailableMemoryArea::remove(MemoryArea &area)

{

  MemoryAreaMap::iterator it = _areas.find(area.area_start());

  if (it != _areas.end())

  {

    _areas.erase(it);

    MemoryAreas::iterator ita = _allocated.find(it->second);

    if (ita != _allocated.end())

    {

      delete *ita;

      _allocated.erase(ita);

    }

  }

  return L4_EOK;

}

/* Find an region able to support a memory access. */

long AvailableMemoryArea::find(address_t addr, MemoryArea **area,

                               MemoryArea **parent)

{

  MemoryAreaMap::iterator it = _areas.upper_bound(addr);

  /* Consider any area preceding or encompassing the desired address. */

  if (it != _areas.begin())

  {

    it--;

    /* Test whether the desired region start is encompassed by the preceding

       area. */

    MemoryArea *r = it->second;

    *parent = this;

    if (r->supports(addr))

      return r->find(addr, area, parent);

  }

  /* Otherwise, no area within this area supports the address. */

  return -L4_ENOMEM;

}

/* Find an area suitable for attaching a memory region. */

long AvailableMemoryArea::find(address_t *start, address_t *size,

                               map_flags_t flags, unsigned char align,

                               MemoryArea **area)

{

  /* Obtain the alignment increment and a properly aligned size. */

  address_t increment = 1UL << align;

  address_t region_size = round(*size, increment);

  /* Align any desired location. */

  address_t region_start = trunc(*start, increment);

  /* Enforce a minimum address. */

  if (region_start < _start)

    region_start = round(_start, increment);

  /* Search for existing regions after the desired, conformant start address. */

  MemoryAreaMap::iterator it = _areas.upper_bound(region_start);

  /* Consider any area preceding or encompassing the desired address. */

  if (it != _areas.begin())

  {

    MemoryAreaMap::iterator next = it;

    /* Step back to the preceding area to get its details. */

    it--;

    MemoryArea *pr = it->second;

    it = next;

    /* Test whether the desired region start is encompassed by the preceding

       area. */

    if (region_start < pr->area_end())

    {

      /* Where the preceding area is mapped or a reserved area, adjust the start

         of any search range. If an exact request is made for a region, deny the

         request. */

      if (pr->is_mapped() || pr->is_reserved())

      {

        if (!(flags & L4RE_RM_F_SEARCH_ADDR))

          return -L4_ENOMEM;

        region_start = round(pr->area_end(), increment);

      }

      /* Where the preceding area is an area within which regions might be

         established, search within that area. */

      else

        return pr->find(start, size, flags, align, area);

    }

  }

  /* Consider the regions following the current region start candidate. */

  MemoryArea *r;

  while ((it != _areas.end()) && !(_end && ((region_start + region_size) > _end)))

  {

    r = it->second;

    /* Obtain the limit of available space being considered. */

    address_t end_limit = r->area_start();

    /* Test if not enough space exists between the preceding region (or start of

       memory) and the current region. */

    if ((region_start + region_size) > end_limit)

    {

      /* If an exact request is made for a region, deny the request. */

      if (!(flags & L4RE_RM_F_SEARCH_ADDR))

        return -L4_ENOMEM;

      /* Otherwise, investigate subsequent regions if not enough space exists

         between the preceding region (or start of memory) and the current

         region. */

      region_start = round(r->area_end(), increment);

      it++;

    }

    /* Otherwise, the region can be positioned. */

    else

      break;

  }

  /* Test for enough memory constrained by any predefined limit. */

  if (_end && ((region_start + region_size) > _end))

    return -L4_ENOMEM;

  /* Return the configured start and size. */

  *start = region_start;

  *size = region_size;

  /* Return the area within which any region will be added. */

  *area = this;

  return L4_EOK;

}

/* Obtain a recursive iterator over a memory area. */

AvailableMemoryArea::iterator AvailableMemoryArea::begin()

{

  return AvailableMemoryArea::iterator(_areas.begin(), _areas.end());

}

AvailableMemoryArea::iterator AvailableMemoryArea::end()

{

  return AvailableMemoryArea::iterator(_areas.end(), _areas.end());

}

MemoryAreaMap::iterator AvailableMemoryArea::areas_begin()

{

  return _areas.begin();

}

MemoryAreaMap::iterator AvailableMemoryArea::areas_end()

{

  return _areas.end();

}

/* Initialise a recursive iterator over a memory area. */

AvailableMemoryArea::iterator::iterator(MemoryAreaMap::iterator it,

                                        MemoryAreaMap::iterator end)

{

  _iterators.push(it);

  _ends.push(end);

  /* Descend to the first non-container area. */

  descend_all();

}

AvailableMemoryArea::iterator::iterator()

{

}

/* Return the current underlying iterator. */

MemoryAreaMap::iterator &AvailableMemoryArea::iterator::area_iterator()

{

  return _iterators.top();

}

/* Return the end point of the current underlying iterator. */

MemoryAreaMap::iterator &AvailableMemoryArea::iterator::area_end()

{

  return _ends.top();

}

/* Return the current area. */

MemoryArea *AvailableMemoryArea::iterator::operator *()

{

  return area_iterator()->second;

}

/* Return whether this iterator references the same area as the other

   iterator. */

bool AvailableMemoryArea::iterator::operator ==(AvailableMemoryArea::iterator other)

{

  return area_iterator() == other.area_iterator();

}

/* Return whether this iterator references a different area to the other

   iterator. */

bool AvailableMemoryArea::iterator::operator !=(AvailableMemoryArea::iterator other)

{

  return area_iterator() != other.area_iterator();

}

/* Advance this iterator to the next area. */

AvailableMemoryArea::iterator &AvailableMemoryArea::iterator::operator ++()

{

  /* Advance the area iterator. */

  area_iterator()++;

  /* Descend to the next non-container area. */

  descend_all();

  return *this;

}

AvailableMemoryArea::iterator &AvailableMemoryArea::iterator::operator ++(int)

{

  return ++(*this);

}

/* Advance this iterator to the next area not containing other areas. */

void AvailableMemoryArea::iterator::descend_all()

{

  while ((area_iterator() != area_end()) || (_iterators.size() > 1))

  {

    /* Handle empty areas by ascending to refer to the area. */

    if (area_iterator() == area_end())

    {

      ascend();

      break;

    }

    MemoryArea *r = area_iterator()->second;

    /* Handle areas by descending into them. */

    if (!r->is_reserved() && !r->is_mapped())

      descend();

    /* Yield any non-container areas. */

    else

      break;

  }

}

/* Ascend from a memory area. */

void AvailableMemoryArea::iterator::ascend()

{

  _iterators.pop();

  _ends.pop();

}

/* Descend into a memory area. */

void AvailableMemoryArea::iterator::descend()

{

  AvailableMemoryArea *a = dynamic_cast<AvailableMemoryArea *>(area_iterator()->second);

  if (a != NULL)

  {

    _iterators.push(a->areas_begin());

    _ends.push(a->areas_end());

  }

}

/* vim: tabstop=2 expandtab shiftwidth=2

*/