/*

 * A page collection for handling map requests.

 *

 * Copyright (C) 2019, 2020 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

 */

#pragma once

#include <l4/sys/semaphore.h>

#include <l4/sys/types.h>

#include <list>

#include <map>

#include <fsserver/accessor.h>

#include <fsserver/flexpage.h>

/* Queue of allocated flexpages with the accessors using them. */

typedef std::pair<PagingAccessor *, Flexpage *> Flexpage_queue_item;

typedef std::list<Flexpage_queue_item> Flexpage_queue;

/* Mapping of flexpages to their queue positions. */

typedef std::pair<Flexpage *, Flexpage_queue::iterator> Flexpage_position_item;

typedef std::map<Flexpage *, Flexpage_queue::iterator> Flexpage_positions;

/* A wrapper around a list and map to provide a coherent, searchable queue. */

class PageQueue

{

protected:

  Flexpage_queue _queue;

  Flexpage_positions _positions;

  /* Semaphores to ensure available flexpages and to guard the queue when adding

     or removing items. */

  l4_cap_idx_t _counter_semaphore;

  l4_cap_idx_t _queue_semaphore;

  void lock_queue()

  {

    l4_semaphore_down(_queue_semaphore, L4_IPC_NEVER);

  }

  void unlock_queue()

  {

    l4_semaphore_up(_queue_semaphore);

  }

  void decrement()

  {

    l4_semaphore_down(_counter_semaphore, L4_IPC_NEVER);

  }

  void increment()

  {

    l4_semaphore_up(_counter_semaphore);

  }

public:

  explicit PageQueue();

  virtual ~PageQueue();

  PagingAccessor *find(Flexpage *flexpage)

  {

    lock_queue();

    Flexpage_positions::iterator item = _positions.find(flexpage);

    if (item == _positions.end())

    {

      unlock_queue();

      return NULL;

    }

    unlock_queue();

    return item->second->first;

  }

  bool pop(PagingAccessor **accessor, Flexpage **flexpage)

  {

    Flexpage_queue_item item;

    /* Handle concurrent removal. */

    while (1)

    {

      decrement();

      lock_queue();

      if (!_queue.empty())

        break;

      unlock_queue();

    }

    item = _queue.front();

    *accessor = item.first;

    *flexpage = item.second;

    _remove(*flexpage);

    unlock_queue();

    return true;

  }

  void push(PagingAccessor *accessor, Flexpage *flexpage)

  {

    lock_queue();

    if (_positions.find(flexpage) != _positions.end())

    {

      unlock_queue();

      return;

    }

    _queue.push_back(Flexpage_queue_item(accessor, flexpage));

    Flexpage_queue::iterator it = _queue.end();

    it--;

    _positions.insert(Flexpage_position_item(flexpage, it));

    increment();

    unlock_queue();

  }

  bool remove(Flexpage *flexpage)

  {

    lock_queue();

    bool result = _remove(flexpage);

    unlock_queue();

    return result;

  }

  bool _remove(Flexpage *flexpage)

  {

    Flexpage_positions::iterator item = _positions.find(flexpage);

    /* With the counter moderating access, this condition should never be

       true. */

    if (item == _positions.end())

      return false;

    _queue.erase(item->second);

    _positions.erase(item);

    return true;

  }

  void purge(PagingAccessor *accessor)

  {

    lock_queue();

    Flexpage_queue::iterator it = _queue.begin();

    while (it != _queue.end())

    {

      Flexpage_queue::iterator current = it;

      it++;

      if (current->first != accessor)

        continue;

      /* Insert a new queue entry for the flexpage to replace the existing

         one. */

      Flexpage_queue::iterator repl = _queue.insert(it, Flexpage_queue_item(NULL, current->second));

      /* Find the position of the queue entry and remove it from the mapping. */

      Flexpage_positions::iterator item = _positions.find(current->second);

      if (item != _positions.end())

      {

        _positions.erase(item);

        _positions.insert(Flexpage_position_item(current->second, repl));

      }

      /* Erase the existing queue entry, leaving a null replacement. */

      _queue.erase(current);

    }

    unlock_queue();

  }

};

/* A page collection exposing parts of a resource. */ 

class Pages

{

  /* Memory used to provide flexpages. */

  unsigned long _allocated, _limit;

  l4_cap_idx_t _memory_semaphore;

  /* Queue of issued flexpages for eventual recycling. */

  PageQueue _queue;

protected:

  bool can_get_memory();

  l4_addr_t get_memory(unsigned long size);

public:

  explicit Pages(unsigned long limit);

  Flexpage *new_flexpage(unsigned long offset, l4_addr_t hot_spot,

                         unsigned long flags);

  Flexpage *new_flexpage(unsigned long offset, l4_addr_t hot_spot,

                         unsigned long flags, l4_addr_t address,

                         unsigned long size);

  void queue_flexpage(PagingAccessor *accessor, Flexpage *flexpage);

  bool reserve_flexpage(PagingAccessor *accessor, Flexpage *flexpage);

  Flexpage *remove_flexpage();

  void remove_accessor(PagingAccessor *accessor);

};