The Place to Start for Operating System Developers
http://f.osdev.org/
No. You use your own data structures to keep track of the allocations, and only write to the page table as necessary. For virtual memory, the normal recommendation is to create a self-balancing range-tree containing all virtual memory areas. Indeed, creating one for every process. In it you keep track of where the nominal allocations are, what files they connect to (at what offset) and what access permissions are set. If someone needs memory, you can walk through the VMAs and find if there is a hole somewhere matching the requirements of the allocation. Then add a new VMA for that address. Note that you don't need to write to the page tables right away when adding a mapping, and when removing or changing a mapping, it is enough to clear out the affected mappings in the system call itself. In the page-fault handler, you would then look up the VMA for the fault address, and either allocate a new page (if mapping is anonymous), enqueue a request to read a file (if mapping is file-backed), or fault the process (in UNIX-like systems: Send SIGSEGV).ngx wrote:I was writing my memory manager and finished nearly everything except the allocation method. I have no idea of how I should keep track of which pages are free and which aren't, so I could easily give one on a user request - should I just search through the whole page table tree to find one that has the present bit off and then set the bit to on and map it to a physical address, but if a user needs several pages one after another, should I search for place where enough pages are free - considering that I am in long mode with PML4, it could take tons of time?
What @nullplan tried to say is, use two separate structures. It doesn't really matter what data structure you use:ngx wrote:I don't really understand, is this like a linked list?
Nope, don't mix allocated address and free pages. You'll need two separate allocation layer at a minimum: a PMM and a VMM. For the PMM the address doesn't matter (you just ask for a physical page and add it to the paging table), handling the address space (and hence mapped addresses) is a job for the VMM. Since both the PMM and VMM should deal with pages, you'll probably need a third level too, libc malloc, which can allocate arbitrary sized memory and returns virtual addresses to your applications.ngx wrote: If yes, then I would think it would be enormous as each node is at least 128 bits wide(for the page address and the pointer to next node) if we have no metadata like you said and that is only for one process. SO if I understand correctly - I just add the allocated addresses at the end like in a linked list, and then to allocate I just have a variable set to some certain address which I increase with every allocation, and I just search if this address is in the tree and if it isn't I allocate it or otherwise I increase it and search again if it is free? Am I right?
And how do you record the RAM used by the page table itself? You need to keep track of free RAM in the system independently to page tables. The first is global (you have only one RAM), and the second changes on each task switch (you have many page tables, one for each process).rdos wrote:I don't have lists of free pages. The present bit in the page table will tell if a page is in use
You said you know which pages are mapped or not. Then this is simple, as unmapped pages must be unallocated too.ngx wrote:I could track which pages are mapped/not mapped using the present flag on the page. The problem I have is that I can't think of a data structure that could be used to know which virtual memory pages are free(by free I mean not mapped and not allocated)
The request in this case would be a page fault, meaning you'll know exactly where to map the new page (CR2). On exit(), you'll have to walk through the page tables, and free all physical addresses (recorded in the tables as well as the physical address of the table itself). Not sure what this has to do with MMIO. You just map those as you would map any free memory (maybe with different bits set in the table, but that's all). It doesn't matter where the MMIO appears in the address space.ngx wrote:and which are used(allocated and mapped/not mapped) so I could allocate them on a request or map them to MMIO...
Actually this is exactly what dlmalloc does for example. With one little modification, it records what's not allocated. When you free a memory area, dlmalloc puts a linked list pointer in that memory area, which points to the next free memory block. It is on you to choose the correct algorithm that doesn't need to iterate through the entire chain in order to work correctly. Such algorithms do exist.ngx wrote:There could be a linked list of all allocated pages, but searching through it every time to check if some page is free would take loads of time and with more pages being allocated it would take longer and longer
For PMM, keeping track of free pages I believe bitmap is still the best. This is RAM size / page size / 8 bytes, for example with 4k pages and 16G RAM would require 512K of memory, definitely less than gigabytes. Other alternatives buddy and SLAB.ngx wrote:stack would not work here and a bitmap would take several million of GB(and also I don't really like bitmaps bitmaps), so I would really appreciate advice on the data structure to use and how to use it in this context.
So if a program asks your OS for more memory, you iterate over the page tables to find a free spot in VM space to put the new memory? Seems inefficient, especially with address space as vast as it is on x86_64.rdos wrote:I don't have lists of free pages. The present bit in the page table will tell if a page is in use, and there are a few more bits that can be used for aliasing, second-chance and copy-on-write. When the present bit is not set, there are 31 (or 63) bits free for house keeping. I reserve bit 1 for "allocated" but not yet referenced. This is the way I allocate memory in the application by scanning for pages where bit 1 & 0 are both 0 and then set bit 1 to 1. When the application tries to use it the pagefault handler will see that it is reserved and allocate a physical page, set the present bit and re-execute the instruction. For images, I use selector:offset in the page table that will be called by the pagefault handler. The PE loader uses this so it can dynamically load pages in the executable on demand.
I don't anticipate supporting fork() myself, I think it is a bad way to start a new process. All of its use cases can be handled by either pthread_create() or posix_spawn(). Well, almost all. But I am surprised to hear you of all people proclaim your support for fork().rdos wrote:The only thing that this model cannot handle is fork. When I added fork I needed to create lists of pages & reference counts for forked processes, but if you don't support fork, you really don't need this.
Binary tree. Self-balancing binary range tree. You will have to do some searching. The red-black tree seems to be favored among OS enthusiasts, though I have always been partial to the Anderson tree myself. The "range" part of that description means that every tree node has a range of keys instead of just one key. In this case, all nodes are keyed by their address and length. When handling page faults, the correct VMA can be quickly identified by just walking the tree, and even failure can be handled quickly. And once you have the VMA, you can quickly identify if it just needs a physical page to back it, or if the page fault was spurious (apparently it can sometimes happen that you get a page-fault although nothing was wrong, and just returning from the #PF handler makes the problem go away). Or if it really was a bad fault and you need to reprimand the process in whatever way you see fit.There could be a linked list of all allocated pages, but searching through it every time to check if some page is free would take loads of time There could be a linked list of all allocated pages, but searching through it every time to check if some page is free would take loads of time and with more pages being allocated it would take longer and longer, stack would not work here and a bitmap would take several million of GB(and also I don't really like bitmaps bitmaps), so I would really appreciate advice on the data structure to use and how to use it in this context.and with more pages being allocated it would take longer and longer, stack would not work here and a bitmap would take several million of GB(and also I don't really like bitmaps bitmaps), so I would really appreciate advice on the data structure to use and how to use it in this context.ngx wrote:The problem I have is that I can't think of a data structure that could be used to know which virtual memory pages are free(by free I mean not mapped and not allocated) and which are used(allocated and mapped/not mapped) so I could allocate them on a request or map them to MMIO...
Stack and bitmap are more for physical memory, anyway.ngx wrote:There could be a linked list of all allocated pages, but searching through it every time to check if some page is free would take loads of time and with more pages being allocated it would take longer and longer, stack would not work here and a bitmap would take several million of GB(and also I don't really like bitmaps bitmaps), so I would really appreciate advice on the data structure to use and how to use it in this context.
The problem with iterating over the page tables rather than the VMAs is that this way, allocation becomes linear in the number of pages rather than the number of VMAs. To illustrate the difference: One firefox instance on my system right now has 567 VMAs, but a virtual size of 642410 pages (if all of them are small pages, but I think they are).ngx wrote:So I would have a pointer to the start of the heap(4096 aligned) right after the end of the executable and when a user requests for a page I would just check if the pointer points to a free page and if yes mark it as used and return or otherwise move forwards until a free page is found and do the same thing, if multiple pages are required then there will be a place found where all of them fit one after another. If a page is freed then it's present bit will be removed and it will become free and will be added to the linked list. The linked list of free pages will be used by the allocator to allocate a page if the user only requests for one page, otherwise the pages will be allocated starting from the heap pointer.
I still don't get it as you're mixing free pages with allocation. You shouldn't. So "free page" only exists in context of physical memory allocator, but not on other levels. At VMM, there's no free page, just mapped ones. At libc malloc level, you have allocated and free areas of arbitrary size (not page sized). If the application frees memory, then it is up to the allocator if the mapped pages are returned to the PMM or not. With dlmalloc, you cannot return the pages because you have free memory pointers on them. On the other hand if the application allocates again, there's no need to call the VMM and the PMM (which can be slow), because pages are already mapped into the address space, and the allocator does not need extra memory to keep track of memory because pointers are simply stored in free memory areas.ngx wrote:Ok thanks. I thought of an algorithm and would be grateful if you could point out some things that I could change in it:
So I would have a pointer to the start of the heap(4096 aligned) right after the end of the executable and when a user requests for a page I would just check if the pointer points to a free page and if yes mark it as used and return or otherwise move forwards until a free page is found and do the same thing, if multiple pages are required then there will be a place found where all of them fit one after another. If a page is freed then it's present bit will be removed and it will become free and will be added to the linked list. The linked list of free pages will be used by the allocator to allocate a page if the user only requests for one page, otherwise the pages will be allocated starting from the heap pointer.
Code: Select all
head -> block at 0 size 256 -> block at 768 end of chainCode: Select all
head[size 8] -> end
head[size 16] -> end
head[size 32] -> end
...
head[size 256] -> block at 0 -> end
head[size 512] -> end
...
overall tail -> block at 768 end of chainThose are allocated automatically by the pagefault handler. When the process terminates, these are freed again automatically.bzt wrote:And how do you record the RAM used by the page table itself?rdos wrote:I don't have lists of free pages. The present bit in the page table will tell if a page is in use
Physical memory is handled using bitmaps.bzt wrote: You need to keep track of free RAM in the system independently to page tables. The first is global (you have only one RAM), and the second changes on each task switch (you have many page tables, one for each process).