From 21fba08fc3a66c7f395b2a95b3e6dd3dfd9c8002 Mon Sep 17 00:00:00 2001 From: Daniel Stenberg Date: Thu, 8 Jan 2004 15:42:18 +0000 Subject: not used git-svn-id: svn://svn.rockbox.org/rockbox/trunk@4209 a1c6a512-1295-4272-9138-f99709370657 --- firmware/malloc/THOUGHTS | 170 ----------------------------------------------- 1 file changed, 170 deletions(-) delete mode 100644 firmware/malloc/THOUGHTS (limited to 'firmware/malloc/THOUGHTS') 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 -- cgit v1.2.3