Need memory management Tutorials/explained code - 2005/04/20 11:37Hi,
I'm trying to make a memory management for my OS, but I need a good tutorial on doing this. I'm quite unsure how to get from physical memory management to virtual and malloc-similar functions. There are some tutorials on the net, but they are very few, somehow incompleted and they don't show the code. I know this sounds dummy, but I don't know how to start. Please give me an advice!
| | The administrator has disabled public write access.
OSDEV Community
Advertisement
gaf
User Platinum Osdever
Posts: 153
Karma: 10
Re: Need memory management Tutorials/explained code - 2005/04/21 09:34Well, memory managemant is a huge chapter.. If you're new to it, you should probably start by implementing some basic paging. A small tutoial can be found on bonafide os dev and the megatokyo wiki also contains some infos about it. I hope that this will be enought to get started..
regards, gaf
| | The administrator has disabled public write access.
anonymous
Visitor Fresh Osdever
Posts: 0
Karma: 0
Re: Need memory management Tutorials/explained code - 2005/04/30 12:22Thanks, I started by implementing a simple memory manager which returns pointers to 4kb pages of memory and frees them on request. Now I need something more sophisticated because 4kb is too much for linked lists and similar stuff. I can't find tutorials on implementing malloc/free-like functions and I don't have an idea on how to do this. Any help?
| | The administrator has disabled public write access.
gaf
User Platinum Osdever
Posts: 153
Karma: 10
Re: Need memory management Tutorials/explained code - 2005/05/01 16:30Memory management is done in a (more or less) different way in every operating system. It's a question of your design and thus I can't give you a definite answer.. Here's my idea of how to do it but I'd advice you to have a look at several other opinions before actually deciding on anything (Os Journal, cottontail memory management at bonafide once the site is up again):
Allocation of memory is done on two levels: - kernel 4kb - user-space byte granularity
The kernel manager is probably not much unlike the one you've already written. It only allows to allocate/free 4kb pages of memory and uses either a bitmap or a linked list to keep track of which memory is in use and which is free.
These very simple allocation/delocation methodes are all that the kernel provides. Applications can now either use these 4kb pages directly (which is not very comfortable) or make use of a user-space manager (->library) that divides the pages into smaller units for them. You may now argue that it'd be a better idea to include this manager (with byte granularity) in the kernel, but in fact there's no advantage doing so because paging protection only works on a 4kb level. This means that when a 4kb page is split into several parts these parts can't be used by different processes, because each process would be able to write to the entire page, although it only owns a portion of it. If a page is devided into multiple parts there are therefore only two options: a) The same process that already has the first part requestes the rest b) The rest remains unused As you can see it really doesn't matter from the OS's point of view because no other process is involved.
The big advantage of doing byte-granularity allocations in user-space is that the application may use an policy of its choice in order to get the best performance (e.g database vs. word processor).
Code:
I can't find tutorials on implementing malloc/free-like functions and I don't have an idea on how to do this.
A simple implementation might work as following:
Allocation: (X = bytes are requested by the app)
- check if we have a block of at least x free bytes (C) in our local list
- if so, take these bytes and update the list:
-> DelList(addressC, c, free)
-> AddList(addressX, x used)
-> AddList(addressR, remainer of the block, free)
- if not: round up to the next page boundry (multiple of 4kb) and allocate the memory from the kernel
- give x bytes to the app and update the local list:
-> AddList(addressX, x, used)
-> AddList(addressX+x, 4096-x, free)
Delocation: (X = pointer to the memory area that is supposed to be delocated)
- if the chunk is bigger than 4kb, free all 4kb blocks
- remove the remaining bytes (R) from the local list
-> DelList(addressR, r, used)
-> AddList(addressR, r, free)
- check if we just freed the last part of a page
- if so, free this page aswell and remove it from the local list
regards,
gaf
| | The administrator has disabled public write access.
MrKaktus
User Junior Osdever
Posts: 12
Karma: 1
Re: Need memory management Tutorials/explained code - 2006/03/24 07:14Hmm but if you allocated first for example 6KB block (2 pages) and after that another block (10bytes -> goest to that second page). When you will want to dealocate 6kb block it will kill that 10bytes long (because it will "free all 4kb blocks"). If I'm understanding that method correct, deallocation algorithm is not correct.
I have also question, do you have byte granularity in your kernel space (DPL0) ?
| | The administrator has disabled public write access.
gaf
User Platinum Osdever
Posts: 153
Karma: 10
Re: Need memory management Tutorials/explained code - 2006/03/25 10:44Hello MrKaktus, Let me see.. What I described in my post is a very simple byte-granularity allocator based on a 4kb kernel memory manager. It uses the list approach with only a single list for both, free and used entries, but it would of course also be possible to use two seperate lists, which might increase performance a little bit.
Code:
struct node
{
void* base_address; // Base address of the memory chunk
uint size_chunk; // Size of the chunk in bytes
bool used; // true = chunk is used, false = chunk is free
};
To allocate memory one would first walk trough the list to find a free chunk that is big enough. Once an entry that can be used is found, it is taken from the list and divided into two new entries: One that describes the just allocated memory (old_base, size_alloc, true) and a second that holds the remaining memory (old_base + size_alloc, size_chunk - size_alloc, false) if there's any.
In case that there's no free node on the list, or if they're all too small, we first have ask the kernel for some new 4kb pages. These memory is now taken from these just allocated pages and just like in the first case two new entries are added to the list: One that describes the just allocated area and a second one that describes the remaining memory.
When delocating a chunk the memory manager first has to locate its entry in the list. If the chunk is greater than 4kb all pages it used exclusivly/completly are returned to the kernel. The remainer (chunk_size % 4096 = 0) is still on the list and gets marked as free so that it can be used for further allocations:
Code:
while(node.size_chunk % 4096)
{
FreePage(base_address); // Returns 4kb page to the kernel
if(node.size_chunk == 0)
{
list.RemoveNode(node);
}
else
{
node.used = false; // Mark the entry as unused
CleanList(list); // Marges enties with same borders
}
CleanList(..) keeps the list clean by merging entries that have the same borders and are either both 'used' or both 'unused':
Code:
{base = 0x100, size = 0x050; used = false}
+ {base = 0x150, size = 0x050; used = false}
= {base = 0x100, size = 0x100; used = false}
allocate(6kb) : list still empty -> q = AllocatePage(8kb) // kernel..
CreateEntry(q, 6kb, true) // Add used area to the list
CreateEntry(q+6kb, 8kb-6kb, false) // Remaing free space
return q
allocate(10byte) : free node on the list (q+6kb(b), 8kb-6kb(s), false)
CreateEntry(b, 10byte, true) // Allocated memory
CreateEntry(b + 10byte, (s) - 10bytes, false) // Remaining memory
return b
delocate(q): Greater than 4kb -> Free complete pages first
FreePage(q) // Returns the first 4kb
RemoveEntry(q) // Remove the old entry
CreateEntry(q+4kb, 2kb, false) // Remaining memory that can't be freed
Once the 10byte block gets delocated, the list can combine all three entries and return the second page.
I have also question, do you have byte granularity in your kernel space (DPL0) ? Nope, at least not a generic byte-granularity allocator. I however plan to include a highly specialized memory manager that allows the allocation of memory for new list entries. Apart from pagetables, which are 4kb anyway, they are the only data structures that have to allocated at run-time with my design.
regards,
gaf
| | The administrator has disabled public write access.
root
Moderator Moderator
Posts: 121
Karma: 1
Re: Need memory management Tutorials/explained cod - 2006/03/28 01:06Hi,
These messages were posted on the old site after we migrated the threads so I added them here:
MrKaktus:
"Apart from pagetables, which are 4kb anyway, they are the only data structures that have to allocated at run-time with my design."
And what with Task State Blocks ? Are they 4kb in your OS too?
gaf
Not quite - that's why I'll too store them in a list. Basically I'm planning to intermingle my list implementation with a specialized memory manager. The list will be based on a 4kb page allocator and thus too grows and shrinks with this granularity. That means that it can allocate a new 4kb block when it runs out of memory or free one of its block if several nodes have been deleted. Each of the blocks is divided into x list nodes:
The list-nodes {x} are on either of the two internally managed lists - free or used. If a new list-node is needed, all that has to be done is to moves one the nodes from the free list to the used list. If a list-node gets freed its moved from the used list to the free list. As there's only one allocation size, which is the size of the node structure, the whole process is very simple and can be implemented much faster than a generic allocator. The downside is that the allocator can only be used for data structures that are stored on lists, and that the rather local allocation policy might lead to some wasted memory (even the smallest list uses at least 4kb of memory). The latter point however becomes less and less important once the list exceeds a certain size.
regards, gaf
MrKaktus
For a while I have also 4kb granularity allocator written for my Kernel space. And I think that it will be ok because I'm writing microkernel . And for process wirtual memory I am writing 1B granularity allocator. I have list that describes all blocks each one after another, with flag free/clear. They are in dynamic list in such order like they are in memoy. That dynamic list is supported by 4kb boundary blocks that are connected in list .
I have question now: You are using two separated lists, so blocks are not segregated, how looks connecting of 2 or 3 free blocks that are one after another ? You have system process that is searching for connections in free block list ?
gaf
Not quite sure if I really understood your question..
There is no connection between list-nodes that are located next to each other. That means that two nodes will always be stored as two entries on either of the lists. As the allocation size is always the same as the block size, there's actually no point in trying to merge the entries. After all they would have to be aplit into smaller units again before the actual memory can be returned.. The whole purpose of the used and free lists is to provide me with a simple mean of getting a free node or recycling a node that is no longer used. Conceptually you could replace it with two stacks, one that contains the addresses used items and a second that consists of free list-nodes.
regards, gaf
MrKaktus
Ahh so that inodes describes just 4kb free or allocated blocks :> or blocks of smaller size but all with thesame size (eg. 8bytes) ? [now I'm not sure about what we are talking - that inodes structure is to provide 1B granularity allocation?]
Post edited by: root, at: 2006/03/28 02:12
| | The administrator has disabled public write access.
MrKaktus
User Junior Osdever
Posts: 12
Karma: 1
Re: Need memory management Tutorials/explained cod - 2006/03/28 07:19Ok, I read once again your posts and now I understand everything. That 4KB granularity list provides supporting normal list with S-size entries in it that you are calling NODES? I was thinking that NODEs are entries in the list that are describing free or used blocks of mem, so I mistake it with 1B granularity allocator .
| | The administrator has disabled public write access.
Forums 
so I added them here:
.
.