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

/* Partie de la memoire physique accessible directement par les tables des
 * pages du noyau.
 * Le systeme d'allocation utilise est l'algorithme du compagnon ("buddy"). */

#include <i386.h>
#include <misc.h>
#include <stddef.h>

#define FREE_TABLE_SIZE (32 - LOG_PAGE_SIZE)

struct lowmem_free_page_frame_data_struct {
  struct lowmem_free_page_frame_data_struct *previous;
  struct lowmem_free_page_frame_data_struct *next;
};

struct lowmem_allocated_page_frame_data_struct {
  unsigned short count;
};

/* cadres de pages */
static void *page_frames_start;
static struct lowmem_allocated_page_frame_data_struct *page_frames_map;
static struct lowmem_allocated_page_frame_data_struct *page_frames_map_lazy_end;
static struct lowmem_allocated_page_frame_data_struct *page_frames_map_end;
static struct lowmem_free_page_frame_data_struct *first_free_page_frame_data[FREE_TABLE_SIZE];

#define _index(page_frame) (((page_frame) - page_frames_start) / PAGE_SIZE)
#define _page_frame(index) (page_frames_start + (index) * PAGE_SIZE)

static void init_page_frames(void *start, void *end)
{
  unsigned long n;
  void *page_frame;
  unsigned int k;
  struct lowmem_free_page_frame_data_struct *page_frame_data;

  /* partition de la memoire */
  n = (end - start) / (sizeof (struct lowmem_allocated_page_frame_data_struct) + PAGE_SIZE);
  page_frames_start = end - n * PAGE_SIZE;
  page_frames_map = start;
  page_frames_map_lazy_end = start;
  page_frames_map_end = start + n * sizeof (struct lowmem_allocated_page_frame_data_struct);

  /* liste des cadres de pages libres */
  page_frame = page_frames_start;
  for (k = FREE_TABLE_SIZE; k--;) {
    if (n & exp2(k)) {
      page_frame_data = (struct lowmem_free_page_frame_data_struct *)page_frame;
      page_frame_data->previous = NULL;
      page_frame_data->next = NULL;
      first_free_page_frame_data[k] = page_frame_data;
      page_frame += PAGE_SIZE << k;
    }
    else
      first_free_page_frame_data[k] = NULL;
  }
}

static void push_free_page_frame_data(struct lowmem_free_page_frame_data_struct *page_frame_data, unsigned int k)
{
  page_frame_data->previous = NULL;
  page_frame_data->next = first_free_page_frame_data[k];
  if (page_frame_data->next)
    page_frame_data->next->previous = page_frame_data;
  first_free_page_frame_data[k] = page_frame_data;
}

static struct lowmem_free_page_frame_data_struct *pop_free_page_frame_data(unsigned int k)
{
  struct lowmem_free_page_frame_data_struct *page_frame_data;

  if ((page_frame_data = first_free_page_frame_data[k])) {
    if (page_frame_data->next)
      page_frame_data->next->previous = NULL;
    first_free_page_frame_data[k] = page_frame_data->next;
  }
  return page_frame_data;
}

static void remove_free_page_frame_data(struct lowmem_free_page_frame_data_struct *page_frame_data, unsigned int k)
{
  if (page_frame_data->previous)
    page_frame_data->previous->next = page_frame_data->next;
  else
    first_free_page_frame_data[k] = page_frame_data->next;
  if (page_frame_data->next)
    page_frame_data->next->previous = page_frame_data->previous;
}

static int is_mapped(const void *page_frame)
{
  return page_frame >= page_frames_start;
}

static struct lowmem_allocated_page_frame_data_struct *get_page_frame_data(const void *page_frame)
{
  struct lowmem_allocated_page_frame_data_struct *page_frame_data;

  page_frame_data = &page_frames_map[_index(page_frame)];
  while (page_frames_map_lazy_end <= page_frame_data) {
    page_frames_map_lazy_end->count = 0;
    page_frames_map_lazy_end++;
  }
  return page_frame_data;
}

static void allocate_page_frames(void *page_frames, unsigned long n)
{
  while (n--) {
    get_page_frame_data(page_frames)->count = 1;
    page_frames += PAGE_SIZE;
  }
}

static void deallocate_page_frames(void *page_frames, unsigned long n)
{
  while (n--) {
    get_page_frame_data(page_frames)->count = 0;
    page_frames += PAGE_SIZE;
  }
}

static int are_page_frames_free(void *page_frames, unsigned long n)
{
  while (n--) {
    if (get_page_frame_data(page_frames)->count)
      return 0;
    page_frames += PAGE_SIZE;
  }
  return 1;
}

static void hold_page_frame(void *page_frame)
{
  get_page_frame_data(page_frame)->count++;
}

static int release_page_frame(void *page_frame)
{
  struct lowmem_allocated_page_frame_data_struct *page_frame_data;

  page_frame_data = get_page_frame_data(page_frame);
  if (page_frame_data->count == 1)
    return 0;
  page_frame_data->count--;
  return 1;
}

static int is_page_frame_shared(void *page_frame)
{
  return get_page_frame_data(page_frame)->count > 1;
}

static void *get_buddy(void *page_frames, unsigned int k)
{
  unsigned long i;

  i = _index(page_frames) ^ exp2(k); /* compagnon */
  if (&page_frames_map[i + exp2(k)] > page_frames_map_end)
    return NULL; /* le compagnon n'existe pas */
  return _page_frame(i);
}

/* Interface de l'allocateur de pages noyau contigues */

void lowmem_init(unsigned short size_m, void *start_data)
{
  init_page_frames(start_data, (void *)((unsigned long)size_m << 20));
}

void lowmem_print_info() {}

/* Alloue 2^k pages noyaux contigues. */
void *alloc_page_frames(unsigned int k)
{
  void *page_frames;
  unsigned int i;

  page_frames = NULL;
  i = k;
  while (i < FREE_TABLE_SIZE && !(page_frames = pop_free_page_frame_data(i)))
    i++;
  if (!page_frames)
    return NULL;

  /* division */
  while (i > k) {
    i--;
    push_free_page_frame_data(page_frames + (PAGE_SIZE << i), i);
  }

  allocate_page_frames(page_frames, exp2(k));
  return page_frames;
}

void free_page_frames(void *ptr, unsigned int k)
{
  void *page_frames, *buddy;

  page_frames = ptr;
  deallocate_page_frames(page_frames, exp2(k));

  /* fusion */
  while (k < FREE_TABLE_SIZE && (buddy = get_buddy(page_frames, k)) && are_page_frames_free(buddy, exp2(k))) {
    remove_free_page_frame_data(buddy, k);
    if (buddy < page_frames)
      page_frames = buddy;
    k++;
  }
  push_free_page_frame_data(page_frames, k);
}

/* Allocateur de cadre de pages utilisateurs dans la memoire basse */

unsigned long alloc_page_frame_lowmem()
{
  return (unsigned long)alloc_page_frames(0);
}

void hold_page_frame_lowmem(unsigned long page_frame)
{
  if (is_mapped((void *)page_frame))
    hold_page_frame((void *)page_frame);
}

void release_page_frame_lowmem(unsigned long page_frame)
{
  if (is_mapped((void *)page_frame))
    if (!release_page_frame((void *)page_frame))
      free_page_frames((void *)page_frame, 0);
}

int is_page_frame_shared_lowmem(unsigned long page_frame)
{
  if (is_mapped((void *)page_frame))
    return is_page_frame_shared((void *)page_frame);
  else
    return 1;
}