summaryrefslogtreecommitdiff
path: root/apps/plugins/pdbox/dbestfit-3.3
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/pdbox/dbestfit-3.3')
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/CHANGES24
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/FILES30
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/Makefile76
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/Malloc.c402
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/README44
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bmalloc.c740
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bmalloc.h12
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bysize.c848
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bysize.h8
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmalloc.c1380
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmalloc.h16
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmytest.c276
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/malloc.man190
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/mytest.c140
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/thoughts340
15 files changed, 4526 insertions, 0 deletions
diff --git a/apps/plugins/pdbox/dbestfit-3.3/CHANGES b/apps/plugins/pdbox/dbestfit-3.3/CHANGES
new file mode 100644
index 0000000000..f244f66f87
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/CHANGES
@@ -0,0 +1,24 @@
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.
13Changes
14
15* (March 30 2005) Daniel
16
17 Linus Nielsen Feltzing provided a patch that corrected several minor problems
18 that prevented dbestfit from working good. Linus also tested and timed
19 dbestfit for real in a target where he replaced the pSOS-provided memory
20 subsystem.
21
22* 3.2
23
24 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
new file mode 100644
index 0000000000..684a225972
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/FILES
@@ -0,0 +1,30 @@
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
16/bysize.c
17/bysize.h
18/bmalloc.c
19/bmalloc.h
20/dmalloc.c
21/dmalloc.h
22/FILES
23/README
24/Makefile
25/Malloc.c
26/mytest.c
27/dmytest.c
28/thoughts
29/malloc.man
30/CHANGES
diff --git a/apps/plugins/pdbox/dbestfit-3.3/Makefile b/apps/plugins/pdbox/dbestfit-3.3/Makefile
new file mode 100644
index 0000000000..e34b02e918
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/Makefile
@@ -0,0 +1,76 @@
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)
39
40OBJS1 = bmalloc.o bysize.o mytest.o
41TARGET1 = mytest
42
43OBJS2 = dmalloc.o bmalloc.o bysize.o Malloc.o
44TARGET2 = mtest
45
46OBJS3 = dmalloc.o bmalloc.o bysize.o dmytest.o
47TARGET3 = dmytest
48
49CFLAGS = -g -DUNIX -DBMALLOC -Wall -pedantic -DDEBUG
50CC = gcc
51
52all: $(TARGET1) $(TARGET2) $(TARGET3)
53
54$(TARGET1): $(OBJS1)
55 $(CC) -g -o $(TARGET1) $(OBJS1)
56
57$(TARGET2): $(OBJS2)
58 $(CC) -g -o $(TARGET2) $(OBJS2)
59
60$(TARGET3): $(OBJS3)
61 $(CC) -g -o $(TARGET3) $(OBJS3)
62
63bmalloc.o: bmalloc.c
64dmalloc.o: dmalloc.c
65mytest.o: mytest.c
66dmytest.o: dmytest.c
67Malloc.o : Malloc.c
68bysize.o : bysize.c
69
70tgz:
71 @(dir=`pwd`;name=`basename $$dir`;echo Creates $$name.tar.gz; cd .. ; \
72 tar -cf $$name.tar `cat $$name/FILES | sed "s:^/:$$name/:g"` ; \
73 gzip $$name.tar ; chmod a+r $$name.tar.gz ; mv $$name.tar.gz $$name/)
74
75clean:
76 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
new file mode 100644
index 0000000000..25e30706fe
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/Malloc.c
@@ -0,0 +1,402 @@
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}
201
202#include <stdio.h>
203#include <stdlib.h>
204#include <string.h>
205#include <time.h>
206
207/* Storleken på allokeringen bestäms genom att först slumpas en position i
208"size_table" ut, sedan slumpas en storlek mellan den postionen och nästa värde
209i tabellen. Genom att ha tabellen koncentrerad med låga värden, så skapas
210flest såna. Rutinen håller på tills minnet en allokeringen nekas. Den kommer
211aldrig att ha mer än MAXIMAL_MEMORY_TO_ALLOCATE allokerat samtidigt. Maximalt
212har den MAX_ALLOCATIONS allokeringar samtidigt.
213
214Statistiskt sätt så kommer efter ett tag MAX_ALLOCATIONS/2 allokeringar finnas
215samtidigt, med varje allokering i median med värdet av halva "size_table".
216
217När minnet är slut (malloc()=NULL), frågas användaren om han ska fortsätta.
218
219Med jämna mellanrum skrivs statisktik ut på skärmen. (DISPLAY_WHEN)
220
221För att stressa systemet med fler små allokeringar, så kan man öka
222MAX_ALLOCATIONS. AMOUNT_OF_MEMORY bör få den att slå i taket fortare om man
223minskar det.
224
225Ingen initiering görs av slumptalen, så allt är upprepbart (men plocka bort
226kommentaren på srand() och det löser sig.
227
228*/
229
230/*#undef BMALLOC*/
231
232#ifdef BMALLOC
233#include "dmalloc.h"
234
235#include "bmalloc.h"
236#endif
237
238#define MAX_ALLOCATIONS 100000
239#define AMOUNT_OF_MEMORY 180000 /* bytes */
240#define MAXIMAL_MEMORY_TO_ALLOCATE 100000 /* Sätt den här högre än
241 AMOUNT_OF_MEMORY, och malloc() bör
242 returnera NULL förr eller senare */
243
244#define DISPLAY_WHEN (123456) /* When to display statistic */
245
246#define min(a, b) (((a) < (b)) ? (a) : (b))
247#define BOOL char
248#define TRUE 1
249#define FALSE 0
250
251typedef struct {
252 char *memory;
253 long size;
254 char filled_with;
255 long table_position;
256} MallocStruct;
257
258/*
259Skapar en lista med MAX_ALLOCATIONS storlek där det slumpvis allokeras
260eller reallokeras i.
261*/
262
263MallocStruct my_mallocs[MAX_ALLOCATIONS];
264
265long 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};
266#define TABLESIZE ((sizeof(size_table)-1)/sizeof(long))
267long size_allocs[TABLESIZE];
268
269int main(void)
270{
271 int i;
272 long count=-1;
273 long count_free=0, count_malloc=0, count_realloc=0;
274 long total_memory=0;
275 BOOL out_of_memory=FALSE;
276 unsigned int seed = time( NULL );
277
278#ifdef BMALLOC
279 void *thisisourheap;
280 thisisourheap = (malloc)(AMOUNT_OF_MEMORY);
281 if(!thisisourheap)
282 return -1; /* can't get memory */
283 add_pool(thisisourheap, AMOUNT_OF_MEMORY);
284#endif
285
286 seed = 1109323906;
287
288 srand( seed ); /* Initialize randomize */
289
290 printf("seed: %d\n", seed);
291
292 while (!out_of_memory) {
293 long number=rand()%MAX_ALLOCATIONS;
294 long size;
295 long table_position=rand()%TABLESIZE;
296 char fill_with=rand()&255;
297
298 count++;
299
300 size=rand()%(size_table[table_position+1]-size_table[table_position])+size_table[table_position];
301
302/* fprintf(stderr, "number %d size %d\n", number, size); */
303
304 if (my_mallocs[number].size) { /* Om allokering redan finns på den här
305 positionen, så reallokerar vi eller
306 friar. */
307 long old_size=my_mallocs[number].size;
308 if (my_mallocs[number].size && fill_with<40) {
309 free(my_mallocs[number].memory);
310 total_memory -= my_mallocs[number].size;
311 count_free++;
312 size_allocs[my_mallocs[number].table_position]--;
313 size=0;
314 my_mallocs[number].size = 0;
315 my_mallocs[number].memory = NULL;
316 } else {
317 /*
318 * realloc() part
319 *
320 */
321 char *temp;
322#if 0
323 if(my_mallocs[number].size > size) {
324 printf("*** %d is realloc()ed to %d\n",
325 my_mallocs[number].size, size);
326 }
327#endif
328 if (total_memory-old_size+size>MAXIMAL_MEMORY_TO_ALLOCATE)
329 goto output; /* for-loop */
330 temp = (char *)realloc(my_mallocs[number].memory, size);
331 if (!temp)
332 out_of_memory=TRUE;
333 else {
334 my_mallocs[number].memory = temp;
335
336 my_mallocs[number].size=size;
337 size_allocs[my_mallocs[number].table_position]--;
338 size_allocs[table_position]++;
339 total_memory -= old_size;
340 total_memory += size;
341 old_size=min(old_size, size);
342 while (--old_size>0) {
343 if (my_mallocs[number].memory[old_size]!=my_mallocs[number].filled_with)
344 fprintf(stderr, "Wrong filling!\n");
345 }
346 count_realloc++;
347 }
348 }
349 } else {
350 if (total_memory+size>MAXIMAL_MEMORY_TO_ALLOCATE) {
351 goto output; /* for-loop */
352 }
353 my_mallocs[number].memory=(char *)malloc(size); /* Allokera! */
354 if (!my_mallocs[number].memory)
355 out_of_memory=TRUE;
356 else {
357 size_allocs[table_position]++;
358 count_malloc++;
359 total_memory += size;
360 }
361 }
362
363 if(!out_of_memory) {
364 my_mallocs[number].table_position=table_position;
365 my_mallocs[number].size=size;
366 my_mallocs[number].filled_with=fill_with;
367 memset(my_mallocs[number].memory, fill_with, size);
368 }
369 output:
370 if (out_of_memory || !(count%DISPLAY_WHEN)) {
371 printf("(%d) malloc %d, realloc %d, free %d, total size %d\n", count, count_malloc, count_realloc, count_free, total_memory);
372 {
373 int count;
374 printf("[size bytes]=[number of allocations]\n");
375 for (count=0; count<TABLESIZE; count++) {
376 printf("%ld=%ld, ", size_table[count], size_allocs[count]);
377 }
378 printf("\n\n");
379 }
380 }
381 if (out_of_memory) {
382 fprintf(stderr, "Memory is out! Continue (y/n)");
383 switch (getchar()) {
384 case 'y':
385 case 'Y':
386 out_of_memory=FALSE;
387 break;
388 }
389 fprintf(stderr, "\n");
390 }
391 }
392 for(i = 0;i < MAX_ALLOCATIONS;i++) {
393 if((my_mallocs[i].memory))
394 free(my_mallocs[i].memory);
395 }
396
397 print_lists();
398
399 printf("\n");
400 return 0;
401}
402
diff --git a/apps/plugins/pdbox/dbestfit-3.3/README b/apps/plugins/pdbox/dbestfit-3.3/README
new file mode 100644
index 0000000000..919875df96
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/README
@@ -0,0 +1,44 @@
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).
22
23Package: dbestfit - a dynamic memory allocator
24Date: March 30, 2005
25Version: 3.3
26Author: Daniel Stenberg <daniel@haxx.se>
27
28 I wrote the dmalloc part for small allocation sizes to improve the behavior
29of the built-in (first-fit) allocator found in pSOS (around 1996).
30
31 I wrote the bmalloc part (best-fit with splay-tree sorting) just for the fun
32of it and to see how good malloc() clone I could make. The quality of my
33implementation is still left to be judged in real-world tests.
34
35TODO:
36 * Remove the final not-so-very-nice loop in dmalloc.c that checks for a block
37 with free fragments (when the list gets longer too much time might be spent
38 in that loop).
39
40 * Add semaphore protection in bmalloc.
41
42 * Make a separate application that samples the memory usage of a program
43 and is capable of replaying it (in order to test properly).
44
diff --git a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c
new file mode 100644
index 0000000000..f95b4f6125
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c
@@ -0,0 +1,740 @@
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
239void print_lists()
240{
241 struct BlockInfo *block = blockHead;
242#if 1
243 printf("List of BLOCKS (in address order):\n");
244 while(block) {
245 printf(" START %p END %p SIZE %ld FLAG %s\n",
246 (char *)block,
247 (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE,
248 (block->info&INFO_FREE)?"free":"used");
249 block = block->higher;
250 }
251 printf("End of BLOCKS:\n");
252#endif
253 print_sizes();
254}
255
256void *bmalloc(size_t size)
257{
258 void *mem;
259
260#ifdef DEBUG
261 {
262 static int count=0;
263 int realsize = size + sizeof(struct BlockInfo);
264 if(realsize%4096)
265 realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
266 printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
267 }
268#endif
269
270 size += sizeof(struct BlockInfo); /* add memory for our header */
271
272 if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
273 changed if the BLOCKSIZE is not 2^X ! */
274 size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
275
276 /* get a CHUNK from the list with this size */
277 mem = obtainbysize ( size );
278 if(mem) {
279 /* the memory block we have got is the "best-fit" and it is already
280 un-linked from the free list */
281
282 /* now do the math to get the proper block pointer */
283 struct BlockInfo *block= (struct BlockInfo *)
284 ((char *)mem - sizeof(struct BlockInfo));
285
286 block->info &= ~INFO_FREE;
287 /* not free anymore */
288
289 if( size != (block->info&INFO_SIZE)) {
290 /* split this chunk into two pieces and return the one that fits us */
291 size_t othersize = (block->info&INFO_SIZE) - size;
292
293 if(othersize > BMEM_ALIGN) {
294 /* prevent losing small pieces of memory due to weird alignments
295 of the memory pool */
296
297 block->info = size; /* set new size (leave FREE bit cleared) */
298
299 /* Add the new chunk to the lists: */
300 add_blocktolists(block,
301 (struct BlockInfo *)((char *)block + size),
302 othersize );
303 }
304 }
305
306 /* Return the memory our parent may use: */
307 return (char *)block+sizeof(struct BlockInfo);
308 }
309 else {
310 bmalloc_failed(size);
311 return NULL; /* can't find any memory, fail hard */
312 }
313 return NULL;
314}
315
316void bfree(void *ptr)
317{
318 struct BlockInfo *block = (struct BlockInfo *)
319 ((char *)ptr - sizeof(struct BlockInfo));
320 size_t size;
321
322 /* setup our initial higher and lower pointers */
323 struct BlockInfo *lower = block->lower;
324 struct BlockInfo *higher = block->higher;
325
326#ifdef DEBUG
327 static int freecount=0;
328 printf("%d bfree(%p)\n", freecount++, ptr);
329#endif
330
331 /* bind together lower addressed FREE CHUNKS */
332 if(lower && (lower->info&INFO_FREE) &&
333 ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
334 size = block->info&INFO_SIZE; /* original size */
335
336 /* remove from size-link: */
337 remove_chunksize((char *)lower+sizeof(struct BlockInfo));
338
339 remove_block(block); /* unlink from address list */
340 block = lower; /* new base area pointer */
341 block->info += size; /* append the new size (the FREE bit
342 will remain untouched) */
343
344 lower = lower->lower; /* new lower pointer */
345 }
346 /* bind together higher addressed FREE CHUNKS */
347 if(higher && (higher->info&INFO_FREE) &&
348 ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) {
349 /* append higher size, the FREE bit won't be affected */
350 block->info += (higher->info&INFO_SIZE);
351
352 /* unlink from size list: */
353 remove_chunksize((char *)higher+sizeof(struct BlockInfo));
354 remove_block(higher); /* unlink from address list */
355 higher = higher->higher; /* the new higher link */
356 block->higher = higher; /* new higher link */
357 }
358 block->info |= INFO_FREE; /* consider this FREE! */
359
360 block->lower = lower;
361 block->higher = higher;
362
363 insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE);
364
365#ifdef DEBUG
366 print_lists();
367#endif
368
369}
370
371/*****************************************************************************
372 *
373 * Big (best-fit) Memory Allocation
374 *
375 * Author: Daniel Stenberg
376 * Date: March 5, 1997
377 * Version: 2.0
378 * Email: Daniel.Stenberg@sth.frontec.se
379 *
380 *
381 * Read 'thoughts' for theories and details in implementation.
382 *
383 * Routines meant to replace the most low level functions of an Operting
384 * System
385 *
386 * v2.0
387 * - Made all size-routines get moved out from this file. This way, the size
388 * functions can much more easily get replaced.
389 * - Improved how new memory blocks get added to the size-sorted list. When
390 * not adding new pools, there should never ever be any list traversing
391 * since all information is dynamically gathered.
392 *
393 ****************************************************************************/
394
395#include <stdio.h>
396#include <stdlib.h>
397
398#include "bysize.h"
399
400#ifndef TRUE
401#define TRUE 1
402#endif
403#ifndef FALSE
404#define FALSE 0
405#endif
406
407/* #define DEBUG */
408
409#define BMEM_ALIGN 64 /* resolution */
410
411#define BMEMERR_TOOSMALL -1
412
413/* this struct will be stored in all CHUNKS and AREAS */
414struct BlockInfo {
415 struct BlockInfo *lower; /* previous block in memory (lower address) */
416 struct BlockInfo *higher; /* next block in memory (higher address) */
417 unsigned long info; /* 31 bits size: 1 bit free boolean */
418#define INFO_FREE 1
419#define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */
420
421 /* FREE+SIZE Could be written to use ordinary bitfields if using a smart
422 (like gcc) compiler in a manner like:
423 int size:31;
424 int free:1;
425
426 The 'higher' pointer COULD be removed completely if the size is used as
427 an index to the higher one. This would then REQUIRE the entire memory
428 pool to be contiguous and it needs a 'terminating' "node" or an extra
429 flag that informs about the end of the list.
430 */
431};
432
433/* the BLOCK list should be sorted in a lower to higher address order */
434struct BlockInfo *blockHead=NULL; /* nothing from the start */
435
436void print_lists(void);
437
438
439/***********************************************************************
440 *
441 * remove_block()
442 *
443 * Remove the block from the address-sorted list.
444 *
445 ***********************************************************************/
446
447void remove_block(struct BlockInfo *block)
448{
449 if(block->lower)
450 block->lower->higher = block->higher;
451 else
452 blockHead = block->higher;
453 if(block->higher)
454 block->higher->lower = block->lower;
455}
456
457/****************************************************************************
458 *
459 * add_blocktolists()
460 *
461 * Adds the specified block at the specified place in the address-sorted
462 * list and at the appropriate place in the size-sorted.
463 *
464 ***************************************************************************/
465void add_blocktolists(struct BlockInfo *block,
466 struct BlockInfo *newblock,
467 size_t newsize)
468{
469 struct BlockInfo *temp; /* temporary storage variable */
470 if(block) {
471 /* `block' is now a lower address than 'newblock' */
472
473 /*
474 * Check if the new CHUNK is wall-to-wall with the lower addressed
475 * one (if *that* is free)
476 */
477 if(block->info&INFO_FREE) {
478 if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) {
479 /* yes sir, this is our lower address neighbour, enlarge that one
480 pick it out from the list and recursively add that chunk and
481 then we escape */
482
483 /* remove from size-sorted list: */
484 remove_chunksize((char*)block+sizeof(struct BlockInfo));
485
486 block->info += newsize; /* newsize is an even number and thus the FREE
487 bit is untouched */
488
489 remove_block(block); /* unlink the block address-wise */
490
491 /* recursively check our lower friend(s) */
492 add_blocktolists(block->lower, block, block->info&INFO_SIZE);
493 return;
494 }
495 }
496
497 temp = block->higher;
498
499 block->higher = newblock;
500 newblock->lower = block;
501 newblock->higher = temp;
502 if(newblock->higher)
503 newblock->higher->lower = newblock;
504 }
505 else {
506 /* this block should preceed the heading one */
507 temp = blockHead;
508
509 /* check if this is our higher addressed neighbour */
510 if((char *)newblock + newsize == (char *)temp) {
511
512 /* yes, we are wall-to-wall with the higher CHUNK */
513 if(temp->info&INFO_FREE) {
514 /* and the neighbour is even free, remove that one and enlarge
515 ourselves, call add_pool() recursively and then escape */
516
517 remove_block(temp); /* unlink 'temp' from list */
518
519 /* remove from size-sorted list: */
520 remove_chunksize((char*)temp+sizeof(struct BlockInfo) );
521
522 /* add the upper block's size on ourselves */
523 newsize += temp->info&INFO_SIZE;
524
525 /* add the new, bigger block */
526 add_blocktolists(block, newblock, newsize);
527 return;
528 }
529 }
530
531 blockHead = newblock;
532 newblock->higher = temp;
533 newblock->lower = NULL; /* there is no lower one */
534 if(newblock->higher)
535 newblock->higher->lower = newblock;
536 }
537
538 newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the
539 FREE bit */
540 insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize);
541}
542
543/***********************************************************************
544 *
545 * findblockbyaddr()
546 *
547 * Find the block that is just before the input block in memory. Returns NULL
548 * if none is.
549 *
550 ***********************************************************************/
551
552static struct BlockInfo *findblockbyaddr(struct BlockInfo *block)
553{
554 struct BlockInfo *test = blockHead;
555 struct BlockInfo *lower = NULL;
556
557 while(test && (test < block)) {
558 lower = test;
559 test = test->higher;
560 }
561 return lower;
562}
563
564/***********************************************************************
565 *
566 * add_pool()
567 *
568 * This function should be the absolutely first function to call. It sets up
569 * the memory bounds of the [first] CHUNK(s). It should be possible to call
570 * this function several times to add more CHUNKs to the pool of free
571 * memory. This allows the bmalloc system to deal with a non-contigous memory
572 * area.
573 *
574 * Returns non-zero if an error occured. The memory was not added then.
575 *
576 ***********************************************************************/
577
578int add_pool(void *start,
579 size_t size)
580{
581 struct BlockInfo *newblock = (struct BlockInfo *)start;
582 struct BlockInfo *block;
583
584 if(size < BMEM_ALIGN)
585 return BMEMERR_TOOSMALL;
586
587 block = findblockbyaddr( newblock );
588 /* `block' is now a lower address than 'newblock' or NULL */
589
590 if(size&1)
591 size--; /* only add even sizes */
592
593 add_blocktolists(block, newblock, size);
594
595 return 0;
596}
597
598
599#ifdef DEBUG
600static void bmalloc_failed(size_t size)
601{
602 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
603 print_lists();
604}
605#else
606#define bmalloc_failed(x)
607#endif
608
609void print_lists()
610{
611 struct BlockInfo *block = blockHead;
612#if 1
613 printf("List of BLOCKS (in address order):\n");
614 while(block) {
615 printf(" START %p END %p SIZE %ld FLAG %s\n",
616 (char *)block,
617 (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE,
618 (block->info&INFO_FREE)?"free":"used");
619 block = block->higher;
620 }
621 printf("End of BLOCKS:\n");
622#endif
623 print_sizes();
624}
625
626void *bmalloc(size_t size)
627{
628 void *mem;
629
630#ifdef DEBUG
631 {
632 static int count=0;
633 int realsize = size + sizeof(struct BlockInfo);
634 if(realsize%4096)
635 realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
636 printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
637 }
638#endif
639
640 size += sizeof(struct BlockInfo); /* add memory for our header */
641
642 if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
643 changed if the BLOCKSIZE is not 2^X ! */
644 size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
645
646 /* get a CHUNK from the list with this size */
647 mem = obtainbysize ( size );
648 if(mem) {
649 /* the memory block we have got is the "best-fit" and it is already
650 un-linked from the free list */
651
652 /* now do the math to get the proper block pointer */
653 struct BlockInfo *block= (struct BlockInfo *)
654 ((char *)mem - sizeof(struct BlockInfo));
655
656 block->info &= ~INFO_FREE;
657 /* not free anymore */
658
659 if( size != (block->info&INFO_SIZE)) {
660 /* split this chunk into two pieces and return the one that fits us */
661 size_t othersize = (block->info&INFO_SIZE) - size;
662
663 if(othersize > BMEM_ALIGN) {
664 /* prevent losing small pieces of memory due to weird alignments
665 of the memory pool */
666
667 block->info = size; /* set new size (leave FREE bit cleared) */
668
669 /* Add the new chunk to the lists: */
670 add_blocktolists(block,
671 (struct BlockInfo *)((char *)block + size),
672 othersize );
673 }
674 }
675
676 /* Return the memory our parent may use: */
677 return (char *)block+sizeof(struct BlockInfo);
678 }
679 else {
680 bmalloc_failed(size);
681 return NULL; /* can't find any memory, fail hard */
682 }
683 return NULL;
684}
685
686void bfree(void *ptr)
687{
688 struct BlockInfo *block = (struct BlockInfo *)
689 ((char *)ptr - sizeof(struct BlockInfo));
690 size_t size;
691
692 /* setup our initial higher and lower pointers */
693 struct BlockInfo *lower = block->lower;
694 struct BlockInfo *higher = block->higher;
695
696#ifdef DEBUG
697 static int freecount=0;
698 printf("%d bfree(%p)\n", freecount++, ptr);
699#endif
700
701 /* bind together lower addressed FREE CHUNKS */
702 if(lower && (lower->info&INFO_FREE) &&
703 ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
704 size = block->info&INFO_SIZE; /* original size */
705
706 /* remove from size-link: */
707 remove_chunksize((char *)lower+sizeof(struct BlockInfo));
708
709 remove_block(block); /* unlink from address list */
710 block = lower; /* new base area pointer */
711 block->info += size; /* append the new size (the FREE bit
712 will remain untouched) */
713
714 lower = lower->lower; /* new lower pointer */
715 }
716 /* bind together higher addressed FREE CHUNKS */
717 if(higher && (higher->info&INFO_FREE) &&
718 ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) {
719 /* append higher size, the FREE bit won't be affected */
720 block->info += (higher->info&INFO_SIZE);
721
722 /* unlink from size list: */
723 remove_chunksize((char *)higher+sizeof(struct BlockInfo));
724 remove_block(higher); /* unlink from address list */
725 higher = higher->higher; /* the new higher link */
726 block->higher = higher; /* new higher link */
727 }
728 block->info |= INFO_FREE; /* consider this FREE! */
729
730 block->lower = lower;
731 block->higher = higher;
732
733 insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE);
734
735#ifdef DEBUG
736 print_lists();
737#endif
738
739}
740
diff --git a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h
new file mode 100644
index 0000000000..4f77667290
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h
@@ -0,0 +1,12 @@
1int add_pool(void *start, size_t size);
2void print_lists();
3
4void *bmalloc(size_t size);
5void bfree(void *ptr);
6
7int add_pool(void *start, size_t size);
8void print_lists();
9
10void *bmalloc(size_t size);
11void bfree(void *ptr);
12
diff --git a/apps/plugins/pdbox/dbestfit-3.3/bysize.c b/apps/plugins/pdbox/dbestfit-3.3/bysize.c
new file mode 100644
index 0000000000..6808406dbc
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/bysize.c
@@ -0,0 +1,848 @@
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
369int printtree(Tree * t, int d, char output)
370{
371 int distance=0;
372 Tree *node;
373 int i;
374 if (t == NULL)
375 return 0;
376 distance += printtree(t->larger, d+1, output);
377 for (i=0; i<d; i++)
378 if(output)
379 printf(" ");
380
381 if(output) {
382 printf("%d[%d]", t->key, i);
383 }
384
385 for(node = t->same; node; node = node->same) {
386 distance += i; /* this has the same "virtual" distance */
387
388 if(output)
389 printf(" [+]");
390 }
391 if(output)
392 puts("");
393
394 distance += i;
395 distance += printtree(t->smaller, d+1, output);
396 return distance;
397}
398
399/* Here follow the look-alike interface so that the tree-function names are
400 the same as the list-ones to enable easy interchange */
401
402void remove_chunksize(void *data)
403{
404 chunkHead = removebyaddr(chunkHead, data);
405}
406
407void insert_bysize(char *data, size_t size)
408{
409 chunkHead = insert(size, chunkHead, (Tree *)data);
410}
411
412char *obtainbysize( size_t size)
413{
414 Tree *receive;
415 chunkHead = removebestfit(size, chunkHead, &receive);
416 return (char *)receive;
417}
418
419void print_sizes(void)
420{
421 printtree(chunkHead, 0, 1);
422}
423
424#endif
425/*****************************************************************************
426 *
427 * Size-sorted list/tree functions.
428 *
429 * Author: Daniel Stenberg
430 * Date: March 7, 1997
431 * Version: 2.0
432 * Email: Daniel.Stenberg@sth.frontec.se
433 *
434 *
435 * v2.0
436 * - Added SPLAY TREE functionality.
437 *
438 * Adds and removes CHUNKS from a list or tree.
439 *
440 ****************************************************************************/
441
442#include <stdio.h>
443#include <stdlib.h>
444
445#define SPLAY /* we use the splay version as that is much faster */
446
447#ifndef TRUE
448#define TRUE 1
449#endif
450#ifndef FALSE
451#define FALSE 0
452#endif
453
454#ifndef SPLAY /* these routines are for the non-splay version */
455
456struct ChunkInfo {
457 struct ChunkInfo *larger;
458 struct ChunkInfo *smaller;
459 size_t size;
460};
461
462/* the CHUNK list anchor */
463struct ChunkInfo *chunkHead=NULL;
464
465/***********************************************************************
466
467 findchunkbysize()
468
469 Find the chunk that is smaller than the input size. Returns
470 NULL if none is.
471
472 **********************************************************************/
473
474static struct ChunkInfo *findchunkbysize(size_t size)
475{
476 struct ChunkInfo *test = chunkHead;
477 struct ChunkInfo *smaller = NULL;
478 while(test && (test->size < size)) {
479 smaller = test;
480 test = test->larger;
481 }
482 return smaller;
483}
484
485/***********************************************************************
486
487 remove_chunksize()
488
489 Remove the chunk from the size-sorted list.
490 ***********************************************************************/
491
492void remove_chunksize(void *data)
493{
494 struct ChunkInfo *chunk = (struct ChunkInfo *)data;
495 if(chunk->smaller)
496 chunk->smaller->larger = chunk->larger;
497 else {
498 /* if this has no smaller, this is the head */
499 chunkHead = chunk->larger; /* new head */
500 }
501 if(chunk->larger)
502 chunk->larger->smaller = chunk->smaller;
503}
504
505void insert_bysize(char *data, size_t size)
506{
507 struct ChunkInfo *newchunk = (struct ChunkInfo *)data;
508 struct ChunkInfo *chunk = findchunkbysize ( size );
509
510 newchunk->size = size;
511
512 if(chunk) {
513 /* 'chunk' is smaller than size, append the new chunk ahead of this */
514 newchunk->smaller = chunk;
515 newchunk->larger = chunk->larger;
516 if(chunk->larger)
517 chunk->larger->smaller = newchunk;
518 chunk->larger = newchunk;
519 }
520 else {
521 /* smallest CHUNK around, append first in the list */
522 newchunk->larger = chunkHead;
523 newchunk->smaller = NULL;
524
525 if(chunkHead)
526 chunkHead->smaller = newchunk;
527 chunkHead = newchunk;
528 }
529}
530
531char *obtainbysize( size_t size)
532{
533 struct ChunkInfo *chunk = findchunkbysize( size );
534
535 if(!chunk) {
536 if(size <= (chunkHead->size))
537 /* there is no smaller CHUNK, use the first one (if we fit within that)
538 */
539 chunk = chunkHead;
540 }
541 else
542 /* we're on the last CHUNK that is smaller than requested, step onto
543 the bigger one */
544 chunk = chunk->larger;
545
546 if(chunk) {
547 remove_chunksize( chunk ); /* unlink size-wise */
548 return (char *)chunk;
549 }
550 else
551 return NULL;
552}
553
554void print_sizes(void)
555{
556 struct ChunkInfo *chunk = chunkHead;
557 printf("List of CHUNKS (in size order):\n");
558#if 1
559 while(chunk) {
560 printf(" START %p END %p SIZE %d\n",
561 chunk, (char *)chunk+chunk->size, chunk->size);
562 chunk = chunk->larger;
563 }
564#endif
565 printf("End of CHUNKS:\n");
566}
567
568#else /* Here follows all routines dealing with the SPLAY TREES */
569
570typedef struct tree_node Tree;
571struct tree_node {
572 Tree *smaller; /* smaller node */
573 Tree *larger; /* larger node */
574 Tree *same; /* points to a node with identical key */
575 int key; /* the "sort" key */
576};
577
578Tree *chunkHead = NULL; /* the root */
579
580#define compare(i,j) ((i)-(j))
581
582/* Set this to a key value that will *NEVER* appear otherwise */
583#define KEY_NOTUSED -1
584
585/*
586 * Splay using the key i (which may or may not be in the tree.) The starting
587 * root is t. Weight fields are maintained.
588 */
589Tree * splay (int i, Tree *t)
590{
591 Tree N, *l, *r, *y;
592 int comp;
593
594 if (t == NULL)
595 return t;
596 N.smaller = N.larger = NULL;
597 l = r = &N;
598
599 for (;;) {
600 comp = compare(i, t->key);
601 if (comp < 0) {
602 if (t->smaller == NULL)
603 break;
604 if (compare(i, t->smaller->key) < 0) {
605 y = t->smaller; /* rotate smaller */
606 t->smaller = y->larger;
607 y->larger = t;
608
609 t = y;
610 if (t->smaller == NULL)
611 break;
612 }
613 r->smaller = t; /* link smaller */
614 r = t;
615 t = t->smaller;
616 }
617 else if (comp > 0) {
618 if (t->larger == NULL)
619 break;
620 if (compare(i, t->larger->key) > 0) {
621 y = t->larger; /* rotate larger */
622 t->larger = y->smaller;
623 y->smaller = t;
624 t = y;
625 if (t->larger == NULL)
626 break;
627 }
628 l->larger = t; /* link larger */
629 l = t;
630 t = t->larger;
631 }
632 else {
633 break;
634 }
635 }
636
637 l->larger = r->smaller = NULL;
638
639 l->larger = t->smaller; /* assemble */
640 r->smaller = t->larger;
641 t->smaller = N.larger;
642 t->larger = N.smaller;
643
644 return t;
645}
646
647/* Insert key i into the tree t. Return a pointer to the resulting tree or
648 NULL if something went wrong. */
649Tree *insert(int i, Tree *t, Tree *new)
650{
651 if (new == NULL) {
652 return t;
653 }
654
655 if (t != NULL) {
656 t = splay(i,t);
657 if (compare(i, t->key)==0) {
658 /* it already exists one of this size */
659
660 new->same = t;
661 new->key = i;
662 new->smaller = t->smaller;
663 new->larger = t->larger;
664
665 t->smaller = new;
666 t->key = KEY_NOTUSED;
667
668 return new; /* new root node */
669 }
670 }
671
672 if (t == NULL) {
673 new->smaller = new->larger = NULL;
674 }
675 else if (compare(i, t->key) < 0) {
676 new->smaller = t->smaller;
677 new->larger = t;
678 t->smaller = NULL;
679 }
680 else {
681 new->larger = t->larger;
682 new->smaller = t;
683 t->larger = NULL;
684 }
685 new->key = i;
686
687 new->same = NULL; /* no identical node (yet) */
688
689 return new;
690}
691
692/* Finds and deletes the best-fit node from the tree. Return a pointer to the
693 resulting tree. best-fit means the smallest node that fits the requested
694 size. */
695Tree *removebestfit(int i, Tree *t, Tree **removed)
696{
697 Tree *x;
698
699 if (t==NULL)
700 return NULL;
701 t = splay(i,t);
702 if(compare(i, t->key) > 0) {
703 /* too small node, try the larger chain */
704 if(t->larger)
705 t=splay(t->larger->key, t);
706 else {
707 /* fail */
708 *removed = NULL;
709 return t;
710 }
711 }
712
713 if (compare(i, t->key) <= 0) { /* found it */
714
715 /* FIRST! Check if there is a list with identical sizes */
716 x = t->same;
717 if(x) {
718 /* there is, pick one from the list */
719
720 /* 'x' is the new root node */
721
722 x->key = t->key;
723 x->larger = t->larger;
724 x->smaller = t->smaller;
725 *removed = t;
726 return x; /* new root */
727 }
728
729 if (t->smaller == NULL) {
730 x = t->larger;
731 }
732 else {
733 x = splay(i, t->smaller);
734 x->larger = t->larger;
735 }
736 *removed = t;
737
738 return x;
739 }
740 else {
741 *removed = NULL; /* no match */
742 return t; /* It wasn't there */
743 }
744}
745
746
747/* Deletes the node we point out from the tree if it's there. Return a pointer
748 to the resulting tree. */
749Tree *removebyaddr(Tree *t, Tree *remove)
750{
751 Tree *x;
752
753 if (!t || !remove)
754 return NULL;
755
756 if(KEY_NOTUSED == remove->key) {
757 /* just unlink ourselves nice and quickly: */
758 remove->smaller->same = remove->same;
759 if(remove->same)
760 remove->same->smaller = remove->smaller;
761 /* voila, we're done! */
762 return t;
763 }
764
765 t = splay(remove->key,t);
766
767 /* Check if there is a list with identical sizes */
768
769 x = t->same;
770 if(x) {
771 /* 'x' is the new root node */
772
773 x->key = t->key;
774 x->larger = t->larger;
775 x->smaller = t->smaller;
776
777 return x; /* new root */
778 }
779
780 /* Remove the actualy root node: */
781
782 if (t->smaller == NULL) {
783 x = t->larger;
784 }
785 else {
786 x = splay(remove->key, t->smaller);
787 x->larger = t->larger;
788 }
789
790 return x;
791}
792
793int printtree(Tree * t, int d, char output)
794{
795 int distance=0;
796 Tree *node;
797 int i;
798 if (t == NULL)
799 return 0;
800 distance += printtree(t->larger, d+1, output);
801 for (i=0; i<d; i++)
802 if(output)
803 printf(" ");
804
805 if(output) {
806 printf("%d[%d]", t->key, i);
807 }
808
809 for(node = t->same; node; node = node->same) {
810 distance += i; /* this has the same "virtual" distance */
811
812 if(output)
813 printf(" [+]");
814 }
815 if(output)
816 puts("");
817
818 distance += i;
819 distance += printtree(t->smaller, d+1, output);
820 return distance;
821}
822
823/* Here follow the look-alike interface so that the tree-function names are
824 the same as the list-ones to enable easy interchange */
825
826void remove_chunksize(void *data)
827{
828 chunkHead = removebyaddr(chunkHead, data);
829}
830
831void insert_bysize(char *data, size_t size)
832{
833 chunkHead = insert(size, chunkHead, (Tree *)data);
834}
835
836char *obtainbysize( size_t size)
837{
838 Tree *receive;
839 chunkHead = removebestfit(size, chunkHead, &receive);
840 return (char *)receive;
841}
842
843void print_sizes(void)
844{
845 printtree(chunkHead, 0, 1);
846}
847
848#endif
diff --git a/apps/plugins/pdbox/dbestfit-3.3/bysize.h b/apps/plugins/pdbox/dbestfit-3.3/bysize.h
new file mode 100644
index 0000000000..2fbf23154d
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/bysize.h
@@ -0,0 +1,8 @@
1void remove_chunksize(void *data);
2void insert_bysize(char *data, size_t size);
3char *obtainbysize( size_t size);
4void print_sizes(void);
5void remove_chunksize(void *data);
6void insert_bysize(char *data, size_t size);
7char *obtainbysize( size_t size);
8void print_sizes(void);
diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
new file mode 100644
index 0000000000..9336276883
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
@@ -0,0 +1,1380 @@
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#include <stdio.h>
27#include <string.h>
28
29#ifdef DEBUG
30#include <stdarg.h>
31#endif
32
33#ifdef PSOS
34#include <psos.h>
35#define SEMAPHORE /* the PSOS routines use semaphore protection */
36#else
37#include <stdlib.h> /* makes the PSOS complain on the 'size_t' typedef */
38#endif
39
40#ifdef BMALLOC
41#include "bmalloc.h"
42#endif
43
44/* Each TOP takes care of a chain of BLOCKS */
45struct MemTop {
46 struct MemBlock *chain; /* pointer to the BLOCK chain */
47 long nfree; /* total number of free FRAGMENTS in the chain */
48 short nmax; /* total number of FRAGMENTS in this kind of BLOCK */
49 size_t fragsize; /* the size of each FRAGMENT */
50
51#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */
52 long semaphore_id; /* semaphore used to lock this particular list */
53#endif
54
55};
56
57/* Each BLOCK takes care of an amount of FRAGMENTS */
58struct MemBlock {
59 struct MemTop *top; /* our TOP struct */
60 struct MemBlock *next; /* next BLOCK */
61 struct MemBlock *prev; /* prev BLOCK */
62
63 struct MemFrag *first; /* the first free FRAGMENT in this block */
64
65 short nfree; /* number of free FRAGMENTS in this BLOCK */
66};
67
68/* This is the data kept in all _free_ FRAGMENTS */
69struct MemFrag {
70 struct MemFrag *next; /* next free FRAGMENT */
71 struct MemFrag *prev; /* prev free FRAGMENT */
72};
73
74/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this
75 to the allocation size first thing in the ALLOC function to make room for
76 this smoothly. */
77
78struct MemInfo {
79 void *block;
80 /* which BLOCK is our father, if BLOCK_BIT is set it means this is a
81 stand-alone, large allocation and then the rest of the bits should be
82 treated as the size of the block */
83#define BLOCK_BIT 1
84};
85
86/* ---------------------------------------------------------------------- */
87/* Defines */
88/* ---------------------------------------------------------------------- */
89
90#ifdef DEBUG
91#define MEMINCR(addr,x) memchange(addr, x)
92#define MEMDECR(addr,x) memchange(addr,-(x))
93#else
94#define MEMINCR(a,x)
95#define MEMDECR(a,x)
96#endif
97
98/* The low level functions used to get memory from the OS and to return memory
99 to the OS, we may also define a stub that does the actual allocation and
100 free, these are the defined function names used in the dmalloc system
101 anyway: */
102#ifdef PSOS
103
104#ifdef DEBUG
105#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
106#define DMEM_OSFREEMEM(x) dbgfree(x)
107#else
108#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer)
109/* Similar, but this returns the memory */
110#define DMEM_OSFREEMEM(x) rn_retseg(0, x)
111#endif
112
113/* Argument: <id> */
114#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0)
115/* Argument: <id> */
116#define SEMAPHORERETURN(x) sm_v(x)
117/* Argument: <name> <id-variable name> */
118#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y))
119
120#else
121#ifdef BMALLOC /* use our own big-memory-allocation system */
122#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size)
123#define DMEM_OSFREEMEM(x) bfree(x)
124#elif DEBUG
125#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
126#define DMEM_OSFREEMEM(x) dbgfree(x)
127#else
128#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size)
129#define DMEM_OSFREEMEM(x) free(x)
130#endif
131#endif
132
133
134/* the largest memory allocation that is made a FRAGMENT: (grab the highest
135 number from the list below) */
136#define DMEM_LARGESTSIZE 2032
137
138/* The total size of a BLOCK used for FRAGMENTS
139 In order to make this use only *1* even alignment from the big-block-
140 allocation-system (possible the bmalloc() system also written by me)
141 we need to subtract the [maximum] struct sizes that could get added all
142 the way through to the grab from the memory. */
143#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */
144
145/* Since the blocksize isn't an even 2^X story anymore, we make a table with
146 the FRAGMENT sizes and amounts that fills up a BLOCK nicely */
147
148/* a little 'bc' script that helps us maximize the usage:
149 - for 32-bit aligned addresses (SPARC crashes otherwise):
150 for(i=20; i<2040; i++) { a=4064/i; if(a*i >= 4060) { if(i%4==0) {i;} } }
151
152
153 I try to approximate a double of each size, starting with ~20. We don't do
154 ODD sizes since several CPU flavours dump core when accessing such
155 addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain
156 happy with us.
157 */
158
159#if BIGBLOCKS==4060 /* previously */
160short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
161#else
162short qinfo[]= { 20, 28, 52, 116, 312, 580, 1016, 2032};
163/* 52 and 312 only make use of 4056 bytes, but without them there are too
164 wide gaps */
165#endif
166
167#define MIN(x,y) ((x)<(y)?(x):(y))
168
169/* ---------------------------------------------------------------------- */
170/* Globals */
171/* ---------------------------------------------------------------------- */
172
173/* keeper of the chain of BLOCKS */
174static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
175
176/* are we experienced? */
177static char initialized = 0;
178
179/* ---------------------------------------------------------------------- */
180/* Start of the real code */
181/* ---------------------------------------------------------------------- */
182
183#ifdef DEBUG
184/************
185 * A few functions that are verbose and tells us about the current status
186 * of the dmalloc system
187 ***********/
188
189static void dmalloc_status()
190{
191 int i;
192 int used;
193 int num;
194 int totalfree=0;
195 struct MemBlock *block;
196 for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) {
197 block = top[i].chain;
198 used = 0;
199 num = 0;
200 while(block) {
201 used += top[i].nmax-block->nfree;
202 num++;
203 block = block->next;
204 }
205 printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n",
206 i, top[i].fragsize, used, top[i].nfree,
207 top[i].nfree*top[i].fragsize, num);
208 totalfree += top[i].nfree*top[i].fragsize;
209 }
210 printf("Total unused memory stolen by dmalloc: %d\n", totalfree);
211}
212
213static void dmalloc_failed(size_t size)
214{
215 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
216 dmalloc_status();
217}
218#else
219#define dmalloc_failed(x)
220#endif
221
222#ifdef DEBUG
223
224#define BORDER 1200
225
226void *dbgmalloc(int size)
227{
228 char *mem;
229 size += BORDER;
230#ifdef PSOS
231 rn_getseg(0,size,RN_NOWAIT,0,(void **)&mem);
232#else
233 mem = malloc(size);
234#endif
235 if(mem) {
236 memset(mem, 0xaa, BORDER/2);
237 memset(mem+BORDER/2, 0xbb, size -BORDER);
238 memset(mem-BORDER/2+size, 0xcc, BORDER/2);
239 *(long *)mem = size;
240 mem += (BORDER/2);
241 }
242 printf("OSmalloc(%p)\n", mem);
243 return (void *)mem;
244}
245
246void checkmem(char *ptr)
247{
248 int i;
249 long size;
250 ptr -= BORDER/2;
251
252 for(i=4; i<(BORDER/2); i++)
253 if((unsigned char)ptr[i] != 0xaa) {
254 printf("########### ALERT ALERT\n");
255 break;
256 }
257 size = *(long *)ptr;
258 for(i=size-1; i>=(size - BORDER/2); i--)
259 if((unsigned char)ptr[i] != 0xcc) {
260 printf("********* POST ALERT\n");
261 break;
262 }
263}
264
265void dbgfree(char *ptr)
266{
267 long size;
268 checkmem(ptr);
269 ptr -= BORDER/2;
270 size = *(long *)ptr;
271
272 printf("OSfree(%ld)\n", size);
273#ifdef PSOS
274 rn_retseg(0, ptr);
275#else
276 free(ptr);
277#endif
278}
279
280
281#define DBG(x) syslog x
282
283void syslog(char *fmt, ...)
284{
285 va_list ap;
286 va_start(ap, fmt);
287 vfprintf(stdout, fmt, ap);
288 va_end(ap);
289}
290
291void memchange(void *a, int x)
292{
293 static int memory=0;
294 static int count=0;
295 static int max=0;
296 if(memory > max)
297 max = memory;
298 memory += x;
299 DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max));
300}
301#else
302#define DBG(x)
303#endif
304
305/****************************************************************************
306 *
307 * FragBlock()
308 *
309 * This function makes FRAGMENTS of the BLOCK sent as argument.
310 *
311 ***************************************************************************/
312
313static void FragBlock(char *memp, int size)
314{
315 struct MemFrag *frag=(struct MemFrag *)memp;
316 struct MemFrag *prev=NULL; /* no previous in the first round */
317 int count=0;
318 while((count+size) <= DMEM_BLOCKSIZE) {
319 memp += size;
320 frag->next = (struct MemFrag *)memp;
321 frag->prev = prev;
322 prev = frag;
323 frag = frag->next;
324 count += size;
325 }
326 prev->next = NULL; /* the last one has no next struct */
327}
328
329/***************************************************************************
330 *
331 * initialize();
332 *
333 * Called in the first dmalloc(). Inits a few memory things.
334 *
335 **************************************************************************/
336static void initialize(void)
337{
338 int i;
339 /* Setup the nmax and fragsize fields of the top structs */
340 for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) {
341 top[i].fragsize = qinfo[i];
342 top[i].nmax = DMEM_BLOCKSIZE/qinfo[i];
343
344#ifdef PSOS
345 /* for some reason, these aren't nulled from start: */
346 top[i].chain = NULL; /* no BLOCKS */
347 top[i].nfree = 0; /* no FRAGMENTS */
348#endif
349#ifdef SEMAPHORE
350 {
351 char name[7];
352 sprintf(name, "MEM%d", i);
353 SEMAPHORECREATE(name, top[i].semaphore_id);
354 /* doesn't matter if it failed, we continue anyway ;-( */
355 }
356#endif
357 }
358 initialized = 1;
359}
360
361/****************************************************************************
362 *
363 * FragFromBlock()
364 *
365 * This should return a fragment from the block and mark it as used
366 * accordingly.
367 *
368 ***************************************************************************/
369
370static void *FragFromBlock(struct MemBlock *block)
371{
372 /* make frag point to the first free FRAGMENT */
373 struct MemFrag *frag = block->first;
374 struct MemInfo *mem = (struct MemInfo *)frag;
375
376 /*
377 * Remove the FRAGMENT from the list and decrease the free counters.
378 */
379 block->first = frag->next; /* new first free FRAGMENT */
380
381 block->nfree--; /* BLOCK counter */
382 block->top->nfree--; /* TOP counter */
383
384 /* heal the FRAGMENT list */
385 if(frag->prev) {
386 frag->prev->next = frag->next;
387 }
388 if(frag->next) {
389 frag->next->prev = frag->prev;
390 }
391 mem->block = block; /* no block bit set here */
392
393 return ((char *)mem)+sizeof(struct MemInfo);
394}
395
396/***************************************************************************
397 *
398 * dmalloc()
399 *
400 * This needs no explanation. A malloc() look-alike.
401 *
402 **************************************************************************/
403
404void *dmalloc(size_t size)
405{
406 void *mem;
407
408 DBG(("dmalloc(%d)\n", size));
409
410 if(!initialized)
411 initialize();
412
413 /* First, we make room for the space needed in every allocation */
414 size += sizeof(struct MemInfo);
415
416 if(size < DMEM_LARGESTSIZE) {
417 /* get a FRAGMENT */
418
419 struct MemBlock *block=NULL; /* SAFE */
420 struct MemBlock *newblock=NULL; /* SAFE */
421 struct MemTop *memtop=NULL; /* SAFE */
422
423 /* Determine which queue to use */
424 int queue;
425 for(queue=0; size > qinfo[queue]; queue++)
426 ;
427 do {
428 /* This is the head master of our chain: */
429 memtop = &top[queue];
430
431 DBG(("Top info: %p %d %d %d\n",
432 memtop->chain,
433 memtop->nfree,
434 memtop->nmax,
435 memtop->fragsize));
436
437#ifdef SEMAPHORE
438 if(SEMAPHOREOBTAIN(memtop->semaphore_id))
439 return NULL; /* failed somehow */
440#endif
441
442 /* get the first BLOCK in the chain */
443 block = memtop->chain;
444
445 /* check if we have a free FRAGMENT */
446 if(memtop->nfree) {
447 /* there exists a free FRAGMENT in this chain */
448
449 /* I WANT THIS LOOP OUT OF HERE! */
450
451 /* search for the free FRAGMENT */
452 while(!block->nfree)
453 block = block->next; /* check next BLOCK */
454
455 /*
456 * Now 'block' is the first BLOCK with a free FRAGMENT
457 */
458
459 mem = FragFromBlock(block);
460
461 }
462 else {
463 /* we do *not* have a free FRAGMENT but need to get us a new BLOCK */
464
465 DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock),
466 newblock,
467 struct MemBlock *);
468 if(!newblock) {
469 if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) {
470 /* There are queues for bigger FRAGMENTS that we should check
471 before we fail this for real */
472#ifdef DEBUG
473 printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue);
474#endif
475 mem = NULL;
476 }
477 else {
478 dmalloc_failed(size- sizeof(struct MemInfo));
479 return NULL; /* not enough memory */
480 }
481 }
482 else {
483 /* allocation of big BLOCK was successful */
484
485 MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
486
487 memtop->chain = newblock; /* attach this BLOCK to the chain */
488 newblock->next = block; /* point to the previous first BLOCK */
489 if(block)
490 block->prev = newblock; /* point back on this new BLOCK */
491 newblock->prev = NULL; /* no previous */
492 newblock->top = memtop; /* our head master */
493
494 /* point to the new first FRAGMENT */
495 newblock->first = (struct MemFrag *)
496 ((char *)newblock+sizeof(struct MemBlock));
497
498 /* create FRAGMENTS of the BLOCK: */
499 FragBlock((char *)newblock->first, memtop->fragsize);
500
501#if defined(DEBUG) && !defined(BMALLOC)
502 checkmem((char *)newblock);
503#endif
504
505 /* fix the nfree counters */
506 newblock->nfree = memtop->nmax;
507 memtop->nfree += memtop->nmax;
508
509 /* get a FRAGMENT from the BLOCK */
510 mem = FragFromBlock(newblock);
511 }
512 }
513#ifdef SEMAPHORE
514 SEMAPHORERETURN(memtop->semaphore_id); /* let it go */
515#endif
516 } while(NULL == mem); /* if we should retry a larger FRAGMENT */
517 }
518 else {
519 /* get a stand-alone BLOCK */
520 struct MemInfo *meminfo;
521
522 if(size&1)
523 /* don't leave this with an odd size since we'll use that bit for
524 information */
525 size++;
526
527 DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *);
528
529 if(meminfo) {
530 MEMINCR(meminfo, size);
531 meminfo->block = (void *)(size|BLOCK_BIT);
532 mem = (char *)meminfo + sizeof(struct MemInfo);
533 }
534 else {
535 dmalloc_failed(size);
536 mem = NULL;
537 }
538 }
539 return (void *)mem;
540}
541
542/***************************************************************************
543 *
544 * dfree()
545 *
546 * This needs no explanation. A free() look-alike.
547 *
548 **************************************************************************/
549
550void dfree(void *memp)
551{
552 struct MemInfo *meminfo = (struct MemInfo *)
553 ((char *)memp- sizeof(struct MemInfo));
554
555 DBG(("dfree(%p)\n", memp));
556
557 if(!((size_t)meminfo->block&BLOCK_BIT)) {
558 /* this is a FRAGMENT we have to deal with */
559
560 struct MemBlock *block=meminfo->block;
561 struct MemTop *memtop = block->top;
562
563#ifdef SEMAPHORE
564 SEMAPHOREOBTAIN(memtop->semaphore_id);
565#endif
566
567 /* increase counters */
568 block->nfree++;
569 memtop->nfree++;
570
571 /* is this BLOCK completely empty now? */
572 if(block->nfree == memtop->nmax) {
573 /* yes, return the BLOCK to the system */
574 if(block->prev)
575 block->prev->next = block->next;
576 else
577 memtop->chain = block->next;
578 if(block->next)
579 block->next->prev = block->prev;
580
581 memtop->nfree -= memtop->nmax; /* total counter subtraction */
582 MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
583 DMEM_OSFREEMEM((void *)block); /* return the whole block */
584 }
585 else {
586 /* there are still used FRAGMENTS in the BLOCK, link this one
587 into the chain of free ones */
588 struct MemFrag *frag = (struct MemFrag *)meminfo;
589 frag->prev = NULL;
590 frag->next = block->first;
591 if(block->first)
592 block->first->prev = frag;
593 block->first = frag;
594 }
595#ifdef SEMAPHORE
596 SEMAPHORERETURN(memtop->semaphore_id);
597#endif
598 }
599 else {
600 /* big stand-alone block, just give it back to the OS: */
601 MEMDECR(&meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */
602 DMEM_OSFREEMEM((void *)meminfo);
603 }
604}
605
606/***************************************************************************
607 *
608 * drealloc()
609 *
610 * This needs no explanation. A realloc() look-alike.
611 *
612 **************************************************************************/
613
614void *drealloc(char *ptr, size_t size)
615{
616 struct MemInfo *meminfo = (struct MemInfo *)
617 ((char *)ptr- sizeof(struct MemInfo));
618 /*
619 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
620 * NOTE: the ->size field of the meminfo will now contain the MemInfo
621 * struct size too!
622 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
623 */
624 void *mem=NULL; /* SAFE */
625 size_t prevsize;
626
627 /* NOTE that this is only valid if BLOCK_BIT isn't set: */
628 struct MemBlock *block;
629
630 DBG(("drealloc(%p, %d)\n", ptr, size));
631
632 if(NULL == ptr)
633 return dmalloc( size );
634
635 block = meminfo->block;
636
637 if(!((size_t)meminfo->block&BLOCK_BIT) &&
638 (size + sizeof(struct MemInfo) <
639 (prevsize = block->top->fragsize) )) {
640 /* This is a FRAGMENT and new size is possible to retain within the same
641 FRAGMENT */
642 if((prevsize > qinfo[0]) &&
643 /* this is not the smallest memory Q */
644 (size < (block->top-1)->fragsize))
645 /* this fits in a smaller Q */
646 ;
647 else
648 mem = ptr; /* Just return the same pointer as we got in. */
649 }
650 if(!mem) {
651 /* This is a stand-alone BLOCK or a realloc that no longer fits within
652 the same FRAGMENT */
653
654 if((size_t)meminfo->block&BLOCK_BIT) {
655 prevsize = ((size_t)meminfo->block&~BLOCK_BIT) -
656 sizeof(struct MemInfo);
657 }
658 else
659 prevsize -= sizeof(struct MemInfo);
660
661 /* No tricks involved here, just grab a new bite of memory, copy the data
662 * from the old place and free the old memory again. */
663 mem = dmalloc(size);
664 if(mem) {
665 memcpy(mem, ptr, MIN(size, prevsize) );
666 dfree(ptr);
667 }
668 }
669 return mem;
670}
671
672/***************************************************************************
673 *
674 * dcalloc()
675 *
676 * This needs no explanation. A calloc() look-alike.
677 *
678 **************************************************************************/
679/* Allocate an array of NMEMB elements each SIZE bytes long.
680 The entire array is initialized to zeros. */
681void *
682dcalloc (size_t nmemb, size_t size)
683{
684 void *result = dmalloc (nmemb * size);
685
686 if (result != NULL)
687 memset (result, 0, nmemb * size);
688
689 return result;
690}
691/*****************************************************************************
692 *
693 * Dynamic Memory Allocation
694 *
695 * Author: Daniel Stenberg
696 * Date: March 10, 1997
697 * Version: 2.3
698 * Email: Daniel.Stenberg@sth.frontec.se
699 *
700 *
701 * Read 'thoughts' for theories and details of this implementation.
702 *
703 * v2.1
704 * - I once again managed to gain some memory. BLOCK allocations now only use
705 * a 4 bytes header (instead of previos 8) just as FRAGMENTS.
706 *
707 * v2.2
708 * - Re-adjusted the fragment sizes to better fit into the somewhat larger
709 * block.
710 *
711 * v2.3
712 * - Made realloc(NULL, size) work as it should. Which is like a malloc(size)
713 *
714 *****************************************************************************/
715
716#include <stdio.h>
717#include <string.h>
718
719#ifdef DEBUG
720#include <stdarg.h>
721#endif
722
723#ifdef PSOS
724#include <psos.h>
725#define SEMAPHORE /* the PSOS routines use semaphore protection */
726#else
727#include <stdlib.h> /* makes the PSOS complain on the 'size_t' typedef */
728#endif
729
730#ifdef BMALLOC
731#include "bmalloc.h"
732#endif
733
734/* Each TOP takes care of a chain of BLOCKS */
735struct MemTop {
736 struct MemBlock *chain; /* pointer to the BLOCK chain */
737 long nfree; /* total number of free FRAGMENTS in the chain */
738 short nmax; /* total number of FRAGMENTS in this kind of BLOCK */
739 size_t fragsize; /* the size of each FRAGMENT */
740
741#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */
742 long semaphore_id; /* semaphore used to lock this particular list */
743#endif
744
745};
746
747/* Each BLOCK takes care of an amount of FRAGMENTS */
748struct MemBlock {
749 struct MemTop *top; /* our TOP struct */
750 struct MemBlock *next; /* next BLOCK */
751 struct MemBlock *prev; /* prev BLOCK */
752
753 struct MemFrag *first; /* the first free FRAGMENT in this block */
754
755 short nfree; /* number of free FRAGMENTS in this BLOCK */
756};
757
758/* This is the data kept in all _free_ FRAGMENTS */
759struct MemFrag {
760 struct MemFrag *next; /* next free FRAGMENT */
761 struct MemFrag *prev; /* prev free FRAGMENT */
762};
763
764/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this
765 to the allocation size first thing in the ALLOC function to make room for
766 this smoothly. */
767
768struct MemInfo {
769 void *block;
770 /* which BLOCK is our father, if BLOCK_BIT is set it means this is a
771 stand-alone, large allocation and then the rest of the bits should be
772 treated as the size of the block */
773#define BLOCK_BIT 1
774};
775
776/* ---------------------------------------------------------------------- */
777/* Defines */
778/* ---------------------------------------------------------------------- */
779
780#ifdef DEBUG
781#define MEMINCR(addr,x) memchange(addr, x)
782#define MEMDECR(addr,x) memchange(addr,-(x))
783#else
784#define MEMINCR(a,x)
785#define MEMDECR(a,x)
786#endif
787
788/* The low level functions used to get memory from the OS and to return memory
789 to the OS, we may also define a stub that does the actual allocation and
790 free, these are the defined function names used in the dmalloc system
791 anyway: */
792#ifdef PSOS
793
794#ifdef DEBUG
795#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
796#define DMEM_OSFREEMEM(x) dbgfree(x)
797#else
798#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer)
799/* Similar, but this returns the memory */
800#define DMEM_OSFREEMEM(x) rn_retseg(0, x)
801#endif
802
803/* Argument: <id> */
804#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0)
805/* Argument: <id> */
806#define SEMAPHORERETURN(x) sm_v(x)
807/* Argument: <name> <id-variable name> */
808#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y))
809
810#else
811#ifdef BMALLOC /* use our own big-memory-allocation system */
812#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size)
813#define DMEM_OSFREEMEM(x) bfree(x)
814#elif DEBUG
815#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
816#define DMEM_OSFREEMEM(x) dbgfree(x)
817#else
818#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size)
819#define DMEM_OSFREEMEM(x) free(x)
820#endif
821#endif
822
823
824/* the largest memory allocation that is made a FRAGMENT: (grab the highest
825 number from the list below) */
826#define DMEM_LARGESTSIZE 2032
827
828/* The total size of a BLOCK used for FRAGMENTS
829 In order to make this use only *1* even alignment from the big-block-
830 allocation-system (possible the bmalloc() system also written by me)
831 we need to subtract the [maximum] struct sizes that could get added all
832 the way through to the grab from the memory. */
833#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */
834
835/* Since the blocksize isn't an even 2^X story anymore, we make a table with
836 the FRAGMENT sizes and amounts that fills up a BLOCK nicely */
837
838/* a little 'bc' script that helps us maximize the usage:
839 - for 32-bit aligned addresses (SPARC crashes otherwise):
840 for(i=20; i<2040; i++) { a=4064/i; if(a*i >= 4060) { if(i%4==0) {i;} } }
841
842
843 I try to approximate a double of each size, starting with ~20. We don't do
844 ODD sizes since several CPU flavours dump core when accessing such
845 addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain
846 happy with us.
847 */
848
849#if BIGBLOCKS==4060 /* previously */
850short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
851#else
852short qinfo[]= { 20, 28, 52, 116, 312, 580, 1016, 2032};
853/* 52 and 312 only make use of 4056 bytes, but without them there are too
854 wide gaps */
855#endif
856
857#define MIN(x,y) ((x)<(y)?(x):(y))
858
859/* ---------------------------------------------------------------------- */
860/* Globals */
861/* ---------------------------------------------------------------------- */
862
863/* keeper of the chain of BLOCKS */
864static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
865
866/* are we experienced? */
867static char initialized = 0;
868
869/* ---------------------------------------------------------------------- */
870/* Start of the real code */
871/* ---------------------------------------------------------------------- */
872
873#ifdef DEBUG
874/************
875 * A few functions that are verbose and tells us about the current status
876 * of the dmalloc system
877 ***********/
878
879static void dmalloc_status()
880{
881 int i;
882 int used;
883 int num;
884 int totalfree=0;
885 struct MemBlock *block;
886 for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) {
887 block = top[i].chain;
888 used = 0;
889 num = 0;
890 while(block) {
891 used += top[i].nmax-block->nfree;
892 num++;
893 block = block->next;
894 }
895 printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n",
896 i, top[i].fragsize, used, top[i].nfree,
897 top[i].nfree*top[i].fragsize, num);
898 totalfree += top[i].nfree*top[i].fragsize;
899 }
900 printf("Total unused memory stolen by dmalloc: %d\n", totalfree);
901}
902
903static void dmalloc_failed(size_t size)
904{
905 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
906 dmalloc_status();
907}
908#else
909#define dmalloc_failed(x)
910#endif
911
912#ifdef DEBUG
913
914#define BORDER 1200
915
916void *dbgmalloc(int size)
917{
918 char *mem;
919 size += BORDER;
920#ifdef PSOS
921 rn_getseg(0,size,RN_NOWAIT,0,(void **)&mem);
922#else
923 mem = malloc(size);
924#endif
925 if(mem) {
926 memset(mem, 0xaa, BORDER/2);
927 memset(mem+BORDER/2, 0xbb, size -BORDER);
928 memset(mem-BORDER/2+size, 0xcc, BORDER/2);
929 *(long *)mem = size;
930 mem += (BORDER/2);
931 }
932 printf("OSmalloc(%p)\n", mem);
933 return (void *)mem;
934}
935
936void checkmem(char *ptr)
937{
938 int i;
939 long size;
940 ptr -= BORDER/2;
941
942 for(i=4; i<(BORDER/2); i++)
943 if((unsigned char)ptr[i] != 0xaa) {
944 printf("########### ALERT ALERT\n");
945 break;
946 }
947 size = *(long *)ptr;
948 for(i=size-1; i>=(size - BORDER/2); i--)
949 if((unsigned char)ptr[i] != 0xcc) {
950 printf("********* POST ALERT\n");
951 break;
952 }
953}
954
955void dbgfree(char *ptr)
956{
957 long size;
958 checkmem(ptr);
959 ptr -= BORDER/2;
960 size = *(long *)ptr;
961
962 printf("OSfree(%ld)\n", size);
963#ifdef PSOS
964 rn_retseg(0, ptr);
965#else
966 free(ptr);
967#endif
968}
969
970
971#define DBG(x) syslog x
972
973void syslog(char *fmt, ...)
974{
975 va_list ap;
976 va_start(ap, fmt);
977 vfprintf(stdout, fmt, ap);
978 va_end(ap);
979}
980
981void memchange(void *a, int x)
982{
983 static int memory=0;
984 static int count=0;
985 static int max=0;
986 if(memory > max)
987 max = memory;
988 memory += x;
989 DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max));
990}
991#else
992#define DBG(x)
993#endif
994
995/****************************************************************************
996 *
997 * FragBlock()
998 *
999 * This function makes FRAGMENTS of the BLOCK sent as argument.
1000 *
1001 ***************************************************************************/
1002
1003static void FragBlock(char *memp, int size)
1004{
1005 struct MemFrag *frag=(struct MemFrag *)memp;
1006 struct MemFrag *prev=NULL; /* no previous in the first round */
1007 int count=0;
1008 while((count+size) <= DMEM_BLOCKSIZE) {
1009 memp += size;
1010 frag->next = (struct MemFrag *)memp;
1011 frag->prev = prev;
1012 prev = frag;
1013 frag = frag->next;
1014 count += size;
1015 }
1016 prev->next = NULL; /* the last one has no next struct */
1017}
1018
1019/***************************************************************************
1020 *
1021 * initialize();
1022 *
1023 * Called in the first dmalloc(). Inits a few memory things.
1024 *
1025 **************************************************************************/
1026static void initialize(void)
1027{
1028 int i;
1029 /* Setup the nmax and fragsize fields of the top structs */
1030 for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) {
1031 top[i].fragsize = qinfo[i];
1032 top[i].nmax = DMEM_BLOCKSIZE/qinfo[i];
1033
1034#ifdef PSOS
1035 /* for some reason, these aren't nulled from start: */
1036 top[i].chain = NULL; /* no BLOCKS */
1037 top[i].nfree = 0; /* no FRAGMENTS */
1038#endif
1039#ifdef SEMAPHORE
1040 {
1041 char name[7];
1042 sprintf(name, "MEM%d", i);
1043 SEMAPHORECREATE(name, top[i].semaphore_id);
1044 /* doesn't matter if it failed, we continue anyway ;-( */
1045 }
1046#endif
1047 }
1048 initialized = 1;
1049}
1050
1051/****************************************************************************
1052 *
1053 * FragFromBlock()
1054 *
1055 * This should return a fragment from the block and mark it as used
1056 * accordingly.
1057 *
1058 ***************************************************************************/
1059
1060static void *FragFromBlock(struct MemBlock *block)
1061{
1062 /* make frag point to the first free FRAGMENT */
1063 struct MemFrag *frag = block->first;
1064 struct MemInfo *mem = (struct MemInfo *)frag;
1065
1066 /*
1067 * Remove the FRAGMENT from the list and decrease the free counters.
1068 */
1069 block->first = frag->next; /* new first free FRAGMENT */
1070
1071 block->nfree--; /* BLOCK counter */
1072 block->top->nfree--; /* TOP counter */
1073
1074 /* heal the FRAGMENT list */
1075 if(frag->prev) {
1076 frag->prev->next = frag->next;
1077 }
1078 if(frag->next) {
1079 frag->next->prev = frag->prev;
1080 }
1081 mem->block = block; /* no block bit set here */
1082
1083 return ((char *)mem)+sizeof(struct MemInfo);
1084}
1085
1086/***************************************************************************
1087 *
1088 * dmalloc()
1089 *
1090 * This needs no explanation. A malloc() look-alike.
1091 *
1092 **************************************************************************/
1093
1094void *dmalloc(size_t size)
1095{
1096 void *mem;
1097
1098 DBG(("dmalloc(%d)\n", size));
1099
1100 if(!initialized)
1101 initialize();
1102
1103 /* First, we make room for the space needed in every allocation */
1104 size += sizeof(struct MemInfo);
1105
1106 if(size < DMEM_LARGESTSIZE) {
1107 /* get a FRAGMENT */
1108
1109 struct MemBlock *block=NULL; /* SAFE */
1110 struct MemBlock *newblock=NULL; /* SAFE */
1111 struct MemTop *memtop=NULL; /* SAFE */
1112
1113 /* Determine which queue to use */
1114 int queue;
1115 for(queue=0; size > qinfo[queue]; queue++)
1116 ;
1117 do {
1118 /* This is the head master of our chain: */
1119 memtop = &top[queue];
1120
1121 DBG(("Top info: %p %d %d %d\n",
1122 memtop->chain,
1123 memtop->nfree,
1124 memtop->nmax,
1125 memtop->fragsize));
1126
1127#ifdef SEMAPHORE
1128 if(SEMAPHOREOBTAIN(memtop->semaphore_id))
1129 return NULL; /* failed somehow */
1130#endif
1131
1132 /* get the first BLOCK in the chain */
1133 block = memtop->chain;
1134
1135 /* check if we have a free FRAGMENT */
1136 if(memtop->nfree) {
1137 /* there exists a free FRAGMENT in this chain */
1138
1139 /* I WANT THIS LOOP OUT OF HERE! */
1140
1141 /* search for the free FRAGMENT */
1142 while(!block->nfree)
1143 block = block->next; /* check next BLOCK */
1144
1145 /*
1146 * Now 'block' is the first BLOCK with a free FRAGMENT
1147 */
1148
1149 mem = FragFromBlock(block);
1150
1151 }
1152 else {
1153 /* we do *not* have a free FRAGMENT but need to get us a new BLOCK */
1154
1155 DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock),
1156 newblock,
1157 struct MemBlock *);
1158 if(!newblock) {
1159 if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) {
1160 /* There are queues for bigger FRAGMENTS that we should check
1161 before we fail this for real */
1162#ifdef DEBUG
1163 printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue);
1164#endif
1165 mem = NULL;
1166 }
1167 else {
1168 dmalloc_failed(size- sizeof(struct MemInfo));
1169 return NULL; /* not enough memory */
1170 }
1171 }
1172 else {
1173 /* allocation of big BLOCK was successful */
1174
1175 MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
1176
1177 memtop->chain = newblock; /* attach this BLOCK to the chain */
1178 newblock->next = block; /* point to the previous first BLOCK */
1179 if(block)
1180 block->prev = newblock; /* point back on this new BLOCK */
1181 newblock->prev = NULL; /* no previous */
1182 newblock->top = memtop; /* our head master */
1183
1184 /* point to the new first FRAGMENT */
1185 newblock->first = (struct MemFrag *)
1186 ((char *)newblock+sizeof(struct MemBlock));
1187
1188 /* create FRAGMENTS of the BLOCK: */
1189 FragBlock((char *)newblock->first, memtop->fragsize);
1190
1191#if defined(DEBUG) && !defined(BMALLOC)
1192 checkmem((char *)newblock);
1193#endif
1194
1195 /* fix the nfree counters */
1196 newblock->nfree = memtop->nmax;
1197 memtop->nfree += memtop->nmax;
1198
1199 /* get a FRAGMENT from the BLOCK */
1200 mem = FragFromBlock(newblock);
1201 }
1202 }
1203#ifdef SEMAPHORE
1204 SEMAPHORERETURN(memtop->semaphore_id); /* let it go */
1205#endif
1206 } while(NULL == mem); /* if we should retry a larger FRAGMENT */
1207 }
1208 else {
1209 /* get a stand-alone BLOCK */
1210 struct MemInfo *meminfo;
1211
1212 if(size&1)
1213 /* don't leave this with an odd size since we'll use that bit for
1214 information */
1215 size++;
1216
1217 DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *);
1218
1219 if(meminfo) {
1220 MEMINCR(meminfo, size);
1221 meminfo->block = (void *)(size|BLOCK_BIT);
1222 mem = (char *)meminfo + sizeof(struct MemInfo);
1223 }
1224 else {
1225 dmalloc_failed(size);
1226 mem = NULL;
1227 }
1228 }
1229 return (void *)mem;
1230}
1231
1232/***************************************************************************
1233 *
1234 * dfree()
1235 *
1236 * This needs no explanation. A free() look-alike.
1237 *
1238 **************************************************************************/
1239
1240void dfree(void *memp)
1241{
1242 struct MemInfo *meminfo = (struct MemInfo *)
1243 ((char *)memp- sizeof(struct MemInfo));
1244
1245 DBG(("dfree(%p)\n", memp));
1246
1247 if(!((size_t)meminfo->block&BLOCK_BIT)) {
1248 /* this is a FRAGMENT we have to deal with */
1249
1250 struct MemBlock *block=meminfo->block;
1251 struct MemTop *memtop = block->top;
1252
1253#ifdef SEMAPHORE
1254 SEMAPHOREOBTAIN(memtop->semaphore_id);
1255#endif
1256
1257 /* increase counters */
1258 block->nfree++;
1259 memtop->nfree++;
1260
1261 /* is this BLOCK completely empty now? */
1262 if(block->nfree == memtop->nmax) {
1263 /* yes, return the BLOCK to the system */
1264 if(block->prev)
1265 block->prev->next = block->next;
1266 else
1267 memtop->chain = block->next;
1268 if(block->next)
1269 block->next->prev = block->prev;
1270
1271 memtop->nfree -= memtop->nmax; /* total counter subtraction */
1272 MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
1273 DMEM_OSFREEMEM((void *)block); /* return the whole block */
1274 }
1275 else {
1276 /* there are still used FRAGMENTS in the BLOCK, link this one
1277 into the chain of free ones */
1278 struct MemFrag *frag = (struct MemFrag *)meminfo;
1279 frag->prev = NULL;
1280 frag->next = block->first;
1281 if(block->first)
1282 block->first->prev = frag;
1283 block->first = frag;
1284 }
1285#ifdef SEMAPHORE
1286 SEMAPHORERETURN(memtop->semaphore_id);
1287#endif
1288 }
1289 else {
1290 /* big stand-alone block, just give it back to the OS: */
1291 MEMDECR(&meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */
1292 DMEM_OSFREEMEM((void *)meminfo);
1293 }
1294}
1295
1296/***************************************************************************
1297 *
1298 * drealloc()
1299 *
1300 * This needs no explanation. A realloc() look-alike.
1301 *
1302 **************************************************************************/
1303
1304void *drealloc(char *ptr, size_t size)
1305{
1306 struct MemInfo *meminfo = (struct MemInfo *)
1307 ((char *)ptr- sizeof(struct MemInfo));
1308 /*
1309 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1310 * NOTE: the ->size field of the meminfo will now contain the MemInfo
1311 * struct size too!
1312 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1313 */
1314 void *mem=NULL; /* SAFE */
1315 size_t prevsize;
1316
1317 /* NOTE that this is only valid if BLOCK_BIT isn't set: */
1318 struct MemBlock *block;
1319
1320 DBG(("drealloc(%p, %d)\n", ptr, size));
1321
1322 if(NULL == ptr)
1323 return dmalloc( size );
1324
1325 block = meminfo->block;
1326
1327 if(!((size_t)meminfo->block&BLOCK_BIT) &&
1328 (size + sizeof(struct MemInfo) <
1329 (prevsize = block->top->fragsize) )) {
1330 /* This is a FRAGMENT and new size is possible to retain within the same
1331 FRAGMENT */
1332 if((prevsize > qinfo[0]) &&
1333 /* this is not the smallest memory Q */
1334 (size < (block->top-1)->fragsize))
1335 /* this fits in a smaller Q */
1336 ;
1337 else
1338 mem = ptr; /* Just return the same pointer as we got in. */
1339 }
1340 if(!mem) {
1341 /* This is a stand-alone BLOCK or a realloc that no longer fits within
1342 the same FRAGMENT */
1343
1344 if((size_t)meminfo->block&BLOCK_BIT) {
1345 prevsize = ((size_t)meminfo->block&~BLOCK_BIT) -
1346 sizeof(struct MemInfo);
1347 }
1348 else
1349 prevsize -= sizeof(struct MemInfo);
1350
1351 /* No tricks involved here, just grab a new bite of memory, copy the data
1352 * from the old place and free the old memory again. */
1353 mem = dmalloc(size);
1354 if(mem) {
1355 memcpy(mem, ptr, MIN(size, prevsize) );
1356 dfree(ptr);
1357 }
1358 }
1359 return mem;
1360}
1361
1362/***************************************************************************
1363 *
1364 * dcalloc()
1365 *
1366 * This needs no explanation. A calloc() look-alike.
1367 *
1368 **************************************************************************/
1369/* Allocate an array of NMEMB elements each SIZE bytes long.
1370 The entire array is initialized to zeros. */
1371void *
1372dcalloc (size_t nmemb, size_t size)
1373{
1374 void *result = dmalloc (nmemb * size);
1375
1376 if (result != NULL)
1377 memset (result, 0, nmemb * size);
1378
1379 return result;
1380}
diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h
new file mode 100644
index 0000000000..053b3a114b
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h
@@ -0,0 +1,16 @@
1
2void *dmalloc(size_t);
3void dfree(void *);
4void *drealloc(void *, size_t);
5
6#define malloc(x) dmalloc(x)
7#define free(x) dfree(x)
8#define realloc(x,y) drealloc(x,y)
9
10void *dmalloc(size_t);
11void dfree(void *);
12void *drealloc(void *, size_t);
13
14#define malloc(x) dmalloc(x)
15#define free(x) dfree(x)
16#define realloc(x,y) drealloc(x,y)
diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmytest.c b/apps/plugins/pdbox/dbestfit-3.3/dmytest.c
new file mode 100644
index 0000000000..46d4c73efd
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/dmytest.c
@@ -0,0 +1,276 @@
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}
139#include <stdio.h>
140#include <stdlib.h>
141
142#include "dmalloc.h"
143
144#define MAX 500
145#define MAX2 1000
146#define MAXC 2
147
148#define TESTA
149#define TESTB
150#define TESTC
151#define TESTD
152
153int main(int argc, char **argv)
154{
155 int i;
156 int memory = 0;
157
158#ifdef BMALLOC
159#define HEAP 10000
160 void *heap = (malloc)(HEAP);
161 if(!heap)
162 return -1;
163 add_pool(heap, HEAP);
164#endif
165
166 {
167#define MAXK 100
168 void *wow[MAXK];
169 wow[0]=malloc(700);
170 realloc(wow[0], 680);
171 return 0;
172
173 for(i=0; i<MAXK; i++)
174 if(!(wow[i]=malloc(412))) {
175 printf("*** Couldn't allocated memory, exiting\n");
176 return -2;
177 }
178 for(i=MAXK-1; i>=0; i-=2)
179 free(wow[i]);
180 return 0;
181 }
182
183
184#ifdef TESTD
185 {
186#define MAXS 10
187#define MAXS1 0
188 void *ptr[MAXS];
189
190 for(i=MAXS1; i< MAXS; i++) {
191 printf("%d malloc(%d)\n", i, i*55);
192 ptr[i] = malloc (i*55);
193 }
194 for(i=MAXS1; i< MAXS; i++) {
195 void *tmp;
196 printf("%d realloc(%d)\n", i, i*155);
197 tmp=realloc(ptr[i], i*155);
198 if(tmp)
199 ptr[i] = tmp;
200 }
201 for(i=MAXS1; i< MAXS; i++) {
202 printf("%d free(%d)\n", i, i*155);
203 free(ptr[i]);
204 }
205 }
206#endif
207
208#ifdef TESTC
209 {
210 void *ptr[MAXC];
211 printf("This is test C:\n");
212
213 for(i=0; i< MAXC; i++) {
214 printf("%d malloc(100)\n", i+1);
215 ptr[i] = malloc(100);
216 printf(" ...returned %p\n", ptr[i]);
217 }
218
219 for(i=0; i< MAXC; i++) {
220 printf("%d free()\n", i+1);
221 free(ptr[i]);
222 }
223
224 printf("End of test C:\n");
225 }
226#endif
227
228#ifdef TESTA
229 {
230 void *pointers[MAX];
231 printf("This is test I:\n");
232
233 for(i=0; i<MAX; i++) {
234 printf("%d attempts malloc(%d)\n", i, i*6);
235 pointers[i]=malloc(i*6);
236 if(!pointers[i]) {
237 printf("cant get more memory!");
238 return(0);
239 }
240 memory += (i*6);
241 }
242 printf("\namount: %d\n", memory);
243 memory = 0;
244 for(i=0; i<MAX; i++) {
245 printf("%d attempts realloc(%d)\n", i, i*7);
246 pointers[i]=realloc(pointers[i], i*7);
247 memory += i*7;
248 }
249 printf("\namount: %d\n", memory);
250 for(i=0; i<MAX; i++) {
251 printf("%d attempts free(%d)\n", i, i*7);
252 free(pointers[i]);
253 }
254 printf("\nend of test 1\n");
255 }
256#endif
257#ifdef TESTB
258 {
259 void *pointers2[MAX2];
260 memory = 0;
261 printf("\nTest II\n");
262 for(i=0; i< MAX2; i++) {
263/* printf("%d attempts malloc(%d)\n", i, 7); */
264 pointers2[i] = malloc(7);
265 memory += 7;
266 }
267 printf("\namount: %d\n", memory);
268 for(i=0; i< MAX2; i++) {
269 free(pointers2[i]);
270 }
271 printf("\nend of test II\n");
272
273 }
274#endif
275 return 0;
276}
diff --git a/apps/plugins/pdbox/dbestfit-3.3/malloc.man b/apps/plugins/pdbox/dbestfit-3.3/malloc.man
new file mode 100644
index 0000000000..79f6f3ea37
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/malloc.man
@@ -0,0 +1,190 @@
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.
96MALLOC(3V) C LIBRARY FUNCTIONS MALLOC(3V)
97
98
99NAME
100 malloc, free, realloc, calloc
101
102SYNOPSIS
103 #include <malloc.h>
104
105 void *malloc(size)
106 size_t size;
107
108 void free(ptr)
109 void *ptr;
110
111 void *realloc(ptr, size)
112 void *ptr;
113 size_t size;
114
115 void *calloc(nelem, elsize)
116 size_t nelem;
117 size_t elsize;
118
119DESCRIPTION
120 These routines provide a general-purpose memory allocation
121 package. They maintain a table of free blocks for efficient
122 allocation and coalescing of free storage. When there is no
123 suitable space already free, the allocation routines call
124 rn_getseg() to get more memory from the system.
125
126 Each of the allocation routines returns a pointer to space
127 suitably aligned for storage of any type of object. Each
128 returns a NULL pointer if the request cannot be completed
129 (see DIAGNOSTICS).
130
131 malloc() returns a pointer to a block of at least size
132 bytes, which is appropriately aligned.
133
134 free() releases a previously allocated block. Its argument
135 is a pointer to a block previously allocated by malloc(),
136 calloc() or realloc().
137
138 realloc() changes the size of the block referenced by ptr to
139 size bytes and returns a pointer to the (possibly moved)
140 block. The contents will be unchanged up to the lesser of
141 the new and old sizes. If unable to honor a reallocation
142 request, realloc() leaves its first argument unaltered.
143
144 **** DMALLOC DOES NOT COMPLY WITH THE PARAGRAPH BELOW ****
145
146 For backwards compatibility, realloc() accepts a pointer to a
147 block freed since the most recent call to malloc(), cal-
148 loc() or realloc().
149
150 Note: using realloc() with a block freed before the most recent
151 call to malloc(), calloc() or realloc() is an error.
152
153 calloc() uses malloc() to allocate space for an array of
154 nelem elements of size elsize, initializes the space to
155 zeros, and returns a pointer to the initialized block. The
156 block should be freed with free().
157
158
159 malloc() and realloc() return a non- NULL pointer if size is 0,
160 and calloc() returns a non-NULL pointer if nelem or elsize is 0,
161 but these pointers should not be dereferenced.
162
163 Note: Always cast the value returned by malloc(), realloc() or
164 calloc().
165
166
167RETURN VALUES On success, malloc(), calloc() and realloc() return a
168 pointer to space suitably aligned for storage of any type of
169 object. On failure, they return NULL.
170
171 free() does not return a value.
172
173
174NOTES
175 Because malloc() and realloc() return a non-NULL pointer if size
176 is 0, and calloc() returns a non-NULL pointer if nelem or elsize
177 is 0, a zero size need not be treated as a special case if it
178 should be passed to these functions unpredictably. Also, the
179 pointer returned by these functions may be passed to subsequent
180 invocations of realloc().
181
182
183BUGS
184
185 **** DMALLOC DOES NOT COMPLY WITH THE PARAGRAPH BELOW ****
186
187 Since realloc() accepts a pointer to a block freed since the last
188 call to malloc(), calloc() or realloc(), a degradation of
189 performance results. The semantics of free() should be changed
190 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
new file mode 100644
index 0000000000..bf338b72ef
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/mytest.c
@@ -0,0 +1,140 @@
1
2#include <stdio.h>
3#include <stdlib.h>
4
5#include "bmalloc.h"
6
7int main(int argc, char **argv)
8{
9 void *pointers[5];
10 int i;
11 void *area;
12
13 for(i=0; i<5; i++)
14 pointers[i] = malloc(8000);
15
16 if(argc>1) {
17 switch(argv[1][0]) {
18 case '1':
19 for(i=0; i<5; i++) {
20 add_pool(pointers[i], 4000);
21 add_pool((char *)pointers[i]+4000, 4000);
22 }
23 break;
24 case '2':
25 area = malloc(20000);
26 add_pool(area, 3000);
27 add_pool((char *)area+6000, 3000);
28 add_pool((char *)area+3000, 3000);
29 add_pool((char *)area+12000, 3000);
30 add_pool((char *)area+9000, 3000);
31 break;
32 case '3':
33 {
34 void *ptr[10];
35 area = malloc(20000);
36 add_pool(area, 20000);
37
38 printf(" ** TEST USAGE\n");
39 for(i=0; i<9; i++)
40 ptr[i]=bmalloc(200);
41 print_lists();
42 for(i=0; i<9; i++)
43 bfree(ptr[i]);
44 printf(" ** END OF TEST USAGE\n");
45 }
46
47 break;
48 case '4':
49 {
50 void *ptr[10];
51 area = malloc(20000);
52 add_pool(area, 20000);
53
54 ptr[0]=bmalloc(4080);
55 print_lists();
56 bfree(ptr[0]);
57 printf(" ** END OF TEST USAGE\n");
58 }
59
60 break;
61 }
62 }
63 else
64 for(i=4; i>=0; i--)
65 add_pool(pointers[i], 8000-i*100);
66
67 print_lists();
68
69 return 0;
70}
71
72#include <stdio.h>
73#include <stdlib.h>
74
75#include "bmalloc.h"
76
77int main(int argc, char **argv)
78{
79 void *pointers[5];
80 int i;
81 void *area;
82
83 for(i=0; i<5; i++)
84 pointers[i] = malloc(8000);
85
86 if(argc>1) {
87 switch(argv[1][0]) {
88 case '1':
89 for(i=0; i<5; i++) {
90 add_pool(pointers[i], 4000);
91 add_pool((char *)pointers[i]+4000, 4000);
92 }
93 break;
94 case '2':
95 area = malloc(20000);
96 add_pool(area, 3000);
97 add_pool((char *)area+6000, 3000);
98 add_pool((char *)area+3000, 3000);
99 add_pool((char *)area+12000, 3000);
100 add_pool((char *)area+9000, 3000);
101 break;
102 case '3':
103 {
104 void *ptr[10];
105 area = malloc(20000);
106 add_pool(area, 20000);
107
108 printf(" ** TEST USAGE\n");
109 for(i=0; i<9; i++)
110 ptr[i]=bmalloc(200);
111 print_lists();
112 for(i=0; i<9; i++)
113 bfree(ptr[i]);
114 printf(" ** END OF TEST USAGE\n");
115 }
116
117 break;
118 case '4':
119 {
120 void *ptr[10];
121 area = malloc(20000);
122 add_pool(area, 20000);
123
124 ptr[0]=bmalloc(4080);
125 print_lists();
126 bfree(ptr[0]);
127 printf(" ** END OF TEST USAGE\n");
128 }
129
130 break;
131 }
132 }
133 else
134 for(i=4; i>=0; i--)
135 add_pool(pointers[i], 8000-i*100);
136
137 print_lists();
138
139 return 0;
140}
diff --git a/apps/plugins/pdbox/dbestfit-3.3/thoughts b/apps/plugins/pdbox/dbestfit-3.3/thoughts
new file mode 100644
index 0000000000..8dbd8b9979
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/thoughts
@@ -0,0 +1,340 @@
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
171 =====================================
172 Memory Allocation Algorithm Theories.
173 =====================================
174
175GOAL
176 It is intended to be a 100% working memory allocation system. It should be
177 capable of replacing an ordinary Operating System's own routines. It should
178 work good in a multitasking, shared memory, non-virtual memory environment
179 without clogging the memory. Primary aimed for small machines, CPUs and
180 memory amounts.
181
182 I use a best-fit algorithm with a slight overhead in order to increase speed
183 a lot. It should remain scalable and work good with very large amount of
184 memory and free/used memory blocks too.
185
186TERMINOLOGY
187
188 FRAGMENT - small identically sized parts of a larger BLOCK, they are when
189 travered in lists etc _not_ allocated.
190 BLOCK - large memory area, if used for FRAGMENTS, they are linked in a
191 lists. One list for each FRAGMENT size supported.
192 TOP - head struct that holds information about and points to a chain
193 of BLOCKS for a particular FRAGMENT size.
194 CHUNK - a contiguous area of free memory
195
196MEMORY SYSTEM
197
198 We split the system in two parts. One part allocates small memory amounts
199 and one part allocates large memory amounts, but all allocations are done
200 "through" the small-part-system. There is an option to use only the small
201 system (and thus use the OS for large blocks) or the complete package.
202
203##############################################################################
204 SMALL SIZE ALLOCATIONS
205##############################################################################
206
207 Keywords for this system is 'Deferred Coalescing' and 'quick lists'.
208
209 ALLOC
210
211 * Small allocations are "aligned" upwards to a set of preset sizes. In the
212 current implementation I use 20, 28, 52, 116, 312, 580, 812, 2028 bytes.
213 Memory allocations of these sizes are refered to as FRAGMENTS.
214 (The reason for these specific sizes is the requirement that they must be
215 32-bit aligned and fit as good as possible within 4060 bytes.)
216
217 * Allocations larger than 2028 will get a BLOCK for that allocation only.
218
219 * Each of these sizes has it's own TOP. When a FRAGMENT is requested, a
220 larger BLOCK will be allocated and divided into many FRAGMENTS (all of the
221 same size). TOP points to a list with BLOCKS that contains FRAGMENTS of
222 the same size. Each BLOCK has a 'number of free FRAGMENTS' counter and so
223 has each TOP (for the entire chain).
224
225 * A BLOCK is around 4060 bytes plus the size of the information header. This
226 size is adjusted to make the allocation of the big block not require more
227 than 4096 bytes. (This might not be so easy to be sure of, if you don't
228 know how the big-block system works, but the BMALLOC system uses an
229 extra header of 12 bytes and the header for the FRAGMENT BLOCK is 20 bytes
230 in a general 32-bit unix environment.)
231
232 * In case the allocation of a BLOCK fails when a FRAGMENT is required, the
233 next size of FRAGMENTS will be checked for a free FRAGMENT. First when the
234 larger size lists have been tested without success it will fail for real.
235
236 FREE
237
238 * When FRAGMENTS are freed so that a BLOCK becomes non-used, it is returned
239 to the system.
240
241 * FREEing a fragment adds the buffer in a LIFO-order. That means that the
242 next request for a fragment from the same list, the last freed buffer will
243 be returned first.
244
245 REALLOC
246
247 * REALLOCATION of a FRAGMENT does first check if the new size would fit
248 within the same FRAGMENT and if it would use the same FRAGMENT size. If it
249 does and would, the same pointer is returned.
250
251 OVERHEAD
252
253 Yes, there is an overhead on small allocations (internal fragmentation).
254 Yet, I do believe that small allocations more often than larger ones are
255 used dynamically. I believe that a large overhead is not a big problem if it
256 remains only for a while. The big gain is with the extreme speed we can GET
257 and RETURN small allocations. This has yet to be proven. I am open to other
258 systems of dealing with the small ones, but I don`t believe in using the
259 same system for all sizes of allocations.
260
261 IMPROVEMENT
262
263 An addition to the above described algorithm is the `save-empty-BLOCKS-a-
264 while-afterwards`. It will be used when the last used FRAGMENT within a
265 BLOCK is freed. The BLOCK will then not get returned to the system until "a
266 few more" FRAGMENTS have been freed in case the last [few] freed FRAGMENTS
267 are allocated yet again (and thus prevent the huge overhead of making
268 FRAGMENTS in a BLOCK). The "only" drawback of such a SEBAWA concept is
269 that it would mean an even bigger overhead...
270
271 HEADERS (in allocated data)
272
273 FRAGMENTS - 32-bit pointer to its parent BLOCK (lowest bit must be 0)
274 BLOCK - 32-bit size (lowest bit must be 1 to separate this from
275 FRAGMENTS)
276
277##############################################################################
278 LARGER ALLOCATIONS
279##############################################################################
280
281 If the requested size is larger than the largest FRAGMENT size supported,
282 the allocation will be made for this memory area alone, or if a BLOCK is
283 allocated to fit lots of FRAGMENTS a large block is also desired.
284
285 * We add memory to the "system" with the add_pool() function call. It
286 specifies the start and size of the new block of memory that will be
287 used in this memory allocation system. Several add_pool() calls are
288 supported and they may or may not add contiguous memory.
289
290 * Make all blocks get allocated aligned to BLOCKSIZE (sometimes referred to
291 as 'grain size'), 64 bytes in my implementation. Reports tell us there is
292 no real gain in increasing the size of the align.
293
294 * We link *all* pieces of memory (AREAS), free or not free. We keep the list
295 in address order and thus when a FREE() occurs we know instanstly if there
296 are FREE CHUNKS wall-to-wall. No list "travels" needed. Requires some
297 extra space in every allocated BLOCK. Still needs to put the new CHUNK in
298 the right place in size-sorted list/tree. All memory areas, allocated or
299 not, contain the following header:
300 - size of this memory area
301 - FREE status
302 - pointer to the next AREA closest in memory
303 - pointer to the prev AREA closest in memory
304 (12 bytes)
305
306 * Sort all FREE CHUNKS in size-order. We use a SPLAY TREE algorithm for
307 maximum speed. Data/structs used for the size-sorting functions are kept
308 in an abstraction layer away from this since it is really not changing
309 anything (except executing speed).
310
311 ALLOC (RSIZE - requested size, aligned properly)
312
313 * Fetch a CHUNK that RSIZE fits within. If the found CHUNK is larger than
314 RSIZE, split it and return the RSIZE to the caller. Link the new CHUNK
315 into the list/tree.
316
317 FREE (AREA - piece of memory that is returned to the system)
318
319 * Since the allocated BLOCK has kept its link-pointers, we can without
320 checking any list instantly see if there are any FREE CHUNKS that are
321 wall-to-wall with the AREA (both sides). If the AREA *is* wall-to-wall
322 with one or two CHUNKS that or they are unlinked from the lists, enlarged
323 and re-linked into the lists.
324
325 REALLOC
326
327 * There IS NO realloc() of large blocks, they are performed in the higher
328 layer (dmalloc).
329
330
331##############################################################################
332 FURTHER READING
333##############################################################################
334
335 * "Dynamic Storage Allocation: A Survey and Critical Review" (Paul R. Wilson,
336 Mark S. Johnstone, Michael Neely, David Boles)
337 ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps
338
339 * "A Memory Allocator" (Doug Lea)
340 http://g.oswego.edu/dl/html/malloc.html
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-17 21:56:15 +0000