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;
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;
}