Question about Context register in TLB refilling

Question about Context register in TLB refilling

[wilbur.chan]

Hi all,

I have some questions  concerning  TLB refilling mechanism on mips:



1) In linux ,esspecially in TLB refilling,  is Context[PTEBase] used
to store cpuid? (refer to build_get_pgde32 in tlbex.c)


2) In function of build_get_ptep, when generating a   pte offset , is
Context[BadVPN]  replaceable  by BadVAddr register?


Thanks in advance

Re: Question about Context register in TLB refilling

[Kevin Cernekee]

On Sun, Oct 17, 2010 at 8:51 AM, wilbur.chan <wilbur512@gmail.com> wrote:
> 1) In linux ,esspecially in TLB refilling,  is Context[PTEBase] used
> to store cpuid? (refer to build_get_pgde32 in tlbex.c)

On 32-bit systems, PTEBase stores a byte offset that can be added to
&pgd_current[0].  i.e. smp_processor_id() * sizeof(unsigned long)

So the TLB refill handler can find pgd for the current CPU using code
that looks something like this:

   0:   401b2000        mfc0    k1,c0_context
   4:   3c1a8054        lui     k0,0x8054
   8:   001bddc2        srl     k1,k1,0x17
   c:   035bd821        addu    k1,k0,k1
...
  14:   8f7b5008        lw      k1,20488(k1)

where pgd_current is at 0x8054_5008, and PTEBase is 0, 4, 8, 12, ...

See also: TLBMISS_HANDLER_SETUP().

For 64-bit systems with CONFIG_MIPS_PGD_C0_CONTEXT, it looks like a
direct pgd pointer is now being stored in Context, to speed up the TLB
handlers.

Re: Question about Context register in TLB refilling

[Maciej W. Rozycki]

On Sun, 17 Oct 2010, Kevin Cernekee wrote:

> > 1) In linux ,esspecially in TLB refilling,  is Context[PTEBase] used
> > to store cpuid? (refer to build_get_pgde32 in tlbex.c)
> 
> On 32-bit systems, PTEBase stores a byte offset that can be added to
> &pgd_current[0].  i.e. smp_processor_id() * sizeof(unsigned long)
> 
> So the TLB refill handler can find pgd for the current CPU using code
> that looks something like this:
> 
>    0:   401b2000        mfc0    k1,c0_context
>    4:   3c1a8054        lui     k0,0x8054
>    8:   001bddc2        srl     k1,k1,0x17
>    c:   035bd821        addu    k1,k0,k1
> ...
>   14:   8f7b5008        lw      k1,20488(k1)
> 
> where pgd_current is at 0x8054_5008, and PTEBase is 0, 4, 8, 12, ...

 It has been always making me wonder (though not as much to go and dig 
through our code ;) ) why Linux is uncapable of using the value presented 
by the CPU in the CP0 Context register as is, or perhaps after a trivial 
operation such as a left-shift by a constant number of bits (where the 
size of the page entry slot assumed by hardware turned out too small).  
There should be no need to add another constant as in the piece of code 
you have quoted -- this constant should already have been preloaded to 
this register when switching the context the last time.  The design of the 
TLB refill exception in the MIPS Architecture has been such as to allow 
this register to be readily used as an address into the page table.  
Hmm...

  Maciej

Re: Question about Context register in TLB refilling

[Kevin Cernekee]

On Sun, Oct 17, 2010 at 12:33 PM, Maciej W. Rozycki
<macro@linux-mips.org> wrote:
>> where pgd_current is at 0x8054_5008, and PTEBase is 0, 4, 8, 12, ...
>
>  It has been always making me wonder (though not as much to go and dig
> through our code ;) ) why Linux is uncapable of using the value presented
> by the CPU in the CP0 Context register as is, or perhaps after a trivial
> operation such as a left-shift by a constant number of bits (where the
> size of the page entry slot assumed by hardware turned out too small).
> There should be no need to add another constant as in the piece of code
> you have quoted -- this constant should already have been preloaded to
> this register when switching the context the last time.  The design of the
> TLB refill exception in the MIPS Architecture has been such as to allow
> this register to be readily used as an address into the page table.

On plain old 32-bit MIPS:

The pgd entry for "va" is at address: (unsigned long)pgd + ((va >> 22) << 2)

i.e. each 4-byte entry in the pgd table represents 4MB of virtual address space.

PTEBase only gives you 9 bits to work with.  If you use it to store
pgd[31:23] directly, that means every pgd needs to be 8MB-aligned -
ouch.

You could potentially use PTEBase to store more of the significant bits, e.g.

pgd = 0x8000_0000 | (PTEBase << 12)

But that still places limits on where the pgd table can be stored, and
probably adds a decent number of extra arithmetic operations to each
handler.

Re: Question about Context register in TLB refilling

[Maciej W. Rozycki]

On Sun, 17 Oct 2010, Kevin Cernekee wrote:

> On plain old 32-bit MIPS:
> 
> The pgd entry for "va" is at address: (unsigned long)pgd + ((va >> 22) << 2)
> 
> i.e. each 4-byte entry in the pgd table represents 4MB of virtual address space.
> 
> PTEBase only gives you 9 bits to work with.  If you use it to store
> pgd[31:23] directly, that means every pgd needs to be 8MB-aligned -
> ouch.

 Good point!  I believe the original idea behind the Context and XContext 
registers was to put page tables somewhere within KSEG2/3 or XKSSEG which 
would make this alignment restriction not a problem, but I realise the 
overhead of placing page tables in paged memory may be higher than that of 
our current arrangement.

 I wonder however if such performance evaluation was actually ever made or 
whether it was the complexity of having page tables paged alone that 
scared people off. ;)

  Maciej

Re: Question about Context register in TLB refilling

[Ralf Baechle]

On Sun, Oct 17, 2010 at 08:33:24PM +0100, Maciej W. Rozycki wrote:

> > > 1) In linux ,esspecially in TLB refilling,  is Context[PTEBase] used
> > > to store cpuid? (refer to build_get_pgde32 in tlbex.c)
> > 
> > On 32-bit systems, PTEBase stores a byte offset that can be added to
> > &pgd_current[0].  i.e. smp_processor_id() * sizeof(unsigned long)
> > 
> > So the TLB refill handler can find pgd for the current CPU using code
> > that looks something like this:
> > 
> >    0:   401b2000        mfc0    k1,c0_context
> >    4:   3c1a8054        lui     k0,0x8054
> >    8:   001bddc2        srl     k1,k1,0x17
> >    c:   035bd821        addu    k1,k0,k1
> > ...
> >   14:   8f7b5008        lw      k1,20488(k1)
> > 
> > where pgd_current is at 0x8054_5008, and PTEBase is 0, 4, 8, 12, ...
> 
>  It has been always making me wonder (though not as much to go and dig 
> through our code ;) ) why Linux is uncapable of using the value presented 
> by the CPU in the CP0 Context register as is, or perhaps after a trivial 
> operation such as a left-shift by a constant number of bits (where the 
> size of the page entry slot assumed by hardware turned out too small).  
> There should be no need to add another constant as in the piece of code 
> you have quoted -- this constant should already have been preloaded to 
> this register when switching the context the last time.  The design of the 
> TLB refill exception in the MIPS Architecture has been such as to allow 
> this register to be readily used as an address into the page table.  
> Hmm...

The design of the R4000 c0_context / c0_xcontext register assumes 8 byte
ptes and a flat page table array.  You can map the pagetables into virtual
memory to get that and in fact very old Linux/MIPS versions did that but
that approach may result in aliases on some processors so I eventually
dropped it.  The implementation requires nested TLB refill implementations
and (Linux/MIPS was still using a.out in this days) I implemented a new
relocation type to squeeze a cycle out of the slow path.

The aliasing problem is solvable and it may be worth to revisit that old
piece of code again now 15 years later.

  Ralf

Re: Question about Context register in TLB refilling

[Gleb O. Raiko]

On 18.10.2010 4:00, Ralf Baechle wrote:
> The aliasing problem is solvable and it may be worth to revisit that old
> piece of code again now 15 years later.

