Page Eviction Algorithm

Page Eviction Algorithm

[Prasad Joshi]

Hi All,

I was just going over TODO list on KVM page. In MMU related TODO I saw
only page eviction algorithm currently implemented is FIFO.

Is it really the case? If yes I would like to work on it. Can someone
let me know the place where the FIFO code is implemented?

Thanks and Regards,
Prasad

Re: Page Eviction Algorithm

[Avi Kivity]

  On 10/26/2010 11:19 AM, Prasad Joshi wrote:
> Hi All,
>
> I was just going over TODO list on KVM page. In MMU related TODO I saw
> only page eviction algorithm currently implemented is FIFO.
>
> Is it really the case?

Yes.

> If yes I would like to work on it. Can someone
> let me know the place where the FIFO code is implemented?

Look at the code that touches mmu_active_list.

FWIW improving the algorithm is not critically important.  It's rare 
that mmu shadow pages need to be evicted.

-- 
error compiling committee.c: too many arguments to function

Re: Page Eviction Algorithm

[Prasad Joshi]

Thanks a lot for your reply.

On Tue, Oct 26, 2010 at 11:31 AM, Avi Kivity <avi@redhat.com> wrote:
>  On 10/26/2010 11:19 AM, Prasad Joshi wrote:
>>
>> Hi All,
>>
>> I was just going over TODO list on KVM page. In MMU related TODO I saw
>> only page eviction algorithm currently implemented is FIFO.
>>
>> Is it really the case?
>
> Yes.
>
>> If yes I would like to work on it. Can someone
>> let me know the place where the FIFO code is implemented?
>
> Look at the code that touches mmu_active_list.
>
> FWIW improving the algorithm is not critically important.  It's rare that
> mmu shadow pages need to be evicted.

I would be doing a University project on Virtualization. I would like
to work on Linux kernel and KVM. I was looking over the TODO list on
KVM wiki.

Can you please suggest me something that would add value to KVM?

>
> --
> error compiling committee.c: too many arguments to function
>
>

Re: Page Eviction Algorithm

[Avi Kivity]

  On 10/26/2010 12:42 PM, Prasad Joshi wrote:
> Thanks a lot for your reply.
>
> On Tue, Oct 26, 2010 at 11:31 AM, Avi Kivity<avi@redhat.com>  wrote:
> >    On 10/26/2010 11:19 AM, Prasad Joshi wrote:
> >>
> >>  Hi All,
> >>
> >>  I was just going over TODO list on KVM page. In MMU related TODO I saw
> >>  only page eviction algorithm currently implemented is FIFO.
> >>
> >>  Is it really the case?
> >
> >  Yes.
> >
> >>  If yes I would like to work on it. Can someone
> >>  let me know the place where the FIFO code is implemented?
> >
> >  Look at the code that touches mmu_active_list.
> >
> >  FWIW improving the algorithm is not critically important.  It's rare that
> >  mmu shadow pages need to be evicted.
>
> I would be doing a University project on Virtualization. I would like
> to work on Linux kernel and KVM. I was looking over the TODO list on
> KVM wiki.
>
> Can you please suggest me something that would add value to KVM?
>

O(1) write protection (on the TODO page) is interesting and important.  
It's difficult, so you may want to start with O(1) invalidation.

-- 
error compiling committee.c: too many arguments to function

Re: Page Eviction Algorithm

[Prasad Joshi]

On Tue, Oct 26, 2010 at 2:07 PM, Avi Kivity <avi@redhat.com> wrote:
>  On 10/26/2010 12:42 PM, Prasad Joshi wrote:
>>
>> Thanks a lot for your reply.
>>
>> On Tue, Oct 26, 2010 at 11:31 AM, Avi Kivity<avi@redhat.com>  wrote:
>> >    On 10/26/2010 11:19 AM, Prasad Joshi wrote:
>> >>
>> >>  Hi All,
>> >>
>> >>  I was just going over TODO list on KVM page. In MMU related TODO I saw
>> >>  only page eviction algorithm currently implemented is FIFO.
>> >>
>> >>  Is it really the case?
>> >
>> >  Yes.
>> >
>> >>  If yes I would like to work on it. Can someone
>> >>  let me know the place where the FIFO code is implemented?
>> >
>> >  Look at the code that touches mmu_active_list.
>> >
>> >  FWIW improving the algorithm is not critically important.  It's rare
>> > that
>> >  mmu shadow pages need to be evicted.
>>
>> I would be doing a University project on Virtualization. I would like
>> to work on Linux kernel and KVM. I was looking over the TODO list on
>> KVM wiki.
>>
>> Can you please suggest me something that would add value to KVM?
>>
>
> O(1) write protection (on the TODO page) is interesting and important.  It's
> difficult, so you may want to start with O(1) invalidation.

