/* memory.c
 * This file is a part of decomp - a disassembler.  Here are the memory
 * allocation and deallocation routines.
 *
 * Copyright (C) 2001 Jonathan duSaint <dusaint@earthlink.net>
 *
 * The memory allocation is fairly routine.  The justification for not
 * using malloc as is is primarily a speed issue.  Secondary is the
 * fact that this organization allows sloppy memory accounting in the
 * main program.  When disassembling a file, there will be a lot of
 * allocations and deallocations of small, similarly-sized blocks of
 * memory (i.e. INSN).  By not releasing the memory each time a section
 * read is completed, it allows the same block to be reused for the
 * next section.
 * The mechanism of allocation is that large, CHUNK_SIZE sized blocks
 * of memory are requested from the system.  They are kept track of
 * by overlaying the first sizeof (sys_block) bytes with a
 * struct sys_block and having the next pointer point to the next
 * block, or being NULL.  That way, when xfree is called, the linked
 * list, kept in the variable memory, is walked and each node is free'd.
 * Each block is then carved up into smaller blocks.  Each of these
 * smaller blocks has the first sizeof (mem_header) bytes overlaid
 * by a struct mem_header.  Then, if one of the smaller blocks is needed,
 * the struct mem_header is placed on the alloc list.  If, relative
 * to the size of the memory request, it is fairly large, it is
 * partitioned into two blocks.  One is placed on the alloc list and
 * returned to the caller; the other is placed on the free list.  Then,
 * as space is needed, adjacent free blocks are merged to create larger
 * blocks.  If the global variable memory_trace is non-zero, then
 * messages are printed to stdout as important/interesting events
 * take place.  Also provided is the function void mem_trace (void),
 * which prints the alloc list, the free list, and the sys list.
 *
 * Started around 15 October 2001.
 */


#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "decomp.h"


/* the default amount of memory to request from the system each time */
#define DEFAULT_CHUNK_SIZE 2048

/* the minimum size of housekeeping info in a sys block */
#define ALLOC_ADJUST (sizeof (struct sys_block) + sizeof (struct mem_header))

/* the smallest amount which will be returned */
#define MIN_ALLOC_AMOUNT 8

/* the largest amount that can be handled at one time */
#define MAX_ALLOC_AMOUNT (chunk_size - ALLOC_ADJUST)


/* header for a block of memory - this is what is referenced on
   both the alloc and free lists */
struct mem_header {
  /* size of the chunk, not including the header */
  unsigned long size;
  struct mem_header *next;
} __attribute__ ((packed));


/* header for the block returned by a call to malloc(3) */
struct sys_block {
  struct sys_block *next;
} __attribute__ ((packed));


/* the free list */
struct mem_header *free_list = NULL;

/* the alloc list */
struct mem_header *alloc_list = NULL;

/* the list of malloc'ed blocks */
struct sys_block *memory;


/* info used for keeping stats */

/* the total memory alloc'ed from the OS */
unsigned long total_alloced;

/* the number of calls to xmalloc */
unsigned long xmalloc_calls;

/* the number of bytes returned by xmalloc */
unsigned long xmalloc_bytes;

/* the number of bytes free'd by xfree */
unsigned long xfree_bytes;


/* the allocation size for memory chunks */
unsigned long chunk_size;

/* whether or not to print status messages */
volatile int memory_trace = 0;

/* whether or not memory is fragmented */
int free_list_needs_compacting = 0;

/* forward declaration needed for mem_trace */
void compact_free_list (void);


/* mem_trace
 * Called in case something bad has happened.  Prints the contents
 * of the alloc list, the free list, and the sys list.
 */
