[RFC/PATCH] sparc32/LEON: Cache flush during context switch

[RFC/PATCH] sparc32/LEON: Cache flush during context switch

[Matthias Rosenfelder]

Hello,

I looked at the Leon code base and noticed several issues:

1.) As far as I can see, the leon_flush_needed() in mm/leon_mm.c is only
called from init_leon() in mm/srmmu.c. init_leon() is marked as __init,
but the leon_flush_needed() is not. So there is no point in having still
leon_flush_needed() lying around after boot and we should also add
__init to it.
But looking further at leon_flush_needed() reveals other things...


2.) What is the code in leon_flush_needed() actually doing? It tries to
conclude from the Leon cache config if a cache flush is needed during a
context switch. But as far as I know, this is never necessary. Why?
Because the Leon data and instruction caches hit only if the following
two conditions are true:

a) the virtual tag matches the upper bits of the virtual address in a
    given set and(!)
b) the current context number (from the SRMMU) matches the context
    number belonging to each cache line.

    The two conditions above ensure that if we change the address space,
there will _never_ be a cache hit that returns data from the old address
space. In fact, the moment we write a new (i.e. different) value into
the context number register of the SRMMU, the whole data cache will
become invalid. Every following access is guaranteed to produce a cache
miss because the context number does not match any more (even though the
valid bits may still be set). The currently residing cache lines will
then be evicted eventually during the following memory accesses
(assuming we don't change back to the old address space soon).

     The hit detection mechanism is mentioned in the GRIP manual [1] from
Aeroflex Gaisler (page 639, Section 62.6.1) and can be additionally
verified by looking into the Leon3 VHDL code (available at [2]) in
mmu_dcache.vhd, lines 512 -- 516. The same hit detection mechanism is
used for the instruction cache, too. For Leon4 I didn't find exact
information on cache hit generation in the manual. However, reading the
cache description in the manual makes me assume this has not changed
(it's almost the same text word for word). So, I'm not sure about Leon4
but at least for Leon3 flushing is not necessary.

    The Leon3 and 4 can also have physical tags but they are used _only_
for snooping / cache coherency. They are not used for hit/miss detec-
tion. Only the virtual tags and the context number belonging to every
cache line are used for hit/miss detection. It is therefore safe to
_always_ omit cache flushing during context switching. Remember that
the Leon caches are write-through, so main memory is always up-to-date.

    Thus, we can simply replace the whole leon_flush_needed() function
body with "return 0;". However, this also destroys the cache information
printed at boot time. Therefore, I suggest to add an explicit
print_leon3_cache_config() function. This also has the advantage that we
can correct the wrong cache terminology by Gaisler. During the Leon 2
and 3 development, they mixed up the cache "set" and cache "way" terms.
The VHDL code as well as the manuals for these processors are full of
these errors, but apparently for Leon4 they got it right. Thumbs up.

     In the last year, I have been using the Snapgear Linux distribution
from Gaisler based on kernel 2.6.21.1 on Leon2- and Leon3-based systems
without flushing the caches during a context switch. I experienced no
problems. However, I have not yet tested this on the current kernel
version but I'm pretty sure it will work there, too.


3.) The GRIP manual also says that a "flush" instruction flushes both
the data and the instruction cache (Section 62.5.1 on page 636). But for
flushing all caches in leon_flush_cache_all() not only a "flush"
instruction is issued but afterwards follows an explicit data cache
flush with a write to ASI_LEON_DFLUSH. Either the manual is wrong (which
would not amaze me much) or the second write is rather unnecessary.
However, I assume this does not hurt performance much as the cache is
already flushed by the "flush" right before.


What are your opinion on these three issues?
Thanks,

     Matthias

[1] http://www.gaisler.com/products/grlib/grip.pdf
[2] http://www.gaisler.com/products/grlib/grlib-gpl-1.1.0-b4104.zip

Re: [RFC/PATCH] sparc32/LEON: Cache flush during context switch

[Daniel Hellstrom]

Matthias Rosenfelder wrote:

> Hello,
>
> I looked at the Leon code base and noticed several issues:
>
> 1.) As far as I can see, the leon_flush_needed() in mm/leon_mm.c is only
> called from init_leon() in mm/srmmu.c. init_leon() is marked as __init,
> but the leon_flush_needed() is not. So there is no point in having still
> leon_flush_needed() lying around after boot and we should also add
> __init to it.
> But looking further at leon_flush_needed() reveals other things...

