From 840cd1069292e3f29d18e57f2274ec1e979f858b Mon Sep 17 00:00:00 2001 From: Peter D'Hoye Date: Thu, 23 Jul 2009 21:37:35 +0000 Subject: Another pdbox patch by Wincent Balin (FS #10416): switch to using TLSF as memory allocator. Probably the last patch I commit for him, next changes are for him :) git-svn-id: svn://svn.rockbox.org/rockbox/trunk@22017 a1c6a512-1295-4272-9138-f99709370657 --- apps/plugins/pdbox/dbestfit-3.3/CHANGES | 12 - apps/plugins/pdbox/dbestfit-3.3/FILES | 15 - apps/plugins/pdbox/dbestfit-3.3/Makefile | 38 -- apps/plugins/pdbox/dbestfit-3.3/Malloc.c | 200 -------- apps/plugins/pdbox/dbestfit-3.3/README | 21 - apps/plugins/pdbox/dbestfit-3.3/bmalloc.c | 371 --------------- apps/plugins/pdbox/dbestfit-3.3/bmalloc.h | 5 - apps/plugins/pdbox/dbestfit-3.3/bysize.c | 428 ----------------- apps/plugins/pdbox/dbestfit-3.3/bysize.h | 4 - apps/plugins/pdbox/dbestfit-3.3/dmalloc.c | 711 ----------------------------- apps/plugins/pdbox/dbestfit-3.3/dmalloc.h | 12 - apps/plugins/pdbox/dbestfit-3.3/dmytest.c | 138 ------ apps/plugins/pdbox/dbestfit-3.3/malloc.man | 95 ---- apps/plugins/pdbox/dbestfit-3.3/mytest.c | 69 --- apps/plugins/pdbox/dbestfit-3.3/thoughts | 170 ------- 15 files changed, 2289 deletions(-) delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/CHANGES delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/FILES delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/Makefile delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/Malloc.c delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/README delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/bmalloc.c delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/bmalloc.h delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/bysize.c delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/bysize.h delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/dmalloc.c delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/dmalloc.h delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/dmytest.c delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/malloc.man delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/mytest.c delete mode 100644 apps/plugins/pdbox/dbestfit-3.3/thoughts (limited to 'apps/plugins/pdbox/dbestfit-3.3') diff --git a/apps/plugins/pdbox/dbestfit-3.3/CHANGES b/apps/plugins/pdbox/dbestfit-3.3/CHANGES deleted file mode 100644 index 7f63d384fa..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/CHANGES +++ /dev/null @@ -1,12 +0,0 @@ -Changes - -* (March 30 2005) Daniel - - Linus Nielsen Feltzing provided a patch that corrected several minor problems - that prevented dbestfit from working good. Linus also tested and timed - dbestfit for real in a target where he replaced the pSOS-provided memory - subsystem. - -* 3.2 - - Made eons ago, all older changes have been forgotten. diff --git a/apps/plugins/pdbox/dbestfit-3.3/FILES b/apps/plugins/pdbox/dbestfit-3.3/FILES deleted file mode 100644 index 6076c5fe20..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/FILES +++ /dev/null @@ -1,15 +0,0 @@ -/bysize.c -/bysize.h -/bmalloc.c -/bmalloc.h -/dmalloc.c -/dmalloc.h -/FILES -/README -/Makefile -/Malloc.c -/mytest.c -/dmytest.c -/thoughts -/malloc.man -/CHANGES diff --git a/apps/plugins/pdbox/dbestfit-3.3/Makefile b/apps/plugins/pdbox/dbestfit-3.3/Makefile deleted file mode 100644 index fc1e7e68d9..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/Makefile +++ /dev/null @@ -1,38 +0,0 @@ - -OBJS1 = bmalloc.o bysize.o mytest.o -TARGET1 = mytest - -OBJS2 = dmalloc.o bmalloc.o bysize.o Malloc.o -TARGET2 = mtest - -OBJS3 = dmalloc.o bmalloc.o bysize.o dmytest.o -TARGET3 = dmytest - -CFLAGS = -g -DUNIX -DBMALLOC -Wall -pedantic -DDEBUG -CC = gcc - -all: $(TARGET1) $(TARGET2) $(TARGET3) - -$(TARGET1): $(OBJS1) - $(CC) -g -o $(TARGET1) $(OBJS1) - -$(TARGET2): $(OBJS2) - $(CC) -g -o $(TARGET2) $(OBJS2) - -$(TARGET3): $(OBJS3) - $(CC) -g -o $(TARGET3) $(OBJS3) - -bmalloc.o: bmalloc.c -dmalloc.o: dmalloc.c -mytest.o: mytest.c -dmytest.o: dmytest.c -Malloc.o : Malloc.c -bysize.o : bysize.c - -tgz: - @(dir=`pwd`;name=`basename $$dir`;echo Creates $$name.tar.gz; cd .. ; \ - tar -cf $$name.tar `cat $$name/FILES | sed "s:^/:$$name/:g"` ; \ - gzip $$name.tar ; chmod a+r $$name.tar.gz ; mv $$name.tar.gz $$name/) - -clean: - rm -f *.o *~ $(TARGET1) $(TARGET2) $(TARGET3) diff --git a/apps/plugins/pdbox/dbestfit-3.3/Malloc.c b/apps/plugins/pdbox/dbestfit-3.3/Malloc.c deleted file mode 100644 index 10b02c94ec..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/Malloc.c +++ /dev/null @@ -1,200 +0,0 @@ -#include -#include -#include -#include - -/* Storleken på allokeringen bestäms genom att först slumpas en position i -"size_table" ut, sedan slumpas en storlek mellan den postionen och nästa värde -i tabellen. Genom att ha tabellen koncentrerad med låga värden, så skapas -flest såna. Rutinen håller på tills minnet en allokeringen nekas. Den kommer -aldrig att ha mer än MAXIMAL_MEMORY_TO_ALLOCATE allokerat samtidigt. Maximalt -har den MAX_ALLOCATIONS allokeringar samtidigt. - -Statistiskt sätt så kommer efter ett tag MAX_ALLOCATIONS/2 allokeringar finnas -samtidigt, med varje allokering i median med värdet av halva "size_table". - -När minnet är slut (malloc()=NULL), frågas användaren om han ska fortsätta. - -Med jämna mellanrum skrivs statisktik ut på skärmen. (DISPLAY_WHEN) - -För att stressa systemet med fler små allokeringar, så kan man öka -MAX_ALLOCATIONS. AMOUNT_OF_MEMORY bör få den att slå i taket fortare om man -minskar det. - -Ingen initiering görs av slumptalen, så allt är upprepbart (men plocka bort -kommentaren på srand() och det löser sig. - -*/ - -/*#undef BMALLOC*/ - -#ifdef BMALLOC -#include "dmalloc.h" - -#include "bmalloc.h" -#endif - -#define MAX_ALLOCATIONS 100000 -#define AMOUNT_OF_MEMORY 180000 /* bytes */ -#define MAXIMAL_MEMORY_TO_ALLOCATE 100000 /* Sätt den här högre än - AMOUNT_OF_MEMORY, och malloc() bör - returnera NULL förr eller senare */ - -#define DISPLAY_WHEN (123456) /* When to display statistic */ - -#define min(a, b) (((a) < (b)) ? (a) : (b)) -#define BOOL char -#define TRUE 1 -#define FALSE 0 - -typedef struct { - char *memory; - long size; - char filled_with; - long table_position; -} MallocStruct; - -/* -Skapar en lista med MAX_ALLOCATIONS storlek där det slumpvis allokeras -eller reallokeras i. -*/ - -MallocStruct my_mallocs[MAX_ALLOCATIONS]; - -long size_table[]={5,8,10,11,12,14,16,18,20,26,33,50,70,90,120,150,200,400,800,1000,2000,4000,8000,10000,11000,12000,13000,14000,15000,16000,17000,18000}; -#define TABLESIZE ((sizeof(size_table)-1)/sizeof(long)) -long size_allocs[TABLESIZE]; - -int main(void) -{ - int i; - long count=-1; - long count_free=0, count_malloc=0, count_realloc=0; - long total_memory=0; - BOOL out_of_memory=FALSE; - unsigned int seed = time( NULL ); - -#ifdef BMALLOC - void *thisisourheap; - thisisourheap = (malloc)(AMOUNT_OF_MEMORY); - if(!thisisourheap) - return -1; /* can't get memory */ - add_pool(thisisourheap, AMOUNT_OF_MEMORY); -#endif - - seed = 1109323906; - - srand( seed ); /* Initialize randomize */ - - printf("seed: %d\n", seed); - - while (!out_of_memory) { - long number=rand()%MAX_ALLOCATIONS; - long size; - long table_position=rand()%TABLESIZE; - char fill_with=rand()&255; - - count++; - - size=rand()%(size_table[table_position+1]-size_table[table_position])+size_table[table_position]; - -/* fprintf(stderr, "number %d size %d\n", number, size); */ - - if (my_mallocs[number].size) { /* Om allokering redan finns på den här - positionen, så reallokerar vi eller - friar. */ - long old_size=my_mallocs[number].size; - if (my_mallocs[number].size && fill_with<40) { - free(my_mallocs[number].memory); - total_memory -= my_mallocs[number].size; - count_free++; - size_allocs[my_mallocs[number].table_position]--; - size=0; - my_mallocs[number].size = 0; - my_mallocs[number].memory = NULL; - } else { - /* - * realloc() part - * - */ - char *temp; -#if 0 - if(my_mallocs[number].size > size) { - printf("*** %d is realloc()ed to %d\n", - my_mallocs[number].size, size); - } -#endif - if (total_memory-old_size+size>MAXIMAL_MEMORY_TO_ALLOCATE) - goto output; /* for-loop */ - temp = (char *)realloc(my_mallocs[number].memory, size); - if (!temp) - out_of_memory=TRUE; - else { - my_mallocs[number].memory = temp; - - my_mallocs[number].size=size; - size_allocs[my_mallocs[number].table_position]--; - size_allocs[table_position]++; - total_memory -= old_size; - total_memory += size; - old_size=min(old_size, size); - while (--old_size>0) { - if (my_mallocs[number].memory[old_size]!=my_mallocs[number].filled_with) - fprintf(stderr, "Wrong filling!\n"); - } - count_realloc++; - } - } - } else { - if (total_memory+size>MAXIMAL_MEMORY_TO_ALLOCATE) { - goto output; /* for-loop */ - } - my_mallocs[number].memory=(char *)malloc(size); /* Allokera! */ - if (!my_mallocs[number].memory) - out_of_memory=TRUE; - else { - size_allocs[table_position]++; - count_malloc++; - total_memory += size; - } - } - - if(!out_of_memory) { - my_mallocs[number].table_position=table_position; - my_mallocs[number].size=size; - my_mallocs[number].filled_with=fill_with; - memset(my_mallocs[number].memory, fill_with, size); - } - output: - if (out_of_memory || !(count%DISPLAY_WHEN)) { - printf("(%d) malloc %d, realloc %d, free %d, total size %d\n", count, count_malloc, count_realloc, count_free, total_memory); - { - int count; - printf("[size bytes]=[number of allocations]\n"); - for (count=0; count - - I wrote the dmalloc part for small allocation sizes to improve the behavior -of the built-in (first-fit) allocator found in pSOS (around 1996). - - I wrote the bmalloc part (best-fit with splay-tree sorting) just for the fun -of it and to see how good malloc() clone I could make. The quality of my -implementation is still left to be judged in real-world tests. - -TODO: - * Remove the final not-so-very-nice loop in dmalloc.c that checks for a block - with free fragments (when the list gets longer too much time might be spent - in that loop). - - * Add semaphore protection in bmalloc. - - * Make a separate application that samples the memory usage of a program - and is capable of replaying it (in order to test properly). diff --git a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c deleted file mode 100644 index f0ac7312a4..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c +++ /dev/null @@ -1,371 +0,0 @@ -/***************************************************************************** - * - * Big (best-fit) Memory Allocation - * - * Author: Daniel Stenberg - * Date: March 5, 1997 - * Version: 2.0 - * Email: Daniel.Stenberg@sth.frontec.se - * - * - * Read 'thoughts' for theories and details in implementation. - * - * Routines meant to replace the most low level functions of an Operting - * System - * - * v2.0 - * - Made all size-routines get moved out from this file. This way, the size - * functions can much more easily get replaced. - * - Improved how new memory blocks get added to the size-sorted list. When - * not adding new pools, there should never ever be any list traversing - * since all information is dynamically gathered. - * - ****************************************************************************/ - -#include -#include - -#include "bysize.h" - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -/* #define DEBUG */ - -#define BMEM_ALIGN 64 /* resolution */ - -#define BMEMERR_TOOSMALL -1 - -/* this struct will be stored in all CHUNKS and AREAS */ -struct BlockInfo { - struct BlockInfo *lower; /* previous block in memory (lower address) */ - struct BlockInfo *higher; /* next block in memory (higher address) */ - unsigned long info; /* 31 bits size: 1 bit free boolean */ -#define INFO_FREE 1 -#define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */ - - /* FREE+SIZE Could be written to use ordinary bitfields if using a smart - (like gcc) compiler in a manner like: - int size:31; - int free:1; - - The 'higher' pointer COULD be removed completely if the size is used as - an index to the higher one. This would then REQUIRE the entire memory - pool to be contiguous and it needs a 'terminating' "node" or an extra - flag that informs about the end of the list. - */ -}; - -/* the BLOCK list should be sorted in a lower to higher address order */ -struct BlockInfo *blockHead=NULL; /* nothing from the start */ - -void print_lists(void); - - -/*********************************************************************** - * - * remove_block() - * - * Remove the block from the address-sorted list. - * - ***********************************************************************/ - -void remove_block(struct BlockInfo *block) -{ - if(block->lower) - block->lower->higher = block->higher; - else - blockHead = block->higher; - if(block->higher) - block->higher->lower = block->lower; -} - -/**************************************************************************** - * - * add_blocktolists() - * - * Adds the specified block at the specified place in the address-sorted - * list and at the appropriate place in the size-sorted. - * - ***************************************************************************/ -void add_blocktolists(struct BlockInfo *block, - struct BlockInfo *newblock, - size_t newsize) -{ - struct BlockInfo *temp; /* temporary storage variable */ - if(block) { - /* `block' is now a lower address than 'newblock' */ - - /* - * Check if the new CHUNK is wall-to-wall with the lower addressed - * one (if *that* is free) - */ - if(block->info&INFO_FREE) { - if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) { - /* yes sir, this is our lower address neighbour, enlarge that one - pick it out from the list and recursively add that chunk and - then we escape */ - - /* remove from size-sorted list: */ - remove_chunksize((char*)block+sizeof(struct BlockInfo)); - - block->info += newsize; /* newsize is an even number and thus the FREE - bit is untouched */ - - remove_block(block); /* unlink the block address-wise */ - - /* recursively check our lower friend(s) */ - add_blocktolists(block->lower, block, block->info&INFO_SIZE); - return; - } - } - - temp = block->higher; - - block->higher = newblock; - newblock->lower = block; - newblock->higher = temp; - if(newblock->higher) - newblock->higher->lower = newblock; - } - else { - /* this block should preceed the heading one */ - temp = blockHead; - - /* check if this is our higher addressed neighbour */ - if((char *)newblock + newsize == (char *)temp) { - - /* yes, we are wall-to-wall with the higher CHUNK */ - if(temp->info&INFO_FREE) { - /* and the neighbour is even free, remove that one and enlarge - ourselves, call add_pool() recursively and then escape */ - - remove_block(temp); /* unlink 'temp' from list */ - - /* remove from size-sorted list: */ - remove_chunksize((char*)temp+sizeof(struct BlockInfo) ); - - /* add the upper block's size on ourselves */ - newsize += temp->info&INFO_SIZE; - - /* add the new, bigger block */ - add_blocktolists(block, newblock, newsize); - return; - } - } - - blockHead = newblock; - newblock->higher = temp; - newblock->lower = NULL; /* there is no lower one */ - if(newblock->higher) - newblock->higher->lower = newblock; - } - - newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the - FREE bit */ - insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize); -} - -/*********************************************************************** - * - * findblockbyaddr() - * - * Find the block that is just before the input block in memory. Returns NULL - * if none is. - * - ***********************************************************************/ - -static struct BlockInfo *findblockbyaddr(struct BlockInfo *block) -{ - struct BlockInfo *test = blockHead; - struct BlockInfo *lower = NULL; - - while(test && (test < block)) { - lower = test; - test = test->higher; - } - return lower; -} - -/*********************************************************************** - * - * add_pool() - * - * This function should be the absolutely first function to call. It sets up - * the memory bounds of the [first] CHUNK(s). It should be possible to call - * this function several times to add more CHUNKs to the pool of free - * memory. This allows the bmalloc system to deal with a non-contigous memory - * area. - * - * Returns non-zero if an error occured. The memory was not added then. - * - ***********************************************************************/ - -int add_pool(void *start, - size_t size) -{ - struct BlockInfo *newblock = (struct BlockInfo *)start; - struct BlockInfo *block; - - if(size < BMEM_ALIGN) - return BMEMERR_TOOSMALL; - - block = findblockbyaddr( newblock ); - /* `block' is now a lower address than 'newblock' or NULL */ - - if(size&1) - size--; /* only add even sizes */ - - add_blocktolists(block, newblock, size); - - return 0; -} - - -#ifdef DEBUG -static void bmalloc_failed(size_t size) -{ - printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size); - print_lists(); -} -#else -#define bmalloc_failed(x) -#endif - -#ifdef DEBUG -void print_lists() -{ - struct BlockInfo *block = blockHead; -#if 1 - printf("List of BLOCKS (in address order):\n"); - while(block) { - printf(" START %p END %p SIZE %ld FLAG %s\n", - (char *)block, - (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE, - (block->info&INFO_FREE)?"free":"used"); - block = block->higher; - } - printf("End of BLOCKS:\n"); -#endif - print_sizes(); -} -#endif /* DEBUG */ - -void *bmalloc(size_t size) -{ - void *mem; - -#ifdef DEBUG - { - static int count=0; - int realsize = size + sizeof(struct BlockInfo); - if(realsize%4096) - realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; - printf("%d bmalloc(%d) [%d]\n", count++, size, realsize); - } -#endif - - size += sizeof(struct BlockInfo); /* add memory for our header */ - - if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be - changed if the BLOCKSIZE is not 2^X ! */ - size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */ - - /* get a CHUNK from the list with this size */ - mem = obtainbysize ( size ); - if(mem) { - /* the memory block we have got is the "best-fit" and it is already - un-linked from the free list */ - - /* now do the math to get the proper block pointer */ - struct BlockInfo *block= (struct BlockInfo *) - ((char *)mem - sizeof(struct BlockInfo)); - - block->info &= ~INFO_FREE; - /* not free anymore */ - - if( size != (block->info&INFO_SIZE)) { - /* split this chunk into two pieces and return the one that fits us */ - size_t othersize = (block->info&INFO_SIZE) - size; - - if(othersize > BMEM_ALIGN) { - /* prevent losing small pieces of memory due to weird alignments - of the memory pool */ - - block->info = size; /* set new size (leave FREE bit cleared) */ - - /* Add the new chunk to the lists: */ - add_blocktolists(block, - (struct BlockInfo *)((char *)block + size), - othersize ); - } - } - - /* Return the memory our parent may use: */ - return (char *)block+sizeof(struct BlockInfo); - } - else { - bmalloc_failed(size); - return NULL; /* can't find any memory, fail hard */ - } - return NULL; -} - -void bfree(void *ptr) -{ - struct BlockInfo *block = (struct BlockInfo *) - ((char *)ptr - sizeof(struct BlockInfo)); - size_t size; - - /* setup our initial higher and lower pointers */ - struct BlockInfo *lower = block->lower; - struct BlockInfo *higher = block->higher; - -#ifdef DEBUG - static int freecount=0; - printf("%d bfree(%p)\n", freecount++, ptr); -#endif - - /* bind together lower addressed FREE CHUNKS */ - if(lower && (lower->info&INFO_FREE) && - ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) { - size = block->info&INFO_SIZE; /* original size */ - - /* remove from size-link: */ - remove_chunksize((char *)lower+sizeof(struct BlockInfo)); - - remove_block(block); /* unlink from address list */ - block = lower; /* new base area pointer */ - block->info += size; /* append the new size (the FREE bit - will remain untouched) */ - - lower = lower->lower; /* new lower pointer */ - } - /* bind together higher addressed FREE CHUNKS */ - if(higher && (higher->info&INFO_FREE) && - ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) { - /* append higher size, the FREE bit won't be affected */ - block->info += (higher->info&INFO_SIZE); - - /* unlink from size list: */ - remove_chunksize((char *)higher+sizeof(struct BlockInfo)); - remove_block(higher); /* unlink from address list */ - higher = higher->higher; /* the new higher link */ - block->higher = higher; /* new higher link */ - } - block->info |= INFO_FREE; /* consider this FREE! */ - - block->lower = lower; - block->higher = higher; - - insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE); - -#ifdef DEBUG - print_lists(); -#endif - -} diff --git a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h deleted file mode 100644 index ab7215af0a..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h +++ /dev/null @@ -1,5 +0,0 @@ -int add_pool(void *start, size_t size); -void print_lists(void); - -void *bmalloc(size_t size); -void bfree(void *ptr); diff --git a/apps/plugins/pdbox/dbestfit-3.3/bysize.c b/apps/plugins/pdbox/dbestfit-3.3/bysize.c deleted file mode 100644 index 8728e247b9..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/bysize.c +++ /dev/null @@ -1,428 +0,0 @@ -/***************************************************************************** - * - * Size-sorted list/tree functions. - * - * Author: Daniel Stenberg - * Date: March 7, 1997 - * Version: 2.0 - * Email: Daniel.Stenberg@sth.frontec.se - * - * - * v2.0 - * - Added SPLAY TREE functionality. - * - * Adds and removes CHUNKS from a list or tree. - * - ****************************************************************************/ - -#include -#include - -#define SPLAY /* we use the splay version as that is much faster */ - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -#ifndef SPLAY /* these routines are for the non-splay version */ - -struct ChunkInfo { - struct ChunkInfo *larger; - struct ChunkInfo *smaller; - size_t size; -}; - -/* the CHUNK list anchor */ -struct ChunkInfo *chunkHead=NULL; - -/*********************************************************************** - - findchunkbysize() - - Find the chunk that is smaller than the input size. Returns - NULL if none is. - - **********************************************************************/ - -static struct ChunkInfo *findchunkbysize(size_t size) -{ - struct ChunkInfo *test = chunkHead; - struct ChunkInfo *smaller = NULL; - while(test && (test->size < size)) { - smaller = test; - test = test->larger; - } - return smaller; -} - -/*********************************************************************** - - remove_chunksize() - - Remove the chunk from the size-sorted list. - ***********************************************************************/ - -void remove_chunksize(void *data) -{ - struct ChunkInfo *chunk = (struct ChunkInfo *)data; - if(chunk->smaller) - chunk->smaller->larger = chunk->larger; - else { - /* if this has no smaller, this is the head */ - chunkHead = chunk->larger; /* new head */ - } - if(chunk->larger) - chunk->larger->smaller = chunk->smaller; -} - -void insert_bysize(char *data, size_t size) -{ - struct ChunkInfo *newchunk = (struct ChunkInfo *)data; - struct ChunkInfo *chunk = findchunkbysize ( size ); - - newchunk->size = size; - - if(chunk) { - /* 'chunk' is smaller than size, append the new chunk ahead of this */ - newchunk->smaller = chunk; - newchunk->larger = chunk->larger; - if(chunk->larger) - chunk->larger->smaller = newchunk; - chunk->larger = newchunk; - } - else { - /* smallest CHUNK around, append first in the list */ - newchunk->larger = chunkHead; - newchunk->smaller = NULL; - - if(chunkHead) - chunkHead->smaller = newchunk; - chunkHead = newchunk; - } -} - -char *obtainbysize( size_t size) -{ - struct ChunkInfo *chunk = findchunkbysize( size ); - - if(!chunk) { - if(size <= (chunkHead->size)) - /* there is no smaller CHUNK, use the first one (if we fit within that) - */ - chunk = chunkHead; - } - else - /* we're on the last CHUNK that is smaller than requested, step onto - the bigger one */ - chunk = chunk->larger; - - if(chunk) { - remove_chunksize( chunk ); /* unlink size-wise */ - return (char *)chunk; - } - else - return NULL; -} - -void print_sizes(void) -{ - struct ChunkInfo *chunk = chunkHead; - printf("List of CHUNKS (in size order):\n"); -#if 1 - while(chunk) { - printf(" START %p END %p SIZE %d\n", - chunk, (char *)chunk+chunk->size, chunk->size); - chunk = chunk->larger; - } -#endif - printf("End of CHUNKS:\n"); -} - -#else /* Here follows all routines dealing with the SPLAY TREES */ - -typedef struct tree_node Tree; -struct tree_node { - Tree *smaller; /* smaller node */ - Tree *larger; /* larger node */ - Tree *same; /* points to a node with identical key */ - int key; /* the "sort" key */ -}; - -Tree *chunkHead = NULL; /* the root */ - -#define compare(i,j) ((i)-(j)) - -/* Set this to a key value that will *NEVER* appear otherwise */ -#define KEY_NOTUSED -1 - -/* - * Splay using the key i (which may or may not be in the tree.) The starting - * root is t. Weight fields are maintained. - */ -Tree * splay (int i, Tree *t) -{ - Tree N, *l, *r, *y; - int comp; - - if (t == NULL) - return t; - N.smaller = N.larger = NULL; - l = r = &N; - - for (;;) { - comp = compare(i, t->key); - if (comp < 0) { - if (t->smaller == NULL) - break; - if (compare(i, t->smaller->key) < 0) { - y = t->smaller; /* rotate smaller */ - t->smaller = y->larger; - y->larger = t; - - t = y; - if (t->smaller == NULL) - break; - } - r->smaller = t; /* link smaller */ - r = t; - t = t->smaller; - } - else if (comp > 0) { - if (t->larger == NULL) - break; - if (compare(i, t->larger->key) > 0) { - y = t->larger; /* rotate larger */ - t->larger = y->smaller; - y->smaller = t; - t = y; - if (t->larger == NULL) - break; - } - l->larger = t; /* link larger */ - l = t; - t = t->larger; - } - else { - break; - } - } - - l->larger = r->smaller = NULL; - - l->larger = t->smaller; /* assemble */ - r->smaller = t->larger; - t->smaller = N.larger; - t->larger = N.smaller; - - return t; -} - -/* Insert key i into the tree t. Return a pointer to the resulting tree or - NULL if something went wrong. */ -Tree *insert(int i, Tree *t, Tree *new) -{ - if (new == NULL) { - return t; - } - - if (t != NULL) { - t = splay(i,t); - if (compare(i, t->key)==0) { - /* it already exists one of this size */ - - new->same = t; - new->key = i; - new->smaller = t->smaller; - new->larger = t->larger; - - t->smaller = new; - t->key = KEY_NOTUSED; - - return new; /* new root node */ - } - } - - if (t == NULL) { - new->smaller = new->larger = NULL; - } - else if (compare(i, t->key) < 0) { - new->smaller = t->smaller; - new->larger = t; - t->smaller = NULL; - } - else { - new->larger = t->larger; - new->smaller = t; - t->larger = NULL; - } - new->key = i; - - new->same = NULL; /* no identical node (yet) */ - - return new; -} - -/* Finds and deletes the best-fit node from the tree. Return a pointer to the - resulting tree. best-fit means the smallest node that fits the requested - size. */ -Tree *removebestfit(int i, Tree *t, Tree **removed) -{ - Tree *x; - - if (t==NULL) - return NULL; - t = splay(i,t); - if(compare(i, t->key) > 0) { - /* too small node, try the larger chain */ - if(t->larger) - t=splay(t->larger->key, t); - else { - /* fail */ - *removed = NULL; - return t; - } - } - - if (compare(i, t->key) <= 0) { /* found it */ - - /* FIRST! Check if there is a list with identical sizes */ - x = t->same; - if(x) { - /* there is, pick one from the list */ - - /* 'x' is the new root node */ - - x->key = t->key; - x->larger = t->larger; - x->smaller = t->smaller; - *removed = t; - return x; /* new root */ - } - - if (t->smaller == NULL) { - x = t->larger; - } - else { - x = splay(i, t->smaller); - x->larger = t->larger; - } - *removed = t; - - return x; - } - else { - *removed = NULL; /* no match */ - return t; /* It wasn't there */ - } -} - - -/* Deletes the node we point out from the tree if it's there. Return a pointer - to the resulting tree. */ -Tree *removebyaddr(Tree *t, Tree *remove) -{ - Tree *x; - - if (!t || !remove) - return NULL; - - if(KEY_NOTUSED == remove->key) { - /* just unlink ourselves nice and quickly: */ - remove->smaller->same = remove->same; - if(remove->same) - remove->same->smaller = remove->smaller; - /* voila, we're done! */ - return t; - } - - t = splay(remove->key,t); - - /* Check if there is a list with identical sizes */ - - x = t->same; - if(x) { - /* 'x' is the new root node */ - - x->key = t->key; - x->larger = t->larger; - x->smaller = t->smaller; - - return x; /* new root */ - } - - /* Remove the actualy root node: */ - - if (t->smaller == NULL) { - x = t->larger; - } - else { - x = splay(remove->key, t->smaller); - x->larger = t->larger; - } - - return x; -} - -#ifdef DEBUG -int printtree(Tree * t, int d, char output) -{ - int distance=0; - Tree *node; - int i; - if (t == NULL) - return 0; - distance += printtree(t->larger, d+1, output); - for (i=0; ikey, i); - } - - for(node = t->same; node; node = node->same) { - distance += i; /* this has the same "virtual" distance */ - - if(output) - printf(" [+]"); - } - if(output) - puts(""); - - distance += i; - distance += printtree(t->smaller, d+1, output); - return distance; -} -#endif /* DEBUG */ - -/* Here follow the look-alike interface so that the tree-function names are - the same as the list-ones to enable easy interchange */ - -void remove_chunksize(void *data) -{ - chunkHead = removebyaddr(chunkHead, data); -} - -void insert_bysize(char *data, size_t size) -{ - chunkHead = insert(size, chunkHead, (Tree *)data); -} - -char *obtainbysize( size_t size) -{ - Tree *receive; - chunkHead = removebestfit(size, chunkHead, &receive); - return (char *)receive; -} - -#ifdef DEBUG -void print_sizes(void) -{ - printtree(chunkHead, 0, 1); -} -#endif /* DEBUG */ - -#endif diff --git a/apps/plugins/pdbox/dbestfit-3.3/bysize.h b/apps/plugins/pdbox/dbestfit-3.3/bysize.h deleted file mode 100644 index 877e2ea4c5..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/bysize.h +++ /dev/null @@ -1,4 +0,0 @@ -void remove_chunksize(void *data); -void insert_bysize(char *data, size_t size); -char *obtainbysize( size_t size); -void print_sizes(void); diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c deleted file mode 100644 index b46d4af926..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c +++ /dev/null @@ -1,711 +0,0 @@ -/***************************************************************************** - * - * Dynamic Memory Allocation - * - * Author: Daniel Stenberg - * Date: March 10, 1997 - * Version: 2.3 - * Email: Daniel.Stenberg@sth.frontec.se - * - * - * Read 'thoughts' for theories and details of this implementation. - * - * v2.1 - * - I once again managed to gain some memory. BLOCK allocations now only use - * a 4 bytes header (instead of previos 8) just as FRAGMENTS. - * - * v2.2 - * - Re-adjusted the fragment sizes to better fit into the somewhat larger - * block. - * - * v2.3 - * - Made realloc(NULL, size) work as it should. Which is like a malloc(size) - * - *****************************************************************************/ - -#ifdef ROCKBOX -#include "plugin.h" -#define memset rb->memset -#define memcpy rb->memcpy -#else /* ROCKBOX */ -#include -#include -#endif /* ROCKBOX */ - -#ifdef DEBUG -#include -#endif - -#ifdef PSOS -#include -#define SEMAPHORE /* the PSOS routines use semaphore protection */ -#else -#include /* makes the PSOS complain on the 'size_t' typedef */ -#endif - -#ifdef BMALLOC -#include "bmalloc.h" -#endif - -/* Each TOP takes care of a chain of BLOCKS */ -struct MemTop { - struct MemBlock *chain; /* pointer to the BLOCK chain */ - long nfree; /* total number of free FRAGMENTS in the chain */ - short nmax; /* total number of FRAGMENTS in this kind of BLOCK */ - size_t fragsize; /* the size of each FRAGMENT */ - -#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */ - long semaphore_id; /* semaphore used to lock this particular list */ -#endif - -}; - -/* Each BLOCK takes care of an amount of FRAGMENTS */ -struct MemBlock { - struct MemTop *top; /* our TOP struct */ - struct MemBlock *next; /* next BLOCK */ - struct MemBlock *prev; /* prev BLOCK */ - - struct MemFrag *first; /* the first free FRAGMENT in this block */ - - short nfree; /* number of free FRAGMENTS in this BLOCK */ -}; - -/* This is the data kept in all _free_ FRAGMENTS */ -struct MemFrag { - struct MemFrag *next; /* next free FRAGMENT */ - struct MemFrag *prev; /* prev free FRAGMENT */ -}; - -/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this - to the allocation size first thing in the ALLOC function to make room for - this smoothly. */ - -struct MemInfo { - void *block; - /* which BLOCK is our father, if BLOCK_BIT is set it means this is a - stand-alone, large allocation and then the rest of the bits should be - treated as the size of the block */ -#define BLOCK_BIT 1 -}; - -/* ---------------------------------------------------------------------- */ -/* Defines */ -/* ---------------------------------------------------------------------- */ - -#ifdef DEBUG -#define MEMINCR(addr,x) memchange(addr, x) -#define MEMDECR(addr,x) memchange(addr,-(x)) -#else -#define MEMINCR(a,x) -#define MEMDECR(a,x) -#endif - -/* The low level functions used to get memory from the OS and to return memory - to the OS, we may also define a stub that does the actual allocation and - free, these are the defined function names used in the dmalloc system - anyway: */ -#ifdef PSOS - -#ifdef DEBUG -#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size) -#define DMEM_OSFREEMEM(x) dbgfree(x) -#else -#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer) -/* Similar, but this returns the memory */ -#define DMEM_OSFREEMEM(x) rn_retseg(0, x) -#endif - -/* Argument: */ -#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0) -/* Argument: */ -#define SEMAPHORERETURN(x) sm_v(x) -/* Argument: */ -#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y)) - -#else -#ifdef BMALLOC /* use our own big-memory-allocation system */ -#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size) -#define DMEM_OSFREEMEM(x) bfree(x) -#elif DEBUG -#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size) -#define DMEM_OSFREEMEM(x) dbgfree(x) -#else -#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size) -#define DMEM_OSFREEMEM(x) free(x) -#endif -#endif - - -/* the largest memory allocation that is made a FRAGMENT: (grab the highest - number from the list below) */ -#define DMEM_LARGESTSIZE 2032 - -/* The total size of a BLOCK used for FRAGMENTS - In order to make this use only *1* even alignment from the big-block- - allocation-system (possible the bmalloc() system also written by me) - we need to subtract the [maximum] struct sizes that could get added all - the way through to the grab from the memory. */ -#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */ - -/* Since the blocksize isn't an even 2^X story anymore, we make a table with - the FRAGMENT sizes and amounts that fills up a BLOCK nicely */ - -/* a little 'bc' script that helps us maximize the usage: - - for 32-bit aligned addresses (SPARC crashes otherwise): - for(i=20; i<2040; i++) { a=4064/i; if(a*i >= 4060) { if(i%4==0) {i;} } } - - - I try to approximate a double of each size, starting with ~20. We don't do - ODD sizes since several CPU flavours dump core when accessing such - addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain - happy with us. - */ - -#if defined(BIGBLOCKS) && BIGBLOCKS==4060 /* previously */ -#ifdef ROCKBOX -unsigned -#endif /* ROCKBOX */ -short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 }; -#else -#ifdef ROCKBOX -unsigned -#endif /* ROCKBOX */ -short qinfo[]= { 20, 28, 52, 116, 312, 580, 1016, 2032}; -/* 52 and 312 only make use of 4056 bytes, but without them there are too - wide gaps */ -#endif - -#ifndef ROCKBOX -#define MIN(x,y) ((x)<(y)?(x):(y)) -#endif /* ROCKBOX */ - -/* ---------------------------------------------------------------------- */ -/* Globals */ -/* ---------------------------------------------------------------------- */ - -/* keeper of the chain of BLOCKS */ -static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ]; - -/* are we experienced? */ -static char initialized = 0; - -/* ---------------------------------------------------------------------- */ -/* Start of the real code */ -/* ---------------------------------------------------------------------- */ - -#ifdef DEBUG -/************ - * A few functions that are verbose and tells us about the current status - * of the dmalloc system - ***********/ - -static void dmalloc_status() -{ - int i; - int used; - int num; - int totalfree=0; - struct MemBlock *block; - for(i=0; infree; - num++; - block = block->next; - } - printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n", - i, top[i].fragsize, used, top[i].nfree, - top[i].nfree*top[i].fragsize, num); - totalfree += top[i].nfree*top[i].fragsize; - } - printf("Total unused memory stolen by dmalloc: %d\n", totalfree); -} - -static void dmalloc_failed(size_t size) -{ - printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size); - dmalloc_status(); -} -#else -#define dmalloc_failed(x) -#endif - -#ifdef DEBUG - -#define BORDER 1200 - -void *dbgmalloc(int size) -{ - char *mem; - size += BORDER; -#ifdef PSOS - rn_getseg(0,size,RN_NOWAIT,0,(void **)&mem); -#else - mem = malloc(size); -#endif - if(mem) { - memset(mem, 0xaa, BORDER/2); - memset(mem+BORDER/2, 0xbb, size -BORDER); - memset(mem-BORDER/2+size, 0xcc, BORDER/2); - *(long *)mem = size; - mem += (BORDER/2); - } - printf("OSmalloc(%p)\n", mem); - return (void *)mem; -} - -void checkmem(char *ptr) -{ - int i; - long size; - ptr -= BORDER/2; - - for(i=4; i<(BORDER/2); i++) - if((unsigned char)ptr[i] != 0xaa) { - printf("########### ALERT ALERT\n"); - break; - } - size = *(long *)ptr; - for(i=size-1; i>=(size - BORDER/2); i--) - if((unsigned char)ptr[i] != 0xcc) { - printf("********* POST ALERT\n"); - break; - } -} - -void dbgfree(char *ptr) -{ - long size; - checkmem(ptr); - ptr -= BORDER/2; - size = *(long *)ptr; - - printf("OSfree(%ld)\n", size); -#ifdef PSOS - rn_retseg(0, ptr); -#else - free(ptr); -#endif -} - - -#define DBG(x) syslog x - -void syslog(char *fmt, ...) -{ - va_list ap; - va_start(ap, fmt); - vfprintf(stdout, fmt, ap); - va_end(ap); -} - -void memchange(void *a, int x) -{ - static int memory=0; - static int count=0; - static int max=0; - if(memory > max) - max = memory; - memory += x; - DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max)); -} -#else -#define DBG(x) -#endif - -/**************************************************************************** - * - * FragBlock() - * - * This function makes FRAGMENTS of the BLOCK sent as argument. - * - ***************************************************************************/ - -static void FragBlock(char *memp, int size) -{ - struct MemFrag *frag=(struct MemFrag *)memp; - struct MemFrag *prev=NULL; /* no previous in the first round */ - int count=0; - while((count+size) <= DMEM_BLOCKSIZE) { - memp += size; - frag->next = (struct MemFrag *)memp; - frag->prev = prev; - prev = frag; - frag = frag->next; - count += size; - } - prev->next = NULL; /* the last one has no next struct */ -} - -/*************************************************************************** - * - * initialize(); - * - * Called in the first dmalloc(). Inits a few memory things. - * - **************************************************************************/ -static void initialize(void) -{ -#ifdef ROCKBOX - unsigned -#endif /* ROCKBOX */ - int i; - /* Setup the nmax and fragsize fields of the top structs */ - for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) { - top[i].fragsize = qinfo[i]; - top[i].nmax = DMEM_BLOCKSIZE/qinfo[i]; - -#ifdef PSOS - /* for some reason, these aren't nulled from start: */ - top[i].chain = NULL; /* no BLOCKS */ - top[i].nfree = 0; /* no FRAGMENTS */ -#endif -#ifdef SEMAPHORE - { - char name[7]; - sprintf(name, "MEM%d", i); - SEMAPHORECREATE(name, top[i].semaphore_id); - /* doesn't matter if it failed, we continue anyway ;-( */ - } -#endif - } - initialized = 1; -} - -/**************************************************************************** - * - * FragFromBlock() - * - * This should return a fragment from the block and mark it as used - * accordingly. - * - ***************************************************************************/ - -static void *FragFromBlock(struct MemBlock *block) -{ - /* make frag point to the first free FRAGMENT */ - struct MemFrag *frag = block->first; - struct MemInfo *mem = (struct MemInfo *)frag; - - /* - * Remove the FRAGMENT from the list and decrease the free counters. - */ - block->first = frag->next; /* new first free FRAGMENT */ - - block->nfree--; /* BLOCK counter */ - block->top->nfree--; /* TOP counter */ - - /* heal the FRAGMENT list */ - if(frag->prev) { - frag->prev->next = frag->next; - } - if(frag->next) { - frag->next->prev = frag->prev; - } - mem->block = block; /* no block bit set here */ - - return ((char *)mem)+sizeof(struct MemInfo); -} - -/*************************************************************************** - * - * dmalloc() - * - * This needs no explanation. A malloc() look-alike. - * - **************************************************************************/ - -void *dmalloc(size_t size) -{ - void *mem; - - DBG(("dmalloc(%d)\n", size)); - - if(!initialized) - initialize(); - - /* First, we make room for the space needed in every allocation */ - size += sizeof(struct MemInfo); - - if(size < DMEM_LARGESTSIZE) { - /* get a FRAGMENT */ - - struct MemBlock *block=NULL; /* SAFE */ - struct MemBlock *newblock=NULL; /* SAFE */ - struct MemTop *memtop=NULL; /* SAFE */ - - /* Determine which queue to use */ -#ifdef ROCKBOX - unsigned -#endif /* ROCKBOX */ - int queue; - - for(queue=0; size > qinfo[queue]; queue++) - ; - do { - /* This is the head master of our chain: */ - memtop = &top[queue]; - - DBG(("Top info: %p %d %d %d\n", - memtop->chain, - memtop->nfree, - memtop->nmax, - memtop->fragsize)); - -#ifdef SEMAPHORE - if(SEMAPHOREOBTAIN(memtop->semaphore_id)) - return NULL; /* failed somehow */ -#endif - - /* get the first BLOCK in the chain */ - block = memtop->chain; - - /* check if we have a free FRAGMENT */ - if(memtop->nfree) { - /* there exists a free FRAGMENT in this chain */ - - /* I WANT THIS LOOP OUT OF HERE! */ - - /* search for the free FRAGMENT */ - while(!block->nfree) - block = block->next; /* check next BLOCK */ - - /* - * Now 'block' is the first BLOCK with a free FRAGMENT - */ - - mem = FragFromBlock(block); - - } - else { - /* we do *not* have a free FRAGMENT but need to get us a new BLOCK */ - - DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock), - newblock, - struct MemBlock *); - if(!newblock) { - if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) { - /* There are queues for bigger FRAGMENTS that we should check - before we fail this for real */ -#ifdef DEBUG - printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue); -#endif - mem = NULL; - } - else { - dmalloc_failed(size- sizeof(struct MemInfo)); - return NULL; /* not enough memory */ - } - } - else { - /* allocation of big BLOCK was successful */ - - MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock)); - - memtop->chain = newblock; /* attach this BLOCK to the chain */ - newblock->next = block; /* point to the previous first BLOCK */ - if(block) - block->prev = newblock; /* point back on this new BLOCK */ - newblock->prev = NULL; /* no previous */ - newblock->top = memtop; /* our head master */ - - /* point to the new first FRAGMENT */ - newblock->first = (struct MemFrag *) - ((char *)newblock+sizeof(struct MemBlock)); - - /* create FRAGMENTS of the BLOCK: */ - FragBlock((char *)newblock->first, memtop->fragsize); - -#if defined(DEBUG) && !defined(BMALLOC) - checkmem((char *)newblock); -#endif - - /* fix the nfree counters */ - newblock->nfree = memtop->nmax; - memtop->nfree += memtop->nmax; - - /* get a FRAGMENT from the BLOCK */ - mem = FragFromBlock(newblock); - } - } -#ifdef SEMAPHORE - SEMAPHORERETURN(memtop->semaphore_id); /* let it go */ -#endif - } while(NULL == mem); /* if we should retry a larger FRAGMENT */ - } - else { - /* get a stand-alone BLOCK */ - struct MemInfo *meminfo; - - if(size&1) - /* don't leave this with an odd size since we'll use that bit for - information */ - size++; - - DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *); - - if(meminfo) { - MEMINCR(meminfo, size); - meminfo->block = (void *)(size|BLOCK_BIT); - mem = (char *)meminfo + sizeof(struct MemInfo); - } - else { - dmalloc_failed(size); - mem = NULL; - } - } - return (void *)mem; -} - -/*************************************************************************** - * - * dfree() - * - * This needs no explanation. A free() look-alike. - * - **************************************************************************/ - -void dfree(void *memp) -{ - struct MemInfo *meminfo = (struct MemInfo *) - ((char *)memp- sizeof(struct MemInfo)); - - DBG(("dfree(%p)\n", memp)); - - if(!((size_t)meminfo->block&BLOCK_BIT)) { - /* this is a FRAGMENT we have to deal with */ - - struct MemBlock *block=meminfo->block; - struct MemTop *memtop = block->top; - -#ifdef SEMAPHORE - SEMAPHOREOBTAIN(memtop->semaphore_id); -#endif - - /* increase counters */ - block->nfree++; - memtop->nfree++; - - /* is this BLOCK completely empty now? */ - if(block->nfree == memtop->nmax) { - /* yes, return the BLOCK to the system */ - if(block->prev) - block->prev->next = block->next; - else - memtop->chain = block->next; - if(block->next) - block->next->prev = block->prev; - - memtop->nfree -= memtop->nmax; /* total counter subtraction */ - MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock)); - DMEM_OSFREEMEM((void *)block); /* return the whole block */ - } - else { - /* there are still used FRAGMENTS in the BLOCK, link this one - into the chain of free ones */ - struct MemFrag *frag = (struct MemFrag *)meminfo; - frag->prev = NULL; - frag->next = block->first; - if(block->first) - block->first->prev = frag; - block->first = frag; - } -#ifdef SEMAPHORE - SEMAPHORERETURN(memtop->semaphore_id); -#endif - } - else { - /* big stand-alone block, just give it back to the OS: */ - MEMDECR(&meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */ - DMEM_OSFREEMEM((void *)meminfo); - } -} - -/*************************************************************************** - * - * drealloc() - * - * This needs no explanation. A realloc() look-alike. - * - **************************************************************************/ - -void *drealloc(char *ptr, size_t size) -{ - struct MemInfo *meminfo = (struct MemInfo *) - ((char *)ptr- sizeof(struct MemInfo)); - /* - * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - * NOTE: the ->size field of the meminfo will now contain the MemInfo - * struct size too! - * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - */ - void *mem=NULL; /* SAFE */ - size_t prevsize = 0; - - /* NOTE that this is only valid if BLOCK_BIT isn't set: */ - struct MemBlock *block; - - DBG(("drealloc(%p, %d)\n", ptr, size)); - - if(NULL == ptr) - return dmalloc( size ); - - block = meminfo->block; - - if(!((size_t)meminfo->block&BLOCK_BIT) && - (size + sizeof(struct MemInfo) < - (prevsize = block->top->fragsize) )) { - /* This is a FRAGMENT and new size is possible to retain within the same - FRAGMENT */ - if((prevsize > qinfo[0]) && - /* this is not the smallest memory Q */ - (size < (block->top-1)->fragsize)) - /* this fits in a smaller Q */ - ; - else - mem = ptr; /* Just return the same pointer as we got in. */ - } - if(!mem) { - /* This is a stand-alone BLOCK or a realloc that no longer fits within - the same FRAGMENT */ - - if((size_t)meminfo->block&BLOCK_BIT) { - prevsize = ((size_t)meminfo->block&~BLOCK_BIT) - - sizeof(struct MemInfo); - } - else - prevsize -= sizeof(struct MemInfo); - - /* No tricks involved here, just grab a new bite of memory, copy the data - * from the old place and free the old memory again. */ - mem = dmalloc(size); - if(mem) { - memcpy(mem, ptr, MIN(size, prevsize) ); - dfree(ptr); - } - } - return mem; -} - -/*************************************************************************** - * - * dcalloc() - * - * This needs no explanation. A calloc() look-alike. - * - **************************************************************************/ -/* Allocate an array of NMEMB elements each SIZE bytes long. - The entire array is initialized to zeros. */ -void * -dcalloc (size_t nmemb, size_t size) -{ - void *result = dmalloc (nmemb * size); - - if (result != NULL) - memset (result, 0, nmemb * size); - - return result; -} diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h deleted file mode 100644 index 6a0c993815..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h +++ /dev/null @@ -1,12 +0,0 @@ -void *dmalloc(size_t); -void dfree(void *); -void *drealloc(void *, size_t); - -#define malloc(x) dmalloc(x) -#define free(x) dfree(x) -#define realloc(x,y) drealloc(x,y) - -#ifdef ROCKBOX -void *dcalloc(size_t, size_t); -#define calloc(x,y) dcalloc(x,y) -#endif diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmytest.c b/apps/plugins/pdbox/dbestfit-3.3/dmytest.c deleted file mode 100644 index ed12686b3d..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/dmytest.c +++ /dev/null @@ -1,138 +0,0 @@ -#include -#include - -#include "dmalloc.h" - -#define MAX 500 -#define MAX2 1000 -#define MAXC 2 - -#define TESTA -#define TESTB -#define TESTC -#define TESTD - -int main(int argc, char **argv) -{ - int i; - int memory = 0; - -#ifdef BMALLOC -#define HEAP 10000 - void *heap = (malloc)(HEAP); - if(!heap) - return -1; - add_pool(heap, HEAP); -#endif - - { -#define MAXK 100 - void *wow[MAXK]; - wow[0]=malloc(700); - realloc(wow[0], 680); - return 0; - - for(i=0; i=0; i-=2) - free(wow[i]); - return 0; - } - - -#ifdef TESTD - { -#define MAXS 10 -#define MAXS1 0 - void *ptr[MAXS]; - - for(i=MAXS1; i< MAXS; i++) { - printf("%d malloc(%d)\n", i, i*55); - ptr[i] = malloc (i*55); - } - for(i=MAXS1; i< MAXS; i++) { - void *tmp; - printf("%d realloc(%d)\n", i, i*155); - tmp=realloc(ptr[i], i*155); - if(tmp) - ptr[i] = tmp; - } - for(i=MAXS1; i< MAXS; i++) { - printf("%d free(%d)\n", i, i*155); - free(ptr[i]); - } - } -#endif - -#ifdef TESTC - { - void *ptr[MAXC]; - printf("This is test C:\n"); - - for(i=0; i< MAXC; i++) { - printf("%d malloc(100)\n", i+1); - ptr[i] = malloc(100); - printf(" ...returned %p\n", ptr[i]); - } - - for(i=0; i< MAXC; i++) { - printf("%d free()\n", i+1); - free(ptr[i]); - } - - printf("End of test C:\n"); - } -#endif - -#ifdef TESTA - { - void *pointers[MAX]; - printf("This is test I:\n"); - - for(i=0; i - - void *malloc(size) - size_t size; - - void free(ptr) - void *ptr; - - void *realloc(ptr, size) - void *ptr; - size_t size; - - void *calloc(nelem, elsize) - size_t nelem; - size_t elsize; - -DESCRIPTION - These routines provide a general-purpose memory allocation - package. They maintain a table of free blocks for efficient - allocation and coalescing of free storage. When there is no - suitable space already free, the allocation routines call - rn_getseg() to get more memory from the system. - - Each of the allocation routines returns a pointer to space - suitably aligned for storage of any type of object. Each - returns a NULL pointer if the request cannot be completed - (see DIAGNOSTICS). - - malloc() returns a pointer to a block of at least size - bytes, which is appropriately aligned. - - free() releases a previously allocated block. Its argument - is a pointer to a block previously allocated by malloc(), - calloc() or realloc(). - - realloc() changes the size of the block referenced by ptr to - size bytes and returns a pointer to the (possibly moved) - block. The contents will be unchanged up to the lesser of - the new and old sizes. If unable to honor a reallocation - request, realloc() leaves its first argument unaltered. - - **** DMALLOC DOES NOT COMPLY WITH THE PARAGRAPH BELOW **** - - For backwards compatibility, realloc() accepts a pointer to a - block freed since the most recent call to malloc(), cal- - loc() or realloc(). - - Note: using realloc() with a block freed before the most recent - call to malloc(), calloc() or realloc() is an error. - - calloc() uses malloc() to allocate space for an array of - nelem elements of size elsize, initializes the space to - zeros, and returns a pointer to the initialized block. The - block should be freed with free(). - - - malloc() and realloc() return a non- NULL pointer if size is 0, - and calloc() returns a non-NULL pointer if nelem or elsize is 0, - but these pointers should not be dereferenced. - - Note: Always cast the value returned by malloc(), realloc() or - calloc(). - - -RETURN VALUES On success, malloc(), calloc() and realloc() return a - pointer to space suitably aligned for storage of any type of - object. On failure, they return NULL. - - free() does not return a value. - - -NOTES - Because malloc() and realloc() return a non-NULL pointer if size - is 0, and calloc() returns a non-NULL pointer if nelem or elsize - is 0, a zero size need not be treated as a special case if it - should be passed to these functions unpredictably. Also, the - pointer returned by these functions may be passed to subsequent - invocations of realloc(). - - -BUGS - - **** DMALLOC DOES NOT COMPLY WITH THE PARAGRAPH BELOW **** - - Since realloc() accepts a pointer to a block freed since the last - call to malloc(), calloc() or realloc(), a degradation of - performance results. The semantics of free() should be changed - so that the contents of a previously freed block are undefined. diff --git a/apps/plugins/pdbox/dbestfit-3.3/mytest.c b/apps/plugins/pdbox/dbestfit-3.3/mytest.c deleted file mode 100644 index 80407dee00..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/mytest.c +++ /dev/null @@ -1,69 +0,0 @@ -#include -#include - -#include "bmalloc.h" - -int main(int argc, char **argv) -{ - void *pointers[5]; - int i; - void *area; - - for(i=0; i<5; i++) - pointers[i] = malloc(8000); - - if(argc>1) { - switch(argv[1][0]) { - case '1': - for(i=0; i<5; i++) { - add_pool(pointers[i], 4000); - add_pool((char *)pointers[i]+4000, 4000); - } - break; - case '2': - area = malloc(20000); - add_pool(area, 3000); - add_pool((char *)area+6000, 3000); - add_pool((char *)area+3000, 3000); - add_pool((char *)area+12000, 3000); - add_pool((char *)area+9000, 3000); - break; - case '3': - { - void *ptr[10]; - area = malloc(20000); - add_pool(area, 20000); - - printf(" ** TEST USAGE\n"); - for(i=0; i<9; i++) - ptr[i]=bmalloc(200); - print_lists(); - for(i=0; i<9; i++) - bfree(ptr[i]); - printf(" ** END OF TEST USAGE\n"); - } - - break; - case '4': - { - void *ptr[10]; - area = malloc(20000); - add_pool(area, 20000); - - ptr[0]=bmalloc(4080); - print_lists(); - bfree(ptr[0]); - printf(" ** END OF TEST USAGE\n"); - } - - break; - } - } - else - for(i=4; i>=0; i--) - add_pool(pointers[i], 8000-i*100); - - print_lists(); - - return 0; -} diff --git a/apps/plugins/pdbox/dbestfit-3.3/thoughts b/apps/plugins/pdbox/dbestfit-3.3/thoughts deleted file mode 100644 index d509d36d2a..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/thoughts +++ /dev/null @@ -1,170 +0,0 @@ - ===================================== - Memory Allocation Algorithm Theories. - ===================================== - -GOAL - It is intended to be a 100% working memory allocation system. It should be - capable of replacing an ordinary Operating System's own routines. It should - work good in a multitasking, shared memory, non-virtual memory environment - without clogging the memory. Primary aimed for small machines, CPUs and - memory amounts. - - I use a best-fit algorithm with a slight overhead in order to increase speed - a lot. It should remain scalable and work good with very large amount of - memory and free/used memory blocks too. - -TERMINOLOGY - - FRAGMENT - small identically sized parts of a larger BLOCK, they are when - travered in lists etc _not_ allocated. - BLOCK - large memory area, if used for FRAGMENTS, they are linked in a - lists. One list for each FRAGMENT size supported. - TOP - head struct that holds information about and points to a chain - of BLOCKS for a particular FRAGMENT size. - CHUNK - a contiguous area of free memory - -MEMORY SYSTEM - - We split the system in two parts. One part allocates small memory amounts - and one part allocates large memory amounts, but all allocations are done - "through" the small-part-system. There is an option to use only the small - system (and thus use the OS for large blocks) or the complete package. - -############################################################################## - SMALL SIZE ALLOCATIONS -############################################################################## - - Keywords for this system is 'Deferred Coalescing' and 'quick lists'. - - ALLOC - - * Small allocations are "aligned" upwards to a set of preset sizes. In the - current implementation I use 20, 28, 52, 116, 312, 580, 812, 2028 bytes. - Memory allocations of these sizes are refered to as FRAGMENTS. - (The reason for these specific sizes is the requirement that they must be - 32-bit aligned and fit as good as possible within 4060 bytes.) - - * Allocations larger than 2028 will get a BLOCK for that allocation only. - - * Each of these sizes has it's own TOP. When a FRAGMENT is requested, a - larger BLOCK will be allocated and divided into many FRAGMENTS (all of the - same size). TOP points to a list with BLOCKS that contains FRAGMENTS of - the same size. Each BLOCK has a 'number of free FRAGMENTS' counter and so - has each TOP (for the entire chain). - - * A BLOCK is around 4060 bytes plus the size of the information header. This - size is adjusted to make the allocation of the big block not require more - than 4096 bytes. (This might not be so easy to be sure of, if you don't - know how the big-block system works, but the BMALLOC system uses an - extra header of 12 bytes and the header for the FRAGMENT BLOCK is 20 bytes - in a general 32-bit unix environment.) - - * In case the allocation of a BLOCK fails when a FRAGMENT is required, the - next size of FRAGMENTS will be checked for a free FRAGMENT. First when the - larger size lists have been tested without success it will fail for real. - - FREE - - * When FRAGMENTS are freed so that a BLOCK becomes non-used, it is returned - to the system. - - * FREEing a fragment adds the buffer in a LIFO-order. That means that the - next request for a fragment from the same list, the last freed buffer will - be returned first. - - REALLOC - - * REALLOCATION of a FRAGMENT does first check if the new size would fit - within the same FRAGMENT and if it would use the same FRAGMENT size. If it - does and would, the same pointer is returned. - - OVERHEAD - - Yes, there is an overhead on small allocations (internal fragmentation). - Yet, I do believe that small allocations more often than larger ones are - used dynamically. I believe that a large overhead is not a big problem if it - remains only for a while. The big gain is with the extreme speed we can GET - and RETURN small allocations. This has yet to be proven. I am open to other - systems of dealing with the small ones, but I don`t believe in using the - same system for all sizes of allocations. - - IMPROVEMENT - - An addition to the above described algorithm is the `save-empty-BLOCKS-a- - while-afterwards`. It will be used when the last used FRAGMENT within a - BLOCK is freed. The BLOCK will then not get returned to the system until "a - few more" FRAGMENTS have been freed in case the last [few] freed FRAGMENTS - are allocated yet again (and thus prevent the huge overhead of making - FRAGMENTS in a BLOCK). The "only" drawback of such a SEBAWA concept is - that it would mean an even bigger overhead... - - HEADERS (in allocated data) - - FRAGMENTS - 32-bit pointer to its parent BLOCK (lowest bit must be 0) - BLOCK - 32-bit size (lowest bit must be 1 to separate this from - FRAGMENTS) - -############################################################################## - LARGER ALLOCATIONS -############################################################################## - - If the requested size is larger than the largest FRAGMENT size supported, - the allocation will be made for this memory area alone, or if a BLOCK is - allocated to fit lots of FRAGMENTS a large block is also desired. - - * We add memory to the "system" with the add_pool() function call. It - specifies the start and size of the new block of memory that will be - used in this memory allocation system. Several add_pool() calls are - supported and they may or may not add contiguous memory. - - * Make all blocks get allocated aligned to BLOCKSIZE (sometimes referred to - as 'grain size'), 64 bytes in my implementation. Reports tell us there is - no real gain in increasing the size of the align. - - * We link *all* pieces of memory (AREAS), free or not free. We keep the list - in address order and thus when a FREE() occurs we know instanstly if there - are FREE CHUNKS wall-to-wall. No list "travels" needed. Requires some - extra space in every allocated BLOCK. Still needs to put the new CHUNK in - the right place in size-sorted list/tree. All memory areas, allocated or - not, contain the following header: - - size of this memory area - - FREE status - - pointer to the next AREA closest in memory - - pointer to the prev AREA closest in memory - (12 bytes) - - * Sort all FREE CHUNKS in size-order. We use a SPLAY TREE algorithm for - maximum speed. Data/structs used for the size-sorting functions are kept - in an abstraction layer away from this since it is really not changing - anything (except executing speed). - - ALLOC (RSIZE - requested size, aligned properly) - - * Fetch a CHUNK that RSIZE fits within. If the found CHUNK is larger than - RSIZE, split it and return the RSIZE to the caller. Link the new CHUNK - into the list/tree. - - FREE (AREA - piece of memory that is returned to the system) - - * Since the allocated BLOCK has kept its link-pointers, we can without - checking any list instantly see if there are any FREE CHUNKS that are - wall-to-wall with the AREA (both sides). If the AREA *is* wall-to-wall - with one or two CHUNKS that or they are unlinked from the lists, enlarged - and re-linked into the lists. - - REALLOC - - * There IS NO realloc() of large blocks, they are performed in the higher - layer (dmalloc). - - -############################################################################## - FURTHER READING -############################################################################## - - * "Dynamic Storage Allocation: A Survey and Critical Review" (Paul R. Wilson, - Mark S. Johnstone, Michael Neely, David Boles) - ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps - - * "A Memory Allocator" (Doug Lea) - http://g.oswego.edu/dl/html/malloc.html -- cgit v1.2.3