2006-12-07 2g1520 OS

malloc.c

#include <stdio.h>
#include <unistd.h>
#include "malloc.h"


#define err(X,Y) (_err((X),(Y),(__LINE__)))

void ___msg(){}

static void _err(const char* str, unsigned int d, unsigned int line)
{
	fprintf(stderr,"**ERR: %s: %d, line %d\n",str,d,line);
	exit(1);
}

static size_t leaked_memory = 0;
static void report_leaked_memory(size_t leak)
{
	leaked_memory+=leak;
	MSG("Reporting %u bytes of leaked memory, total %u bytes missing\n",leak, leaked_memory);
}

static memoryblock* freelist = null;

static bool check_list()
{
	int l=0;
	memoryblock* start = freelist;
	MSG("Will now control integrity of free list.\n");

	if(start==null)
	{
		MSG("Free list is empty\n");
		return true;
	}
	/* this could keep going for a while if loop doesnt return to first node but to another node */
	while(true)
	{
	/*	MSG("list element %d, &%x, n:%x, p:%x, l:%u\n",l,(unsigned int)start,(unsigned int)start->next,(unsigned int)start->prev,start->length);*/
		l+=1;
		if(start->next->prev != start)
			return false;
		if(start->prev->next != start)
			return false;
		if(start->security != PASSIVE)
			return false;
		start = start->next;
		if(start==freelist)
			return true;
	}
}

static void add_block_to_freelist(memoryblock* mb)
{
	if(mb==null)
	{
		err("Trying to add null to freelist.",(unsigned int)mb);
		return;
	}

	if(mb->security!=ACTIVE)
	{
		err("Trying to add contaminated block.",(unsigned int)mb);;
		return;
	}

	mb->security=PASSIVE;

	if(freelist==null)
	{
		freelist=mb;
		mb->next = mb->prev = mb;
		return;
	}

	freelist->prev->next=mb;
	mb->prev=freelist->prev;
	mb->next=freelist;
	freelist->prev=mb;
}

static void* remove_block_from_freelist(memoryblock* mb)
{
	if(freelist==null)
	{
		err("Tried to remove block from empty list",(unsigned int)mb);
		return null;
	}

	if(mb->security != PASSIVE)
	{
		err("Block to be removed was contaminated",(unsigned int)mb);
		return null;
	}

	mb->security = ACTIVE;

	if(mb==mb->next)
	{
		freelist=null;
		return mb;
	}

	if(mb==freelist)
	{
		freelist=mb->next;
	}

	mb->next->prev = mb->prev;
	mb->prev->next = mb->next;

	return mb;
}

static void check_and_merge_blocks(memoryblock* mb1, memoryblock* mb2)
{
	char* one = (char*)mb1, * two = (char*)mb2;
	if( one + sizeof(Header) + mb1->length == two )
	{
		MSG("Merging block at %x with block at %x.\n",(unsigned int)mb1,(unsigned int) mb2);
		mb1->length+= (sizeof(Header) + mb2->length);
		if(remove_block_from_freelist(mb2) == null)
			return;
	}
}

static void merge_list()
{
	memoryblock* cmp1=freelist;
	MSG("Will now try merge any neighbour blocks in free list.\n");
	if(cmp1==null)return;
	if(cmp1==cmp1->next)return;

	do
	{
		memoryblock *cmp2=cmp1->next;
		do
		{
			check_and_merge_blocks(cmp1,cmp2);
			check_and_merge_blocks(cmp2,cmp1);

			cmp2=cmp2->next;
		}while(cmp2!=freelist);

		cmp1=cmp1->next;
	}while(cmp1!=freelist);
}

static memoryblock* requestmem(size_t length)
{
	void* new;
	long int allocated = ALLOCATE_AT_LEAST_THIS_MUCH_MEMORY;
	const int temp = length % sizeof(double);
	if(temp!=0)
		length+=sizeof(double)-temp;

	while(allocated < length+sizeof(Header))
	{
		allocated+=ALLOCATE_AT_LEAST_THIS_MUCH_MEMORY;
	}

	MSG("More memory was requested, will allocate %ld more memory\n",allocated);

	new = sbrk(allocated);

	if ((char *)new == (char *) -1)
	{
		err("sbrk returned error",0);
		return null;
	}
	else
	{
		memoryblock* n = (memoryblock*)new;
		n->length=allocated-sizeof(Header);
		n->security = ACTIVE;

		MSG("Success, will now insert new block into free list.\n");

		add_block_to_freelist(n);

		return n;
	}
}

#if STRATEGY==FIRSTFIT
static memoryblock* findfirst(size_t length)
{
	memoryblock* start= freelist;
	if(start==null)
		return null;
	MSG("Using strategy firstfit.\n");


	while(true)
	{
		if(start->length >= length)
			return start;
		start = start->next;
		if(start==freelist)
			return null;
	}
}
#endif

#if STRATEGY==BESTFIT || STRATEGY==QUICKFIT
static memoryblock* findbest(size_t length)
{
	memoryblock* start= freelist, *best=null;
	if(start==null)
		return null;
	MSG("Using strategy bestfit.\n");

	while(true)
	{
		if(start->length >= length)
		{
			if(start->length == length)
				return start;
			if(best==null)
				best=start;
			else if(start->length < best->length)
				best=start;
		}


		start = start->next;
		if(start==freelist)
			return best;
	}
}
#endif

#if STRATEGY==WORSTFIT
static memoryblock* findworst(size_t length)
{
	memoryblock* start= freelist, *worst=null;
	if(start==null)
		return null;

	MSG("Using strategy worstfit.\n");

	while(true)
	{
		if(start->length >= length)
		{
			/* maybe this isnt proper worstfit, but not doing this is just stupid */
			if(start->length == length)
				return start;

			if(worst==null)
				worst=start;
			else if(start->length > worst->length)
				worst=start;
		}


		start = start->next;
		if(start==freelist)
			return worst;
	}
}
#endif

#if STRATEGY == QUICKFIT
static memoryblock* quicklists[NRFREELISTS] = {null};
static memoryblock* split_block(memoryblock* old, size_t new_length)
{
	memoryblock* new;

	if(old->length < (sizeof(Header)+new_length+32))
	{
		return old;
	}

	new = (char*)old+(old->length-new_length);
	new->length=new_length;
	old->length-=new_length+sizeof(Header);
	return new;
}

static void fill_quicklists(size_t length)
{
	unsigned int i=0,val=16;
	memoryblock* r;
	if(length%sizeof(double)!=0)
		length+=sizeof(double)-(length%sizeof(double));
	r = requestmem(length);
	remove_block_from_freelist(r);

	while(true)
	for(i=0;val=16;i<NRFREELISTS && r->length>val;i+=1,val=val<<1)
	{
		memoryblock* r2 = split_block(r,val);
		if(r2==r)
		{
			add_block_to_freelist(r);
			return ;
		}
		r2->security=PASSIVE;
		if(quicklists[i]==null)
		{
			r2->next=r2->prev=r2;
			quicklists[i]=r2;
		}
		else
		{
			r2->prev=quicklists[i]->prev;
			r2->prev->next=quicklists[i]->prev=r2;
			r2->next=quicklists[i];
		}
	}
}

static memoryblock* findquick(size_t length)
{
	int i,val;
	MSG("Using strategy quickfit.\n");
	for(i=0,val=16;i<NRFREELISTS;i+=1,val=val<<1)
	{
		if(length<=val)
		{
			if(quicklists[i]==null)
				fill_quicklists(length);

			memoryblock* r = quicklists[i]->prev;
			if(r->security != PASSIVE)
			{
				err("Block to be removed was contaminated",(unsigned int)mb);
				return null;
			}
			r->security = ACTIVE;
			if(quicklists[i]==quicklists[i]->next)
			{
				quicklists[i]=null;
				return quicklists[i];
			}

			r->prev->next=quicklists[i];
			quicklists[i]->prev=r->prev;
			return r;
		}
	}

	return null;
}
#endif

void free(void* ptr)
{
	memoryblock * m = (memoryblock*)((char*)ptr-sizeof(Header));
	MSG("Free pointer %x\n",(unsigned int)ptr);
	if(ptr == null)
	{
		return;
	}

	if(m->security!=ACTIVE)
	{
		MSG("Validity check failed, block contaminated.\n");
/*		err("This blocks active was faulty, m",(unsigned int)m);*/
		report_leaked_memory(m->length+sizeof(Header));
		return;
	}

	MSG("Add block to free list.\n");

	add_block_to_freelist(m);

/* missar saker */
	merge_list();

	return;
}

