/* 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/>. */

/* Memoire cache pour les acces disque.
 * Reference : Tanenbaum, p. 447. */

#include "device_struct.h"

#include <block_driver_struct.h>
#include <printk.h>
#include <condition.h>
#include <condition_struct.h>
#include <areas.h>
#include <consts.h>
#include <config.h>
#include <stddef.h>

#define HASH_TABLE_SIZE 307     /* un nombre premier raisonnable */

#define hash(dev, blk)  (((unsigned)(dev->id ^ blk)) % HASH_TABLE_SIZE)

struct block_info_struct {
  /* cle */
  const struct device_struct *device;
  unsigned long block;

  /* tampon */
  void *buffer;

  /* indicateurs */
  unsigned locked : 1;          /* verrouille (en cours d'utilisation) */
  unsigned invalid : 1;         /* a ete invalide (n'a de sens que si locked != 0) */
  unsigned uptodate : 1;        /* contient les donnees du bloc du disque */
  unsigned dirty : 1;           /* a ete modifie par rapport au bloc du disque */

  /* chainage pour la liste des blocs libres */
  struct block_info_struct *previous_free;
  struct block_info_struct *next_free;

  /* chainage pour la table de hachage */
  struct block_info_struct *previous_hash;
  struct block_info_struct *next_hash;

  /* chainage pour la liste de blocs sales */
  struct block_info_struct *next_dirty;
};

#define get_block_info(buf) ((struct block_info_struct *)buffer_start + ((buffer_end - (buf)) / BLOCK_SIZE - 1))

/* liste des blocs libres */
static struct block_info_struct *first_free; /* LRU */
static struct block_info_struct *last_free; /* MRU */

/* table de hachage */
static struct block_info_struct *hash_table[HASH_TABLE_SIZE];

/* divers */
static unsigned long size; /* nombre de blocs */
static struct condition_struct condition; /* condition pour l'obtention d'un block_info */
/* Le buffer cache lui-meme n'est pas synchronise. Il ne doit donc pas etre
 * accede dans des gestionnaires d'interruptions. */

/* Liste des blocs libres */

/* Retourne le bloc libre le moins recemment utilise (LRU). */
static struct block_info_struct *get_free()
{
  return first_free;
}

/* Le bloc ne doit pas etre dans la liste. */
static void push_free(struct block_info_struct *block_info)
{
  /* preparation */
  block_info->previous_free = last_free;
  block_info->next_free = NULL;

  /* connexion */
  if (last_free) /* first_free et last_free sont toujours tous deux nuls ou tous deux non nuls */
    last_free->next_free = block_info;
  else
    first_free = block_info;
  last_free = block_info;
}

/* Le bloc doit etre dans la liste. */
static void remove_free(struct block_info_struct *block_info)
{
  /* deconnexion */
  if (block_info == first_free)
    first_free = first_free->next_free;
  else
    block_info->previous_free->next_free = block_info->next_free;
  if (block_info == last_free)
    last_free = last_free->previous_free;
  else
    block_info->next_free->previous_free = block_info->previous_free;
}

/* Enleve le bloc de la liste des blocs vides et le verrouille (maintient la
 * coherence de la structure). */
static void take(struct block_info_struct *block_info)
{
  remove_free(block_info);
  block_info->locked = 1;
}

/* Deverrouille le bloc et l'ajoute dans la liste des blocs vides (maintient la
 * coherence de la structure). */
static void release(struct block_info_struct *block_info)
{
  block_info->locked = 0;
  push_free(block_info);
}

/* Table de hachage */

/* Retourne NULL si le bloc demande n'est pas dans la table. */
static struct block_info_struct *get_hash(const struct device_struct *device, unsigned long block)
{
  struct block_info_struct *bi;

  for (bi = hash_table[hash(device, block)]; bi; bi = bi->next_hash)
    if (bi->device == device && bi->block == block)
      return bi;
  return NULL;
}

/* Le bloc ne doit pas etre dans la table. */
static void put_hash(struct block_info_struct *block_info)
{
  unsigned long hash_code;
  struct block_info_struct *fh;

  hash_code = hash(block_info->device, block_info->block);
  fh = hash_table[hash_code];

  /* preparation */
  block_info->previous_hash = NULL;
  block_info->next_hash = fh;

  /* connexion */
  if (fh)
    fh->previous_hash = block_info;
  hash_table[hash_code] = block_info;
}