True, it should only be called once on startup. leon_flush_needed() 
should be __init. Please submit a patch for this.

>
>
> 2.) What is the code in leon_flush_needed() actually doing? It tries to
> conclude from the Leon cache config if a cache flush is needed during a
> context switch.

Yes it does.

> But as far as I know, this is never necessary. Why?
> Because the Leon data and instruction caches hit only if the following
> two conditions are true:
>
> a) the virtual tag matches the upper bits of the virtual address in a
>    given set and(!)
> b) the current context number (from the SRMMU) matches the context
>    number belonging to each cache line.


Have you taken cache aliasing into account? The problem may be that the 
same physical address may be mapped onto different virtual addresses. 
This is no problem when there is only one location in the cache multiple 
virtual addresses with the same page offset can be located at, one 
virtual address mapped to the same physical address will replace the 
other. That is why the check is for 4KByte cache of less (less then one 
page) and only one set.

I have seen problems appearing when using shared memory or NFS. 
Debugging this kind of problem is not easy, I can say honstly that apart 
from another hardware related problem this was the hardest to pinpoint 
so far in my career.

Note that there is a non-standard SRMMU modification to the LEON that 
can be enabled, by changing the page size to 8k or 16k this problem can 
be avoided a bit more. That patch required modifications to both kernel 
and toolchain, it exists only for 2.6.21.1.

>
>    The two conditions above ensure that if we change the address space,
> there will _never_ be a cache hit that returns data from the old address
> space. In fact, the moment we write a new (i.e. different) value into
> the context number register of the SRMMU, the whole data cache will
> become invalid. Every following access is guaranteed to produce a cache
> miss because the context number does not match any more (even though the
> valid bits may still be set). The currently residing cache lines will
> then be evicted eventually during the following memory accesses
> (assuming we don't change back to the old address space soon).
>
>     The hit detection mechanism is mentioned in the GRIP manual [1] from
> Aeroflex Gaisler (page 639, Section 62.6.1) and can be additionally
> verified by looking into the Leon3 VHDL code (available at [2]) in
> mmu_dcache.vhd, lines 512 -- 516. The same hit detection mechanism is
> used for the instruction cache, too. For Leon4 I didn't find exact
> information on cache hit generation in the manual. However, reading the
> cache description in the manual makes me assume this has not changed
> (it's almost the same text word for word). So, I'm not sure about Leon4
> but at least for Leon3 flushing is not necessary.
>
>    The Leon3 and 4 can also have physical tags but they are used _only_
> for snooping / cache coherency. They are not used for hit/miss detec-
> tion. Only the virtual tags and the context number belonging to every
> cache line are used for hit/miss detection. It is therefore safe to
> _always_ omit cache flushing during context switching. Remember that
> the Leon caches are write-through, so main memory is always up-to-date.

Please send document errors and question about LEON CPU implementation 
to support_at_gaisler.com instead.

>
>    Thus, we can simply replace the whole leon_flush_needed() function
> body with "return 0;". However, this also destroys the cache information
> printed at boot time. Therefore, I suggest to add an explicit
> print_leon3_cache_config() function. This also has the advantage that we
> can correct the wrong cache terminology by Gaisler. During the Leon 2
> and 3 development, they mixed up the cache "set" and cache "way" terms.
> The VHDL code as well as the manuals for these processors are full of
> these errors, but apparently for Leon4 they got it right. Thumbs up.

Please do not change this.

We are well aware of this problem, I think some day Jiri will present a 
solution.

>
>     In the last year, I have been using the Snapgear Linux distribution
> from Gaisler based on kernel 2.6.21.1 on Leon2- and Leon3-based systems
> without flushing the caches during a context switch. I experienced no
> problems. However, I have not yet tested this on the current kernel
> version but I'm pretty sure it will work there, too.

The old kernel also included leon_flush_needed(), however the code also 
took LEON2 into account. So what is your cache configuration? Do you 
feel lucky? :)

>
>
> 3.) The GRIP manual also says that a "flush" instruction flushes both
> the data and the instruction cache (Section 62.5.1 on page 636). But for
> flushing all caches in leon_flush_cache_all() not only a "flush"
> instruction is issued but afterwards follows an explicit data cache
> flush with a write to ASI_LEON_DFLUSH. Either the manual is wrong (which
> would not amaze me much) or the second write is rather unnecessary.
> However, I assume this does not hurt performance much as the cache is
> already flushed by the "flush" right before.

flush instruction in sparc V8/7 means instruction flush, this is 
probably only a documentation error. Please send this to our support.

Best Regards,
Daniel Hellstrom

>
>
> What are your opinion on these three issues?
> Thanks,
>
>     Matthias
>
> [1] http://www.gaisler.com/products/grlib/grip.pdf
> [2] http://www.gaisler.com/products/grlib/grlib-gpl-1.1.0-b4104.zip
>
>

Re: [RFC/PATCH] sparc32/LEON: Cache flush during context switch

[Matthias Rosenfelder]

Am 10.05.2011 09:19, schrieb Daniel Hellstrom:
 >
 > Have you taken cache aliasing into account? The problem may be that
 > the same physical address may be mapped onto different virtual
 > addresses. This is no problem when there is only one location in
 > the cache multiple virtual addresses with the same page offset can
 > be located at, one virtual address mapped to the same physical
 > address will replace the other. That is why the check is for 4KByte
 > cache of less (less then one page) and only one set.

In this case cache aliasing is not an issue. It is only a problem if two
aliases (i.e. two virtual addresses that are mapped to the same
physical address) can be present in the cache _and_ the cache can
generate a hit when reading from one of these two after having written
the other one before. Then the cache hit will return the old data rather
than then new ones.

But in the case of context switching the cache does not generate a hit.
The context number stored alongside every cache line prevents this. You
never get a cache hit from data that was pulled into the cache in a
different address space than the current. That's why after _changing_
the address space the cache will produce a series of misses. It is like
flushing the cache atomically within one cycle when you write a
different context number into the SRMMU register.


 >
 > I have seen problems appearing when using shared memory or NFS.
 > Debugging this kind of problem is not easy, I can say honstly that
 > apart from another hardware related problem this was the hardest to
 > pinpoint so far in my career.

Even if the new and the old address spaces have shared memory it doesn't
matter. Due to the write-through nature of the data cache main
memory is always up-to-date and any cache miss will read correct data.
And any cache access after the address space change _is guaranteed_
to produce a miss and never return any data stored there previously.

I'm aware of the fact that those problems are very hard to debug. That's
why I would like to hear from other people on this list if they also
think this is okay and there is no error in my argumentation or
thinking.



 >
 > Note that there is a non-standard SRMMU modification to the LEON that
 > can be enabled, by changing the page size to 8k or 16k this problem
 > can be avoided a bit more. That patch required modifications to both
 > kernel and toolchain, it exists only for 2.6.21.1.

Yes, I have seen this. I suppose it is just there to be able to enlarge
the cache while still preventing the cache aliasing. But this only works
with a direct-mapped cache. With any associativity larger than one there
exists the possibility that two virtual aliases reside in the same cache
set but in different ways.

So what about multi-way cache configurations? Virtual aliases between
different address spaces are no problem due to the context number but
what about virtual aliases within the same address space? I know that
for accessing I/O often MMU bypass ASI is used that bypasses the Leon
data cache and therefore prevents cache aliasing problems. But are there
any other areas in which several virtual pages in one address space are
mapped to the same physical page frame within the Linux kernel?



 >
 > Please send document errors and question about LEON CPU implementation
 > to support_at_gaisler.com instead.
 >

Okay, I will do this.


 >>
 >> This also has the advantage that we
 >> can correct the wrong cache terminology by Gaisler. During the Leon 2
 >> and 3 development, they mixed up the cache "set" and cache "way" terms.
 >> The VHDL code as well as the manuals for these processors are full of
 >> these errors, but apparently for Leon4 they got it right. Thumbs up.
 >
 > Please do not change this.
 >
 > We are well aware of this problem, I think some day Jiri will present a
 > solution.

Hmm, this is non-standard terminology. How can others understand the
source code if it doesn't use the generally accepted terms found in
textbooks about computer architecture?

I think this might confuse a lot of people (as it did confuse me
in the past until I found out and understood the error) and should
therefore not be tolerated to remain in the Linux kernel in the long
run. The promise of a solution "some day" is way too vague for my taste.
This should be changed in the near future.


 >
 >>
 >> In the last year, I have been using the Snapgear Linux distribution
 >> from Gaisler based on kernel 2.6.21.1 on Leon2- and Leon3-based systems
 >> without flushing the caches during a context switch. I experienced no
 >> problems. However, I have not yet tested this on the current kernel
 >> version but I'm pretty sure it will work there, too.
 >
 > The old kernel also included leon_flush_needed(), however the code also
 > took LEON2 into account. So what is your cache configuration? Do you
 > feel lucky? :)
 >

I have been testing various cache configurations, mostly with Leon2 but
recently also with Leon3. Our latest configuration for Leon2 uses a
24 kiB data cache (3 way set associative; way size 8 kiB). The
instruction cache is 8 kiB in size (4 way set associative; way size
2 kiB). This works with the old Snapgear kernel and no cache flushing on
a context switch without experiencing problems. :-)

The Leon3 cache configuration is the standard one. If I remember
correctly there are a 4 kiB direct-mapped and a 8 kiB 2-way associative
cache but I don't remember which one was for data and instructions.


Thanks,

      Matthias



P.S.: I have not seen my first mail to appear on the list yet. But it is 
shown by marc.info as being received:

http://marc.info/?l=linux-sparc&m\x130501201909654&w=2

Is this my fault? I've not been using mailing lists before...

Re: [RFC/PATCH] sparc32/LEON: Cache flush during context switch

[Kristoffer Glembo]

Matthias Rosenfelder wrote:
> Am 10.05.2011 09:19, schrieb Daniel Hellstrom:
>>
>> Have you taken cache aliasing into account? The problem may be that
>> the same physical address may be mapped onto different virtual
>> addresses. This is no problem when there is only one location in
>> the cache multiple virtual addresses with the same page offset can
>> be located at, one virtual address mapped to the same physical
>> address will replace the other. That is why the check is for 4KByte
>> cache of less (less then one page) and only one set.
> 
> In this case cache aliasing is not an issue. It is only a problem if two
> aliases (i.e. two virtual addresses that are mapped to the same
> physical address) can be present in the cache _and_ the cache can
> generate a hit when reading from one of these two after having written
> the other one before. Then the cache hit will return the old data rather
> than then new ones.
> 
> But in the case of context switching the cache does not generate a hit.
> The context number stored alongside every cache line prevents this. You
> never get a cache hit from data that was pulled into the cache in a
> different address space than the current. That's why after _changing_
> the address space the cache will produce a series of misses. It is like
> flushing the cache atomically within one cycle when you write a
> different context number into the SRMMU register.
> 


The cache can generate a hit after a context switch if there exists cache lines
belonging to the newly switched in process. Then the new process can get a hit in 
the cache when another process has updated the value in memory. Just because you write 
the context register it does not mean that the cache is automatically invalidated.

You could avoid this if you always make shared memory regions non-cacheable. I don't know 
enough to say whether this is currently possible.



>> We are well aware of this problem, I think some day Jiri will present a
>> solution.
> 
> Hmm, this is non-standard terminology. How can others understand the
> source code if it doesn't use the generally accepted terms found in
> textbooks about computer architecture?

> I think this might confuse a lot of people (as it did confuse me
> in the past until I found out and understood the error) and should
> therefore not be tolerated to remain in the Linux kernel in the long
> run. The promise of a solution "some day" is way too vague for my taste.
> This should be changed in the near future.


I think Daniel meant a solution to the cache coherency problem. It is possible to
fully avoid aliases in hardware.

What terminology do you have a problem with in the Linux kernel? That it is written
"set size" instead of "way size" in some comments? I don't think "set size" is an uncommon
alias for "way size" ...



> The Leon3 cache configuration is the standard one. If I remember
> correctly there are a 4 kiB direct-mapped and a 8 kiB 2-way associative
> cache but I don't remember which one was for data and instructions.
> 

Try using shared memory to a greater extent.

Best regards,
Kristoffer Glembo
Aeroflex Gaisler

Re: [RFC/PATCH] sparc32/LEON: Cache flush during context switch

