TLB evaluation for Linux

TLB evaluation for Linux

[CHADHA,VINEET]

Hi,

I have been working to evaluate TLB performance for Linux O/S and 
virtualized workloads(such as Xen) in a Full system simulator(e.g. 
simics). While my evaluation is in nascent stage, I do notice that 
most of the IPIs in multi-core environments cause complete TLB 
Flush.

I want to evaluate cost of TLB shootdown including re-population 
vs. each entry shootdown (invlpg). While a similar study has been 
done in other kernels (e.g. L4 kernel), I am not aware if it has 
been done for Linux O/S.

Are there hooks or patches to test or evaluate TLB performance. 
Specifically, I would like to know where to make changes in Linux 
kernel to support each entry shootdown.

Questions may sound little naive, but any pointers or related work 
will be helpful to me.

Thanks in advance.

Regards,
Vineet

Re: TLB evaluation for Linux

[Nick Piggin]

On Tuesday 02 September 2008 14:12, CHADHA,VINEET wrote:
> Hi,
>
> I have been working to evaluate TLB performance for Linux O/S and
> virtualized workloads(such as Xen) in a Full system simulator(e.g.
> simics). While my evaluation is in nascent stage, I do notice that
> most of the IPIs in multi-core environments cause complete TLB
> Flush.
>
> I want to evaluate cost of TLB shootdown including re-population
> vs. each entry shootdown (invlpg). While a similar study has been
> done in other kernels (e.g. L4 kernel), I am not aware if it has
> been done for Linux O/S.

This is a very interesting area to investigate. Do you have a link to
any of the existing studies?


> Are there hooks or patches to test or evaluate TLB performance.
> Specifically, I would like to know where to make changes in Linux
> kernel to support each entry shootdown.

The main thing I guess is to look at tlb_flush(), called by tlb_flush_mmu
when unmapping user virtual memory, which on x86 is going to call
flush_tlb_mm, which flushes the entire tlb.

It would need a bit of reworking of things in order to store the virtual
address corresponding to each page in the struct mmu_gather, and then
deciding to branch off to do multiple invlpg if you have only a small
number of pages to be flushed. I'd suggest the easiest way to get
something working on x86 would be to modify the asm-generic infrastructure
(ignore other architectures for the time being).

You will also have to rework the IPI flushing scheme so that it can handle
more than one flush_va for invlpg invalidations.

After you get all this done, you could also look at applying similar
heuristics to flush_tlb_range. This one should be much easier at this point,
but it is used in fewer places (eg. mprotect).

Re: TLB evaluation for Linux

[Andi Kleen]

"CHADHA,VINEET" <vineet@ufl.edu> writes:

> Hi,
>
> I have been working to evaluate TLB performance for Linux O/S and
> virtualized workloads(such as Xen) in a Full system
> simulator(e.g. simics). While my evaluation is in nascent stage, I do
> notice that most of the IPIs in multi-core environments cause complete
> TLB Flush.
>
> I want to evaluate cost of TLB shootdown including re-population
> vs. each entry shootdown (invlpg). While a similar study has been done
> in other kernels (e.g. L4 kernel), I am not aware if it has been done
> for Linux O/S.
>
> Are there hooks or patches to test or evaluate TLB
> performance. Specifically, I would like to know where to make changes
> in Linux kernel to support each entry shootdown.

Linux doesn't use a threshold to distingush between range flush
and full flush in certain situations, but always does the full
flush. 

That is something that might be possible to be improved, but it was so
far always unclear how much it helps (it depends on the particular TLB
size, cost of TLB refill etc.)

-Andi

-- 
ak@linux.intel.com

Re: TLB evaluation for Linux

[Arjan van de Ven]

On Tue, 2 Sep 2008 00:12:03 -0400 (EDT)
"CHADHA,VINEET" <vineet@ufl.edu> wrote:

> Hi,
> 
> I have been working to evaluate TLB performance for Linux O/S and 
> virtualized workloads(such as Xen) in a Full system simulator(e.g. 
> simics). While my evaluation is in nascent stage, I do notice that 
> most of the IPIs in multi-core environments cause complete TLB 
> Flush.

note that linux only does an ipi to processors that actually are
currently running a thread of the same program (or a kernel thread).
Old versions didn't do this (they also IPI'd idle processors), but
on modern cpus and modern kernels that's not supposed to happen anymore
(the C-states that flush the tlb anyway now do the kernel side
bookkeeping as well to avoid the wakeup+useless flush)
> 
> I want to evaluate cost of TLB shootdown including re-population 
> vs. each entry shootdown (invlpg). While a similar study has been 
> done in other kernels (e.g. L4 kernel), I am not aware if it has 
> been done for Linux O/S.
> 

one of the problems is that invlpg is rather expensive; in long-ago
experiments the threshold was like around a handful of pages already.
At that point.. all the bookkeeping isn't likely to be a win.
Esp since a tlb refill on x86 is quite cheap. 

-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: TLB evaluation for Linux

[CHADHA,VINEET]

Thanks Nick.

A PhD dissertation to study scalability of micro-kernels can be 
found :

http://l4ka.org/publications/2005/uhlig_phd-thesis_scalability.pdf

An example of study I would like to do through Full system 
simulator is in Figure 4.11.