/* Le bloc doit etre dans la table. */
static void remove_hash(struct block_info_struct *block_info)
{
  /* deconnexion */
  if (block_info->previous_hash)
    block_info->previous_hash->next_hash = block_info->next_hash;
  else
    hash_table[hash(block_info->device, block_info->block)] = block_info->next_hash;
  if (block_info->next_hash)
    block_info->next_hash->previous_hash = block_info->previous_hash;
}

/* Liste des blocs sales */

static void add_dirty(struct block_info_struct **first_dirty, struct block_info_struct *block_info)
{
  block_info->next_dirty = *first_dirty;
  *first_dirty = block_info;
}

static inline int compare_dirty(const struct block_info_struct *block_info1, const struct block_info_struct *block_info2)
{
  if (block_info1->device != block_info2->device)
    return block_info1->device < block_info2->device ? -1 : 1;
  if (block_info1->block != block_info2->block)
    return block_info1->block < block_info2->block ? -1 : 1;
  return 0;
}

static void divide_dirty(struct block_info_struct *first, struct block_info_struct **first1, struct block_info_struct **first2)
{
  struct block_info_struct *bi1, *bi2;

  if (!(*first1 = first)) {
    *first2 = NULL;
    return;
  }
  if (!(*first2 = first->next_dirty))
    return;
  divide_dirty(first->next_dirty->next_dirty, &bi1, &bi2);
  (*first1)->next_dirty = bi1;
  (*first2)->next_dirty = bi2;
}

static void merge_dirty(struct block_info_struct *first1, struct block_info_struct *first2, struct block_info_struct **first)
{
  if (!first1) {
    *first = first2;
    return;
  }
  if (!first2) {
    *first = first1;
    return;
  }
  if (compare_dirty(first1, first2) < 0) {
    merge_dirty(first1->next_dirty, first2, first);
    first1->next_dirty = *first;
    *first = first1;
  }
  else {
    merge_dirty(first1, first2->next_dirty, first);
    first2->next_dirty = *first;
    *first = first2;
  }
}

/* Tri de la liste des blocs sales par tri-fusion. */
static void sort_dirty(struct block_info_struct **first)
{
  struct block_info_struct *first1, *first2;

  if (!*first || !(*first)->next_dirty)
    return;
  divide_dirty(*first, &first1, &first2);
  sort_dirty(&first1);
  sort_dirty(&first2);
  merge_dirty(first1, first2, first);
}

/* Entrees / Sorties */

static int read(struct block_info_struct *block_info)
{
  return block_info->device->block_driver->read(block_info->block, block_info->buffer);
}

static int write(struct block_info_struct *block_info)
{
  return block_info->device->block_driver->write(block_info->block, block_info->buffer);
}

/* Cache */

/* non bloquante */
static void invalidate(const struct device_struct *device)
{
  struct block_info_struct *bi;
  int i;

  for (i = 0; i < HASH_TABLE_SIZE; i++)
    for (bi = hash_table[i]; bi; bi = bi->next_hash)
      if (!device || bi->device == device) {
        if (bi->locked)
          bi->invalid = 1;
        else
          remove_hash(bi); /* n'invalide pas l'iteration :) */
      }
}

/* A la difference de invalidate(), sync() est bloquante, car elle fait des
 * appels a write(). Il est donc necessaire de verrouiller les blocs concernes.
 * A defaut d'un veritable algorithme d'optimisation des deplacements du bras
 * des lecteurs de disques, on ecrit les blocs sales dans l'ordre croissant, ce
 * qui devrait reduire les degats. */
static int sync(const struct device_struct *device)
{
  struct block_info_struct *bi;
  struct block_info_struct *first_dirty;
  const struct device_struct *bad_dev;
  int i;
  int st;

  /* construction de la liste des blocs sales */
  first_dirty = NULL;
  for (i = 0; i < HASH_TABLE_SIZE; i++)
    for (bi = hash_table[i]; bi; bi = bi->next_hash)
      if ((!device || bi->device == device) && !bi->locked && bi->dirty)
        add_dirty(&first_dirty, bi);

  /* tri de la liste des blocs sales et ecriture */
  if (first_dirty) { /* test non indispensable - petite optimisation */
    st = 1;
    sort_dirty(&first_dirty);
    bad_dev = 0;
    for (bi = first_dirty; bi; bi = bi->next_dirty) {
      /* On est oblige de retester la condition car la fonction est bloquante. */
      if ((!device || bi->device == device) && !bi->locked && bi->dirty) {
        if (bi->device == bad_dev)
          continue;
        take(bi);
        if (!write(bi)) {
          bad_dev = bi->device; /* on retient que ce peripherique ne fonctionne pas */
          st = 0;
        }
        else {
          bi->uptodate = 1;
          bi->dirty = 0;
        }
        release(bi);
      }
    }
    return st;
  }
  else
    return 1;
}

