apps/plugins/pdbox/dbestfit-3.3/dmalloc.c

   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 */
  45 struct 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 */
  58 struct 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 */
  69 struct 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
  78 struct 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 */
 160 short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
 161 #else
 162 short 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 */
 174 static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
 175
 176 /* are we experienced? */
 177 static 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
 189 static 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
 213 static 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
 226 void *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
 246 void 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
 265 void 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
 283 void syslog(char *fmt, ...)
 284 {
 285   va_list ap;
 286   va_start(ap, fmt);
 287   vfprintf(stdout, fmt, ap);
 288   va_end(ap);
 289 }
 290
 291 void 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
 313 static 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  **************************************************************************/
 336 static 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
 370 static 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
 404 void *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
 550 void 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
 614 void *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.  */
 681 void *
 682 dcalloc (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 */
 735 struct 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 */
 748 struct 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 */
 759 struct 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
 768 struct 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 */
 850 short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
 851 #else
 852 short 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 */
 864 static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
 865
 866 /* are we experienced? */
 867 static 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
 879 static 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
 903 static 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
 916 void *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
 936 void 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
 955 void 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
 973 void syslog(char *fmt, ...)
 974 {
 975   va_list ap;
 976   va_start(ap, fmt);
 977   vfprintf(stdout, fmt, ap);
 978   va_end(ap);
 979 }
 980
 981 void 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
1003 static 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  **************************************************************************/
1026 static 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
1060 static 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
1094 void *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
1240 void 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
1304 void *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.  */
1371 void *
1372 dcalloc (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 }