src/memory/heap.cpp

Idź do dokumentacji tego pliku.

/***********************************************************
*PANALIX 0.06, (c) Adrian Panasiuk 2002-4                  *
*adek336[at]o2.pl, panalix.prv.pl                          *
*under GPLv3 license                                       *
*                                                          *
*panalix - small osdev project                             *
************************************************************
*       heap.cpp, version 2.1                              *
************************************************************
*                                                          *
*heaps for the kernel                                      *
*                                                          *
*30'07'04- the heap is locked when resizing used blocks    *
*table; a list of used virtual space; blocks may now carry *
*a name instead of bitwise facility codes; bug fixes(2.1)  *
*25'04'04- base on o.05 branch, changed hugely, mainly a   *
*big rewrite(2.0)                                          *
*                                                          *
***********************************************************/

#include "src/common/shared.hpp"
#include "src/common/string.hpp"
#include "src/thread/thread.hpp"
#include "src/thread/scheduler.hpp"
#include "src/memory/align.hpp"
#include "src/memory/zone.hpp"
#include "src/memory/memset.hpp"
#include "src/memory/alloc4k.hpp"
#include "src/memory/pager.hpp"
#include "src/memory/heap.hpp"

#define OUT_OF_MEMORY_CRITICAL 0
#define INVALID_FREE_ALERT 0

#define HEAP_DONT_USE_PROLOG 0

/* \} */


namespace Memory {
   namespace Heap {
      uint32 dbg=0;  // czasem potrzebna

      //some vars
      class heapbox heap0;      //the most principal heap
      Memory::zone virtual_pages;//a stack of free, virtual pages
      class blist_t HeapList;   //here we store all the heaps.

      heapbox::heapbox() { lock_heap.init(const_cast<char*>("heap")); } ;

      /*init some basic data for heaps*/
      void init()
      {
         uint32 *stack_addr, stack_size;
         uint32 page0,page1;uint32 i,n;
         uint32 x;
         HeapList.init("HeapList",&heap0);
         //computate variables
         page0=align_up(mem_heap_start+Memory::Physical::heap_area_addend,PAGE_ALIGN);
         page1=mem_heap_end;
         stack_size=align_up((page1-page0)/HEAP_STACK_GRAN * sizeof(uint32),PAGE_ALIGN);
         Memory::Physical::disable_balloc();

         //allocate some space
         stack_addr = (uint32*) page0; page0+=stack_size;
         for (i=0;i<stack_size;i+=PAGE_SIZE)
         { x= alloc4k(1,true);
            Memory::Pager::kmem.pte_map(i+(uint32)stack_addr,
                  x|PTE_PRESENT|PTE_WRITEABLE); }
            //init the virtual pages stack
            virtual_pages.init(stack_addr,stack_size/sizeof(uint32),HEAP_STACK_GRAN);
            n=0;
         #if 0
                cout("\npage1-HEAP_STACK_GRAN=");
                cout(page1-HEAP_STACK_GRAN);
                cout("\npage0=");
                cout(page0);
         #endif
            for (i=page1-HEAP_STACK_GRAN;i>page0;i-=HEAP_STACK_GRAN)
            {
               stack_addr[n++]=i;
            }
            virtual_pages.set_length(n);
         #if 0
                cout("\nvirt stack_addr=");cout((uint32)stack_addr);
                cout("\nstack_size=");cout(stack_size);
                cout("\nphys=");cout(Memory::Pager::kmem.pte_val((uint32)stack_addr&0xfffff000));
                cout("\n&stack_addr[n]=");cout((uint32)&stack_addr[n]);
             for (i=0;i<1000000;i++)
              {
             int in= Memory::Physical::free_pages_low.alloc(1);
                if (in) { cout("{");cout(in);cout("}"); }
              }
             sysfail("");
         #endif

            /*allocate heap0*/
            int r;
            r = allocate_heapbox(&heap0, "heap0");
            if (r != ESUCCESS)
               sysfail("error allocating heap0");
      }

      int allocate_heapbox(class heapbox *hbx, const char *name)
      {
         /*allocate space for the heap. we need to find space for the used blocks table, and we will
           do this in the space dedicated for the heap. later, we will put the info about the table
           in the table itself so we can free it on resize.*/
         addr_t heap_addr = morecore(HEAP_GRAN); // must be sufficient for the used blocks table
         uint32 prolog_shift = 
            #if HEAP_DONT_USE_PROLOG
               0
            #else
               sizeof(struct block_prolog)
            #endif
         ;
         addr_t heap0_addr = heap_addr+prolog_shift;
         size_t used_blocks_table_size = HEAP_TBLE*sizeof(block_used);
         size_t used_blocks_alloc_size = used_blocks_table_size+prolog_shift;
         if ( (used_blocks_alloc_size/HEAP_MIN_BLOCK) * HEAP_MIN_BLOCK != used_blocks_alloc_size)
            used_blocks_alloc_size = (used_blocks_alloc_size/HEAP_MIN_BLOCK+1)*HEAP_MIN_BLOCK;

         if (heap_addr == NULL) {
         #if OUT_OF_MEMORY_CRITICAL
            sysfail("cannot allocate heapbox");
         #else
            complain("cannot allocate heapbox");
         #endif
            return EOUTOFMEMORY;
         }


         block_free *firstfree;
         memset((void*)heap0_addr,NULL,used_blocks_table_size);

         //insert into the table
         ((block_used*)heap0_addr)->ptr=(void*) heap_addr;
         ((block_used*)heap0_addr)->size=used_blocks_alloc_size;
         ((block_used*)heap0_addr)->facility=FAC_MEMORY|FAC_USEDBLOCKS;
         ((block_used*)heap0_addr)->destruct=null;
         countMagic((block_used*)heap0_addr);

         //firstfree
         firstfree=(block_free*)(heap_addr + used_blocks_alloc_size);
         firstfree->prev=NULL;
         firstfree->next=NULL;
         firstfree->size=HEAP_GRAN*HEAP_STACK_GRAN - used_blocks_alloc_size;
         countMagic(firstfree);

         //initialise the management
         hbx->init((block_used*)heap0_addr, HEAP_TBLE, firstfree, name);

      #if HEAP_DONT_USE_PROLOG
      #else
         ((struct block_prolog*)heap_addr)->ov= 0;
         ((struct block_prolog*)heap_addr)->check= PROLOG_CHECKSUM - 0 + hbx->heapbox_no;
      #endif

         //update the statistics
         hbx->stats.max=HEAP_GRAN*HEAP_STACK_GRAN;
         hbx->stats.used=used_blocks_alloc_size;/* \bug ensure consistent use of [used] field */

         //create a table of used virtual addresses
         hbx->VirtAddrs.init("virtaddrs", hbx);
         hbx->VirtAddrs.ptr((void*) heap_addr, NULL);
         //add the heap to the heaplist
         HeapList.ptr(hbx,NULL);

         hbx->morecor_new_node= (struct blist_s*) hbx->mallocFunc(sizeof(struct blist_s), NO_ALIGN, (uint32)"virtaddr", NULL, 0);

         return ESUCCESS;
      }

      //allocates some virtual space
      addr_t morecore(size_t cnt)
      {
         addr_t ret;
         uint32 i,x;
         // for(i=0;i<10;i++){
         ret=virtual_pages.alloc(cnt);
         //     cout("\nret=");
         //     cout(ret);
         //             }
         //     cout("\nMemory::Pager::lazy_enable=");
         //     cout(Memory::Pager::lazy_enable);
         // cout("A");for(;;);
         if ((ret==NULL) || (ret==0xFFFFFFFF)) return ret;
         //allocate physical pages
         if (!Pager::lazy_enable)       //if lazy paging not enabled
            for (i=0;i<cnt*HEAP_STACK_GRAN/PAGE_SIZE;i++)
            { x=alloc4k(1,true);
               Memory::Pager::kmem.pte_map(ret+i*PAGE_SIZE,x|PTE_WRITEABLE|PTE_PRESENT);}
         else
            for (i=0;i<cnt*HEAP_STACK_GRAN/PAGE_SIZE;i++)
               Pager::kmem.pte_lazy(ret+i*PAGE_SIZE,PTE_WRITEABLE);

         return ret;
      }

      //free them
      void freecore(addr_t virt, size_t cnt)
      {
         /*FIXME*/
         notimpl();
      }

      //checksum check
      int checkMagic(block_free *item)
      {
         /*FIXME*/
         return 1;
      }

      //checksum check
      int checkMagic(block_used *item)
      {
         /*FIXME*/
         return 1;
      }

      //count checksum
      int countMagic(block_free *item)
      {
         /*FIXME*/
         return 1;
      }

      //count checksum
      int countMagic(block_used *item)
      {
         /*FIXME*/
         return 1;
      }


      //initialise variables
      void heapbox::init(block_used *usd, size_t max_blcks, block_free *fir, const char *nam)
      {
         static uint32 heapbox_no_acc;
         heapbox_no = heapbox_no_acc ;
         heapbox_no_acc ++ ;
         //clear struct
         memset(this, 0, sizeof(heapbox));
         //setup vars
         lock_heap.init(nam);
         used=usd; max_blocks=max_blcks; first=fir;
         memmove(&name, nam, MIN(lgth(nam),HEAPBOX_NAME-1));
      }

      //dispose all memory
      void heapbox::destruct()
      {
         size_t i;
         uint32 z;
         blist_s *item,*next;
         uint32 addr,ph;
         //delete from HeapList
         HeapList.del(HeapList.find(this));
         //destruct all items with a destructor field
         for (i=0;i<max_blocks;i++)
            if (used[i].destruct)
               used[i].destruct(this,used[i].ptr);
         //free physical pages & freecore virtual space
         for (item=VirtAddrs.head;item;item=next)
         {
            next=item->next;
            addr=(uint32)item->data;
            for(z=0;z<HEAP_STACK_GRAN;z+=PAGE_SIZE)
               if ((ph=Memory::Pager::kmem.pte_val(z+addr))&PTE_PRESENT)
                  disalloc4k(ph&0xfffff000);
            virtual_pages.free(addr);
         }
         //destroy book keeping
         VirtAddrs.done();
      }

      //check if a block of size (size) can be alligned (allignment) between memory adresses (r0) and (r0 + r_size)
      /*allignment has to be power of 2*/
      int can_be_aligned(uint32 r0, size_t r_size, size_t size, uint32 allignment)
      {
         uint32 i;
         /*this is an unoptimized algorithm, though.*/
         /*check if size is big enough*/
         if (r_size < size) return EINVAL;
         /*zero align is align of 1*/
         if (allignment == 0) 
            allignment = 1;
         /*this is the first alligned space, lower or equal than the upper range*/
         i = (r0 + r_size - size) & (0xFFFFFFFF - allignment + 1);
         /*the adress is in the upper range, but what about lower range?*/
         if (i >= r0) return i;
         return EINVAL; /*otherwise, no*/
      }

      /*adds a new block at address (new_block), between item and item->b_next*/
      void new_bl_bl (block_free *item, block_free *new_block)
      {
         block_free *i;
         uint32 old_size;
         i = item -> next;

         /*check if new_block is above item*/
         if ((uint32)new_block <= (uint32) item) sysfail("error #1");

         /*check, if 1) new_block is below item -> b_next or 2) item -> b_next == 0*/
         if ((i != 0)&&((uint32) new_block >= (uint32) i)) sysfail("error #2");

         /*create the block*/
         item -> next = new_block;
         old_size = item -> size;
         item -> size = (uint32) new_block - (uint32) item;
         countMagic(item);


         new_block -> prev = item;
         new_block -> next = i;
         new_block -> size = old_size - item -> size;
         countMagic(new_block);

         if (i) {
            i -> prev = new_block;
            countMagic(i);}

      }

      /*unanchor block from firstfree linked list*/
      void heapbox::unAnchorBlock(block_free *item)
      {
         /*unanchor from previous block*/
         if (item -> prev) {
            item -> prev -> next = item -> next;
            countMagic(item -> prev);}

            /*unanchor from next block*/
            if (item -> next) {
               item -> next -> prev = item -> prev;
               countMagic(item -> next);}

               /*what if this is the only block in the linked list?*/
               if ((!item -> prev)&&(!item -> next))
               {
                  /*the block's size is zero*/
                  //            firstfree -> b_size = 0;
                  //            countMagic(firstfree);
                  /*zero firstfree as we have no free blocks, sbrk() will recreate the list*/
                  first = NULL;
                  /*now - allocate more space for heap*/
                  morecor(HEAP_GRAN, !Memory::Pager::lazy_enable);      /*64kb, allocate phys pages*/
               } else
                  if (item == first)    /*what if this is firstfree but it's not the only block?*/
                  {
                     first = item -> next;
                     first -> prev = 0;
                     countMagic(first);
                  }     
      }

      /*change block_used (item) into a memused block*/
      int heapbox::take_block (block_free *item, uint32 facility, int (destructor)(class heapbox*,void*))
      {
         /*unanchor from linked list*/
         unAnchorBlock(item);


         /*save info about the block*/
         int bu = knew_used(item, item -> size, facility, destructor);
         if (bu == -1) {
            complain("knew_used failed;");
            panic();
            return -1;
         }
         /*update stats*/
         stats.used+=item->size;
         return bu;
      }