void* malloc(size_t length)
{
	memoryblock * r;

	MSG("malloc was called with argument %d\n",length);

	if(length == 0)
		return null;
	if(!check_list())
	{
		err("free list is broken, pointer",(int)freelist);
		return null;
	}

r =

#if STRATEGY == FIRSTFIT
	findfirst
#elif STRATEGY == BESTFIT
	findbest
#elif STRATEGY == WORSTFIT
	findworst
#elif STRATEGY == QUICKFIT
	findquick
#endif

(length);


	MSG("Strategy returned %x\n",(unsigned int)r);

#if STRATEGY == QUICKFIT

	if(r==null)
	{
		r= findbest(length);
	}
	else return (void *)(((char*)r)+sizeof(Header));

#endif

	if(r==null)
		r = requestmem(length);

	if(r==null)
	{
		err("requested memory returned null pointer, length requested was ",length);
		return null;
	}


	remove_block_from_freelist(r);

	if( r->length == length )
	{
		/* perfect fit, return block as is*/
		return (void *)(((char*)r)+sizeof(Header));
	}
	else
	{
		size_t aligned_length = length;
		if(aligned_length%sizeof(double)!=0)
			aligned_length+=sizeof(double)-(aligned_length%sizeof(double));

		if( (r->length < aligned_length) || ((r->length - aligned_length) < 1+sizeof(Header)) )
		{
			/* then we have no room for further splits, give block as it is */
			/* waste is here r->length - length? */
			return (void *)(((char*)r)+sizeof(Header));
		}
		else
		{
			/* split block */
			memoryblock* n = (memoryblock*)(((char*)r) + aligned_length+sizeof(Header));
			n->length = ( r->length - aligned_length ) - sizeof(Header);
			n->security=ACTIVE;
			add_block_to_freelist(n);

			MSG("split block %x to %x | ol:%u l1:%u l2:%u\n",(unsigned int)r,(unsigned int)n,r->length,aligned_length,n->length);

			r->length = aligned_length;

			return (void *)(((char*)r)+sizeof(Header));
		}
	}
}

void* realloc(void* ptr, size_t length)
{
	int i;

	if(ptr == null)
	{
		return malloc(length);
	}
	else if(length==0)
	{
		free(ptr);
		return null;
	}
	else
	{
		char* one = (char*)ptr;
		memoryblock* mb = (memoryblock*)(((char*)ptr)-sizeof(Header));
		size_t wr_length = (mb->length < length ) ? mb->length : length;
		if(mb->length == length)
			return ptr;

		free(ptr);
		ptr = malloc(length);
		for(i=0;i<wr_length;i+=1)
			((char*)ptr)[i]=one[i];
		return ptr;
	}
}

malloc.h

#ifndef __MALLOC_H
#define __MALLOC_H


/* These should be given on command line to gcc */
/* If not, set these default values */

#ifndef STRATEGY
#define STRATEGY 4
#endif

#ifndef NRFREELISTS
#define NRFREELISTS 2
#endif

#ifndef MEMALLOC
/* undefined things may happen if this is lower than the sum of the blocksizes in the quicklists , or not divisible by sizeof(Header) */
#define MEMALLOC 8192
#endif

/*#define VERBOSE*/


/* Now define null and bool */

#ifndef NULL
#define NULL ( 0 )
#endif

#define null NULL


#define true ( 1 )
#define false ( 0 )


typedef signed int bool;

#ifndef _SIZE_T
#define _SIZE_T
typedef unsigned long size_t;
#endif



/* and some local macros */

#define FIRSTFIT 1
#define BESTFIT  2
#define WORSTFIT 3
#define QUICKFIT 4

#define ALLOCATE_AT_LEAST_THIS_MUCH_MEMORY MEMALLOC

#define ACTIVE 0xAAAAAAAA
/* 2863311530 */
/* 0xAAAAAAAA */
#define PASSIVE 0x55555555
/* 1431655765 */
/* 0x55555555 */

#ifdef VERBOSE
#define MSG printf
#else
#define MSG ___msg
#endif

/* and our doubly-linked-list memoryblock structs */

typedef struct
{
	double one;
	double two;
} Align;

typedef struct HEAD
{
	struct HEAD *	next;
	struct HEAD *	prev;
	size_t			length;
	unsigned int	security;
} Head;

typedef union
{
	Head  data;
	Align bytes_16;
} Block;



/* sizeof(Header) should be 16, which keeps alignment */
typedef Block Header;

/* easy access to internals */
typedef Head memoryblock;


#ifndef _SIZE_T
#define _SIZE_T
typedef unsigned long size_t;
#endif

void  free    ( void*         ) ;
void* malloc  ( size_t        ) ;
void* realloc ( void*, size_t ) ;

#endif