Subject: Re: [UPDATED PATCH] IP28 support

From: Kumba <[email-masked]>
Date: Wed, 05 Dec 2007 01:16:13 -0500

Ralf Baechle wrote:
> On Thu, Nov 29, 2007 at 10:54:42AM +0100, Thomas Bogendoerfer wrote:
> 
>> Add support for SGI IP28 machines (Indigo 2 with R10k CPUs)
>> This work is mainly based on Peter Fuersts work.
> 
> Queued for 2.6.25.  There clearly is work remaining to be done but the
> code is now in an acceptable shape and the best way to push it forward
> is integrating it.  Thanks for all the work and especially to Peter
> Fürst for the initial heavyweight lifting!
> 
>   Ralf

Seconded.  Peter is made of Win.

I've been out of it lately -- did the gcc side of things ever make it in, or do 
we need to go push on that some more?

--Kumba

-- 
Gentoo/MIPS Team Lead

"Such is oft the course of deeds that move the wheels of the world: small hands 
do them because they must, while the eyes of the great are elsewhere."  --Elrond

---

From: [email-masked] (Thomas Bogendoerfer)
Date: Wed, 5 Dec 2007 10:39:38 +0100

On Wed, Dec 05, 2007 at 01:16:13AM -0500, Kumba wrote:
> I've been out of it lately -- did the gcc side of things ever make it in, 
> or do we need to go push on that some more?

We need push on that. Looking at 

http://gcc.gnu.org/ml/gcc-patches/2006-04/msg00291.html

there seems to be a missing understanding, why the cache
barriers are needed. I guess the patch could be improved
by pointing directly to the errata section of the R10k
user manual. Or even better copy the text out of the user
manual. That should make clear why this patch is needed.

Peter did you do the copyright assigment ? That's probably
the second part, which needs to be done.

Thomas.

-- 
Crap can work. Given enough thrust pigs will fly, but it's not necessary a
good idea.                                                [ RFC1925, 2.3 ]

---

From: peter fuerst <[email-masked]>
Date: Wed, 5 Dec 2007 20:49:53 +0100 (CET)

On Wed, 5 Dec 2007, Thomas Bogendoerfer wrote:

> Date: Wed, 5 Dec 2007 10:39:38 +0100
> From: Thomas Bogendoerfer <[email-masked]>
> To: Kumba <[email-masked]>
> Cc: Ralf Baechle <[email-masked]>, [email-masked]
> Subject: Re: [UPDATED PATCH] IP28 support
>
> We need push on that. ...

There was no answer to .../2006-05/msg01446.html. Perhaps i should just
put together an updated patch, that incorporates the changes proposed in
msg01446.html, and submit it (with the longer "Cc:" line and a hint to
the increasing demand for it ;-) to revive at least the discussion at
gcc-patches.
What could be changed beyond the proposed changes without either omitting
necessary cache-barriers or crippling the R10k, i can't see yet.

> manual. That should make clear why this patch is needed.

Better copy, i guess. (Assuming copying whole paragraphs is still proper
citation ;-) Along with the initial patch (.../2006-03.msg00090.html) as
well as in the last letter so far (.../2006-05/msg01446.html) i pointed
to the corresponding chapter in the R10k User's Manual and to the entry
in the NetBSD eMail archive. In the last letter i tried to augment these
by a summarizing explanation, but it seems i'm not very good at that...

> the second part, which needs to be done.

Yes, the assignment process became complete on May 22 2006
(though apparently i missed to notify Richard Sandiford about it)

> Thomas.

kind regards

peter

---

From: David Daney <[email-masked]>
Date: Wed, 05 Dec 2007 12:37:59 -0800

peter fuerst wrote:
> put together an updated patch,

That would be helpful.  It would have to be against GCC's svn trunk. 
Currently 4.3 is in regression fix only mode.  The earliest the patch 
could appear in an official GCC release would probably be version 4.4

> that incorporates the changes proposed in

Just sent it to gcc-patches@   I think it will be noticed.

> (though apparently i missed to notify Richard Sandiford about it)

Good.  Richard is generally quite responsive to patches.  Perhaps CC him 
on your patch.

David Daney

---