[Matthias Rosenfelder]

On 10.05.2011 13:26, Kristoffer Glembo wrote:
>
> The cache can generate a hit after a context switch if there exists cache lines
> belonging to the newly switched in process.

Is this really possible? You mean that the cache line has "survived" 
during the execution of the last timeslice of another (i.e. different) 
task AND that the last and the new task have shared a memory region AND 
this shared memory region is susceptible to virtual aliasing in the data 
cache AND the last task has actually written to one of these virtual 
addresses AND the new task actually reads from exactly this virtual 
alias address that the last task wrote to?

This seems very unlikely to me but I must admit that you have a point 
here. It is possible in theory, though very unlikely.

But then what is the context number stored for every cache line for?
Only for the case when you have a tiny cache with the lowest possible 
associativity that you can save a few cycle on a context switch? People 
want _big_ caches with _high_ associativity in order to improve the hit 
rate. Having a bigger cache even if you have to flush it on a context 
switch is much better for performance than having a tiny one without a 
flush. Why do you waste so much hardware on a feature that has so little 
benefit?



> You could avoid this if you always make shared memory regions non-cacheable. I don't know
> enough to say whether this is currently possible.

I don't think this is a good idea. It is propably better to still use 
caches and flush the caches on a context switch than making these 
regions uncacheable at all. This will propably slow down access to these 
regions too much.


>
> I think Daniel meant a solution to the cache coherency problem. It is possible to
> fully avoid aliases in hardware.

Ah yes, of course.

>
> What terminology do you have a problem with in the Linux kernel? That it is written
> "set size" instead of "way size" in some comments? I don't think "set size" is an uncommon
> alias for "way size" ...

But I do. A cache set consists of all cache lines in a cache that can 
store data belonging to addresses that have the same index (i.e. the 
"middle" part of the cache address is the same for all cache lines in a 
cache set). The way size is the sum of all cache lines that belong to a 
certain way, i.e. the n-th possiblity within a cache set to store and 
retrieve a cache line. Way zero is the first possibility in each set; 
Way one is the second and so on...
Cache lines belonging to the same way don't necessarily have any address 
bits in common. Whereas the cache lines belonging to a cache set do...

By the way: If it is correct what you say then why was this changed for 
the Leon4 manual? Leon2 and 3 manuals use the wrong terminology while 
the Leon4 manual uses the correct one. Obviously, there must be at least 
one person at Gaisler who believes that the previous terminology was not 
correct. Leon2 and 3 manual mention "multi-set caches" while 
Leon4-manual mentions "multi-way caches". Look at the GRLIB ipcore 
user's manual.

One thing in addition: Please don't get me wrong. I don't want to blame 
anybody too much. I just would like to see consistent terminology in the 
code so it is easier for everybody to understand. That's all I am aiming 
for.


Thanks,

      Matthias

Re: [RFC/PATCH] sparc32/LEON: Cache flush during context switch

[Kristoffer Glembo]

Matthias Rosenfelder wrote:

> This seems very unlikely to me but I must admit that you have a point
> here. It is possible in theory, though very unlikely.
> 

In practice, unlikely thing do happen ...


> But I do. A cache set consists of all cache lines in a cache that can
> store data belonging to addresses that have the same index (i.e. the
> "middle" part of the cache address is the same for all cache lines in a
> cache set). 

Please feel free to send patches correcting the things you find confusing.

Best regards
Kristoffer Glembo
Aeroflex Gaisler

Re: [RFC/PATCH] sparc32/LEON: Cache flush during context switch

[Daniel Hellstrom]

Daniel Hellstrom wrote:

>>
>>    Thus, we can simply replace the whole leon_flush_needed() function
>> body with "return 0;". However, this also destroys the cache information
>> printed at boot time. Therefore, I suggest to add an explicit
>> print_leon3_cache_config() function. This also has the advantage that we
>> can correct the wrong cache terminology by Gaisler. During the Leon 2
>> and 3 development, they mixed up the cache "set" and cache "way" terms.
>> The VHDL code as well as the manuals for these processors are full of
>> these errors, but apparently for Leon4 they got it right. Thumbs up.
>
>
> Please do not change this.

I was referring to the functionality of the leon_flush_needed() code, 
please improve comments and/or clean up code.

Daniel