[Example] Heap Manager for brokenthorn

OS Design, Theory, and Programming

Moderator: Moderators

[Example] Heap Manager for brokenthorn

Postby Fadekraft » Thu Jul 12, 2012 8:24 pm

Hey everyone, today I finally was tired of seeing people needing help with a heap manager so i decided to share with you all a _SIMPLE_ heap manager i wrote a long time ago. Code is commented and you might need to replace the calls to mappage and allocblock to your own functions, but it will work with brokenthorns. The heap can expand but not contract. The code is commented most of it anyway. You can use the code as you want or for inspiration, but please keep the copyright if you decide to copy paste it.

Tell me if there is code missing! The defines can be changed to your own need if you need to relocate the heap
Also you might have to change the includes from heap.c and so on, but nothing hard.

Here is the heap.h:
Code: Select all
/***************************
   Heap Management
 ***************************/
#define KMALLOC_ADDR_START   0xD0000000
#define KMALLOC_ADDR_END   0xE0000000

#define KERNEL_HEAP_STRUCT   0xD0000000
#define KERNEL_HEAP_START   0xD0200000
#define KERNEL_HEAP_END      0xE0000000
#define KERNEL_HEAP_INC      0x100000
#define KERNEL_HEAP_SINC   0x40000
#define KERNEL_HEAP_SIZE   (KERNEL_HEAP_END - KERNEL_HEAP_START)

#define USER_HEAP_STRUCT   0xB0000000
#define USER_HEAP_START      0xB0200000
#define USER_HEAP_END      0xC0000000
#define USER_HEAP_INC      0x100000
#define USER_HEAP_SINC      0x20000
#define USER_HEAP_SIZE      (USER_HEAP_END - USER_HEAP_START)

//This is really big, 12 bytes.
typedef struct HmmHeader
{
   uint32_t addr;
   HmmHeader *next;
   uint32_t allocated : 1;
   uint32_t length : 31;

}hmmheader_t;

#define NODE_4KB_FLAG   0x1
#define NodeIs4KB(x)   ((((x)->start_addr) & 0x1) == 0x1)
#define AddrIsAligned(x) ((x & 0xFFF) == 0)

//16 bytes :x
typedef struct HmmNode
{
   uint32_t   start_addr;
   uint32_t   end_addr;
   
   HmmNode *next;
   HmmHeader *head;
}hmmnode_t;

//4 bytes
typedef struct HmmArea
{
   HmmNode *head;
}hmmarea_t;

//Init
extern void Initialize_Heap();
extern uint32_t HmmGetCount();

//kMalloc Align and phys return
extern void *kmalloc_ap(uint32_t l, uint32_t *p);

//kMalloc return phys
extern void *kmalloc_p(uint32_t l, uint32_t *p);

//kMalloc align
extern void *kmalloc_a(uint32_t l);

//kMalloc
extern void *kmalloc(uint32_t l);

//Internal kmalloc
extern void *_kmalloc(uint32_t sz, uint32_t aligned);

//kFree
extern void kfree(void *p);

//krealloc / reallocate
extern void *kcalloc(size_t nmemb, size_t size);
extern void *krealloc(void *ptr, size_t size);

extern HmmArea* kHeap;


