How efficiently manage page metadata

[OSwhatever]

Most of the pages that you allocate in the system need some kind of metadata in a structure. This means for almost every page you have to allocate this structure. I know that Linux has all of these preallocated which can consume several megabytes. My kernel, you will not need these structures if you allocate pages in the kernel as they are non-swappable and owned by the kernel so I'm a bit reluctant to preallocate these structures. Also locked memory will optimize the page sizes so a structure of each small page in the large page will not be necessary.

The question is if preallocation is the best anyway in order to avoid fragmentation of the kernel memory.

[Nessphoro]

But, what's the question?

[Brendan]

Hi,

The question is if preallocation is the best anyway in order to avoid fragmentation of the kernel memory.

The first step would be to determine exactly what this metadata is and how it will be used. Once you've figured that out you'd have different structures for different purposes; partly because you'll find some things only care about a subset of (virtual or physical) pages anyway, partly to improve cache locality and reduce lock contention, and partly so that you can change the data structures that one piece of the OS uses without messing up the data structures that other pieces of the OS use.


Cheers,

Brendan

[OSwhatever]

Digging deeper into this I realize that if you going to implement a fully paged operating system with demand paging and everything you must have a structure that associates virtual pages with physical pages and vice versa, so they must go both ways.

Many CPUs use forward mapping, virtual translates to physical in tables. This requires that the OS must create extra page meta data so that the translation can go the other way, physical to virtual. Now inverted page tables do the opposite, physical to virtual mapping where some kind of hash tables are often used. In practice this method enables CPU designers to combine this structure so that page meta data can be stored in only one location enabling to way association which leads to less memory overhead. Also this method seems to be more different page size friendly.

Maybe MIPS made a better decision by allowing the SW to deal with the tables.

[Brendan]

Hi,

Digging deeper into this I realize that if you going to implement a fully paged operating system with demand paging and everything you must have a structure that associates virtual pages with physical pages and vice versa, so they must go both ways.

For which specific use case/s?

Are you saying that the CPU needs to be able to convert physical addresses back into none or more virtual addresses? Are you saying that the OS/kernel's "memory mapped file" support needs to be able to convert any physical address back into none or more virtual addresses? Is it for the OS/kernel's "copy on write shared memory" support? Is it for the OS/kernel's code to that retrieves pages from swap space back into memory? Is it for the OS/kernel's code to that determines which pages are the best pages to send to swap space?

I still think you're designing metadata for "unknown use cases". If you are, stop it - determine the use cases, then design meta-data to suit each different use case.


Cheers,

Brendan

[Antti]

...preallocated which can consume several megabytes

Are you a bit reluctant to preallocate these structures because of this? It is a very small fraction of the total available memory that is needed for those structures (unless your structure is huge). I use this approach in my own kernel and it has worked quite well so far.

[OSwhatever]

Hi,

For which specific use case/s?

Are you saying that the CPU needs to be able to convert physical addresses back into none or more virtual addresses? Are you saying that the OS/kernel's "memory mapped file" support needs to be able to convert any physical address back into none or more virtual addresses? Is it for the OS/kernel's "copy on write shared memory" support? Is it for the OS/kernel's code to that retrieves pages from swap space back into memory? Is it for the OS/kernel's code to that determines which pages are the best pages to send to swap space?

I still think you're designing metadata for "unknown use cases". If you are, stop it - determine the use cases, then design meta-data to suit each different use case.


Cheers,

Brendan

Imagine this scenario.

Your swap algorithm has found a virtual address it wants to evict. Most swap algorithms work on virtual addresses and not physical addresses in order to find candidates, which is kind of unfortunate but anyway. Since you know the virtual address you can easily get the physical address and you can unmap it and find a new purpose for it. However, this particular page was mapped in several other processes as well. In order for the OS to find out where these are you have to have some structure that can find all virtual addresses from a physical address because we must unmap all the locations that use this particular physical page. These additional structures for each mapped page has an overhead in addition to the page table itself.

Now suddenly we get the option that we don't need to use the page table in order to do the translation in software in both directions, because we have all the metadata we need. We have a little bit of a double bookkeeping here. My previous point was that I haven't seen any CPU architecture where they have tried to merge the need of the OS and the need of the CPU translation in order to avoid this double bookkeeping .

