/* 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);
}