And here is the heap.c
Code: Select all
/* MollenOS Heap Manager
   Basic Heap Manager
   No contraction for now, for simplicity.

   MollenOS
   Copyright 2012

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation?, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <Kernel\Memory.h>
#include <Kernel\kPrintf.h>
#include <Kernel\kPanic.h>
#include <Kernel\asmdefs.h>
#include <string.h>
#include <assert.h>

//Prototypes
void HmmExpand4Kb(uint32_t sz);
void HmmExpand1Kb(uint32_t sz);

HmmArea *kHeap = NULL;
uint32_t heap_caddr = KERNEL_HEAP_START;
uint32_t heap_calloc = KERNEL_HEAP_STRUCT;
uint32_t heap_cc_max = KERNEL_HEAP_STRUCT;

void *salloc(size_t sz)
{
   //Make sure we allocate pages enough ;b
   if((heap_calloc + sz) >= heap_cc_max)
   {
      VmmMapPage(PmmAllocBlock(), heap_cc_max);
      heap_cc_max += 0x1000;
   }

   uint32_t *ret = (uint32_t*)heap_calloc;
   memset((void*)heap_calloc, 0, sz);
   heap_calloc += sz;
   
   return ret;
}

void Initialize_Heap()
{
   //use our specially designed struct-alloc hihi
   kHeap = (hmmarea_t*)salloc(sizeof(hmmarea_t));

   //We start out by inserting 128 byte blocks
   HmmNode *node = (hmmnode_t*)salloc(sizeof(hmmnode_t));
   node->head = 0;
   node->next = 0;
   node->start_addr = heap_caddr;
   node->end_addr = heap_caddr + KERNEL_HEAP_SINC;
   
   //Insert pages into heap list!
   for(uint32_t i = 0; i < (KERNEL_HEAP_SINC); i += 0x80)
   {
      //Create a new hole, of size 0x80 (128 bytes)
      hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
      hole->addr = (heap_caddr + i);
      hole->allocated = 0;
      hole->length = 0x80;
      hole->next = NULL;
      
      //Insert it
      if(!node->head)
         node->head = hole;
      else
      {
         hmmheader_t *cur_header = node->head, *prev_header = NULL;
         while (cur_header)
         {
            prev_header = cur_header;
            cur_header = cur_header->next;
         }
         prev_header->next = hole;
      }
   }

   //Set start
   kHeap->head = node;

   //Increment
   heap_caddr += KERNEL_HEAP_SINC;
   
   //Make a 4KB node aswell
   HmmNode *node4kb = (hmmnode_t*)salloc(sizeof(hmmnode_t));
   node4kb->head = 0;
   node4kb->next = 0;
   node4kb->start_addr = heap_caddr | NODE_4KB_FLAG;
   node4kb->end_addr = heap_caddr + KERNEL_HEAP_INC;

   //Insert only 4kb pages
   for(uint32_t i = 0; i < (KERNEL_HEAP_INC); i += 0x1000)
   {
      //Create a new hole, of size 0x1000 (4kb)
      hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
      hole->addr = (heap_caddr + i);
      hole->allocated = 0;
      hole->length = 0x1000;      //This can change
      hole->next = 0;
      
      //Insert it
      if(!node4kb->head)
         node4kb->head = hole;
      else
      {
         hmmheader_t *cur_header = node4kb->head, *prev_header = NULL;
         while (cur_header)
         {
            prev_header = cur_header;
            cur_header = cur_header->next;
         }
         prev_header->next = hole;
      }
   }
   //Set start
   kHeap->head->next = node4kb;

   //Increment
   heap_caddr += KERNEL_HEAP_INC;
}

void HmmExpand1Kb(uint32_t sz)
{
   //Expand time!
   //Alloc
   HmmNode *node = (hmmnode_t*)salloc(sizeof(hmmnode_t));
   node->head = 0;
   node->next = 0;
   node->start_addr = heap_caddr;
   node->end_addr = heap_caddr + sz;

   //Insert new headers
   for(uint32_t i = 0; i < (sz); i += 0x80)
   {
      hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
      hole->addr = (heap_caddr + i);
      hole->allocated = 0;
      hole->length = 0x80;
      hole->next = 0;
      
      if(!node->head)
         node->head = hole;
      else
      {
         hmmheader_t *cur_header = node->head, *prev_header = NULL;
         while (cur_header)
         {
            prev_header = cur_header;
            cur_header = cur_header->next;
         }
         prev_header->next = hole;
      }
   }

   //Find a place in the heap list
   hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
   while (cur_node)
   {
      prev_node = cur_node;
      cur_node = cur_node->next;
   }

   //Set it in list
   prev_node->next = node;

   //Increment
   heap_caddr += sz;
}

void HmmExpand4Kb(uint32_t sz)
{
   //Expand time!
   //Alloc
   HmmNode *node = (hmmnode_t*)salloc(sizeof(hmmnode_t));
   node->head = 0;
   node->next = 0;
   node->start_addr = heap_caddr | NODE_4KB_FLAG;   //Tag it 4kb node
   node->end_addr = heap_caddr + sz;

   //Insert new headers
   for(uint32_t i = 0; i < (sz); i += 0x1000)
   {
      hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
      hole->addr = (heap_caddr + i);
      hole->allocated = 0;
      hole->length = 0x1000;
      hole->next = 0;
      
      if(!node->head)
         node->head = hole;
      else
      {
         hmmheader_t *cur_header = node->head, *prev_header = NULL;
         while (cur_header)
         {
            prev_header = cur_header;
            cur_header = cur_header->next;
         }
         prev_header->next = hole;
      }
   }

   //Find a place in the heap list
   hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
   while (cur_node)
   {
      prev_node = cur_node;
      cur_node = cur_node->next;
   }

   //Set it in list
   prev_node->next = node;

   //Increment
   heap_caddr += sz;
}

uint32_t HmmGetCount()
{
   //Primarily debugging purpose
   //Counts entries.
   uint32_t count = 0;
   hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
   while (cur_node)
   {
      hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
      while (cur_header)
      {
         count++;
         prev_header = cur_header;
         cur_header = cur_header->next;
      }
      prev_node = cur_node;
      cur_node = cur_node->next;
   }

   return count;
}

uint32_t _alloc(uint32_t sz, uint32_t aligned)
{
   //For expansion purposes
   uint32_t found = 0;
   //Are we looking for a page aligned space?
   hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
   while (cur_node)
   {
      if(NodeIs4KB(cur_node) && aligned)
      {
         uint32_t blocks_needed = sz / 0x1000;
         if((sz & 0xFFF) != 0x0)
            blocks_needed++;

         hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
         while (cur_header)
         {
            if(!cur_header->allocated)
            {
               //We found an unallocted 4kb header
               //If blocks needed is above one, we need to search for an hole
               if(blocks_needed > 1)
               {
                  hmmheader_t *chead = cur_header;
                  uint32_t blocks = blocks_needed;   //2, 1
                  while(blocks && chead)
                  {
                     if(chead->allocated)
                        break;

                     chead = chead->next;
                     blocks--;
                  }

                  if(blocks)   //ran out of headers and still blocks left to alloc
                  {
                     if(cur_header->next != NULL)
                        cur_header = cur_header->next;
                     else
                        break;
                     continue;
                  }
               }

               //If we reach this point, one of two things happened.
               //Either we only need to alloc 1 block, or we need to alloc some more.

               if(blocks_needed > 1)
               {
                  hmmheader_t *chead = cur_header;
                  while(blocks_needed)
                  {
                     //Map it in if it isn't
                     if(!VmmGetMapping(chead->addr, 0))
                        VmmMapPage(PmmAllocBlock(), chead->addr);

                     chead->allocated = 1;

                     chead = chead->next;
                     blocks_needed--;
                  }
                  cur_header->length = sz;
                  return cur_header->addr;
               }

               //1 block needed
               if(!VmmGetMapping(cur_header->addr, 0))
                  VmmMapPage(PmmAllocBlock(), cur_header->addr);
               
               cur_header->allocated = 1;
               return cur_header->addr;
            }

            prev_header = cur_header;
            
            if(cur_header->next != NULL)
               cur_header = cur_header->next;
            else
               break;
         }
      }
      else if(!NodeIs4KB(cur_node) && !aligned)
      {
         uint32_t blocks_needed = sz / 0x80;
         if((sz % 0x80) > 0x0)
            blocks_needed++;

         hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
         while (cur_header)
         {
            if(!cur_header->allocated)
            {
               //We found an unallocted 1kb header
               //If blocks needed is above one, we need to search for an hole
               if(blocks_needed > 1)
               {
                  hmmheader_t *chead = cur_header;
                  uint32_t blocks = blocks_needed;
                  while(blocks && chead)
                  {
                     if(chead->allocated)
                        break;

                     chead = chead->next;
                     blocks--;
                  }

                  if(blocks)   //ran out of headers and still blocks left to alloc
                  {
                     if(cur_header->next != NULL)
                        cur_header = cur_header->next;
                     else
                        break;
                     continue;
                  }
               }

               //If we reach this point, one of two things happened.
               //Either we only need to alloc 1 block, or we need to alloc some more.

               if(blocks_needed > 1)
               {
                  hmmheader_t *chead = cur_header;
                  while(blocks_needed)
                  {
                     //Map it in if it isn't
                     if(!VmmGetMapping(chead->addr, 0))
                        VmmMapPage(PmmAllocBlock(), chead->addr);

                     chead->allocated = 1;

                     chead = chead->next;
                     blocks_needed--;
                  }
                  cur_header->length = sz;
                  return cur_header->addr;
               }

               //We found an unallocted 128byte header
               //Map it in if not already.
               if(!VmmGetMapping((cur_header->addr & PAGE_MASK), 0))
                  VmmMapPage(PmmAllocBlock(), (cur_header->addr & PAGE_MASK));
               
               cur_header->allocated = 1;
               return cur_header->addr;
            }

            prev_header = cur_header;
            
            if(cur_header->next != NULL)
               cur_header = cur_header->next;
            else
               break;
         }

      }

      prev_node = cur_node;
      cur_node = cur_node->next;
   }

   //If we get here we need to expand.
   if(aligned && !found)
      HmmExpand4Kb(KERNEL_HEAP_INC);
   else
      HmmExpand1Kb(KERNEL_HEAP_SINC);   //128 byte

   return _alloc(sz, aligned);
}

uint32_t _free(uint32_t addr)
{
   uint32_t freed = 0;
   hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
   while (cur_node)
   {
      //Initial pointers
      hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
      //Search headers
      while (cur_header)
      {
         //Is this header our header?
         if(cur_header->addr == addr)
         {
            if(NodeIs4KB(cur_node) && (cur_header->length > 0x1000))
            {
               //Find amount of blocks to free
               uint32_t blocks_needed = cur_header->length / 0x1000;
               if((cur_header->length % 0x1000) > 0x0)
                  blocks_needed++;

               //search headers
               hmmheader_t *chead = cur_header;
               while(blocks_needed)
               {
                  //Unmap
                  if(VmmGetMapping(chead->addr, 0))
                     VmmUnmapPage(chead->addr);

                  chead->allocated = 0;   //set free
                  chead->length = 0x1000; //reset length just in case

                  chead = chead->next;
                  blocks_needed--;

               }
               return 1;
            }
            else if(cur_header->length > 0x80)
            {
               uint32_t blocks_needed = cur_header->length / 0x80;
               if((cur_header->length % 0x80) > 0x0)
                  blocks_needed++;

               //search headers
               hmmheader_t *chead = cur_header;
               while(blocks_needed)
               {
                  //Unmap, we need a better algorithm here....
                  //if(VmmGetMapping(chead->addr, 0))
                  //   VmmUnmapPage(chead->addr);

                  chead->allocated = 0;   //set free
                  chead->length = 0x80; //reset length just in case

                  chead = chead->next;
                  blocks_needed--;
               }

               return 1;
            }
            //If 4kb note, it was page aligned and we can unallocate
            if(NodeIs4KB(cur_node))
            {
               //found it, lets unmap it and unallocate it
               if(VmmGetMapping(addr, 0))
                  VmmUnmapPage(addr);
               
            }
            cur_header->allocated = 0;
            freed = 1;
            return freed;
         }
         prev_header = cur_header;
         cur_header = cur_header->next;
      }
      prev_node = cur_node;
      cur_node = cur_node->next;
   }

   return freed;
}

/*
 * KMALLOC
 */