      //add a block to used list
      int heapbox::knew_used(void *ptr, uint32 size, uint32 facility, int (*destruct)(class heapbox*,void*))
      {
         uint32 i;
         i = begin_search;
         //     i=0;
         while (used[i].size)
         {
            i++;        /*find a free place*/
            if (i >= max_blocks)
            {
               TTYDisableLock=true;
               cout(const_cast<char*>("knew_used failed; reached allocated heap blocks limit"));
            #if 0
               complain(max_blocks);
               complain(stats.allocs);
            #endif

               asm volatile("cli\nhlt");
               return -1;
            }
         #if 0/*{{{*/
                {
               for (i=0;i<1000000;i++)
               {
               int in;
               (in=Memory::Physical::free_pages_high.alloc(1))||(in=Memory::Physical::free_pages_low.alloc(1));
               if (in) { cout("{");cout(in);cout("}"); }
               }

               cout("\nname=");
               cout(name);
               cout("\nstats.used=");
               cout(stats.used);
               cout("\nstats.max=");
               cout(stats.max);
               cout("\nstats.allocs=");
               cout(stats.allocs);
               cout("\nmax_blocks=");
               cout(max_blocks);
               cout("\nbegin_search=");
               cout(begin_search);
               cout("\ni=");
               cout(i);
               sysfail("oh no!");
               }
          #endif/*}}}*/
         } begin_search=i;
         /*create the used object*/
         used[i].size = size;
         used[i].ptr = ptr;
         used[i].facility = facility;
         used[i].destruct=destruct;
         countMagic(&used[i]);
         /*new block in tha club*/
         stats.allocs++;

         return i;
      }

      addr_t heapbox::morecor(uint32 cnt, bool alloc_pgs)
      {
         /* **** */
         //should not put a lock on "lock_heap", because this function is only ran
         //from within functions already holding the lock.
         addr_t ret;
         uint32 i,x;
         block_free *item;
         block_free *list, *pr=NULL;
         blist_s *node;
         ret=virtual_pages.alloc(cnt);

         if (ret==NULL) return NULL;
         //book keeping: add these virtual pages to the list, later we use the table when freeing virt mem
         //     VirtAddrs.ptr((void*)ret,NULL); //we save info which virtual pages are used by the heap
         //node= (struct blist_s*) mallocFunc(sizeof(struct blist_s), NO_ALIGN, (uint32)"virtaddr", NULL, MALLOC_NOLOCKS|(NowResizingUsed?MALLOC_NORESCUE:0));
         node= morecor_new_node;
         morecor_new_node=null;
         memset(node,0,sizeof(struct blist_s*));
         node->size= 0; node->data= (void*)ret; node->func=(char*)__func__; node->line=__LINE__; node->file=(char*)__FILE__; node->tree= NULL;
         VirtAddrs.link(node);
         //allocate physical pages
         for (i=0;i<cnt*(HEAP_STACK_GRAN/PAGE_SIZE);i++)
            if (alloc_pgs)
            { x=alloc4k(1,true);
               Memory::Pager::kmem.pte_map(ret+i*PAGE_SIZE,x|PTE_WRITEABLE|PTE_PRESENT); }
            else
               Memory::Pager::kmem.pte_lazy(ret+i*PAGE_SIZE, PTE_WRITEABLE);
         //create a freeblock item
         item=(block_free*)ret;
         memset(item,0,sizeof(block_free));
         item->size=cnt*HEAP_STACK_GRAN;
         //add to the list
         for (list=first;list;list=list->next)
         { pr= list; if (list > item) break; }

         if (list == NULL)
         {
            if (pr==NULL)       //no other blocks
               first=item;
            else
            {
               pr->next=item;
               countMagic(pr);
               item->prev=pr;
               countMagic(item);
            }
         } else
         {
            item->prev=list->prev;
            item->next=list;
            if (list->prev)
               list->prev->next=item;
            list->prev=item;
         }
         //defragment
         kdefragment(item);
         //update statistics
         stats.max+= cnt*HEAP_STACK_GRAN;

         return ESUCCESS;
      }

      //allocate memory; return the block
      void *heapbox::mallocFunc(size_t size, size_t alignment,uint32 facility, int (*destruct)(class heapbox*, void*), uint32 MallocState) {
         void *ret;
#if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
#endif/*}}}*/
#if HEAP_DONT_USE_PROLOG
         ret= mallocFuncPr(size,alignment,facility,destruct,MallocState);
#else
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
         ret= mallocFuncPr(size+sizeof(struct block_prolog),alignment,facility,destruct,MallocState);
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
         assert(kget_info(ret));
         ret = (void*) (((struct block_prolog*)ret)+1);
#endif
#if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
#endif/*}}}*/

         if ( ( (MallocState & MALLOC_NORESCUE) == 0) && ( (MallocState & MALLOC_MORECOR_NEW_NODE) == 0) && (morecor_new_node == null) ) {
            morecor_new_node= (struct blist_s*) mallocFunc(sizeof(struct blist_s), NO_ALIGN, (uint32)"virtaddr", NULL, MALLOC_MORECOR_NEW_NODE);
         }
#if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
#endif/*}}}*/
         return ret;
      }
      //allocate memory; return the prolog
      void *heapbox::mallocFuncPr(size_t size, size_t alignment, uint32 facility, int (*destruct)(class heapbox*,void*), uint32 MallocState)
      {
//      static int Z;
//      int Zn= 0x3400;
//      Z++;
//         if (Z>Zn)
//            complain(Z);
//         if (Z>Zn) lnDbg ;
         block_free *item;
         uint32 n;
         uint32 prolog_alignment_shift=
         #if HEAP_DONT_USE_PROLOG
            0
         #else
            sizeof(struct block_prolog)
         #endif
         ;

         //lock tha heap
         if ((MallocState & MALLOC_NOLOCKS)==0)
            lock_heap.lock();


         //if there are only two slots left, resize the table. one is for the new table before the old is freed. The second is for morecor(), if by chance we get out of slots in the used table atm we exhaust virtual space in the heap.
      #if HEAP_DONT_USE_PROLOG
      // wtf
         if (stats.allocs+2 >= max_blocks-1)
      #else
         if (stats.allocs+2 >= max_blocks-22)
      #endif
            if ((MallocState&MALLOC_NORESCUE)==0)
               //        {      rescue_malloc=true;
            { NowResizingUsed= true;
               resize_used_blocks_table();
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
           complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
           freeze();
         }
      #endif/*}}}*/
               //               rescue_malloc=false; }
               NowResizingUsed= false; }
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
           complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
           freeze();
         }
      #endif/*}}}*/

