4 ms·

Forward Page Tables vs. Inverted Page Tables

28 points by luu 12y ago

rayiner 12y ago
The whole point of inverted page tables is that when size(virtual mappings) >> size(physical memory), you can avoid eating up a lot of space with page tables. With an inverted page table, you only need one PTE per physical page, versus one PTE per virtual page. The problem is that in practice you need to keep information about each virtual page anyway, or at least it's very convenient to be able to do so. For example, the Linux MM stores (or at least did last time I looked), uses the PTE to store the location of swapped-out pages. The UVM paper describes very thoroughly why it's useful to have per-virtual page state around: https://www.usenix.org/legacy/event/usenix99/full_papers/cranor/cranor.pdf; https://www.usenix.org/legacy/event/usenix99/full_papers/cra... see also http://www.cs.columbia.edu/~krj/os/lectures/L17-LinuxPaging.pdf http://www.cs.columbia.edu/~krj/os/lectures/L17-LinuxPaging.....
- StillBored 12y ago
  The other point is that TLB misses can be satisfied with a single cache line fill. Or that is the theory, as told to me by a big inverted page table advocate a couple of years before of Linus's comments. Personally, I tend to favor Linus's perspective. Particularly because making an optimal decision about how large the page table hash is, turns out to be pretty hard to do at runtime. Changing the size is even harder. This means that you either waste a lot of unnecessarily memory on the inverted tables, or you tend to take excessive page table misses, and waste a lot more than 3 cache line fills satisfying them.
closetnerd 12y ago
"I don't know about you, but to me the difference between technological thrill and masturbation is that real technology actually matters to real people." Linus Torvalds
nextw33k 12y ago
> I even wrote my masters thesis on why it was done the way it was done (the only actual academic use I ever got out of the whole Linux exercise ;) Brilliant sound bite. I've always love academic work, however it does really account for a very small portion of actually creating something.

28 points by luu 12y ago

The whole point of inverted page tables is that when size(virtual mappings) >> size(physical memory), you can avoid eating up a lot of space with page tables. With an inverted page table, you only need one PTE per physical page, versus one PTE per virtual page. The problem is that in practice you need to keep information about each virtual page anyway, or at least it's very convenient to be able to do so. For example, the Linux MM stores (or at least did last time I looked), uses the PTE to store the location of swapped-out pages. The UVM paper describes very thoroughly why it's useful to have per-virtual page state around: https://www.usenix.org/legacy/event/usenix99/full_papers/cranor/cranor.pdf; https://www.usenix.org/legacy/event/usenix99/full_papers/cra... see also http://www.cs.columbia.edu/~krj/os/lectures/L17-LinuxPaging.pdf http://www.cs.columbia.edu/~krj/os/lectures/L17-LinuxPaging.....

StillBored 12y ago
The other point is that TLB misses can be satisfied with a single cache line fill. Or that is the theory, as told to me by a big inverted page table advocate a couple of years before of Linus's comments. Personally, I tend to favor Linus's perspective. Particularly because making an optimal decision about how large the page table hash is, turns out to be pretty hard to do at runtime. Changing the size is even harder. This means that you either waste a lot of unnecessarily memory on the inverted tables, or you tend to take excessive page table misses, and waste a lot more than 3 cache line fills satisfying them.

closetnerd 12y ago

"I don't know about you, but to me the difference between technological thrill and masturbation is that real technology actually matters to real people." Linus Torvalds

nextw33k 12y ago

> I even wrote my masters thesis on why it was done the way it was done (the only actual academic use I ever got out of the whole Linux exercise ;) Brilliant sound bite. I've always love academic work, however it does really account for a very small portion of actually creating something.