Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
2006-12-07 2g1520 OS
#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;
}
}
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment