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/CHANGES12
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/FILES15
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/Makefile38
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/Malloc.c202
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/README23
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bmalloc.c371
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bmalloc.h7
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bysize.c424
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bysize.h4
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmalloc.c690
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmalloc.h9
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmytest.c138
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/malloc.man95
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/mytest.c71
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/thoughts170
15 files changed, 0 insertions, 2269 deletions
diff --git a/apps/plugins/pdbox/dbestfit-3.3/CHANGES b/apps/plugins/pdbox/dbestfit-3.3/CHANGES
index f244f66f87..7f63d384fa 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/CHANGES
+++ b/apps/plugins/pdbox/dbestfit-3.3/CHANGES
@@ -10,15 +10,3 @@ Changes
10* 3.2 10* 3.2
11 11
12 Made eons ago, all older changes have been forgotten. 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
index 684a225972..6076c5fe20 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/FILES
+++ b/apps/plugins/pdbox/dbestfit-3.3/FILES
@@ -13,18 +13,3 @@
13/thoughts 13/thoughts
14/malloc.man 14/malloc.man
15/CHANGES 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
index e34b02e918..fc1e7e68d9 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/Makefile
+++ b/apps/plugins/pdbox/dbestfit-3.3/Makefile
@@ -36,41 +36,3 @@ tgz:
36 36
37clean: 37clean:
38 rm -f *.o *~ $(TARGET1) $(TARGET2) $(TARGET3) 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
index 25e30706fe..10b02c94ec 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/Malloc.c
+++ b/apps/plugins/pdbox/dbestfit-3.3/Malloc.c
@@ -198,205 +198,3 @@ int main(void)
198 printf("\n"); 198 printf("\n");
199 return 0; 199 return 0;
200} 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
index 919875df96..7452e36279 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/README
+++ b/apps/plugins/pdbox/dbestfit-3.3/README
@@ -19,26 +19,3 @@ TODO:
19 19
20 * Make a separate application that samples the memory usage of a program 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). 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
index f95b4f6125..35cafb8f96 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c
+++ b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c
@@ -367,374 +367,3 @@ void bfree(void *ptr)
367#endif 367#endif
368 368
369} 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
index 4f77667290..550aa5a010 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h
+++ b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.h
@@ -3,10 +3,3 @@ void print_lists();
3 3
4void *bmalloc(size_t size); 4void *bmalloc(size_t size);
5void bfree(void *ptr); 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
index 6808406dbc..85dc327491 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/bysize.c
+++ b/apps/plugins/pdbox/dbestfit-3.3/bysize.c
@@ -422,427 +422,3 @@ void print_sizes(void)
422} 422}
423 423
424#endif 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
index 2fbf23154d..877e2ea4c5 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/bysize.h
+++ b/apps/plugins/pdbox/dbestfit-3.3/bysize.h
@@ -2,7 +2,3 @@ void remove_chunksize(void *data);
2void insert_bysize(char *data, size_t size); 2void insert_bysize(char *data, size_t size);
3char *obtainbysize( size_t size); 3char *obtainbysize( size_t size);
4void print_sizes(void); 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
index 9336276883..6ce38cced0 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
+++ b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
@@ -688,693 +688,3 @@ dcalloc (size_t nmemb, size_t size)
688 688
689 return result; 689 return result;
690} 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
index 053b3a114b..9921e3b94a 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h
+++ b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.h
@@ -1,12 +1,3 @@
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); 1void *dmalloc(size_t);
11void dfree(void *); 2void dfree(void *);
12void *drealloc(void *, size_t); 3void *drealloc(void *, size_t);
diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmytest.c b/apps/plugins/pdbox/dbestfit-3.3/dmytest.c
index 46d4c73efd..ed12686b3d 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/dmytest.c
+++ b/apps/plugins/pdbox/dbestfit-3.3/dmytest.c
@@ -136,141 +136,3 @@ int main(int argc, char **argv)
136#endif 136#endif
137 return 0; 137 return 0;
138} 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
index 79f6f3ea37..8b6e3dbea5 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/malloc.man
+++ b/apps/plugins/pdbox/dbestfit-3.3/malloc.man
@@ -93,98 +93,3 @@ BUGS
93 call to malloc(), calloc() or realloc(), a degradation of 93 call to malloc(), calloc() or realloc(), a degradation of
94 performance results. The semantics of free() should be changed 94 performance results. The semantics of free() should be changed
95 so that the contents of a previously freed block are undefined. 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
index bf338b72ef..80407dee00 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/mytest.c
+++ b/apps/plugins/pdbox/dbestfit-3.3/mytest.c
@@ -1,74 +1,3 @@
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> 1#include <stdio.h>
73#include <stdlib.h> 2#include <stdlib.h>
74 3
diff --git a/apps/plugins/pdbox/dbestfit-3.3/thoughts b/apps/plugins/pdbox/dbestfit-3.3/thoughts
index 8dbd8b9979..d509d36d2a 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/thoughts
+++ b/apps/plugins/pdbox/dbestfit-3.3/thoughts
@@ -168,173 +168,3 @@ MEMORY SYSTEM
168 168
169 * "A Memory Allocator" (Doug Lea) 169 * "A Memory Allocator" (Doug Lea)
170 http://g.oswego.edu/dl/html/malloc.html 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 22:14:06 +0000