Page 1 of 1

memory allocation functions

Posted: Thu Nov 12, 2009 3:02 am
by xixpsychoxix
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!!!

Re: memory allocation functions

Posted: Thu Nov 12, 2009 3:44 pm
by djsilence
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.

Re: memory allocation functions

Posted: Tue Nov 17, 2009 9:09 pm
by xixpsychoxix
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?

Re: memory allocation functions

Posted: Wed Nov 18, 2009 1:44 am
by Andyhhp
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

Re: memory allocation functions

Posted: Wed Nov 18, 2009 1:58 am
by xixpsychoxix
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?

Re: memory allocation functions

Posted: Thu Nov 19, 2009 3:26 pm
by Andyhhp
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

Re: memory allocation functions

Posted: Sun Nov 22, 2009 8:05 pm
by xixpsychoxix
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?

Re: memory allocation functions

Posted: Mon Nov 23, 2009 1:53 pm
by Andyhhp
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

Re: memory allocation functions

Posted: Tue Nov 24, 2009 4:07 am
by xixpsychoxix
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.

Re: memory allocation functions

Posted: Fri Dec 04, 2009 9:20 pm
by Mike
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.

Re: memory allocation functions

Posted: Tue Feb 16, 2010 3:57 am
by xixpsychoxix
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?

Re: memory allocation functions

Posted: Tue Feb 16, 2010 9:59 am
by Andyhhp
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

Re: memory allocation functions

Posted: Tue Feb 16, 2010 6:22 pm
by xixpsychoxix
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?