4 ms·

What other kinda of optimizations can be made by using the page table? For example, from what I understand, allocators operate on virtual memory, so if for exa

by eulgro 2y ago

What other kinda of optimizations can be made by using the page table? For example, from what I understand, allocators operate on virtual memory, so if for example a vector increases in size past its capacity, memory has to be reallocated and the existing content copied. Wouldn't it be possible to perform that copy by updating virtual addresses in the page table, with no copy actually being performed in physical memory?

ncruces 2y ago
If the array is large enough to span a page, and the memory was obtained from the system with mmap, you can extend it with mremap, yes. https://man7.org/linux/man-pages/man2/mremap.2.html https://man7.org/linux/man-pages/man2/mremap.2.html
superjan 2y ago
There’s a great paper from the group of Emery Berger, where they merge memory pages that become sparse. A kind of garbage collection for C and C++ languages. There’s also a good presentation about it on youtube. https://arxiv.org/abs/1902.04738 https://arxiv.org/abs/1902.04738 The presentation: https://youtu.be/c1UBJbfR-H0 https://youtu.be/c1UBJbfR-H0
- eulgro 2y ago
  Interesting! Thanks for the link.
giomasce 2y ago
That still requires you to plan how you use the virtual address space, though. You can't just add more memory pages on the back of your vector if you've already started using those virtual memory locations for other stuff. So you have to know in advance how much space your vector might end up using, and carefully avoid placing anything else there. If you're willing to come up with such an estimate, and if your OS is happy to overcommit memory (and I think Linux is, by default at least), then you can just malloc() all that memory in the first place. With overcommitting no physical page will be used to back your virtual memory block until you really use it. If your system doesn't do overcommitting, then I guess that with some mmap() trickery (using the appropriate flags) you could do more or less the same thing, reserving the virtual address space that you need and then actually backing with memory as you need.
junon 2y ago
Technically yes, you can do copy-on-write semantics, which marks both the original and "copied" page as read-only, and the first write to either virtual page causes a page fault in the kernel (access violation) prompting a physical page allocation, copying the page, and then updating both virtual page table entries' permissions to be RW, then the equivalent of `invlpg` to flush them out of the TLB, before returning to the program to re-try the write instruction. However this gets tricky with heap allocators since they often pack `malloc`-like allocations into the same page using some allocation scheme (e.g. buddy allocation, etc.). Though you can typically bypass malloc-like, in-process allocators to handle page mappings yourself, it's just a little more cumbersome. This is actually how "virtual allocation" (I think is the term, don't quote me) happens; if you `malloc` a very large space on many modern OSes, you get a pointer back and there is an allotment in the process's virtual address space registered, but no page tables are actually updated (the kernel can assume they're "not present", meaning that there is no read nor write availability; any memory operation with that range causes a page fault). Upon any page in that range being accessed for the first time, the page fault handler sees it's part of that otherwise very large segment and will allocate in physical memory to that virtual page, then return. It allows for e.g. allocating a VERY large sparse array of items (even terabytes!) that might otherwise exceed the size of physical memory actually available to the system, with the assumption that it'll never actually be fully populated (or at least populated across enough memory pages such that you exhaust 'real', physical memory). This is also how file mapping works. You file map something from the filesystem, and the kernel keeps a cache of read pages from that file; memory reads and writes cause page faults if they haven't been read in (and cached), prompting a read from the disk storage into a physical page, updating the page tables, and resuming the faulting thread. It also allows the kernel to selectively reclaim less-frequently-used file mapped pages for higher priority allocations at any time really, since the next time the program tries to access that page, the kernel just faults again, reads it into a new page, and updates the tables. It's entirely transparent to the process. I'm designing a novel kernel at the moment and some of these sorts of possibilities are what I find the more interesting parts of design, actually. I find them to be underutilized to some extent even in modern kernels :)
HALtheWise 2y ago
One example that comes to mind is the (abandoned) proposal for safe arena allocation in Go. It takes advantage of the fact that 64 bit computers have absolutely massive virtual memory, so that "freed" memory can be permanently unmapped from virtual memory in order to make any future accesses an error instead of a use-after-free bug. https://github.com/golang/go/issues/51317 https://github.com/golang/go/issues/51317

by eulgro 2y ago

ncruces 2y ago

If the array is large enough to span a page, and the memory was obtained from the system with mmap, you can extend it with mremap, yes. https://man7.org/linux/man-pages/man2/mremap.2.html https://man7.org/linux/man-pages/man2/mremap.2.html

superjan 2y ago

There’s a great paper from the group of Emery Berger, where they merge memory pages that become sparse. A kind of garbage collection for C and C++ languages. There’s also a good presentation about it on youtube. https://arxiv.org/abs/1902.04738 https://arxiv.org/abs/1902.04738 The presentation: https://youtu.be/c1UBJbfR-H0 https://youtu.be/c1UBJbfR-H0

eulgro 2y ago
Interesting! Thanks for the link.

giomasce 2y ago

That still requires you to plan how you use the virtual address space, though. You can't just add more memory pages on the back of your vector if you've already started using those virtual memory locations for other stuff. So you have to know in advance how much space your vector might end up using, and carefully avoid placing anything else there. If you're willing to come up with such an estimate, and if your OS is happy to overcommit memory (and I think Linux is, by default at least), then you can just malloc() all that memory in the first place. With overcommitting no physical page will be used to back your virtual memory block until you really use it. If your system doesn't do overcommitting, then I guess that with some mmap() trickery (using the appropriate flags) you could do more or less the same thing, reserving the virtual address space that you need and then actually backing with memory as you need.

junon 2y ago

Technically yes, you can do copy-on-write semantics, which marks both the original and "copied" page as read-only, and the first write to either virtual page causes a page fault in the kernel (access violation) prompting a physical page allocation, copying the page, and then updating both virtual page table entries' permissions to be RW, then the equivalent of `invlpg` to flush them out of the TLB, before returning to the program to re-try the write instruction. However this gets tricky with heap allocators since they often pack `malloc`-like allocations into the same page using some allocation scheme (e.g. buddy allocation, etc.). Though you can typically bypass malloc-like, in-process allocators to handle page mappings yourself, it's just a little more cumbersome. This is actually how "virtual allocation" (I think is the term, don't quote me) happens; if you `malloc` a very large space on many modern OSes, you get a pointer back and there is an allotment in the process's virtual address space registered, but no page tables are actually updated (the kernel can assume they're "not present", meaning that there is no read nor write availability; any memory operation with that range causes a page fault). Upon any page in that range being accessed for the first time, the page fault handler sees it's part of that otherwise very large segment and will allocate in physical memory to that virtual page, then return. It allows for e.g. allocating a VERY large sparse array of items (even terabytes!) that might otherwise exceed the size of physical memory actually available to the system, with the assumption that it'll never actually be fully populated (or at least populated across enough memory pages such that you exhaust 'real', physical memory). This is also how file mapping works. You file map something from the filesystem, and the kernel keeps a cache of read pages from that file; memory reads and writes cause page faults if they haven't been read in (and cached), prompting a read from the disk storage into a physical page, updating the page tables, and resuming the faulting thread. It also allows the kernel to selectively reclaim less-frequently-used file mapped pages for higher priority allocations at any time really, since the next time the program tries to access that page, the kernel just faults again, reads it into a new page, and updates the tables. It's entirely transparent to the process. I'm designing a novel kernel at the moment and some of these sorts of possibilities are what I find the more interesting parts of design, actually. I find them to be underutilized to some extent even in modern kernels :)

HALtheWise 2y ago

One example that comes to mind is the (abandoned) proposal for safe arena allocation in Go. It takes advantage of the fact that 64 bit computers have absolutely massive virtual memory, so that "freed" memory can be permanently unmapped from virtual memory in order to make any future accesses an error instead of a use-after-free bug. https://github.com/golang/go/issues/51317 https://github.com/golang/go/issues/51317