0

I've been trying to figure out this stuff for years, but every time I don't understand. I understand quite well how paging, page tables and page table directories work in Linux, I just don't get why they're actually needed.

The problem why we need paging and page table levels (Linux uses 4 levels) seems to be the fact that you can't load all memory in the same moment. But can't we just load a selected amount of pages and addresses without all of the directories thing?

I know we need to learn where a certain frame is located in physical memory, but why can't we directly retrieve a certain subset of a big page table? What issues would that cause? I understand that if we didn't use pages + offsets the whole thing'd be too big, but do the directories really solve anything?

There is a lot of discussion on how different systems divide the bits of an address in order to structure the page table levels, but at the end of the day we're always gonna have 32/64 bits for an entry. We won't be able to address more than that (except with tricks on the cr3 register like PAE does), what's the point of splitting them? In the end, how is having (I'll simplify) "directory 3, subdirectory 5, page 7, offset 2" better than just saying "address 3572"?

Even worse, if the CPU didn't help us (I guess it has built-in circuits to do all of the process in 1 clock cycle? Not really sure!) wouldn't it be a lot less efficient to have to retrieve all of the directories and subdirectories at every memory access rather than directly retrieving the logical/physical memory mapping and then accessing the needed address?

4
  • 2
    Say you have 48 bits of effective address space, and your pages are 4k (12 bits) in size. This means you need to translate potentially 36 bits. If you have this in a linear array (your address 3572 example sort of implies this), and you need 8 bytes per entry, then this array will be 512Gb. Almost all of these will probably be set to indicate an invalid mapping. Whilst machines are getting bigger most do not have this sort of amount of memory. Splitting it into a number of levels reduces the space, for example if the first level is not 3 then it is invalid.
    – icarus
    Oct 24, 2019 at 0:21
  • @icarus Oh I see! So the thing is, I can directly say (to use my shitty decimal example) "all directory 3 is empty" and save myself from writing 8 bytes*1000 entries of basically "this page is empty"?
    – memememe
    Oct 28, 2019 at 10:21
  • I would use "invalid mapping" rather than "empty" in the example phrase, but yes.
    – icarus
    Oct 28, 2019 at 13:41
  • You're right, they do not represent an empty page but a page not mapped to a segment. Consider doing an answer so I can accept it.
    – memememe
    Oct 30, 2019 at 13:09

1 Answer 1

2

The reason for having the multiple levels is to save space.

Consider what would be needed if there were not multiple levels. If there are 48 bits of address space (no current x86_64 cpu gives you the full 64 bits), and you are using a 4k byte page size (12 bits), then you have 2 to the power of 36 pages.

If you could fit the mapping information into 64 bits (8 bytes), then you would need 8 * 2**36 bytes or 512Gb of memory just to hold the translation table.

Almost all of this table would be set to a value representing "Invalid address".

With the multiple levels you can reduce the space requirements for the translation table. If the 64bit address space is split into 16/9/9/9/9/12 bits for currently_unused/PML4/PDPT/PD/PT/address_in_page then you only need 512 entries for the PML4 table, of which 510 are probably the value representing "Invalid Address" and the remaining 2 point to two arrays of 512 entries of PDPT. If we stopped there then we have reduced the space needed from 2**36 entries to about 2 + 2**27 entries, less than 0.2% of the original linear requirement. Of course it doesn't stop there, there are 3 additional levels although they tend not to give quite as large savings.

1
  • It also improves average TLB performance, assuming "reasonable" access patterns. (And cache, insofar as it reduces cache pressure on any caches feeding the TLB.)
    – TLW
    May 23, 2021 at 5:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .