OSDev.org

I need some advice regarding the implementation of a virtual memory manager.

Currently, the kernel will initialize the kernel heap by calling morecore() to grab a page and pointing a endOfHeap pointer to it. When kmalloc() is called, the memory manager will increment the heap pointer by the number of bytes being allocated. If the allocation requires more pages, kmalloc will call morecore.

So far, it's working fine. But, now I want to implement kfree().

I've researched the matter and found several implementations - linked list, bitmap, stack, etc...

However, I'm confused about what I should do to keep track of free non contiguous bytes. It seems like a large overhead to maintain a bitmap to keep track of bytes. It's even more of an overhead to use a stack. Linked lists won't fit in bytes.

Am I approaching this all wrong?

Vince

Me, Im using a linked list to store the memory fragmentation arising from dealocating a block before the last block of memory allocated.
Before allocating a new block, my memanager search the list for the smallest "free" block large enough for the new allocation and mark it "allocated". On top of that I have an array of eight of theses blocks to store the fragmented memory. When there's need for more, I make sure the last memory block is not allocated, and allocate a new array of eight free blocks, pointed by the last free block in my previous array. It looks complicated, but it works and is simple, well, simpler than my previous attempt at a memory manager.

To answer your question, your better with a linked list, in my opinion, allocated with your heap, that you can deallocate with kfree

If you can wait 2 days, There'll be a tutorial on my website about it (I'll post the link). I've just finished debugging the sample code, but theres quite a bit of it so I'm not sure how long it'll take to write the tutorial itself.

JamesM wrote:If you can wait 2 days, There'll be a tutorial on my website about it (I'll post the link). I've just finished debugging the sample code, but theres quite a bit of it so I'm not sure how long it'll take to write the tutorial itself.

You're a good person for taking the time to do that. I'll wait.

Yes! I am also interested in this. I have read some of your tutorials and they are very good.

Alright fellas... (and gals)...

This is what i did.

My tasks have two pointers: These pointers point to linked lists. Each block of memory will have a header describe here: The big_mem_block list keeps track of blocks of memory larger than 8 Bytes, therefore BIG_MEM_BLOCKs are at least 8 bytes long. Each of these blocks will contain the 8 byte header described above.

All memory assigned from the big_mem_block list must be a multiple of 8. If not, the allocator will upsize the request so that it is.
For example, big_alloc( 17) will actually allocate 24 bytes.

The algorithm works as follows (let r be requested size): malloc() will actually check to see if the size you're trying to allocate is smaller than 8 bytes. If so, malloc will call small_alloc. Else, malloc will call big_alloc.

SMALL_MEM_BLOCKS are actually 264 bytes long. Each of these blocks will contain the 8 byte header described above. Therefore, 256 bytes of the block will be used for allocation. The header has a pointer to the next small_mem_block node as well as a bitmap to keep track of which of the 256 bytes have been allocated.

When malloc needs to allocate a block smaller than 8 bytes, it will use the small_mem_block list. Here is a description of the small_alloc() function: I hope that's complete. My eyes are glazed over and I don't know if I'm missing anything.

Basically, I can now allocate large blocks and small blocks of memory. (one) of the downsides is that I will waste blocks of memory when allocating something larger than 8 bytes that are non-multiples of 8.

Any thoughts?

I haven't posted in a long time here. Anyway, ....

I have two structures, both of which contain magic numbers which should be a1 byte value unique to both those structures(0xAA for one, 0xBB for the other). These structures are described more fully below and you don't need to make them exactly as I have.

