[CLOSED] Memory allocation with pages.

[dansmahajan]

How does the virtual allocator determine where to map that/those physical page/pages?

Depends on the situation, suppose you have a request to alter your userspace heap or to load an exe in that case either you'll load the exe at its base address or you will apply relocation.

I've one thought about this question that the virtual allocator needs a bitmap or something else to keep free virtual pages

I think bitmaps should not used for virtual memory allocator because your virtual memory allocator has to keep a bitmap for all the virtual address spaces which means redundancy and wastage. So in a 32-bit machine total pages = (4*1024*1024*1024) / (4*1024) = 1024*1024 and required bitmap size = 1024*1024*4/32 bytes = 128KB in every address space.
In my kernel, virtual memory allocator is allocating memory in blocks and using linked list to keep a track of free/allocated memory or shared blocks.

[Brendan]

Hi,

Thanks for help, but I've one more question. How does the virtual allocator determine where to map that/those physical page/pages?

For my OSs, the virtual memory manager just does what it's told. For example, a process might ask the virtual memory manager to allocate 123 pages starting at virtual address 0x12345000, so the virtual memory manager allocates 123 pages starting at virtual address 0x12345000. It doesn't know why 123 pages are needed and doesn't know why the virtual address 0x12345000 is being used.

Maybe the executable loader wants 123 pages at virtual address 0x12345000 for the executable file's ".bss", maybe there's some JIT thing that wants 123 pages at virtual address 0x12345000 to store compiled native code, maybe the process' "malloc()" ran out of heap and wants those 123 pages at virtual address 0x12345000. It doesn't matter why; and it's none of the kernel's business why the process wanted it or where the process wanted it.

I've one thought about this question that the virtual allocator needs a bitmap or something else to keep free virtual pages. So there is my theory for the virtual allocator:

If the virtual memory manager just does what it's told; then it can do a lot of things (e.g. allocating and freeing pages, "allocate on demand", transferring pages to/from swap space) using the page tables (that the CPU needs anyway) and nothing else. It's only the messier things (shared memory, memory mapped files and deciding which pages to send to swap space) where you need any additional data structures.

Don't forget that a page table entry that's marked as "present" has a minimum of 3 bits that are available for your use (e.g. enough to keep track of whether the page is a normal page of RAM or something special), and that a page table entry that's marked as "not present" has a minimum of 31 bits that are available for your use (e.g. enough to keep track of whether the page is unused, or part of a memory mapped file or in swap space, plus 29 more bits you can use for "page number in swap space" or "entry number in memory mapped file list" or whatever).


Cheers,

Brendan

[ExeTwezz]

For my OSs, the virtual memory manager just does what it's told. For example, a process might ask the virtual memory manager to allocate 123 pages starting at virtual address 0x12345000, so the virtual memory manager allocates 123 pages starting at virtual address 0x12345000. It doesn't know why 123 pages are needed and doesn't know why the virtual address 0x12345000 is being used.

Hm.. I've thought that there is no an argument that tells where to start allocating. But what if the page at the given address (e.g. 0x12345000) is already allocated?

Don't forget that a page table entry that's marked as "present" has a minimum of 3 bits that are available for your use (e.g. enough to keep track of whether the page is a normal page of RAM or something special), and that a page table entry that's marked as "not present" has a minimum of 31 bits that are available for your use (e.g. enough to keep track of whether the page is unused, or part of a memory mapped file or in swap space, plus 29 more bits you can use for "page number in swap space" or "entry number in memory mapped file list" or whatever).

OK. Do you mean that I can store the used bit for a page in the certain entry in a page table? Is it faster than a bitmap (I have two bitmaps (C array with elements with the size of 32 bits): the first one for superpages (1024 pages; 32 elements in the array), and the second one for pages itself (32768 elements in the array)).

And I want to ask something. If the physical allocator uses the stack to keep free physical pages, does the virtual allocator need to map these physical pages to the consistent virtual pages starting at the given address (e.g. 0x12345000)?

[Combuster]