Regarding TLB flushing modifications, I will get back to you (and 
mailing list) after I get a better understanding of source code.

Regards,
Vineet


On Tue Sep 02 00:39:00 EDT 2008, Nick Piggin 
<nickpiggin@yahoo.com.au> wrote:

> On Tuesday 02 September 2008 14:12, CHADHA,VINEET wrote:
>> Hi,
>> 
>> I have been working to evaluate TLB performance for Linux O/S and
>> virtualized workloads(such as Xen) in a Full system 
>> simulator(e.g.
>> simics). While my evaluation is in nascent stage, I do notice 
>> that
>> most of the IPIs in multi-core environments cause complete TLB
>> Flush.
>> 
>> I want to evaluate cost of TLB shootdown including re-population
>> vs. each entry shootdown (invlpg). While a similar study has been
>> done in other kernels (e.g. L4 kernel), I am not aware if it has
>> been done for Linux O/S.
> 
> This is a very interesting area to investigate. Do you have a 
> link to
> any of the existing studies?
> 
> 
>> Are there hooks or patches to test or evaluate TLB performance.
>> Specifically, I would like to know where to make changes in Linux
>> kernel to support each entry shootdown.
> 
> The main thing I guess is to look at tlb_flush(), called by 
> tlb_flush_mmu
> when unmapping user virtual memory, which on x86 is going to call
> flush_tlb_mm, which flushes the entire tlb.
> 
> It would need a bit of reworking of things in order to store the 
> virtual
> address corresponding to each page in the struct mmu_gather, and 
> then
> deciding to branch off to do multiple invlpg if you have only a 
> small
> number of pages to be flushed. I'd suggest the easiest way to get
> something working on x86 would be to modify the asm-generic 
> infrastructure
> (ignore other architectures for the time being).
> 
> You will also have to rework the IPI flushing scheme so that it 
> can handle
> more than one flush_va for invlpg invalidations.
> 
> After you get all this done, you could also look at applying 
> similar
> heuristics to flush_tlb_range. This one should be much easier at 
> this point,
> but it is used in fewer places (eg. mprotect).
> 
> 

Re: TLB evaluation for Linux

[CHADHA,VINEET]

On Tue Sep 02 09:43:53 EDT 2008, Arjan van de Ven 
<arjan@infradead.org> wrote:

> On Tue, 2 Sep 2008 00:12:03 -0400 (EDT)
> "CHADHA,VINEET" <vineet@ufl.edu> wrote:
> 

> note that linux only does an ipi to processors that actually are
> currently running a thread of the same program (or a kernel 
> thread).
> Old versions didn't do this (they also IPI'd idle processors), 
> but
> on modern cpus and modern kernels that's not supposed to happen 
> anymore
> (the C-states that flush the tlb anyway now do the kernel side
> bookkeeping as well to avoid the wakeup+useless flush)

Interesting to know about it.

> one of the problems is that invlpg is rather expensive; in 
> long-ago
> experiments the threshold was like around a handful of pages 
> already.
> At that point.. all the bookkeeping isn't likely to be a win.
> Esp since a tlb refill on x86 is quite cheap.

Yeah that is possible. Do you have link to any published work ? It 
would be still interesting to characterize and  compare behavior 
for new workloads scenarios such as virtual machines.

Re: TLB evaluation for Linux

[Arjan van de Ven]

On Tue, 2 Sep 2008 10:59:25 -0400 (EDT)
"CHADHA,VINEET" <vineet@ufl.edu> wrote:

> 
> On Tue Sep 02 09:43:53 EDT 2008, Arjan van de Ven 
> <arjan@infradead.org> wrote:
> 
> > On Tue, 2 Sep 2008 00:12:03 -0400 (EDT)
> > "CHADHA,VINEET" <vineet@ufl.edu> wrote:
> > 
> 
> > note that linux only does an ipi to processors that actually are
> > currently running a thread of the same program (or a kernel 
> > thread).
> > Old versions didn't do this (they also IPI'd idle processors), 
> > but
> > on modern cpus and modern kernels that's not supposed to happen 
> > anymore
> > (the C-states that flush the tlb anyway now do the kernel side
> > bookkeeping as well to avoid the wakeup+useless flush)
> 
> Interesting to know about it.
> 
> > one of the problems is that invlpg is rather expensive; in 
> > long-ago
> > experiments the threshold was like around a handful of pages 
> > already.
> > At that point.. all the bookkeeping isn't likely to be a win.
> > Esp since a tlb refill on x86 is quite cheap.
> 
> Yeah that is possible. Do you have link to any published work ? It 
> would be still interesting to characterize and  compare behavior 
> for new workloads scenarios such as virtual machines.
> 

I don't have a reference, but I'd not be surprised to see on virtual
machines for this to be even stronger; each invlpg would be a
hypercall, compared to only one for the total flush.

Re: TLB evaluation for Linux

[CHADHA,VINEET]

> I don't have a reference, but I'd not be surprised to see on 
> virtual
> machines for this to be even stronger; each invlpg would be a
> hypercall, compared to only one for the total flush.
> 

I agree that overhead could be more in virtual machines. Questions 
is that does VMs
are designed with evaluation of performance issues at 
micro-architetural level. Is this the best design for virtual 
machines or Linux ?

I don't see many numbers or published paper to make a claim.

Regards,
Vineet