Subject: VCE exceptions

From: [email-masked]
Date: Thu, 2 Apr 1998 22:53:14 +0200

I think I know why we're catching VCE exceptions even though we try to
avoid them at any price - the reason spells ``empty_zero_page''.  This
page is filled with zeros and is being mapped to arbitrary addresses
at the same time.  Arbitrary addresses means also bits 14:12 of the
virtual address may be different, welcome VCED.  This also means that
at least sane code should never cause VCEI exceptions.  The text of
the panic message ``should not happend'' is therefore wrong as well ...

Whatever, the fact that the hardware causes VCE exceptions which don't
help us at all forces us to handle them somehow.  How handy, they'll
fit quite well in the revamped interface for board caches :-)

Another way to finally eleminate the virtual coherency problem from
KSEG0's landscape would be to actually use 8 pages as an array of
empty_zero_pages[], so we would be able to map one wherever we want
such that we never run into virtual coherency trouble.

  Ralf

---

From: "William J. Earl" <[email-masked]>
Date: Thu, 2 Apr 1998 13:41:02 -0800

> such that we never run into virtual coherency trouble.

      For an always-zero page, this is the best solution.  At a small
cost in memory, you get far less overhead.

---

From: [email-masked]
Date: Fri, 3 Apr 1998 00:36:23 +0200

> cost in memory, you get far less overhead.

Indeed, 16ns on a 250Mhz machine for every exception that goes via the
general exception vector _plus_ the actual vce / vci handling, that sucks.
I just wonder why those exceptions have been implemented at all?

They may help somewhat in debugging operating systems, but in our situation
they're nervragging by their mere existance.

  Ralf

---

From: "William J. Earl" <[email-masked]>
Date: Thu, 2 Apr 1998 15:15:03 -0800

> they're nervragging by their mere existance.

     In the R10000, the hardware does the VCE correction.  On the R4000PC, R4600,
and R5000, we have to avoid the problem in software, since the hardware
does not detect conflicts.   The motivation, and the reason that IRIX
depends on VCEs on the R4000 and R4400, was to make it easier to port
R3000 operating systems to the R4000.  If you don't have infrastructure
to control virtual aliasing (where a single page is mapped read-write at
two distinct virtual addresses with differing primary cache virtual indexes),
you get wrong answers with VCE (whether handled in software or hardware).
At MIPS, with the Magnum 4000PC under RISC/os, and at SGI, with the
Indy R4000PC (and later R4600 and R5000), I modified RISC/os and IRIX to
control virtual aliasing, but only for those platforms without hardware
VCE detection (in order to minimize time to market).  

    Note that taking a K0SEG address for a physical page which is also mapped
to user space can easily cause a VCE, since there is a good chance that
the K0SEG virtual index differs from the user space virtual index, unless
you match physical page color to virtual page color when allocating pages.
Note that you have to do that for any pages which must be accessible in
the general exception handler, since you cannot handle a VCE in the
exception handler.

---

From: [email-masked]
Date: Fri, 3 Apr 1998 13:52:45 +0200

> VCE detection (in order to minimize time to market).  

VCE's don't look too difficult to tackle under Linux.

> the general exception handler, since you cannot handle a VCE in the

The VCE bug is actually worse than I thought before.  I was in the assumption
that we'd handle all cases were VC might hit us because the MIPS ABI takes
care of by it's restrictions of the virtual addresses for mmaping.  Well,
I was wrong.  Writing via write(2) to a file that is also mmap(2)ed may
result in virtual coherency problems.

Another problem is that under Linux one cannot simply allocate a page of
a desired colour - which would of course be the prefered solution.  Luckily
a vce exceptionhandler will not run into the problem under Linux.

A small test program for the mmap/write problem attached.  If may be
necessary to start it several times in order to make it print the ``Big
trouble, man ...'' message.

  Ralf

---

From: "William J. Earl" <[email-masked]>
Date: Fri, 3 Apr 1998 11:11:15 -0800

[email-masked] writes:
 > 
 > --PXFtsOsTdHNUZQcU
 > Content-Type: text/plain; charset=us-ascii
 > 

     Remember that there are two parts to the problem.  For the R4000SC and
R4400SC, you can attack it by having the general exception handler avoid
referencing any page which could get a VCE (probably by not using data in
memory until after determining that the exception is a VCE exception) 
and having the VCE exception handler, running in assembly code at SR_EXL
level, fixup the cache (typically by doing hit-writeback-invalidate on
the D cache, hit-invalidate on the I cache, and hit-set-virtual on
the S cache, or else by doing hit-writeback-invalidate on the S-cache,
which is simpler but slower, accounting for the multiple I and
D cache entries per S cache entry).    For the other processors, the software
has to avoid creating D cache aliases (mappings with different virtual
indexes in the D cache) for writeable pages, to avoid data corruption
via stale copies in the D cache.  Since there is no hardware detection
of the aliases, the data corruption is silent.

 > trouble, man ...'' message.

     As soon as I get a chance, I will look at the relevant linux
code.  Note that physical color allocation can also make a big
performance difference on direct mapped secondary caches, as on all of
the Indy processors with secondary caches.  That is, you want to
maximize the likelihood that the secondary cache indexes of the
physical pages in a given application will be uniformly distributed
across the secondary cache.  Excessive hot spots will lead to
dramatically lower performance.  Allocation of a page where physical
color matches intented virtual color matters only if you need
to use a K0SEG address for the page to avoid TLB misses (as in 
the general exception handler, unless the K2SEG address is wired).

     For the mmap/write problem, what I did in IRIX was to first try
to assign mmap() virtual colors and buffer cache virtual colors
(colors of the K2SEG address for the page, not necessarily physical
color of the page, although having the physical color match means that
a cheaper K0SEG reference can be used) congruent to the virtual color
of the file offset for that page.  Then write() will see the same
virtual color when accessing the page as will the user program when
accessing the page using an address created using mmap().  When
MAP_FIXED and MAP_SHARED are set, however, and the specified virtual
color for the mapping is not congruent to the specified file offset,
an extra mechanism is required, namely software ownership switching of
the "current" virtual color.  For the page frame, we remember the
current virtual color, and arrange that the pg_vr bit is set only for
mappings which match that virtual color.  If we get a fault on a
mapping of a different color, we writeback-invalidate the primary
caches for the "current" color, invalidate the "current" mappings (by
turning off pg_vr), record the new "current" color, and then validate
the new "current" mappings (by turning on pg_vr).  In IRIX 6.3 and
later versions, I also allow the possibility of a "shared read
multiple color" state, where all mappings were allowed to be valid,
but with pg_m off.  That is, the "current" color became a
multiple-reader/single-writer lock on access to the page (where the
"single-writer" was a color equivalence class, not a single mapping).
In this case, the transition from "multiple-reader" mode to
"single-writer" mode requires invalidating all colors of the primary
cache for the given page.  Note that for MAP_FIXED with MAP_PRIVATE,
we can simply copy the page, even when it has not yet been modified,
if the mapped virtual color is not congruent to the file offset
virtual color.

    In IRIX, we handle the instruction cache specially, and do not
attempt to keep it coherent on the processors without hardware VCE
detection, so the above description is a little more restrictive than
what actually happens.  This approach is based on updates to instruction
pages being relatively rare, compared to updates to other pages,
so we wind up doing fewer I cache invalidates overall.

---

From: [email-masked] (Alan Cox)
Date: Fri, 3 Apr 1998 20:17:41 +0100 (BST)

> performance difference on direct mapped secondary caches, as on all of

Colouring in Linux isnt going to work without ripping the godawful buddy
allocator out of it. Unfortunately Linus seems quite attached to it at
the moment. Bamboo under the finger nails at Linux Expo perhaps Ralph ?

Whenever we try and do any colouring it fragments the buddy stuff up 
sufficiently badly that we basically break the box. 

Alan

---

From: [email-masked] (Alan Cox)
Date: Fri, 3 Apr 1998 22:00:37 +0100 (BST)

> Has anybody already played with a kind of ``colour caches''?  I'm thinking

Yes in the CVS tree Linux. Didnt work terribly well.

> of creating a cache of a couple of free pages per colour that is similarly
> related to the buddy system as the slab is currently, just for pages of
> certain colours.  That would still by kludgy, but Linus might like it ;-)
> 
>   Ralf  (Still not Ralph :-)

Sorry, I deal with two .de Ral*s  the tv card one is a ph 8)

---

From: [email-masked]
Date: Fri, 3 Apr 1998 23:02:30 +0200

> the moment. Bamboo under the finger nails at Linux Expo perhaps Ralph ?

That alone would be worth the price of the ticket.

---

From: [email-masked]
Date: Fri, 3 Apr 1998 23:27:41 +0200

Cc this to linux-kernel so this reaches the other Linux-vm people and
porters as well.  Maybe someone of them already has a way of dealing with
virtual aliases in virtual indexed caches.

>  > a vce exceptionhandler will not run into the problem under Linux.

In the meantime I've got a draft of the a handler available.

> the Indy processors with secondary caches.

Mark Hemment and David Miller had a page coloring scheme implemented.  I
think he dumped it again for whatever reasons.  Whatever, given the problems
with cache aliasing as result of not having proper cache coloring the code
needs to be resurrected.

>  That is, you want to

I *think* the VCEI case never happens under Linux, at least not until an
application does something _really_ stupid.  What an apps would need to
do is something opening a mapping with PROT_EXEC|PROT_WRITE|PROT_READ
and attempt to modify it by write(2) to it.  I don't think this ever
happens in real live.

Anyway, we have to deal with the problem and I'm going to hope the people
that actually have machines with SC/MC CPUs were the hardware detects the
problem for us will help me by running test kernels.

  Ralf

---

From: "William J. Earl" <[email-masked]>
Date: Fri, 3 Apr 1998 14:07:50 -0800

...
 > problem for us will help me by running test kernels.
...

     They can help by having the hardware show some of the cases where
the software is doing the wrong thing, but a reliable system will require
a solution which works on an R5000 or R4600, where there is no hardware detection.
That is, in most cases where an R4000SC would give you a VCE, an R5000 will
give you corrupted data (in general, not every time).  The solution needs
to be correct by construction, not by testing.

