page table walking in early linux

[ITchimp]

I have a question regarding the page table walking code. I remember (I could be wrong) in early version of linux,
there are code for doing page table walking if there is tlb miss... but I am not 100% sure... can someone
enlighten me on the history of MMU for x86, was the current hardware page table walking present in the early days
of x86 architecture ie, 80386 ?

[thewrongchristian]

I have a question regarding the page table walking code. I remember (I could be wrong) in early version of linux,
there are code for doing page table walking if there is tlb miss... but I am not 100% sure... can someone
enlighten me on the history of MMU for x86, was the current hardware page table walking present in the early days
of x86 architecture ie, 80386 ?

Yes. i386 (where paging was introduced) has always had hardware page table walking.

Prior x86 didn't provide paging at all.

[bzt]

Not entirely sure what you mean by "table walk". In order to provide virtual memory, the MMU must translate linear addresses to physical ones, which involves interpreting the page tables. If you meant that, then the answer is yes.

If you meant an instruction that the programmer can use to do a table walk to detect errors (like the "AT" instruction on ARM), then the answer is no. Page translation is hidden from the programmer, and entirely in the realm of the MMU (which is fine because it is the programmer who provides the page tables, so they should know what's in them).

Doing a table walk in software is simple: first map the root page at a fixed address (let's say 0x10000) call this "uint32_t* tmp". Then take a linear address virtaddr, shift it and mask it to get the first page index. Get the address from tmp[idx]. Repeat the process: map the new address at tmp, and get the next index from virtaddr. You can do any checks or validation on the page table entry you'd like during this. Stop when there's only 12 bits left in virtaddr.

This scheme works for both 32 and 64 bit systems, the only difference is the number of bits to shift and mask. On 32 bit (early days of x86) you have 10+10+12, while on 64 bits (recent x86) you have 9+9+9+9+12. The algorithm is the same. This should make this clear:

So map CR3 at tmp, and get tmp[(virtaddr >> (9+9+9+12)) & 0x1FF]. Map this at tmp and get tmp[(virtaddr >> (9+9+12)) & 0x1FF] etc. This did not changed ever since paging was introduced (only the number of bits used).

Cheers,
bzt

[Octocontrabass]

Not entirely sure what you mean by "table walk".

In some CPU architectures, a TLB miss causes an exception and it's up to the programmer to fill the TLB with a new mapping. That process is called a "table walk" or "page walk" or "page table walk".

In x86, the CPU automatically walks the page table upon a TLB miss, and the TLB is mostly transparent to the programmer (aside from the need to invalidate stale TLB entries). It has worked this way since paging was introduced in the 80386.

[linguofreak]

I have a question regarding the page table walking code. I remember (I could be wrong) in early version of linux,
there are code for doing page table walking if there is tlb miss... but I am not 100% sure... can someone
enlighten me on the history of MMU for x86, was the current hardware page table walking present in the early days
of x86 architecture ie, 80386 ?

It's most likely not a difference between early and modern Linux, but between the Linux memory management code for different architectures. Some architectures (e.g, x86) only ever handle TLB misses in hardware. Some force the OS to walk the page tables when a translation isn't in the TLB. Some architectures make it implementation dependent. As a result, any OS that runs on a large number of different architectures is likely to have to be able to work in both kinds of MMU environment.

[ITchimp]

thanks!bzt and linguofreak... i worship you both!

[linguofreak]

thanks!bzt and linguofreak... i worship you both!

No need to worship me. I'm not a god or anything.