OSDev.org

I am progressing very nicely in my OS project now. I have a good basic message passing system in place now, but I have got to do one thing I have avoided until now, that is freeing previously allocated memory.

Now, this in itself is not difficult, I am using a linked list of allocations and free space, so if I keep the list of free space in ascending address order, I can do free-space coalescing.

But, I thought does anybody know of any good easy to implement algoriths that produce good performance but are not too complex too implement. A quick google search brings a few up, but has anybody on here got any good experience with any algorithms?

hi,
if you are using a linked list to manage free space then the fastest possible way to do this would be to find a quick way to update the pointers in the list ie use as little amount of code as possible first in c and then (if possible, i haven't tried linked lists in asm before) recode it in asm!

Well, the size of the free space/allocation structs are exactly the same structure and size so I can convert a allocation into a free space very quickly.

*But* I have to parse the who linked list working at the most recently allocated first and going back to the first. Also I am going to loop through the free space list to place the free space allocation next to each other for coalescing.

*But* my could end up having to loop through thousands of allocations trying to find the right one.

I thought about a binary tree, but that sounds a little bit much for the moment!!

Why do you have to do a search to find the block information structure?

What kind of allocator are you making?
a) Something like malloc, which stores allocation information just before each user block?
b) Something with the allocation structures separate?

If (a), then there's no need to do any searching unless you start coalescing free blocks (even then, you can save time by keeping adjacent blocks next to each other in a linked list).

If (b), then you can cut down your search time drastically by using a tree instead of a linked list.

Basically the malloc structure, where I have the allocation (or free) structure immediately before the memory segment allocated (or free). I am starting to doubt the wisdom of this and might switch to having a contigous block of memory for the structures, if only to simplify the code ( I have to use a few + sizeof(struct) etc in the allocation code)

Basically, because my object manager works similar, its a linked list of objects which are used to store just about everything in my kernel except memory allocations. Its a very nice way of working from a kernel design point of view because everything in the system becomes an object with searching/deletion etc. code shared among all different sub-systems. I worry though that perform will start to become heavily impacted if the system grows to a point where ten's of thousands of objects are in the list (quite probable because I use the same object manager mechanism to store what I call entity objects, which is a database of keys and values, similar to windows registry or active directory). I was toying with a system of indexing (I have a database background) but that will have its own problems.

How have others done this?

Thanks.

hi,
don't know if this can help but this is how i did my memory management.
The kernel allocates blocks of physical memory of any size that is requested (have to add 32 bit aligning code ??? or fix the blocks to 4k, will help when i implement paging ;D )
It places a 16byte struct before the address returned to the caller and adds this struct to the linked list of allocated physical memory. the struct contains pointers for the list, the block size and owner etc. this is the easy part!
the hard part (which i'm not sure i have fully debugged :-\) is my deallocation which i wanted to automatically merge adjacent free blocks.

The kernel starts with an empty allocated list (except for memory dedicated to the kernel) and a full free list (this is a single struct specifying the start address,length of free memory,owner as kernel,etc)
when some size of memory is allocated, I
1. subtract the size of new block +16bytes (for the struct before the returned memory address) from the size of the free memory list (that is the single free memory struct)
2. add size of new block + 16 bytes to the start address of the free memory to get the new start address of free memory
3.insert this new block's info struct in the list of allocated blocks (just an append to the end of the list)
4. return new blocks struct address + 16 bytes to caller(struct is 16 bytes before actual memory to be given to caller)

now for deallocating, :'(
I tried sorting the blocks as they are deallocated and inserted into the free list. During the insert operation, I compare base addresses of the previous block with the one to be inserted if the address of the new block is

1. less than that of the previous one, I change the address of the previous block to that of the new one and also increase the size of the previous block by adding the size of the new block +16 bytes to the previous block's size, effectively joining them together ;D

2. greater than that of the previous one, I check that the new block is adjacent to the previous one. I do this by adding the previous blocks address to its size and compare it to the new block's struct address. if they match then they are adjacent and i just merge the blocks by only changing the size of the previous block as in 1.
But if they are not the same, then i insert the new block as a seperate block in the sorted list.

that's how i've done mine. hope it sparks ideas for you
also I welcome any ideas on improving this scheme!
thanks

Code Slasher,

That is pretty much identical to what I am doing, the difference with mine is that I intend to have different lists in different areas of memory for kernel and user processes so I don't have an owner flag.

Thing is, as you know, it can be a nightmare to debug, I keep having to dump all the current allocations and manually check everything lines up!!

Daryl.

hi,
i wrote my memory code and debugged it in my OS gradually. This is what i did
I created 2 functions that print out the structs in both the free and allocated list
I then just allocated some block ( 2 to 3) of various sizes and called debug free list function first, halted the cpu to examine the output (no fs had to use screen)
I then changed the call from debug free list to debug allocated list. This prints the allocated block list, this includes the addresses of each block and size etc.
After being satisfied with the values returned (took many iterations of proces stated above ::)) I then considered the allocation functions to be fine ;D (no problems have occurred since been about 5 months of constant use )

Repeating the same process with the deallocation function, I allocated some blocks(I've check the validity of its opperation) and then systematically deallocated them one at a time in various order. In between each deallocation, I called debug free list to see that the combining algorithm worked as expected (as i was typing my first reply above, i improved it ;D so have to go home and change my deallocation function ;D).
this is how i debugged my memory manager, in fact all my system functions are debugged in a similar way!
hope this helps.

I can only assume there is only so many ways of coding, because I use the exact same debugging method as you too!

As you say, without a file system, its impossible to save to a file and debug the output.

Actually in the last hour, I have improved my allocation routine by dropping the size of my alloc struct to 8 bytes, a size variable and a pointer to the next allocation.

Its amazing how many of the same techniques are used in different OS's, I was looking at Pype's clicker earlier and noticed we had both done a lot of thngs very similar, although clicker is much further along than my OS attempt !

Daryl.

hi,
how are you going to determine if a process has the right to deallocate a block of memory if you don't record which blocks belong to which process?

Essentially, processes will not allocate memory from the kernel, rather have thier own personal allocation area in the user area < 0x80000000. This is for arbitrary sized blocks (i.e. malloc implementation), note that a user process will use the same allocation routines, but have thier own allocator struct which defines where the memory is and what the access priviliges are.

This is different from the procedure I will use for issuing whole pages of memory to the user process. In fact the memory allocator works on top of this.

I have never been very good at describing what I mean?!!

I was about to give some suggestions, but I remembered that I had already written anything useful in my tutorials.

http://osdev.berlios.de/memory1.html and http://osdev.berlios.de/memory2.html.

Thanks Tim, some good suggestions in there. I have implemented most already but a couple made sense, especially the one about not allocating physical pages to the allocation region but instead marking the whole region I am using (256MB) as zero-fill and simply assigning pages as page faults occur, this will be a bit more efficient than my current method.

Daryl.