diff options
author | Alan Korr <alkorr@rockbox.org> | 2002-04-17 17:01:55 +0000 |
---|---|---|
committer | Alan Korr <alkorr@rockbox.org> | 2002-04-17 17:01:55 +0000 |
commit | 1caca5f58597257e22c2fa8a3d8e1f528df90181 (patch) | |
tree | dbc8749ba04c0fb974bec094a7bdf0734ad200f0 | |
parent | 98d5df6fa71e04e424162f6254207dc06e87e072 (diff) | |
download | rockbox-1caca5f58597257e22c2fa8a3d8e1f528df90181.tar.gz rockbox-1caca5f58597257e22c2fa8a3d8e1f528df90181.zip |
small explanation of algorithm used for memory-page.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@129 a1c6a512-1295-4272-9138-f99709370657
-rw-r--r-- | firmware/test/memory/memory-page.txt | 74 |
1 files changed, 74 insertions, 0 deletions
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 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id: | ||
9 | * | ||
10 | * Copyright (C) 2002 by Alan Korr | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | |||
20 | Best-fit via binning represent the main ideas of the algorithm. | ||
21 | |||
22 | The memory-page allocator uses an array which contains the power-of-two | ||
23 | orders of each free or used pages to retrieve their sizes. | ||
24 | |||
25 | Available pages are maintained in bins, grouped by size. Depending on | ||
26 | its size, a free page is stored in the bin corresponding to the correct | ||
27 | size range (bins are detailed further): 512 B, 1 KB, 2 KB, 4 KB, 8 KB, | ||
28 | 16 KB, 32 KB, 64 KB, 128 KB, 256 KB, 512 KB, 1 MB or 2 MB. | ||
29 | |||
30 | Searches for available pages are processed in smallest-first, best-fit | ||
31 | order. | ||
32 | |||
33 | Two implementations to chain same-sized pages are provided: | ||
34 | * using doubly linked stack (unordered list) as bin, pages are left | ||
35 | unsorted within bins, so that the best-fit strategy should only be | ||
36 | approximate. | ||
37 | * using splay tree (ordered list) as bin, pages are instead sorted | ||
38 | by address within bins. | ||
39 | |||
40 | Using splay trees is slower than using doubly linked stacks but affords us | ||
41 | to allocate contiguous pages when possible : since doubly linked stack is | ||
42 | not ordered, it cannot warrant a contiguous allocation of pages. However, | ||
43 | there is no evidence that using splay trees really helps unfragmenting | ||
44 | much more than using doubly linked stack. | ||
45 | |||
46 | All procedures maintain the invariant that no free page physically | ||
47 | borders another one (two bordering unused pages are always coalesced | ||
48 | into one larger page). | ||
49 | |||
50 | * Alignment of pages: power-of-two, the same as their sizes. | ||
51 | * Minimum overhead per allocated pages: no overhead. | ||
52 | * Minimum allocated size: minimal page size, i.e, 512 bytes. | ||
53 | * Maximum allocated size: maximal page size, i.e, 2 megabytes. | ||
54 | |||
55 | -- ALGORITHMS ----------------------------------------------------------------- | ||
56 | |||
57 | Unoptimized and recursive algorithm to allocate an N-sized page : | ||
58 | |||
59 | * If there is no pages in the bin of N-sized pages, try to allocate | ||
60 | a (2xN)-sized page and split it into two N-sized pages and free | ||
61 | both if they are not N-sized pages or just free one and keep | ||
62 | the other to mark it used if they are N-sized pages. | ||
63 | |||
64 | Unoptimized and recursive algorithm to release an N-sized page : | ||
65 | |||
66 | * If there is a "contiguous" page, merge it with our N-sized page and | ||
67 | try to release it as a (2xN)-sized page. Otherwise mark it free. | ||
68 | |||
69 | Notes: | ||
70 | * Two pages are "contiguous" if they are also N-aligned and mergeable | ||
71 | as a 2xN-aligned page. | ||
72 | * The address of a "contiguous" page is quickly given by : | ||
73 | |||
74 | address("contiguous" page) = (address(page) ^ size(page)) | ||