Memory Management Idea
Posted: Mon Jun 23, 2008 4:03 pm
Title: New Heap Method Idea
Hullo, I have what I believe to be a new method for dynamic memory allocation, that seems to be efficient against fragmentation of memory (Or what I consider memory fragmentation, that is), and performance. I was just wondering what you all think of it, and your thoughts, suggestions, and criticisms.
Basically, there's a list of unused (free) space. Each item in the list would look something like the pseudo code below:
When memory is required to be allocated (dynamically, of course), the kernel will go through the list, and search for the first item which can hold the amount of memory allocated, if an item is found it will be "split." For example, say the user wants to allocate 0x200 bytes, and the first item it comes across says there are 0x800 bytes free at address, say, 0x300000 (freeItem->pAddress = 0x300000, freeItem->sizeInBytes = 0x800). The memory manager would then split that item, in a fashion similar to this pseudo code:
When memory is deallocated, the kernel will create a new item, and try to merge it with an existing item in the list. For example, say two items were allocated, one from 0x100000, and the other at 0x100200, lets say the first one (at 0x100000) used up 0x200 bytes, and the second (0x100200) used up X amount of bytes. Now, if the first item or second item is freed, and later on the other item is freed, they would be merged into one item because they FIT with each other.
The item would always have its items sorted from lowest memory address available, to the highest memory address available, in that order. Initialy, there would be ONE item in the list, from the starting address of free memory, to the ending address of free memory. Those values would be dependant on the OS which uses it, perhaps even the kernel if it allocates its memory differently (Which it probably would, mainly).
This is how multiple items would be created. Lets pretend that there are 3 calls to allocate some memory, the 1st call returns an address at 0x200000, the 2nd call returns an address at 0x200100, and the 3rd call at 0x200200. Lets say that the 1st allocated memory (at 0x200000) is freed, right there an additional item would have to be created because the free memory doesn't "fit" with the existing chunk of free memory (The size of memory returned to the memory manager plus the base address of that memory would not equal the base address of the existing free memory). In that case, there would now, theoretically, be two free memory items that would have to be searched through to find the next chunk of free memory, provided the memory requested was larger than the first chunk of memory. Again, once all the other memory is freed, there would be, once again, one item (Or, a lower number of items, lol).
Each process would have its own list of allocated memory. When the process is terminated, all of its allocated memory is unallocated. Also, an "is_mem_valid" routine could be written which checks the process' list of allocated memory to check if a specific address is valid, and when memory is freed, it would be removed from the process. That list would be sorted in the same way the free list is, meaning from lowest address to highest address. However, there would be no merging of the used list, as that could cause problems during calls to "free" lol.
Anyways, its just an idea I had, perhaps its already in use, perhaps theres good reason for it not to be used. I'm interested to know everyone's opinions on it though.
Cheers,
-naota
Hullo, I have what I believe to be a new method for dynamic memory allocation, that seems to be efficient against fragmentation of memory (Or what I consider memory fragmentation, that is), and performance. I was just wondering what you all think of it, and your thoughts, suggestions, and criticisms.
Basically, there's a list of unused (free) space. Each item in the list would look something like the pseudo code below:
Code: Select all
struct sFreeItem
{
void* pAddress;
u32 sizeInBytes;
sFreeItem *pPrev, *pNext;
};
Code: Select all
void* split_item(sFreeItem* pItem, u32 size)
{
// Preliminary
void* pAddr = (void*)0;
if (pItem->sizeInBytes > size)
{
// Prepare the address
pAddr = pItem->pAddress;
// Increment the address
pItem->pAddress += size;
// Decrement the free amount of space in the item
pItem->sizeInBytes -= size;
}
else if (pItem->sizeInBytes == size)
{
// Prepare the address
pAddr = pItem->pAddress;
// The item can't sacrifice any more space, remove it
mm_remove_item(pItem);
}
// Return the address of the memory item
return pAddr;
}
The item would always have its items sorted from lowest memory address available, to the highest memory address available, in that order. Initialy, there would be ONE item in the list, from the starting address of free memory, to the ending address of free memory. Those values would be dependant on the OS which uses it, perhaps even the kernel if it allocates its memory differently (Which it probably would, mainly).
This is how multiple items would be created. Lets pretend that there are 3 calls to allocate some memory, the 1st call returns an address at 0x200000, the 2nd call returns an address at 0x200100, and the 3rd call at 0x200200. Lets say that the 1st allocated memory (at 0x200000) is freed, right there an additional item would have to be created because the free memory doesn't "fit" with the existing chunk of free memory (The size of memory returned to the memory manager plus the base address of that memory would not equal the base address of the existing free memory). In that case, there would now, theoretically, be two free memory items that would have to be searched through to find the next chunk of free memory, provided the memory requested was larger than the first chunk of memory. Again, once all the other memory is freed, there would be, once again, one item (Or, a lower number of items, lol).
Each process would have its own list of allocated memory. When the process is terminated, all of its allocated memory is unallocated. Also, an "is_mem_valid" routine could be written which checks the process' list of allocated memory to check if a specific address is valid, and when memory is freed, it would be removed from the process. That list would be sorted in the same way the free list is, meaning from lowest address to highest address. However, there would be no merging of the used list, as that could cause problems during calls to "free" lol.
Anyways, its just an idea I had, perhaps its already in use, perhaps theres good reason for it not to be used. I'm interested to know everyone's opinions on it though.
Cheers,
-naota