Virtual Memory Question [HEAP/malloc/free]

[Tutul]

Hi there

I'm actually working on a virtual memory allocator and I would like to read your opinion on it. It's only a firt work and I'm not sure if it can be efficient enough and fast enough but, again, it's a first work.

You can find a graphical explanation down here ^^

- Each block is a header with random space
- Each header contain size and un bool (free or not)
- Each block is fully adjacent
- To find the next block you only need to add size + sizeof(header) to the pointer value
- The heap is initialized with a unique free block
- When you want to use a block, you find the first free block big enough, split it if needed, mark a part as used and the other as free, and return the address after the header
- When you want to free a block, you find it, mark it as free and see both adjacent if they are free for merge or not
- When no more free block can be found, we just ask PA to give use an other page if availbable

I'm think the biggest problem is the operation to find the next one and maybe the internal fragmentation.

What do you think ? Love to learn ^^

[MichaelFarthing]

With time I think this system would degrade quite badly with you finishing up with a lot of small disconnected blocks that would rarely be assigned.

Remember that you can use the free space in each free block for additional information - for example you could use the start of each free unallocated block to maintain a linked list of all the free blocks of a particular size, the start entry of each linked list being held in a relatively small array (a block in its own right). This will frequently avoid the need to split oversize blocks and also reduces the time needed to find a potential candidate block. If a block of the exact required size is not available then you would need to fall back on your splitting idea but because you can easily pick the size of block to split there is room for a fairly efficient alogorithm to make good choices about this - for example, if a block of size n is not available then splitting a block of size (2n+header length) gives you your required block and also populates the size n list for next time it might be asked for.

[Also note that the linked lists never need to be traversed, because both allocations and deallocations can be made at the start of the list very efficiently]

[~]

See this link, they are the same answers for what you are asking:
http://forum.osdev.org/viewtopic.php?t=32702

[Tutul]

I saw that topic but my idea is to know the best and the worst of my idea. I want my heap to be used for very small allocation like an small array of char, or very big like a big struct that need to be created.
Yea it will probably get that worst case. But if I use the free space to retain informations, free space must be with a minimal size.

[zaval]

if this is about pool allocations and you "love to learn", then throw this away and go read the Knuth's dynamic memory allocation chapter.
The (almost) first-fit algorithm with tagged at both ends blocks with the rover pointer are what you need. It learns quickly, it's reasonably fast, and it doesn't waste as much space as buddy allocation.

This is exactly what I've done for pool (and page) allocations in my UEFI project.

[Tutul]

I see that the only change I must code is the roving pointer. I'm already close to that algorithm (at least for the simple version).

[zaval]

I see that the only change I must code is the roving pointer. I'm already close to that algorithm (at least for the simple version).

sorry, it was not clear what blocks are in the list. only free blocks should be in it.

[Tutul]

Actually I don't have any list, just jumping from one address to an other. But I already begin a version with a pointer in the header. So I just to update it to be a free block_header extention with that pointer and skip the used block.

[zaval]

Actually I don't have any list, just jumping from one address to an other. But I already begin a version with a pointer in the header. So I just to update it to be a free block_header extention with that pointer and skip the used block.

that approach sucks honestly. you need a doubly linked list with a special pseudo-block elsewhere (list head). don't forget about boundary conditions (on addresses before and after your alloc region) are satisfied, the head is initialized. that's why I told you read that chapter. it's easy in fact.
sorry, how do you merge blocks with this approach? it all will get fragmented AF quickly. You need "size" and "tag" field in the end of block too. walking through the list is faster than walking through the whole blocks.

and of course for the OS whose session (uptime) could last years and number of blocks is going to be huge, it's better to use something more sophisticated than lists. like balanced binary trees.

[Tutul]

sorry, how do you merge blocks with this approach?

Quite easy, I can get the previous and next address and check free bool:
current + next => update current size with next->size + header size
previous + current => update previous size with current->size + header size

[zaval]

emmm. your client's Free() functions calls:
Free(AddrToFree);

AddrToFree is an address of the block to free. What's "previous" and "next" here when you say you don't have any list?
You would need to start from the beginning of the alloc region just to find the "previous" adjacent block. Instead, you might have a tag and size field at the end of each block, so figuring out the status and address of the previous adjacent block is a constant operation.
By the way "previous" and "next" in the sense of adjacency is not the same as in the list.

[Tutul]

I'm agree with the chained list of free block. For the second header, I'll do some reading and experiment about space usage vs fast process

Thanks you anyway ^^