home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / cm3.zip / CMALLOC.C next >
C/C++ Source or Header  |  1995-02-12  |  28KB  |  1,228 lines
  1. /* CMALLOC ===================== MULTI HEAP MALLOC ========================== 
  2.  * 
  3.  *  Copyright (c) 1995
  4.  *  Norman D. Culver dba Oxbow Software
  5.  *  1323 S.E. 17th Street #662
  6.  *  Ft. Lauderdale, FL 33316
  7.  *  (305) 527-1663 Voice
  8.  *  (305) 760-7584 Fax
  9.  *  (305) 760-4679 Data
  10.  *  ndc@fhd486.harvard.edu
  11.  *  norman.culver@channel1.com
  12.  *  All rights reserved.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted
  15.  * provided that: (1) source distributions retain this entire copyright
  16.  * notice and comment, and (2) distributions including binaries display
  17.  * the following acknowledgement:  ``This product includes software
  18.  * developed by Norman D. Culver dba Oxbow Software''
  19.  * in the documentation or other materials provided with the distribution
  20.  * and in all advertising materials mentioning features or use of this
  21.  * software.
  22.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  23.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  24.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25.  
  26.     
  27.     This implementation of malloc has some unique features.
  28.  
  29.       1. Multiple heaps (categories) are very convenient because
  30.          the programmer can free an entire category of allocations
  31.          instead of ensuring that each malloc is paired with a free.
  32.       2. It is implemented with skip lists.
  33.       3. Nevertheless it competes favorably with BSD malloc for speed
  34.          and total space consumed.
  35.       4. If 'USEDLIST' is defined == 1, then allocated memory is never
  36.          touched. In a demand paging situation this method is ENORMOUSLY
  37.          faster than conventional mallocs which store bookkeeping info
  38.          in the allocated area and thus can/will cause thrashing when
  39.          space is allocated or freed.
  40.       5. With some minor modifications this implementation would make
  41.          a respectable disk allocator.
  42.       6. Individual categories can be set to 'guarded' mode in which
  43.          case guard words are stored at the front and back of each
  44.          allocation, the guard words are tested when the space is
  45.          freed or reallocated. If 'USEDLIST' == 1, then the function
  46.          Ccatcheck(int category, void *startaddr) will walk the heap
  47.          forward from 'startaddr' and return a bad address or 0.
  48. */
  49.     
  50. extern void *sbrk(unsigned);
  51. extern void bzero(void*,unsigned);
  52. extern void memmove(void*,void*,unsigned);
  53. extern int printf(const char *fmt, ...);
  54. extern int vprintf();
  55. extern void abort(void);
  56.  
  57. static void *do_sbrk(unsigned amount);
  58. static void print_freenodes(int);
  59.  
  60. /* User API */
  61. static void *Cmalloc(int category, unsigned amount);
  62. static void *Ccalloc(int category, unsigned nelems, unsigned elemsize);
  63. static void *Crealloc(int category, void* buf, unsigned newsize);
  64. static void Cfree(int category, void* buf);
  65. static void Cfreecat(int category);
  66. static int Cmemrange(int category, unsigned* minp, unsigned* maxp);
  67. static int Cusedrange(int category, unsigned* minp, unsigned* maxp);
  68. static void Ctotrange(unsigned* minp,unsigned* maxp);
  69. static int Cnewcat(void);
  70. static void *Ccatcheck(int category, void *start);
  71. static void Cguard(int category);
  72. /* END: User API */
  73.  
  74. #define DEBUG 0
  75. #define DEBUG_STATISTICS 0
  76. #define DEBUG_USEDNODES 0
  77. #define DEBUG_SPARES 0
  78.  
  79. #define USEDLIST 1    /* adds 13 bytes of nodespace per allocation */
  80. #define ALIGNMENT (sizeof(int))
  81. #define MAXLEVEL (15)
  82. #define ROUNDING(a) ((ALIGNMENT-((a)&(ALIGNMENT-1)))&(ALIGNMENT-1))
  83. #define ALLOCSIZE (4096)
  84. #define GUARDWORD (0xa7b3a7b3)
  85. #define THEWELL do_sbrk
  86. #define PRINTF printf
  87. #define VPRINTF vprintf
  88. #define PERROR prerror
  89.  
  90. #if USEDLIST
  91. #define NUMTYPES 3
  92. #define SIZE 0
  93. #define FREE 1
  94. #define USED 2
  95. #else
  96. #define NUMTYPES 2
  97. #define SIZE 0
  98. #define FREE 1
  99. #endif
  100.  
  101. #define SKIPVARS NodeP update[MAXLEVEL+1];NodeP node,prev;int level
  102.  
  103. #define DELETENODE(TYPE) \
  104. {for(level=0;level<=bp->TYPE##level; level++)\
  105. {if(update[level]->fptr[level] == node)\
  106. update[level]->fptr[level] = node->fptr[level];else break;}\
  107. while(bp->TYPE##level>0 && bp->TYPE##header->fptr[bp->TYPE##level]==_NIL)\
  108. bp->TYPE##level--;free_node(bp,node,TYPE);}
  109.  
  110. #define INSERT() \
  111. {while(level >= 0){\
  112. node->fptr[level] = update[level]->fptr[level];\
  113. update[level]->fptr[level] = node;level--;}}
  114.  
  115. #define SETLEVEL(TYPE) \
  116. {level = getlevel(bp, bp->TYPE##level);\
  117. while(bp->TYPE##level < level)update[++bp->TYPE##level]=bp->TYPE##header;}
  118.  
  119. #define FINDKEY(TYPE, KEYVAL)\
  120. {node = bp->TYPE##header;\
  121. for(level = bp->TYPE##level; level >= 0; level--){\
  122. while(node->fptr[level]->key < KEYVAL)\
  123. node = node->fptr[level];\
  124. update[level] = node;}prev=node;node=node->fptr[0];}
  125.  
  126. #define DETACH(SN)\
  127. {SN->bptr->fptr=SN->fptr;if(SN->fptr)SN->fptr->bptr=SN->bptr;}
  128.  
  129. #define UNLINK(SN, N)\
  130. {if(!sp->fptr&&sp->bptr->bptr<=(AddrP)(MAXLEVEL+1))dsize[N]=sp->size;\
  131. DETACH(SN);free_addr(bp,SN);}
  132.  
  133. #if USEDLIST
  134. #define CHECKGUARDS(MSG)\
  135. {if(bp->guarded){\
  136. unsigned *p2;\
  137. p2 = (void*)((char*)address+cursize-ALIGNMENT);\
  138. if(*address != (unsigned)GUARDWORD)\
  139. PERROR(#MSG ": heap(%d) corrupted at 0x%x\n", bp->bincat, addr);\
  140. if(*p2 != ~((unsigned)GUARDWORD))\
  141. PERROR(#MSG ": heap(%d) corrupted by 0x%x\n", bp->bincat, addr);}}
  142. #else
  143. #define CHECKGUARDS(MSG)\
  144. {if(bp->guarded){\
  145. unsigned *p2;\
  146. address = (void*)((char*)address-ALIGNMENT);\
  147. p2 = (void*)((char*)address+cursize-ALIGNMENT);\
  148. if(*address != (unsigned)GUARDWORD)\
  149. PERROR(#MSG ": heap(%d) corrupted at 0x%x\n", bp->bincat, addr);\
  150. if(*p2 != ~((unsigned)GUARDWORD))\
  151. PERROR(#MSG ": heap(%d) corrupted by 0x%x\n", bp->bincat, addr);}}
  152. #endif
  153.  
  154. struct _catlocs {
  155.     void *addr;
  156.     struct _catlocs *fptr;
  157. };
  158.  
  159. typedef struct _node
  160. {
  161.     unsigned key;
  162.     unsigned value;
  163.     unsigned levels;    /* must always be after value */
  164.     struct _node *fptr[1];
  165. } Node, *NodeP;
  166.  
  167. typedef struct _addr
  168. {
  169.     struct _addr *fptr;
  170.     struct _addr *bptr;
  171.     NodeP maddr;
  172.     unsigned size;
  173. } *AddrP;
  174.  
  175. struct _bins {
  176.     unsigned bits;
  177.     unsigned nbits;
  178.     NodeP SIZEheader;
  179.     int SIZElevel;
  180.     NodeP FREEheader;
  181.     int FREElevel; 
  182. #if USEDLIST
  183.     NodeP USEDheader;
  184.     int USEDlevel;
  185. #endif
  186.     unsigned bincat;
  187.     unsigned maxloc;
  188.     unsigned minloc;
  189.     struct _catlocs *catlocs;
  190.     struct _bins *fptr;
  191.     NodeP freenodes[NUMTYPES][MAXLEVEL+2];
  192.     struct _addr *freeaddrlocs;
  193.     char *chunkbase[NUMTYPES];
  194.     int chunksize[NUMTYPES];
  195.     int guarded;
  196.     int addrbump;
  197.     int overhead;
  198. } zbp;
  199.  
  200. static struct _bins *hmap[1009];
  201. static struct _node _nil = {0xffffffff,0,0,0};
  202. static struct _node *_NIL = &_nil;
  203. static unsigned maxloc;
  204. static unsigned minloc;
  205. static struct _bins *freebinlocs;
  206. struct _catlocs *freecatlocs;
  207. static char *binbase;
  208. static int binsize;
  209. static int chunksizes[] = {ALLOCSIZE,3*ALLOCSIZE,2*ALLOCSIZE};
  210.  
  211. #if DEBUG_STATISTICS
  212. static unsigned histnodes[MAXLEVEL+1];
  213. static unsigned nodetypes[NUMTYPES];
  214. #endif
  215.  
  216. #include "lrandom.c"
  217.  
  218. static void
  219. prerror(char *fmt, ...)
  220. {
  221.     VPRINTF(fmt, (char *)(((int *)(&fmt))+1));
  222.     exit(0);
  223. }
  224. static struct _catlocs *
  225. new_catloc(void)
  226. {
  227. struct _catlocs *p;
  228.     if((p=freecatlocs))
  229.     {
  230.         freecatlocs = p->fptr;
  231.         return p;
  232.     }
  233.     if(binsize < sizeof(struct _catlocs))
  234.     {
  235.         binbase = THEWELL(4096);
  236.         binsize = 4096;
  237.     }
  238.     binsize -= sizeof(struct _catlocs);
  239.     p = (void*)binbase;
  240.     binbase += sizeof(struct _catlocs);
  241.     return p;
  242. }
  243. static void
  244. free_catloc(struct _catlocs *p)
  245. {
  246.     p->fptr = freecatlocs;
  247.     freecatlocs = p;
  248. }
  249. static void *
  250. new_chunk(struct _bins *bp, int size, int type)
  251. {
  252. char *p;
  253.      if(bp->chunksize[type] < size)
  254.     {
  255.         if(bp->bincat == 0) {
  256.             bp->chunkbase[type] = THEWELL(chunksizes[type]);
  257.             bp->chunksize[type] = chunksizes[type];
  258.         }
  259.         else {
  260.         struct _catlocs *cl;
  261.             bp->chunkbase[type] = Cmalloc(0,chunksizes[type]-zbp.overhead);
  262.             bp->chunksize[type] = chunksizes[type]-zbp.overhead;
  263.             cl = new_catloc();
  264.             cl->addr = bp->chunkbase[type];
  265.             cl->fptr = bp->catlocs;
  266.             bp->catlocs = cl;
  267.         }
  268.     }
  269.     bp->chunksize[type] -= size;
  270.     p = bp->chunkbase[type];
  271.     bp->chunkbase[type] += size;
  272.     return p;
  273. }
  274. static void *
  275. new_node(struct _bins *bp, int levels, int type)
  276. {
  277. int size;
  278. NodeP p;
  279.  
  280. #if DEBUG_STATISTICS
  281.     nodetypes[type]++;
  282. #endif
  283.     if((p=bp->freenodes[type][levels]))
  284.     {
  285. #if DEBUG_STATISTICS
  286.         histnodes[levels]--;
  287. #endif
  288.         bp->freenodes[type][levels] = p->fptr[0];
  289.         return p;
  290.     }
  291.      size = sizeof(struct _node) + levels * sizeof(void*);
  292.     p = new_chunk(bp, size, type);
  293.     p->levels = levels;
  294.     return p;    
  295. }
  296. static void
  297. free_node(struct _bins *bp, NodeP p, int type)
  298. {
  299.     p->fptr[0] = bp->freenodes[type][p->levels];
  300.     bp->freenodes[type][p->levels] = p;
  301. #if DEBUG_STATISTICS
  302.     nodetypes[type]--;
  303.     histnodes[p->levels]++;
  304. #endif
  305. }
  306. static struct _addr *
  307. new_addr(struct _bins *bp)
  308. {
  309. struct _addr *p;
  310.     if((p=bp->freeaddrlocs))
  311.     {
  312.         bp->freeaddrlocs = p->fptr;
  313.         return p;
  314.     }
  315.     return new_chunk(bp, sizeof(struct _addr), FREE);
  316. }
  317. static void
  318. free_addr(struct _bins *bp, struct _addr *p)
  319. {
  320.     p->fptr = bp->freeaddrlocs;
  321.     bp->freeaddrlocs = p;
  322. }
  323. static struct _bins *
  324. new_bins(void)
  325. {
  326. struct _bins *p;
  327.     if((p=freebinlocs))
  328.     {
  329.         freebinlocs = p->fptr;
  330.         return p;
  331.     }
  332.      if(binsize < sizeof(struct _bins))
  333.     {
  334.         binbase = THEWELL(4096);
  335.         binsize = 4096;
  336.     }
  337.     binsize -= sizeof(struct _bins);
  338.     p = (struct _bins*)binbase;
  339.     binbase += sizeof(struct _bins);
  340.     return p;
  341. }
  342. static void
  343. free_bins(struct _bins *p)
  344. {
  345.     p->fptr = freebinlocs;
  346.     freebinlocs = p;
  347. }
  348. static int
  349. getlevel (struct _bins *p, int binlevel)
  350. {
  351. int level = -1;
  352. int bits = 0;
  353.  
  354.     while(bits == 0)
  355.     {
  356.         if (p->nbits == 0)
  357.         {
  358.             p->bits = lrandom();
  359.             p->nbits = 15;
  360.         }
  361.         bits = p->bits & 3;
  362.         p->bits >>= 2;
  363.         p->nbits--;
  364.  
  365.         if(++level > binlevel)
  366.             break;
  367.     }
  368.     return (level > MAXLEVEL) ? MAXLEVEL : level;
  369. }
  370.  
  371. static void
  372. init_bins(struct _bins *bp, unsigned category)
  373. {
  374. int i;
  375. int binnum = category % 1009;
  376.  
  377.     bzero(bp, sizeof(struct _bins));
  378.     bp->bincat = category;
  379.     bp->minloc = 0xffffffff;
  380.     bp->fptr = hmap[binnum];
  381.     hmap[binnum] = bp;
  382.     bp->SIZEheader = new_node(bp, MAXLEVEL+1, SIZE);
  383.     bp->FREEheader = new_node(bp, MAXLEVEL+1, FREE);
  384. #if USEDLIST
  385.     bp->USEDheader = new_node(bp, MAXLEVEL+1, USED);
  386. #else
  387.     bp->addrbump = 1;
  388.     bp->overhead = ALIGNMENT;
  389. #endif
  390.     for(i = 0; i <= MAXLEVEL; ++i)
  391.     {
  392.         bp->SIZEheader->fptr[i] = _NIL;
  393.         bp->FREEheader->fptr[i] = _NIL;
  394. #if USEDLIST
  395.         bp->USEDheader->fptr[i] = _NIL;
  396. #endif
  397.     }
  398. }
  399.  
  400. static struct _bins*
  401. getcat(unsigned category)
  402. {
  403. struct _bins *hbp;
  404.  
  405.     hbp = hmap[category % 1009];
  406.     while(hbp)
  407.     {
  408.         if(hbp->bincat == category)
  409.             return hbp;
  410.         hbp = hbp->fptr;
  411.     }
  412.     return 0;
  413. }
  414. static struct _bins *
  415. initcat(unsigned category)
  416. {
  417. struct _bins *bp;
  418.  
  419.     if(category == 0)
  420.     {
  421.         bp = &zbp;
  422.         if(zbp.SIZEheader == 0)
  423.             init_bins(bp, category);
  424.         return bp;
  425.     }
  426.     /* do this to set zbp.overhead properly on startup */
  427.     if(zbp.SIZEheader == 0)
  428.         initcat(0);
  429.  
  430.     if((bp = new_bins()))
  431.     {
  432.         init_bins(bp, category);
  433.         return bp;
  434.     }
  435.     return 0;
  436. }
  437. static void *
  438. do_sbrk(unsigned amount)
  439. {
  440. void *address;
  441.  
  442.     address = sbrk(amount);
  443.     if(address == (void*)-1)
  444.     {
  445.         PERROR("cmalloc: system out of memory\n");
  446.     }
  447.     return address;
  448. }
  449. static void *
  450. getspace(struct _bins *bp, unsigned size, unsigned *remainder)
  451. {
  452. unsigned desired;
  453. void *address;
  454.   
  455.     desired = ((size+ALLOCSIZE-1)/ALLOCSIZE)*ALLOCSIZE;
  456.     if(bp->bincat == 0)
  457.     {
  458.         address = THEWELL(desired);
  459.         *remainder = desired - size;
  460.     }
  461.     else
  462.     {
  463.     struct _catlocs *cl;
  464.  
  465.         if((desired-size) > zbp.overhead)
  466.             desired -= zbp.overhead;
  467.         
  468.         address = Cmalloc(0, desired);
  469.         *remainder = desired - size;
  470.  
  471.         /* save the gross allocations for the category */
  472.         cl = new_catloc();
  473.         cl->addr = address;
  474.         cl->fptr = bp->catlocs;
  475.         bp->catlocs = cl;
  476.     }
  477.     /* maintain address range info */
  478.     if((unsigned)address < bp->minloc)
  479.         bp->minloc = (unsigned)address;
  480.     if(((unsigned)address + desired) > bp->maxloc)
  481.         bp->maxloc = (unsigned)address + desired;
  482.      if(bp->minloc < minloc)
  483.          minloc = bp->minloc;
  484.      if(bp->maxloc > maxloc)
  485.          maxloc = bp->maxloc;
  486.     return address;
  487. }
  488. static void
  489. addto_sizelist(struct _bins *bp, AddrP ap)
  490. {
  491. SKIPVARS;
  492.  
  493.     /* INSERT IN SIZE LIST */
  494.     FINDKEY(SIZE, ap->size)
  495.  
  496.     if(node->key == ap->size)
  497.     {/* size node exists */
  498.         ap->fptr = (AddrP)node->value;
  499.         ap->bptr = (AddrP)&node->value;
  500.         if(ap->fptr) ap->fptr->bptr = ap;
  501.         node->value = (unsigned)ap;
  502.     }
  503.     else
  504.     {/* create new size node */
  505.         SETLEVEL(SIZE)
  506.         node = new_node(bp, level, SIZE);
  507.         node->key = ap->size;
  508.         node->value = (unsigned)ap;
  509.         ap->fptr = 0;
  510.         ap->bptr = (AddrP)&node->value;
  511.         INSERT()
  512.     }
  513. }
  514. static void
  515. addto_freelist(struct _bins *bp, void *addr, unsigned size)
  516. {
  517. SKIPVARS;
  518. AddrP ap,sp;
  519. unsigned dsize[2];
  520.  
  521.     /* GET NEW ADDR STRUCT */
  522.     ap = new_addr(bp);
  523.     ap->size = size;
  524.  
  525.     dsize[1] = dsize[0] = 0; /* sizenode deletion markers */
  526.  
  527.     /* CHECK FREE LIST */
  528.     FINDKEY(FREE, (unsigned)addr)
  529.  
  530.     /* CHECK FOR MERGE OR INSERT */
  531.     if(prev->value && prev->key+((AddrP)prev->value)->size == (unsigned)addr)
  532.     {/* merge with previous block */
  533.         ap->size += ((AddrP)prev->value)->size;
  534.  
  535.         if(prev->key + ap->size == node->key)
  536.         {/* merge with previous and next block */
  537.             sp = (AddrP) node->value;;
  538.             ap->size += sp->size;
  539.  
  540.             /* delete size struct for next block */
  541.             UNLINK(sp, 0)
  542.  
  543.             /* delete next block */
  544.             DELETENODE(FREE);
  545.         }
  546.         /* delete size struct for prev block */
  547.         sp = (AddrP)prev->value;
  548.         UNLINK(sp, 1)
  549.  
  550.         /* set new address struct */
  551.         prev->value = (unsigned)ap;
  552.         ap->maddr = prev;
  553.     }
  554.     else if(node->value && (char*)addr + size == (void*)node->key)
  555.     {/* merge with next block */
  556.         sp = (AddrP) node->value;;
  557.         node->key = (unsigned)addr;
  558.         ap->size += sp->size;
  559.  
  560.         /* unlink size struct for next block */
  561.         UNLINK(sp,0)
  562.  
  563.         /* set new address struct */
  564.         node->value = (unsigned)ap;
  565.         ap->maddr = node;
  566.     }
  567.     else
  568.     {/* insert in free list */
  569.  
  570.         SETLEVEL(FREE)
  571.         node = new_node(bp, level, FREE);
  572.         node->key = (unsigned)addr;
  573.         node->value = (unsigned)ap;
  574.         ap->maddr = node;
  575.         INSERT()
  576.     }
  577.     addto_sizelist(bp, ap);
  578.  
  579.     /* Remove sizenodes eliminated by merge */
  580.     if(dsize[0])
  581.     {
  582.         FINDKEY(SIZE, dsize[0])
  583.         if(node->value == 0)
  584.           DELETENODE(SIZE)
  585.     }
  586.     if(dsize[1])
  587.     {
  588.         FINDKEY(SIZE, dsize[1])
  589.         if(node->value == 0)
  590.           DELETENODE(SIZE)
  591.     }
  592. }
  593. static void* 
  594. Cmalloc(int category, unsigned size)
  595. {
  596. SKIPVARS;
  597. NodeP fnode;
  598. unsigned remainder;
  599. unsigned *address;
  600. struct _bins *bp;
  601.  
  602.     if(!(bp = getcat(category)))
  603.       if(!(bp = initcat(category)))
  604.           return 0;
  605.  
  606.     if(size == 0)
  607.         size = ALIGNMENT;
  608.     else
  609.         size += ROUNDING(size);
  610.     size += bp->guarded;
  611.  
  612. #if USEDLIST == 0
  613.     size += ALIGNMENT;
  614. #endif
  615.  
  616.     /* check sizelist for candidate */
  617.     FINDKEY(SIZE, size)
  618.     fnode = node;
  619. trynext:
  620.     if(node->key != 0xffffffff)
  621.     {/* found an appropriately sized block */
  622.     AddrP sp = (AddrP)node->value;
  623.  
  624.         if(!sp && node == fnode)
  625.         {
  626.         NodeP q;
  627.             q = node->fptr[0];
  628.             DELETENODE(SIZE)
  629.             node = q;
  630.             goto trynext;
  631.         }
  632.         if(!sp)
  633.         {/* no available space at this size */
  634.             node = node->fptr[0];
  635.             goto trynext;
  636.         }
  637.  
  638.         /* extract some space from this block */
  639.         remainder = node->key - size;
  640.         address = (void*)sp->maddr->key;
  641.         sp->maddr->key += size;
  642.         DETACH(sp);
  643.  
  644.         if(node->value == 0)
  645.         {/* no more blocks of this size, delete sizenode */
  646.             if(node != fnode)
  647.               FINDKEY(SIZE, size)
  648.             DELETENODE(SIZE)
  649.         }
  650.  
  651.         if(remainder == 0)
  652.         {/* no remaining space,the node in freelist is exhausted, delete it */
  653.             FINDKEY(FREE, sp->maddr->key)
  654.             DELETENODE(FREE)
  655.             free_addr(bp, sp);
  656.         }
  657.         else
  658.         {/* space remains in block, move it to new size loc */
  659.             sp->size = remainder;
  660.             addto_sizelist(bp, sp);
  661.         }
  662.     }
  663.     else
  664.     {
  665.         address = getspace(bp, size, &remainder);
  666.         if(remainder)
  667.           addto_freelist(bp, ((char*)address)+size, remainder);
  668.     }
  669.     if(bp->guarded)
  670.     {
  671.       *address = (unsigned)GUARDWORD;
  672.       *((unsigned*)(((char*)address)+size-ALIGNMENT)) = ~((unsigned)GUARDWORD);
  673. #if USEDLIST == 0
  674.       ++address;
  675. #endif
  676.     }
  677. #if USEDLIST
  678.     FINDKEY(USED, (unsigned)address)
  679.     if(node->key == (unsigned)address) {
  680.       PERROR("Cmalloc: bookkeeping nodes are corrupted at:0x%x\n", address);
  681.     }
  682.     SETLEVEL(USED)
  683.     node = new_node(bp, level, USED);
  684.     node->key = (unsigned)address;
  685.     node->value = size;
  686.     INSERT()    
  687. #else
  688.     *address = size | (ALIGNMENT-1);
  689. #endif
  690.     return address+bp->addrbump;
  691. }
  692. static void*
  693. Ccalloc(int category, unsigned cnt, unsigned elem_size)
  694. {
  695. unsigned size = cnt * elem_size;
  696. void* buf;;
  697.  
  698.   if((buf = Cmalloc(category, size)))
  699.       bzero(buf, size);
  700.   return buf;
  701. };
  702. static void
  703. Cfree(int category, void* addr)
  704. {
  705. unsigned cursize;
  706. unsigned *address;
  707. struct _bins *bp;
  708.  
  709. #if USEDLIST
  710. SKIPVARS;
  711. #endif
  712.  
  713.     if(addr)
  714.     {
  715.         if(!(bp = getcat(category)))
  716.             PERROR("Cfree: non-existant category:%d at:0x%x\n",category,addr);
  717.  
  718. #if USEDLIST
  719.         address = (void*)(((char*)addr)-(bp->guarded/2));
  720.         FINDKEY(USED, (unsigned)address)
  721.         if(node->key != (unsigned)address)
  722.           PERROR("Cfree: bogus address=0x%x\n", addr);
  723.  
  724.         cursize = node->value;
  725.         CHECKGUARDS(Cfree)
  726.         DELETENODE(USED)
  727. #else
  728.         address = (void*)(((char*)addr)-ALIGNMENT);
  729.         if((unsigned)address & (ALIGNMENT-1))
  730.           PERROR("Cfree: bogus address=0x%x\n", addr);
  731.  
  732.         cursize = *address;
  733.         if((cursize & (ALIGNMENT-1)) != (ALIGNMENT-1))
  734.           PERROR("Cfree: heap(%d) corrupted at 0x%x\n", bp->bincat, addr);
  735.  
  736.         cursize &= ~(ALIGNMENT-1);
  737.         *address = cursize;
  738.         CHECKGUARDS(Cfree)
  739. #endif
  740.         addto_freelist(bp, address, cursize);
  741.     }
  742.     else PERROR("Cfree: null pointer in category %d\n", category);
  743. }
  744. static void* 
  745. Crealloc(int category, void* addr, unsigned newsize)
  746. {
  747. SKIPVARS;
  748. unsigned cursize;
  749. unsigned *address;
  750. unsigned *sizptr;
  751. struct _bins *bp;
  752.  
  753. #if USEDLIST
  754. NodeP onode;
  755. #endif
  756.  
  757.     if(addr == 0) 
  758.         return Cmalloc(category, newsize);
  759.     else
  760.     {
  761.         if(!(bp = getcat(category)))
  762.            PERROR("Crealloc: non-existant category:%d at:%x\n",category,addr);
  763.  
  764.         if(newsize == 0)
  765.             newsize = ALIGNMENT;
  766.         else
  767.             newsize += ROUNDING(newsize);
  768.         newsize += bp->guarded;
  769.  
  770. #if USEDLIST
  771.         address = (void*)(((char*)addr)-(bp->guarded/2));
  772.         FINDKEY(USED, (unsigned)address)
  773.         if(node->key != (unsigned)address)
  774.           PERROR("Crealloc: bogus address=0x%x\n", addr);
  775.  
  776.         cursize = node->value;
  777.         node->value = newsize;
  778.         onode = node;
  779. #else
  780.         newsize += ALIGNMENT;
  781.         if((unsigned)addr & (ALIGNMENT-1))
  782.           PERROR("Crealloc: bogus address=0x%x\n", addr);
  783.  
  784.         address = (void*)(((char*)addr)-ALIGNMENT);
  785.         cursize = *address;
  786.         if((cursize & (ALIGNMENT-1)) != (ALIGNMENT-1))
  787.           PERROR("Crealloc: heap(%d) corrupted at 0x%x\n",
  788.               bp->bincat, addr);
  789.  
  790.         cursize &= ~(ALIGNMENT-1);
  791.         sizptr = address;
  792. #endif
  793.         CHECKGUARDS(Crealloc)
  794.  
  795.         if(newsize == cursize)
  796.             return addr;
  797.         if(newsize > cursize)
  798.         {/* check if block can be extended */
  799.         void *taddr = ((char*)address) + cursize;
  800.         unsigned extendsize = newsize-cursize;
  801.  
  802.             /* check freelist for an available block at the right address */
  803.             FINDKEY(FREE, (unsigned)taddr)
  804.             if(node->key == (unsigned)taddr)
  805.             {
  806.             AddrP sp = (AddrP)node->value;
  807.                 if(sp->size >= extendsize)
  808.                 {/* BLOCK CAN BE EXTENDED INTERNALLY */
  809.                     node->key += extendsize;
  810.                     sp->size -= extendsize;
  811.                     DETACH(sp)
  812.                     if(sp->size == 0)
  813.                     {/* the extension block is used up, delete this node */
  814.                         free_addr(bp, sp);
  815.                         DELETENODE(FREE)
  816.                     }
  817.                     else
  818.                     {/* shift the remainder in the sizelist */
  819.                         addto_sizelist(bp, sp);
  820.                     }
  821.                     /* SUCCESS */
  822.                     if(bp->guarded)
  823.                     {
  824.                         *((unsigned*)(((char*)address)+newsize-ALIGNMENT))
  825.                             = ~((unsigned)GUARDWORD);
  826.                     }
  827. #if USEDLIST == 0
  828.                     *sizptr = newsize | (ALIGNMENT-1);
  829. #endif
  830.                     return addr;
  831.                 }
  832.             }
  833.             /* HERE WE COULD CHECK OTHER SOURCES OF SPACE */
  834.  
  835.             /* can't extend block, malloc some new space */
  836.             if((taddr = Cmalloc(category,newsize-bp->overhead)))
  837.             {
  838.                 memmove(taddr,addr,cursize-bp->overhead);
  839. #if USEDLIST
  840.                 onode->value = cursize;
  841. #endif
  842.                 Cfree(category, addr);
  843.             }
  844.             /* SUCCESS */
  845.             return taddr;
  846.         }
  847.         else
  848.         {/* shrink block */
  849.             if(bp->guarded)
  850.             {
  851.                 *((unsigned*)(((char*)address)+newsize-ALIGNMENT))
  852.                     = ~((unsigned)GUARDWORD);
  853.             }
  854.             addto_freelist(bp, ((char*)address)+newsize, cursize-newsize); 
  855.  
  856. #if USEDLIST == 0
  857.             *sizptr = newsize | (ALIGNMENT-1);
  858. #endif
  859.             return addr;
  860.         }
  861.       }
  862. }
  863. static void
  864. Cfreecat(int category)
  865. {
  866. struct _bins *bp;
  867.  
  868.     if(category == 0)
  869.         return;
  870.  
  871.     if((bp = getcat(category)))
  872.     {
  873.     struct _catlocs *cl = bp->catlocs;
  874.     struct _bins *hbp;
  875.     struct _bins *prev;
  876.  
  877.         while(cl)
  878.         {/* Space allocated to the category is moved to category 0 */
  879.         void *ql = cl->fptr;
  880.  
  881.             Cfree(0, cl->addr);
  882.             free_catloc(cl);
  883.             cl = ql;
  884.         }
  885.         /* space for the _bins struct is placed on a free list */
  886.         hbp = hmap[category % 1009];
  887.         prev = 0;
  888.         while(hbp)
  889.         {
  890.             if(hbp->bincat == category)
  891.             {
  892.                 if(prev == 0)
  893.                     hmap[category % 1009] = hbp->fptr;
  894.                 else
  895.                     prev->fptr = hbp->fptr;
  896.                 free_bins(hbp);
  897.                 return;
  898.             }
  899.             prev = hbp;
  900.             hbp = hbp->fptr;
  901.         }
  902.     }
  903. }
  904. static int
  905. Cmemrange(int category, unsigned *min, unsigned *max)
  906. {
  907. struct _bins *bp;
  908.  
  909.     if((bp = getcat(category)))
  910.     {
  911.         *min = bp->minloc;
  912.         *max = bp->maxloc;
  913.         return 1;
  914.     }
  915.     return 0;
  916. }
  917. static int
  918. Cusedrange(int category, unsigned *min, unsigned *max)
  919. {
  920. #if USEDLIST
  921. struct _bins *bp;
  922. NodeP node;
  923. int level;
  924.  
  925.     if((bp = getcat(category)))
  926.     {
  927.         node = bp->USEDheader;
  928.         *min = node->fptr[0]->key;
  929.         for(level = bp->USEDlevel; level >= 0; level--)
  930.           while(node->fptr[level]->key < 0xffffffff)
  931.             node = node->fptr[level];
  932.         *max = node->key;
  933.         return 1;
  934.     }
  935. #endif
  936.     return 0;
  937. }
  938. static void
  939. Ctotrange(unsigned *min, unsigned *max)
  940. {
  941.     *min = minloc;
  942.     *max = maxloc;
  943. }
  944. static int
  945. Cnewcat(void)
  946. {
  947. static int cat;
  948.     return ++cat;
  949. }
  950. static void
  951. Cguard(int category)
  952. {
  953. struct _bins *bp;
  954.  
  955.     if(!(bp = getcat(category)))
  956.       if(!(bp = initcat(category)))
  957.           return;
  958.  
  959.     if(!bp->guarded)
  960.     {
  961.         bp->guarded = 2*ALIGNMENT;
  962.         bp->addrbump = 1;
  963.         bp->overhead += 2*ALIGNMENT;
  964.     }
  965. }
  966. static void*
  967. Ccatcheck(int category, void *start)
  968. {
  969. #if USEDLIST
  970. struct _bins *bp;
  971. NodeP node,prev;
  972. unsigned *p1,*p2;
  973.     if((bp = getcat(category)))
  974.     {
  975.         if(bp->guarded)
  976.         {
  977.             prev = 0;
  978.             node = bp->USEDheader;
  979.             while((node = node->fptr[0]) != (NodeP)0xffffffff)
  980.             {
  981.                 if((void*)node->key > start)
  982.                 {
  983.                     p1 = (unsigned*)node->key;
  984.                     p2 = (void*)((char*)p1+node->value+ALIGNMENT);
  985.                     if(*p1 != (unsigned)GUARDWORD)
  986.                     {
  987.                         if(prev)
  988.                             return (char*)prev->key+ALIGNMENT;
  989.                         else
  990.                             return (void*)1;
  991.                     }
  992.                     if(*p2 != ~((unsigned)GUARDWORD))
  993.                         return (char*)node->key+ALIGNMENT;
  994.                 }
  995.                 prev = node;
  996.             }
  997.         }
  998.     }
  999. #endif
  1000.     return 0;
  1001. }
  1002. #if DEBUG
  1003. long clock();
  1004. long start, end, diff;
  1005. void *malloc();
  1006. void *realloc();
  1007. void free();
  1008. #define CLOCKS_PER_SECOND 1000000L
  1009. #define ITERATIONS 0x10000
  1010. #define MAXALLOC 0x1ff
  1011.  
  1012. #define PRINT_TIME(string)\
  1013. diff = end - start;\
  1014. diff /= CLOCKS_PER_SECOND/10;\
  1015. if(diff == 0) diff = 1;\
  1016. printf(string " = %ld\n", (i*10) / diff);print_freenodes(1);
  1017.  
  1018. static void
  1019. print_freenodes(int category)
  1020. {
  1021. int i;
  1022. NodeP node;
  1023. AddrP ap;
  1024. struct _bins *bp = getcat(category);
  1025.  
  1026. #if DEBUG_STATISTICS
  1027.     printf("SIZENODES=%d\n", nodetypes[0]);
  1028.     node = bp->SIZEheader;
  1029.     while((node = node->fptr[0]))
  1030.     {
  1031.         printf("Size:%d\n", node->key);
  1032.         ap = (void*)node->value;
  1033.         while(ap)
  1034.         {
  1035.             printf("    %x    size=%d\n", ap->maddr->key, ap->size);
  1036.             ap = ap->fptr;
  1037.         }
  1038.     }
  1039.     printf("FREENODES=%d\n", nodetypes[1]);
  1040.     node = bp->FREEheader;
  1041.     while((node = node->fptr[0]))
  1042.     {
  1043.     int size;
  1044.         if((ap = (void*)node->value))
  1045.             size = ap->size;
  1046.         else size=-1;
  1047.  
  1048.         printf("Addr:%x    size=%d=0x%x End:%x\n",
  1049.             node->key, size, size, node->key+size);
  1050.     }
  1051. #if DEBUG_USEDNODES
  1052.     printf("USEDNODES=%d\n", nodetypes[2]);
  1053.     node = bp->USEDheader;
  1054.     while((node = node->fptr[0]))
  1055.     {
  1056.         printf("Addr:0x%x    Size:%d\n", node->key, node->value);
  1057.     }
  1058. #endif
  1059. #if DEBUG_SPARES
  1060.     printf("SPARES\n");
  1061.     for(i = 0; i <= MAXLEVEL; ++i)
  1062.         printf("%d    %d\n", i, histnodes[i]);
  1063. #endif
  1064. #endif
  1065. }
  1066. int
  1067. main(int argc, char **argv)
  1068. {
  1069. int i;
  1070. void *buf;
  1071. void *addrs[ITERATIONS];
  1072. unsigned random[ITERATIONS];
  1073. int cm = 0;
  1074.  
  1075.   if(argc > 1)
  1076.     cm =1;
  1077.  
  1078.   for(i = 0; i < ITERATIONS; ++i)
  1079.   {
  1080.     random[i] = lrandom();
  1081.     addrs[i] = 0;
  1082.   }
  1083.   if(cm)
  1084.   {
  1085.  
  1086.     start = clock();
  1087.     for(i = 0; i < ITERATIONS; ++i)
  1088.         addrs[i] = Cmalloc(1,random[i] & MAXALLOC);
  1089.     end = clock();
  1090.     PRINT_TIME("CMALLOC PER SEC")
  1091.  
  1092.     start = clock();
  1093.     /* Free the addresses in random order */
  1094.     for(i = 0; i < ITERATIONS; ++i)
  1095.     {
  1096.     int j = random[i] & (ITERATIONS-1);
  1097.         if(addrs[j])
  1098.         {
  1099.             Cfree(1,addrs[j]);
  1100.             addrs[j] = 0;
  1101.         }
  1102.     }
  1103.     /* Clean up any missed elements */
  1104.     for(i = 0; i < ITERATIONS; ++i)
  1105.     {
  1106.         if(addrs[i])
  1107.             Cfree(1,addrs[i]);
  1108.     }
  1109.     end = clock();
  1110.     PRINT_TIME("CFREE PER SEC")
  1111.  
  1112.     start = clock();
  1113.     for(i = 0; i < ITERATIONS; ++i)
  1114.     {
  1115.     int j = random[i] & (ITERATIONS-1);
  1116.         addrs[i] = Cmalloc(1,j & MAXALLOC);
  1117.         if(j < i && addrs[j])
  1118.         {
  1119.             Cfree(1,addrs[j]);
  1120.             addrs[j] = 0;
  1121.         }
  1122.     }
  1123.     end = clock();
  1124.     PRINT_TIME("C_COMBO PER SEC");
  1125.  
  1126.     /* Cleanup */
  1127.     for(i = 0; i < ITERATIONS; ++i)
  1128.         if(addrs[i]) Cfree(1,addrs[i]);
  1129.  
  1130.     start = clock();
  1131.     for(i = 0; i < ITERATIONS/2; ++i)
  1132.     {
  1133.     int j = random[i] & ((ITERATIONS/2)-1);
  1134.  
  1135.         addrs[i] = Cmalloc(1,random[i] & MAXALLOC);
  1136.         *((unsigned*)addrs[i]) = random[i];
  1137.  
  1138.         if(j < i && addrs[j])
  1139.         {
  1140.             if(*((unsigned*)addrs[j]) != random[j])
  1141.               printf("Cmalloc: fail i=%d j=%d addr=0x%x des=%x got=%x size=%d\n",
  1142.                 i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
  1143.                 random[j] & MAXALLOC);
  1144.  
  1145.             addrs[j] = Crealloc(1,addrs[j], random[i] & MAXALLOC);
  1146.             if(*((unsigned*)addrs[j]) != random[j])
  1147.               printf("Crealloc: fail i=%d j=%d addr=0x%x des=%x got=%x nsize=%d\n",
  1148.                 i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
  1149.                 random[i] & MAXALLOC);
  1150.         }
  1151.     }
  1152.     end = clock();
  1153.     PRINT_TIME("C_REALLOC PER SEC")
  1154.  
  1155.     Cfreecat(1);
  1156.   } else {
  1157.  
  1158.     start = clock();
  1159.     for(i = 0; i < ITERATIONS; ++i)
  1160.         addrs[i] = malloc(random[i] & MAXALLOC);
  1161.     end = clock();
  1162.     PRINT_TIME("MALLOC PER SEC")
  1163.  
  1164.     start = clock();
  1165.     for(i = 0; i < ITERATIONS; ++i)
  1166.     {
  1167.     int j = random[i] & (ITERATIONS-1);
  1168.         if(addrs[j])
  1169.         {
  1170.             free(addrs[j]);
  1171.             addrs[j] = 0;
  1172.         }
  1173.     }
  1174.     /* Clean up any missed elements */
  1175.     for(i = 0; i < ITERATIONS; ++i)
  1176.     {
  1177.         if(addrs[i])
  1178.             free(addrs[i]);
  1179.     }
  1180.     end = clock();
  1181.     PRINT_TIME("FREE PER SEC")
  1182.  
  1183.     start = clock();
  1184.     for(i = 0; i < ITERATIONS; ++i)
  1185.     {
  1186.     int j = random[i] & (ITERATIONS-1);
  1187.         addrs[i] = malloc(j & MAXALLOC);
  1188.         if(j < i && addrs[j])
  1189.         {
  1190.             free(addrs[j]);
  1191.             addrs[j] = 0;
  1192.         }
  1193.     }
  1194.     end = clock();
  1195.     PRINT_TIME("COMBO PER SEC");
  1196.  
  1197.     /* Cleanup */
  1198.     for(i = 0; i < ITERATIONS; ++i)
  1199.         if(addrs[i]) free(addrs[i]);
  1200.  
  1201.     start = clock();
  1202.     for(i = 0; i < ITERATIONS/2; ++i)
  1203.     {
  1204.     int j = random[i] & ((ITERATIONS/2)-1);
  1205.  
  1206.         addrs[i] = malloc((random[i] & MAXALLOC)+4);
  1207.         *((unsigned*)addrs[i]) = random[i];
  1208.  
  1209.         if(j < i && addrs[j])
  1210.         {
  1211.             if(*((unsigned*)addrs[j]) != random[j])
  1212.               printf("malloc: fail i=%d j=%d addr=0x%x des=%x got=%x size=%d\n",
  1213.                 i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
  1214.                 (random[j] & MAXALLOC)+4);
  1215.  
  1216.             addrs[j] = realloc(addrs[j], (random[i] & MAXALLOC)+4);
  1217.             if(*((unsigned*)addrs[j]) != random[j])
  1218.               printf("realloc: fail i=%d j=%d addr=0x%x des=%x got=%x size=%d\n",
  1219.                 i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
  1220.                 (random[i] & MAXALLOC)+4);
  1221.         }
  1222.     }
  1223.     end = clock();
  1224.     PRINT_TIME("REALLOC PER SEC")
  1225.   }
  1226. }
  1227. #endif /* DEBUG */
  1228.