OSDev.org

The Place to Start for Operating System Developers
It is currently Wed Dec 13, 2017 12:30 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Memory Management
PostPosted: Thu Jun 26, 2003 11:22 am 
I was wondering how I could implement a defrager for my MM table. The table takes the form of:-

typedef struct
{
void *start;
unsigned long length;
short owner;
}memory_t;

Where owner = -2 for free and all other values indicate the owner task. What I need is a quick function to consolidate consecutive small areas into a larger area. If this was done after every free you would only have to check if the freed area was consecutive with any others but any code that I've come up with has been toooooo slow. Currently my code works as well as complicated MM yet being less than 100 lines of code (something must be wrong) I've attached the mm in case you want a closer look.

Any ideas?

Thanks in advance

Pete

[attachment deleted by admin]


Top
  
 
 Post subject: Re:Memory Management
PostPosted: Thu Jun 26, 2003 12:24 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
just a question you should ask yourself ...
your MM's clients have received pointers and store them everywhere in their other structures, etc. How will you defrag while ensuring pointers consistency ?

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Memory Management
PostPosted: Thu Jun 26, 2003 12:57 pm 
Do you mean defrag by moving allocated memory around to make larger chunks of free memory? Or do you just mean consolidation, where two chunks of free memory that are consecutive are replaced with one chunk of free memory that spans the two?

Because you have to worry about what Pype said if you're talking about moving around allocated memory. Otherwise, you should be able to write a relatively simple, straightforward algorithm that checks when an allocation is freed if there is a free one immediately after it. Checking before it becomes more difficult since you dont know how long it would be, but I'm sure you can find something online about this. Look up something like "memory allocation algorithms" on google and you should get lots of info.

Unfortunately, my mem man. right now is far from optimized, and that's something I have on my list to look into. So if you find out anything really good, leave a note here... :)


Top
  
 
 Post subject: Re:Memory Management
PostPosted: Thu Jun 26, 2003 2:04 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 2:31 am
Posts: 5959
Location: In a galaxy, far, far away
from the code, it appear that he's only trying to merge contiguous free zones in one larger zone. Note that first fit algorithms are not especially complicated. What can make them more complex is the need for faster or more deterministic behaviour, plus some extra features like being able to allocate memory that will have alignment constraint, or deal with paged memory.

For a reasonably fast algorithm, my approach was to split the memory into boxes of 64K. Each box keep track of the largest zone it holds, so if you need a zone of N, first look for a box that can offer it, then allocate in the box.

Unfortunately, when N>>64K, sweeping the box list becomes a nuisance, so we could try to extend the algorithm with boxes of boxes, etc. in a tree-fashionned datastructure.

_________________
Image May the source be with you.


Top
 Profile  
 
 Post subject: Re:Memory Management
PostPosted: Fri Jun 27, 2003 10:34 am 
Pype.Clicker wrote:
just a question you should ask yourself ...
your MM's clients have received pointers and store them everywhere in their other structures, etc. How will you defrag while ensuring pointers consistency ?


I'm not changing pointers just organizing the table.

eg.

There is free mem between 0x100000 and 0x200000. This is in the table as start=0x100000, length = 0x100000 and owner = -2. Then there are two requests for 0x80000 bytes. The table now has the entries:-

start = 0x100000
length = 0x80000
owner != -2

start = 0x180000
length = 0x80000
owner != -2

Now these are both freed leaving the same in the table except the owner now equals -2. Then if a request is made for 0x100000 bytes there is not a big enough segment to take the memory from although there is 0x100000 bytes of mem free. What I need is a fast bit of code that will, when the second chunk is freed, join it back into the original single block so that a request for larger ammounts of memory won't fail.

Pete


Top
  
 
 Post subject: Re:Memory Management
PostPosted: Fri Jun 27, 2003 10:44 am 
I found some useful information at http://gee.cs.oswego.edu/dl/html/malloc.html on some of the ideas of memory allocation and subsequent coalsceing. Basically, you keep enough information at the head and tail of a free block of memory to describe how long it is and that it's free, and then you can look immediately before a block you are freeing and immediately after it and see if there are free blocks on either side and, if there are, joining them into one larger block (by simply removing the old smaller block from your list of free memory, changing its size to reflect the combined size of the two chunks, and adding it back to the free mem list). This is a simple algorithm, that is also fast and works well at reducing simple free space fragmentation.


Top
  
 
 Post subject: Re:Memory Management
PostPosted: Fri Jun 27, 2003 2:17 pm 
Problem Solved!

I'm not sure what the problem was because when I recoded something similar to what didn't work it worked. The code is barely 15 lines long and works sweetly :-)


Top
  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot], Google [Bot], Yahoo [Bot] and 22 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group