For my OSs, the virtual memory manager just does what it's told. For example, a process might ask the virtual memory manager to allocate 123 pages starting at virtual address 0x12345000, so the virtual memory manager allocates 123 pages starting at virtual address 0x12345000. It doesn't know why 123 pages are needed and doesn't know why the virtual address 0x12345000 is being used.

Hm.. I've thought that it doesn't know where to start allocating pages. But what if they're already allocated?

Trying to allocate new memory into a virtual address that's already used is probably an error. At least for debugging you can probably decide to throw a screen of death if it happens so that you know you have a bug to fix.

In normal cases it shouldn't happen. A typical OS comes with a memory design. The kernel occupies a certain area of the address space - and it should refuse userspace requests to map memory in this area. The user side is split up in where you want your binary to be, where the stack goes, and where the heap goes. For a 32-bit binary you can for instance say that anything between 0x4000 0000 and 0xC000 0000 is for usable memory, and that the kernel goes after that and all code and data sections before it. When you allocate your first page for your heap, malloc() will cause a request for a page to be mapped at 0x40000000. When it ran out of space on that page, the next request will then map a page at 0x40001000. As long as your allocator properly keeps track of the heap, you shouldn't see new allocations to already mapped addresses.

[Brendan]

Hi,

Don't forget that a page table entry that's marked as "present" has a minimum of 3 bits that are available for your use (e.g. enough to keep track of whether the page is a normal page of RAM or something special), and that a page table entry that's marked as "not present" has a minimum of 31 bits that are available for your use (e.g. enough to keep track of whether the page is unused, or part of a memory mapped file or in swap space, plus 29 more bits you can use for "page number in swap space" or "entry number in memory mapped file list" or whatever).

OK. Do you mean that I can store the used bit for a page in the certain entry in a page table?

Typically as the OS gets more and more complicated the virtual memory manager evolves. Initially, all "present" pages might be normal RAM and all "not present" pages might be unused. Then you might add support for "allocation on demand" (where the same physical page full of zeros is mapped everywhere as "read only" and replaced with a normal read/write page when something tries to write to it) and now a "present" page could be either normal page of RAM or the special read-only page full of zeros, and you have to be able to tell the difference. Then you might add support for memory mapped devices, where a "present" page could be (e.g.) part of video display memory and not normal RAM. After that you might add support for memory mapped files, swap space, "copy on write" shared memory areas, etc. In the end you could end up with 5 or more different types of "present" page, where you need to tell the difference between each of them quickly.

For "not present" pages it's the same - it could be "unused", or part of memory mapped file that hasn't been loaded from disk yet, or the data might have been sent to swap space, etc.

Now; for almost everything the virtual memory manager does (allocating memory, freeing memory, creating memory mapped file areas, etc), one of the first things the virtual memory manager will do is check the page table entries for the requested area, to figure out what's is currently mapped. For performance, you want to pack as much information as you can into the page table entry, (e.g.) to avoid any additional cache misses or lookups.

So...

For "present" pages there's a minimum of 3 "available for OS use" bits in each page table entry; and you've got 5 or more different types of "present" page, and need to know what type of "present" page it is quickly. Using those 3 "available for OS use" bits to keep track of the type of present page is a very obvious solution.

For "not present" pages there are a minimum of 31 "available for OS use" bits in each page table entry. In this case you only have a few different types of "not present" pages, so you only need a few of those 31 bits to keep track of what type of page it is. However, you wouldn't waste the other bits - you'd use them to speed up other things. For a simple example, maybe you use 2 of the bits to keep track of what type of not present page, and then if the page happens to be "not present, current in swap space" you use the remaining 29 bits to store a "page number within swap space" so that if you have to fetch a page from swap space you immediately know where to fetch it from. Note: a 29-bit "page number within swap space" would allow you to support up to 2048 GiB of swap space; which is plenty for a 32-bit OS kernel.

Note: For "plain 32-bit paging" you only have 3 available bits for "present" pages and 31 available bits for "not present" pages. For PAE and long mode you get more. For example, in long mode there are 14 available bits for "present" pages and 63 available bits for "not present" pages.