From: Ralf Baechle <[email-masked]>
Date: Thu, 6 Dec 2007 11:41:03 +0000

> by a summarizing explanation, but it seems i'm not very good at that...

I'm not sure how far "fair use" of the R10000 manual text can be stretched.
But afair Bill Earl ([email-masked]) posted a reasonable explanation which
also for the purposes of the gcc manual is much easier to understand.

  Ralf

---

From: Ralf Baechle <[email-masked]>
Date: Thu, 6 Dec 2007 11:44:46 +0000

On Wed, Dec 05, 2007 at 12:37:59PM -0800, David Daney wrote:

> Currently 4.3 is in regression fix only mode.  The earliest the patch could 
> appear in an official GCC release would probably be version 4.4

Many distributions have the policy of applying only patches that are
upstream, even if they're upstream only for a newer version.  As such
getting them into the FSF 4.4 tree would also be tremendously useful as
an icebreaker.

  Ralf

---

From: Richard Sandiford <[email-masked]>
Date: Sat, 08 Dec 2007 17:52:06 +0000

[email-masked] (Thomas Bogendoerfer) writes:
> barriers are needed.

Heh.  Quite probably.  Which bit of my message don't you agree with?

FWIW, I was going off the original message as posted here:

    http://gcc.gnu.org/ml/gcc-patches/2006-03/msg00090.html

The explanation of the chosen workaround seemed to be left to this bit
of http://mail-index.netbsd.org/port-sgimips/2000/06/29/0006.html:

    All is well with coherent IO systems.  On non coherent
    systems like Indigo2 and O2 this creates a race
    condition with DMA reads (IO->mem) where a stale
    cached data can be written back over the DMAed data.

    R10K Indigo2:

    This issue was figured out late the the R10K I2
    design cycle.  The problem was fixed by modifying
    the compiler and assembler to issue a cache barrier
    instruction to address 0(sp) as the first instruction
    in basic blocks that contain stores to registers
    other than $0 and $sp.

and from a compiler point of view, it would be nice to know
_why_ that was a reasonable workaround.  What I was really
looking for was: (a) a short description of the problem,
(b) a list of assumptions that the compiler is going to
make when working around the problem and (c) a description
of what said workarounds are.

My understanding of (a) is that, if a store is speculatively executed,
the target of the store might be fetched into cache and marked dirty.
We therefore want to avoid the speculative execution of stores if:

  (1) the addressed memory might be the target of a later DMA operation.
      If the DMA completes before the "dirty" cache line is flushed,
      the cached data might overwrite the DMAed data.

  (2) the addressed memory might be to IO-mapped cached memory
      (usually through the address being garbage).  The cached
      data will be written back to the IO region when flushed.

We also want to avoid speculative execution of loads if:

  (3) the addressed memory might be to load-sensitive IO-mapped cached
      memory (usually through the address being garbage).  The hardware
      would "see" loads that aren't actually executed.

Is that vaguely accurate?

I tried to piece together (b) by asking questions in the reviews,
but it would be great to have a single explanation.

The idea behind (c) is simple, of course: we insert a cache barrier
before the potentially-problematic stores (and, for certain
configurations, loads, although the original gcc patch had the
associated macro hard-wired to false).  The key is explaining how,
from a compiler internals viewpoint, we decide what is "potentially-
problematic".  This ties in with the assumptions for (b).

I'm sure my attempt at (a) above can be improved upon even if it's
vaguely right.  But...

> I guess the patch could be improved
> user manual.

...I think an integrated explanation of (a), (b) and (c) above
would be better than quoting large parts of the processor manual.
The processor manual is aimed at a much broader audience and has
a lot of superfluous info.  It also doesn't explain what _our_
assumptions are and what our chosen workaround is.

Richard

---

From: Ralf Baechle <[email-masked]>
Date: Sat, 8 Dec 2007 19:24:05 +0000

>     cached data can be written back over the DMAed data.

It's not a race condition.

> Is that vaguely accurate?

Yes.

> problematic".  This ties in with the assumptions for (b).

The principle for the compiler is a store is problematic unless proven
otherwise.  A speculative store relative to the stack pointer, frame
pointer or global pointer for example is harmless.

