Subject: TLB invalidation
To: None <>
From: Toru Nishimura <>
List: port-mips
Date: 03/30/2000 10:34:57
Last night, before going to bed, I made a technical brief describing
MIPS TLB management as follows.  Feel free to correct me if wrong.

Tohru Nishimura

Unlike most other processors, MIPS MMU machinary has only two
protection bits, V and D.  V (valid) bit has rather normal sense;
TLB entry without V bit makes TLBinv. exception when referenced.

The D bit is somehow confusing.  The absence of D bit means WP (write
protected).  The TLB entry without D bit makes TLBmod. exception
when referenced for store (write to memory) operation.

TLBmod. exception has 4 different cases to handle;

- The page is RO; then post protection violation.
- The page is COW; then react and make things so-so.
- The page has datum to be written (flushed) to somewhere but deferred to
  do so; now it's time to flush the content to make room for fresh one.
- The page was expected to be referenced for write; then mark this page so.

The last two are almost synonym.  Note that the (absence of) D
bit can be used to implement so-called referenced bit found in
other processors (with the expense of exception handing each time).

It's remarkable that there is no "exception code" commonly found
in other processors to tell what the condition made the exception.
MIPS processor completely frees software to analyze and react for
any exception, and poses few hardware defined (hardwired) algorithmic
logic or data structure.  MIPS processor has no exception frame
built on stack, no page directory hierarchy traversing, no task
control block for context switch.  All it has is TLB machinary.
Smart functions like virtual memory and COW can be implemented by
well designed software, not by hardware MMU.

MIPS processor is peculiar in TLB invalidation issue.

TLB invalidation costs much in general, particularly for MIPS
processor.  Many processor provide the limited set of specially
designed instructions for TLB invalidation.  The most ridiculous TLB
instruction is TBIA to flush (make invalid) all the TLB entries.  TBIA
should be avoided at all cost because with MIPS processor TBIA brings a
flood of TLBmiss. whenever it is used.  TBIS is to invalidate a single
TLB entry with given virtual address iff such the entry is in TLB.
TBIS is less ridiculous to use, however, it would not be optimal to run
TBIS repeatedly to invalidate a large range of virtual address because
TLB likely contains very few entries to be affected.

Context switch is major source of TLB invalidation.  TLB is cache
for MMU machinary.  As context switch replaces process virtual
address space with another, any entry "cached" inside TLB gets
defunct and subject to be removed.

MIPS processor provides a smart way to avoid TBIA operation for
context switch.  Each TLB entry has a tag number, called TLBpid or
ASID, to distinguish which address space the entry belongs to.
MIPS processor maintains a current TLBpid to lookup TLB for given
va (virtual addresses).  TLB machinary searchs and looks up an
entry which has the given va and current TLBpid. Entries whose
TLBpids do not match current one are neglected even if they have
va in question.

Changing TLBpid removes the necessity of TBIA op.  By resetting
processor's current TLBpid with new one for now running process, TLB
entry(s) belong to the old process get invalidated in effect.  If the
old process retains MIPS processor on context switch, TLB entry(s)
(statistically) left intact in TLB at the moment can be reused.  Note
that so called TLB shootdown operation on multiprocessor system can
be handled in the same mannner.  A TLB tag could be regarded as the
extent of address space parallel across processes or address space
identifier to distinguish between.

Tighten protection
- No V bit anymore; the page has no use and is to be removed.
- No D bit anymore; the page was allowed to be written, but now COW or RO.

TLB is subject to invalidation because TLB possibly contains now
defunct entry(s).  Unless validation is done correctly, such the
pages would not post any exception when it should.

Loosen protection;
- Turn on V bit;
- Turn on D bit;

TLB is (might) not subject to invalidation.  The latter case is in
question.  It should be ok not to invalidate even though then-no-D bit
TLB entry would post TLBmod. which happens left in TLB.  Just to make
sure to have D bit in that exception pass.

A TLB tag is useful to invalidate (flush old) TLB entry when process
address space protection was tightened.  By assigning new TLBpid
for the process in question, old now defunct TLB entry(s) possibly
stored in TLB get invalidated in effect with a little cost.

TLB entry could have G bit to nullify TLBpid.  G bit means wildcard
match for given va.  Current TLBpid is not consulted to search and
TLBpid stored in each TLB entry is neglected if it has G bit; only
va takes effect to match.  G bit is useful when applied to mark
TLB entries for kernel address space located in KSEG2 which common
and shared between processes.  A variant of TBIA, TBIAP, invalidates
all of TLB entry for non global, per-process user address space.