Nested page tables (virtualization article) question

[Onox]

Hi,

I have an operating systems exam this week, and virtualization is part of it, but the course that dealt with this had a substitute teacher whose slides are very incomplete... So I tried to write a short summary about shadow page tables and nested page tables using different resources. I found this article here on AnandTech useful, but there is something that I don't understand : on the linked page, I don't understand that part in bold :

“There is only one downside: nested paging or EPT makes the virtual to real physical address translation a lot more complex if the TLB does not have the right entry. For each step we take in the blue area, we need to do all the steps in the orange area. Thus, four table searches in the "native situation" have become 16 searches (for each of the four blue steps, four orange steps).”

This seems to imply that for each VA → PA mapping in the light blue part, we would need to check all PA →MA mappings in the orange part. Why would we need to do that ? (These are tree structures, aren't they ?) And where does the 4/16 come from ? Is it a specific example ?

Thanks

 

[KingFatty]

I believe it's referring to the example when you have a TLB miss. So you have to walk all the tables and figure out what the actual information is. So you have to walk the four blue tables. But, that's just for native. By nesting, you have 4 orange table for each blue table. So, you'd need to walk sixteen tables. All because one entry in the TLB was missing or wrong.