> assumptions are and what our chosen workaround is.

There are two R10000 manuals, one from SGI and one from NEC and they're
differing quite a bit on the workaround.  The SGI one gives a large number
of suggestions on how to work around the behaviour some of which even
require hardware asistance by on the system board.  A long time ago
Bill Earl, one of the engineers at SGI responsible for the workaround
emailed me this explanation which I believe is quite reasonable:

[...]
     The R10000 "bug" is, in a sense, a feature, in that it improves
performance, and is harmless on machines with cache-coherent I/O.
Specifically, on a speculative store miss (a cache miss due to a
speculatively executed store instruction), the R10000 fetches the line
dirty-exclusive and marks it modified, in anticipation of the store.
If, however, the speculatively executed store never graduates (is
never committed), the line is left dirty, even though it has not been
modified.  If the line happens to be part of a buffer into which data
is being DMAed, a subsequent victim writeback of the dirty cache line
might overwrite good data from the DMA with the obsolete data in the
cache line.  This means that, one way or the other, a system with
non-cache-coherent I/O and an R10000 must avoid allowing the
processor to perform a speculative store miss with respect to memory
into which a DMA is taking place.

     Note that the Indigo2 and O2 have somewhat different workarounds.
The Indigo2 deals with the kernel side using a special compilation mode,
and the O2 deals with the kernel side using a special hardware feature
plus a generalization of the solution for the user mode part of the problem.
Both deal with the user mode by invalidating TLB entries for pages into
which data is being transferred via DMA, so that the processor cannot
resolve the virtual address, and hence cannot speculatively fetch
a cache line at that address, while the DMA is in progress.  The kernel
side is harder, since the TLB is not used for K0SEG and XKPHYS address
spaces, which is where things get complicated.
[...]

I should mention that the hardware assissted solution for the O2 which is
implemented using an CPLD codenamed "juice" is not currently used by
Linux that is it relies on the same software-only workaround as the
Indigo 2 R10000.

  Ralf

---

From: Richard Sandiford <[email-masked]>
Date: Sat, 08 Dec 2007 20:09:31 +0000

> pointer or global pointer for example is harmless.

Right.  But just so we're on the same page (and I think we probably are),
my point was that those rules aren't intrinsically obvious.  They're
based on assumptions about how the code is written.  For example,
it assumes there's no DMAing into stack variables.  Maybe obvious,
but I think it needs to be stated explicitly.  Then there's the
language-lawyerly code I gave to Peter on gcc-patches@:

     void foo (int x)
     {
       int array[1];
       if (x)
         bar (array[0x1fff]);
     }

This function is valid if x is never true, so we cannot assume that all
accesses off the stack and frame pointers are actually in-frame.  You're
assuming either (i) the kernel doesn't use code like that or (ii) that
"garbage" addresses in the range [$sp - 0x8000, $sp + 0x7fff] will not
trigger the problem.  I imagine both are reasonable assumptions, and I'm
perfectly happy for us to make them.  But they're the kind of assumption
we need to state explicitly.

Peter's patch also treated accesses to constant integer and symbolic
addresses as safe.  Again, this involves making assumptions about how
constant integer and symbolic addresses are used, and this is a much
less obvious assumption than the stack one.  Again, I understand that
it's a reasonable assumption to make in the linux context, but it's one
we need to pin down.  E.g. there must be no run-time guarding of
target-specific constant integer IO-mapped addresses in cases where
those addresses might trigger the problem on other systems that the
same kernel image supports.

Despite appearances, I'm not trying to be awkward here ;)  I just think
the assumptions are too loosely-defined at the moment (or at least too
scattered around).  It would be nice to have some self-contained
description, targetted specifically at gcc and linux, that contains
anything a gcc hacker or user needs to know about the gcc patch.

Richard

---

From: peter fuerst <[email-masked]>
Date: Sat, 8 Dec 2007 22:25:01 +0100 (CET)

Hi!

could text like this help to pin the assumptions down (from
"http://gcc.gnu.org/ml/gcc-patches/2006-05/msg01446.html") ?

  "...
  What cases of $N can be exempted from this measure?
  - Stack-addresses and constant (static) addresses ("sd $M,symbol+n") will not
    be used for DMA, since DMA-buffers are allocated at runtime.
  - Uncached accesses will not be done speculatively, but they fall under the
    "constant"-case already or will not be recognized at compile-time.

  Besides the DMA-problem, depending on the mis-speculation path (up to four
  branches deep), one of the frequently reused multi-purpose registers $N
  will contain some "random" value, which may be a legal but invalid kernel-
  address (say a800000061234567), reaching the memory-controller...
  However, there are cases where a register $N's content is well defined, no
  matter what (mis-)speculation path took us to this instruction:
  - The stack-pointer points to the stack from kernel-initializtion on.
  - Constant addresses ("symbol+n") are well defined "per se".
  (Luckily, legal-but-invalid doesn't occur in user mode, where no cache-
  barriers can be used. There we get either an address-error or a TLB-miss,
  leaving memory/bus untouched.)
  ..."

kind regards

peter

On Sat, 8 Dec 2007, Richard Sandiford wrote:

> Date: Sat, 08 Dec 2007 20:09:31 +0000
> From: Richard Sandiford <[email-masked]>
> To: Ralf Baechle <[email-masked]>
> Cc: Thomas Bogendoerfer <[email-masked]>, Kumba <[email-masked]>,
>      [email-masked]

---

From: Richard Sandiford <[email-masked]>
Date: Sat, 08 Dec 2007 23:24:03 +0000

>   leaving memory/bus untouched.)

Well, the explanation of the exceptions doesn't really address the
corner cases I was trying to draw attention to in the message you
replied to.  What about top of the stack + X?  Do we guarantee that
the code will never cause the compiler to generate a store to such
an address, even with an always-false guard?  Or do we guarantee
that stores and loads to [top-of-stack, top-of-stack + 0x7fff] can
be speculated safely?  Do we guarantee that every store and load to
a cached constant address in the kernel image will not result in
a harmful IO access on any target that the image supports?

Perhaps we should just turn this around slightly and instead say:
what must the compiler do, and when must it do it?  The reasons why
aren't that important from the compiler's perspective.  So if we can
just phrase it as:

-mr10k-cache-barrier=load-store
  Insert a cache barrier at the beginning of any sequentially-executed
  series of instructions that contains a load or store.  For the purposes
  of this option, GCC can ignore loads and stores that it can prove:

  (a) access a region in the range [-0x8000 + bottom of stack frame,
      0x7fff + top of stack frame]; or
  (b) access a link-time-constant address.

  Here, a ``sequentially-executed series'' is one in which calls,
  jumps and branches occur only as the last instruction.

-mr10k-cache-barrier=store
  Like -mr10k-cache-barrier=load-store, but ignore all loads.

-mr10k-cache-barrier=none
  ...

And if you guys are willing to make sure that's safe, and change
the kernel whenever you find instances that it isn't safe, then
that should be enough.  (Bear in mind that there's ongoing work
to do link-time optimisation in gcc, so translation-unit separation
is no real guarantee.)

Richard

---

From: Ralf Baechle <[email-masked]>
Date: Sun, 9 Dec 2007 04:38:21 +0000

On Sat, Dec 08, 2007 at 08:09:31PM +0000, Richard Sandiford wrote:

> but I think it needs to be stated explicitly.

Can't harm to be explicit.  Linux forbids DMA to the stack.  In that past
DMA to the stack has caused alot of grief for Linux ports on some
architectures.

> Then there's the language-lawyerly code I gave to Peter on gcc-patches@:
> 
>      void foo (int x)
>      {
>        int array[1];
>        if (x)
>          bar (array[0x1fff]);
>      }
> 

Interesting test case.  I've been thinking about it myself but in the end
decieded to believe Peter's analysis since he's banged the head for longer
to the wall about this problem that I have ;-)  I'm quite but not absolutely
certain that this case cannot happen for realworld code, so I'd rather
err on the side of caution.

Peter & Thomas - we could make the stack thing bullet proof by vmallocing
stacks and ensuring a sufficient virtual address gap exists around the stack
such that the stack is the only addressable thing in the range of
$sp +0x7fff / -0x8000?

A -mr10k-cache-barrier=sp-is-safe option?

