(Answered)Heap/Pool Dynamic Memory Allocation Implementation

[Octacone]

@Geri
Yeah, I realized it, many people have mentioned it. I guess I will have to deal with it. Even 1000 KB of RAM is nothing compared to 4 GB.

@Octacone..

I'm in a bit of a hurry, so don't have time to quote properly, also let me know if I missed anything..

Wrt to the "why 5 and not 3", not sure what you meant by that..? If you are referring to the "5" in the "100x5B", then that 5 is picked up from your earlier post (32-27), so I was just continuing with your example and pointing out that wasting 5B per allocation is irrelevant if there's only ever going to be a 100 such allocations (ie. 500B). Also it's irrelevant if there's 10k such allocations on modern x86 systems (though embedded may of course be different). So I was trying to point out that while you want to be frugal with most of your memory, in some cases (especially wrt to the kernel) it really doesn't matter.

Whether you want to optimize for cache lines is of course up to you, but only supporting a couple of allocation sizes for the kernel malloc (kmalloc) makes things simpler on that side. If your userland malloc crashes it's easier to diagnose, if your kmalloc crashes it's more difficult, so keeping kmalloc simple has benefits, keeping malloc simple isn't really feasible..

Didn't really get your 7247 => 200+B, where's the 200 come from? But regardless, if there's only handful of such structs allocated then 200B wasted on each is again meaningless.



Wrt to 33 -> 64 rounding, I was just giving some examples, the exact rounding you want to do is up to you. There's two things to consider, one is having a relatively low number of allocation sizes to keep the allocator simple and the other is for cache line optimizations. You can ignore the cache line optimizations for now if you like, but keeping things simple does help. So 33 could also be rounded to 36 or 48, etc.. Once you know all the structs you need you can decide how you want to round them, for starters you could just give each 4KiB to get the ball rolling and fix those once you have all of your structs ready, since you probably don't know all the sizes yet..

The basic idea is that when you call kmalloc:
void* ptr = kmalloc(32); // ok
void* ptr = kmalloc(33); // kpanic, invalid allocation size
void* ptr = kmalloc(64); // ok
etc..

So then inside kmalloc you just check the requested size, and based on it you have different page for each size from which you allocate, that way you don't have to deal with odd sizes, etc. The idea here is to keep it as simple as possible. So if you only needed three different allocation sizes, say 32B, 64B and 256B you might have:
void* free32BList;
void* free64BList;
void* free256BList;
And then just keep track of those, but if this complicates things for you, you can certainly do it anyway you like =)

Note also that I would not use identity mapping at all, what benefit do you think you get from it?

Finally, the userland malloc is not something that comes with the OS at all, it's part of the language runtime, yes, you'll have to create it if you want to compile C apps for your OS, but it's not part of the OS and you should _NOT_ want to enforce any malloc on anyone.

Even if you did enforce your malloc on your userland, you couldn't. Consider the following code on _any_ OS:

Code: Select all

void* lotsOfMem; // allocate ram from OS, using "enforced" malloc

void* myMalloc(size_t count) {
void* addr;
// somehow parcel out the large 10GiB block for internal allocations
return addr;
}

void main() {
lotsOfMem = malloc(10GiB);
uint32_t* manyInts = myMalloc(10 * 1000 * 1000 * 4);
}

The point here is that you can't enforce your malloc nor should you even attempt. AFAIK Windows apps that use malloc, the malloc internally uses VirtualAlloc (part of Win32 API) or something similar.

So the idea is that the language runtime malloc uses the OS's VMM to allocate what it wants. And you can offload the burden of figuring out what they want to userland, which makes simpler/stabler kernel, leaves more room for userland optimizations, etc.

So when userland calls:
VMM_Alloc(/*start*/ 0x10000, /*stop*/ 0x20000);

All your kernel VMM has to do is check that the userland is not requesting allocation on top of kernel memory. You may also want to check it's not doing something stupid, like requesting allocation on top of something that's already allocated to it (or you may want to allow it as a quick way of allowing to change the allocation type (read-only vs read-write vs execute, etc)). My VMM_Alloc example above didn't include "type", you may want to do that though.

So all the VMM_Alloc needs to do is basic sanity and security checking and then just do what it was asked to do, which makes its implementation quite simple.

