memory allocation functions

If you are new to development, plan on spending some time here before visiting the other forums.

Moderator:Moderators

Post Reply
xixpsychoxix
Posts:59
Joined:Tue Oct 13, 2009 8:49 pm
memory allocation functions

Post by xixpsychoxix » Thu Nov 12, 2009 3:02 am

I wanted to get started writing some memory functions like malloc and free, but i have no idea how to start. Basically what i am asking is if someone can give me like a basic overview of how to use the tutorial's physical or virtual memory manager to start writing stuff like this. Or a tutorial on the subject just something that will give me the basic idea of what im gonna have to do for this cuz i have alot of code that i wanna write that will rely on these functions and i need help!!!

User avatar
djsilence
Posts:30
Joined:Sun Feb 15, 2009 8:49 pm
Location:Kyiv, Ukraine
Contact:

Re: memory allocation functions

Post by djsilence » Thu Nov 12, 2009 3:44 pm

http://www.jamesmolloy.co.uk/tutorial_h ... 0Heap.html

Look through this tutorial... it has some simple implementation of malloc function (kmalloc) but it is hardly connected to its own tutorial's base (I mean previous chapters of that tutorial). Else, some theory is given there.



http://www.osdever.net/tutorials.php?cat=6&sort=1

And get some view here. that's lot of theory and no practice, but that material is truly helpful.

Daniel.
Thinking of great - thinking of little, thinking of little - thinking of great.

xixpsychoxix
Posts:59
Joined:Tue Oct 13, 2009 8:49 pm

Re: memory allocation functions

Post by xixpsychoxix » Tue Nov 17, 2009 9:09 pm

so would a good solution based off of what we have now (i plan on extending this much farther after the next few tutorials but i wanna write a temporary memory manager) be to simply use the physical memory manager to allocate an area of memory that i can divide up as needed? so that i could do something like:

Code: Select all


char *os_memory = pmmgr_alloc_blocks (10);
init_mem_mgr (os_memory);

//*os_memory is the block that the OS will use
char *test = (char *) malloc (10);

So basically we would initialize the library to use os_memory to give memory out but then how would i keep track of the locations stored and their attributes and their addresses and such?

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

Re: memory allocation functions

Post by Andyhhp » Wed Nov 18, 2009 1:44 am

Generally yes.

your init_mem_mgr function should also take the number of pages it currently has allocated so it knows when to ask the kernel for some more.

A completely different alternative is for the kernel to map the entire 4GB Virtual Address Space when the process starts and just flag most of the pages as unavaliable (i.e. unpaged).

This way, all that will happen if you need more heap space is that you take a pagefault (which you would have to take anyway).

~Andrew
Image

xixpsychoxix
Posts:59
Joined:Tue Oct 13, 2009 8:49 pm

Re: memory allocation functions

Post by xixpsychoxix » Wed Nov 18, 2009 1:58 am

ok, but i was going over some options and to use a bitmap to store information about bytes currently available it would take 1 byte per 8 bytes to mark bytes as used, so should i do it in larger chunks? because it seems that when you make a call to malloc it does not return a fixed chunk of memory but an exact size chunk of memory based on what you tell it to. so should i keep track of individual bits used or is there a better way? because if i store information in an array then i would be wasting alot more space or so it seems. I would have to make some sort of structure to define where the block of memory started and how long it is, which is size-efficient for bigger memory blocks but is not very efficient for small blocks. so is the bitmap the better approach? and is there a solution that i cannot see that will not waste as much space?

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

Re: memory allocation functions

Post by Andyhhp » Thu Nov 19, 2009 3:26 pm

a bitmap is not a good idea

if you are using 1 bit per byte that you allocate, you have a 1/9 or 11% overhead which is far too much of a waste of space.

In general, people will be using malloc to allocate large areas of memory.

A good easy start is just to have a linked list of allocated regions. and possibly a linked list of unallocated regions.

when you need to allocate some memory, you find a region in the unallocated list.
alter the unallocated entry accordingly and update the allocated list accordingly.

when you need to free some memory, delete the entry in the allocated list and update the unallocated list.


This method is by no means optimised or efficient but is a good starting point and significantly better than the bitmap approach

~Andrew
Image

xixpsychoxix
Posts:59
Joined:Tue Oct 13, 2009 8:49 pm

Re: memory allocation functions

Post by xixpsychoxix » Sun Nov 22, 2009 8:05 pm