void *kmalloc_ap(uint32_t l, uint32_t *p)
{
   void *ret = _kmalloc(l, 1);
   VmmGetMapping((uint32_t)ret, p);
   *p += (uint32_t)ret % 0x1000;
   return ret;
}

void *kmalloc_p(uint32_t l, uint32_t *p)
{
   void *ret = _kmalloc(l, 0);
   VmmGetMapping((uint32_t)ret, p);
   *p += (uint32_t)ret % 0x1000;
   return ret;
}

void *kmalloc_a(uint32_t l)
{
   return _kmalloc(l, 1);
}

void *kmalloc(uint32_t l)
{
   return _kmalloc(l, 0);
}

//Implementation of _kmalloc.
void *_kmalloc(uint32_t sz, uint32_t aligned)
{
   //Sanity checks
   if(heap_caddr >= KERNEL_HEAP_END)
      kPanic("kmalloc: Out of Memory!!!\n");
   if(heap_calloc >= KERNEL_HEAP_START)
      kPanic("kmalloc: Out of salloc-Memory!!!\n");

   if(sz > 0x1000)
      aligned = 1;

   //Allocation time!
   void* addr = (uint32_t*)_alloc(sz, aligned);

   //Null it
   if(aligned && sz <= 0x1000)
      memset(addr, 0, 0x1000);
   else
      memset(addr, 0, sz);

   return addr;
}

