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

/* Allocateur de memoire minimaliste pour ld.so.
 * Caracteristiques :
 * - malloc() ne doit plus etre appele une fois que du code du programme
 * principal a ete execute. En effet, le programme peut lui-meme modifier la
 * taille du segment de donnees, ce qui invalide les structures de gestion de
 * la memoire de ld.so.
 * - free() ne libere pas de memoire, ni n'accede au systeme pour modifier la
 * taille du segment de donnees. Il peut donc etre appele sans risque meme si
 * du code utilisateur a ete execute.
 * Par consequent la consommation memoire ne fait qu'augmenter, ce qui n'est
 * pas genant vu la consommation tres limitee de ld.so. */

#include "stdlib.h"

#include "unistd.h"

#include <string.h>
#include <stddef.h>

#define BITS (sizeof (size_t) * 8)

#define MEMORY_GROW 131072 /* 128K */

/* bloc de memoire */
struct block_struct {
  size_t size; /* taille du bloc */
  void *data[1];
};

#define BLOCK_HEADER_SIZE (offsetof(struct block_struct, data))

/* taille minimale d'un bloc */
static size_t min_block_size;

static void *memory_end;

/* tas */
static void *heap_end = NULL;

static inline size_t nextpow2(size_t n)
{
  register unsigned int k;

  n--;
  for (k = 1; k < BITS; k <<= 1)
    n = n | n >> k;
  return n + 1;
}

/* Allocation de memoire aupres du systeme */

static int init_memory(void **memory_start)
{
  void *addr;

  if ((addr = __sbrk(0)) == (void *)-1)
    return -1;
  *memory_start = memory_end = addr;
  return 0;
}

static int resize_memory(void *end)
{
  size_t incr;
  void *addr;

  if (end > memory_end) {
    incr = (end - memory_end + (MEMORY_GROW - 1)) / MEMORY_GROW * MEMORY_GROW;
    if ((addr = __sbrk(incr)) == (void *)-1)
      return -1;
    memory_end = addr + incr;
  }
  return 0;
}

/* Fonctions sur le tas */

static int setup_heap()
{
  min_block_size = nextpow2(sizeof (struct block_struct));
  if (init_memory(&heap_end) == -1)
    return -1;
  /* alignement de heap_end de sorte que le pointeur sur les donnees des
     blocs soit correctement aligne pour n'importe quel type d'objet (ANSI C)
  */
  heap_end += BLOCK_HEADER_SIZE;
  heap_end = (void *)(((intptr_t)heap_end | (sizeof (union {long l; double d;}) - 1)) + 1);
  heap_end -= BLOCK_HEADER_SIZE;
  return 0;
}

/* size doit etre un diviseur de heap_size. */
static int grow_heap(size_t incr)
{
  if (resize_memory(heap_end + incr) == -1)
    return -1;
  heap_end += incr;
  return 0;
}

/* Fonctions sur les blocs */

static struct block_struct *alloc_block(size_t size)
{
  struct block_struct *block;

  block = heap_end;
  if (grow_heap(size) == -1)
    return NULL;
  block->size = size;
  return block;
}

/* Redimensionne un bloc alloue, si possible. */
static int resize_block(struct block_struct *block, size_t size)
{
  if (size == block->size)
    return 1;
  else if (size > block->size)
    return 0;
  else { /* size < block->size */
    block->size = size;
    return 1;
  }
}

/* D'apres le standard, "If the size of the space requested is 0, the behavior
 * is implementation-defined: the value returned shall be either a null pointer
 * or a unique pointer.". Ici, nous renvoyons un pointeur unique. */
void __attribute__ ((weak, visibility ("default"))) *malloc(size_t size)
{
  struct block_struct *block;

  if (!heap_end)
    if (setup_heap() == -1)
      return NULL;

  size += BLOCK_HEADER_SIZE;
  size = (size + (min_block_size - 1)) & ~(min_block_size - 1);
  if (!(block = alloc_block(size)))
    return NULL;
  return block->data;
}
typeof (malloc) __malloc __attribute__ ((alias ("malloc")));

void __attribute__ ((weak, visibility ("default"))) *calloc(size_t nmemb, size_t size)
{
  void *ptr;

  if (!(ptr = __malloc(nmemb * size)))
    return NULL;
  memset(ptr, 0, nmemb * size);
  return ptr;
}
typeof (calloc) __calloc __attribute__ ((alias ("calloc")));

void __attribute__ ((weak, visibility ("default"))) free(void *ptr) {}
typeof (free) __free __attribute__ ((alias ("free")));

void __attribute__ ((weak, visibility ("default"))) *realloc(void *ptr, size_t size)
{
  struct block_struct *block, *new_block;

  if (ptr == NULL)
    return __malloc(size);

  if (size == 0) {
    __free(ptr);
    return NULL;
  }

  size += BLOCK_HEADER_SIZE;
  size = (size + (min_block_size - 1)) & ~(min_block_size - 1);
  block = ptr - BLOCK_HEADER_SIZE;

  /* On essaie d'abord de redimensionner le bloc. */
  if (resize_block(block, size))
    return ptr;

  /* S'il n'est pas possible de redimensionner le bloc, on en alloue un nouveau
     et on copie les donnees dedans. */
  if (!(new_block = alloc_block(size)))
    return NULL;
  memcpy(new_block->data, block->data, (size < block->size ? size : block->size) -  BLOCK_HEADER_SIZE);
  return new_block->data;
}
typeof (realloc) __realloc __attribute__ ((alias ("realloc")));