Is it faster than a bitmap (I have two bitmaps (C array with elements with the size of 32 bits): the first one for superpages (1024 pages; 32 elements in the array), and the second one for pages itself (32768 elements in the array)).

I have no idea what you think you need those bitmaps for.

And I want to ask something. If the physical allocator uses the stack to keep free physical pages, does the virtual allocator need to map these physical pages to the consistent virtual pages starting at the given address (e.g. 0x12345000)?

Different people implement things in different ways. I don't map free physical pages (in the physical memory allocator's stack/s) into any virtual address space (but other people do).


Cheers,

Brendan

[ExeTwezz]

Thanks, Brendan.

Again, what if the virtual allocator needs a page for a page table, and the physical allocator will return the address of a page that is mapped to a used virtual page?
Info: my virtual allocator allocates the specified number of pages starting at the specified address, the page table entry has used bit. The physical allocator has a stack of free pages.

[dansmahajan]

Thanks, Brendan.

How does the allocator determine how many pages to free? Does the function need to have an argument for it?

Again, what if the virtual allocator needs a page for a page table, and the physical allocator will return the address of a page that is mapped to a used virtual page?

Virtual memory allocator frees/allocates pages,on demand, is given the location where to do so. In a general case,your malloc/free functions implemented in the userspace take request from user programs and pass it to virtual memory allocator via system call (assuming no space is allocated) which depends on your OS design.

[dansmahajan]

Thanks, Brendan.

Again, what if the virtual allocator needs a page for a page table, and the physical allocator will return the address of a page that is mapped to a used virtual page?
Info: my virtual allocator allocates the specified number of pages starting at the specified address, the page table entry has used bit. The physical allocator has a stack of free pages.

Why would your physical memory allocator return a used page?? Isn't it containing a list of free pages??
Even if it does that page will get shared between process or address spaces using it. So if any one of them writes to it,other gets the dirty page.

[ExeTwezz]

Thanks, Brendan.

How does the allocator determine how many pages to free? Does the function need to have an argument for it?

Again, what if the virtual allocator needs a page for a page table, and the physical allocator will return the address of a page that is mapped to a used virtual page?

Virtual memory allocator frees/allocates pages,on demand, is given the location where to do so. In a general case,your malloc/free functions implemented in the userspace take request from user programs and pass it to virtual memory allocator via system call (assuming no space is allocated) which depends on your OS design.

Yeah, I know that it allocates at the given address. But what if the virtual page where this address is, is mapped to a physical page that contains a page table? It's not possible to detect that it is allocated, since it is allocated by the physical allocator.

[ExeTwezz]

Thanks, Brendan.

Again, what if the virtual allocator needs a page for a page table, and the physical allocator will return the address of a page that is mapped to a used virtual page?
Info: my virtual allocator allocates the specified number of pages starting at the specified address, the page table entry has used bit. The physical allocator has a stack of free pages.

Why would your physical memory allocator return a used page?? Isn't it containing a list of free pages??
Even if it does that page will get shared between process or address spaces using it. So if any one of them writes to it,other gets the dirty page.

I mean that it can return the page that is mapped to a used virtual page .

[ExeTwezz]

I've thought about the conflicts between the physical and virtual allocators that I described before (if you don't understand what conflicts, just read the next paragraph), and I think they can't be if I will properly select an area of free physical pages.
Can you please say me where are the best areas where I can store free physical pages? I think they should be below 1 MB, since all pages after 2 MB are marked as free in my kernel.

[dansmahajan]

I've thought about the conflicts between the physical and virtual allocators that I described before (if you don't understand what conflicts, just read the next paragraph), and I think they can't be if I will properly select an area of free physical pages.
Can you please say me where are the best areas where I can store free physical pages? I think they should be below 1 MB, since all pages after 2 MB are marked as free in my kernel.