/*
 * KFREE
 */

//Basically just a call to _free
void kfree(void *p)
{
   if(_free((uint32_t)p))
      return;
   else
      kprintf("kfree: Invalid addr to free.");
}

/*
 * KCALLOC
 */

void *kcalloc(size_t nmemb, size_t size)
{
    return kmalloc(nmemb * size);
}

/*
 * KREALLOC
 */


void *krealloc(void *ptr, size_t size)
{
   uint32_t *new_ptr;
    if (ptr == NULL) {
        return kmalloc(size);
    }

    if (ptr != NULL && size == 0) {
        kfree(ptr);
        return NULL;
    }

    /* Simple implementation: allocate new space and copy the contents
       over.  Exercise: Improve this by searching through the free
       list and seeing whether an actual enlargement is possible. */
    new_ptr = (uint32_t*)kmalloc(size);
   
   if (new_ptr != NULL) {
        for (uint32_t i = 0; i < size; i++) {
            new_ptr[i] = ((uint32_t*)ptr)[i];
        }
        kfree(ptr);
    }
    return new_ptr;
}


Tell me if you have any problems using it!
Last edited by Fadekraft on Tue Jul 31, 2012 4:12 pm, edited 2 times in total.
Fadekraft
 
Posts: 15
Joined: Mon Sep 26, 2011 10:56 pm

