# Why do we need the valid-invalid bit in a page table?

I'm reading about memory management in Operating System Concepts, by A. Silberschatz. The author says:

[...] the user process by definition is unable to access memory it does not own. It has no way of addressing memory outside of its page table, and the table includes only those pages that the process owns.

Then, the author explains the need of having a valid-invalid bit:

One additional bit is generally attached to each entry in the page table: a valid–invalid bit. When this bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page. When the bit is set to invalid, the page is not in the process’s logical address space.

Why do we also need a valid-invalid bit, if a process is by definition able to access only memory addresses stored in its own page table?

The two quoted sentences appear to be contradictory, in my opinion. There must be something I am missing here.

This exact same question has been already asked a few times; however, none of the answers clarified my doubt. Source:

The answers that other users have given don’t explain why the validity bit is needed to protect address spaces. The page table of a process contains only those pages that are valid for that process (i.e., that the process actually owns), so why do we need to replicate a security feature that is already present thanks to the way the page table is implemented?

• The questions you link already give detailed answers to your question. You say that they don't clarify your doubt but what actually is your doubt? At the moment, we have a collection of answers and you're essentially saying, "They're no good for me." OK, but what if somebody spends 20 minutes writing a new answer for you. How are they supposed to know what they're supposed to say to avoid your response being, "That's no good, either"? – David Richerby Aug 19 '17 at 13:16
• Possible duplicate of what is the need for valid/invalid bit in paged memory technique? – David Richerby Aug 19 '17 at 13:16
• @DavidRicherby The answers they gave do not take into account the assumption is made with the first quoted text. This is why I needed to open a new question about the topic. None of the answers that have been already given solves the question: "Why do we need a validity bit when the process has no way of addressing memory outside its page table?". The page table only contains addresses owned by the process, nothing more. – user76258 Aug 19 '17 at 13:33

As David Richerby says, it’s not clear what you don't understand.  Most of my answer here has already been presented in answers (or comments) to the questions you linked to.

I’ll admit, though, that the Operating System Concepts book is probably not as clear as it should be.

The book (going back to Figure 8.6 (Hardware support for relocation and limit registers) on page 361) suggests that the processor knows the maximum user virtual address for a context (process), so if the process tries to access an address above this limit, the access fails with an addressing error.  This concept seems to erode over the following pages; for example, Section 8.4.2 (Segmentation Hardware) (pages 365 and 366) introduces a limit field in each segment table entry, but waves its hands over the question of specifying the maximum virtual address (and, correspondingly, the length of the entire segment table).

I would argue that Figure 8.9 (Example of segmentation), on page 367:

[images copied from this 944-page PDF of the book]

• It’s clearly not to scale.  It says that Segment 0 is 1000* bytes long — both explicitly, in the segment table, and in the map of physical memory $(2400-1400=1000)$.  Likewise, it says that Segment 4 is 1000 bytes long — both explicitly, in the segment table, and in the memory map $(5700-4700=1000)$.  But Segment 4 is clearly larger than Segment 0 in the memory map, while Segment 0 is clearly larger than Segment 4 in the nebulous logical address space on the left.
• Why are the segments colored inconsistently?  Segments 2 and 3 are gray on the left and white on the right.  Does this mean something?
• How do we know which “segment” a given address is in?
• How do we know the length of the segment table?

Wandering Logic addresses the fourth bullet with their statement, “Typically the page table is a tree of fixed size pages.” (emphasis added).  So, looking at Figure 8.15 (“Valid (v) or invalid (i) bit in a page table”), excerpted here,

it might be that the system has no way of knowing which pages are valid (0-5) and which ones are invalid (6 and 7) other than marking the entries for the invalid pages with an invalid flag.

But also, while Figure 8.9 is somewhat confusing, it also contains the kernel of part of the answer to your question: The user virtual address space may be segmented / fragmented / sparse / discontiguous.  In other words, just because the maximum virtual address is $N$, that doesn’t mean that every $M$ such that $0 \le M \le N$ is a valid address.  Just as the segments are explicitly shown as being discontiguous (and out of order) in the physical memory (on the right), and are implicitly shown as disassociated in the logical address space on the left, with order being irrelevant**, they may actually be discontiguous in the logical address space.  In fact, the book (somewhat) explicitly (but not clearly) tells us that they are discontiguous, in the last paragraph of Section 8.4.2:

A reference to byte 1222 of segment 0 would result in a trap to the operating system, as this segment is only 1,000 bytes long.

So the 1222nd byte of the logical address space is not the 222nd byte of segment 1, but rather falls in the gap between segment 0 and segment 1.  If we assume that the segments occur in numeric order in the logical address space with addresses at multiples of 2000, starting at 0, then the complete (logical and physical) segment map/table might look something like this:

segment               logical                                  physical
#    | base  limit          range       ...     base  limit          range
--------------------------------------     ...     ----------------------------
0    |    0   1000           0-999              1400   1000        1400-2399
1    | 2000    400        2000-2399             6300    400        6300-6699
2    | 4000    400        4000-4399             4300    400        4300-4699
3    | 6000   1100        6000-7099             3200   1100        3200-4299
4    | 8000   1000        8000-8999             4700   1000        4700-5699


(I’m sorry, but I just don’t see any reason to display the limit to the left of the base, as the authors do.)  So, pretending that the page size is 100 bytes, using a format inspired by Figure 8.15, we would get a page table that looks like this:

virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical
page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #
0   |   14    ┃   18   | invalid ┃   36   | invalid ┃   54   | invalid ┃   72   | invalid
1   |   15    ┃   19   | invalid ┃   37   | invalid ┃   55   | invalid ┃   73   | invalid
2   |   16    ┃   20   |   63    ┃   38   | invalid ┃   56   | invalid ┃   74   | invalid
3   |   17    ┃   21   |   64    ┃   39   | invalid ┃   57   | invalid ┃   75   | invalid
4   |   18    ┃   22   |   65    ┃   40   |   43    ┃   58   | invalid ┃   76   | invalid
5   |   19    ┃   23   |   66    ┃   41   |   44    ┃   59   | invalid ┃   77   | invalid
6   |   20    ┃   24   | invalid ┃   42   |   45    ┃   60   |   32    ┃   78   | invalid
7   |   21    ┃   25   | invalid ┃   43   |   46    ┃   61   |   33    ┃   79   | invalid
8   |   22    ┃   26   | invalid ┃   44   | invalid ┃   62   |   34    ┃   80   |   47
9   |   23    ┃   27   | invalid ┃   45   | invalid ┃   63   |   35    ┃   81   |   48
10   | invalid ┃   28   | invalid ┃   46   | invalid ┃   64   |   36    ┃   82   |   49
11   | invalid ┃   29   | invalid ┃   47   | invalid ┃   65   |   37    ┃   83   |   50
12   | invalid ┃   30   | invalid ┃   48   | invalid ┃   66   |   38    ┃   84   |   51
13   | invalid ┃   31   | invalid ┃   49   | invalid ┃   67   |   39    ┃   85   |   52
14   | invalid ┃   32   | invalid ┃   50   | invalid ┃   68   |   40    ┃   86   |   53
15   | invalid ┃   33   | invalid ┃   51   | invalid ┃   69   |   41    ┃   87   |   54
16   | invalid ┃   34   | invalid ┃   52   | invalid ┃   70   |   42    ┃   88   |   55
17   | invalid ┃   35   | invalid ┃   53   | invalid ┃   71   | invalid ┃   89   |   56
90   | invalid
91   |    ︙


(Consider all entries that have physical page numbers (not flagged “invalid”) to be flagged “valid” — I left that out to save space.)  See also What is stored in the first memory address? Why can’t I print the contents?, where Scott provides an answer that includes a hypothetical (example) virtual (logical) → physical memory map

Maybe Silberschatz, et. al., should have used something like that instead of their Figure 8.9.  (Their Figure 8.17 comes close, but, IMO, it is too complex and confusing, and not really the same thing in any case.)

Also, as Pseudonym points out, pages that are valid addresses in the process's virtual address space might not be OK for the CPU to access:

• A page might be swapped/paged out to secondary storage (disk or SSD), or it might be located in a memory-mapped file.  The operating system would need to trap the access so it can fetch the page from secondary storage.
• A page might have been allocated to the process, but not yet zero-filled.  The operating system would need to trap an access to such a page so it can set it to all zeroes.
(Note: I’m not sure the OS would use an “invalid” flag for that; it should be possible to flag the entry as “valid”, but turn off read, write, and execute permissions, so any access to any address in the page will cause a trap to the OS.)
• The conventional wisdom is that fork() copies a process’s memory image.  In reality, it probably copies the page table, so both parent and child are pointing to the same physical memory.  If/when the child process does an exec(), it relinquishes its claim on the memory, and everything is cool.  But you don’t want it to appear (behave) as though the processes are sharing memory, so, as soon as either process makes any attempt to modify any memory, the kernel wants to intercede and make a copy of the page (so each process can have its own copy).  This is the “copy-on-write” paradigm that Pseudonym refers to.
(Although, again, I’m not sure the OS would use an “invalid” flag for that; it should be possible to flag the entry as “valid”, but turn off write permission, so any write access to any address in the page will cause a trap to the OS.)

Why do we need a validity bit when the process has no way of addressing memory outside its page table?

is that there can be addresses within the process’s page table that are not valid addresses to access.

Why do we [also] need a valid-invalid bit?

Good question.  As Silberschatz’s Figure 8.15 suggests, it might be good enough just to set the physical page address (or frame number) to 0.  But, notwithstanding the issue raised in the What is stored in the first memory address? Why can’t I print the contents? question (which Pseudonym also mentions: “The first few pages of the address space of a process are deliberately left invalid so that any attempt to access memory through a NULL pointer is trapped by the operating system.”), page 0 is a valid physical page address.  To say that “0” means “invalid” would make page 0 of physical memory inaccessible — even to the OS.  Pretty much by definition, anything that can fit into a field that is sized to a physical page number will be a (theoretically) valid page number.  Sure, you could use an all-ones value (e.g., 0xFFFFFFFF), but even that could result in a situation where a machine that had 128 terabytes*** of physical memory might be unable to access the last 512 or 1024 bytes; that would be silly.

Consider also what Daniel Jour points out:

Because the [page number] entry isn't used by the MMU [if the entry is flagged as invalid,] the operating system can use it to store its own information, like for example a reference to the filesystem entity (for example inode number) where it stored the data to free the main memory for some other processes (it swapped that page out).

So that’s why a page table entry contains a physical page number and a valid/invalid flag.

___________________
*  Apparently these numbers are decimal! — see the last paragraph of Section 8.4.2 (Segmentation Hardware).  This is, of course, totally unrealistic, but I guess it doesn't matter as long as the numbers are handled consistently.
**  which is nonsense — they are numbers, so they have an order.
*** I'm pulling a large number out of my hat here; I haven’t checked that the math on this exactly makes sense.

Think of a simple scenario, where you have process A's page table. OS swaps out some of the pages, hence some of the page table entries will be invalidated and invalid bit has to be set.

From Silberchatz, Section 9.4 Page replacement (Page 360): We can free a frame by writing its contents to swap space and changing the page table (and all other tables) to indicate that the page is no longer in memory.

• Why don't just delete that page table entry as it's translation it's not in the physical memory? – gdaras Jul 1 '18 at 10:53

I think the confusion may be from this quote:

One additional bit is generally attached to each entry in the page table: a valid–invalid bit. When this bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page. When the bit is set to invalid, the page is not in the process’s logical address space.

I think this is a bit misleading, or at least incomplete.

There are two views of a virtual address space: the CPU's view (which is implemented by the page table mechanism), and the operating system's view, which involves a bunch of additional data structures and concepts that the CPU's page translation hardware doesn't see.

The CPU has no concept of memory-mapped files, swapping, or anything like that, because that requires knowledge about filesystems and secondary storage devices. The only case it can handle directly is the case where a page of virtual address space maps correctly to a page frame of memory. Anything else requires the operating system to emulate it.

When the bit is set to invalid, from the CPU's point of view, it is not a valid mapping. The CPU's page translation hardware will not translate that virtual address to a physical address, and will instead trap to the operating system.

From there, it's up to the operating system to decide what to do with it. From the operating system's point of view, it may well be "correct" for a task to try to access that page, and in that sense it's not "invalid". It's only the hardware mapping that's invalid.

It may help to think of the "invalid" bit as meaning "cause a page fault". It's up to the operating system to decide what that means and what to do about it when it happens.

To understand the purpose of the valid bit, you need to first understand the layout of the page table. The page table is a table full of entries. The entries for some virtual addresses contain mappings to a physical address; the entries for other virtual addresses might contain no mapping. The latter is indicated by marking the entry as invalid, i.e., clearing the valid bit.