From 1caca5f58597257e22c2fa8a3d8e1f528df90181 Mon Sep 17 00:00:00 2001 From: Alan Korr Date: Wed, 17 Apr 2002 17:01:55 +0000 Subject: small explanation of algorithm used for memory-page. git-svn-id: svn://svn.rockbox.org/rockbox/trunk@129 a1c6a512-1295-4272-9138-f99709370657 --- firmware/test/memory/memory-page.txt | 74 ++++++++++++++++++++++++++++++++++++ 1 file changed, 74 insertions(+) (limited to 'firmware/test') diff --git a/firmware/test/memory/memory-page.txt b/firmware/test/memory/memory-page.txt index e69de29bb2..03811f9bde 100644 --- a/firmware/test/memory/memory-page.txt +++ b/firmware/test/memory/memory-page.txt @@ -0,0 +1,74 @@ +/*************************************************************************** + * __________ __ ___. + * Open \______ \ ____ ____ | | _\_ |__ _______ ___ + * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / + * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < + * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ + * \/ \/ \/ \/ \/ + * $Id: + * + * Copyright (C) 2002 by Alan Korr + * + * 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. + * + ****************************************************************************/ + +Best-fit via binning represent the main ideas of the algorithm. + +The memory-page allocator uses an array which contains the power-of-two +orders of each free or used pages to retrieve their sizes. + +Available pages are maintained in bins, grouped by size. Depending on +its size, a free page is stored in the bin corresponding to the correct +size range (bins are detailed further): 512 B, 1 KB, 2 KB, 4 KB, 8 KB, +16 KB, 32 KB, 64 KB, 128 KB, 256 KB, 512 KB, 1 MB or 2 MB. + +Searches for available pages are processed in smallest-first, best-fit +order. + +Two implementations to chain same-sized pages are provided: +* using doubly linked stack (unordered list) as bin, pages are left + unsorted within bins, so that the best-fit strategy should only be + approximate. +* using splay tree (ordered list) as bin, pages are instead sorted + by address within bins. + +Using splay trees is slower than using doubly linked stacks but affords us +to allocate contiguous pages when possible : since doubly linked stack is +not ordered, it cannot warrant a contiguous allocation of pages. However, +there is no evidence that using splay trees really helps unfragmenting +much more than using doubly linked stack. + +All procedures maintain the invariant that no free page physically +borders another one (two bordering unused pages are always coalesced +into one larger page). + +* Alignment of pages: power-of-two, the same as their sizes. +* Minimum overhead per allocated pages: no overhead. +* Minimum allocated size: minimal page size, i.e, 512 bytes. +* Maximum allocated size: maximal page size, i.e, 2 megabytes. + +-- ALGORITHMS ----------------------------------------------------------------- + +Unoptimized and recursive algorithm to allocate an N-sized page : + +* If there is no pages in the bin of N-sized pages, try to allocate + a (2xN)-sized page and split it into two N-sized pages and free + both if they are not N-sized pages or just free one and keep + the other to mark it used if they are N-sized pages. + +Unoptimized and recursive algorithm to release an N-sized page : + +* If there is a "contiguous" page, merge it with our N-sized page and + try to release it as a (2xN)-sized page. Otherwise mark it free. + +Notes: +* Two pages are "contiguous" if they are also N-aligned and mergeable + as a 2xN-aligned page. +* The address of a "contiguous" page is quickly given by : + + address("contiguous" page) = (address(page) ^ size(page)) -- cgit v1.2.3