/* Initialisation */

static void init_cache()
{
  struct block_info_struct *bi;
  void *b;

  bi = buffer_start;
  b = buffer_end;
  size = 0;
  while ((b -= BLOCK_SIZE) >= (void *)(bi + 1)) {
    bi->device = NULL;
    bi->buffer = b; /* fixe */
    bi->locked = 0; /* entree libre */
    bi->previous_free = bi - 1;
    bi->next_free = bi + 1;
    bi++;
    size++;
  }
  first_free = buffer_start;
  first_free->previous_free = NULL;
  last_free = bi - 1;
  last_free->next_free = NULL;
}

static void init_hash_table()
{
  int i;

  for (i = 0; i < HASH_TABLE_SIZE; i++)
    hash_table[i] = NULL;
}

/* Fonctions exportees */

void buffer_init()
{
  init_cache();
  init_hash_table();
  condition_init(&condition);
}

void buffer_print_info()
{
  printk("Buffer cache size: %luKB\n", (size * BLOCK_SIZE) >> 10);
}

int buffer_is_writable(const struct device_struct *device)
{
  if (device->type != FT_BLK)
    return 0;

  return device->block_driver->is_writable();
}

/* Retourne un tampon sur un bloc. Cette fonction est bloquante si le cache est
 * plein. La valeur de retour n'est jamais nulle, sauf si device n'est pas un
 * peripherique de type bloc ou si le bloc n'existe pas pour ce peripherique.
 */
void *buffer_get(const struct device_struct *device, unsigned long block)
{
  struct block_info_struct *bi;

  if (device->type != FT_BLK)
    return NULL;

  /* Inutile de gaspiller de la place avec des blocs inexistants. */
  if (block >= device->block_driver->get_block_count())
    return NULL;

 start:
  if (device->block_driver->has_changed())
    invalidate(device);
  if (!(bi = get_hash(device, block))) {
    if (!(bi = get_free())) { /* bloc libre le moins recemment utilise */
      condition_wait(&condition);
      goto start;
    }
    take(bi);
    if (bi->device && get_hash(bi->device, bi->block)) { /* le bloc est utilise */
      if (bi->dirty) /* il contient des donnees non synchronisees */
        write(bi); /* on le synchronise */
      remove_hash(bi);
    }
    bi->device = device;
    bi->block = block;
    bi->uptodate = 0;
    bi->dirty = 0;
    put_hash(bi);
  }
  else if (bi->locked) {
    condition_wait(&condition);
    goto start;
  }
  else
    take(bi);
  bi->invalid = 0;
  return bi->buffer;
}

/* Indique que le tampon n'est plus en cours d'utilisation. */
void buffer_release(const void *buffer)
{
  struct block_info_struct *bi;

  bi = get_block_info(buffer);
  if (bi->invalid)
    bi->uptodate = 0;
  release(bi);
  condition_signal_all(&condition);
}

/* Transfert, si necessaire, le bloc du disque vers le tampon. Retourne une
 * valeur non nulle si et seulement si le transfert a reussi. */
int buffer_update(void *buffer)
{
  struct block_info_struct *bi;

  bi = get_block_info(buffer);
  if (bi->invalid)
    return 0;
  if (!bi->uptodate) {
    if (!read(bi))
      return 0;
    bi->uptodate = 1;
    bi->dirty = 0;
  }
  return 1;
}

/* Marque le bloc comme sale. Le transfert du bloc du tampon vers le disque
 * aura lieu lors du prochain appel a buffer_sync(). */
void buffer_dirty(const void *buffer)
{
  struct block_info_struct *bi;

  bi = get_block_info(buffer);
  if (bi->invalid)
    return;
  bi->dirty = 1;
}

/* Transfert tous les blocs sales du peripherique device de leur tampon vers le
 * disque. Si device == 0, transfert tous les blocs sales. Retourne une valeur
 * non nulle si et seulement si le transfert a reussi. */
int buffer_sync(const struct device_struct *device)
{
  if (device->type != FT_BLK)
    return 0;

  return sync(device);
}