> less obvious assumption than the stack one.

The latter assumption is also needed for -msym32 kernels, so it's well
proven to be valid.  The former hold, too.

>  Again, I understand that

In case of a hypothetic multi-platform kernel of which at least one needs
the R10000 workarounds, all code would be uniformly compiled with the
magic -mr10k-cache-barrier option and all source level workaround would
be enabled.

> anything a gcc hacker or user needs to know about the gcc patch.

Your help is certainly appreciated and trying to find the potencial holes
here will only help.

  Ralf

---

From: Richard Sandiford <[email-masked]>
Date: Mon, 10 Dec 2007 11:00:54 +0000

> such that the stack is the only addressable thing in the range of

FWIW, my first cut at the option restrictions were based on what
the patch exempts (and doesn't exempt).  We could instead get gcc
to only exempt accesses that it can prove are either to the current
function's stack frame or to its stack arguments.  I.e. rather than
consider every $sp-based access to be safe, we'd instead do some
bounds checking on the value.  (We could also use MEM_ATTRS to
pick up cases where a stack variable is acceesed via something
other than the stack or frame pointers, as happens for large frames.)

> magic -mr10k-cache-barrier option and all source level workaround would

Hmm.  This probably shows I am misunderstanding the problem, but I was
thinking about the IO-mapped case.  I thought one of the problems was
that if you had a cached speculative load or store to an access-sensitive
IO-mapped address, the IO-mapped device might "see" that access even if it
doesn't take place.  Could you not have a situation where a KSEG0 or
XKSEG0 access is access-sensitive on one machine and not another?
The patch won't insert countermeasures before symbolic and constant
addresses, because it believes all such addresses to be safe.

I'm also a little worried that the compiler is free to make up accesses
that didn't exist in the original program, provided that those accesses
are never actually performed in cases where they'd be wrong.  So how about:

-mr10k-cache-barrier=load-store
  Insert a cache barrier at the beginning of any sequentially-executed
  series of instructions that contains a load or store.  For the purposes
  of this option, GCC can ignore loads and stores that it can prove
  are an in-range access to:

  (a) the current function's stack frame;
  (b) an incoming stack argument;
  (b) an object with a link-time-constant address; or
  (c) a block of uncached memory

  It can also ignore sequences that are always immediately preceded by
  an untaken branch-likely instruction.

Richard

---

From: peter fuerst <[email-masked]>
Date: Wed, 12 Dec 2007 16:26:31 +0100 (CET)

> >> Then there's the language-lawyerly code I gave to Peter on gcc-patches@:

A strange method to pass data... Of course, cooking up such an "ABI",
where local variables are accessed with a const offset that is not known at
compile-time to be valid, would subvert the test for $sp-based accesses...

> > such that the stack is the only addressable thing in the range of

...but having an address-gap, virtual or by unused memory, should make it save
even with such code.

Typical "realworld" examples for speculative access to stack-variables are

void foo (int x)             void foo ()
{                            {
  int array[N];                int array[N], i;
  if (x < N)                   for (i = 0; i < N; i++)
    bar (array[x]);              array[i] = 0;
}                            }
i.e. accesses with non-const offsets, i.e. no longer $sp-based, which always
will trigger a CB.

> consider every $sp-based access to be safe, we'd instead do some

"every $sp-based access" (set(mem(plus(sp)(const_int)))) is restricted
to local variables too, with the constant offset being either
- compiler-generated or
- deliberately put in the source (however including the above example)

> bounds checking on the value.
Fine, if that is possible.

>                                (We could also use MEM_ATTRS to

Aren't these always accesses with non-constant offset, where a CB can't be
avoided, even if they are recognized as being actually relative to $sp ?

> addresses, because it believes all such addresses to be safe.

The threat to IO-addresses comes from the addressing register in the speculated
mem-instruction (set(mem(plus(reg)...), containing one of the addresses as
"garbage".

Symbolic addresses are well defined from link-time on, no matter what history
before the access.  They either point (set(mem(plus(symbol_ref)...) to
- some variable in the cached area, what is harmless (unless DMA-related),
  or to
- IO-devices, accessed uncached, i.e. non-speculative,
unless there is a programming-error ;)
The same holds for const_int used as address.

If used for DMA and also directly accessed, symbolic addresses could be
problematic though:
extern char big_fat_dma_buffer[N];
if (!dma_running)
	*big_fat_dma_buffer = 0;
else
	...
(However, as soon as accessed with non-constant offset - e.g. in a loop,... -
the symbol_ref disappears from the mem-instruction which will trigger a CB)

Btw. with 4.x symbolic addresses are practically (without backtrace analysis)
not exempted from CBs, since they no longer show up in the mem-instruction
and (set(mem(lo_sum(reg)... is seen instead.

> that didn't exist in the original program, provided that those accesses
The cache-barrier itself ?

>   (c) a block of uncached memory
Can we recognize uncached memory in the instruction ?

>   an untaken branch-likely instruction.
Fine!

kind regards

peter

---

From: Richard Sandiford <[email-masked]>
Date: Wed, 12 Dec 2007 18:09:31 +0000

> compile-time to be valid, would subvert the test for $sp-based accesses...

Well, as I said when I gave that example originally, it's unlikely that
the example would be written in that form.  But hide the constants and
checks in configurable macros, and the general idea becomes a little
more feasible.

> - deliberately put in the source (however including the above example)

That's not literally true.  SP+INT addresses can be used to access
stack arguments too, and 4.x can optimise some varargs accesses to
compile-time base+offset addresses.  And as I said, the compiler is
free to make up accesses that aren't in fact valid for cases where
the access isn't made.  E.g. if you had a loop with a stride of 128,
the compiler could unroll the loop as many times as it likes.  Some
of the unrolled iterations might access areas outside the stack frame.
(You would hope that the compiler would be intelligent enough to crop
the iteration count in such cases, because the extra iterations should
never be used in valid code.  But that isn't the point.  The compiler
doesn't _need_ to crop the iteration count for correctness, and we're
talking about something we _do_ need for correctness.)

> Fine, if that is possible.

FWIW, the frame info is available in cfun->machine->frame at the time
your code runs.

> avoided, even if they are recognized as being actually relative to $sp ?

The MEM_ATTRS I meant were MEM_EXPR + MEM_OFFSET, which only apply where
there is a known constant offset.

> The same holds for const_int used as address.

I think you're missing my point.  If you access an I/O-mapped device
through KSEG2 or an uncached XKPHYS address, is it not also physically
possible (though clearly unwise) to access it through KSEG0 or a cached
XKPHYS address too?  So can you guarantee that every const_int cached
address in a multi-platform kernel is not I/O-mapped on any of the r10k
platforms?  Or can you guarantee that the compiler will not manufacture
such an address from an otherwise harmless address?  Again, the key thing
is to think about what the compiler can validly do on non-r10k platforms,
however silly it might seem, and then make sure the workarounds cope
with it.

> The cache-barrier itself ?

No, in general.  Optimisers (particularly loop optimisers) can invent
accesses that didn't exist in the original source code.  Normally they
would only be executed in correct circumstances, but with this
speculative execution, that might not be true.

> Can we recognize uncached memory in the instruction ?

Well, I was just thinking about teaching the compiler about KSEG2,
the always-uncached XKPHYS addresses, etc.  (Sorry for messing up
the bullet letters there!)  The idea is that we have a correlation
between symbolic constants and C objects, so we can check whether
an offset in a symbolic constant is within the object.  We already
have code to do this in other situations.  But there is no correlation
between const_int addresses and C objects, and we cannot be sure that
a given const_int address existed in the original source code, so
I think the only safe thing is to check its uncached properties instead.

I know all this must be frustrating.  I'm sure your patches work great
as they are with current and past kernels, and current and past compilers.
The problem is that, if it becomes a mainline gcc feature, it needs to be
defined from first principles.  And we need to do that without assuming
that the accesses we're looking at existed in the original source code.

FWIW, I'm happy to help update the patch once we've agreed on an
option spec.

Richard

---

From: Richard Sandiford <[email-masked]>
Date: Wed, 12 Dec 2007 18:22:25 +0000

> through KSEG2 or an uncached XKPHYS address, is it not also physically

er, I meant KSEG1 of course.  Same mistake later.

Richard