void
mem_trace (void)
{
  struct mem_header *tmp;
  struct sys_block *sys;

  if (free_list_needs_compacting)
    compact_free_list ();

  fprintf (stderr, "alloc list:\n");
  tmp = alloc_list;
  while (tmp != NULL)
    {
      fprintf (stderr, "  %p->(%p, %ld)\n", tmp, tmp->next, tmp->size);
      tmp = tmp->next;
    }

  fprintf (stderr, "free list (%d):\n", free_list_needs_compacting);
  tmp = free_list;
  while (tmp != NULL)
    {
      fprintf (stderr, "  %p->(%p, %ld)\n", tmp, tmp->next, tmp->size);
      tmp = tmp->next;
    }

  sys = memory;
  fprintf (stderr, "system memory:\n");
  while (sys != NULL)
    {
      fprintf (stderr, "  %p - %p ->(%p)\n", sys, sys + chunk_size,
	       sys->next);
      sys = sys->next;
    }
}


/* free_list_insert_sorted
 * Insert NEW onto the free list, sorted numerically by address.
 */
void
free_list_insert_sorted (struct mem_header *new)
{
  struct mem_header *free_tmp = free_list;

  /* check for empty list */
  if (free_list == NULL)
    {
      free_list = new;
      free_list->next = NULL;
      return;
    }

  /* if NEW is the lowest address */
  if (new < free_tmp)
    {
      new->next = free_tmp;
      free_list = new;
      return;
    }

  /* general case - find the insertion point */
  while (free_tmp->next != NULL)
    {
      if (new < free_tmp->next) break;
      free_tmp = free_tmp->next;
    }

  new->next = free_tmp->next;
  free_tmp->next = new;
}


/* compact_free_list
 * Defragment memory by merging all adjacent free blocks.
 */
void
compact_free_list (void)
{
  struct mem_header *free_tmp = free_list;

  /* search through the free list for adjacent blocks - if two
     are adjacent, then merge them to create a larger block */
  while (free_tmp != NULL)
    {
      if (free_tmp->next == NULL) break; /* at the end of the list */

      /* if two free blocks are adjacent */
      if ((void *)free_tmp + free_tmp->size
	  + sizeof (struct mem_header) == (void *)free_tmp->next)
	{
	  /* merge them */
	  free_tmp->size += free_tmp->next->size
	    + sizeof (struct mem_header);
	  free_tmp->next = free_tmp->next->next;

	  continue; /* try again with this same block */
	}

      free_tmp = free_tmp->next;
    }

  free_list_needs_compacting = 0;
}

/* safe_malloc
 * A wrapper around malloc which never returns NULL.
 */
void *
safe_malloc (size_t amount)
{
  void *mem;

  mem = malloc (amount);

  if (mem == NULL) PANIC; /* Houston, we have a problem */

  /* keep stats */
  total_alloced += amount;

  return (mem);
}

/* mem_init
 * Called when xmalloc is first invoked.  Sets up the necessary
 * data structures.
 */
void
mem_init (void)
{
  /* set up stats */
  total_alloced = 0;
  xmalloc_calls = 0;
  xmalloc_bytes = 0;
  xfree_bytes = 0;

  /* set up the system list */
  memory = safe_malloc (chunk_size);
  memory->next = NULL;

  /* set up the free list */
  free_list = (void *)memory + sizeof (struct sys_block);
  free_list->size = chunk_size - sizeof (struct sys_block)
    - sizeof (struct mem_header);
  free_list->next = NULL;

  if (memory_trace)
    printf ("=== alloc'ed block (%p) ===\n", memory);
}


/* xmalloc
 * Allocate AMOUNT bytes of memory and return it with all of
 * its bytes set to 0x00.
 */
