How do you write a memory manager

[earlz]

I basically have no idea how to write a memory manager
I cant use a bitmap to store if the byte is in use or not because it takes over 500mb so i dont know how to do it

[kataklinger]

http://www.osdever.net/tutorials/memory1.php?the_id=44
http://www.osdever.net/tutorials/memory2.php?the_id=45

[matthias]

Though a bitmap is an option.. you don't need 500 mb..

To calculate the number of pages:

TotalMem (in kilobyte)

Code: Select all

totalPages = (TotalMem * 1024) / 4096;

example with 524288 kb of memory (512 mb):

Code: Select all

TotalPages = (524288 * 1024) / 4096 = 131072 pages..

in a bitmap every bit represents a page..
so you need a space of (131072 / 32) * 4 = 16384 bytes
=> so you need 16 kb of space to store your bitmap not 500

a dword is 32-bits.. so it can hold 32 pages.. a dword is also 4 bytes.. so you need only 4096 dwords in total to hold your bitmap => 16 kb

The only thing left is code to set bits and zero them

The rest is easy

I'll provide some example code:

Code: Select all

dword bit_pattern[] = 
{ 
	0x00000008, 0x00000004, 0x00000002, 0x00000001, 
	0x00000080, 0x00000040, 0x00000020, 0x00000010,  
	0x00000800, 0x00000400, 0x00000200, 0x00000100,  
	0x00008000, 0x00004000, 0x00002000, 0x00001000,    
	0x00080000, 0x00040000, 0x00020000, 0x00010000, 
	0x00800000, 0x00400000, 0x00200000, 0x00100000,      
	0x08000000, 0x04000000, 0x02000000, 0x01000000, 
	0x80000000, 0x40000000, 0x20000000, 0x10000000,
};

// indices range from 0 to 31 !!!! :)

void clear_bit(dword* field, dword index)
{
	*field = ((*field) & (~bit_pattern[index]));
}

void set_bit(dword* field, dword index)
{
	*field = ((*field) | (bit_pattern[index]));
}

dword is_bit_set(dword field, dword index)
{
	if((field | (~bit_pattern[index])) == ~bit_pattern[index])
	{
		return 0;
	}

	return 1;
}

Don't ask me how it works I made it someday.. but how I don't know :P The efficiency I think is very low as well.. anyways.. It works

[earlz]

but how would you do something like malloc(50) so if i only wanted 50 bytes instead of a page

edit:
those links you gave me didnt really help

[deadmutex]

It is also possible to use a stack of available page addresses. When you need a page, all you have to do is pop one off. Freeing a page is also simple: just push an address back onto the stack.

The bad thing about stacks is that they take up more space than the bitmap (128K vs. 16K, if you use 4K pages). Also, it is very easy to corrupt the manager if you free an already free page. You could check the stack to see if page is valid, but that would defeat the purpose of using a stack in the first place...

[deadmutex]

You would have to keep a list of allocated memory block and heap size information somewhere. The allocation data contains information about an allocated block, such as: size, status(used or free), and the location of the next block on the heap. If you wanted to allocate memory, you would extend the heap size, set the block as used and add allocation data to the list.

If you wanted to free memory, all you have to do is mark the block as free in the list. The problem here however, is that after you free memory blocks, you may have a list of small blocks that will need to be compacted.

*Note that this is only one way of storing allocation data.

Visit: http://www.bridgeport.edu/sed/projects/ ... memory.htm
and http://gee.cs.oswego.edu/dl/html/malloc.html
for more info on different techniques

[matthias]

but how would you do something like malloc(50) so if i only wanted 50 bytes instead of a page

edit:
those links you gave me didnt really help

Ok, you want to write a malloc() sort of stuff... Well I thought you wanted to write a manager What you want is an allocator.. a manager also handles stuff like paging and stuff.. first build a manager.. paging, virtual address space.. etc. etc.. Then build an allocator.. Otherwise your OS will turn out to be ****.. Believe me.. Once I was a cut&paste guy.. but nothing is better than a good written OS.. You must not want to do the fun stuff directly.. you must handle the hard part first before you can write something fun like an allocator.. I'm not critisizing you.. but imho you still have to do a lot of stuff.. Start with a good core of your OS.. then build things around it It is hard.. I know.. but the result is better than you would've expected Take this as an advice

So take a look at kataklinger's post again:

http://www.osdever.net/tutorials/memory1.php?the_id=44
http://www.osdever.net/tutorials/memory2.php?the_id=45

They helped me a lot

[Da_Maestro]

A good algorithm for an allocator is using a list of free blocks in memory.

I wrote an allocator which uses it's own allocation space to keep a linked list of free blocks. Quite nifty

[kataklinger]

@matthias: Me too!

[JAAman]

but how would you do something like malloc(50) so if i only wanted 50 bytes instead of a page

normally, your OS syscall will not handle this at all, rather this is done by the application itself (generally controlled by a library linked in containing the malloc function)

the malloc function is contained entirely within the application, the application then controlls small memory uses, and only if it doesn't have enough memory to satisfy the request, it will make a syscall to allocate another page from the OS, which will only allocate entire pages

[kataklinger]

Well kernel must handle malloc and free for kernel heap

[JAAman]

yes, but that should also be through a library (or not at all: my kernel design currently (not guaranteed to remain) calls for a kernel that never allocates anything less than one page at a time (i currently have had no need for anything more))

but most people do, and then it should be handled through a library (or a separate function, if you aren't writing your library yet), rather than within the allocator, which should never work with values smaller than a page (you physical manager will have to allocate full physical pages anyway)

[earlz]

ok so lemme get this straight
(i have a kernel library, so kmalloc would go there)
kmalloc makes a syscall for 1 page to be added to its address space and then it (i guess) keeps soem allocation data of rather a bitmap sayign which bytes are uin use or ranges of addresses in use

am i right?

edit:
this tut helped me a lot more
http://osdever.net/tutorials/cottontailmm.php?the_id=47

[JAAman]

actually i think most 'malloc' implementations place a data structure at the begining of a block of memory containing the length of the block, then it passes this block to the application, if the application 'free's a block, it checks the bytes before the pointer for the length and looks to see if the block before or after is also free (combining them if they are), then adds a pointer to the block to its 'free list'
next time the application calls malloc, it allocates an existing block if there is one large enough (and splits it to not waste space), if not then it makes another syscall to retrieve another page (or more -- at least enough to satisfy the request)

sometimes, when free is called, it will realize it has a lot of contigious free space (more than is likely to be needed) and it calls the 'free' syscall (which will de-allocate an entire page)


ps. not familier with that tut, but it appears to be more about the syscall allocator

[earlz]

yes but so was those other 2; the second part said something like "i will not go into how to code a malloc" which it didnt so those didnt help

now then back on topic
yes but how would you keep a list of what bytes of a block are in use and which are free
that is most of the problem i have