Subversion Repositories Kolibri OS

Rev

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

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