malloc/free simple questions

[xyjamepa]

Hi guys...
i want to write a simple malloc,free functions but there
some points i don't understand them:
correct me if i'm wrong and please with some explain...
i should build a heep that comes right after the kernel.
the heep consists of at least two linked list:
one for allocated but free memory chunk and the
other one for used memory chunk.
let us assume i want my heep to be 1MB, this mega
must be in a virtual memory i mean we shouldn't reserve
1MB of physical memory,if yes how can i do this?
and if no what should i do?
Thanx.

[ces_mohab]

i should build a heep that comes right after the kernel.

the heap can be any where in the address space but it's recommended after the kernel.

the idea is to allocate some physical pages from the physical allocator nad map them to the heap virtual address assume 0xD0000000.

now you start with an empty heap. then a request of memory search your linked lists when not found suitable block allocate more heap from physical allocator. ans so on.

freeing memory is tricky some how. because you simply don't move an item from used list ot empty list only. as you need to merge freed areas to reduce fragmentation. so take care

[Combuster]

Generally, you'd define a start of heap, and add to it as you need more memory.

The kernel will need to map the needed memory to some hardware, in most cases thats either physical memory, or the swap. Essentially you dont need to reserve physical memory for anything as it can be swapped out any moment and used for something else later.

But malloc shouldnt need any knowledge of your memory management. You can simply design it to use a certain area in the virtual address space, and have the memory manager take care of the memory actually being present.

However, if you dont use swap, then all requested memory should be mapped to physical memory, needing you to allocate physical memory for your programs.

Either case, i suggest you surf the internet on how to manage physical memory in the kernel.
Wiki link you may want to start with

[xyjamepa]

No guys this not what i mean.
my question is:
dose the heep consist of the linked list?
or the heep just save some pointers to the free
memory chunk?if yes where can i save the linked list?
and about the heep size and location is it in the physical
memory or in the virtual ?
Thanx.

[carbonBased]

This is something that will change depending on the allocator you use. Generally speaking (I believe) people layer allocators.

I use a page allocator as the lowest level (I call it a large granularity allocator). The page allocator will only ever allocate 1 (4kb) page. I implemented using a "page stack." Effectively an array which contains pointers to every page in the heap. Every page ahead of (and including) index 'n' is free, every page behind index 'n' is allocated. Allocating and freeing involves moving the pages from one side to the other (you effectively pop the next available page into the other side of the array -- ie, increment or decrement 'n').

The page allocator works entirely in the physical address space. A pager module will then be used to map these pages where required.

On top of the page allocator and the pager can be what I call a byte granularity allocator. There are several different ways to implement this (there's a good tut on one method called the cottontail method, iirc... you should be able to google it). Some encode data into the actual allocated blocks (but do not make this accessable to apps) while others include lists and accounting details in another area of memory.

Personally, I use dlmalloc (Doug Lee's Malloc). It's a free (and widely used/tested) implementation of malloc and free that uses concepts such as "fast bins" and "free memory consolidation." I don't think I'd do these justice to explain, however, as I haven't fully wrapped my head around the Doug Lee implementation yet. Hopefully someone can shed some decent details on these.

--Jeff

[B.E]

Hi guys...
i want to write a simple malloc,free functions but there
some points i don't understand them:
correct me if i'm wrong and please with some explain...
i should build a heep that comes right after the kernel.
the heep consists of at least two linked list:
one for allocated but free memory chunk and the
other one for used memory chunk.

It's up to you how your OS manages memory. there is no definitive answer to your which method of memory managment is the best.

let us assume i want my heep to be 1MB, this mega
must be in a virtual memory i mean we shouldn't reserve
1MB of physical memory,if yes how can i do this?
and if no what should i do?
Thanx.

The page can exist anywere in physical memory or swaped out. when the kernal/user program, uses a peace of memory, the processor "sends" a pagefault exception for your OS to get the memory from disk or do what every you want

[deathangel]

The way I do my memory management is I have two ways of allocating memory. The first is by page, it can allocate anywhere from 1 to as many pages as the system will allow, which means it's page aligned which is good for executables, etc...

The second way is I have my heap manager allocate a fixed (yes I know it is fixed for now) size of that page aligned memory for the heap. Then I use a linked-list type of allocate algorithm to allocate heap space.

[ces_mohab]

No guys this not what i mean.
my question is:
dose the heep consist of the linked list?

it's your implementation to make linked list or binary tree or any data structure you want.

if yes where can i save the linked list?

You have two ways to save linked lists either a static array of items and having a field used set when this item is used. or a more elegant solution to use a header before each memory allocation.
e.g. to allocate 20 bytes you allocate 20 bytes + size of header.
acctual allocated memory = pointer to header + header size.

and about the heep size and location is it in the physical
memory or in the virtual ?

heap size is dynamic. which means heap expand when allocation in linked lists fail.
Generally heap management is on top level of memory manager which means that you don't access physical memory manager.

[xyjamepa]

ok guys here comes a problem, the linked list can handle
only one type of data int,char,long.....etc
and i'm programming my os using C not C++ so
i can't use template and sure i want to be able to
allocate all kinds of data so what can i do?
Thanx.

[deathangel]

Why you post twice? The way you are suggesting will not work, as a template class from the c library uses the new and delete operators, which call other memory allocators which would have to implemented. You have to implement your own linked list from scratch.