               /*must be divisible by HEAP_MIN_BLOCK, and must be at least HEAP_MIN_BLOCK*/
               size=align_up(size, HEAP_MIN_BLOCK);

      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
               for (item=first; item; item=item->next)
               {
                  /*look for the magic key*/
                  checkMagic(item);

                  /*allignability*/
                  n = can_be_aligned(prolog_alignment_shift+ (uint32) item, item->size-prolog_alignment_shift,  /*range*/
                        size-prolog_alignment_shift, alignment);
                  #if HEAP_DONT_USE_PROLOG
                  #else
                  assert(prolog_alignment_shift == sizeof(struct block_prolog));
                  assert(8 == sizeof(struct block_prolog));
                  #endif
                  

                  /*da block's big enough, and allignment possible?*/
                  if (n==(uint32)EINVAL) continue;

                  assert ( (alignment==0) || ( (n & (alignment-1)) == 0) );
                  n -= prolog_alignment_shift;


      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/

                  /*if the align's place is not equal to the blocks start,
                    and the difference is less than DEF_MIN_BLOCK_SIZE - then we can not
                    give away this block*/
                  if (n != (uint32) item) {
                     if (n - (uint32)item < HEAP_MIN_BLOCK) {
                        continue;
                     }
                     else
                        if (n!= (uint32) item)
                        {
                           /*there is a difference of at least DEF_MIN_BLOCK_SIZE bytes*/
                           /*divide the block*/
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
                           new_bl_bl(item, (block_free*)n);
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            complain((uint32)item);
            complain(n);
            complain((uint32)used);
            complain((uint32)&used[max_blocks]);
            freeze();
         }
      #endif/*}}}*/

                           /*continue work on the upper block*/
                           item = (block_free*) n;
                        }
                  }
                  /*whether the space between the block's size and requested size is
                    at least DEF_MIN_BLOCK_SIZE*/
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
                  if (item -> size - size >= HEAP_MIN_BLOCK)
                  {
                     /*divide into two*/
                     new_bl_bl (item, (block_free*)((uint32)item + size));
                     /*we take the one under*/
                     int bu;
                     bu= take_block (item,facility,destruct);
#if HEAP_DONT_USE_PROLOG
#else
                     /* construct prolog (could this be unlocked ? ) */
                     struct block_prolog *bp;
                     bp= reinterpret_cast<struct block_prolog*>(item);
                     bp->ov=bu;
                     bp->check = PROLOG_CHECKSUM - bp->ov+heapbox_no;
                     assert(kget_info(item));
#endif
                     /*unlock system*/
                     if ((MallocState & MALLOC_NOLOCKS)==0)
                        lock_heap.ulock();
                     /*return the block*/
//                     if (Z > Zn) lnDbg;
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
//                     if (Z > Zn) lnDbg;
                     return ((char*) item);  // zwraca prolog
                  }
                  else
                  {
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
                     /*take whole block*/
                     int bu;
                     bu=take_block(item,facility,destruct);
                  #if HEAP_DONT_USE_PROLOG
                  #else
                     /* construct prolog */
                     struct block_prolog *bp;
                     bp= reinterpret_cast<struct block_prolog*>(item);
                     bp->ov=bu;
                     bp->check = PROLOG_CHECKSUM - bp->ov + heapbox_no;
                     assert(kget_info(item));
                  #endif
                     /*unlock system*/
                     if ((MallocState & MALLOC_NOLOCKS)==0)
                        lock_heap.ulock();
                     /*return the block*/
//                     if (Z > Zn) lnDbg;
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
//                     if (Z > Zn) lnDbg;
                     return((char*) item); // zwraca prolog; mallocFunc dodaje odpowiednia ilosc bajtow
                  }
               }

               /*we've got here? that means no block is good enough*/
               /*let's allocate some more space for the heap*/
               if ((size/HEAP_STACK_GRAN) < HEAP_GRAN) {
                  morecor (HEAP_GRAN, !Memory::Pager::lazy_enable);             /*at least 64kb*/
               }
               else {
                  morecor((size/HEAP_STACK_GRAN) + 1, !Memory::Pager::lazy_enable);
               }

               /*back to the starting point*/
               void *d;
