Systems for tracking uncommitted virtual memory (x86)
Posted: Sun Oct 30, 2016 5:34 am
Hello everyone,
I'm in the process of writing my virtual memory manager, and I wanted to get the opinions of some people on the forum about something. I plan on adding demand paging / page swapped / etc. to my kernel eventually, and wanted to get people's opinion on how they handle these systems in their kernel. Please move this to another forum if it's too heavy on theory, but I feel like it has enough of a focus on the x86 platform to be relevant in this forum.
For my own kernel, I was planning on having uncommitted pages (by "uncommitted pages", I mean pages which aren't mapped in to the page table, but are supposed to have something mapped to them, such as demand-paged code or not yet used data pages) use a ticket number to track what they're supposed to be holding. These ticket numbers would correspond to some kind of table in the kernel which had information about the information they're supposed to contain, such as the sector on drive where they're stored, or the file they need to load from when they end up demand-paged in. I'm kind of bad at explaining things like this, so here's a small diagram:
In the above case, I just show the first few entries in a regular page table. The first 2 are mapped as read only to some physical memory near 2MB, in this example they're probably just program code. The next two are read write, mapped just after the read only ones. They would be some of the data section for the program image. The next two are NOT present in the and will trigger a page fault if read or written to. The "Ticket Index" is an index into the table in kernel memory, it would likely look something like this:
I just arbitrarily chose to use the top 16 bits of the page table entry for the ticket index, that gives me the option of having 2^16 tickets, and leaves 15 bits spare for some kind of signature or similar, to make sure that the ticket index is actually valid. When a page fault occurs, the kernel would look at the faulting address, look it up in the page tables, see that it's unmapped, and make sure the ticket index is valid, and then use the ticket to decide what to do next.
As an example of the life cycle of some virtual address space in this system, consider a data page from a userspace program. The page starts off completely unmapped, its page table entry being 0x0000 0000. Then, when the program is being loaded in, the system sees that some pages are needed for data, and creates a ticket for this page, which says that this page is an unused data page, and should be given some physical memory to use on a page fault. Then, when the program goes to access this page during execution, it page faults trying to write to the page. The page's ticket it read, and the kernel puts maps in a new physical page for it to use, and the tickets is destroyed. Later on, the system is running low on memory, and sees that this page hasn't been used in a while, and decides to page it out. It creates a ticket for the page indicating that it has been pages out to disk. After some time, the program once again needs this page, and so it page faults again. Again, the kernel looks up the ticket, sees that the page has been paged out, and puts in a request to load the page from disk and blocks. Eventually, the page will be loaded in, and the program can resume. After some time, the page gets sent to disk again, and a similar process happens to the one described earlier. Finally, the program terminates, while the page is still out on disk. There needs to be a way to get rid of the ticket from this process, and the space it's taking up in disk, which I'm having problems with, but more on that later.
This system seems like a good solution to me, since it can handle different kinds of uncommitted pages in a generic way, and can be expanded to have more kinds of pages later (eg. different kinds of paged-out pages, for different device speeds). It also has the bonus that generic kinds of pages, such as data pages that haven't been used yet, can share a common ticket. For example, If I have 5 program data pages that are all blank, they can all refer to the same "Not yet used page that eventually needs a physical page to back it up." Also, the lookup of tickets takes constant time, since the number provided by the page fault is an index into the ticket list, so once it's checked that the ticket number is valid, the ticket can be used. And finally, since the ticket type describes the behaviours allowed for that memory, the appropriate errors can still be thrown in error conditions (eg. If a write to a ticket of type "paged-out code" happens, the kernel can still throw an error, without even having to load the page in.) But it has a few problems which I can't really figure out:
It's very likely that I would page out several pieces of a program at once, for example, say I have a program that has 32K of code, whose code is located in "/bin/prog.exe" in the VFS. If only the first 8K of the program gets used often, and the other 24K is sitting on disk, 6 separate tickets need to be made for each of those 4K chunks of the program left to load, which means 6 tickets, or 48 bytes. Not so bad for 24K of unloaded code, but if I had a large-ish program (maybe 8MB) that was mostly demand-paged, it would be 2000 tickets, or about 16K of memory, pretty bad in terms of both memory use and taking up ticket numbers. Is there a way for me to reduce the number of tickets taken by large programs like this? I imagine large pages (4MB) might be a good solution, but if I can avoid that, it would be nice, since my physical page allocator currently isn't made to handle handing out 4MB pages.
The other main problem I was having was to do with clean up. Somehow, if the process terminates either regularly or through some kind of unexpected abort, it needs to be able to clean up the tickets and any resources associated with them. The only way I can think of doing this is scanning through ALL of the process' page tables for ticket references, and making sure those tickets are taken care of, but this seems like a very bad way to do it. Is there a better way I could do cleanup?
In summary, I have come up with a system of keeping track of the properties of uncommitted memory though a list of tickets. (I doubt this is new, I just haven't seen anything like it in my limited experiences). However, it has a couple flaws, namely, groups of similar, but non identical tickets will pollute the ticket tables, and cleanup seems inefficient as of now. If anybody has and suggestions for improvements or solutions to the flaws I mentioned above, I'd love to hear about them. Also, feel free to post about your own ways of managing uncommitted memory in your kernel, I'd love to hear about them, I'm sure it's quite interesting and will provide an insight into how I can improve my own kernel.
- Mikumiku747
(This is a long post, sorry if there's any errors / typos, I'm not very good at proofreading.
)
I'm in the process of writing my virtual memory manager, and I wanted to get the opinions of some people on the forum about something. I plan on adding demand paging / page swapped / etc. to my kernel eventually, and wanted to get people's opinion on how they handle these systems in their kernel. Please move this to another forum if it's too heavy on theory, but I feel like it has enough of a focus on the x86 platform to be relevant in this forum.
For my own kernel, I was planning on having uncommitted pages (by "uncommitted pages", I mean pages which aren't mapped in to the page table, but are supposed to have something mapped to them, such as demand-paged code or not yet used data pages) use a ticket number to track what they're supposed to be holding. These ticket numbers would correspond to some kind of table in the kernel which had information about the information they're supposed to contain, such as the sector on drive where they're stored, or the file they need to load from when they end up demand-paged in. I'm kind of bad at explaining things like this, so here's a small diagram:
In the above case, I just show the first few entries in a regular page table. The first 2 are mapped as read only to some physical memory near 2MB, in this example they're probably just program code. The next two are read write, mapped just after the read only ones. They would be some of the data section for the program image. The next two are NOT present in the and will trigger a page fault if read or written to. The "Ticket Index" is an index into the table in kernel memory, it would likely look something like this:
I just arbitrarily chose to use the top 16 bits of the page table entry for the ticket index, that gives me the option of having 2^16 tickets, and leaves 15 bits spare for some kind of signature or similar, to make sure that the ticket index is actually valid. When a page fault occurs, the kernel would look at the faulting address, look it up in the page tables, see that it's unmapped, and make sure the ticket index is valid, and then use the ticket to decide what to do next.
As an example of the life cycle of some virtual address space in this system, consider a data page from a userspace program. The page starts off completely unmapped, its page table entry being 0x0000 0000. Then, when the program is being loaded in, the system sees that some pages are needed for data, and creates a ticket for this page, which says that this page is an unused data page, and should be given some physical memory to use on a page fault. Then, when the program goes to access this page during execution, it page faults trying to write to the page. The page's ticket it read, and the kernel puts maps in a new physical page for it to use, and the tickets is destroyed. Later on, the system is running low on memory, and sees that this page hasn't been used in a while, and decides to page it out. It creates a ticket for the page indicating that it has been pages out to disk. After some time, the program once again needs this page, and so it page faults again. Again, the kernel looks up the ticket, sees that the page has been paged out, and puts in a request to load the page from disk and blocks. Eventually, the page will be loaded in, and the program can resume. After some time, the page gets sent to disk again, and a similar process happens to the one described earlier. Finally, the program terminates, while the page is still out on disk. There needs to be a way to get rid of the ticket from this process, and the space it's taking up in disk, which I'm having problems with, but more on that later.
This system seems like a good solution to me, since it can handle different kinds of uncommitted pages in a generic way, and can be expanded to have more kinds of pages later (eg. different kinds of paged-out pages, for different device speeds). It also has the bonus that generic kinds of pages, such as data pages that haven't been used yet, can share a common ticket. For example, If I have 5 program data pages that are all blank, they can all refer to the same "Not yet used page that eventually needs a physical page to back it up." Also, the lookup of tickets takes constant time, since the number provided by the page fault is an index into the ticket list, so once it's checked that the ticket number is valid, the ticket can be used. And finally, since the ticket type describes the behaviours allowed for that memory, the appropriate errors can still be thrown in error conditions (eg. If a write to a ticket of type "paged-out code" happens, the kernel can still throw an error, without even having to load the page in.) But it has a few problems which I can't really figure out:
It's very likely that I would page out several pieces of a program at once, for example, say I have a program that has 32K of code, whose code is located in "/bin/prog.exe" in the VFS. If only the first 8K of the program gets used often, and the other 24K is sitting on disk, 6 separate tickets need to be made for each of those 4K chunks of the program left to load, which means 6 tickets, or 48 bytes. Not so bad for 24K of unloaded code, but if I had a large-ish program (maybe 8MB) that was mostly demand-paged, it would be 2000 tickets, or about 16K of memory, pretty bad in terms of both memory use and taking up ticket numbers. Is there a way for me to reduce the number of tickets taken by large programs like this? I imagine large pages (4MB) might be a good solution, but if I can avoid that, it would be nice, since my physical page allocator currently isn't made to handle handing out 4MB pages.
The other main problem I was having was to do with clean up. Somehow, if the process terminates either regularly or through some kind of unexpected abort, it needs to be able to clean up the tickets and any resources associated with them. The only way I can think of doing this is scanning through ALL of the process' page tables for ticket references, and making sure those tickets are taken care of, but this seems like a very bad way to do it. Is there a better way I could do cleanup?
In summary, I have come up with a system of keeping track of the properties of uncommitted memory though a list of tickets. (I doubt this is new, I just haven't seen anything like it in my limited experiences). However, it has a couple flaws, namely, groups of similar, but non identical tickets will pollute the ticket tables, and cleanup seems inefficient as of now. If anybody has and suggestions for improvements or solutions to the flaws I mentioned above, I'd love to hear about them. Also, feel free to post about your own ways of managing uncommitted memory in your kernel, I'd love to hear about them, I'm sure it's quite interesting and will provide an insight into how I can improve my own kernel.
- Mikumiku747
(This is a long post, sorry if there's any errors / typos, I'm not very good at proofreading.
)