From a posting to ac.csci.c335 in response to a how about you find out
request when questioning cache behavior. Seemed I ought to save it.


Date: Tue, 26 Feb 2002 03:07:33 -0500 (EST)
From: Christopher J Dent <cjdent@cs.indiana.edu>
Subject: 68040 cache behavior

As requested in class today (yesterday depending on when tomorrow is)
I went looking for some information the behavior of the instruction
cache on the 68040.

General information on the caches in the 680x0 family is available in
the Wakerly book in Chapter 15 (p. 521). Caches are described in general
and then more detail about the caches in the 68020 and 68030 is provided.

Generally data in the cache is replaced using the least recently used
(LRU) algorithm. Wakerly says: "LRU: Replace the cache line whose last
access was farthest in the past."

A line is an entry in the cache, it is made up an info field and a tag
field. The info field contains the instruction or data being cached.
The tag field contains main memory address the info came from.

When a read from memory is requested the cache is checked for an
entry corresponding to the memory address. If it is there it is read
from the cache.

Writes to the cache and from the cache to memory are more complicated
and depend on the policy of the cache. More detail is available on
page 527 of the book.

Lookups in the cache can be accelerated by addressing the cache by only
some of the bits in the address.

The 68020 has instruction cache. The 68030 has both instruction and data.

Information about the cache on the 68040 (as well as more info on the
other processors, and cache mechanics in general) can be found here:

  http://developer.apple.com/technotes/hw/hw_06.html

So, based on all this, the behavior of the instruction is what I would
call non-deterministic. You can't know what's going to be happening in
the cache unless you have perfect knowledge of the activity of the
machine that allows you to know when lines in the cache will be written
to memory or read from memory (I imagine there are some cases where this
may be possible, but, wow, ouch).

If you want to write self-modifying code there are strategies for
dealing with the state of the cache. There's a hardware trap that can
flush the cache called FlushInstructionCache. It is described in various
places but one is in a discussion of 68040 emulation on the PowerPC
found here:

  http://developer.apple.com/technotes/pt/pt_39.html

or in

  http://www.mactech.com/articles/mactech/Vol.13/13.10/RoutinesasValues/

entitled:

  Routines As Values
  by Lawrence D'Oliveiro

  The High-Level Programmer's Guide to Generating Code at Run-Time