Re: [Tutorial] Heap Manager for brokenthorn

Postby Fadekraft » Thu Jul 12, 2012 8:30 pm

Oh, and i know this is not a tutorial, i just didn't know what to put.
Fadekraft
 
Posts: 15
Joined: Mon Sep 26, 2011 10:56 pm

Re: [Tutorial] Heap Manager for brokenthorn

Postby pathos » Fri Jul 13, 2012 1:35 pm

Thank you, I'll give it a try sometime. My heap manager is a mess....
pathos
Moderator
 
Posts: 97
Joined: Thu Jan 10, 2008 6:43 pm
Location: USA

Re: [Tutorial] Heap Manager for brokenthorn

Postby Fadekraft » Fri Jul 13, 2012 4:50 pm

No problem at all, tell me if you need any help or if im using something there isn't in the brokenthorn virtual memory manager.
It worked perfectly for me so if implemented correctly it will work perfectly for all of you ^^
Fadekraft
 
Posts: 15
Joined: Mon Sep 26, 2011 10:56 pm

Re: [Tutorial] Heap Manager for brokenthorn

Postby Benjamin » Sun Jul 15, 2012 1:41 am

Then call it "Simple Heap Example."
When life gives you lemmings, keep them safe.
User avatar
Benjamin
 
Posts: 10
Joined: Sat Apr 16, 2011 2:52 am