What i do is I use a doubly linked list. The memory manager has a granularity of 16 bytes(the size of the element of that linked list). This is for a 32-bit architecture(pointers are 4 bytes). The linked list structure would store the next and previous pointers(obviously) and it would also store a magic number(to make sure it isn't corrupt) and a free region count. The free region count is the number of 16-byte blocks that are free after the structure including the structure itself. Anyway, basically, I would identify the area i wanted to allocate for and count the number of 16-byte blocks in that area. Then I would create the first list structure at the beginning of the area to allocate and set the values in that structure to the correct values. Then I would set a global pointer to the current linked list structure

When I would allocate something I would first find how many 16-byte blocks I would need +1. So if i wanted to allocate something of 30-bytes the blocks I need would be 2 + 1(3). Then I would use the global pointer which should point to the first free region. I would check to make sure that the structure pointed to by the global pointer first had enough blocks(by checking the free block field). If not, I would traverse the linked list until I found a region with enough blocks. Return NULL If there is not enough space.

After you have found the region with enough space. Subtract the blocks needed from the free block count. If the block count is 0, delete the free region block from the linked list. If the block is the global pointer and its count is 0, set the global pointer to the next element. Next move the structure to the next free area(the structure's address + (block's needed * 16)). Then update the next and prev addresses of the siblings(Set prev->next's to our new address and next->prev to our new address). Now in the area that we have vacated(the old address of the list element), we create a new structure with another magic number and the blocks allocated after it (not including itself). We then return the address of the allocated memory structure + 16. That is why we allocated the extra block.

To free a region of memory, we first subtract the address to free(which we will refer to as AF) by 16 and make sure that it is an allocation structure(using the magic number. We will refer to this as AS ). Then we take the AF and add 16 * the blocks allocated which we got from the AS. This number is the address immediately after the AF. Check to see if this is a free memory structure(using the magic number). The magic number can't be from a random piece of memory because we would have moved the free structure there and if not, there would be an allocation structure there and they both have different magic numbers. Going on, if there is a free structure there, then we add the blocks we're going to free(The block count of AS + 1) to the free structure's free region count. Then we move the free structure to the new address and update the sibling's addresses and/or the global pointer if it is the global pointer.

If there is not free structure there however, we create a new free structure where the old allocation structure was and set that structure's free region count to the AS's free block count + 1. Then we set this new free structure's prev value to NULL and next value to the global pointer. We set the global pointer's previous value to the new free block, Finally, we set the global pointer to this new free structure.

This memory manager makes some good compromises and the way I implemented is surprisingly fast. It is O(1) if the global pointer has enough free blocks and O(n) if we have to search the list. Freeing is O(1).

It also makes good use of memory as a structure with less than 4 unsigned integers is kind of pointless for most kernel tasks.

Well.. I already found one flaw in my design. It doesn't coalesce adjacent free blocks.

What about the idea of maintaining that the list is in order? That way, when I free a block, the algorithm can traverse the list to see where the newly freed block will fit in. Then, it can determine if the block can be combined with another one. Otherwise, it'll just insert the new node into the list.

Alrighty, gents, the tutorial is up!

http://www.jamesmolloy.co.uk/tutorial_h ... 0Heap.html

Reading your comments you were going for a linked-list approach. This will probably work, but linked-lists are slooooooowwwwww!

My method is a simplification of doug lea's malloc which is used in the GLU libc. Enjoy!


PS: please let me know how you find it - it's rather long but I couldn't find a way of compressing it without losing helpful descriptions!

JamesM

Hi,

I have had a look and it seems very good. I'm not implementing a memory manager so haven't tried following it, but it all seems well explained with nice code examples.

I like the code highlighting too - what html generator/editor do you use?

Cheers,
Adam

AJ: Cheers

I use my own rendering engine. I needed to learn perl fast (for work) so I thought it would be a good idea to write a series of lexers and a wikimedia parser (does a subset of wikimedia syntax).

You can have the source if you like - it's not well documented though!

JamesM

James, Thanks for posting this.

I have three questions:

1) According to your diagram, it looks like the heap index only keeps track of one hole of any particular size. How do you manage different holes of the same size?

2) When you're freeing memory, you inspect the neighbor's magic number. Am I correct to say that if the user overwrites this section of data with a value that happens to be the same as the magic number, it would compromise the integrity of the hole?

3) Is there any reason why you chose to use a whole byte for the is_hole flag rather than borrowing a bit for the magic field?

Vince

Hi vgh, thanks for replying.

1) That is not the case . The index is ordered. This does not mean that every item in it must be unique. Different holes of the same size are supported implicitly. (Tell me if you require a better explanation! )

2) That is correct. That will happen in *any* implementation though, and we are trusting to two things that it wont:
a) This is a *kernel heap*. So we don't have any untrusted (and crap, or malicious) user code running.
b) The sentinel value is so strange that it is very unlikely (the odds being one in 4billion (0xFFFFFFFF) ).

3) Yes, readability and simplicity. the ASSERT(field == MAGIC) lines would be much more difficult to read if one bit could be one or zero. I felt that the tutorial is long enough as it is!

I'd be glad of a reply - in particular do you think it's worth mentioning point no. 1 on the tutorial itself to avoid confusion?

JamesM

JamesM wrote:Hi vgh, thanks for replying.

1) That is not the case . The index is ordered. This does not mean that every item in it must be unique. Different holes of the same size are supported implicitly. (Tell me if you require a better explanation! )

I don't know about everyone else, but I need a little more explanation on how the heap index works.

Is the index statically allocated? Would you ever need to allocate a new heap index structure? Is your heap index actually an array of pointers to arrays?

Understood, I'll add that on monday.

The heap index is statically allocated. The current virtual memory set aside for it is 0x20000 bytes, which at 4 bytes per item, gives 32768 possible holes. Which I think is sufficient. You may disagree.

The heap index is an array of pointers to 'hole' structures. That is shown on the topmost diagram on the page. Maybe I should make that a little clearer