summaryrefslogtreecommitdiff
path: root/apps/plugins/pdbox/dbestfit-3.3
diff options
context:
space:
mode:
authorPeter D'Hoye <peter.dhoye@gmail.com>2009-07-23 21:37:35 +0000
committerPeter D'Hoye <peter.dhoye@gmail.com>2009-07-23 21:37:35 +0000
commit840cd1069292e3f29d18e57f2274ec1e979f858b (patch)
tree0ee1d43fa3863de53c99432dc32001e625703d1c /apps/plugins/pdbox/dbestfit-3.3
parent0d9b7ec73e71188632a4fd584dfd745aeb7571b3 (diff)
downloadrockbox-840cd1069292e3f29d18e57f2274ec1e979f858b.tar.gz
rockbox-840cd1069292e3f29d18e57f2274ec1e979f858b.zip
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
Diffstat (limited to 'apps/plugins/pdbox/dbestfit-3.3')
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/CHANGES12
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/FILES15
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/Makefile38
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/Malloc.c200
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/README21
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bmalloc.c371
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bmalloc.h5
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bysize.c428
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bysize.h4
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmalloc.c711
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmalloc.h12
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmytest.c138
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/malloc.man95
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/mytest.c69
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/thoughts170
15 files changed, 0 insertions, 2289 deletions
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 @@
1Changes
2
3* (March 30 2005) Daniel
4
5 Linus Nielsen Feltzing provided a patch that corrected several minor problems
6 that prevented dbestfit from working good. Linus also tested and timed
7 dbestfit for real in a target where he replaced the pSOS-provided memory
8 subsystem.
9
10* 3.2
11
12 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 @@
1/bysize.c
2/bysize.h
3/bmalloc.c
4/bmalloc.h
5/dmalloc.c
6/dmalloc.h
7/FILES
8/README
9/Makefile
10/Malloc.c
11/mytest.c
12/dmytest.c
13/thoughts
14/malloc.man
15/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 @@
1
2OBJS1 = bmalloc.o bysize.o mytest.o
3TARGET1 = mytest
4
5OBJS2 = dmalloc.o bmalloc.o bysize.o Malloc.o
6TARGET2 = mtest
7
8OBJS3 = dmalloc.o bmalloc.o bysize.o dmytest.o
9TARGET3 = dmytest
10
11CFLAGS = -g -DUNIX -DBMALLOC -Wall -pedantic -DDEBUG
12CC = gcc
13
14all: $(TARGET1) $(TARGET2) $(TARGET3)
15
16$(TARGET1): $(OBJS1)
17 $(CC) -g -o $(TARGET1) $(OBJS1)
18
19$(TARGET2): $(OBJS2)
20 $(CC) -g -o $(TARGET2) $(OBJS2)
21
22$(TARGET3): $(OBJS3)
23 $(CC) -g -o $(TARGET3) $(OBJS3)
24
25bmalloc.o: bmalloc.c
26dmalloc.o: dmalloc.c
27mytest.o: mytest.c
28dmytest.o: dmytest.c
29Malloc.o : Malloc.c
30bysize.o : bysize.c
31
32tgz:
33 @(dir=`pwd`;name=`basename $$dir`;echo Creates $$name.tar.gz; cd .. ; \
34 tar -cf $$name.tar `cat $$name/FILES | sed "s:^/:$$name/:g"` ; \
35 gzip $$name.tar ; chmod a+r $$name.tar.gz ; mv $$name.tar.gz $$name/)
36
37clean:
38 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 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <time.h>
5
6/* Storleken på allokeringen bestäms genom att först slumpas en position i
7"size_table" ut, sedan slumpas en storlek mellan den postionen och nästa värde
8i tabellen. Genom att ha tabellen koncentrerad med låga värden, så skapas
9flest såna. Rutinen håller på tills minnet en allokeringen nekas. Den kommer
10aldrig att ha mer än MAXIMAL_MEMORY_TO_ALLOCATE allokerat samtidigt. Maximalt
11har den MAX_ALLOCATIONS allokeringar samtidigt.
12
13Statistiskt sätt så kommer efter ett tag MAX_ALLOCATIONS/2 allokeringar finnas
14samtidigt, med varje allokering i median med värdet av halva "size_table".
15
16När minnet är slut (malloc()=NULL), frågas användaren om han ska fortsätta.
17
18Med jämna mellanrum skrivs statisktik ut på skärmen. (DISPLAY_WHEN)
19
20För att stressa systemet med fler små allokeringar, så kan man öka
21MAX_ALLOCATIONS. AMOUNT_OF_MEMORY bör få den att slå i taket fortare om man
22minskar det.
23
24Ingen initiering görs av slumptalen, så allt är upprepbart (men plocka bort
25kommentaren på srand() och det löser sig.
26
27*/
28
29/*#undef BMALLOC*/
30
31#ifdef BMALLOC
32#include "dmalloc.h"
33
34#include "bmalloc.h"
35#endif
36
37#define MAX_ALLOCATIONS 100000
38#define AMOUNT_OF_MEMORY 180000 /* bytes */
39#define MAXIMAL_MEMORY_TO_ALLOCATE 100000 /* Sätt den här högre än
40 AMOUNT_OF_MEMORY, och malloc() bör
41 returnera NULL förr eller senare */
42
43#define DISPLAY_WHEN (123456) /* When to display statistic */
44
45#define min(a, b) (((a) < (b)) ? (a) : (b))
46#define BOOL char
47#define TRUE 1
48#define FALSE 0
49
50typedef struct {
51 char *memory;
52 long size;
53 char filled_with;
54 long table_position;
55} MallocStruct;
56
57/*
58Skapar en lista med MAX_ALLOCATIONS storlek där det slumpvis allokeras
59eller reallokeras i.
60*/
61
62MallocStruct my_mallocs[MAX_ALLOCATIONS];
63
64long 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};
65#define TABLESIZE ((sizeof(size_table)-1)/sizeof(long))
66long size_allocs[TABLESIZE];
67
68int main(void)
69{
70 int i;
71 long count=-1;
72 long count_free=0, count_malloc=0, count_realloc=0;
73 long total_memory=0;
74 BOOL out_of_memory=FALSE;
75 unsigned int seed = time( NULL );
76
77#ifdef BMALLOC
78 void *thisisourheap;
79 thisisourheap = (malloc)(AMOUNT_OF_MEMORY);
80 if(!thisisourheap)
81 return -1; /* can't get memory */
82 add_pool(thisisourheap, AMOUNT_OF_MEMORY);
83#endif
84
85 seed = 1109323906;
86
87 srand( seed ); /* Initialize randomize */
88
89 printf("seed: %d\n", seed);
90
91 while (!out_of_memory) {
92 long number=rand()%MAX_ALLOCATIONS;
93 long size;
94 long table_position=rand()%TABLESIZE;
95 char fill_with=rand()&255;
96
97 count++;
98
99 size=rand()%(size_table[table_position+1]-size_table[table_position])+size_table[table_position];
100
101/* fprintf(stderr, "number %d size %d\n", number, size); */
102
103 if (my_mallocs[number].size) { /* Om allokering redan finns på den här
104 positionen, så reallokerar vi eller
105 friar. */
106 long old_size=my_mallocs[number].size;
107 if (my_mallocs[number].size && fill_with<40) {
108 free(my_mallocs[number].memory);
109 total_memory -= my_mallocs[number].size;
110 count_free++;
111 size_allocs[my_mallocs[number].table_position]--;
112 size=0;
113 my_mallocs[number].size = 0;
114 my_mallocs[number].memory = NULL;
115 } else {
116 /*
117 * realloc() part
118 *
119 */
120 char *temp;
121#if 0
122 if(my_mallocs[number].size > size) {
123 printf("*** %d is realloc()ed to %d\n",
124 my_mallocs[number].size, size);
125 }
126#endif
127 if (total_memory-old_size+size>MAXIMAL_MEMORY_TO_ALLOCATE)
128 goto output; /* for-loop */
129 temp = (char *)realloc(my_mallocs[number].memory, size);
130 if (!temp)
131 out_of_memory=TRUE;
132 else {
133 my_mallocs[number].memory = temp;
134
135 my_mallocs[number].size=size;
136 size_allocs[my_mallocs[number].table_position]--;
137 size_allocs[table_position]++;
138 total_memory -= old_size;
139 total_memory += size;
140 old_size=min(old_size, size);
141 while (--old_size>0) {
142 if (my_mallocs[number].memory[old_size]!=my_mallocs[number].filled_with)
143 fprintf(stderr, "Wrong filling!\n");
144 }
145 count_realloc++;
146 }
147 }
148 } else {
149 if (total_memory+size>MAXIMAL_MEMORY_TO_ALLOCATE) {
150 goto output; /* for-loop */
151 }
152 my_mallocs[number].memory=(char *)malloc(size); /* Allokera! */
153 if (!my_mallocs[number].memory)
154 out_of_memory=TRUE;
155 else {
156 size_allocs[table_position]++;
157 count_malloc++;
158 total_memory += size;
159 }
160 }
161
162 if(!out_of_memory) {
163 my_mallocs[number].table_position=table_position;
164 my_mallocs[number].size=size;
165 my_mallocs[number].filled_with=fill_with;
166 memset(my_mallocs[number].memory, fill_with, size);
167 }
168 output:
169 if (out_of_memory || !(count%DISPLAY_WHEN)) {
170 printf("(%d) malloc %d, realloc %d, free %d, total size %d\n", count, count_malloc, count_realloc, count_free, total_memory);
171 {
172 int count;
173 printf("[size bytes]=[number of allocations]\n");
174 for (count=0; count<TABLESIZE; count++) {
175 printf("%ld=%ld, ", size_table[count], size_allocs[count]);
176 }
177 printf("\n\n");
178 }
179 }
180 if (out_of_memory) {
181 fprintf(stderr, "Memory is out! Continue (y/n)");
182 switch (getchar()) {
183 case 'y':
184 case 'Y':
185 out_of_memory=FALSE;
186 break;
187 }
188 fprintf(stderr, "\n");
189 }
190 }
191 for(i = 0;i < MAX_ALLOCATIONS;i++) {
192 if((my_mallocs[i].memory))
193 free(my_mallocs[i].memory);
194 }
195
196 print_lists();
197
198 printf("\n");
199 return 0;
200}
diff --git a/apps/plugins/pdbox/dbestfit-3.3/README b/apps/plugins/pdbox/dbestfit-3.3/README
deleted file mode 100644
index 7452e36279..0000000000
--- a/apps/plugins/pdbox/dbestfit-3.3/README
+++ /dev/null
@@ -1,21 +0,0 @@
1Package: dbestfit - a dynamic memory allocator
2Date: March 30, 2005
3Version: 3.3
4Author: Daniel Stenberg <daniel@haxx.se>
5
6 I wrote the dmalloc part for small allocation sizes to improve the behavior
7of the built-in (first-fit) allocator found in pSOS (around 1996).
8
9 I wrote the bmalloc part (best-fit with splay-tree sorting) just for the fun
10of it and to see how good malloc() clone I could make. The quality of my
11implementation is still left to be judged in real-world tests.
12
13TODO:
14 * Remove the final not-so-very-nice loop in dmalloc.c that checks for a block
15 with free fragments (when the list gets longer too much time might be spent
16 in that loop).
17
18 * Add semaphore protection in bmalloc.
19
20 * Make a separate application that samples the memory usage of a program
21 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 @@
1/*****************************************************************************
2 *
3 * Big (best-fit) Memory Allocation
4 *
5 * Author: Daniel Stenberg
6 * Date: March 5, 1997
7 * Version: 2.0
8 * Email: Daniel.Stenberg@sth.frontec.se
9 *
10 *
11 * Read 'thoughts' for theories and details in implementation.
12 *
13 * Routines meant to replace the most low level functions of an Operting
14 * System
15 *
16 * v2.0
17 * - Made all size-routines get moved out from this file. This way, the size
18 * functions can much more easily get replaced.
19 * - Improved how new memory blocks get added to the size-sorted list. When
20 * not adding new pools, there should never ever be any list traversing
21 * since all information is dynamically gathered.
22 *
23 ****************************************************************************/
24
25#include <stdio.h>
26#include <stdlib.h>
27
28#include "bysize.h"
29
30#ifndef TRUE
31#define TRUE 1
32#endif
33#ifndef FALSE
34#define FALSE 0
35#endif
36
37/* #define DEBUG */
38
39#define BMEM_ALIGN 64 /* resolution */
40
41#define BMEMERR_TOOSMALL -1
42
43/* this struct will be stored in all CHUNKS and AREAS */
44struct BlockInfo {
45 struct BlockInfo *lower; /* previous block in memory (lower address) */
46 struct BlockInfo *higher; /* next block in memory (higher address) */
47 unsigned long info; /* 31 bits size: 1 bit free boolean */
48#define INFO_FREE 1
49#define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */
50
51 /* FREE+SIZE Could be written to use ordinary bitfields if using a smart
52 (like gcc) compiler in a manner like:
53 int size:31;
54 int free:1;
55
56 The 'higher' pointer COULD be removed completely if the size is used as
57 an index to the higher one. This would then REQUIRE the entire memory
58 pool to be contiguous and it needs a 'terminating' "node" or an extra
59 flag that informs about the end of the list.
60 */
61};
62
63/* the BLOCK list should be sorted in a lower to higher address order */
64struct BlockInfo *blockHead=NULL; /* nothing from the start */
65
66void print_lists(void);
67
68
69/***********************************************************************
70 *
71 * remove_block()
72 *
73 * Remove the block from the address-sorted list.
74 *
75 ***********************************************************************/
76
77void remove_block(struct BlockInfo *block)
78{
79 if(block->lower)
80 block->lower->higher = block->higher;
81 else
82 blockHead = block->higher;
83 if(block->higher)
84 block->higher->lower = block->lower;
85}
86
87/****************************************************************************
88 *
89 * add_blocktolists()
90 *
91 * Adds the specified block at the specified place in the address-sorted
92 * list and at the appropriate place in the size-sorted.
93 *
94 ***************************************************************************/
95void add_blocktolists(struct BlockInfo *block,
96 struct BlockInfo *newblock,
97 size_t newsize)
98{
99 struct BlockInfo *temp; /* temporary storage variable */
100 if(block) {
101 /* `block' is now a lower address than 'newblock' */
102
103 /*
104 * Check if the new CHUNK is wall-to-wall with the lower addressed
105 * one (if *that* is free)
106 */
107 if(block->info&INFO_FREE) {
108 if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) {
109 /* yes sir, this is our lower address neighbour, enlarge that one
110 pick it out from the list and recursively add that chunk and
111 then we escape */
112
113 /* remove from size-sorted list: */
114 remove_chunksize((char*)block+sizeof(struct BlockInfo));
115
116 block->info += newsize; /* newsize is an even number and thus the FREE
117 bit is untouched */
118
119 remove_block(block); /* unlink the block address-wise */
120
121 /* recursively check our lower friend(s) */
122 add_blocktolists(block->lower, block, block->info&INFO_SIZE);
123 return;
124 }
125 }
126
127 temp = block->higher;
128
129 block->higher = newblock;
130 newblock->lower = block;
131 newblock->higher = temp;
132 if(newblock->higher)
133 newblock->higher->lower = newblock;
134 }
135 else {
136 /* this block should preceed the heading one */
137 temp = blockHead;
138
139 /* check if this is our higher addressed neighbour */
140 if((char *)newblock + newsize == (char *)temp) {
141
142 /* yes, we are wall-to-wall with the higher CHUNK */
143 if(temp->info&INFO_FREE) {
144 /* and the neighbour is even free, remove that one and enlarge
145 ourselves, call add_pool() recursively and then escape */
146
147 remove_block(temp); /* unlink 'temp' from list */
148
149 /* remove from size-sorted list: */
150 remove_chunksize((char*)temp+sizeof(struct BlockInfo) );
151
152 /* add the upper block's size on ourselves */
153 newsize += temp->info&INFO_SIZE;
154
155 /* add the new, bigger block */
156 add_blocktolists(block, newblock, newsize);
157 return;
158 }
159 }
160
161 blockHead = newblock;
162 newblock->higher = temp;
163 newblock->lower = NULL; /* there is no lower one */
164 if(newblock->higher)
165 newblock->higher->lower = newblock;
166 }
167
168 newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the
169 FREE bit */
170 insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize);
171}
172
173/***********************************************************************
174 *
175 * findblockbyaddr()
176 *
177 * Find the block that is just before the input block in memory. Returns NULL
178 * if none is.
179 *
180 ***********************************************************************/
181
182static struct BlockInfo *findblockbyaddr(struct BlockInfo *block)
183{
184 struct BlockInfo *test = blockHead;
185 struct BlockInfo *lower = NULL;
186
187 while(test && (test < block)) {
188 lower = test;
189 test = test->higher;
190 }
191 return lower;
192}
193
194/***********************************************************************
195 *
196 * add_pool()
197 *
198 * This function should be the absolutely first function to call. It sets up
199 * the memory bounds of the [first] CHUNK(s). It should be possible to call
200 * this function several times to add more CHUNKs to the pool of free
201 * memory. This allows the bmalloc system to deal with a non-contigous memory
202 * area.
203 *
204 * Returns non-zero if an error occured. The memory was not added then.
205 *
206 ***********************************************************************/
207
208int add_pool(void *start,
209 size_t size)
210{
211 struct BlockInfo *newblock = (struct BlockInfo *)start;
212 struct BlockInfo *block;
213
214 if(size < BMEM_ALIGN)
215 return BMEMERR_TOOSMALL;
216
217 block = findblockbyaddr( newblock );
218 /* `block' is now a lower address than 'newblock' or NULL */
219
220 if(size&1)
221 size--; /* only add even sizes */
222
223 add_blocktolists(block, newblock, size);
224
225 return 0;
226}
227
228
229#ifdef DEBUG
230static void bmalloc_failed(size_t size)
231{
232 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
233 print_lists();
234}
235#else
236#define bmalloc_failed(x)
237#endif
238
239#ifdef DEBUG
240void print_lists()
241{
242 struct BlockInfo *block = blockHead;
243#if 1
244 printf("List of BLOCKS (in address order):\n");
245 while(block) {
246 printf(" START %p END %p SIZE %ld FLAG %s\n",
247 (char *)block,
248 (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE,
249 (block->info&INFO_FREE)?"free":"used");
250 block = block->higher;
251 }
252 printf("End of BLOCKS:\n");
253#endif
254 print_sizes();
255}
256#endif /* DEBUG */
257
258void *bmalloc(size_t size)
259{
260 void *mem;
261
262#ifdef DEBUG
263 {
264 static int count=0;
265 int realsize = size + sizeof(struct BlockInfo);
266 if(realsize%4096)
267 realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
268 printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
269 }
270#endif
271
272 size += sizeof(struct BlockInfo); /* add memory for our header */
273
274 if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
275 changed if the BLOCKSIZE is not 2^X ! */
276 size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
277
278 /* get a CHUNK from the list with this size */
279 mem = obtainbysize ( size );
280 if(mem) {
281 /* the memory block we have got is the "best-fit" and it is already
282 un-linked from the free list */
283
284 /* now do the math to get the proper block pointer */
285 struct BlockInfo *block= (struct BlockInfo *)
286 ((char *)mem - sizeof(struct BlockInfo));
287
288 block->info &= ~INFO_FREE;
289 /* not free anymore */
290
291 if( size != (block->info&INFO_SIZE)) {
292 /* split this chunk into two pieces and return the one that fits us */
293 size_t othersize = (block->info&INFO_SIZE) - size;
294
295 if(othersize > BMEM_ALIGN) {
296 /* prevent losing small pieces of memory due to weird alignments
297 of the memory pool */
298
299 block->info = size; /* set new size (leave FREE bit cleared) */
300
301 /* Add the new chunk to the lists: */
302 add_blocktolists(block,
303 (struct BlockInfo *)((char *)block + size),
304 othersize );
305 }
306 }
307
308 /* Return the memory our parent may use: */
309 return (char *)block+sizeof(struct BlockInfo);
310 }
311 else {
312 bmalloc_failed(size);
313 return NULL; /* can't find any memory, fail hard */
314 }
315 return NULL;
316}
317
318void bfree(void *ptr)
319{
320 struct BlockInfo *block = (struct BlockInfo *)
321 ((char *)ptr - sizeof(struct BlockInfo));
322 size_t size;
323
324 /* setup our initial higher and lower pointers */
325 struct BlockInfo *lower = block->lower;
326 struct BlockInfo *higher = block->higher;
327
328#ifdef DEBUG
329 static int freecount=0;
330 printf("%d bfree(%p)\n", freecount++, ptr);
331#endif
332
333 /* bind together lower addressed FREE CHUNKS */
334 if(lower && (lower->info&INFO_FREE) &&
335 ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
336 size = block->info&INFO_SIZE; /* original size */
337
338 /* remove from size-link: */
339 remove_chunksize((char *)lower+sizeof(struct BlockInfo));
340
341 remove_block(block); /* unlink from address list */
342 block = lower; /* new base area pointer */
343 block->info += size; /* append the new size (the FREE bit
344 will remain untouched) */
345
346 lower = lower->lower; /* new lower pointer */
347 }
348 /* bind together higher addressed FREE CHUNKS */
349 if(higher && (higher->info&INFO_FREE) &&
350 ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) {
351 /* append higher size, the FREE bit won't be affected */
352 block->info += (higher->info&INFO_SIZE);
353
354 /* unlink from size list: */
355 remove_chunksize((char *)higher+sizeof(struct BlockInfo));
356 remove_block(higher); /* unlink from address list */
357 higher = higher->higher; /* the new higher link */
358 block->higher = higher; /* new higher link */
359 }
360 block->info |= INFO_FREE; /* consider this FREE! */
361
362 block->lower = lower;
363 block->higher = higher;
364
365 insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE);
366
367#ifdef DEBUG
368 print_lists();
369#endif
370
371}
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 @@
1int add_pool(void *start, size_t size);
2void print_lists(void);
3
4void *bmalloc(size_t size);
5void 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 @@
1/*****************************************************************************
2 *
3 * Size-sorted list/tree functions.
4 *
5 * Author: Daniel Stenberg
6 * Date: March 7, 1997
7 * Version: 2.0
8 * Email: Daniel.Stenberg@sth.frontec.se
9 *
10 *
11 * v2.0
12 * - Added SPLAY TREE functionality.
13 *
14 * Adds and removes CHUNKS from a list or tree.
15 *
16 ****************************************************************************/
17
18#include <stdio.h>
19#include <stdlib.h>
20
21#define SPLAY /* we use the splay version as that is much faster */
22
23#ifndef TRUE
24#define TRUE 1
25#endif
26#ifndef FALSE
27#define FALSE 0
28#endif
29
30#ifndef SPLAY /* these routines are for the non-splay version */
31
32struct ChunkInfo {
33 struct ChunkInfo *larger;
34 struct ChunkInfo *smaller;
35 size_t size;
36};
37
38/* the CHUNK list anchor */
39struct ChunkInfo *chunkHead=NULL;
40
41/***********************************************************************
42
43 findchunkbysize()
44
45 Find the chunk that is smaller than the input size. Returns
46 NULL if none is.
47
48 **********************************************************************/
49
50static struct ChunkInfo *findchunkbysize(size_t size)
51{
52 struct ChunkInfo *test = chunkHead;
53 struct ChunkInfo *smaller = NULL;
54 while(test && (test->size < size)) {
55 smaller = test;
56 test = test->larger;
57 }
58 return smaller;
59}
60
61/***********************************************************************
62
63 remove_chunksize()
64
65 Remove the chunk from the size-sorted list.
66 ***********************************************************************/
67
68void remove_chunksize(void *data)
69{
70 struct ChunkInfo *chunk = (struct ChunkInfo *)data;
71 if(chunk->smaller)
72 chunk->smaller->larger = chunk->larger;
73 else {
74 /* if this has no smaller, this is the head */
75 chunkHead = chunk->larger; /* new head */
76 }
77 if(chunk->larger)
78 chunk->larger->smaller = chunk->smaller;
79}
80
81void insert_bysize(char *data, size_t size)
82{
83 struct ChunkInfo *newchunk = (struct ChunkInfo *)data;
84 struct ChunkInfo *chunk = findchunkbysize ( size );
85
86 newchunk->size = size;
87
88 if(chunk) {
89 /* 'chunk' is smaller than size, append the new chunk ahead of this */
90 newchunk->smaller = chunk;
91 newchunk->larger = chunk->larger;
92 if(chunk->larger)
93 chunk->larger->smaller = newchunk;
94 chunk->larger = newchunk;
95 }
96 else {
97 /* smallest CHUNK around, append first in the list */
98 newchunk->larger = chunkHead;
99 newchunk->smaller = NULL;
100
101 if(chunkHead)
102 chunkHead->smaller = newchunk;
103 chunkHead = newchunk;
104 }
105}
106
107char *obtainbysize( size_t size)
108{
109 struct ChunkInfo *chunk = findchunkbysize( size );
110
111 if(!chunk) {
112 if(size <= (chunkHead->size))
113 /* there is no smaller CHUNK, use the first one (if we fit within that)
114 */
115 chunk = chunkHead;
116 }
117 else
118 /* we're on the last CHUNK that is smaller than requested, step onto
119 the bigger one */
120 chunk = chunk->larger;
121
122 if(chunk) {
123 remove_chunksize( chunk ); /* unlink size-wise */
124 return (char *)chunk;
125 }
126 else
127 return NULL;
128}
129
130void print_sizes(void)
131{
132 struct ChunkInfo *chunk = chunkHead;
133 printf("List of CHUNKS (in size order):\n");
134#if 1
135 while(chunk) {
136 printf(" START %p END %p SIZE %d\n",
137 chunk, (char *)chunk+chunk->size, chunk->size);
138 chunk = chunk->larger;
139 }
140#endif
141 printf("End of CHUNKS:\n");
142}
143
144#else /* Here follows all routines dealing with the SPLAY TREES */
145
146typedef struct tree_node Tree;
147struct tree_node {
148 Tree *smaller; /* smaller node */
149 Tree *larger; /* larger node */
150 Tree *same; /* points to a node with identical key */
151 int key; /* the "sort" key */
152};
153
154Tree *chunkHead = NULL; /* the root */
155
156#define compare(i,j) ((i)-(j))
157
158/* Set this to a key value that will *NEVER* appear otherwise */
159#define KEY_NOTUSED -1
160
161/*
162 * Splay using the key i (which may or may not be in the tree.) The starting
163 * root is t. Weight fields are maintained.
164 */
165Tree * splay (int i, Tree *t)
166{
167 Tree N, *l, *r, *y;
168 int comp;
169
170 if (t == NULL)
171 return t;
172 N.smaller = N.larger = NULL;
173 l = r = &N;
174
175 for (;;) {
176 comp = compare(i, t->key);
177 if (comp < 0) {
178 if (t->smaller == NULL)
179 break;
180 if (compare(i, t->smaller->key) < 0) {
181 y = t->smaller; /* rotate smaller */
182 t->smaller = y->larger;
183 y->larger = t;
184
185 t = y;
186 if (t->smaller == NULL)
187 break;
188 }
189 r->smaller = t; /* link smaller */
190 r = t;
191 t = t->smaller;
192 }
193 else if (comp > 0) {
194 if (t->larger == NULL)
195 break;
196 if (compare(i, t->larger->key) > 0) {
197 y = t->larger; /* rotate larger */
198 t->larger = y->smaller;
199 y->smaller = t;
200 t = y;
201 if (t->larger == NULL)
202 break;
203 }
204 l->larger = t; /* link larger */
205 l = t;
206 t = t->larger;
207 }
208 else {
209 break;
210 }
211 }
212
213 l->larger = r->smaller = NULL;
214
215 l->larger = t->smaller; /* assemble */
216 r->smaller = t->larger;
217 t->smaller = N.larger;
218 t->larger = N.smaller;
219
220 return t;
221}
222
223/* Insert key i into the tree t. Return a pointer to the resulting tree or
224 NULL if something went wrong. */
225Tree *insert(int i, Tree *t, Tree *new)
226{
227 if (new == NULL) {
228 return t;
229 }
230
231 if (t != NULL) {
232 t = splay(i,t);
233 if (compare(i, t->key)==0) {
234 /* it already exists one of this size */
235
236 new->same = t;
237 new->key = i;
238 new->smaller = t->smaller;
239 new->larger = t->larger;
240
241 t->smaller = new;
242 t->key = KEY_NOTUSED;
243
244 return new; /* new root node */
245 }
246 }
247
248 if (t == NULL) {
249 new->smaller = new->larger = NULL;
250 }
251 else if (compare(i, t->key) < 0) {
252 new->smaller = t->smaller;
253 new->larger = t;
254 t->smaller = NULL;
255 }
256 else {
257 new->larger = t->larger;
258 new->smaller = t;
259 t->larger = NULL;
260 }
261 new->key = i;
262
263 new->same = NULL; /* no identical node (yet) */
264
265 return new;
266}
267
268/* Finds and deletes the best-fit node from the tree. Return a pointer to the
269 resulting tree. best-fit means the smallest node that fits the requested
270 size. */
271Tree *removebestfit(int i, Tree *t, Tree **removed)
272{
273 Tree *x;
274
275 if (t==NULL)
276 return NULL;
277 t = splay(i,t);
278 if(compare(i, t->key) > 0) {
279 /* too small node, try the larger chain */
280 if(t->larger)
281 t=splay(t->larger->key, t);
282 else {
283 /* fail */
284 *removed = NULL;
285 return t;
286 }
287 }
288
289 if (compare(i, t->key) <= 0) { /* found it */
290
291 /* FIRST! Check if there is a list with identical sizes */
292 x = t->same;
293 if(x) {
294 /* there is, pick one from the list */
295
296 /* 'x' is the new root node */
297
298 x->key = t->key;
299 x->larger = t->larger;
300 x->smaller = t->smaller;
301 *removed = t;
302 return x; /* new root */
303 }
304
305 if (t->smaller == NULL) {
306 x = t->larger;
307 }
308 else {
309 x = splay(i, t->smaller);
310 x->larger = t->larger;
311 }
312 *removed = t;
313
314 return x;
315 }
316 else {
317 *removed = NULL; /* no match */
318 return t; /* It wasn't there */
319 }
320}
321
322
323/* Deletes the node we point out from the tree if it's there. Return a pointer
324 to the resulting tree. */
325Tree *removebyaddr(Tree *t, Tree *remove)
326{
327 Tree *x;
328
329 if (!t || !remove)
330 return NULL;
331
332 if(KEY_NOTUSED == remove->key) {
333 /* just unlink ourselves nice and quickly: */
334 remove->smaller->same = remove->same;
335 if(remove->same)
336 remove->same->smaller = remove->smaller;
337 /* voila, we're done! */
338 return t;
339 }
340
341 t = splay(remove->key,t);
342
343 /* Check if there is a list with identical sizes */
344
345 x = t->same;
346 if(x) {
347 /* 'x' is the new root node */
348
349 x->key = t->key;
350 x->larger = t->larger;
351 x->smaller = t->smaller;
352
353 return x; /* new root */
354 }
355
356 /* Remove the actualy root node: */
357
358 if (t->smaller == NULL) {
359 x = t->larger;
360 }
361 else {
362 x = splay(remove->key, t->smaller);
363 x->larger = t->larger;
364 }
365
366 return x;
367}
368
369#ifdef DEBUG
370int printtree(Tree * t, int d, char output)
371{
372 int distance=0;
373 Tree *node;
374 int i;
375 if (t == NULL)
376 return 0;
377 distance += printtree(t->larger, d+1, output);
378 for (i=0; i<d; i++)
379 if(output)
380 printf(" ");
381
382 if(output) {
383 printf("%d[%d]", t->key, i);
384 }
385
386 for(node = t->same; node; node = node->same) {
387 distance += i; /* this has the same "virtual" distance */
388
389 if(output)
390 printf(" [+]");
391 }
392 if(output)
393 puts("");
394
395 distance += i;
396 distance += printtree(t->smaller, d+1, output);
397 return distance;
398}
399#endif /* DEBUG */
400
401/* Here follow the look-alike interface so that the tree-function names are
402 the same as the list-ones to enable easy interchange */
403
404void remove_chunksize(void *data)
405{
406 chunkHead = removebyaddr(chunkHead, data);
407}
408
409void insert_bysize(char *data, size_t size)
410{
411 chunkHead = insert(size, chunkHead, (Tree *)data);
412}
413
414char *obtainbysize( size_t size)
415{
416 Tree *receive;
417 chunkHead = removebestfit(size, chunkHead, &receive);
418 return (char *)receive;
419}
420
421#ifdef DEBUG
422void print_sizes(void)
423{
424 printtree(chunkHead, 0, 1);
425}
426#endif /* DEBUG */
427
428#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 @@
1void remove_chunksize(void *data);
2void insert_bysize(char *data, size_t size);
3char *obtainbysize( size_t size);
4void 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 @@
1/*****************************************************************************
2 *
3 * Dynamic Memory Allocation
4 *
5 * Author: Daniel Stenberg
6 * Date: March 10, 1997
7 * Version: 2.3
8 * Email: Daniel.Stenberg@sth.frontec.se
9 *
10 *
11 * Read 'thoughts' for theories and details of this implementation.
12 *
13 * v2.1
14 * - I once again managed to gain some memory. BLOCK allocations now only use
15 * a 4 bytes header (instead of previos 8) just as FRAGMENTS.
16 *
17 * v2.2
18 * - Re-adjusted the fragment sizes to better fit into the somewhat larger
19 * block.
20 *
21 * v2.3
22 * - Made realloc(NULL, size) work as it should. Which is like a malloc(size)
23 *
24 *****************************************************************************/
25
26#ifdef ROCKBOX
27#include "plugin.h"
28#define memset rb->memset
29#define memcpy rb->memcpy
30#else /* ROCKBOX */
31#include <stdio.h>
32#include <string.h>
33#endif /* ROCKBOX */
34
35#ifdef DEBUG
36#include <stdarg.h>
37#endif
38
39#ifdef PSOS
40#include <psos.h>
41#define SEMAPHORE /* the PSOS routines use semaphore protection */
42#else
43#include <stdlib.h> /* makes the PSOS complain on the 'size_t' typedef */
44#endif
45
46#ifdef BMALLOC
47#include "bmalloc.h"
48#endif
49
50/* Each TOP takes care of a chain of BLOCKS */
51struct MemTop {
52 struct MemBlock *chain; /* pointer to the BLOCK chain */
53 long nfree; /* total number of free FRAGMENTS in the chain */
54 short nmax; /* total number of FRAGMENTS in this kind of BLOCK */
55 size_t fragsize; /* the size of each FRAGMENT */
56
57#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */
58 long semaphore_id; /* semaphore used to lock this particular list */
59#endif
60
61};
62
63/* Each BLOCK takes care of an amount of FRAGMENTS */
64struct MemBlock {
65 struct MemTop *top; /* our TOP struct */
66 struct MemBlock *next; /* next BLOCK */
67 struct MemBlock *prev; /* prev BLOCK */
68
69 struct MemFrag *first; /* the first free FRAGMENT in this block */
70
71 short nfree; /* number of free FRAGMENTS in this BLOCK */
72};
73
74/* This is the data kept in all _free_ FRAGMENTS */
75struct MemFrag {
76 struct MemFrag *next; /* next free FRAGMENT */
77 struct MemFrag *prev; /* prev free FRAGMENT */
78};
79
80/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this
81 to the allocation size first thing in the ALLOC function to make room for
82 this smoothly. */
83
84struct MemInfo {
85 void *block;
86 /* which BLOCK is our father, if BLOCK_BIT is set it means this is a
87 stand-alone, large allocation and then the rest of the bits should be
88 treated as the size of the block */
89#define BLOCK_BIT 1
90};
91
92/* ---------------------------------------------------------------------- */
93/* Defines */
94/* ---------------------------------------------------------------------- */
95
96#ifdef DEBUG
97#define MEMINCR(addr,x) memchange(addr, x)
98#define MEMDECR(addr,x) memchange(addr,-(x))
99#else
100#define MEMINCR(a,x)
101#define MEMDECR(a,x)
102#endif
103
104/* The low level functions used to get memory from the OS and to return memory
105 to the OS, we may also define a stub that does the actual allocation and
106 free, these are the defined function names used in the dmalloc system
107 anyway: */
108#ifdef PSOS
109
110#ifdef DEBUG
111#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
112#define DMEM_OSFREEMEM(x) dbgfree(x)
113#else
114#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer)
115/* Similar, but this returns the memory */
116#define DMEM_OSFREEMEM(x) rn_retseg(0, x)
117#endif
118
119/* Argument: <id> */
120#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0)
121/* Argument: <id> */
122#define SEMAPHORERETURN(x) sm_v(x)
123/* Argument: <name> <id-variable name> */
124#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y))
125
126#else
127#ifdef BMALLOC /* use our own big-memory-allocation system */
128#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size)
129#define DMEM_OSFREEMEM(x) bfree(x)
130#elif DEBUG
131#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
132#define DMEM_OSFREEMEM(x) dbgfree(x)
133#else
134#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size)
135#define DMEM_OSFREEMEM(x) free(x)
136#endif
137#endif
138
139
140/* the largest memory allocation that is made a FRAGMENT: (grab the highest
141 number from the list below) */
142#define DMEM_LARGESTSIZE 2032
143
144/* The total size of a BLOCK used for FRAGMENTS
145 In order to make this use only *1* even alignment from the big-block-
146 allocation-system (possible the bmalloc() system also written by me)
147 we need to subtract the [maximum] struct sizes that could get added all
148 the way through to the grab from the memory. */
149#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */
150
151/* Since the blocksize isn't an even 2^X story anymore, we make a table with
152 the FRAGMENT sizes and amounts that fills up a BLOCK nicely */
153
154/* a little 'bc' script that helps us maximize the usage:
155 - for 32-bit aligned addresses (SPARC crashes otherwise):
156 for(i=20; i<2040; i++) { a=4064/i; if(a*i >= 4060) { if(i%4==0) {i;} } }
157
158
159 I try to approximate a double of each size, starting with ~20. We don't do
160 ODD sizes since several CPU flavours dump core when accessing such
161 addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain
162 happy with us.
163 */
164
165#if defined(BIGBLOCKS) && BIGBLOCKS==4060 /* previously */
166#ifdef ROCKBOX
167unsigned
168#endif /* ROCKBOX */
169short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
170#else
171#ifdef ROCKBOX
172unsigned
173#endif /* ROCKBOX */
174short qinfo[]= { 20, 28, 52, 116, 312, 580, 1016, 2032};
175/* 52 and 312 only make use of 4056 bytes, but without them there are too
176 wide gaps */
177#endif
178
179#ifndef ROCKBOX
180#define MIN(x,y) ((x)<(y)?(x):(y))
181#endif /* ROCKBOX */
182
183/* ---------------------------------------------------------------------- */
184/* Globals */
185/* ---------------------------------------------------------------------- */
186
187/* keeper of the chain of BLOCKS */
188static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
189
190/* are we experienced? */
191static char initialized = 0;
192
193/* ---------------------------------------------------------------------- */
194/* Start of the real code */
195/* ---------------------------------------------------------------------- */
196
197#ifdef DEBUG
198/************
199 * A few functions that are verbose and tells us about the current status
200 * of the dmalloc system
201 ***********/
202
203static void dmalloc_status()
204{
205 int i;
206 int used;
207 int num;
208 int totalfree=0;
209 struct MemBlock *block;
210 for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) {
211 block = top[i].chain;
212 used = 0;
213 num = 0;
214 while(block) {
215 used += top[i].nmax-block->nfree;
216 num++;
217 block = block->next;
218 }
219 printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n",
220 i, top[i].fragsize, used, top[i].nfree,
221 top[i].nfree*top[i].fragsize, num);
222 totalfree += top[i].nfree*top[i].fragsize;
223 }
224 printf("Total unused memory stolen by dmalloc: %d\n", totalfree);
225}
226
227static void dmalloc_failed(size_t size)
228{
229 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
230 dmalloc_status();
231}
232#else
233#define dmalloc_failed(x)
234#endif
235
236#ifdef DEBUG
237
238#define BORDER 1200
239
240void *dbgmalloc(int size)
241{
242 char *mem;
243 size += BORDER;
244#ifdef PSOS
245 rn_getseg(0,size,RN_NOWAIT,0,(void **)&mem);
246#else
247 mem = malloc(size);
248#endif
249 if(mem) {
250 memset(mem, 0xaa, BORDER/2);
251 memset(mem+BORDER/2, 0xbb, size -BORDER);
252 memset(mem-BORDER/2+size, 0xcc, BORDER/2);
253 *(long *)mem = size;
254 mem += (BORDER/2);
255 }
256 printf("OSmalloc(%p)\n", mem);
257 return (void *)mem;
258}
259
260void checkmem(char *ptr)
261{
262 int i;
263 long size;
264 ptr -= BORDER/2;
265
266 for(i=4; i<(BORDER/2); i++)
267 if((unsigned char)ptr[i] != 0xaa) {
268 printf("########### ALERT ALERT\n");
269 break;
270 }
271 size = *(long *)ptr;
272 for(i=size-1; i>=(size - BORDER/2); i--)
273 if((unsigned char)ptr[i] != 0xcc) {
274 printf("********* POST ALERT\n");
275 break;
276 }
277}
278
279void dbgfree(char *ptr)
280{
281 long size;
282 checkmem(ptr);
283 ptr -= BORDER/2;
284 size = *(long *)ptr;
285
286 printf("OSfree(%ld)\n", size);
287#ifdef PSOS
288 rn_retseg(0, ptr);
289#else
290 free(ptr);
291#endif
292}
293
294
295#define DBG(x) syslog x
296
297void syslog(char *fmt, ...)
298{
299 va_list ap;
300 va_start(ap, fmt);
301 vfprintf(stdout, fmt, ap);
302 va_end(ap);
303}
304
305void memchange(void *a, int x)
306{
307 static int memory=0;
308 static int count=0;
309 static int max=0;
310 if(memory > max)
311 max = memory;
312 memory += x;
313 DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max));
314}
315#else
316#define DBG(x)
317#endif
318
319/****************************************************************************
320 *
321 * FragBlock()
322 *
323 * This function makes FRAGMENTS of the BLOCK sent as argument.
324 *
325 ***************************************************************************/
326
327static void FragBlock(char *memp, int size)
328{
329 struct MemFrag *frag=(struct MemFrag *)memp;
330 struct MemFrag *prev=NULL; /* no previous in the first round */
331 int count=0;
332 while((count+size) <= DMEM_BLOCKSIZE) {
333 memp += size;
334 frag->next = (struct MemFrag *)memp;
335 frag->prev = prev;
336 prev = frag;
337 frag = frag->next;
338 count += size;
339 }
340 prev->next = NULL; /* the last one has no next struct */
341}
342
343/***************************************************************************
344 *
345 * initialize();
346 *
347 * Called in the first dmalloc(). Inits a few memory things.
348 *
349 **************************************************************************/
350static void initialize(void)
351{
352#ifdef ROCKBOX
353 unsigned
354#endif /* ROCKBOX */
355 int i;
356 /* Setup the nmax and fragsize fields of the top structs */
357 for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) {
358 top[i].fragsize = qinfo[i];
359 top[i].nmax = DMEM_BLOCKSIZE/qinfo[i];
360
361#ifdef PSOS
362 /* for some reason, these aren't nulled from start: */
363 top[i].chain = NULL; /* no BLOCKS */
364 top[i].nfree = 0; /* no FRAGMENTS */
365#endif
366#ifdef SEMAPHORE
367 {
368 char name[7];
369 sprintf(name, "MEM%d", i);
370 SEMAPHORECREATE(name, top[i].semaphore_id);
371 /* doesn't matter if it failed, we continue anyway ;-( */
372 }
373#endif
374 }
375 initialized = 1;
376}
377
378/****************************************************************************
379 *
380 * FragFromBlock()
381 *
382 * This should return a fragment from the block and mark it as used
383 * accordingly.
384 *
385 ***************************************************************************/
386
387static void *FragFromBlock(struct MemBlock *block)
388{
389 /* make frag point to the first free FRAGMENT */
390 struct MemFrag *frag = block->first;
391 struct MemInfo *mem = (struct MemInfo *)frag;
392
393 /*
394 * Remove the FRAGMENT from the list and decrease the free counters.
395 */
396 block->first = frag->next; /* new first free FRAGMENT */
397
398 block->nfree--; /* BLOCK counter */
399 block->top->nfree--; /* TOP counter */
400
401 /* heal the FRAGMENT list */
402 if(frag->prev) {
403 frag->prev->next = frag->next;
404 }
405 if(frag->next) {
406 frag->next->prev = frag->prev;
407 }
408 mem->block = block; /* no block bit set here */
409
410 return ((char *)mem)+sizeof(struct MemInfo);
411}
412
413/***************************************************************************
414 *
415 * dmalloc()
416 *
417 * This needs no explanation. A malloc() look-alike.
418 *
419 **************************************************************************/
420
421void *dmalloc(size_t size)
422{
423 void *mem;
424
425 DBG(("dmalloc(%d)\n", size));
426
427 if(!initialized)
428 initialize();
429
430 /* First, we make room for the space needed in every allocation */
431 size += sizeof(struct MemInfo);
432
433 if(size < DMEM_LARGESTSIZE) {
434 /* get a FRAGMENT */
435
436 struct MemBlock *block=NULL; /* SAFE */
437 struct MemBlock *newblock=NULL; /* SAFE */
438 struct MemTop *memtop=NULL; /* SAFE */
439
440 /* Determine which queue to use */
441#ifdef ROCKBOX
442 unsigned
443#endif /* ROCKBOX */
444 int queue;
445
446 for(queue=0; size > qinfo[queue]; queue++)
447 ;
448 do {
449 /* This is the head master of our chain: */
450 memtop = &top[queue];
451
452 DBG(("Top info: %p %d %d %d\n",
453 memtop->chain,
454 memtop->nfree,
455 memtop->nmax,
456 memtop->fragsize));
457
458#ifdef SEMAPHORE
459 if(SEMAPHOREOBTAIN(memtop->semaphore_id))
460 return NULL; /* failed somehow */
461#endif
462
463 /* get the first BLOCK in the chain */
464 block = memtop->chain;
465
466 /* check if we have a free FRAGMENT */
467 if(memtop->nfree) {
468 /* there exists a free FRAGMENT in this chain */
469
470 /* I WANT THIS LOOP OUT OF HERE! */
471
472 /* search for the free FRAGMENT */
473 while(!block->nfree)
474 block = block->next; /* check next BLOCK */
475
476 /*
477 * Now 'block' is the first BLOCK with a free FRAGMENT
478 */
479
480 mem = FragFromBlock(block);
481
482 }
483 else {
484 /* we do *not* have a free FRAGMENT but need to get us a new BLOCK */
485
486 DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock),
487 newblock,
488 struct MemBlock *);
489 if(!newblock) {
490 if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) {
491 /* There are queues for bigger FRAGMENTS that we should check
492 before we fail this for real */
493#ifdef DEBUG
494 printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue);
495#endif
496 mem = NULL;
497 }
498 else {
499 dmalloc_failed(size- sizeof(struct MemInfo));
500 return NULL; /* not enough memory */
501 }
502 }
503 else {
504 /* allocation of big BLOCK was successful */
505
506 MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
507
508 memtop->chain = newblock; /* attach this BLOCK to the chain */
509 newblock->next = block; /* point to the previous first BLOCK */
510 if(block)
511 block->prev = newblock; /* point back on this new BLOCK */
512 newblock->prev = NULL; /* no previous */
513 newblock->top = memtop; /* our head master */
514
515 /* point to the new first FRAGMENT */
516 newblock->first = (struct MemFrag *)
517 ((char *)newblock+sizeof(struct MemBlock));
518
519 /* create FRAGMENTS of the BLOCK: */
520 FragBlock((char *)newblock->first, memtop->fragsize);
521
522#if defined(DEBUG) && !defined(BMALLOC)
523 checkmem((char *)newblock);
524#endif
525
526 /* fix the nfree counters */
527 newblock->nfree = memtop->nmax;
528 memtop->nfree += memtop->nmax;
529
530 /* get a FRAGMENT from the BLOCK */
531 mem = FragFromBlock(newblock);
532 }
533 }
534#ifdef SEMAPHORE
535 SEMAPHORERETURN(memtop->semaphore_id); /* let it go */
536#endif
537 } while(NULL == mem); /* if we should retry a larger FRAGMENT */
538 }
539 else {
540 /* get a stand-alone BLOCK */
541 struct MemInfo *meminfo;
542
543 if(size&1)
544 /* don't leave this with an odd size since we'll use that bit for
545 information */
546 size++;
547
548 DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *);
549
550 if(meminfo) {
551 MEMINCR(meminfo, size);
552 meminfo->block = (void *)(size|BLOCK_BIT);
553 mem = (char *)meminfo + sizeof(struct MemInfo);
554 }
555 else {
556 dmalloc_failed(size);
557 mem = NULL;
558 }
559 }
560 return (void *)mem;
561}
562
563/***************************************************************************
564 *
565 * dfree()
566 *
567 * This needs no explanation. A free() look-alike.
568 *
569 **************************************************************************/
570
571void dfree(void *memp)
572{
573 struct MemInfo *meminfo = (struct MemInfo *)
574 ((char *)memp- sizeof(struct MemInfo));
575
576 DBG(("dfree(%p)\n", memp));
577
578 if(!((size_t)meminfo->block&BLOCK_BIT)) {
579 /* this is a FRAGMENT we have to deal with */
580
581 struct MemBlock *block=meminfo->block;
582 struct MemTop *memtop = block->top;
583
584#ifdef SEMAPHORE
585 SEMAPHOREOBTAIN(memtop->semaphore_id);
586#endif
587
588 /* increase counters */
589 block->nfree++;
590 memtop->nfree++;
591
592 /* is this BLOCK completely empty now? */
593 if(block->nfree == memtop->nmax) {
594 /* yes, return the BLOCK to the system */
595 if(block->prev)
596 block->prev->next = block->next;
597 else
598 memtop->chain = block->next;
599 if(block->next)
600 block->next->prev = block->prev;
601
602 memtop->nfree -= memtop->nmax; /* total counter subtraction */
603 MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
604 DMEM_OSFREEMEM((void *)block); /* return the whole block */
605 }
606 else {
607 /* there are still used FRAGMENTS in the BLOCK, link this one
608 into the chain of free ones */
609 struct MemFrag *frag = (struct MemFrag *)meminfo;
610 frag->prev = NULL;
611 frag->next = block->first;
612 if(block->first)
613 block->first->prev = frag;
614 block->first = frag;
615 }
616#ifdef SEMAPHORE
617 SEMAPHORERETURN(memtop->semaphore_id);
618#endif
619 }
620 else {
621 /* big stand-alone block, just give it back to the OS: */
622 MEMDECR(&meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */
623 DMEM_OSFREEMEM((void *)meminfo);
624 }
625}
626
627/***************************************************************************
628 *
629 * drealloc()
630 *
631 * This needs no explanation. A realloc() look-alike.
632 *
633 **************************************************************************/
634
635void *drealloc(char *ptr, size_t size)
636{
637 struct MemInfo *meminfo = (struct MemInfo *)
638 ((char *)ptr- sizeof(struct MemInfo));
639 /*
640 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
641 * NOTE: the ->size field of the meminfo will now contain the MemInfo
642 * struct size too!
643 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
644 */
645 void *mem=NULL; /* SAFE */
646 size_t prevsize = 0;
647
648 /* NOTE that this is only valid if BLOCK_BIT isn't set: */
649 struct MemBlock *block;
650
651 DBG(("drealloc(%p, %d)\n", ptr, size));
652
653 if(NULL == ptr)
654 return dmalloc( size );
655
656 block = meminfo->block;
657
658 if(!((size_t)meminfo->block&BLOCK_BIT) &&
659 (size + sizeof(struct MemInfo) <
660 (prevsize = block->top->fragsize) )) {
661 /* This is a FRAGMENT and new size is possible to retain within the same
662 FRAGMENT */
663 if((prevsize > qinfo[0]) &&
664 /* this is not the smallest memory Q */
665 (size < (block->top-1)->fragsize))
666 /* this fits in a smaller Q */
667 ;
668 else
669 mem = ptr; /* Just return the same pointer as we got in. */
670 }
671 if(!mem) {
672 /* This is a stand-alone BLOCK or a realloc that no longer fits within
673 the same FRAGMENT */
674
675 if((size_t)meminfo->block&BLOCK_BIT) {
676 prevsize = ((size_t)meminfo->block&~BLOCK_BIT) -
677 sizeof(struct MemInfo);
678 }
679 else
680 prevsize -= sizeof(struct MemInfo);
681
682 /* No tricks involved here, just grab a new bite of memory, copy the data
683 * from the old place and free the old memory again. */
684 mem = dmalloc(size);
685 if(mem) {
686 memcpy(mem, ptr, MIN(size, prevsize) );
687 dfree(ptr);
688 }
689 }
690 return mem;
691}
692
693/***************************************************************************
694 *
695 * dcalloc()
696 *
697 * This needs no explanation. A calloc() look-alike.
698 *
699 **************************************************************************/
700/* Allocate an array of NMEMB elements each SIZE bytes long.
701 The entire array is initialized to zeros. */
702void *
703dcalloc (size_t nmemb, size_t size)
704{
705 void *result = dmalloc (nmemb * size);
706
707 if (result != NULL)
708 memset (result, 0, nmemb * size);
709
710 return result;
711}
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 @@
1void *dmalloc(size_t);
2void dfree(void *);
3void *drealloc(void *, size_t);
4
5#define malloc(x) dmalloc(x)
6#define free(x) dfree(x)
7#define realloc(x,y) drealloc(x,y)
8
9#ifdef ROCKBOX
10void *dcalloc(size_t, size_t);
11#define calloc(x,y) dcalloc(x,y)
12#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 @@
1#include <stdio.h>
2#include <stdlib.h>
3
4#include "dmalloc.h"
5
6#define MAX 500
7#define MAX2 1000
8#define MAXC 2
9
10#define TESTA
11#define TESTB
12#define TESTC
13#define TESTD
14
15int main(int argc, char **argv)
16{
17 int i;
18 int memory = 0;
19
20#ifdef BMALLOC
21#define HEAP 10000
22 void *heap = (malloc)(HEAP);
23 if(!heap)
24 return -1;
25 add_pool(heap, HEAP);
26#endif
27
28 {
29#define MAXK 100
30 void *wow[MAXK];
31 wow[0]=malloc(700);
32 realloc(wow[0], 680);
33 return 0;
34
35 for(i=0; i<MAXK; i++)
36 if(!(wow[i]=malloc(412))) {
37 printf("*** Couldn't allocated memory, exiting\n");
38 return -2;
39 }
40 for(i=MAXK-1; i>=0; i-=2)
41 free(wow[i]);
42 return 0;
43 }
44
45
46#ifdef TESTD
47 {
48#define MAXS 10
49#define MAXS1 0
50 void *ptr[MAXS];
51
52 for(i=MAXS1; i< MAXS; i++) {
53 printf("%d malloc(%d)\n", i, i*55);
54 ptr[i] = malloc (i*55);
55 }
56 for(i=MAXS1; i< MAXS; i++) {
57 void *tmp;
58 printf("%d realloc(%d)\n", i, i*155);
59 tmp=realloc(ptr[i], i*155);
60 if(tmp)
61 ptr[i] = tmp;
62 }
63 for(i=MAXS1; i< MAXS; i++) {
64 printf("%d free(%d)\n", i, i*155);
65 free(ptr[i]);
66 }
67 }
68#endif
69
70#ifdef TESTC
71 {
72 void *ptr[MAXC];
73 printf("This is test C:\n");
74
75 for(i=0; i< MAXC; i++) {
76 printf("%d malloc(100)\n", i+1);
77 ptr[i] = malloc(100);
78 printf(" ...returned %p\n", ptr[i]);
79 }
80
81 for(i=0; i< MAXC; i++) {
82 printf("%d free()\n", i+1);
83 free(ptr[i]);
84 }
85
86 printf("End of test C:\n");
87 }
88#endif
89
90#ifdef TESTA
91 {
92 void *pointers[MAX];
93 printf("This is test I:\n");
94
95 for(i=0; i<MAX; i++) {
96 printf("%d attempts malloc(%d)\n", i, i*6);
97 pointers[i]=malloc(i*6);
98 if(!pointers[i]) {
99 printf("cant get more memory!");
100 return(0);
101 }
102 memory += (i*6);
103 }
104 printf("\namount: %d\n", memory);
105 memory = 0;
106 for(i=0; i<MAX; i++) {
107 printf("%d attempts realloc(%d)\n", i, i*7);
108 pointers[i]=realloc(pointers[i], i*7);
109 memory += i*7;
110 }
111 printf("\namount: %d\n", memory);
112 for(i=0; i<MAX; i++) {
113 printf("%d attempts free(%d)\n", i, i*7);
114 free(pointers[i]);
115 }
116 printf("\nend of test 1\n");
117 }
118#endif
119#ifdef TESTB
120 {
121 void *pointers2[MAX2];
122 memory = 0;
123 printf("\nTest II\n");
124 for(i=0; i< MAX2; i++) {
125/* printf("%d attempts malloc(%d)\n", i, 7); */
126 pointers2[i] = malloc(7);
127 memory += 7;
128 }
129 printf("\namount: %d\n", memory);
130 for(i=0; i< MAX2; i++) {
131 free(pointers2[i]);
132 }
133 printf("\nend of test II\n");
134
135 }
136#endif
137 return 0;
138}
diff --git a/apps/plugins/pdbox/dbestfit-3.3/malloc.man b/apps/plugins/pdbox/dbestfit-3.3/malloc.man
deleted file mode 100644
index 8b6e3dbea5..0000000000
--- a/apps/plugins/pdbox/dbestfit-3.3/malloc.man
+++ /dev/null
@@ -1,95 +0,0 @@
1MALLOC(3V) C LIBRARY FUNCTIONS MALLOC(3V)
2
3
4NAME
5 malloc, free, realloc, calloc
6
7SYNOPSIS
8 #include <malloc.h>
9
10 void *malloc(size)
11 size_t size;
12
13 void free(ptr)
14 void *ptr;
15
16 void *realloc(ptr, size)
17 void *ptr;
18 size_t size;
19
20 void *calloc(nelem, elsize)
21 size_t nelem;
22 size_t elsize;
23
24DESCRIPTION
25 These routines provide a general-purpose memory allocation
26 package. They maintain a table of free blocks for efficient
27 allocation and coalescing of free storage. When there is no
28 suitable space already free, the allocation routines call
29 rn_getseg() to get more memory from the system.
30
31 Each of the allocation routines returns a pointer to space
32 suitably aligned for storage of any type of object. Each
33 returns a NULL pointer if the request cannot be completed
34 (see DIAGNOSTICS).
35
36 malloc() returns a pointer to a block of at least size
37 bytes, which is appropriately aligned.
38
39 free() releases a previously allocated block. Its argument
40 is a pointer to a block previously allocated by malloc(),
41 calloc() or realloc().
42
43 realloc() changes the size of the block referenced by ptr to
44 size bytes and returns a pointer to the (possibly moved)
45 block. The contents will be unchanged up to the lesser of
46 the new and old sizes. If unable to honor a reallocation
47 request, realloc() leaves its first argument unaltered.
48
49 **** DMALLOC DOES NOT COMPLY WITH THE PARAGRAPH BELOW ****
50
51 For backwards compatibility, realloc() accepts a pointer to a
52 block freed since the most recent call to malloc(), cal-
53 loc() or realloc().
54
55 Note: using realloc() with a block freed before the most recent
56 call to malloc(), calloc() or realloc() is an error.
57
58 calloc() uses malloc() to allocate space for an array of
59 nelem elements of size elsize, initializes the space to
60 zeros, and returns a pointer to the initialized block. The
61 block should be freed with free().
62
63
64 malloc() and realloc() return a non- NULL pointer if size is 0,
65 and calloc() returns a non-NULL pointer if nelem or elsize is 0,
66 but these pointers should not be dereferenced.
67
68 Note: Always cast the value returned by malloc(), realloc() or
69 calloc().
70
71
72RETURN VALUES On success, malloc(), calloc() and realloc() return a
73 pointer to space suitably aligned for storage of any type of
74 object. On failure, they return NULL.
75
76 free() does not return a value.
77
78
79NOTES
80 Because malloc() and realloc() return a non-NULL pointer if size
81 is 0, and calloc() returns a non-NULL pointer if nelem or elsize
82 is 0, a zero size need not be treated as a special case if it
83 should be passed to these functions unpredictably. Also, the
84 pointer returned by these functions may be passed to subsequent
85 invocations of realloc().
86
87
88BUGS
89
90 **** DMALLOC DOES NOT COMPLY WITH THE PARAGRAPH BELOW ****
91
92 Since realloc() accepts a pointer to a block freed since the last
93 call to malloc(), calloc() or realloc(), a degradation of
94 performance results. The semantics of free() should be changed
95 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 @@
1#include <stdio.h>
2#include <stdlib.h>
3
4#include "bmalloc.h"
5
6int main(int argc, char **argv)
7{
8 void *pointers[5];
9 int i;
10 void *area;
11
12 for(i=0; i<5; i++)
13 pointers[i] = malloc(8000);
14
15 if(argc>1) {
16 switch(argv[1][0]) {
17 case '1':
18 for(i=0; i<5; i++) {
19 add_pool(pointers[i], 4000);
20 add_pool((char *)pointers[i]+4000, 4000);
21 }
22 break;
23 case '2':
24 area = malloc(20000);
25 add_pool(area, 3000);
26 add_pool((char *)area+6000, 3000);
27 add_pool((char *)area+3000, 3000);
28 add_pool((char *)area+12000, 3000);
29 add_pool((char *)area+9000, 3000);
30 break;
31 case '3':
32 {
33 void *ptr[10];
34 area = malloc(20000);
35 add_pool(area, 20000);
36
37 printf(" ** TEST USAGE\n");
38 for(i=0; i<9; i++)
39 ptr[i]=bmalloc(200);
40 print_lists();
41 for(i=0; i<9; i++)
42 bfree(ptr[i]);
43 printf(" ** END OF TEST USAGE\n");
44 }
45
46 break;
47 case '4':
48 {
49 void *ptr[10];
50 area = malloc(20000);
51 add_pool(area, 20000);
52
53 ptr[0]=bmalloc(4080);
54 print_lists();
55 bfree(ptr[0]);
56 printf(" ** END OF TEST USAGE\n");
57 }
58
59 break;
60 }
61 }
62 else
63 for(i=4; i>=0; i--)
64 add_pool(pointers[i], 8000-i*100);
65
66 print_lists();
67
68 return 0;
69}
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 @@
1 =====================================
2 Memory Allocation Algorithm Theories.
3 =====================================
4
5GOAL
6 It is intended to be a 100% working memory allocation system. It should be
7 capable of replacing an ordinary Operating System's own routines. It should
8 work good in a multitasking, shared memory, non-virtual memory environment
9 without clogging the memory. Primary aimed for small machines, CPUs and
10 memory amounts.
11
12 I use a best-fit algorithm with a slight overhead in order to increase speed
13 a lot. It should remain scalable and work good with very large amount of
14 memory and free/used memory blocks too.
15
16TERMINOLOGY
17
18 FRAGMENT - small identically sized parts of a larger BLOCK, they are when
19 travered in lists etc _not_ allocated.
20 BLOCK - large memory area, if used for FRAGMENTS, they are linked in a
21 lists. One list for each FRAGMENT size supported.
22 TOP - head struct that holds information about and points to a chain
23 of BLOCKS for a particular FRAGMENT size.
24 CHUNK - a contiguous area of free memory
25
26MEMORY SYSTEM
27
28 We split the system in two parts. One part allocates small memory amounts
29 and one part allocates large memory amounts, but all allocations are done
30 "through" the small-part-system. There is an option to use only the small
31 system (and thus use the OS for large blocks) or the complete package.
32
33##############################################################################
34 SMALL SIZE ALLOCATIONS
35##############################################################################
36
37 Keywords for this system is 'Deferred Coalescing' and 'quick lists'.
38
39 ALLOC
40
41 * Small allocations are "aligned" upwards to a set of preset sizes. In the
42 current implementation I use 20, 28, 52, 116, 312, 580, 812, 2028 bytes.
43 Memory allocations of these sizes are refered to as FRAGMENTS.
44 (The reason for these specific sizes is the requirement that they must be
45 32-bit aligned and fit as good as possible within 4060 bytes.)
46
47 * Allocations larger than 2028 will get a BLOCK for that allocation only.
48
49 * Each of these sizes has it's own TOP. When a FRAGMENT is requested, a
50 larger BLOCK will be allocated and divided into many FRAGMENTS (all of the
51 same size). TOP points to a list with BLOCKS that contains FRAGMENTS of
52 the same size. Each BLOCK has a 'number of free FRAGMENTS' counter and so
53 has each TOP (for the entire chain).
54
55 * A BLOCK is around 4060 bytes plus the size of the information header. This
56 size is adjusted to make the allocation of the big block not require more
57 than 4096 bytes. (This might not be so easy to be sure of, if you don't
58 know how the big-block system works, but the BMALLOC system uses an
59 extra header of 12 bytes and the header for the FRAGMENT BLOCK is 20 bytes
60 in a general 32-bit unix environment.)
61
62 * In case the allocation of a BLOCK fails when a FRAGMENT is required, the
63 next size of FRAGMENTS will be checked for a free FRAGMENT. First when the
64 larger size lists have been tested without success it will fail for real.
65
66 FREE
67
68 * When FRAGMENTS are freed so that a BLOCK becomes non-used, it is returned
69 to the system.
70
71 * FREEing a fragment adds the buffer in a LIFO-order. That means that the
72 next request for a fragment from the same list, the last freed buffer will
73 be returned first.
74
75 REALLOC
76
77 * REALLOCATION of a FRAGMENT does first check if the new size would fit
78 within the same FRAGMENT and if it would use the same FRAGMENT size. If it
79 does and would, the same pointer is returned.
80
81 OVERHEAD
82
83 Yes, there is an overhead on small allocations (internal fragmentation).
84 Yet, I do believe that small allocations more often than larger ones are
85 used dynamically. I believe that a large overhead is not a big problem if it
86 remains only for a while. The big gain is with the extreme speed we can GET
87 and RETURN small allocations. This has yet to be proven. I am open to other
88 systems of dealing with the small ones, but I don`t believe in using the
89 same system for all sizes of allocations.
90
91 IMPROVEMENT
92
93 An addition to the above described algorithm is the `save-empty-BLOCKS-a-
94 while-afterwards`. It will be used when the last used FRAGMENT within a
95 BLOCK is freed. The BLOCK will then not get returned to the system until "a
96 few more" FRAGMENTS have been freed in case the last [few] freed FRAGMENTS
97 are allocated yet again (and thus prevent the huge overhead of making
98 FRAGMENTS in a BLOCK). The "only" drawback of such a SEBAWA concept is
99 that it would mean an even bigger overhead...
100
101 HEADERS (in allocated data)
102
103 FRAGMENTS - 32-bit pointer to its parent BLOCK (lowest bit must be 0)
104 BLOCK - 32-bit size (lowest bit must be 1 to separate this from
105 FRAGMENTS)
106
107##############################################################################
108 LARGER ALLOCATIONS
109##############################################################################
110
111 If the requested size is larger than the largest FRAGMENT size supported,
112 the allocation will be made for this memory area alone, or if a BLOCK is
113 allocated to fit lots of FRAGMENTS a large block is also desired.
114
115 * We add memory to the "system" with the add_pool() function call. It
116 specifies the start and size of the new block of memory that will be
117 used in this memory allocation system. Several add_pool() calls are
118 supported and they may or may not add contiguous memory.
119
120 * Make all blocks get allocated aligned to BLOCKSIZE (sometimes referred to
121 as 'grain size'), 64 bytes in my implementation. Reports tell us there is
122 no real gain in increasing the size of the align.
123
124 * We link *all* pieces of memory (AREAS), free or not free. We keep the list
125 in address order and thus when a FREE() occurs we know instanstly if there
126 are FREE CHUNKS wall-to-wall. No list "travels" needed. Requires some
127 extra space in every allocated BLOCK. Still needs to put the new CHUNK in
128 the right place in size-sorted list/tree. All memory areas, allocated or
129 not, contain the following header:
130 - size of this memory area
131 - FREE status
132 - pointer to the next AREA closest in memory
133 - pointer to the prev AREA closest in memory
134 (12 bytes)
135
136 * Sort all FREE CHUNKS in size-order. We use a SPLAY TREE algorithm for
137 maximum speed. Data/structs used for the size-sorting functions are kept
138 in an abstraction layer away from this since it is really not changing
139 anything (except executing speed).
140
141 ALLOC (RSIZE - requested size, aligned properly)
142
143 * Fetch a CHUNK that RSIZE fits within. If the found CHUNK is larger than
144 RSIZE, split it and return the RSIZE to the caller. Link the new CHUNK
145 into the list/tree.
146
147 FREE (AREA - piece of memory that is returned to the system)
148
149 * Since the allocated BLOCK has kept its link-pointers, we can without
150 checking any list instantly see if there are any FREE CHUNKS that are
151 wall-to-wall with the AREA (both sides). If the AREA *is* wall-to-wall
152 with one or two CHUNKS that or they are unlinked from the lists, enlarged
153 and re-linked into the lists.
154
155 REALLOC
156
157 * There IS NO realloc() of large blocks, they are performed in the higher
158 layer (dmalloc).
159
160
161##############################################################################
162 FURTHER READING
163##############################################################################
164
165 * "Dynamic Storage Allocation: A Survey and Critical Review" (Paul R. Wilson,
166 Mark S. Johnstone, Michael Neely, David Boles)
167 ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps
168
169 * "A Memory Allocator" (Doug Lea)
170 http://g.oswego.edu/dl/html/malloc.html
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-25 15:14:40 +0000