Rendered at 12:45:37 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
monocasa 2 days ago [-]
While this article correctly points out issues with tree based page tables, it fails to describe how the other option (a PowerPC style hashed page table) being considered by Torvalds, et al. is any better. And a cursory glance doesn't appear to support them being better under the cases described; each issue seems like it'd be the same or worse under hashed page tables.
For one, the hash on PowerPC is over the virtual address and a VSID (virtual segment ID) which functionally gets used as an address space ID[0]. That means that hashed page tables also have separate entries for each process mapping the same physical page.
Since the hashed page table is one (physically!) contiguous structure, that means that all of the same NUMA tradeoffs also apply to it as well.
Because it's based on a hash of the virtual address, you have the same issues with partial residency bloat of the structure as you either have to size the whole page table up in powers of two during hash collisions[1], or you have to treat the whole thing like a large last chance TLB and have a separate software page table to hold your ground truth (which will probably just be a tree based table anyway).
And on top of that, grabbing 8 spatially related PTEs at once rather than just 8 that happened to hash to the same thing also tends to reduce memory bandwidth rather than just latency for the same reasons that caching and prefetching works at all. There's a good chance the other seven PTEs are actually going to be needed soon if you grabbed their sibling, but a hashed page table has you generally grabbing 8 cache lines of PTEs for 8 virtually contiguous pages, for an 8x increase in bandwidth too for the same likely operations.
All of the references are great though; I really enjoyed reading through them. I hadn't stayed current with the state of the art since 2020ish.
0 - A little different than that since each VSID is just a subset of an address space and each process needs a handful of them rather than one, but close enough for this conversation.
1 - PowerPC hashed page tables give you two probes into buckets (PTEGs, or Page Table Entry Groups) that can each hold 8 PTEs.
winocm 16 hours ago [-]
Rest in peace, IBAT and DBAT...
And good riddance to the 603's software managed TLB (and associated interrupt handlers).
hinkley 1 days ago [-]
Something that was true in 2003 can be not true in 2026 with absolutely no contradiction. It’s a problem I’ve had multiple times with people getting bristly assuming that a push to replace a broken but “working” subsystem with something new and better necessitates a confession of guilt by the people who wrote the original system.
As problem domains scale up by orders of magnitude, as they have since Linus ranted on 2003, the correct solution changes. Sometimes several times. It was the right solution, but it might not be the right solution now, and both are correct.
Veserv 9 hours ago [-]
This is easily solved by just using large pages. On x86-64 that is 2 MB per one 8 byte entry which is ~1/256k overhead instead of 1/512.
On a contiguous shared data area on the order of 1 GB, you are only tolerating a 2 MB overallocation on 1 GB of data area (~1/512 overhead), but saving ~2 MB of PTEs per process sharing the data (including the first) so you can come out ahead even if you are sharing at all.
At 300 GB you can even reasonably use 1 GB pages for a even more ridiculous ~1/128M overhead and effectively never run into the problem.
Sopel 2 days ago [-]
At least on windows zombie processes may use no memory but still keep >=32KiB page table. So in this [extreme case of an AMD iGPU driver bug](https://superuser.com/questions/1838566/how-to-identify-a-dr...) close to 100% of memory was used by page tables (or would if pushed far enough)
shellpipe 2 days ago [-]
That's crazy! I appreciate you bringing this up. I will add this case as an interesting aside later.
Edit: added.
sweetjuly 1 days ago [-]
relatedly, it is also worth considering that your VA allocation behavior can have significant impacts on your page table costs.
Some programs like to, for example, map allocations at random VAs for security reasons. If you're only using a single page, this makes your worst case cost 1 page for actual data + 2-3 pages of tables (depending on your CPU architecture and address space size). If you do this very often, this can get very expensive in a hurry.
shieldagent 1 days ago [-]
[flagged]
mastax 2 days ago [-]
Sounds like a reason to prefer multi threading over multi processing.
arakageeta 2 days ago [-]
Sure, if you hate virtual memory protections. Why don't all of those Android binder-using apps just run in one big process?
kccqzy 2 days ago [-]
That’s the argument in The Birth and Death of YavaScript.
int0x29 1 days ago [-]
Which predates specter by three years
HackerThemAll 1 days ago [-]
It was rather towards one-process-per-client such as PostgreSQL server or Apache HTTPd (long obsolete, fortunately). Hopefully PostgreSQL will switch to worker threads soon, and as for Apache HTTPd, I don't care.
For one, the hash on PowerPC is over the virtual address and a VSID (virtual segment ID) which functionally gets used as an address space ID[0]. That means that hashed page tables also have separate entries for each process mapping the same physical page.
Since the hashed page table is one (physically!) contiguous structure, that means that all of the same NUMA tradeoffs also apply to it as well.
Because it's based on a hash of the virtual address, you have the same issues with partial residency bloat of the structure as you either have to size the whole page table up in powers of two during hash collisions[1], or you have to treat the whole thing like a large last chance TLB and have a separate software page table to hold your ground truth (which will probably just be a tree based table anyway).
And on top of that, grabbing 8 spatially related PTEs at once rather than just 8 that happened to hash to the same thing also tends to reduce memory bandwidth rather than just latency for the same reasons that caching and prefetching works at all. There's a good chance the other seven PTEs are actually going to be needed soon if you grabbed their sibling, but a hashed page table has you generally grabbing 8 cache lines of PTEs for 8 virtually contiguous pages, for an 8x increase in bandwidth too for the same likely operations.
All of the references are great though; I really enjoyed reading through them. I hadn't stayed current with the state of the art since 2020ish.
0 - A little different than that since each VSID is just a subset of an address space and each process needs a handful of them rather than one, but close enough for this conversation.
1 - PowerPC hashed page tables give you two probes into buckets (PTEGs, or Page Table Entry Groups) that can each hold 8 PTEs.
And good riddance to the 603's software managed TLB (and associated interrupt handlers).
As problem domains scale up by orders of magnitude, as they have since Linus ranted on 2003, the correct solution changes. Sometimes several times. It was the right solution, but it might not be the right solution now, and both are correct.
On a contiguous shared data area on the order of 1 GB, you are only tolerating a 2 MB overallocation on 1 GB of data area (~1/512 overhead), but saving ~2 MB of PTEs per process sharing the data (including the first) so you can come out ahead even if you are sharing at all.
At 300 GB you can even reasonably use 1 GB pages for a even more ridiculous ~1/128M overhead and effectively never run into the problem.
Edit: added.
Some programs like to, for example, map allocations at random VAs for security reasons. If you're only using a single page, this makes your worst case cost 1 page for actual data + 2-3 pages of tables (depending on your CPU architecture and address space size). If you do this very often, this can get very expensive in a hurry.