OSDev.org

Hi there,
currently I'm still trying to get my memory management on some level where it's usable.

I implemented a Physical Memory Allocator using a Bitmap which doesn't do anything more than marking any frame as used or free.
On top of that there is my Paging-Stuff which has a high level API for mapping virtual pages to physical frames.
I have a small heap which I will trash as soon as I finished my SLAB Allocator since I won't need it anymore.

This is my current memory layout for the kernel: Currently I've got 4 Regions: The Stack, Slabs, Heap and code/static data.
The code and the stack aren't much of a problem. They both don't grow or shrink on runtime. So I can just allocate the amount of space and leave them alone.
The heap is not a big problem. Currently it can expand dynamically, if it is too small, until a given limit which is 256MB here. It can't shrink itself because it uses a linked list for management and as I said it's going to be trashed anyway.
My big problem is the slab allocator. This thing grows and shrinks all the time. At least when physical memory runs short.

Let's assume I create two new slabs which occupy 4 pages and then another slab which takes 5 pages. Then the second of the three slabs gets destroyed.
How can I track that theses 4 pages at this virtual location are free?
The physical location doesn't matter. I've got my paging between the bus and my address space which handles this issue just fine.
But if I create another new 5-pages slab I need to know that I need 5 free frames and map them behind the other 5-page slab. Vice versa, if I create a new slab which takes 4 or less pages I could use the free space behind the first 4-pages slab.
Any ideas how I can track this? And where? Inside my paging stuff? It don't really fits there I think because this virtual-memory-layout-tracking is one level above it.

Does somebody know how linux or the several BSDs handle this? They must have had the same problem.
Unfortunately most of the memory stuff in the linux kernel is total black voodoo magic for me. It's optimized to level where it is almost unreadable. At least for me

I can tell you how I do it.

I have an allocator for the virtual memory. That means. After initing my vmm I free the whole kernelspace which is free (all behind code/data and the identity mapping). When my vmm is asked for some mem I first alloc an address range and than map the memory. For knowing what is free I use 2 avl trees, both use the same objects, but one is sorted by address and one by size. This makes it easy for me to merge ranges when I free a range (sorted by address) and it makes it easy when I need a range (sorted by size).

I hope I could help, if not ask what you didn´t understood.

A slab allocator usually has two pieces to it: the part that creates caches in slabs, and the part that allocates the slabs themselves. Right now, the latter for you seems to be just a stack - it should be more sophisticated than that if you want to be able to have reasonable (virtual) memory efficiency. All you need it to do is allocate page aligned chunks that are multiples of the page size, which is not hard to do.

You can use a bitmap, which may take some time to search to find a certain number of consecutive open pages, or some faster but more wasteful technique like a buddy allocator. The good part about using a buddy allocator in this situation is that you don't have to actually map all of the chunks it gives you, only the part you are using, so you will only waste virtual memory, not physical memory, and it will be simpler and faster.

NickJohnson wrote:A slab allocator usually has two pieces to it: the part that creates caches in slabs, and the part that allocates the slabs themselves. Right now, the latter for you seems to be just a stack - it should be more sophisticated than that if you want to be able to have reasonable (virtual) memory efficiency.

No, not a Stack. It's exactly nothing, yet That's what I don't know how to implement.
I'm managing the free physical frames with a bitmap. Nothing more, yet.

NickJohnson wrote:All you need it to do is allocate page aligned chunks that are multiples of the page size, which is not hard to do.

No, but I need some fast and elegant way to get a free space which is big enough and contignous in virtual space.

NickJohnson wrote:You can use a bitmap, which may take some time to search to find a certain number of consecutive open pages, or some faster but more wasteful technique like a buddy allocator. The good part about using a buddy allocator in this situation is that you don't have to actually map all of the chunks it gives you, only the part you are using, so you will only waste virtual memory, not physical memory, and it will be simpler and faster.

Where does the buddy allocator operate? Do I have several allocators for a region?
For example if my heap and slab allocator would be coexistent. Would I have 2 256MB regions whith one buddy allocator each?
So I request virtual memory space from them? No actual physical memory itself (given the fact that I have to map physical memory to the returned location manually and not automatically in the buddy allocator)?

If I have my slabs with sizes of 2^n, I can use a buddy allocator and just use the whole space.
Great! That's the solution I need. And now I understand how it's done in the linux kernel since they are using slabs with sizes of 2^n. They just take a whole chunk of memory from the buddy allocator.

Thank you

Andy1988 wrote:

NickJohnson wrote:You can use a bitmap, which may take some time to search to find a certain number of consecutive open pages, or some faster but more wasteful technique like a buddy allocator. The good part about using a buddy allocator in this situation is that you don't have to actually map all of the chunks it gives you, only the part you are using, so you will only waste virtual memory, not physical memory, and it will be simpler and faster.

Where does the buddy allocator operate? Do I have several allocators for a region?
For example if my heap and slab allocator would be coexistent. Would I have 2 256MB regions whith one buddy allocator each?
So I request virtual memory space from them? No actual physical memory itself (given the fact that I have to map physical memory to the returned location manually and not automatically in the buddy allocator)?

You don't need the buddy allocator for a normal heap, just for a slab allocator, because the slab allocator needs to be able to get large chunks of memory. You can choose whether to allocate frames to the addresses given by the buddy allocator or not - the only reason not to is if you want to use slabs of non-2^n size and only allocate the physical memory you need - otherwise just have the frames be allocated with the virtual addresses for single-point-of-failure reasons.

Also, I don't think this is how Linux does it - IIRC, they use a buddy allocator for physical memory, but I don't know what they use for allocating slabs. Perhaps a variant of dlmalloc?.

NickJohnson wrote: Also, I don't think this is how Linux does it - IIRC, they use a buddy allocator for physical memory, but I don't know what they use for allocating slabs. Perhaps a variant of dlmalloc?.

Yes, you are right.

The SLAB Allocator gets its memory from the Zone allocator which handles 3 zones: DMA, Normal and Highmem.
The Zones itself are managed by the buddy allocator.

Just found this wiki where it's all described:
http://scriptmatrix.net/cs2106/wiki/ind ... =Main_Page