//               if (Z>Zn) lnDbg ;
               d= mallocFuncPr(size, alignment, facility, destruct, MallocState|MALLOC_NOLOCKS);

               /*unlock system*/
               if ((MallocState & MALLOC_NOLOCKS)==0)
                  lock_heap.ulock();

               return(d); //zwraca prolog
      }


      //allocate memory; stub for mallocFunc
      void *heapbox::malloc(size_t size, size_t alignment, uint32 facility, int (*destruct)(class heapbox*,void*)) {
         _PF;
         uint32 fl;
         asm volatile("pushf\npopl %0\ncli" :"=g"(fl));
         void *ret;
         ret= mallocFunc(size,alignment,facility,destruct, 0);
         asm volatile("pushl %0\npopf"::"g"(fl));
         Preturn (ret);
      }

      //allocate memory; stub for mallocFunc
      void *heapbox::malloc(size_t size, size_t alignment, const char *name, int (*destruct)(class heapbox*,void*)) {
         return malloc(size,alignment,(uint32)name,destruct);
      }

      //find usedblocks table info about allocated space (ptr)
      block_used *heapbox::kget_info(void *ptr)
      {
         if (ptr == 0) {
            sysfail("kget_info: ptr == 0");
            //nulls must not be passed to kget_info
         }

      #if HEAP_DONT_USE_PROLOG
         uint32 i = 0;
         while (used[i].ptr != ptr)
         {
            i++;
            if (i >= max_blocks) return NULL;
         }

         return used + i;
      #else
         struct block_prolog *pr;
         pr= static_cast<struct block_prolog*>(ptr);
         if (pr->ov + pr->check != PROLOG_CHECKSUM+heapbox_no) {
         #if INVALID_FREE_ALERT
               complain("kget_info: prolog checksum erroneous");
               complain((uint32)ptr);
               complain(pr->ov + pr->check);
//               complain(PROLOG_CHECKSUM+heapbox_no);
//               complain(name);
//               freeze();
//            }
         #endif
            return null;
         }
         return &used[pr->ov];

      #endif
      }

      //returns block size
      uint32 heapbox::blsize(char *ptr)
      {
         block_used *info;
         /*get info about the block*/
         info = kget_info(ptr);
         /*should check if such a block exists*/
         if (info == NULL) return 0;

         return info -> size;
      }

      //find last free block
      block_free *heapbox::klastfree()
      {
         block_free *item;
         for (item = first; item -> next; item = item -> next) ;
         return item;
      }


//freeFunc2
#if 1
      int heapbox::freeFunc2(void *ptr, uint32 FreeState) {
         int ret;
         if (ptr==null) { complain("free:null ptr"); freeze(); }
         ret=freeFuncPr2( (void*)(((struct block_prolog*)ptr)-1), FreeState);
         return ret;
      }
      //free it; ptr points to prolog
      int heapbox::freeFuncPr2(void *ptr, uint32 FreeState)
      {
         block_used *info;
         block_free *item, *i;

         info = kget_info(ptr);
         item = (block_free*) ptr;



         ptr= (void*)(((struct block_prolog*)ptr)+0);
         ((struct block_prolog*)ptr)->ov=0;
         ((struct block_prolog*)ptr)->check=0;

         if (info == NULL || info->size == 0) {
            lnDbg;
            return EINVAL;
         }
         /*destruct the object, if a destructor is given*/
         if (info->destruct != NULL) {
            lnDbg;
            info->destruct(this,ptr);
         }
         //one less block in tha heap
         stats.allocs--;

         /*ptr is below firstfree*/
         if (item < first)
         {
            first -> prev = item;
            countMagic(first);
            item -> next = first;
            item -> prev = 0;
            item -> size = info->size;
            first = item;

            countMagic(item);
         } else
         {      /*item is above last free block*/
         #if 1
            i = klastfree();
            if (item > i)
            {
               i -> next = item;
               item -> prev = i;
               item -> next = 0;
               item -> size = info->size;

               countMagic(item); countMagic(i);
            } else
            {   /*item is between 2 blocks*/
               i = first;
               
               /*find the nearest block lower than item*/
               while ((uint32)i -> next < (uint32)item) i = i -> next;

               /*now insert the block into the chain*/
               item -> next = i -> next;
               i -> next = item;
               item -> prev = i;
               item -> next -> prev = item;
               item -> size = info -> size;

            #if 0
               countMagic(item); countMagic(i);
               countMagic(item -> next);
            #endif
            }
         #endif
         }

         /*update stats. allocs var changed earlier*/
         stats.used-= info->size;
         /*we free this entry in the table*/
         info -> ptr = null;
         info -> facility = 0;
         info -> size = 0;
         info -> destruct = null;
         countMagic(info);
         /*begin_search update*/
         uint32 b_new;
         b_new = ((uint32)info-(uint32)used) / sizeof(block_used);
         if (b_new < begin_search)
            begin_search=b_new;
         /*link chain ptr with any other near chains*/
         kdefragment(ptr);
         /*unlock system*/
//         if ((FreeState&MALLOC_NOLOCKS)==0)
//            lock_heap.ulock();

         return ESUCCESS; /*success*/
      }
