Heap Manager

[xfelix]

Spring Break! Now I can play with my OS
Does anyone know of an easy to an adapt Heap Manager.
Right now, I'm trying to adapt bget that came with the GeekOS distribution. Anyone know of one that I can just slap on to my OS?
Has anyone implemented there own Malloc from scratch?
If so, how easy is it to roll your own very simple Malloc (one that doesn't care about fragmentation)

[NickJohnson]

It depends on what kind of features you need the heap to have. If all you need are fixed size blocks, you can make a very simple (and fast) allocator by keeping free blocks in a singly linked list and expanding the heap by simply incrementing a pointer.

[xfelix]

I got this working. Further reading of the mass comments said to simply have #NDEBUG defined, and I decided to
ignore the GEEKOS preprocessives. basically now, all I need to do is implement my own memcpy and memset -_-
This would still be a good place to show off there own custom Heap Mangers

[xfelix]

It depends on what kind of features you need the heap to have. If all you need are fixed size blocks, you can make a very simple (and fast) allocator by keeping free blocks in a singly linked list and expanding the heap by simply incrementing a pointer.

hey thanks for the help, This could be an interesting side project to work on.
I would want to be able to allocate a variable user defined size.
I know that it grows up toward the stack and the space inbetween the heap and stack is called the break, which
is why the linux system call has the brk routine. But How do you get the beginning of the heap?

[NickJohnson]

The algorithm I use in my C library is a type of buddy allocator (although I haven't implemented it fully, because it does not merge free blocks): the allocator maintains both a binary tree of all blocks and an array of linked lists of free blocks, sorted by base 2 logarithm of size. Allocation comes from the linked lists until they are emptied, at which point larger blocks are split. Freeing goes exclusively into the linked lists, although with merging of free blocks, this would be more complicated. The tree is used to find the size of allocated blocks, and tree nodes are allocated by a separate fixed-size allocator private to the heap.

The relevant code is pretty short: https://github.com/nickbjohnson4224/flu ... b/malloc.c. Obviously, don't just copy this code, but feel free to use it to understand the mechanism in more detail.

You may also want to look at glibc's dlmalloc; its implementation is probably a lot less buggy than mine.

I know that it grows up toward the stack and the space inbetween the heap and stack is called the break, which
is why the linux system call has the brk routine. But How do you get the beginning of the heap?

brk() returns the base of the block of memory that was allocated by incrementing the break, so you would use that pointer as the beginning of the heap.

[Tosi]

I am implementing a simple heap. The algorithm probably has a name but I don't know what it is since I came up with most of it on my own. I think it might be similar to the heap described in JamesM's tutorials except more optimized for size.

The heap itself is initialized in a block of (preferably) contiguous memory and contains an index of pointers to free blocks of memory, sorted in order of ascending size. Each block has a header which has a special identifier, like 0xBAADC0DE which allows for a run-time check of pointers passed to free. The header also has the size of the block and flags which describe things such as whether it's free, etc. Using these structures, the algorithms go something like this:

Allocation
1) Look through the index and find the smallest size free block whose size is greater than or equal to the amount of memory requested.
2) If possible, split the block into two pieces; One holds memory exactly the size of what was requested and the other is what is left over.
3) Mark the block as in use and remove it from the index. Return the memory there.
4) If no free blocks of adequate size were found, try and merge subsequent free blocks. Then goto 1.
5) If the index limit would be reached by splitting a block, try and merge subsequent free blocks. Then goto 2.
6) If 5 and 6 fail, return NULL

Freeing
1) Subtract the size of a block header to get a pointer to the block.
2) Compare the identifier in the block to 0xBAADC0DE (or whatever you use). If it doesn't match, this isn't a valid block. Return.
3) Make sure the block isn't already free. If it is, return.
4) Mark the block as free and add it into the sorted index.
5) (Optional) Merge subsequent free blocks. This can speed up later allocations but slow down frees. Use this if you allocate a lot of memory and only free it rarely.

The pros of this approach is that it is easy to code and works reasonably well once the bugs are ironed out.
The cons are that it is slow and probably uses up much more memory than it should. Once I get it working I will probably consider adding other algorithms.

[xfelix]

How do you get the beginning of the heap without the brk() system call?
Should I use the base of the stack, and add the limit to it? Would this be the beginning of the heap?

[Tosi]

Two possible ways:
1) The heap header is stored in the memory it was initialized with. Then you just add the size of the heap to the base address and that will be the first block.
2) Store a pointer to the first block in the heap header.

I prefer 1 but 2 would work fine.