---

From: Olivier Galibert <[email-masked]>
Date: Sat, 4 Apr 1998 01:13:32 +0200

On Fri, Apr 03, 1998 at 08:17:41PM +0100, Alan Cox wrote:
> allocator out of it.[...]

Can someone point me  to a good documentation/book/whatever explaining
what cache colouring is ?

  OG.

---

From: [email-masked] (Alan Cox)
Date: Sat, 4 Apr 1998 00:15:45 +0100 (BST)

> what cache colouring is ?

Well for a flavour of it I can politically correctly recommend

"Unix Systems For Modern Architectures" by a Schimmel last resident I believe
at SGI 8)

---

From: "William J. Earl" <[email-masked]>
Date: Fri, 3 Apr 1998 15:47:19 -0800

> what cache colouring is ?

     As far as I know, there is none.

     I can give a basic tutorial.  A cache color for memory management
purposes is the set of bits from the page number portion of page
address used as part of the cache index (the value which selects a
line in the cache).  For caches indexed by the physical address (such
as secondary caches on most MIPS processors), the cache color is
determined from the physical address bits.  For caches indexed by the
virtual address (such as primary caches on most MIPS processors),
the cache color is determined from the virtual address bits.  
For caches with more than one set (such the primary caches on the R5000
and R10000), the cache color is determined with respect to a single set.

     For example, if the page size is 4KB, and the cache size is 32 KB,
and there are two sets, each set is 16 KB, so two bits of the address
form the cache color.  That is, there are four pages in each set,
so the low-order two bits of the virtual page number are the cache color.
Thus a cache line at virtual address 0x401320 has cache color 1 and,
if the cache line size is 32 bytes, as on the R5000 and R10000, the
cache index is 0x99.  If I map the same physical address to virtual 
0x1002320 (same page offset, but a different virtual page number), the
cache color is 2.  If the hardware does not detect the confict, as on
the R5000, and I try updating a variable via both addresses, I will
in general get wrong answers, since I could have two dirty copies of
the cache line in the cache at the same time (one at cache offset 0x1320
and the other at cache offset 0x2320).  Note that this is not a problem
for read-only data, such as instructions, since they are all the same,
but it is fatal for read-write data, unless software (on the R5000)
or hardware (on the R10000) or a combination (on the R4000SC) arranges
that at most one virtual color can be present in the cache for a given
line at any one time.  If only software is used, typically a whole page
must be managed.  When hardware is used, a secondary cache line is typically
the unit of management (since the "current" virtual index is stored
in the secondary cache tag).  

     Note that there cannot be a virtual-index cache coloring problem if the 
the cache set size is at least the page size.  For example, on the
QED RM7000, the primary cache is 16 KB and four-way set associative,
so each set is 4 KB and hence there are no virtual color index bits.
Similarly, for physically indexed caches, there is no index
coherency problem, since a given page has only one physical address.
(Actually, there are cases where this is not true, as in the case
of the first 512 KB of memory on Indy, which is mapped at both physical
address 0 and physical address 0x8000000, but software can easily deal
with that problem by only using one of the possible physical addresses.)

     The physical cache color, for physically indexed caches, is important
not for correctness but for performance.  Suppose, for example, that
I have a direct-mapped secondary cache, as on the R4000SC, and that
I happen to allocate several of the popular physical pages of a program
to the pages with the same physical cache color.  Then further suppose
that the most popular (frequently referenced) offset of each of these pages happens
to be 0.  Then the processor will try to put the data for the first
cache line of each page into the same slot in the secondary cache, so
that each time the program references a different one of the pages,
it will take a cache miss.  If, on the other hand, the system allocated
physical pages with different cache colors to the various virtual pages,
there would be not collisions and hence far fewer caches misses.  While
a two-set secondary cache, as on the R10000, helps a bit, it is still
important distribute physical addresses as uniformly as possible to minimize
cache misses.

     There has been some research on techniques to detect excessive
cache misses due to color conflicts, so that software can move one
of the offending virtual pages to a physical page with a different
cache color.  (One paper advocated a hardware monitor called a "camel buffer"
to detect such "hot" pages; the buffer was basically looking for 
cache indexes which were replaced more often than other indexes.)
A crude approximation might be derived from the page stealer's 
reference counting.

    The simplest way to reduce color conflicts, given existing
hardware, is to allocate pages with well-distributed colors.  One way
to do this is to divide the free page list into buckets, one per
color, and have a rotor which selects a different bucket for each
allocation.  Moreover, if you also would prefer to match virtual color
to physical color, so that the kernel can use a K0SEG address for a
page without incurring a virtual index conflict with respect to a
KUSEG user mapping of the same pages, you then easily look at just the
appropriate subset of the buckets (those for which the physical color
mod the number of virtual colors is equal to the desired virtual
color).  The use of the array of buckets has been shown to
substantially increase performance on RISC/os and IRIX, especially
on the R4000SC and R4400SC.  It should apply to any processor with
a physically indexed cache.