Then as a starting malloc (for userland) you can do something simple (though inefficient) and just always round up the requested allocation to the nearest 4KiB and allocate that (yeah, I said it's inefficient). And couple of days later fix it when it becomes a problem.

So all four pieces (PMM, VMM, kmalloc and malloc) become really simple, and only reason to change them is to improve efficiency, but that's just optimization.

I finally fully understand what you meant!
What confused me was the fact that I thought that you could only round to 32 and 64 bits (because of the CPU architecture). Looks like that is not the case, perfect. So I just need to figure out the most common sizes that my kernel will use and make a chunk of them available. Maybe to just copy and paste an already existing PMM allocator and make it compatible with different even sizes. Or even, yo yo PMM give me a page (0x1000/4096 bytes), now I have 4096 bytes available, why not parcel that page and turn in into 62 chunks of 48 bytes + 14 chunks of 32 bytes + 10 chunks of 64 bytes, or something like that. You really managed to get my brain running. Thanks for that!!! Okay, I will not enforce it after all, but still I am going to provide a decent implementation that programmers will be able to use if wanted.


Okay, I've got all the answer I needed related to this topic above. I will try to use them wisely and not ignore them.

Now: does anybody have a way of knowing if the page table (virtual one that needs to be allocated) has been already allocated so I don't need to call PMM_Allocate_Block() twice/n for each mapping.
Right now I am using this awful hack (I am surprised it even works, sometimes):

Code: Select all

if(((uint32_t) page_directory->virtual_page_tables[virtual_address >> 22]) % 0x1000 == 0)
{
	  //page table already allocated, not need to create it again
     //mapping...
}
else
{
	 //page table not allocated, need to create one
	 uint32_t page_table_address = PMM.Allocate_Block();
	 page_table_t* new_page_table = (page_table_t*) page_table_address;
	 String.Memory_Set(new_page_table, 0, 4096);
	 //mapping...
}

I need the way of knowing if the specific page table exists without causing a page fault.

[~]

I need the way of knowing if the specific page table exists without causing a page fault.

You could probably "format" the whole memory with paging when your system starts, creating paging structures in a contiguous area after the kernel with a size appropriate for the amount of RAM actually installed. Then you could probably map all pages initially to the kernel. After that you could probably reassign any pages to other address spaces.

But if you always keep the paging structures of all processes somehow in the address space of the memory manager, by the initial memory formatting, then you probably wouldn't cause page faults.

Or you could probably handle the page fault using the faulting address in CR2 and correct. Anyway the page fault is supposed to tell you when a page isn't found so you make it available whenever possible, whenever it isn't because of an actual bug in a program.

[Octacone]

I need the way of knowing if the specific page table exists without causing a page fault.

You could probably "format" the whole memory with paging when your system starts, creating paging structures in a contiguous area after the kernel with a size appropriate for the amount of RAM actually installed. Then you could probably map all pages initially to the kernel. After that you could probably reassign any pages to other address spaces.

But if you always keep the paging structures of all processes somehow in the address space of the memory manager, by the initial memory formatting, then you probably wouldn't cause page faults.

Or you could probably handle the page fault using the faulting address in CR2 and correct. Anyway the page fault is supposed to tell you when a page isn't found so you make it available whenever possible, whenever it isn't because of an actual bug in a program.

Hey, I tried this:

Code: Select all

for(uint32_t i = 0; i <= 0xFFFFFFFF; i += 0x1000)
{
	uint32_t page_table_address = PMM.Allocate_Block();
	page_table_t* new_page_table = (page_table_t*) page_table_address;
	String.Memory_Set(new_page_table, 0, 4096);
	page_directory->virtual_page_tables[i >> 22] = new_page_table;
}

and got this: (I might be a sketchy developer, but look at this abstract art)

Do you think there is a way of dong it where I could use those free bits as a reference for something?

Edit:
I found a way to do it:

Code: Select all

if(page_directory->physical_page_tables[virtual_address >> 22].page_table_address != 0)
{
//Page table already exist do the mapping
}
else
{
//Page table doesn't exist make one and then do the mapping
uint32_t page_table_address = PMM.Allocate_Block();
page_table_t* new_page_table = (page_table_t*) page_table_address;
String.Memory_Set(new_page_table, 0, 4096);
page_directory->virtual_page_tables[virtual_address >> 22] = new_page_table;
}

But the problem is:
I can map everything just fine before I enable paging and all the mapped address work, but when I try to map something after enabling paging I keep getting a page fault. Is this supposed to happen? How do I determine which of the "callers/files" issued a read action?

[LtG]

FYI: As everything I've said in this thread, I'm completely ignoring large pages and talking only about a implementation that supports only 4KiB pages. Multi-page size support is more complex and I think you'll need essentially a "complete" OS before you anyone should even attempt large page support because the only reason to use large pages is optimization and with all optimization you should be able to measure (prove) that it actually has benefit. Nobody can really do that unless the OS is somewhat "complete"...

Now, on to the more interesting stuff..

Yes, the PMM should only ever give full pages (4KiB), because the VMM can only ever map full pages, as a consequence the userland malloc (using VMM_alloc, or some such) may only ever request full pages. So everything always happens at page granularity, except at the very last step which is the C code app that uses malloc, where malloc does the "parcel small pieces". This is also the reason why using a stack for the PMM is very efficient and has zero memory overhead. The VMM itself doesn't care, it just takes orders from malloc or kmalloc, and really only the malloc and kmalloc have to concern themselves with bookkeeping for the most part.

As for providing a decent malloc, yes, you will need to do that, but it's not part of the OS. It's part of the language runtime, so for you that likely means you will need to create a malloc library that your cross-compiler GCC toolchain uses, so that when you create some userland app using C and compiling with your GCC it will use that malloc implementation, not the Linux GCC malloc (which is still part of GCC, not Linux). So you need the malloc to create userland apps (well technically you could do without it, but that's besides the point), but it's not part of the OS, it's part of whatever language runtime and you likely would create a new "malloc" for each compiler (language) you plan to support. The OS only provides the VMM API which each malloc uses. The VMM is part of the OS.

As for knowing if a page table has been allocated, I'm not sure if I understood the question, but assuming I did... When ever a process has been created you can assume a page dir has been created (because creating page dir is part of process creation, therefore if process exists => page dir exists). If you are using the recursive page dir trick, and you have for instance mapped the page dir to the end of VAS (virtual address space), then so long as you are currently using the VAS that you want to modify you can just do a manual page walk your self.

So, let's assume the app has requested something from the VMM (allocate 4KiB at 0x1000), and it did so thru syscall and we are still in the same address space (haven't changed CR3) therefore the current apps address space is still visible/in use even though we are in kernel. We assume (because we've made sure) that we can access the page dir at the very end of the VAS, there we look up the first PDE (Page Directory Entry), we know exactly where it is, if that entry says not present, then we do what needs to be done (allocate a physical page frame for it, clear it, and map it, then we do the previous step again and now it's there). Now that we've read the PDE, we go to check the PTE for 0x1000, if there's nothing there (not present) then we allocate a physical page frame, map it there and return to userland, we've done our job. Most of the VMM stuff turns into very simple code =)

If you're not familiar with the recursive mapping, look at this:
http://wiki.osdev.org/Page_Tables#Recursive_mapping

[~]

Hey, I tried this:

Code: Select all

for(uint32_t i = 0; i <= 0xFFFFFFFF; i += 0x1000)
{
	uint32_t page_table_address = PMM.Allocate_Block();
	page_table_t* new_page_table = (page_table_t*) page_table_address;
	String.Memory_Set(new_page_table, 0, 4096);
	page_directory->virtual_page_tables[i >> 22] = new_page_table;
}

and got this: (I might be a sketchy developer, but look at this abstract art)

Skills.png

Do you think there is a way of dong it where I could use those free bits as a reference for something?

Edit:
I found a way to do it:

Code: Select all

if(page_directory->physical_page_tables[virtual_address >> 22].page_table_address != 0)
{
//Page table already exist do the mapping
}
else
{
//Page table doesn't exist make one and then do the mapping
uint32_t page_table_address = PMM.Allocate_Block();
page_table_t* new_page_table = (page_table_t*) page_table_address;
String.Memory_Set(new_page_table, 0, 4096);
page_directory->virtual_page_tables[virtual_address >> 22] = new_page_table;
}

But the problem is:
I can map everything just fine before I enable paging and all the mapped address work, but when I try to map something after enabling paging I keep getting a page fault. Is this supposed to happen? How do I determine which of the "callers/files" issued a read action?

You could inspect CR2 to see the faulting address, print it actually and trace the state of your programs after each major critical step to see where it breaks. You could probably be better if you create a kernel printing function to screen that you can enable or disable at run time. Then have it print each step and letting you decide whether to continue or not if all of the state of the mapping task is sane at each step.

The problem with paging and other similar things is that they exist as obligate library code which is dependent on another application. You won't really understand it by yourself.

So I suggest that you write a final application that lets you decide if your paging is working well. For example, an animated GIF viewer for you to display a cinemagraph. If it looks right, then you known that your paging is working well. With that you will have to work allocating and deallocating memory for the LZW dictionaries and decompressed bit map data, as pixel chunks and finally as full frames. Or a text viewer. The idea is that you can see if your memory management code works in real practice.

Until you don't use in a final program, at least a simple image viewer for a single image file format, you won't be able to distinguish certain unknown details at this point without which you code will just be buggy. So your implementation will be purely theoretical and conceptually incomplete until you use it in n application you need and thus understand, specially for obligated library-only code like paging which is only a relatively small part in the whole scheme of memory management and protection (it will only be in charge of a few tasks of those).

If you were working in a windowed environment, you could create a window with all of the messages and debugging questions that if you want to continue after verifying that each step is OK, which you could later close without affecting your actual program or library to test.

[Js2xxx]

For me, I divide allocation into 2 parts. First, I allocate page to the caller process. Each process has some page directories (so the unit is 2M); and I map the page to the address space of the process. Second, I allocate memory in that page.
Pseudo-code:

Code: Select all

void * Memory::Allocate(int pid, int size)
{
    void *ret;
    size = Align(size);
    if(The process' page is full)
    {
        ret = Page::Allocate(1);
        Add the page to the process;
    }
    else ret = the process' current page.
    ret = Memory::AllocateInPage(ret, size);
    return ret;
}

That's for requests with size < 2M. For that with size>= 2M, I allocate pages directly.
All the sizes is aligned.

[LtG]

For me, I divide allocation into 2 parts. First, I allocate page to the caller process. Each process has some page directories (so the unit is 2M); and I map the page to the address space of the process. Second, I allocate memory in that page.
Pseudo-code:

Code: Select all

void * Memory::Allocate(int pid, int size)
{
    void *ret;
    size = Align(size);
    if(The process' page is full)
    {
        ret = Page::Allocate(1);
        Add the page to the process;
    }
    else ret = the process' current page.
    ret = Memory::AllocateInPage(ret, size);
    return ret;
}

That's for requests with size < 2M. For that with size>= 2M, I allocate pages directly.
All the sizes is aligned.

What do you do when the app free's memory? The algo you showed looks like it only goes "forward" in VAS and any free'd memory stays free'd and unused, never to be used again by the process or the OS, until the process is killed..

Also, good to keep in mind that AFAIK all modern CPU's have significantly less large page TLB entries than "normal" 4KiB entries. Though that might be such a small "optimization" detail that it doesn't matter to you.. Also probably it's impact varies greatly depending on the type of OS..

[Js2xxx]

@LtG

So here's pseudo-code: For the request with size<0x200000

Code: Select all

void Memory::Free(int pid, void *ptr, int size)
{
    size = Align(size);
    Memory::FreeInPage(ptr, size);
    if(Page::Empty(ptr & ~0x1fffff))
    {
        Page::Free(ptr & ~0x1fffff);
        Remove this page from the process;
    }
}

Size >=0x200000: Free pages directly.
I use Accessed bit to manage pages, and use memory blocks to manage the memory in each page
. My kernel uses this way, and so far no fault has been found.

[LtG]

@LtG

So here's pseudo-code: For the request with size<0x200000

Code: Select all

void Memory::Free(int pid, void *ptr, int size)
{
    size = Align(size);
    Memory::FreeInPage(ptr, size);
    if(Page::Empty(ptr & ~0x1fffff))
    {
        Page::Free(ptr & ~0x1fffff);
        Remove this page from the process;
    }
}

Size >=0x200000: Free pages directly.
I use Accessed bit to manage pages, and use memory blocks to manage the memory in each page
. My kernel uses this way, and so far no fault has been found.

That doesn't really answer the question I asked.. Assuming 32-bit, and assuming 3GiB VAS (Virtual Address Space) left for apps, what happens if some does the following:
1. Allocate 2,5 GiB
2. Free the above 2,5 GiB
3. Allocate 1 GiB

Will the third step succeed or fail? It is expected to succeed since there's enough free VAS, but if your system only goes "forward" in the VAS and never looks back then after any process has allocated a total of 3 GiB of VAS during its lifetime then it will start failing to do allocations.

If you're not sure what happens on your system, then you can test =)

It's always good to have test apps that stress the system as well as more test apps that do stupid stuff just to see that the system behaves as expected.

[Js2xxx]

Do you mean I only allocate virtual page frame and physical memory is "abandoned"?
Well, at the entry of the kernel, I do check how much memory is present. then I map the present memory. I also record the start of the total available memory and the end of that. Also, the maximum VAS size of each process is 1GB. When I do Page::Allocate(), I'll check whether the available page is enough and whether there's underflow or overflow. And when I do Memory::AllocateInPage(), I'll check too. If there isn't enough memory, it'll return a nullptr.

And if you mean my Memory::Free() is useless, I think I didn't tell you clearly.
After some memory blocks is freed, it'll be marked available afresh and if another allocation is requested, Memory::Allocate() will find it.

EDIT: I tested your condition, and it did work well (I allocated it as an integer array and tested every elements with a loop, and freed it, and reallocated it and tested it again. No faults.)