Memory Management Idea

[AaronMiller]

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:

Code: Select all

struct sFreeItem
{
	void*		pAddress;
	u32		sizeInBytes;
	sFreeItem	*pPrev, *pNext;
};

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:

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;
}

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

[dr_evil]

You're describing a regular memory allocator...

Here are some interesting links:
http://en.wikipedia.org/wiki/Malloc#Implementations
http://g.oswego.edu/dl/html/malloc.html


Some notes:
1. The allocator you described suffers from fragmentation as well. See what happens when I request 1MB, 1KB, 1MB, 1KB, 1MB, 1KB, 1MB, 1KB in this order on a 5MB system. Then free all 1MB-blocks. And now let's allocate 4MB. This doesn't work because the 1KB blocks are scattered over the whole address space.

2. Freeing all memory of a "killed" process is a very good idea. All modern OS I know of do this.

3. A programm allocating and deallocating small amounts of memory may degrade the performance of your allocator. Since you need to look trough the list for a block big enough to satisfy the users request your algorithm will be slower than neccessary.



But at the end of the day all of this doesn't matter. Just write a stable, reliable allocator. You can improve it later on.

[JamesM]

dr_evil is correct - what you are describing is essentially dlmalloc (Doug Lea's malloc - dr_evil posted a link).

One thing that dlmalloc has that you do not is tagging of memory. Instead of having a seperate list to walk, each list item is stored at the address it references, e.g. user asks for 80 bytes, you allocate 80bytes + sizeof(list_item). Put your list item at the place that you just allocated and return to the user that address + sizeof(list_item). Then, when freeing, you don't have to walk a list, you just have to look at the address you are given to free by the user - sizeof(list_item) to find your information structure.

I've written a tutorial-style implementation of this myself here, if it's useful.

Cheers,

James

[iammisc]

While I was reading your description of you "new" idea I realized that it was similar to my idea. And then, I looked at my code and realized that you're describing exactly the same thing. However, your idea has no means of actually freeing a block. When a program calls the "free" function how will your memory allocator know exactly how much was allocated? For this, I use a structure 16 bytes before the actual pointer to hold that free info. So malloc actually allocates the memory needed + 16 bytes and returns the pointer to the 16 byte offset into the region.

[AaronMiller]

Okay, I see.

@iammisc
Actually, I said there would be a list of used items per process, that list of used items would contain information about the size that was allocated and such.

@JamesM
Oh that's ironic, I actually just downloaded all thus tutorials you made the other day, haven't had time to look at 'em all yet (I came up with this idea before downloading 'em).

@dr_evil
Ah, well I thought it was original, lol. Well, thank you.


Thanks all, I appreciate the feed back.

Cheers,

-naota