Memory Allocation - How it works

[bace]

So, I'm implementing memory allocation in my kernel, so that when I'm done I'll have kmalloc() and kfree().
I'm a bit confused about some things, so could someone please confirm if my explanation is correct/incorrect.

This is how I think it works:
1. A physical memory allocator provides frame_alloc(pages) and frame_free(position, pages), which allocates physical memory in blocks of however big a page on the system architecture is. This can be implemented with a bitset, a stack, a buddy allocator, etc.
2. A virtual address allocator provides page_alloc(pages) and page_free(position, pages), which allocates virtual memory addresses in blocks of however big a page on the system architecture is, making use of frame_alloc() and frame_free(). This can be implemented with ???.
3. Finally, the memory allocator itself provides malloc(size) and free(position), which allocates virtual memory of any size. This can be implemented in several ways, and the code is usually linked with program binaries. This makes use of page_alloc() and page_free() through system calls (or directly for the kernel's memory allocator).

Please tell me if anything's incorrect!
-bace

[Techel]

Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).

[Combuster]

Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).

In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

[Techel]

Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).

In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

Why?

[bace]

Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).

In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

So, is it the program's job to choose where the physical memory is mapped to in the virtual address space? That doesn't seem right...?

[Techel]

No I meant this method could be used to detect free and unmapped pages in the virtual address space. Of course the program should not choose the physical memory address to use.

[Brendan]

Hi,

This is how I think it works:
1. A physical memory allocator provides frame_alloc(pages) and frame_free(position, pages), which allocates physical memory in blocks of however big a page on the system architecture is. This can be implemented with a bitset, a stack, a buddy allocator, etc.
2. A virtual address allocator provides page_alloc(pages) and page_free(position, pages), which allocates virtual memory addresses in blocks of however big a page on the system architecture is, making use of frame_alloc() and frame_free(). This can be implemented with ???.
3. Finally, the memory allocator itself provides malloc(size) and free(position), which allocates virtual memory of any size. This can be implemented in several ways, and the code is usually linked with program binaries. This makes use of page_alloc() and page_free() through system calls (or directly for the kernel's memory allocator).

That looks mostly right to me; however...

From the kernel's point of view; that final memory allocator should be considered part of the process. It could be "malloc()" and "free()" in a dynamically linked library, it could be something completely different (e.g. garbage collector), and it could also be "nothing" (e.g. programmer explicitly manages their own memory). A kernel doesn't need to know or care what the final memory allocator is.

Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).

In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

So, is it the program's job to choose where the physical memory is mapped to in the virtual address space? That doesn't seem right...?

Once the process is started; the final memory allocator (the one the kernel doesn't know or care about, which is part of the process) would decide which virtual addresses are used for what.

The second "virtual address allocator" is more like a memory manager than an allocator. For example, it might have a set of attributes for each page (e.g. if the page is meant to look like RAM, if the page can/can't be sent to swap space, if the page is part of a memory mapped file, if the page is executable or writeable, etc) and provide a single "change n pages starting at <address> to type <attributes>" function that the third memory allocator uses to do things like changing an area to "meant to look like RAM" or changing an area back to "not meant to look like RAM".


Cheers,

Brendan

[bace]

Thanks, everyone. I understand it now!
-bace

[Combuster]

Allocating free virtual pages can be done by looping through the page directory and find free pages (or finding free page tables, representing 1024 free pages).

In general, if you want map something into virtual space without knowing which address to use for it or if it's free, your logic is flawed to start with.

So, is it the program's job to choose where the physical memory is mapped to in the virtual address space? That doesn't seem right...?

If you need more stack space, it has to go next to existing stack, not some random address in memory.
If you need a few MB of RAM allocated for some data, you want that in one sequence, not in 4K chunks in random places in memory.
For the address of everything else you find in a typical program, try running objdump -h on any binary you have.

[Techel]

If you need more stack space, it has to go next to existing stack, not some random address in memory.
If you need a few MB of RAM allocated for some data, you want that in one sequence, not in 4K chunks in random places in memory.
For the address of everything else you find in a typical program, try running objdump -h on any binary you have.

If the program needs a space for memory mapped files or something else, the virtual memory manager would look through the address space of the program and find a fitting sequence of pages. Where is the problem?

[Combuster]

So it takes the first free area in memory, and return a "valid" null pointer? Pick the spot immediately after the heap so that you can't do any future malloc() calls? Put it halfway into another memory-mapped file because only the first few bytes were read and subsequent pages weren't yet loaded and mapped into memory?