#endif

      int heapbox::freeFunc(void *ptr, uint32 FreeState) {
         int ret;
         if (ptr==null) {
            complain("free:null ptr");
            freeze();
         }
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
     #if HEAP_DONT_USE_PROLOG
         ret=freeFuncPr( ptr, FreeState );
     #else
         ret=freeFuncPr( (void*)(((struct block_prolog*)ptr)-1), FreeState);
     #endif
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
         return ret;
      }
      //free it; ptr points to prolog
      int heapbox::freeFuncPr(void *ptr, uint32 FreeState)
      {
         #if INVALID_FREE_ALERT
         if (ptr==null)
            complain("free: null ptr");
         #endif
         if (ptr == null)
            return EINVAL;
         block_used *info;
         block_free *item, *i;

         info = kget_info(ptr);
         item = (block_free*) ptr;


         sbg;

      #if HEAP_DONT_USE_PROLOG
      #else
         ptr= (void*)(((struct block_prolog*)ptr)+0);
         ((struct block_prolog*)ptr)->ov=0;
         ((struct block_prolog*)ptr)->check=0;
      #endif

         if (info == NULL || info->size == 0) {
         #if INVALID_FREE_ALERT
               complain(name); complain("invalid free "); complain(reinterpret_cast<uint32>((void*)(((struct block_prolog*)ptr)+1)));
         #endif
            return EINVAL;
         }

         /*destruct the object, if a destructor is given*/
         if (info->destruct != NULL) {
            info->destruct(this,ptr);
         }
         /*lock system*/
         if ((FreeState&MALLOC_NOLOCKS)==0)
            lock_heap.lock();
         //one less block in tha heap
         stats.allocs--;

         /*ptr is below firstfree*/
         if (item < first)
         {
            sbg;
//            lnDbg;
            first -> prev = item;
            countMagic(first);
            item -> next = first;
            item -> prev = 0;
            item -> size = info->size;
            first = item;
            sbg;

            countMagic(item);
         } else
         {      /*item is above last free block*/
            sbg;
            i = klastfree();
            if (item > i)
            {
            sbg;
               i -> next = item;
               item -> prev = i;
               item -> next = 0;
               item -> size = info->size;

               countMagic(item); countMagic(i);
            } else
            {   /*item is between 2 blocks*/
               i = first;

               /*find the nearest block lower than item*/
               while (i -> next < item) i = i -> next;

               /*now insert the block into the chain*/
               item -> next = i -> next;
               i -> next = item;
               item -> prev = i;
               item -> next -> prev = item;
               item -> size = info -> size;

               countMagic(item); countMagic(i);
               countMagic(item -> next);
            }
         }

         /*update stats. allocs var changed earlier*/
         stats.used-= info->size;
         /*we free this entry in the table*/
         info -> ptr = null;
         info -> facility = 0;
         info -> size = 0;
         info -> destruct = null;
         countMagic(info);
         /*begin_search update*/
         uint32 b_new;
         b_new = ((uint32)info-(uint32)used) / sizeof(block_used);
         if (b_new < begin_search)
            begin_search=b_new;
         /*link chain ptr with any other near chains*/
         kdefragment(ptr);
         /*unlock system*/
         if ((FreeState&MALLOC_NOLOCKS)==0)
            lock_heap.ulock();

         sbg;
         return ESUCCESS; /*success*/
      }

      int heapbox::free(void *ptr) {
         uint32 fl;
         asm volatile("pushf\npopl %0\ncli":"=g"(fl));
         int ret;
         ret=freeFunc(ptr,0);
         asm volatile("pushl %0\npopf"::"g"(fl));
         return ret;
      }


      //returns allocs
      uint32 heapbox::allocated_count() {
         return stats.allocs;
      }

      //check if (ptr) isn't next to another free block. if yes, link them
      //so this is used for defragmenting memory
      void heapbox::kdefragment(void *ptr)
      {
         block_free *item;

         item = (block_free*) ptr;

         /*look at prev item only if b_prev != 0*/
         if (item -> prev)

            /*can I link with the previous?*/
            if (item -> prev -> size + (uint32) item -> prev == (uint32) item)
            {
               item -> prev -> size += item -> size;    /*size = size of 1 block + size of 2 block*/
               item -> prev -> next = item -> next;     /*get rid of the middle block*/
               if (item -> next) item -> next -> prev = item -> prev;   /*item -> next no more points at nonexistant item, now at item->prev*/

               countMagic(item -> prev);
               if (item -> next) countMagic(item -> prev -> next);
               /*this is necessary for the rest of the function to work, coz item is no longer a valid block reference*/
               item = item -> prev;
            }

         /*look at next item only if b_next != 0*/
         if (item -> next)

            /*can I link with the next?*/
            if ((uint32) item -> next == item -> size + (uint32) item)
            {
               /*we joint the blocks item and item->b_next*/
               item -> size += item -> next -> size;
               /*delete item->b_next block from linked list, coz it's area is now adressed by item*/
               item -> next = item -> next -> next;
               /*delete the block from item -> b_next, formerly item -> b_next -> b_next*/
               if (item->next)
               {item -> next -> prev = item;countMagic(item -> next);}

               /*count the checksum*/
               countMagic(item);
            }
      }
      // resizes the table, ziom
      int heapbox::resize_used_blocks_table()
      {
         void *new_table, *old_table=used;
         //allocate a new table
//         assert(!dbg);
         new_table=mallocFunc((max_blocks+HEAP_TBLE_GRAN)*sizeof(block_used),
               STACK_ALIGN, FAC_MEMORY|FAC_USEDBLOCKS, NULL, MALLOC_NOLOCKS|MALLOC_NORESCUE);
      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)old_table)-1) );
         if ( kget_info(((struct block_prolog*)old_table)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)old_table)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/
         if (new_table == NULL)
         {
         #if OUT_OF_MEMORY_CRITICAL
            debug_dump_call_trace();
         #endif
            complain("out of memory!");
         #if OUT_OF_MEMORY_CRITICAL
            freeze();
         #endif
            return EINVAL; }
         //lock heap
         //     lock_heap.lock();
         //prepare the table
         memmove(new_table, (void*)used, max_blocks*sizeof(block_used));
         memset((char*)new_table+max_blocks*sizeof(block_used), 0, HEAP_TBLE_GRAN*sizeof(block_used));
         //setup new table
         max_blocks+=HEAP_TBLE_GRAN;
      #if 0
         complain(name);
         complain(max_blocks);
         complain(stats.allocs);
      #endif
         used=(block_used*)new_table;
         //ulock heap
         //     lock_heap.ulock();
         //free old table
         freeFunc(old_table, MALLOC_NOLOCKS);

      #if 1/*{{{*/
         assert( kget_info(((struct block_prolog*)used)-1) );
         if ( kget_info(((struct block_prolog*)used)-1)->destruct != null ) {
            complain( (uint32)kget_info(((struct block_prolog*)used)-1)->destruct );
            freeze();
         }
      #endif/*}}}*/


         return ESUCCESS;
      }




};      /*namespace Heap*/
};      /*namespace Memory*/

