Forward Page Tables vs. Inverted Page Tables

yarchive.net

28 points·luu··3 comments

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/cra...; see also http://www.cs.columbia.edu/~krj/os/lectures/L17-LinuxPaging.....

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.

> 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.

Reply on news.ycombinator.com