/* Carte de la memoire lineaire utilisateur d'un processus */
/* Copyright (C) 2008  Emmanuel Varoquaux

   This file is part of XOS.

   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 3 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, see <http://www.gnu.org/licenses/>. */

#include "map.h"
#include "map_struct.h"

#include <maps_struct.h>
#include <map_info_struct.h>
#include <kmalloc.h>
#include <errno.h>
#include <assert.h>
#include <string.h>
#include <stddef.h>
#include <limits.h>

static inline int check_for_addition(unsigned long i1, unsigned long i2)
{
  return i1 <= ULONG_MAX - i2;
}

static int merge_map(struct maps_struct *maps, struct map_struct *map, struct map_struct *map1)
{
  if (!map_merge(map, map1))
    return 0;
  if (map1->next) {
    map->next = map1->next;
    map1->next->previous = map;
  }
  else {
    map->next = NULL;
    maps->last_map = map;
  }
  return 1;
}

/* Construit une carte de la memoire vide. */
void init_maps(struct maps_struct *maps)
{
  maps->first_map = NULL;
  maps->last_map = NULL;
}

/* Retourne 1 en cas de succes, 0 en cas d'echec. */
int insert_map(struct maps_struct *maps, struct map_struct *map)
{
  struct map_struct *map1, *map2;
  int st;

  map1 = NULL;
  map2 = maps->first_map;
  while (map2) {
    st = compare_maps(map, map2);
    if (st == 0) /* les maps se chevauchent */
      return 0;
    if (st < 0)
      break;
    map1 = map2;
    map2 = map2->next;
  }
  /* insertion de map entre map1 et map2 */
  if (!map2) {
    map->next = NULL;
    maps->last_map = map;
  }
  else if (!merge_map(maps, map, map2)) {
    map->next = map2;
    map2->previous = map;
  }
  if (!map1) {
    map->previous = NULL;
    maps->first_map = map;
  }
  else if (!merge_map(maps, map1, map)) {
    map->previous = map1;
    map1->next = map;
  }
  return 1;
}

/* En cas d'erreur, l'effacement peut etre partiellement realise. */
int clear_maps(struct maps_struct *maps, unsigned long start, unsigned long length)
{
  struct map_struct *map1, *map2, *new_map, *next_map;
  int st;
  int rv;

  map1 = NULL;
  map2 = maps->first_map;

  /* recherche de la premiere map apres le debut de l'intervalle */
  while (1) {
    if (!map2)
      return 0;
    st = compare_map_laddr(map2, start);
    if (st > 0) /* map2 est apres start */
      break;
    if (st == 0) { /* map2 contient start */
      if ((rv = map_split(map2, start, &new_map)) < 0)
        /* Hum. Situation bien embarrassante... */
        return rv;
      if (new_map) { /* start est strictement inclus dans map2 : new_map creee */
        new_map->previous = map2;
        new_map->next = map2->next;
        map2->next = new_map;
        if (new_map->next)
          new_map->next->previous = new_map;
        else
          maps->last_map = new_map;
        map1 = map2;
        map2 = new_map;
      }
      break;
    }

    map1 = map2;
    map2 = map2->next;
  }
  /* map1 est la derniere map avant le debut de l'intervalle, map2 est la
    premiere map apres le debut de l'intervalle (forcement non nulle). */

  /* effacement des maps dans l'intervalle */
  do {
    if (check_for_addition(start, length)) {
      st = compare_map_laddr(map2, start + length);
      if (st > 0) /* map2 est strictement apres start + length */
        break; /* on s'arrete la */
      if (st == 0) { /* map2 contient start + length */
        /* map2 est a supprimer partiellement */
        if ((rv = map_split(map2, start + length, &new_map)) < 0)
          return rv;
        if (!new_map)
          break;
        if (map2->next) {
          new_map->next = map2->next;
          new_map->next->previous = new_map;
        }
        else {
          new_map->next = NULL;
          maps->last_map = new_map;
        }
        if (map1) {
          new_map->previous = map1;
          map1->next = new_map;
        }
        else {
          new_map->previous = NULL;
          maps->first_map = new_map;
        }
        free_map(map2);
        break;
      }
    }
    /* map2 est a supprimer entierement */
    if (map1) {
      if (map2->next) {
        map1->next = map2->next;
        map2->next->previous = map1;
      }
      else {
        map1->next = NULL;
        maps->last_map = map1;
      }
    }
    else {
      if (map2->next) {
        maps->first_map = map2->next;
        map2->next->previous = NULL;
      }
      else {
        maps->first_map = NULL;
        maps->last_map = NULL;
      }
    }
    next_map = map2->next;
    free_map(map2);
    map2 = next_map;
  }
  while (map2);
  return 0;
}

/* dest_maps doit etre initialise et vide dans l'intervalle demande.
 * En cas d'erreur, un code d'erreur est renvoye, et les maps deja clonees dans
 * dest_maps ne sont pas detruites. */
int clone_maps(const struct maps_struct *maps, struct maps_struct *dest_maps, unsigned long start, unsigned long length)
{
  struct map_struct *map, *new_map;
  int st;
  int rv;

  for (map = maps->first_map; map; map = map->next) {
    if ((rv = map_clone(map, start, length, &st, &new_map)) < 0)
      return rv; /* erreur */
    if (st > 0) /* map apres l'intervalle */
      break; /* on s'arrete la */
    if (st == 0) /* map dans l'intervalle : clonage effectue */
      assert(insert_map(dest_maps, new_map));
  }
  return 0;
}

