OSDev.org

Hello,

Recently, I read a tutorial about paging. So my kernel uses paging and I don't have issues with it.

I did't know how to implement a function that allocates memory, so I read this tutorial and got how to but I don't understand why is there no reference to bytes that pages store (a bit confusing question, but read further)? I'm worried that it allocates at least one page each time. For example, we need to allocate 128 bytes and this function will allocate the whole page, not 128 bytes, and marks the page as used, so we'll lose other 3968 bytes of the page.

I've seen a message at the forums about adding a bitmap in the beginning of each page (so first 512 bits of a page are a bitmap for the page). I think this is a good solution, but I also think that there are better solutions. If it is the best one, then will I have problems with it in the future? If it isn't, what do you recommend to use?

Thanks.

A page allocator is just that, it allocates pages.
For allocating smaller blocks without 'wasting' space, you need a dynamic memory manager, ie. malloc() and friends.

How does malloc() work?
Does it work as I described a way to keep used/free bytes of a page (bitmap in the beginning of each page)?

Hi,

ExeTwezz wrote:How does malloc() work?
Does it work as I described a way to "save" bytes in a page (I mean is it a way to implement malloc())?

Think of it as 3 layers. The first layer manages physical address space (e.g. allocating and freeing physical pages). The next layer manages virtual address spaces (e.g. allocating and free virtual pages) and uses the physical memory manager when it wants actual RAM. These 2 layers are typically built into the kernel.

The last layer handles (arbitrary sized) dynamic memory allocation; mostly by splitting a range of the virtual address space into smaller pieces (and using the virtual memory manager to acquire range/s of pages to split up). This is typically built into the application (either directly, or indirectly - e.g. as a library or some sort of run-time); and how it works depends on the application and which language it was written in (e.g. "malloc()/free()" vs. objstacks vs. garbage collection).

Note that even there are many different ways of implementing "malloc/free" ( e.g. a simple singly linked list, or trees, or buckets (slabs), or anything else); and many different ways of implementing garbage collection, etc. It's also possible (for some languages) for applications to have one or more of their own custom designed dynamic memory managers (either in addition to, or instead of, whatever the language came with).


Cheers,

Brendan

Brendan wrote:Think of it as 3 layers. The first layer manages physical address space (e.g. allocating and freeing physical pages). The next layer manages virtual address spaces (e.g. allocating and free virtual pages) and uses the physical memory manager when it wants actual RAM. These 2 layers are typically built into the kernel.

I don't understand a bit... Do you mean that the physical allocator allocates the 4KB blocks of the physical memory, and the virtual allocator allocates the pages as they are located in the certain entry in the page directory (virtual memory)?

Brendan wrote:The last layer handles (arbitrary sized) dynamic memory allocation; mostly by splitting a range of the virtual address space into smaller pieces (and using the virtual memory manager to acquire range/s of pages to split up). This is typically built into the application (either directly, or indirectly - e.g. as a library or some sort of run-time); and how it works depends on the application and which language it was written in (e.g. "malloc()/free()" vs. objstacks vs. garbage collection).

Does the dynamic allocator allocate virtual pages for the linked list (or other)? How does the structure of an entry of the linked list look (prev_entry, next_entry, block_start, block_size)? I know that I should have own design of this for my OS, but I just consult with you.

Hi,

ExeTwezz wrote:

Brendan wrote:Think of it as 3 layers. The first layer manages physical address space (e.g. allocating and freeing physical pages). The next layer manages virtual address spaces (e.g. allocating and free virtual pages) and uses the physical memory manager when it wants actual RAM. These 2 layers are typically built into the kernel.

I don't understand a bit... Do you mean that the physical allocator allocates the 4KB blocks in the physical memory, and the virtual allocator allocates the pages as they are located in the certain entry in the page directory (virtual memory)?

Yes.

For example, the virtual memory manager might have a function to allocate a virtual page at a requested virtual address, which:

• Checks if the page table is present; and if it isn't, allocates a physical page to use for the page table and inserts it into the page directory
• Checks if the virtual page already exists (which can include "exists but is currently in swap space" and doesn't necessarily mean "present in RAM"), and returns an error if it is
• Either:
  • Allocates a physical page, and inserts it into the page table (e.g. if there's plenty of free RAM and/or its likely that the page will be used soon), or
  • Maps a pre-existing page full of zeros there as "read only", and doesn't allocate a physical page until/unless something attempts to write to the page (where the virtual memory manager allocates the physical page during the page fault handler).

More importantly, the virtual memory manager might have function/s to make a range of pages into something else. For example, you might ask the virtual memory manager to memory map a file at a certain address, or to make an area "uncached, allocate on demand", or to create a "copy on write" shared memory area, etc.

Virtual memory manager would also take care of things like sending pages from RAM to swap space, loading pages from swap space into RAM, loading pages from memory mapped files into RAM, tracking how many places each virtual page is shared, etc.

Physical memory manager is far simpler - it only needs to care about allocating and freeing physical pages; and doesn't have to care about all the virtual memory manager's shenanigans.

ExeTwezz wrote:

Brendan wrote:The last layer handles (arbitrary sized) dynamic memory allocation; mostly by splitting a range of the virtual address space into smaller pieces (and using the virtual memory manager to acquire range/s of pages to split up). This is typically built into the application (either directly, or indirectly - e.g. as a library or some sort of run-time); and how it works depends on the application and which language it was written in (e.g. "malloc()/free()" vs. objstacks vs. garbage collection).

Does the dynamic allocator allocate virtual pages for the linked list (or other)? How does the structure of an entry of the linked list look (prev_entry, next_entry, block_start, block_size)? I know that I should have own design of this for my OS, but I just consult with you.

For "malloc/free" alone (ignoring garbage collection, etc); there's probably 50 different dynamic memory allocators that all work differently. At a minimum you could get by with a singly linked list of free areas, where each block begins with the address of the next block and the block's size. Of course this would be the simplest and the worst for both performance and features.


Cheers,

Brendan

Brendan wrote:For example, the virtual memory manager might have a function to allocate a virtual page at a requested virtual address, which:

• Checks if the page table is present; and if it isn't, allocates a physical page to use for the page table and inserts it into the page directory
• Checks if the virtual page already exists (which can include "exists but is currently in swap space" and doesn't necessarily mean "present in RAM"), and returns an error if it is
• Either:
  • Allocates a physical page, and inserts it into the page table (e.g. if there's plenty of free RAM and/or its likely that the page will be used soon), or
  • Maps a pre-existing page full of zeros there as "read only", and doesn't allocate a physical page until/unless something attempts to write to the page (where the virtual memory manager allocates the physical page during the page fault handler).

What do you mean by «Checks if the virtual page already exists» — is the virtual page alreday allocated or something else?
And what do you mean by «Allocates a physical page, and inserts it into the page table» — does it mean that the virtual allocator calls the physical allocator to request a physical page, say, at address 0x123000, and binds (or it's better to say "links"?) an entry in the page table at offset 123 to that address?

ExeTwezz wrote:Does the dynamic allocator allocate virtual pages for the linked list (or other)? How does the structure of an entry of the linked list look (prev_entry, next_entry, block_start, block_size)? I know that I should have own design of this for my OS, but I just consult with you.

The dynamic allocator doesn't necessarily know or care about pages. It just takes the memory that has been given to it by the operating system and uses it to fulfill malloc requests. If it doesn't have enough memory to fulfill a request it asks the operating system for more memory. On a modern operating system, the part of the operating system that fulfills that request is generally the virtual memory manager, which allocates enough pages of virtual address space to fulfill the request, and then calls the physical memory manager to back those virtual memory pages with actual RAM (though the part where the physical memory manager gets called is often put off until the program actually tries to access the allocated virtual address space).

Brendan wrote:Hi,

ExeTwezz wrote:

Brendan wrote:Think of it as 3 layers. The first layer manages physical address space (e.g. allocating and freeing physical pages). The next layer manages virtual address spaces (e.g. allocating and free virtual pages) and uses the physical memory manager when it wants actual RAM. These 2 layers are typically built into the kernel.

I don't understand a bit... Do you mean that the physical allocator allocates the 4KB blocks in the physical memory, and the virtual allocator allocates the pages as they are located in the certain entry in the page directory (virtual memory)?

Yes.

For example, the virtual memory manager might have a function to allocate a virtual page at a requested virtual address, which:

• Checks if the page table is present; and if it isn't, allocates a physical page to use for the page table and inserts it into the page directory
• Checks if the virtual page already exists (which can include "exists but is currently in swap space" and doesn't necessarily mean "present in RAM"), and returns an error if it is
• Either:
  • Allocates a physical page, and inserts it into the page table (e.g. if there's plenty of free RAM and/or its likely that the page will be used soon), or
  • Maps a pre-existing page full of zeros there as "read only", and doesn't allocate a physical page until/unless something attempts to write to the page (where the virtual memory manager allocates the physical page during the page fault handler).

More importantly, the virtual memory manager might have function/s to make a range of pages into something else. For example, you might ask the virtual memory manager to memory map a file at a certain address, or to make an area "uncached, allocate on demand", or to create a "copy on write" shared memory area, etc.

Virtual memory manager would also take care of things like sending pages from RAM to swap space, loading pages from swap space into RAM, loading pages from memory mapped files into RAM, tracking how many places each virtual page is shared, etc.

Physical memory manager is far simpler - it only needs to care about allocating and freeing physical pages; and doesn't have to care about all the virtual memory manager's shenanigans.

ExeTwezz wrote:

Brendan wrote:The last layer handles (arbitrary sized) dynamic memory allocation; mostly by splitting a range of the virtual address space into smaller pieces (and using the virtual memory manager to acquire range/s of pages to split up). This is typically built into the application (either directly, or indirectly - e.g. as a library or some sort of run-time); and how it works depends on the application and which language it was written in (e.g. "malloc()/free()" vs. objstacks vs. garbage collection).

Does the dynamic allocator allocate virtual pages for the linked list (or other)? How does the structure of an entry of the linked list look (prev_entry, next_entry, block_start, block_size)? I know that I should have own design of this for my OS, but I just consult with you.

For "malloc/free" alone (ignoring garbage collection, etc); there's probably 50 different dynamic memory allocators that all work differently. At a minimum you could get by with a singly linked list of free areas, where each block begins with the address of the next block and the block's size. Of course this would be the simplest and the worst for both performance and features.


Cheers,

Brendan

OK. But what if the virtual allocator will allocate a page that is already allocated by the physical allocator?

ExeTwezz wrote: OK. But what if the virtual allocator will allocate a page that is already allocated by the physical allocator?

Actually Virtual allocator doesn't allocate a thing, it passes a request to physical memory allocator to allocate pages to it.
A frame(physical page) mapped to more than one page is a shared page/frame, change in any of them will reflect in the other. Actually this concept is used in COW(copy on write) in which more than one pages are allocated to a frame as long as they are not modified; on modification a copy is created and modification is done on that one. COW saves redundant copy of pages unless really required.

dansmahajan wrote:

ExeTwezz wrote: OK. But what if the virtual allocator will allocate a page that is already allocated by the physical allocator?

Actually Virtual allocator doesn't allocate a thing, it passes a request to physical memory allocator to allocate pages to it.
A frame(physical page) mapped to more than one page is a shared page/frame, change in any of them will reflect in the other. Actually this concept is used in COW(copy on write) in which more than one pages are allocated to a frame as long as they are not modified; on modification a copy is created and modification is done on that one. COW saves redundant copy of pages unless really required.

Thanks.
But why the virtual memory needs a physical page for a page table? I think the address space must be completely initialized before calling the virtual memory allocator. Am I correct or there is a reason to create a new page table (except its missing)?

the paging system is designed so that not all page tables need to exist, only the ones you are currently using

the simplest x86 paging mode, there is a directory that lists the page tables, each page table can either exist, or not exist

if no page in that page table exists, then there is no reason for the page table to exist either... therefore, if the page table doesn't exist, and you need to allocate a page in it, you must first create the page table (note in other paging modes there are actually several levels of page tables, like a tree, and any unused branch can be not preset at any level in the tree)

OK, so..

The virtual allocator calls the physical allocator to allocate pages, right?
Imagine, that we want to allocate 8 pages to load a program and we're in the kernel address space. Suppose, that there are only 10 free physical pages. So, the physical allocator has allocated 8 pages for us. But what if we've loaded another address space and we want to allocate 6 pages? Since there are only 2 free physical pages left, the virtual allocator will get an error from the physical allocator (and then the virtual allocator returns -1 or does something else). From this example, I can conclude that the virtual allocator doesn't have a bitmap/stack/something else to keep free pages. Then how does it translate a physical address to a virtual to return the second one to the caller? Or my theory is wrong?

ExeTwezz wrote:OK, so..

The virtual allocator calls the physical allocator to allocate pages, right?

Yes thats correct.

ExeTwezz wrote: Imagine, that we want to allocate 8 pages to load a program and we're in the kernel address space. Suppose, that there are only 10 free physical pages. So, the physical allocator has allocated 8 pages for us. But what if we've loaded another address space and we want to allocate 6 pages? Since there are only 2 free physical pages left, the virtual allocator will get an error from the physical allocator (and then the virtual allocator returns -1 or does something else).

Yes physical memory allocator return error to virtual memory allocator if no pages are avialable. But your virtual memory allocator will have or will then invoke a swapper process to transfer unused or least used pages to swap or secondary disk.

ExeTwezz wrote: From this example, I can conclude that the virtual allocator doesn't have a bitmap/stack/something else to keep free pages. Then how does it translate a physical address to a virtual to return the second one to the caller? Or my theory is wrong?

Virtual memory allocator will place a request, physical memory allocator will address the request by returning the physical address of the page,then it upto the virtual memory allocator where to map that frame. To map a frame to a virtual memory address, it finds (or creates if they doesn't exist) the corresponding page table and page and places the frame address there. After that its the job of a MMU to translate a frame address to the corresponding page address.

dansmahajan wrote:Virtual memory allocator will place a request, physical memory allocator will address the request by returning the physical address of the page,then it upto the virtual memory allocator where to map that frame. To map a frame to a virtual memory address, it finds (or creates if they doesn't exist) the corresponding page table and page and places the frame address there. After that its the job of a MMU to translate a frame address to the corresponding page address.

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

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:

• Do some checks with the number of pages.
  • Return 0, if there are some errors.
• Loop through the bitmaps (http://www.osdever.net/tutorials/view/c ... accounting) and count the number of the longest sequence of free pages. Also save the start of that sequence.
  • If it is less than needed, return 0.
• Call the physical allocator to allocate N pages.
  • If returned 0, return 0.
• Mark N pages as used starting at the saved start of the sequence.
• Update the bitmaps.
• Convert to address and return the saved start of the sequence.

Can you please correct me if there are mistakes?