diff options
| -rw-r--r-- | firmware/malloc/Makefile | 40 | ||||
| -rw-r--r-- | firmware/malloc/README | 21 | ||||
| -rw-r--r-- | firmware/malloc/THOUGHTS | 170 | ||||
| -rw-r--r-- | firmware/malloc/bmalloc.c | 386 | ||||
| -rw-r--r-- | firmware/malloc/bmalloc.h | 30 | ||||
| -rw-r--r-- | firmware/malloc/bysize.c | 451 | ||||
| -rw-r--r-- | firmware/malloc/bysize.h | 24 | ||||
| -rw-r--r-- | firmware/malloc/dmalloc.c | 634 | ||||
| -rw-r--r-- | firmware/malloc/dmalloc.h | 36 |
9 files changed, 0 insertions, 1792 deletions
diff --git a/firmware/malloc/Makefile b/firmware/malloc/Makefile deleted file mode 100644 index 4524d0630b..0000000000 --- a/firmware/malloc/Makefile +++ /dev/null @@ -1,40 +0,0 @@ -# __________ __ ___. -# Open \______ \ ____ ____ | | _\_ |__ _______ ___ -# Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / -# Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < -# Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ -# \/ \/ \/ \/ \/ -# $Id$ -# -# Copyright (C) 2002 by Daniel Stenberg -# -# All files in this archive are subject to the GNU General Public License. -# See the file COPYING in the source tree root for full license agreement. -# -# This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY -# KIND, either express or implied. -# - -TARGET = libdmalloc.a - -LIBOBJS = dmalloc.o bmalloc.o bysize.o - -# define this to talk a lot in runtime -# -DDEBUG_VERBOSE -CFLAGS = -g -W -Wall -DDEBUG_MALLOC -CC = gcc -AR = ar - -LDFLAGS = -L. -ldmalloc - -all: $(TARGET) - -clean: - rm -f core *~ $(TARGET) $(LIBOBJS) - -$(TARGET): $(LIBOBJS) - $(AR) ruv $(TARGET) $(LIBOBJS) - -bmalloc.o: bmalloc.c bysize.h -bysize.o: bysize.c -dmalloc.o: dmalloc.c diff --git a/firmware/malloc/README b/firmware/malloc/README deleted file mode 100644 index 336bd571ae..0000000000 --- a/firmware/malloc/README +++ /dev/null @@ -1,21 +0,0 @@ -Package: dbestfit - a dynamic best-fit memory allocator -Date: 1996 - 2002 -Version: 3.3 -Author: Daniel Stenberg <daniel@haxx.se> -License: MIT originally, files in the Rockbox project are GPL licensed. - - I wrote the dmalloc part for small allocation sizes to improve the behavior -of the built-in (first-fit) allocator found in pSOS, during late 1996 and -spring 1997. - - I wrote the bmalloc part (best-fit with optional splay-tree sorting) just for -the fun of it and to see how good malloc() implementation 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). - - * 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/firmware/malloc/THOUGHTS b/firmware/malloc/THOUGHTS deleted file mode 100644 index 27517361da..0000000000 --- a/firmware/malloc/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 _not_ - allocated when traversed in lists etc - 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, 1016, 2032 bytes. - Memory allocations of these sizes are referred 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 4064 bytes.) - - * Allocations larger than 2032 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 4064 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 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 instantly 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 (31 bits) - - FREE status (1 bit) - - pointer to the next AREA closest in memory (32 bits) - - pointer to the prev AREA closest in memory (32 bits) - (Totally 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 previous - 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 diff --git a/firmware/malloc/bmalloc.c b/firmware/malloc/bmalloc.c deleted file mode 100644 index 470ee49840..0000000000 --- a/firmware/malloc/bmalloc.c +++ /dev/null @@ -1,386 +0,0 @@ -/*************************************************************************** - * __________ __ ___. - * Open \______ \ ____ ____ | | _\_ |__ _______ ___ - * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / - * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < - * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ - * \/ \/ \/ \/ \/ - * $Id$ - * - * Copyright (C) 2002 by Daniel Stenberg - * - * All files in this archive are subject to the GNU General Public License. - * See the file COPYING in the source tree root for full license agreement. - * - * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY - * KIND, either express or implied. - * - ****************************************************************************/ -/***************************************************************************** - * - * Big (best-fit) Memory Allocation - * - * Author: Daniel Stenberg <daniel@haxx.se> - * - * Read THOUGHTS for theories and details on implementation. - * - ****************************************************************************/ - -#include <stdio.h> -#include <stdlib.h> - -#include "bysize.h" - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -/* #define DEBUG_MALLOC */ - -#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 bmalloc_status(void); - - -/*********************************************************************** - * - * remove_block() - * - * Remove the block from the address-sorted list. - * - ***********************************************************************/ - -static -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. - * - ***************************************************************************/ -static -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: */ - bmalloc_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; - } - 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_blocktolists() recursively and then escape */ - - remove_block(temp); /* unlink 'temp' from list */ - - /* remove from size-sorted list: */ - bmalloc_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 */ - } - - newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the - FREE bit */ - bmalloc_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; -} - -/*********************************************************************** - * - * bmalloc_add_pool() - * - * This function should be the absolutely first function to call. It sets up - * the memory bounds of the [first] CHUNK(s). It is 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 non-contigous memory areas. - * - * Returns non-zero if an error occured. The memory was not added then. - * - ***********************************************************************/ - -int bmalloc_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_VERBOSE -static void bmalloc_failed(size_t size) -{ - printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size); - bmalloc_status(); -} -#else -#define bmalloc_failed(x) -#endif - -void bmalloc_status(void) -{ -#ifdef DEBUG_MALLOC - struct BlockInfo *block = blockHead; - long mem_free = 0; - long mem_used = 0; - - printf("List of BLOCKS (in address order):\n"); - while(block) { - printf(" START %p END %p SIZE %ld FLAG %s\n", - block, - (char *)block+(block->info&INFO_SIZE), - block->info&INFO_SIZE, - (block->info&INFO_FREE)?"free":"used"); - if(block->info&INFO_FREE) - mem_free += block->info&INFO_SIZE; - else - mem_used += block->info&INFO_SIZE; - block = block->higher; - } - printf(" Used mem: %ld , free mem: %ld (total %ld)\n", - mem_used, mem_free, mem_used + mem_free); - bmalloc_print_sizes(); -#endif -} - - -void *bmalloc(size_t size) -{ - void *mem; - -#ifdef DEBUG_VERBOSE - { - 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 = bmalloc_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->lower, - (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 */ - } - -#ifdef DEBUG_VERBOSE - bmalloc_status(); -#endif - return mem; -} - -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_VERBOSE - 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: */ - bmalloc_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: */ - bmalloc_remove_chunksize(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; - - bmalloc_insert_bysize((char *)block+sizeof(struct BlockInfo), - block->info&INFO_SIZE); - -#ifdef DEBUG_VERBOSE - bmalloc_status(); -#endif - -} - diff --git a/firmware/malloc/bmalloc.h b/firmware/malloc/bmalloc.h deleted file mode 100644 index 4bb89b9adb..0000000000 --- a/firmware/malloc/bmalloc.h +++ /dev/null @@ -1,30 +0,0 @@ -/*************************************************************************** - * __________ __ ___. - * Open \______ \ ____ ____ | | _\_ |__ _______ ___ - * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / - * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < - * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ - * \/ \/ \/ \/ \/ - * $Id$ - * - * Copyright (C) 2002 by Daniel Stenberg - * - * All files in this archive are subject to the GNU General Public License. - * See the file COPYING in the source tree root for full license agreement. - * - * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY - * KIND, either express or implied. - * - ****************************************************************************/ -#ifndef _BMALLOC_H_ -#define _BMALLOC_H_ - -#include <stdlib.h> - -int bmalloc_add_pool(void *start, size_t size); -void bmalloc_status(void); - -void *bmalloc(size_t size); -void bfree(void *ptr); - -#endif diff --git a/firmware/malloc/bysize.c b/firmware/malloc/bysize.c deleted file mode 100644 index 437159579c..0000000000 --- a/firmware/malloc/bysize.c +++ /dev/null @@ -1,451 +0,0 @@ -/*************************************************************************** - * __________ __ ___. - * Open \______ \ ____ ____ | | _\_ |__ _______ ___ - * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / - * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < - * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ - * \/ \/ \/ \/ \/ - * $Id$ - * - * Copyright (C) 2002 by Daniel Stenberg - * - * All files in this archive are subject to the GNU General Public License. - * See the file COPYING in the source tree root for full license agreement. - * - * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY - * KIND, either express or implied. - * - ****************************************************************************/ -/***************************************************************************** - * - * Size-sorted list/tree functions. - * - * Author: Daniel Stenberg - * Date: March 7, 1997 - * Version: 2.0 - * Email: daniel@haxx.se - * - * v2.0 - * - Added SPLAY TREE functionality. - * - * Adds and removes CHUNKS from a list or tree. - * - ****************************************************************************/ - -#include <stdio.h> -#include <stdlib.h> - -#define SPLAY /* we use the splay version as that is much faster when the - amount of blocks grow */ - -#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 bmalloc_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 bmalloc_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 *bmalloc_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) { - bmalloc_remove_chunksize( chunk ); /* unlink size-wise */ - return (char *)chunk; - } - else - return NULL; -} - -void bmalloc_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. - */ -static -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. */ -static -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. */ -static -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. */ -static -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_MALLOC -static -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; i<d; i++) - if(output) - printf(" "); - - if(output) { - printf("%d[%d]", t->key, 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 - -/* Here follow the look-alike interface so that the tree-function names are - the same as the list-ones to enable easy interchange */ - -void bmalloc_remove_chunksize(void *data) -{ - chunkHead = removebyaddr(chunkHead, data); -} - -void bmalloc_insert_bysize(char *data, size_t size) -{ - chunkHead = insert(size, chunkHead, (Tree *)data); -} - -char *bmalloc_obtainbysize( size_t size) -{ - Tree *receive; - chunkHead = removebestfit(size, chunkHead, &receive); - return (char *)receive; -} - -#ifdef DEBUG_MALLOC -void bmalloc_print_sizes(void) -{ - printtree(chunkHead, 0, 1); -} -#endif - -#endif diff --git a/firmware/malloc/bysize.h b/firmware/malloc/bysize.h deleted file mode 100644 index 34be8f9021..0000000000 --- a/firmware/malloc/bysize.h +++ /dev/null @@ -1,24 +0,0 @@ -/*************************************************************************** - * __________ __ ___. - * Open \______ \ ____ ____ | | _\_ |__ _______ ___ - * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / - * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < - * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ - * \/ \/ \/ \/ \/ - * $Id$ - * - * Copyright (C) 2002 by Daniel Stenberg - * - * All files in this archive are subject to the GNU General Public License. - * See the file COPYING in the source tree root for full license agreement. - * - * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY - * KIND, either express or implied. - * - ****************************************************************************/ -void bmalloc_remove_chunksize(void *data); -void bmalloc_insert_bysize(char *data, size_t size); -char *bmalloc_obtainbysize( size_t size); -#ifdef DEBUG_MALLOC -void bmalloc_print_sizes(void); -#endif diff --git a/firmware/malloc/dmalloc.c b/firmware/malloc/dmalloc.c deleted file mode 100644 index 7f1690b221..0000000000 --- a/firmware/malloc/dmalloc.c +++ /dev/null @@ -1,634 +0,0 @@ -/*************************************************************************** - * __________ __ ___. - * Open \______ \ ____ ____ | | _\_ |__ _______ ___ - * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / - * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < - * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ - * \/ \/ \/ \/ \/ - * $Id$ - * - * Copyright (C) 2002 by Daniel Stenberg - * - * All files in this archive are subject to the GNU General Public License. - * See the file COPYING in the source tree root for full license agreement. - * - * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY - * KIND, either express or implied. - * - ****************************************************************************/ -/***************************************************************************** - * - * Dynamic small-blocks Memory Allocation - * - * Author: Daniel Stenberg <daniel@haxx.se> - * - * Read THOUGHTS for theories and details on the implementation. - * - *****************************************************************************/ - -#include <stdio.h> -#include <string.h> /* memcpy */ - -#ifdef DEBUG_MALLOC -#include <stdarg.h> -#endif - -#ifdef PSOS -#include <psos.h> -#define SEMAPHORE /* the PSOS routines use semaphore protection */ -#else - -#endif - -#define BMALLOC /* we use our own big-malloc system */ - -#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_VERBOSE -#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_MALLOC -#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: <id> */ -#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0) -/* Argument: <id> */ -#define SEMAPHORERETURN(x) sm_v(x) -/* Argument: <name> <id-variable name> */ -#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_MALLOC -#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+=4) { a=4064/i; if(a*i >= 4060) { {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. - */ - -static const unsigned short qinfo[]= { - 20, 28, 52, 116, 312, 580, 1016, 2032 -}; - -#define MIN(x,y) ((x)<(y)?(x):(y)) - -/* ---------------------------------------------------------------------- */ -/* Globals */ -/* ---------------------------------------------------------------------- */ - -/* keeper of the chain of BLOCKS */ -static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ]; - -/* ---------------------------------------------------------------------- */ -/* Start of the real code */ -/* ---------------------------------------------------------------------- */ - -#ifdef DEBUG_MALLOC -/************ - * A few functions that are verbose and tells us about the current status - * of the dmalloc system - ***********/ - -void dmalloc_status(void) -{ - unsigned int i; - int used; - int num; - int totalfree=0; - struct MemBlock *block; - for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) { - block = top[i].chain; - used = 0; - num = 0; - while(block) { - used += top[i].nmax-block->nfree; - 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); -} -#endif - -#ifdef DEBUG_VERBOSE -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_VERBOSE - -#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) { - frag->next = (struct MemFrag *)((char *)frag + size); - frag->prev = prev; - prev = frag; - (char *)frag += size; - count += size; - } - prev->next = NULL; /* the last one has no next struct */ -} - -/*************************************************************************** - * - * dmalloc_initialize(); - * - * Call before the first dmalloc(). Inits a few memory things. - * - **************************************************************************/ -void dmalloc_initialize(void) -{ - unsigned 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]; - snprintf(name, 7, "MEM%d", i); - SEMAPHORECREATE(name, top[i].semaphore_id); - /* doesn't matter if it failed, we continue anyway ;-( */ - } -#endif - } -} - -/**************************************************************************** - * - * 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 *malloc(size_t size) -{ - void *mem; - - DBG(("malloc(%d)\n", size)); - - /* 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 */ - unsigned int queue; - for(queue=0; size > qinfo[queue]; queue++) - ; - do { - /* This is the head master of our chain: */ - memtop = &top[queue]; - - DBG(("Top info: CHAIN %p FREE %d MAX %d FRAGSIZE %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 */ - - /**** We'd prefer to not have this loop 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_VERBOSE - 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); - - /* 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 free(void *memp) -{ - struct MemInfo *meminfo = (struct MemInfo *) - ((char *)memp- sizeof(struct MemInfo)); - - DBG(("free(%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: */ - - /* clean BLOCK_BIT */ - MEMDECR(meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); - DMEM_OSFREEMEM((void *)meminfo); - } -} - -/*************************************************************************** - * - * drealloc() - * - * This needs no explanation. A realloc() look-alike. - * - **************************************************************************/ - -void *realloc(void *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; - - /* NOTE that this is only valid if BLOCK_BIT isn't set: */ - struct MemBlock *block; - - DBG(("realloc(%p, %d)\n", ptr, size)); - - if(NULL == ptr) - return malloc( size ); - - block = meminfo->block; - - /* Here we check if this is a FRAGMENT and if the new size is - still smaller than the fragsize for this block. */ - if(!((size_t)block&BLOCK_BIT) && - (size + sizeof(struct MemInfo) < block->top->fragsize )) { - - 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 fragment, so we will make a realloc - here */ - ; - else - mem = ptr; /* Just return the same pointer as we got in. */ - } - if(!mem) { - if((size_t)meminfo->block&BLOCK_BIT) { - /* This is a stand-alone BLOCK */ - prevsize = ((size_t)meminfo->block&~BLOCK_BIT) - - sizeof(struct MemInfo); - } - else - /* a FRAGMENT realloc that no longer fits within the same FRAGMENT - * or one that fits in a smaller */ - prevsize = block->top->fragsize; - - /* 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 = malloc(size); - if(mem) { - memcpy(mem, ptr, MIN(size, prevsize) ); - free(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 * -calloc (size_t nmemb, size_t size) -{ - void *result = malloc (nmemb * size); - - if (result != NULL) - memset (result, 0, nmemb * size); - - return result; -} diff --git a/firmware/malloc/dmalloc.h b/firmware/malloc/dmalloc.h deleted file mode 100644 index 96772a46f5..0000000000 --- a/firmware/malloc/dmalloc.h +++ /dev/null @@ -1,36 +0,0 @@ -/*************************************************************************** - * __________ __ ___. - * Open \______ \ ____ ____ | | _\_ |__ _______ ___ - * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / - * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < - * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ - * \/ \/ \/ \/ \/ - * $Id$ - * - * Copyright (C) 2002 by Daniel Stenberg - * - * All files in this archive are subject to the GNU General Public License. - * See the file COPYING in the source tree root for full license agreement. - * - * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY - * KIND, either express or implied. - * - ****************************************************************************/ -#ifndef _DMALLOC_H_ -#define _DMALLOC_H_ - -#include <stdlib.h> - -void *malloc(size_t); -void *calloc (size_t nmemb, size_t size); -void free(void *); -void *realloc(void *, size_t); - -/* use this to intialize the internals of the dmalloc engine */ -void dmalloc_initialize(void); - -#ifdef DEBUG -void dmalloc_status(void); -#endif - -#endif |