Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1.  
  2. #include "mf.h"
  3. void * memcpy(void * dst, void * src, size_t count);
  4.  
  5. static struct m_state ms;
  6.  
  7. void init_malloc(void* p)
  8. { mchunkptr chp;
  9.   int i;
  10.   dword psize= 0x10000;
  11.  
  12.   psize-= 40;
  13.   ms.top = (mchunkptr)p;
  14.   ms.topsize = psize;
  15.      
  16.   chp = (mchunkptr)p;
  17.   chp->head=psize|1;
  18.    
  19.   for(i=0; i<32; i++)
  20.   {
  21.     mchunkptr p = &ms.smallbins[i];
  22.     p->fd = p;
  23.     p->bk = p;
  24.    
  25.   };  
  26. }
  27.  
  28. void *malloc(size_t size)
  29. { size_t nb, psize,rsize;
  30.   dword idx;
  31.   dword smallbits;
  32.   mchunkptr B,F,p,r;
  33.   void *mem;
  34.  
  35.   nb = ((size+7)&~7)+8;  
  36.  
  37.   if (nb < 256)
  38.   {
  39. //    idx = nb  >> 3;
  40. //    smallbits= (-1<<idx) & ms.smallmap;
  41.     _asm
  42.     {
  43.       mov ecx, [nb]
  44.       or eax, -1
  45.       shl eax, cl
  46.       and eax, [ms.smallmap]
  47.       mov [smallbits], eax    
  48.     }
  49.     if (smallbits)
  50.     {
  51.       _asm
  52.       { bsf eax, [smallbits]
  53.         mov [idx], eax  
  54.       };
  55.    
  56.       psize= idx<<3;
  57.       rsize= psize-nb;
  58.  
  59.       B = &ms.smallbins[idx];
  60.       p = B->fd;
  61.       F = p->fd;
  62.       if (B == F)
  63.       {
  64. //        ms.smallmap &=  ~(1<< idx);
  65.         _asm
  66.         {
  67.           mov eax, [idx]
  68.           btr [ms.smallmap], eax
  69.         }
  70.       }  
  71.       B->fd = F;
  72.       F->bk = B;
  73.  
  74.       if(rsize<16)
  75.       {
  76.         p->head = psize|PINUSE_BIT|CINUSE_BIT;
  77.         ((mchunkptr)((char*)p + psize))->head |= PINUSE_BIT;
  78.         return chunk2mem(p);
  79.       };
  80.       p->head = nb|PINUSE_BIT|CINUSE_BIT;
  81.       r = chunk_plus_offset(p, nb);
  82.       r->head = rsize|PINUSE_BIT;
  83.       ((mchunkptr)((char*)r + rsize))->prev_foot = rsize;
  84.       {
  85.         dword I;
  86.         mchunkptr B;
  87.         mchunkptr F;  
  88.  
  89.         I  = rsize>>3;
  90.         ms.smallmap |=  1<< I;
  91.         B = &ms.smallbins[I];
  92.         F = B->fd;
  93.         B->fd = r;
  94.         F->bk = r;
  95.         r->fd = F;
  96.         r->bk = B;
  97.        }
  98.       return chunk2mem(p);
  99.     }
  100.     if (ms.treemap != 0 && (mem = malloc_small(nb)) != 0)
  101.       return mem;  
  102.   }
  103.   else
  104.   {
  105.     if (ms.treemap != 0 && (mem = malloc_large(nb)) != 0)
  106.       return mem;  
  107.   };  
  108.  
  109.   if (nb < ms.topsize)
  110.   {
  111.     size_t rsize = ms.topsize -= nb;
  112.     mchunkptr p = ms.top;
  113.     mchunkptr r = ms.top = chunk_plus_offset(p, nb);
  114.     r->head = rsize | PINUSE_BIT;
  115.     p->head = nb |PINUSE_BIT|CINUSE_BIT;
  116.     return chunk2mem(p);
  117.   };
  118.  
  119.   return 0;
  120. };
  121.  
  122. void free(void *mem)
  123. { size_t psize;
  124.   size_t prevsize;
  125.   size_t nsize;
  126.   mchunkptr next;
  127.   mchunkptr prev;
  128.  
  129.   mchunkptr p  = mem2chunk(mem);
  130.   if(p->head & CINUSE_BIT)
  131.   {
  132.     psize = p->head & (~3);
  133.     next = chunk_plus_offset(p, psize);
  134.  
  135.     if(!(p->head & PINUSE_BIT))
  136.     {
  137.       prevsize = p->prev_foot;
  138.       prev=(mchunkptr)(((char*)p) - prevsize);
  139.       psize += prevsize;
  140.       p = prev;
  141.       if (prevsize < 256)
  142.       {  
  143.         dword I;
  144.         mchunkptr F = p->fd;
  145.         mchunkptr B = p->bk;
  146.         I = prevsize>>3;
  147.         if (F == B)
  148.         {
  149.           ms.smallmap &=  ~(1<< I);
  150.         }
  151.         F->bk = B;
  152.         B->fd = F;
  153.       }  
  154.       else
  155.         unlink_large_chunk((tchunkptr)p);
  156.     };
  157.            
  158.     if(next->head & PINUSE_BIT)
  159.     {
  160.       if (! (next->head & CINUSE_BIT))
  161.       {  
  162.         if (next == ms.top)
  163.         {  size_t tsize = ms.topsize += psize;
  164.            ms.top = p;
  165.            p->head = tsize | PINUSE_BIT;
  166.            return;
  167.          }
  168.            
  169.          nsize = next->head & ~INUSE_BITS;
  170.          psize += nsize;
  171.  
  172.          if (nsize < 256)
  173.          {
  174.            dword I;
  175.            mchunkptr F = next->fd;
  176.            mchunkptr B = next->bk;
  177.            I = nsize>>3;
  178.            if (F == B)
  179.              ms.smallmap &=  ~(1<< I);
  180.            F->bk = B;
  181.            B->fd = F;
  182.          }
  183.          else
  184.            unlink_large_chunk((tchunkptr)next);
  185.          
  186.          p->head = psize|PINUSE_BIT;
  187.          ((mchunkptr)((char*)p+psize))->prev_foot = psize;
  188.       }
  189.       else
  190.       {
  191.         next->head &= ~PINUSE_BIT;
  192.         p->head = psize|PINUSE_BIT;
  193.         ((mchunkptr)((char*)p+psize))->prev_foot = psize;
  194.       };
  195.       insert_chunk(p,psize);
  196.     };
  197.   };
  198. }
  199.  
  200. static void insert_chunk(mchunkptr P, size_t S)
  201. {
  202.   dword I;
  203.   mchunkptr B;
  204.   mchunkptr F;  
  205.   if (S < 256)
  206.   {
  207.     I  = S>>3;
  208.     B = &ms.smallbins[I];
  209.     F = B->fd;
  210.     ms.smallmap |=  1<< I;
  211.    
  212.     B->fd = P;
  213.     F->bk = P;
  214.     P->fd = F;
  215.     P->bk = B;
  216.   }
  217.   else
  218.     insert_large_chunk((tchunkptr)P, S);
  219. };  
  220.  
  221. /********
  222. static void insert_small_chunk(mchunkptr p, size_t s)
  223. {
  224.   DWORD I  = s>>3;
  225.    
  226.   mchunkptr B = &ms.smallbins[I];
  227.   mchunkptr F = B->fd;
  228.   if (!(ms.smallmap & 1<<I))
  229.     ms.smallmap |=  1<< I;
  230.  
  231.   B->fd = p;
  232.   F->bk = p;
  233.   p->fd = F;
  234.   p->bk = B;
  235. }
  236. *********/
  237.  
  238. static dword compute_tree_index(size_t s)
  239. {  dword idx;
  240.  
  241.     _asm
  242.     {   mov edx, [s]
  243.         shr edx, 8  
  244.         bsr eax, edx
  245.         lea ecx, [eax+7]
  246.         mov edx, [s]
  247.         shr edx, cl
  248.         and edx, 1
  249.         lea eax, [edx+eax*2]
  250.         mov [idx], eax
  251.     };
  252.  
  253.     return idx;
  254. };
  255.  
  256. static void insert_large_chunk(tchunkptr X, size_t S)
  257. {
  258.   tbinptr* H;
  259.   dword I;
  260.   I = compute_tree_index(S);
  261.   H = &ms.treebins[I];
  262.   X->index = I;
  263.   X->child[0] = X->child[1] = 0;
  264.   if (!(ms.treemap & 1<<I))
  265.   {
  266.     ms.treemap |= 1<<I;
  267.     *H = X;
  268.     X->parent = (tchunkptr)H;
  269.     X->fd = X->bk = X;
  270.   }
  271.   else
  272.   {
  273.     tchunkptr T = *H;
  274.     size_t K = S << leftshift_for_tree_index(I);
  275.     for (;;)
  276.     {
  277.       if ((T->head & ~INUSE_BITS) != S)
  278.       {
  279.         tchunkptr* C = &(T->child[(K >> 31) & 1]);
  280.         K <<= 1;
  281.         if (*C != 0)
  282.           T = *C;
  283.         else
  284.         {
  285.           *C = X;
  286.           X->parent = T;
  287.           X->fd = X->bk = X;
  288.           break;
  289.         }
  290.       }
  291.       else
  292.       {
  293.         tchunkptr F = T->fd;
  294.         T->fd = F->bk = X;
  295.         X->fd = F;
  296.         X->bk = T;
  297.         X->parent = 0;
  298.         break;
  299.       };
  300.     };
  301.   };
  302. };
  303.  
  304. static void* malloc_small(size_t nb)
  305. {
  306.   tchunkptr t, v;
  307.   mchunkptr r;
  308.   size_t rsize;
  309.   dword i;
  310.  
  311.   _asm
  312.   { bsf ecx,[ms.treemap]
  313.     mov [i], ecx
  314.   }  
  315.   v = t =  ms.treebins[i];
  316.   rsize = (t->head & ~INUSE_BITS) - nb;
  317.  
  318.   while ((t = leftmost_child(t)) != 0)
  319.   {
  320.     size_t trem = (t->head & ~INUSE_BITS) - nb;
  321.     if (trem < rsize)
  322.     { rsize = trem;
  323.       v = t;
  324.     }
  325.   }
  326.  
  327.   r = chunk_plus_offset((mchunkptr)v, nb);
  328.   unlink_large_chunk(v);
  329.   if (rsize < 16)
  330.   {
  331.     v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
  332.     ((mchunkptr)((char*)v+rsize + nb))->head |= PINUSE_BIT;
  333.   }
  334.   else
  335.   {
  336.     v->head = nb|PINUSE_BIT|CINUSE_BIT;
  337.     r->head = rsize|PINUSE_BIT;
  338.     ((mchunkptr)((char*)r+rsize))->prev_foot = rsize;
  339.     insert_chunk(r, rsize);
  340. //    replace_dv(r, rsize);
  341.   }
  342.   return chunk2mem(v);
  343. }
  344.  
  345. /********
  346. static void replace_dv(mchunkptr P, size_t S)
  347. {
  348.   size_t DVS = ms.dvsize;
  349.   if (DVS != 0)
  350.   {
  351.     mchunkptr DV = ms.dv;
  352.     insert_small_chunk(DV, DVS);
  353.   }
  354.   ms.dvsize = S;
  355.   ms.dv = P;
  356. }
  357. ***********/
  358.  
  359. void static unlink_large_chunk(tchunkptr X)
  360. {
  361.   tchunkptr XP = X->parent;
  362.   tchunkptr R;
  363.   if (X->bk != X)
  364.   {
  365.     tchunkptr F = X->fd;
  366.     R = X->bk;
  367.     F->bk = R;
  368.     R->fd = F;
  369.   }
  370.   else
  371.   {
  372.     tchunkptr* RP;
  373.     if (((R = *(RP = &(X->child[1]))) != 0) ||
  374.         ((R = *(RP = &(X->child[0]))) != 0))
  375.     {
  376.       tchunkptr* CP;
  377.       while ((*(CP = &(R->child[1])) != 0) ||
  378.              (*(CP = &(R->child[0])) != 0))
  379.       {
  380.         R = *(RP = CP);
  381.       }
  382.       *RP = 0;
  383.     }
  384.   }
  385.   if (XP != 0)
  386.   {
  387.     tbinptr* H = &ms.treebins[X->index];
  388.     if (X == *H)
  389.     {
  390.       if ((*H = R) == 0)
  391.         ms.treemap &= ~(1<<X->index);
  392.     }
  393.     else
  394.     {
  395.       if (XP->child[0] == X)
  396.         XP->child[0] = R;
  397.       else
  398.         XP->child[1] = R;
  399.     };    
  400.     if (R != 0)
  401.     {
  402.       tchunkptr C0, C1;
  403.       R->parent = XP;
  404.       if ((C0 = X->child[0]) != 0)
  405.       {
  406.           R->child[0] = C0;
  407.           C0->parent = R;
  408.       }
  409.       if ((C1 = X->child[1]) != 0)
  410.       {
  411.         R->child[1] = C1;
  412.         C1->parent = R;
  413.       }
  414.     }
  415.   }
  416. }
  417.  
  418. static void* malloc_large(size_t nb)
  419. {
  420.   tchunkptr v = 0;
  421.   size_t rsize = -nb; /* Unsigned negation */
  422.   tchunkptr t;
  423.   dword idx;
  424.   idx = compute_tree_index(nb);
  425.  
  426.   if ((t = ms.treebins[idx]) != 0)
  427.   {
  428.     /* Traverse tree for this bin looking for node with size == nb */
  429.     size_t sizebits = nb << leftshift_for_tree_index(idx);
  430.     tchunkptr rst = 0;  /* The deepest untaken right subtree */
  431.     for (;;)
  432.     {
  433.       tchunkptr rt;
  434.       size_t trem = (t->head & ~INUSE_BITS) - nb;
  435.  
  436.       if (trem < rsize)
  437.       {
  438.         v = t;
  439.         if ((rsize = trem) == 0)
  440.           break;
  441.       }
  442.       rt = t->child[1];
  443.       t = t->child[(sizebits >> 31) & 1];
  444.       if (rt != 0 && rt != t)
  445.         rst = rt;
  446.       if (t == 0)
  447.       {
  448.         t = rst; /* set t to least subtree holding sizes > nb */
  449.         break;
  450.       }
  451.       sizebits <<= 1;
  452.     }
  453.   }
  454.  
  455.   if (t == 0 && v == 0)
  456.   { /* set t to root of next non-empty treebin */
  457.     dword leftbits = (-1<<idx) & ms.treemap;
  458.     if (leftbits != 0)
  459.     { dword i;
  460.       _asm
  461.       { bsf eax, [leftbits]
  462.         mov [i], eax
  463.       }
  464.       t = ms.treebins[i];
  465.     }
  466.   }
  467.  
  468.   while (t != 0)
  469.   { /* find smallest of tree or subtree */
  470.     size_t trem = (t->head & ~INUSE_BITS) - nb;
  471.     if (trem < rsize)
  472.     {
  473.       rsize = trem;
  474.       v = t;
  475.     }
  476.     t = leftmost_child(t);
  477.   }
  478.  
  479.   /*  If dv is a better fit, return 0 so malloc will use it */
  480.   if (v != 0)
  481.   {
  482.     mchunkptr r = chunk_plus_offset((mchunkptr)v, nb);
  483.     unlink_large_chunk(v);
  484.     if (rsize < 256)
  485.     {      
  486.       v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
  487.       ((mchunkptr)((char*)v+rsize + nb))->head |= PINUSE_BIT;
  488.     }  
  489.     else
  490.     {
  491.       v->head = nb|PINUSE_BIT|CINUSE_BIT;
  492.       r->head = rsize|PINUSE_BIT;
  493.       ((mchunkptr)((char*)r+rsize))->prev_foot = rsize;
  494.       insert_large_chunk((tchunkptr)r, rsize);
  495.     }
  496.     return chunk2mem(v);
  497.   }
  498.   return 0;
  499. }
  500.  
  501. static void* internal_realloc(struct m_state *m, void* oldmem,
  502.                                size_t bytes);
  503.  
  504. void* realloc(void* oldmem, size_t bytes)
  505. {
  506.   if (oldmem == 0)
  507.     return malloc(bytes);
  508.   else
  509.   {
  510.     struct m_state *m = &ms;
  511.     return internal_realloc(m, oldmem, bytes);
  512.   }
  513. };
  514.  
  515. #define check_inuse_chunk(M,P)
  516.  
  517. #define MAX_REQUEST 256*1024*1024
  518. #define set_inuse(M,p,s)\
  519.   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
  520.   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
  521.  
  522. static void* internal_realloc(struct m_state *m, void* oldmem, size_t bytes)
  523. { mchunkptr oldp;
  524.   size_t oldsize;
  525.   mchunkptr next;
  526.   mchunkptr newp;
  527.   void* extra;
  528.  
  529.   if (bytes >= MAX_REQUEST)
  530.     return 0;
  531.  
  532.   oldp = mem2chunk(oldmem);
  533.   oldsize = oldp->head & ~INUSE_BITS;
  534.   next = chunk_plus_offset(oldp, oldsize);
  535.   newp = 0;
  536.   extra = 0;
  537.  
  538.     /* Try to either shrink or extend into top. Else malloc-copy-free */
  539.  
  540.   if( (oldp->head & CINUSE_BIT) &&
  541.        ((char*)oldp < (char*)next)&&
  542.        (next->head & PINUSE_BIT))
  543.   {
  544.     size_t nb = ((bytes+7)&~7)+8;
  545.     if (oldsize >= nb)
  546.     { /* already big enough */
  547.       size_t rsize = oldsize - nb;
  548.       newp = oldp;
  549.       if (rsize >= 16)
  550.       {
  551.         mchunkptr remainder = chunk_plus_offset(newp, nb);
  552.         set_inuse(m, newp, nb);
  553.         set_inuse(m, remainder, rsize);
  554.         extra = chunk2mem(remainder);
  555.       }
  556.     }
  557.     else
  558.     if (next == m->top && oldsize + m->topsize > nb)
  559.     {
  560.         /* Expand into top */
  561.       size_t newsize = oldsize + m->topsize;
  562.       size_t newtopsize = newsize - nb;
  563.       mchunkptr newtop = chunk_plus_offset(oldp, nb);
  564.       set_inuse(m, oldp, nb);
  565.       newtop->head = newtopsize |PINUSE_BIT;
  566.       m->top = newtop;
  567.       m->topsize = newtopsize;
  568.       newp = oldp;
  569.     }
  570.   }
  571.   else
  572.   {
  573.     return 0;
  574.   }
  575.  
  576.  
  577.   if (newp != 0)
  578.   {
  579.     if (extra != 0)
  580.        free(extra);
  581.      
  582.     check_inuse_chunk(m, newp);
  583.     return chunk2mem(newp);
  584.   }
  585.   else
  586.   {
  587.     void* newmem = malloc(bytes);
  588.     if (newmem != 0)
  589.     {
  590.        size_t oc = oldsize - 4;
  591.        memcpy(newmem, oldmem, (oc < bytes)? oc : bytes);
  592.        free(oldmem);
  593.     }
  594.     return newmem;
  595.   }
  596.   return 0;
  597. }
  598.