WebSVN – Kolibri OS – Diff – /kernel/branches/kolibri_pe/core/heap.c

 #include
 #include
 #include
+#define page_tabs 0xDF800000
 typedef struct
+{
    link_t link;
    link_t adj;
    addr_t base;
 #define   MD_FREE    1
 #define   MD_USED    2
+typedef struct {
-typedef struct {
+    u32_t  av_mapped;
-    SPINLOCK_DECLARE(lock);   /**< this lock protects everything below */
+    u32_t  av_unmapped;
-    u32_t  availmask;
+    link_t mapped[32];
+    link_t unmapped[32];
-    link_t free[32];
+    link_t used;
-    link_t used;
+    SPINLOCK_DECLARE(lock);   /**< this lock protects everything below */
 heap_t        lheap;
 heap_t        sheap;
-static inline void _set_lmask(count_t idx)
+static inline void _set_lavu(count_t idx)
-{ asm volatile ("bts %0, _lheap"::"r"(idx):"cc"); }
+{ asm volatile ("bts %0, _lheap+4"::"r"(idx):"cc"); }
-static inline void _reset_lmask(count_t idx)
+static inline void _reset_lavu(count_t idx)
-{ asm volatile ("btr %0, _lheap"::"r"(idx):"cc"); }
+{ asm volatile ("btr %0, _lheap+4"::"r"(idx):"cc"); }
+static inline void _set_savm(count_t idx)
+{ asm volatile ("bts %0, _sheap"::"r"(idx):"cc"); }
+static inline void _reset_savm(count_t idx)
+{ asm volatile ("btr %0, _sheap"::"r"(idx):"cc"); }
-static inline void _set_smask(count_t idx)
+static inline void _set_savu(count_t idx)
-{ asm volatile ("bts %0, _sheap"::"r"(idx):"cc"); }
+{ asm volatile ("bts %0, _sheap+4"::"r"(idx):"cc"); }
-static inline void _reset_smask(count_t idx)
+static inline void _reset_savu(count_t idx)
    ASSERT((size & 0x3FFFFF) == 0);
    for (i = 0; i < 32; i++)
+   {
-     list_initialize(&lheap.free[i]);
+        list_initialize(&lheap.mapped[i]);
+        list_initialize(&lheap.unmapped[i]);
-     list_initialize(&sheap.free[i]);
+        list_initialize(&sheap.mapped[i]);
+        list_initialize(&sheap.unmapped[i]);
    };
    list_initialize(&lheap.used);
    md->size = size;
    md->parent = NULL;
    md->state = MD_FREE;
-   list_prepend(&md->link, &lheap.free[31]);
+    list_prepend(&md->link, &lheap.unmapped[31]);
+    lheap.av_mapped    = 0x00000000;
-   lheap.availmask = 0x80000000;
+    lheap.av_unmapped  = 0x80000000;
-   sheap.availmask = 0x00000000;
+    sheap.av_mapped    = 0x00000000;
-  // phm_slab = slab_cache_create(sizeof(phismem_t), 32,NULL,NULL,SLAB_CACHE_MAGDEFERRED);
+    sheap.av_unmapped  = 0x00000000;
    return 1;
 };
    ASSERT((size & 0x3FFFFF) == 0);
    idx0 = (size>>22) - 1 < 32 ? (size>>22) - 1 : 31;
-   mask = lheap.availmask & ( -1<
+    mask = lheap.av_unmapped & ( -1<
    if(mask)
+   {
      if(idx0 == 31)
      {
-        md_t *tmp = (md_t*)lheap.free[31].next;
+            md_t *tmp = (md_t*)lheap.unmapped[31].next;
-        while((link_t*)tmp != &lheap.free[31])
+            while((link_t*)tmp != &lheap.unmapped[31])
+        {
           if(tmp->size >= size)
      else
+     {
        idx0 = _bsf(mask);
-       ASSERT( !list_empty(&lheap.free[idx0]))
+            ASSERT( !list_empty(&lheap.unmapped[idx0]))
-       md = (md_t*)lheap.free[idx0].next;
+            md = (md_t*)lheap.unmapped[idx0].next;
      };
+   }
    else
      return NULL;
    ASSERT(md->state == MD_FREE);
    list_remove((link_t*)md);
-   if(list_empty(&lheap.free[idx0]))
+    if(list_empty(&lheap.unmapped[idx0]))
-     _reset_lmask(idx0);
+        _reset_lavu(idx0);
      list_insert(&new_md->adj, &md->adj);
      new_md->base = md->base;
      new_md->size = size;
+        new_md->parent = NULL;
      new_md->state = MD_USED;
      md->base+= size;
      md->size-= size;
      idx1 = (md->size>>22) - 1 < 32 ? (md->size>>22) - 1 : 31;
-     list_prepend(&md->link, &lheap.free[idx1]);
+        list_prepend(&md->link, &lheap.unmapped[idx1]);
-     _set_lmask(idx1);
+        _set_lavu(idx1);
      return new_md;
    };
    md->state = MD_USED;
    return md;
     efl = safe_cli();
     idx0 = (size>>12) - 1 < 32 ? (size>>12) - 1 : 31;
-    mask = sheap.availmask & ( -1<
+    mask = sheap.av_unmapped & ( -1<
-    DBG("smask %x size %x idx0 %x mask %x\n",sheap.availmask, size, idx0, mask);
+    DBG("smask %x size %x idx0 %x mask %x\n",sheap.av_unmapped, size, idx0, mask);
     if(mask)
     {
         if(idx0 == 31)
         {
-            ASSERT( !list_empty(&sheap.free[31]));
+            ASSERT( !list_empty(&sheap.unmapped[31]));
-            md_t *tmp = (md_t*)sheap.free[31].next;
+            md_t *tmp = (md_t*)sheap.unmapped[31].next;
-            while((link_t*)tmp != &sheap.free[31])
+            while((link_t*)tmp != &sheap.unmapped[31])
+            {
         else
+        {
             idx0 = _bsf(mask);
-            ASSERT( !list_empty(&sheap.free[idx0]));
+            ASSERT( !list_empty(&sheap.unmapped[idx0]));
-            md = (md_t*)sheap.free[idx0].next;
+            md = (md_t*)sheap.unmapped[idx0].next;
+        }
     };
     if(md)
+    {
+        DBG("remove md %x\n", md);
         DBG("remove md %x\n", md);
+        ASSERT(md->state==MD_FREE);
-        ASSERT(md->state==MD_FREE);
+        ASSERT(md->parent != NULL);
         list_remove((link_t*)md);
-        if(list_empty(&sheap.free[idx0]))
+        if(list_empty(&sheap.unmapped[idx0]))
-            _reset_smask(idx0);
+            _reset_savu(idx0);
+    }
             safe_sti(efl);
             return NULL;
         };
+        ASSERT(lmd->size != 0);
+        ASSERT(lmd->base != 0);
+        ASSERT((lmd->base & 0x3FFFFF) == 0);
+        ASSERT(lmd->parent == NULL);
         md = (md_t*)slab_alloc(md_slab,0);    /* FIXME check */
         link_initialize(&md->link);
         list_initialize(&md->adj);
         DBG("insert md %x, base %x size %x idx %x\n", md,md->base, md->size,idx1);
         if( idx1 < 31)
-          list_prepend(&md->link, &sheap.free[idx1]);
+          list_prepend(&md->link, &sheap.unmapped[idx1]);
         else
         {
-            if( list_empty(&sheap.free[31]))
+            if( list_empty(&sheap.unmapped[31]))
-                list_prepend(&md->link, &sheap.free[31]);
+                list_prepend(&md->link, &sheap.unmapped[31]);
             else
             {
-                md_t *tmp = (md_t*)sheap.free[31].next;
+                md_t *tmp = (md_t*)sheap.unmapped[31].next;
-                while((link_t*)tmp != &sheap.free[31])
+                while((link_t*)tmp != &sheap.unmapped[31])
+                {
                     if(md->base < tmp->base)
                         break;
                     tmp = (md_t*)tmp->link.next;
+                }
                 list_insert(&md->link, &tmp->link);
             };
         };
-        _set_smask(idx1);
+        _set_savu(idx1);
     return md;
+}
+md_t* __fastcall find_mapped_md(size_t size)
+{
+    eflags_t efl;
+    md_t *md = NULL;
+    count_t idx0;
+    u32_t mask;
+    ASSERT((size & 0xFFF) == 0);
+    efl = safe_cli();
+    idx0 = (size>>12) - 1 < 32 ? (size>>12) - 1 : 31;
+    mask = sheap.av_mapped & ( -1<
+    DBG("small av_mapped %x size %x idx0 %x mask %x\n",sheap.av_mapped, size,
+         idx0, mask);
+    if(mask)
+    {
+        if(idx0 == 31)
+        {
+            ASSERT( !list_empty(&sheap.mapped[31]));
+            md_t *tmp = (md_t*)sheap.mapped[31].next;
+            while((link_t*)tmp != &sheap.mapped[31])
+            {
+                if(tmp->size >= size)
+                {
+                    md = tmp;
+                    break;
+                };
+                tmp = (md_t*)tmp->link.next;
+            };
+        }
+        else
+        {
+            idx0 = _bsf(mask);
+            ASSERT( !list_empty(&sheap.mapped[idx0]));
+            md = (md_t*)sheap.mapped[idx0].next;
+        }
+    };
+    if(md)
+    {
+        DBG("remove md %x\n", md);
+        ASSERT(md->state==MD_FREE);
+        list_remove((link_t*)md);
+        if(list_empty(&sheap.mapped[idx0]))
+            _reset_savm(idx0);
+    }
+    else
+    {
+        md_t    *lmd;
+        addr_t  frame;
+        addr_t  *pte;
+        int i;
+        lmd = find_large_md((size+0x3FFFFF)&~0x3FFFFF);
+        DBG("get large md %x\n", lmd);
+        if( !lmd)
+        {
+            safe_sti(efl);
+            return NULL;
+        };
+        ASSERT(lmd->size != 0);
+        ASSERT(lmd->base != 0);
+        ASSERT((lmd->base & 0x3FFFFF) == 0);
+        ASSERT(lmd->parent == NULL);
+        frame = core_alloc(10);                        /* FIXME check */
+        lmd->parent = (void*)frame;
+        pte = &((addr_t*)page_tabs)[lmd->base>>12];    /* FIXME remove */
+        for(i = 0; i<1024; i++)
+        {
+           *pte++ = frame;
+           frame+= 4096;
+        }
+        md = (md_t*)slab_alloc(md_slab,0);             /* FIXME check */
+        link_initialize(&md->link);
+        list_initialize(&md->adj);
+        md->base = lmd->base;
+        md->size = lmd->size;
+        md->parent  = lmd;
+        md->state = MD_USED;
+    };
+    if(md->size > size)
+    {
+        count_t idx1;
+        md_t *new_md = (md_t*)slab_alloc(md_slab,0);    /* FIXME check */
+        link_initialize(&new_md->link);
+        list_insert(&new_md->adj, &md->adj);
+        new_md->base = md->base;
+        new_md->size = size;
+        new_md->parent = md->parent;
+        md->base+= size;
+        md->size-= size;
+        md->state = MD_FREE;
+        idx1 = (md->size>>12) - 1 < 32 ? (md->size>>12) - 1 : 31;
+        DBG("insert md %x, base %x size %x idx %x\n", md,md->base, md->size,idx1);
+        if( idx1 < 31)
+          list_prepend(&md->link, &sheap.mapped[idx1]);
+        else
+        {
+            if( list_empty(&sheap.mapped[31]))
+                list_prepend(&md->link, &sheap.mapped[31]);
+            else
+            {
+                md_t *tmp = (md_t*)sheap.mapped[31].next;
+                while((link_t*)tmp != &sheap.mapped[31])
+                {
+                    if(md->base < tmp->base)
+                        break;
+                    tmp = (md_t*)tmp->link.next;
+                }
+                list_insert(&md->link, &tmp->link);
+            };
+        };
+        _set_savm(idx1);
+        md = new_md;
+    };
+    md->state = MD_USED;
+    safe_sti(efl);
+    return md;
+}
-void __fastcall free_small_md(md_t *md)
+void __fastcall free_unmapped_md(md_t *md)
+{
     eflags_t  efl ;
     md_t     *fd;
     md_t     *bk;
+    count_t   idx;
-    count_t   idx;
+    ASSERT(md->parent != NULL);
     efl = safe_cli();
     spinlock_lock(&sheap.lock);
+        {
             idx = (fd->size>>12) - 1 < 32 ? (fd->size>>12) - 1 : 31;
             list_remove((link_t*)fd);
-            if(list_empty(&sheap.free[idx]))
+            if(list_empty(&sheap.unmapped[idx]))
-                _reset_smask(idx);
+                _reset_savu(idx);
             md->size+= fd->size;
             md->adj.next = fd->adj.next;
             md->adj.next->prev = (link_t*)md;
+        {
             idx = (bk->size>>12) - 1 < 32 ? (bk->size>>12) - 1 : 31;
             list_remove((link_t*)bk);
-            if(list_empty(&sheap.free[idx]))
+            if(list_empty(&sheap.unmapped[idx]))
-                _reset_smask(idx);
+                _reset_savu(idx);
             bk->size+= md->size;
             bk->adj.next = md->adj.next;
             bk->adj.next->prev = (link_t*)bk;
     md->state = MD_FREE;
     idx = (md->size>>12) - 1 < 32 ? (md->size>>12) - 1 : 31;
-    _set_smask(idx);
+    _set_savu(idx);
     if( idx < 31)
-        list_prepend(&md->link, &sheap.free[idx]);
+        list_prepend(&md->link, &sheap.unmapped[idx]);
     else
+    {
-        if( list_empty(&sheap.free[31]))
+        if( list_empty(&sheap.unmapped[31]))
-            list_prepend(&md->link, &sheap.free[31]);
+            list_prepend(&md->link, &sheap.unmapped[31]);
         else
+        {
-            md_t *tmp = (md_t*)sheap.free[31].next;
+            md_t *tmp = (md_t*)sheap.unmapped[31].next;
-            while((link_t*)tmp != &sheap.free[31])
+            while((link_t*)tmp != &sheap.unmapped[31])
+            {
     safe_sti(efl);
 };
+void __fastcall free_mapped_md(md_t *md)
+{
+    eflags_t  efl ;
+    md_t     *fd;
+    md_t     *bk;
+    count_t   idx;
+    ASSERT(md->parent != NULL);
+    ASSERT( ((md_t*)(md->parent))->parent != NULL);
-#define page_tabs 0xDF800000
+    efl = safe_cli();
     spinlock_lock(&sheap.lock);
-/*
-phismem_t* __fastcall phis_alloc(count_t count)
-{
+    if( !list_empty(&md->adj))
-   phismem_t *phm;
+    {
-   count_t tmp;
-   phm = (phismem_t*)slab_alloc(phm_slab, 0);
         bk = (md_t*)md->adj.prev;
-   phm->count = count;
+        fd = (md_t*)md->adj.next;
-   tmp = count;
-   while(tmp)
+        if(fd->state == MD_FREE)
+   {
+            idx = (fd->size>>12) - 1 < 32 ? (fd->size>>12) - 1 : 31;
-   {
+            list_remove((link_t*)fd);
+            if(list_empty(&sheap.mapped[idx]))
+                _reset_savm(idx);
+            md->size+= fd->size;
+            md->adj.next = fd->adj.next;
+            md->adj.next->prev = (link_t*)md;
+            slab_free(md_slab, fd);
+        };
+        if(bk->state == MD_FREE)
+        {
+            idx = (bk->size>>12) - 1 < 32 ? (bk->size>>12) - 1 : 31;
+            list_remove((link_t*)bk);
+            if(list_empty(&sheap.mapped[idx]))
+                _reset_savm(idx);
       u32_t order;
+            bk->size+= md->size;
-      asm volatile ("bsr %0, %1":"=&r"(order):"r"(tmp):"cc");
-      asm volatile ("btr %0, %1" :"=r"(tmp):"r"(order):"cc");
+            bk->adj.next = md->adj.next;
-      phm->frames[order] = core_alloc(order);
-   };
+            bk->adj.next->prev = (link_t*)bk;
-   return phm;
+            slab_free(md_slab, md);
+            md = fd;
+        };
    };
-void map_phm(addr_t base, phismem_t *phm, u32_t mapflags)
+    md->state = MD_FREE;
-{
-   count_t count;
+    idx = (md->size>>12) - 1 < 32 ? (md->size>>12) - 1 : 31;
-   addr_t  *pte;
-   count = phm->count;
+    _set_savm(idx);
-   pte = &((addr_t*)page_tabs)[base>>12];
    while(count)
-   {
+    if( idx < 31)
-     u32_t order;
+        list_prepend(&md->link, &sheap.mapped[idx]);
-     addr_t frame;
+    else
      count_t size;
+        if( list_empty(&sheap.mapped[31]))
             list_prepend(&md->link, &sheap.mapped[31]);
+        else
+   {
+            md_t *tmp = (md_t*)sheap.mapped[31].next;
-     asm volatile ("bsr %0, %1":"=&r"(order):"r"(count):"cc");
+            while((link_t*)tmp != &sheap.mapped[31])
      asm volatile ("btr %0, %1" :"=r"(count):"r"(order):"cc");
                 if(md->base < tmp->base)
-     frame = phm->frames[order] | mapflags;
+                    break;
     ASSERT(size != 0);
-    size = (size+4095)&~4095;
-    md = find_small_md(size);
-    if( md )
-    {
-        ASSERT(md->state == MD_USED);
+    size = (size+4095)&~4095;
-        if( flags & PG_MAP )
+    if( flags & PG_MAP )
-        {
-            count_t tmp = size >> 12;
-            addr_t  *pte = &((addr_t*)page_tabs)[md->base>>12];
+    {
+        md = find_mapped_md(size);
-            while(tmp)
+        if( !md )
-            {
-                u32_t  order;
+            return NULL;
-                addr_t frame;
-                size_t size;
+        md_t *lmd = (md_t*)md->parent;
+        ASSERT( lmd != NULL);
+        ASSERT( lmd->parent != NULL);
+        addr_t  frame  = (md->base - lmd->base + (addr_t)lmd->parent)|
+                         (flags & 0xFFF);
-                asm volatile ("bsr %1, %0":"=&r"(order):"r"(tmp):"cc");
+        DBG("frame %x\n", frame);
-                asm volatile ("btr %1, %0" :"=r"(tmp):"r"(order):"cc");
+        ASSERT(frame != 0);
-                frame = core_alloc(order) | flags;         /* FIXME check */
+        count_t  tmp = size >> 12;
         addr_t  *pte = &((addr_t*)page_tabs)[md->base>>12];
+        while(tmp--)
+                {
+                    *pte++ = frame;
-                size = (1 << order);
+                    frame+= 4096;
-                while(size--)
+                };
+    }
+    else
+        md = find_unmapped_md(size);
     if( !md )
-                    *pte++ = frame;
+        return NULL;
                     frame+= 4096;
         DBG("allocate: %x size %x\n\n",md->base, size);
         return (void*)md->base;
-    };
+};
-    return NULL;
-};
 void __fastcall mem_free(void *mem)
+{
+    }
     if( md )
+    {
+        md_t *lmd;
         DBG("\tmd: %x base: %x size: %x\n",md, md->base, md->size);
+        ASSERT(md->state == MD_USED);
+        list_remove((link_t*)md);
+        lmd = (md_t*)md->parent;
+        ASSERT(lmd != 0);
-        ASSERT(md->state == MD_USED);
+        if(lmd->parent != 0)
+        {
         count_t tmp  = md->size >> 12;
         addr_t  *pte = &((addr_t*)page_tabs)[md->base>>12];
         while(tmp--)
+        {
-            *pte++ = 0;
-            asm volatile (
+            *pte++ = 0;
-                "invlpg (%0)"
+            asm volatile (
                 "invlpg (%0)"
+                    ::"r" (mem) );
-                :"r" (mem) );
+            mem+= 4096;
+        };
-            mem+= 4096;
+            free_mapped_md( md );
         };
-        list_remove((link_t*)md);
+        else
-        free_small_md( md );
             free_unmapped_md( md );
-    else
+    }
-        DBG("\tERROR: invalid base address: %x\n", mem);
+    else

Subversion Repositories Kolibri OS

(root)/kernel/branches/kolibri_pe/core/heap.c – Rev 886 → 888