[JAAman]

i think you are thinking about things in the wrong way -- basically you are trying to define how before why (or rather independent of why)

there are only 3 times a page may be mapped into multiple address spaces (that i can think of at the moment):

1) kernel pages
2) COW
3) shared memory


like brendan said, find your use first, and design a solution for that purpose, rather than designing for some unknown possible future scenario

rather than a single solution, each of these should be handled differently, for instance, kernel pages will always be mapped at the same address (and ideally even use the same actual page tables), and is quite simple to handle: you just unmap that page in all address spaces -- no special physical->virtual mapping required, since they should be mapped identically in all address spaces

for the other situations, there is not necessarily one single correct solution, rather the one that is best for your specific use (again, as brendan said, define your use first, then design a solution for that specific purpose) -- for instance, for shared memory you will probably want a list of addresses/address-spaces sharing that page -- this would not be a general structure for all memory, but would only exist for shared memory (it would be part of the shared memory system, which would already require some sort of bookkeeping anyway, but would not exist for all of physical memory)

also, in many designs, it is not possible to access page tables for other processes, which means freeing a shared page would require several task switches -- depending on the design of your particular memory system, you may also decide to simply lock and shared memory so that it cannot be swapped out (this would be a simple solution for a system that rarely or never uses shared memory, esp if user processes cannot create shared memory -- in which case you can easily control the number, size, and duration of shared memory areas)

[OSwhatever]

i think you are thinking about things in the wrong way -- basically you are trying to define how before why (or rather independent of why)

there are only 3 times a page may be mapped into multiple address spaces (that i can think of at the moment):

1) kernel pages
2) COW
3) shared memory


like brendan said, find your use first, and design a solution for that purpose, rather than designing for some unknown possible future scenario

rather than a single solution, each of these should be handled differently, for instance, kernel pages will always be mapped at the same address (and ideally even use the same actual page tables), and is quite simple to handle: you just unmap that page in all address spaces -- no special physical->virtual mapping required, since they should be mapped identically in all address spaces

for the other situations, there is not necessarily one single correct solution, rather the one that is best for your specific use (again, as brendan said, define your use first, then design a solution for that specific purpose) -- for instance, for shared memory you will probably want a list of addresses/address-spaces sharing that page -- this would not be a general structure for all memory, but would only exist for shared memory (it would be part of the shared memory system, which would already require some sort of bookkeeping anyway, but would not exist for all of physical memory)

also, in many designs, it is not possible to access page tables for other processes, which means freeing a shared page would require several task switches -- depending on the design of your particular memory system, you may also decide to simply lock and shared memory so that it cannot be swapped out (this would be a simple solution for a system that rarely or never uses shared memory, esp if user processes cannot create shared memory -- in which case you can easily control the number, size, and duration of shared memory areas)

In my case shared memory will be more common than you would think. For disk or any other storage it will cache a lot of pages and that's where many of the pages will be. Processes associated with the file system will do a lot of caching and therefore own a lot of pages, also they will give those pages to other processes making the page exist in several processes at one time. This include COW (before it is copied), demand paging for various code and data, memory mapped files. This is the reason I want the more general approach. However, the different types of pages should be treated differently in the swap algorithm. Kernel pages are no problem as they are non-swappable and locked.

[rdos]

I think the problem is best solved "locally". For instance, demand paging from an application requires no page metadata. All that is needed is the executable file and it's sections. The COW algorithm might benefit using metadata for userlevel pages, but it is not required (I posted an alternative solution for this a while back that requires no metadata). The FS caches ideally should use free physical memory to keep caches as large as possible, and I cannot see why and what metadata for this would contain. The FS buffer handler needs some way to keep track of used buffers anyway, so it would be better to put additional information there.

[OSwhatever]

The closest equivalent in Linux world is rmap, which is basically the same approach that I try to create. rmap in Linux is only used for certain regions because it has a significant memory overhead. My approach was that I wanted to have this by default for all user process pages. Since a structure is needed for every page where it is mapped, I rather go for a extent based structures rather than page based. This way the memory can be optimized, also the application can choose how to map the virtual region, 4Kb, 64KB or 2MB for example. However, this puts more burden on the swapping mechanism.

I wish I could go back in time and stop this virtual memory madness.