Before anybody will start to prepare patches, I'd like to note using 
c0_context allows less than 128 processes (their mm contexts in fact but 
who cares) to be directly mapped on 32-bit cpus. So, some kind of 
caching needs to be implemented and it will add overhead on every mm 
switch. Sure, this overhead might be bounded for a real case where there 
is a small number of processes, so they all fit in the cache.
--- Beware, wild assumptions here ---
I'm afraid the cost of such caching still will be higher than loading 
pgd_current even from main memory on tlb refill.
--- End of wild assumptions ---

Gleb.

Re: Question about Context register in TLB refilling

[Ralf Baechle]

On Mon, Oct 18, 2010 at 02:46:02PM +0400, Gleb O. Raiko wrote:

> On 18.10.2010 4:00, Ralf Baechle wrote:
> >The aliasing problem is solvable and it may be worth to revisit that old
> >piece of code again now 15 years later.
> 
> Before anybody will start to prepare patches, I'd like to note using
> c0_context allows less than 128 processes (their mm contexts in fact
> but who cares) to be directly mapped on 32-bit cpus. So, some kind
> of caching needs to be implemented and it will add overhead on every
> mm switch. Sure, this overhead might be bounded for a real case
> where there is a small number of processes, so they all fit in the
> cache.
> --- Beware, wild assumptions here ---
> I'm afraid the cost of such caching still will be higher than
> loading pgd_current even from main memory on tlb refill.
> --- End of wild assumptions ---

64 context on R2000/R3000, 256 on everything else but R6000 and RM9000
series, 4096 contexts on RM9000 and that context caching is already
there.  It's fairly lightweight except in the rare case where the
PID / ASID number overflows and a full TLB flush becomes necessary.  A
mm context switch only needs to reload the one wired TLB entry that maps
the pagetables so that's not too bad.  The ugly part are the nested
TLB exceptions.  I dumped that very early on when I realized the cache
alias issues my implementation had so the earliest usable kernel versions
had the tree walking reload handlers.  That's why I don't have any
benchmark results.

  Ralf

Re: Question about Context register in TLB refilling

[Gleb O. Raiko]

On 18.10.2010 16:48, Ralf Baechle wrote:
> On Mon, Oct 18, 2010 at 02:46:02PM +0400, Gleb O. Raiko wrote:
> 64 context on R2000/R3000, 256 on everything else but R6000 and RM9000
> series, 4096 contexts on RM9000 and that context caching is already
> there.  It's fairly lightweight except in the rare case where the
> PID / ASID number overflows and a full TLB flush becomes necessary.  A
> mm context switch only needs to reload the one wired TLB entry that maps
> the pagetables so that's not too bad.

Ralf,

I counted from the opposite side. Size of KSEG2+KSEG3 is 1 GB, flat page 
table shall be 8 MB aligned to be stored in cp0 context, so we end up 
with 128 page tables in the theory (we have to reserve some space for 
other business too in practice).

If we are going to use a "standard" approach when only current page 
table is mapped, we know the address at compile time and don't need cp0 
context at all. We can even has as many page tables as number of ASIDs 
for cpus with multiple page sizes but cp0 context is still out of play 
anyway.

Gleb.

Re: Question about Context register in TLB refilling

[Maciej W. Rozycki]

On Mon, 18 Oct 2010, Ralf Baechle wrote:

> The design of the R4000 c0_context / c0_xcontext register assumes 8 byte
> ptes and a flat page table array.

 As I say you can increase the size by left-shifting the register.  
That's still cheaper than left-shifting and adding a 32-bit of worse yet a 
64-bit base.  Of course that implies higher yet an alignment and the PTE 
size of a power of two (which assuming at least a minimal level of sanity 
you want anyway).

 A flat structure is quite limiting (read: memory-greedy) indeed, but it 
looks to me with clever masking and shifting you should be able to get 
two-level page tables quite cheaply and easily too (on 32-bit).  Hmm...

> You can map the pagetables into virtual memory to get that and in fact 
> very old Linux/MIPS versions did that but that approach may result in 
> aliases on some processors so I eventually dropped it.  The 
> implementation requires nested TLB refill implementations and 
> (Linux/MIPS was still using a.out in this days) I implemented a new 
> relocation type to squeeze a cycle out of the slow path.

 Nested refills shouldn't be too much of a problem, but cache aliases 
always ask for troubles, hmm...  It may be worth investigating on 
processors with no aliases first, if at all.

  Maciej