so then i should not write malloc to allocate single bytes of memory? so then if i write this in windows:

Code: Select all


char *example = (char *) malloc (1);

how much space does this actually reserve? only one byte or multiple?

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

Re: memory allocation functions

Post by Andyhhp » Mon Nov 23, 2009 1:53 pm

In terms of possibility, it is theoretically possible to allocate individual bytes in this mannor

however, from an administrative point of view, it is infeasable to allocate blocks which are not multiples of the machine words size (4 bytes on a 32bit machine, 8 of a 64bit one).

In your example, the runtime will allocate 4 bytes for you, even though you only asked for 1

In terms of real memory, even more will be allocated (16 or so) which form the headers to this allocation. The headers are a constant size so will be the same for a 4 byte allocation or a 4MB allocation. This is why the stack is used for small variables (typically 4 bytes each) and the heap is used for large or complicated data structures.

~Andrew
Image

xixpsychoxix
Posts:59
Joined:Tue Oct 13, 2009 8:49 pm

Re: memory allocation functions

Post by xixpsychoxix » Tue Nov 24, 2009 4:07 am

i dunno i suppose that i still dont fully understand the concepts of memory allocation. when you say stack is this the processor's stack or are we talking about something abstract here? i dont understand stack-based allocation at all. i think i understand the heap. that is just pretty much a chunk of memory that the system owns and hands out according to request and availability right? but stack... i just dont understand. anyone have a good link for me? i am completely google-idiotic. i can never find the right results there that is why im askin this sry.

User avatar
Mike
Site Admin
Posts:465
Joined:Sat Oct 20, 2007 7:58 pm
Contact:

Re: memory allocation functions

Post by Mike » Fri Dec 04, 2009 9:20 pm

Hello,

The basic idea is that the system software needs to allocate an area of pages for the heap to be used by the program. malloc() and free() uses an allocation method, such as a slab allocator to provide methods for allocating and freeing chunks of memory on the heap that was allocated to it. This is how allocation typically works. You can even do this for the kernel: Allocate pages for the kernel heap somewhere in the virtual address space, and impliment an allocator for it.

malloc() and free() contains extra information on every allocation, such as a magic number (to test memory corruption), size of the allocation (so free knows how much to unallocate, etc.) Because of this, it will never allocate a single byte in the heap.

Stack based allocation and Bit map based allocations are fine for the physical frame allocator. Not for the more higher level malloc()/free() though.

I can also post a recent image that I made for Neptunes memory management scheme that might help you better understand how everything fits together.
Lead Programmer for BrokenThorn Entertainment, Co.
Website: http://www.brokenthorn.com
Email: webmaster@brokenthorn.com

xixpsychoxix
Posts:59
Joined:Tue Oct 13, 2009 8:49 pm

Re: memory allocation functions

Post by xixpsychoxix » Tue Feb 16, 2010 3:57 am

i know this post is old, sorry but i have one other thing. I have read alot about memory management and have decided to implement a linked-list style allocation using headers to point to allocated regions. The problem is I don't know what i should do about the list of headers because I cannot obviously dynamically allocate it and if i statically allocate the list it will be a fixed size. I do not want this. So how do i get around that problem?

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

Re: memory allocation functions

Post by Andyhhp » Tue Feb 16, 2010 9:59 am

Just because you allocate a fixed size of memory doesnt mean it cant be updated.

What you can do is allocate a page (4k) of bytes for the memory manager alone, and put the linked list in that area. When the linked list grows too much, allocate yourself another page and continue. The beauty of a linked list is that when the elements have space, it doesnt matter where they are in memory, you can find them by following the list from the beginning.

~Andrew
Image

xixpsychoxix
Posts:59
Joined:Tue Oct 13, 2009 8:49 pm

Re: memory allocation functions

Post by xixpsychoxix » Tue Feb 16, 2010 6:22 pm

so what i should do is make a header for each allocation and place it right before the allocated memory? so if this is the header:

Code: Select all


typedef struct
{
 uint32_t *size;
} header; 

each chunk it would look something like this:

Code: Select all


bytes 1-3 : size
bytes 3 - size: allocation

and my function would return the address directly after the header? does this sound about right, or should i use a separate list to maintain the information using a struct such as this:

Code: Select all


typedef struct
{
 uint32_t start;
 uint32_t size;
} header;

so that my list is in a separate place?

Post Reply