Re: [Example] Heap Manager for brokenthorn

Postby Fadekraft » Tue Jul 17, 2012 11:18 pm

Hehe, changed it!

Anyway, hope it helps some people :)
Fadekraft
 
Posts: 15
Joined: Mon Sep 26, 2011 10:56 pm

Re: [Example] Heap Manager for brokenthorn

Postby Andyhhp » Mon Jul 30, 2012 11:07 pm

If you are looking for some constructive criticism:

Your #defines at the top should have the 'U' suffix to imply unsigned. It changes the behaviour of the arithmatic in certain places.

Change HmmHeader to be more like this:
Code: Select all
typedef struct HmmHeader
{
   uint32_t addr;
   HmmHeader *next;
   uint32_t allocated : 1;
   uint32_t length : 31;
}hmmheader_t;

Having bitfields in the middle of structs rather than at the end is a minefield.

Code: Select all
#define AddrIsAligned(x) ((addr & 0x00000FFF) == 0)
You mean ((x) & 0xFFF) ? Dont forget to wrap all macro parameters in brackets.

You dont need any of the externs for the function declarations, and the internal kmalloc should appear at the top of heap.c rather than in the header (although this is simply good coding practices). Any functions taking no parameters should be declared "ReturnType FunctionName(void)". Leaving out the void means that the function will accept any number of arguments without error.

Code: Select all
HmmArea *kHeap = 0;
This should be NULL not 0. NULL and 0 are very different things.

Code: Select all
hmmheader_t *cur_header = node4kb->head, *prev_header = 0;
This code doesn't do what you presumably intend. It will unconditionally set cur_header to be 0. Futhermore, 0 should be NULL, and prev_header appears to be undeclared. I presume you mean ; instead of , ? This syntax appears in several locations through heap.c

Other than that, its looks like a good resource.

~Andrew (who is soon to rewrite the Xen 64bit heap allocator to account for NUMA layouts)
Image
Andyhhp
Moderator
 
Posts: 387
Joined: Tue Oct 23, 2007 10:05 am
Location: 127.0.0.1

Re: [Example] Heap Manager for brokenthorn

Postby Fadekraft » Tue Jul 31, 2012 4:08 pm

Thanks a lot for taking the time to look through the code and giving comments, most you say i totally agree on, and that mistake with the macros is stupid haha.

I have one counter-comment to the argument about this piece of code:
Code: Select all
hmmheader_t *cur_header = node4kb->head, *prev_header = 0;


This does exactly what I want it to, if it didn't work the heap itself would not work (And this heap compiles and work in the posted state - with visual studio 2010).
In visual studio 2010 that code means exactly the same as:

Code: Select all
hmmheader_t *cur_header = node4kb->head;
hmmheader_t *prev_header = 0;


And yes, indeed it should be NULL and not 0 :D

Thanks again for your comments, much appreciated, I'll just update the code in the post!
Fadekraft
 
Posts: 15
Joined: Mon Sep 26, 2011 10:56 pm

Re: [Example] Heap Manager for brokenthorn

Postby Andyhhp » Tue Jul 31, 2012 10:29 pm

D'oh - I have been doing C89 for so long that without syntax highlighting, i completely missed the fact that that was a declaration rather than just another line of code.

~Andrew
Image
Andyhhp
Moderator
 
Posts: 387
Joined: Tue Oct 23, 2007 10:05 am
Location: 127.0.0.1


Return to Advanced OS Development

Who is online

Users browsing this forum: No registered users and 1 guest