TLB shootdown

There has apparently been quite a bit of confusion about TLB
shootdown. It also doesn't help that because we haven't done
multiprocessor before in CS161 there's a ... lack of institutional
experience, and while it was supposed to be mentioned in lecture,
apparently this got overlooked.

(1) the problem

Suppose you have a multiprocessor system. Each processor's MMU will
operate independently, so on each processor the TLB will contain some
set of cached translations.

If you need to revoke a translation, such as for page eviction, or
upon calls to munmap() or mprotect(), or to mark pages read-only for
copy-on-write, or whatever else, you need to revoke it from *all*
TLBs; otherwise the ones you didn't revoke will in general cause the
wrong things to happen. But, from one processor you can't directly
access another processor's TLB; instead you have to poke the other
processor and ask it to do the revocation for you.

The process of doing so is called "TLB shootdown".

(2) the solution

The way one does TLB shootdown is to issue an inter-processor
interrupt (IPI) to the processor(s) that have, or may have, the
mappings you want removed in their TLBs. These processors, upon
receiving the interrupt, do the necessary TLB flush operations, and
then signal back in some fashion that they've finished. When all of
the target processors have responded, the original process can
continue knowing that the cached mappings have been removed. (And,
obviously, to continue *safely* some sort of locking steps should
already have been taken to prevent the same translations from being
(re)loaded on other processors.)

(3) in OS/161

In OS/161 because we don't have multithreaded processes,
copy-on-write, memory-mapped files, or other sources of shared pages,
the only time TLB shootdown becomes necessary is when you're evicting
a page that's mapped in another process's TLB. This is a fairly rare
operation (because pages mapped in TLBs are by definition poor choices
for page eviction) but nonetheless needs to be handled correctly.

The OS/161 base system provides you with code to send the IPIs, which
is, essentially, a pipe: you can send TLB shootdown requests, they'll
be queued in the target CPU's cpu structure, and when the target CPU
processes the interrupts it'll call back into the VM system to handle
them. The code that does this is at the bottom of thread.c and should
be easy to understand. The data that each request sends (struct
tlbshootdown) is up to you; I put in some default contents, but you
should change it to what makes sense for your VM design.

You need to write the rest, that is, a mechanism to wait for shootdown
to complete (which is a trivial synchronization problem), plus the
code to invalidate the requested mappings, and of course the code that
chooses when to do TLB shootdown.

Remember that because you have to wait for other processors to
respond, TLB shootdown isn't atomic. Your locking model needs to
account for this. Also, because TLB shootdown is expensive, you
probably don't want to e.g. do it on every page eviction and broadcast
the request to all processors just in case; better to know whether and
where to shoot.

(4) somewhat relatedly, thread migration

If you're using address space IDs (the PID field of the MIPS TLB) then
you need to add code to thread migration to update your address space
ID handling. Address space IDs are part of the MMU state and thus
inherently per-processor, so you need to get a new one for the new
processor and perhaps also discard the old one on the old processor.

If you're flushing the whole TLB on each context switch you don't need
to worry about this.

If you do this part properly there's no need to do any further TLB
shootdown handling for translations left in the TLB of the old
processor by migration: either they'll be attached to a no-longer-used
address space ID or they'll be flushed before anything else happens on
that processor, but either way they can't be used again and therefore
don't need to be actively revoked.