void *
xmalloc (size_t amount)
{
  struct mem_header *free_tmp, *last, *ret_block;
  struct sys_block *sys_temp;

  chunk_size = DEFAULT_CHUNK_SIZE;

  /* if more than the default chunk size was requested */
  if (amount > MAX_ALLOC_AMOUNT)
    chunk_size = amount + ALLOC_ADJUST;

  if (free_list == NULL && alloc_list == NULL) mem_init ();

  /* don't allocate less than MIN_ALLOC_AMOUNT */
  if (amount < MIN_ALLOC_AMOUNT)
    amount = MIN_ALLOC_AMOUNT;

  if (memory_trace)
    printf ("=== %d bytes requested ===\n", amount);

  /* keep stats */
  xmalloc_calls++;
  xmalloc_bytes += amount;


  /* loop until a block is found */
  while (1)
    {
      /* first walk the free list, looking for the correct size */
      last = NULL;
      free_tmp = free_list;

      while (free_tmp != NULL)
	{
	  if (free_tmp->size >= amount) goto GOT_FREE_BLOCK;

	  last = free_tmp;
	  free_tmp = free_tmp->next;
	}


      /* didn't find a free block of the right size
	 - try compacting the free list */
      if (free_list_needs_compacting)
	{
	  compact_free_list ();
	  continue;
	}


      /* if we got here, then we need to allocate a new chunk */

      /* find the last chunk */
      sys_temp = memory;
      while (sys_temp->next != NULL) sys_temp = sys_temp->next;

      /* alloc a new chunk and save its ptr */
      sys_temp->next = safe_malloc (chunk_size);
      sys_temp->next->next = NULL;

      if (memory_trace)
	printf ("=== alloc'ed block (%p) ===\n", sys_temp->next);

      /* create the new free block */
      free_tmp = (void *)sys_temp->next + sizeof (struct sys_block);
      free_tmp->next = NULL;
      free_tmp->size = chunk_size - ALLOC_ADJUST;

      /* put that bad boy in the free list */
      free_list_insert_sorted (free_tmp);

      /* with this new large chunk, try again */
    }

 GOT_FREE_BLOCK:
  /* remove the block from the free list */
  if (last == NULL)
    free_list = free_tmp->next;
  else
    last->next = free_tmp->next;

  ret_block = free_tmp;


  /* shrink the block, if possible */
  if (ret_block->size > amount + sizeof (struct mem_header) + MIN_ALLOC_AMOUNT)
    {
      struct mem_header *new = (void *)ret_block
	+ sizeof (struct mem_header) + amount;

      new->size = ret_block->size - sizeof (struct mem_header) - amount;
      new->next = NULL;
      ret_block->size = amount;

      free_list_insert_sorted (new);
    }

  /* put it on the alloc list */
  ret_block->next = alloc_list;
  alloc_list = ret_block;

  /* and (finally) return the memory */
  memset ((void *)ret_block + sizeof (struct mem_header), 0, amount);
  return ((void *)ret_block + sizeof (struct mem_header));
}

/* xfree
 * Add FREEMEM to the free list.
 */
void
xfree (void *freemem)
{
  struct mem_header *mem;
  struct mem_header *tmp = alloc_list, *last = NULL;

  if (freemem == NULL) return;

  mem = freemem - sizeof (struct mem_header);

  /* find FREEMEM on the alloc list */
  while (tmp != NULL)
    {
      if (tmp == mem) break;

      last = tmp;
      tmp = tmp->next;
    }

  /* sanity check */
  if (tmp == NULL)
    {
      fprintf (stderr,
	       "tried to free block %p (%p->(%p, %ld)) not on alloc list\n",
	       freemem, mem, mem->next, mem->size);

      if (memory_trace)
	mem_trace ();

      exit (EXIT_FAILURE);
    }

  /* keep stats */
  xfree_bytes += tmp->size;

  if (memory_trace)
    printf ("=== %ld byte block freed ===\n", tmp->size);

  /* remove from the alloc list */
  if (last == NULL)
    alloc_list = tmp->next;
  else
    last->next = tmp->next;

  /* put it on the free list */
  free_list_insert_sorted (mem);
  free_list_needs_compacting = 1;
}

/* free_all
 * Release all memory back to the OS.
 */
void
free_all (void)
{
  struct sys_block *temp;

  do
    {
      if (memory_trace)
	printf ("=== freeing %p ===\n", memory);

      temp = memory->next;
      free (memory);
      memory = temp;
    }
  while (memory != NULL);

  if (memory_trace)
    printf ("\n*** Stats ***\n"
	    "   %ld total bytes alloc'ed from the system\n"
	    "   %ld calls to xmalloc\n"
	    "   %ld total bytes alloc'ed\n"
	    "   %ld bytes freed\n",
	    total_alloced, xmalloc_calls, xmalloc_bytes, xfree_bytes);
}