We have seen that virtually accessed caches
can overlap the latency of the TLB lookup and the cache lookup.
However, virtually accessed caches have a big problem called aliasing.
The problem of aliasing occurs
because in the virtual address space of the application,
we can have one page mapped to some part of the physical address space.
For example, we can use the mmap function in Linux and
other operating systems to map part of a file so
that it appears in a range of memory that we can address.
The problem occurs when another page in our virtual address space is
also mapped to the same physical addresses.
For example,
when doing an mmap of the same part of the same file to another address.
So now what we have is two virtual addresses
will actually refer to the same physical location.
To see why this is a problem in a virtually accessed cache,
let's look at two specific addresses.
So let's say that A and B are 12345000 and ABCDE000,
and let's say that we have a 64 kB direct-mapped cache
with a 16 byte block size and that is virtually accessed.
So let's say that this is our 64 kB cache.
For this cache, we have a four bit offset part of
the address because of the 16 byte block size.
It's a 64 kB cache, so
the next 12 bits are going to be the index into this cache.
64 kB divided by 16 bytes is four kilo entries, so
we need 2 to the 12th index bits to tell us which index do we have.
And the rest of the bits in the addresses are tags.
So this is how the aliasing problem occurs.
Let's say that the processor writes a value of 16 to A.
It breaks down the address, indexes into the cache, using the index of hex 500.
Let's say that this is a cache miss.
So we go to memory, and from the physical location where this data is
mapping to, we fetch a value, and let's say that this value is four.
Once we fetch the cache block, we now put 16 there, and
the new content of the cache block is 16.
Let's say this is a write-back cache, so this 16 just stays there.
Now, let's see what happens when we try to read B.
We index into the cache using the index for B, which is E00 hex,
and because what we are looking for is not here, we go to memory and
fetch the value, and this maps with the same physical memory location, so
we are going to get four again.
And now we're going to read that.
Note that this problem is not just a problem on the cache misses.
>From now on, whenever we write to A, we will be changing this cache block, and
whenever we read from B, we will be reading this cache block, so
they never really end up sharing the data as they should.
What should've happened is because A and B are really the same data,
when we write to A and read B, we should be getting the same data.
And this problem results
in incorrect execution whenever we have such a mapping.
Unfortunately, such mappings are perfectly legal to do in most operating
systems, so virtually accessed caches need additional support for this.
Every time we write to any virtual location, we would have to do a check
for aliases or different versions of the same physical data in the cache and
either invalidate them, remove them from the cache, or update them so
that they would see the new value.
And this is really expensive to do, and
it kind of defeats the purpose of virtually accessed caches,
which are all about the latency and not needing to do translation.
Now, when we write here, we would need to do translation
in order to check where else do we have the same mapping.
To summarize this, we like virtually accessed caches because they allow us to
overlap, tabulate, and see with cache latency, but we cannot use them because
of the aliasing problem that seriously complicates their implementation.