I am not sure if I can understand what exactly is a MMU invalidation.
Is it cache invalidation or TLB invalidation? Can you please
elaborate. I am really sorry if I am asking a silly question.

>
> --
> error compiling committee.c: too many arguments to function
>
>

Re: Page Eviction Algorithm

[Prasad Joshi]

>>>
>>> Can you please suggest me something that would add value to KVM?
>>>
>>
>> O(1) write protection (on the TODO page) is interesting and important.  It's
>> difficult, so you may want to start with O(1) invalidation.
>
> I am not sure if I can understand what exactly is a MMU invalidation.
> Is it cache invalidation or TLB invalidation? Can you please
> elaborate. I am really sorry if I am asking a silly question.

Does this MMU invalidation has to do something with the EPT (Extended
Page Table) and instruction INVEPT?

Please clarify.

>

Re: Page Eviction Algorithm

[Avi Kivity]

  On 10/26/2010 03:31 PM, Prasad Joshi wrote:
> On Tue, Oct 26, 2010 at 2:07 PM, Avi Kivity<avi@redhat.com>  wrote:
> >    On 10/26/2010 12:42 PM, Prasad Joshi wrote:
> >>
> >>  Thanks a lot for your reply.
> >>
> >>  On Tue, Oct 26, 2010 at 11:31 AM, Avi Kivity<avi@redhat.com>    wrote:
> >>  >      On 10/26/2010 11:19 AM, Prasad Joshi wrote:
> >>  >>
> >>  >>    Hi All,
> >>  >>
> >>  >>    I was just going over TODO list on KVM page. In MMU related TODO I saw
> >>  >>    only page eviction algorithm currently implemented is FIFO.
> >>  >>
> >>  >>    Is it really the case?
> >>  >
> >>  >    Yes.
> >>  >
> >>  >>    If yes I would like to work on it. Can someone
> >>  >>    let me know the place where the FIFO code is implemented?
> >>  >
> >>  >    Look at the code that touches mmu_active_list.
> >>  >
> >>  >    FWIW improving the algorithm is not critically important.  It's rare
> >>  >  that
> >>  >    mmu shadow pages need to be evicted.
> >>
> >>  I would be doing a University project on Virtualization. I would like
> >>  to work on Linux kernel and KVM. I was looking over the TODO list on
> >>  KVM wiki.
> >>
> >>  Can you please suggest me something that would add value to KVM?
> >>
> >
> >  O(1) write protection (on the TODO page) is interesting and important.  It's
> >  difficult, so you may want to start with O(1) invalidation.
>
> I am not sure if I can understand what exactly is a MMU invalidation.
> Is it cache invalidation or TLB invalidation? Can you please
> elaborate. I am really sorry if I am asking a silly question.

Invalidation of all shadow page tables.  The current code which does 
this is in kvm_mmu_zap_all().

-- 
error compiling committee.c: too many arguments to function

Re: Page Eviction Algorithm

[Avi Kivity]

  On 10/26/2010 05:08 PM, Prasad Joshi wrote:
> >>>
> >>>  Can you please suggest me something that would add value to KVM?
> >>>
> >>
> >>  O(1) write protection (on the TODO page) is interesting and important.  It's
> >>  difficult, so you may want to start with O(1) invalidation.
> >
> >  I am not sure if I can understand what exactly is a MMU invalidation.
> >  Is it cache invalidation or TLB invalidation? Can you please
> >  elaborate. I am really sorry if I am asking a silly question.
>
> Does this MMU invalidation has to do something with the EPT (Extended
> Page Table)

No

> and instruction INVEPT?

No, (though INVEPT has to be run as part of this operation, via 
kvm_flush_remote_tlbs).

-- 
error compiling committee.c: too many arguments to function

Re: Page Eviction Algorithm

[Prasad Joshi]

On Thu, Oct 28, 2010 at 1:45 AM, Avi Kivity <avi@redhat.com> wrote:
>> Does this MMU invalidation has to do something with the EPT (Extended
>> Page Table)
>
> No
>
>> and instruction INVEPT?
>
> No, (though INVEPT has to be run as part of this operation, via
> kvm_flush_remote_tlbs).

Thanks a lot Avi for your help. I would look at the code and do my
study. I would ask clarification whenever I need help.

>
> --