int protect_maps(struct maps_struct *maps, unsigned long start, unsigned long length, int prot)
{
  struct map_struct *map, *new_map;
  int st;
  int rv;

  map = maps->first_map;

  /* recherche de la premiere map apres le debut de l'intervalle */
  while (1) {
    if (!map)
      return 0;
    st = compare_map_laddr(map, start);
    if (st > 0) /* map est apres start */
      break;
    if (st == 0) { /* map contient start */
      if (compare_map_prot(map, prot)) {
        map = map->next;
        break;
      }
      if ((rv = map_split(map, start, &new_map)) < 0)
        /* Hum. Situation bien embarrassante... */
        return rv;
      if (new_map) { /* start est strictement inclus dans map : new_map creee */
        new_map->previous = map;
        new_map->next = map->next;
        map->next = new_map;
        if (new_map->next)
          new_map->next->previous = new_map;
        else
          maps->last_map = new_map;
        map = new_map;
      }
      break;
    }

    map = map->next;
  }
  /* map est la premiere map apres le debut de l'intervalle (forcement non
     nulle). */

  /* protection des maps dans l'intervalle */
  do {
    if (check_for_addition(start, length)) {
      st = compare_map_laddr(map, start + length);
      if (st > 0) /* map est strictement apres start + length */
        break; /* on s'arrete la */
      if (st == 0) { /* map contient start + length */
        /* map est a proteger partiellement */
        if (compare_map_prot(map, prot))
          break;
        if ((rv = map_split(map, start + length, &new_map)) < 0)
          return rv;
        if (!new_map)
          break;
        if (map->next) {
          new_map->next = map->next;
          new_map->next->previous = new_map;
        }
        else {
          new_map->next = NULL;
          maps->last_map = new_map;
        }
        new_map->previous = map;
        map->next = new_map;
        map_protect(map, prot);
        break;
      }
    }
    /* map est a proteger entierement */
    map_protect(map, prot);
    map = map->next;
  }
  while (map);
  return 0;
}

struct map_struct *find_map(const struct maps_struct *maps, unsigned long laddr)
{
  struct map_struct *map;

  for (map = maps->first_map; map; map = map->next)
    if (compare_map_laddr(map, laddr) == 0)
      return map;
  return NULL;
}

struct map_struct *find_next_map(const struct maps_struct *maps, unsigned long laddr)
{
  struct map_struct *map;

  for (map = maps->first_map; map; map = map->next)
    if (compare_map_laddr(map, laddr) >= 0)
      return map; /* map est la map qui contient laddr ou celle immediatement superieure */
  return NULL;
}

/* Retourne l'adresse de demarrage d'une zone libre pour une projection de
 * longueur length dans le segment [base, base + size[ de l'espace
 * d'adressage lineaire du processus courant.
 * base doit etre aligne sur une frontiere de page.
 * size doit etre non nul et multiple de PAGE_SIZE.
 * [base, base + size[ doit etre valide.
 * length doit etre non nul et multiple de PAGE_SIZE.
 * Si side est negatif, la zone libre est calee vers les basses addresses,
 * sinon la zone libre est calee vers les hautes addresses.
 * Zero est retourne en cas d'echec. */
unsigned long get_free_area(const struct maps_struct *maps, unsigned long base, unsigned long size, unsigned long length, int side)
{
  const struct map_struct *map1, *map2;
  unsigned long start, len;
  int st;

  if (length > size)
    return 0;
  if (side < 0) {
    map1 = NULL;
    map2 = maps->first_map;
    while (1) {
      st = hole_intersect(map1, map2, base, size, &start, &len);
      if (st > 0)
        return 0;
      if (st == 0 && len >= length)
        return start;
      if (!map2)
        return 0;
      map1 = map2;
      map2 = map2->next;
    }
  }
  else {
    map1 = maps->last_map;
    map2 = NULL;
    while (1) {
      st = hole_intersect(map1, map2, base, size, &start, &len);
      if (st < 0)
        return 0;
      if (st == 0 && len >= length)
        return start + (len - length);
      if (!map1)
        return 0;
      map2 = map1;
      map1 = map1->previous;
    }
  }
}

/* Retourne la liste des projections. */
int get_maps(const struct maps_struct *maps, struct map_info_struct **map_info_array, unsigned int *count)
{
  int retval;
  int map_count;
  struct map_struct *map;
  int i, j;

  if (!maps->first_map) {
    *map_info_array = NULL;
    *count = 0;
    return 0;
  }
  map_count = 0;
  for (map = maps->first_map; map; map = map->next)
    map_count++;
  if (!(*map_info_array = kmalloc(map_count * sizeof (struct map_info_struct))))
    return -ENOMEM;
  *count = map_count;
  i = 0;
  for (map = maps->first_map; map; map = map->next) {
    if ((retval = map_get_info(map, &(*map_info_array)[i])) < 0)
      goto error;
    i++;
  }
  return 0;

 error:
  for (j = 0; j < i; j++)
    if ((*map_info_array)[j].pathname)
      kfree((*map_info_array)[j].pathname, strlen((*map_info_array)[j].pathname) + 1);
  kfree(*map_info_array, *count * sizeof (struct map_info_struct));
  return retval;
}