//output some stats, including the freelist linked list
void debug_heap_stats(Memory::Heap::heapbox *hp)
{
   // new data on output
   cout(const_cast<char*>("\n-----\n"));
   // the free blocks
   Memory::Heap::block_free *item;
   for (item=hp->first; item; item=item->next)
   {
      cout(const_cast<char*>("@"));
      cout((uint32)item);
      cout(const_cast<char*>(", size=0x"));
      cout(item->size);
      cout(const_cast<char*>(", next=0x"));
      cout((uint32)item->next);
      cout(const_cast<char*>(", prev=0x"));
      cout((uint32)item->prev);
      cout(const_cast<char*>(";\n"));
   }
   // ending stats
   cout("\n\"");
   cout(hp->name);
   cout("\", stats.allocs=0x");
   cout(hp->stats.allocs);
   cout(", stats.max=0x");
   cout(hp->stats.max);
   cout(", stats.used=0x");
   cout(hp->stats.used);
   cout("\n==end heap_stats=====\n");
   // do not use kprintf, which is heavy on heap routines
}

/*Gdy gwiazdke blyszczaca zobaczysz na niebie wspomnij
  wszystkich co kochali Ciebie gdy jedna zgasnie a droga
  rozb³ysnie niech Cie anio³ek odemnie u¶ci¶nie..;(

  -od Joelki..*/


/***********************************************************
*                                                          *
*panalix 0.06 (c) Adrian Panasiuk 2002-4                   *
*adek336[at]o2.pl, panalix.prv.pl                          *
*                                                          *
***********************************************************/

---