You can keep your physical pages anywhere you like as after paging is enabled you are going to identity map your kernel to the same virtual address as its physical address. Also these pages/frames will be marked as allocated in physical memory manager so it is not going to return this frame address unless it has gone crazy.
There will be a page directory or address space belonging to kernel exclusively only kernel is having a write access to it. In other address spaces,kernel pages are linked with read only access to avoid kernel crash. So even if you have access to a page table you can't write to it.

Thanks, Brendan.
Again, what if the virtual allocator needs a page for a page table, and the physical allocator will return the address of a page that is mapped to a used virtual page?
Info: my virtual allocator allocates the specified number of pages starting at the specified address, the page table entry has used bit. The physical allocator has a stack of free pages.

Why would your physical memory allocator return a used page?? Isn't it containing a list of free pages??
Even if it does that page will get shared between process or address spaces using it. So if any one of them writes to it,other gets the dirty page.

I mean that it can return the page that is mapped to a used virtual page .

Physical memory allocator's only job is to allocate or free pages. While allocating it will return first free page found in the bitmap(this is what I've implemented) or free frame list. Personally i don't think there would be any case in which a healthy physical memory allocator will return a used/allocated page.

[ExeTwezz]

You can keep your physical pages anywhere you like as after paging is enabled you are going to identity map your kernel to the same virtual address as its physical address. Also these pages/frames will be marked as allocated in physical memory manager so it is not going to return this frame address unless it has gone crazy.
There will be a page directory or address space belonging to kernel exclusively only kernel is having a write access to it. In other address spaces,kernel pages are linked with read only access to avoid kernel crash. So even if you have access to a page table you can't write to it.

Say, there is a physical page at physical address 0x200000 (2 MB) and it is mapped to a virtual address 0x300000 (3 MB). It is possible that the virtual allocator will allocate this page some time, and it will request a physical page for page table. The physical allocator can return a page 0x200000 that is already used by the virtual allocator, but the physical allocator doesn't know that. Is it possible to prevent this?

[Brendan]

Hi,

You can keep your physical pages anywhere you like as after paging is enabled you are going to identity map your kernel to the same virtual address as its physical address. Also these pages/frames will be marked as allocated in physical memory manager so it is not going to return this frame address unless it has gone crazy.
There will be a page directory or address space belonging to kernel exclusively only kernel is having a write access to it. In other address spaces,kernel pages are linked with read only access to avoid kernel crash. So even if you have access to a page table you can't write to it.

Say, there is a physical page at physical address 0x200000 (2 MB) and it is mapped to a virtual address 0x300000 (3 MB).

In that case the virtual memory manager must know that virtual address 0x300000 is "special" (e.g. to prevent it from sending it to swap space, etc).

It is possible that the virtual allocator will allocate this page some time, and it will request a physical page for page table. The physical allocator can return a page 0x200000 that is already used by the virtual allocator, but the physical allocator doesn't know that. Is it possible to prevent this?

If virtual address 0x300000 is part of a special "all RAM mapped here" thing, then there's no reason why the same physical page can't be in that "all RAM mapped here" thing and also used as a page table (or anything else). Note: In my opinion this would be "less than good" because sooner or later the amount of physical RAM will grow to be larger than the amount of virtual space you can use for "all RAM mapped here"; and (especially for monolithic kernels) it maximises the amount of damage a "dodgy pointer" bug can do; and it consumes RAM for the area's page tables, page directories, etc.

If virtual address 0x300000 is part of a special "only free physical pages mapped here" thing, then you'd have to unmap the physical page when the physical page is allocated, and it won't be mapped in 2 places. Note: This is likely to be bad for performance - a lot of unnecessary mapping/unmapping when physical pages are allocated and freed (which will include TLB invalidation, and expensive "multi-CPU TLB shootdown" later).


Cheers,

Brendan

[ExeTwezz]

Brendan,

In my kernel the first physical 4 MB are mapped to the first virtual 4 MB. The first 640 KB are in the stack of free physical pages yet (until I will more understand). All the 4 MB are marked as free in the page table.

And I want free physical pages to be more than 160 (160 * 4096 = 655360 = 640 KB). How can I do that (how to split the memory)?