Andy Glew's comp-arch.net wiki, http://semipublic.comp-arch.net
If you are reading this elsewhere, e.g. at site waboba.info, it is an unauthorized copy, and probably a malware site.
comp-arch.net wiki on hold from October 17, 2011
The Difference Between Invalid and Not Present
From CompArch
PBI vs NP
Many cache protocols have a single state "I", for "Invalid". But in fact it is often possible to distinguish between states
- NP - not present
- and I - invalid - in cache, but not valid for some reason. Usually, stale.
E.g. MESI - the "I" state covers both present but invalid and not present.
For the sake of clarity, let me say
- PBI = present but invalid
- NP = not present
- I = PBI or NP
Uses of PBI Data
It is possible to take advantage of PBI data.
For example, in my (Glew) MS thesis I proposed an update cache protocol optimized for synchronization variables that updated stale lines in PBI state when a lock release was performed.
It has also been proposed to use stale cache line byte data as a data value predictor.
Invalid PTEs and TLB entries
A PTE inside a virtual memory page table address translation mechanism such as the Intel x86 tree shaped page tables may be
- I - invalid - marked invalid in the PTE
- not in the table at all - e.g. if it's parent PDE is itself invalid.
A PTE may be cached inside a TLB. The TLB entry for an address may be NP, or PBI.
Hashed or inverted page tables may have PTEs that are PBI or NP.
In an x86 PTE in memory, the OS is allowed to use other bits of the PTE if the PTE is marked invalid. Q: would it be good to distinguish
- PBI - present, but invalid, although PTE fields may be meaningful
- from present, but PTE fields are not consistent with PTE/TLB interpretation
