CODEWITHSUNDEEP
operating-systempagingpage-tablesdemand-paging
not_that_guy123
not_that_guy123

Reputation: 133

Hardware support for valid / invalid bit in page table

While reading about demand paging, I can see it mentioned in several sources (e.g. http://www.expertsmind.com/questions/name-the-hardware-to-support-demand-paging-30176232.aspx) that we need hardware support for valid / invalid bit for each entry in the page table. However, I'm unable to wrap my head around what that hardware support would look like. As per my understanding,

  1. Page table itself is a software-based construct i.e. it has 4-byte / 8-byte (depending on addressing scheme / architecture etc) entries which are present in RAM.
  2. The valid / invalid bit is separate from the 4-byte / 8-byte used for each entry of the page table so it's not like out of 4-bytes of a page table entry, we're using 31 bits to store the frame number and 1-bit for valid / invalid bit.

So in summary my question is - what does hardware support for valid / invalid bit look like? If it can vary across implementations / architectures, could you share any particular implementation's details?

Upvotes: 0

Views: 378

Answers (1)

Brendan
Brendan

Reputation: 37214

  1. Page table itself is a software-based construct i.e. it has 4-byte / 8-byte (depending on addressing scheme / architecture etc) entries which are present in RAM.

That's possible and is the case for some rare CPUs (which just ask the OS for a translation when they get a "TLB/translation look-aside buffer miss").

However; for most CPUs the page table is a data structure used directly by the CPU itself, and software (kernel) must provide the data in the format that the CPU understands. For these cases the page table entry format required by the CPU typically has multiple bits used for a variety of purposes, including "valid/not valid" (and "accessed/not accessed", and read/write/executable permissions, and user/supervisor permission, and ...).

  1. The valid / invalid bit is separate from the 4-byte / 8-byte used for each entry of the page table so it's not like out of 4-bytes of a page table entry, we're using 31 bits to store the frame number and 1-bit for valid / invalid bit.

A page table entry (when valid) doesn't need to store the whole physical address because the address of the page must be aligned to the start of a page (and therefore the lowest bits can be assumed to be zero and not stored). E.g. if pages are 4 KiB (with 12 bits for "offset in page") and physical addresses are 32 bits; then only 20 bits are needed for physical address in the page table entries (and the lowest 12 bits of the physical address can be "assumed zero"), and with 32-bit page table entries those 12 bits can be used for other things ("valid/not valid", ...).

There are also "less regular" formats where some of the highest bits are repurposed for other things. For example, you might have 64-bit page table entries where the highest 4 bits are used for other things, then the middle 48 bits are used for physical address (without the "assumed zero" lower bits), then the lowest 12 bits are used for other things.

So in summary my question is - what does hardware support for valid / invalid bit look like?

Because it's different for each different type of CPU; the best place to look for page table entry format/s is the CPU manufacturer's manual. You can find a common example (for 32-bit 80x86) in the diagram here: https://wiki.osdev.org/Paging#Page_Table

Note that Intel call it a "present/not present" flag (labelled P), and it's the lowest bit in the page table entry.

Upvotes: 1

Related Questions