KSM Algorithm

KSM Algorithm

[Sukanto Ghosh]

Can anyone answer these queries regarding KSM ?

How does KSM offers its services through the  /dev/ksm device ?

Are every guest pages scanned in KVM while using KSM or page-scanning
and sharing is triggered on some event (low memory, etc) ?

Is sharing done only between the pages which have been registered via
KSM_REGISTER_MEMORY_REGION ?

What are these for ? KSM_CREATE_SHARED_MEMORY_AREA and KSM_CREATE_SCAN ?

Where are the shared pages kept ? In kernel memory ? Aren't the shared
pages always pinned in RAM (due to same reasons for pinned shadowed
pages) ?

How much is the overhead involved due to this ?

--
Regards,
Sukanto Ghosh

Re: KSM Algorithm

[Izik Eidus]

ציטוט Sukanto Ghosh:
> Can anyone answer these queries regarding KSM ?
>
> How does KSM offers its services through the  /dev/ksm device ?
>   
ioctls

> Are every guest pages scanned in KVM while using KSM or page-scanning
> and sharing is triggered on some event (low memory, etc) ?
>   
no, the scanning run all the time (with number pages to scan and sleep 
parameters...)

> Is sharing done only between the pages which have been registered via
> KSM_REGISTER_MEMORY_REGION ?
>   
yes

> What are these for ? KSM_CREATE_SHARED_MEMORY_AREA and KSM_CREATE_SCAN ?
>   

KSM_CREATE_SHARED_MEMORY_AREA - to register memory area to be scanned for identical pages
KSM_CREATE_SCAN - to create the scanner that scan for this pages

> Where are the shared pages kept ? In kernel memory ? Aren't the shared
> pages always pinned in RAM (due to same reasons for pinned shadowed
> pages) ?
>   

in the version that was sent to the list it was kernel memory (meaning 
shared pages are not swappable
(just the pages that are shared not the pages that we scan, when they 
are split beacuse of copy on write it become swappable again
new version that i will send soon the pages are normal 
anonymous/userspace memory that is swappable

> How much is the overhead involved due to this ?
>   
depeand on the speed you tell it to scan, but the overhead is about ~5% 
for common cases

> --
> Regards,
> Sukanto Ghosh
> --
> To unsubscribe from this list: send the line "unsubscribe kvm" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>   

Re: KSM Algorithm

[Sukanto Ghosh]

>> Are every guest pages scanned in KVM while using KSM or page-scanning
>> and sharing is triggered on some event (low memory, etc) ?
>>
>
> no, the scanning run all the time (with number pages to scan and sleep
> parameters...)

Does the scanner(s) run as separate kernel threads ?


>> Is sharing done only between the pages which have been registered via
>> KSM_REGISTER_MEMORY_REGION ?
>>
>
> yes
>
>> What are these for ? KSM_CREATE_SHARED_MEMORY_AREA and KSM_CREATE_SCAN ?
>>
>
> KSM_CREATE_SHARED_MEMORY_AREA - to register memory area to be scanned for
> identical pages
> KSM_CREATE_SCAN - to create the scanner that scan for this pages


So kvm will create a scanner using KSM_CREATE_SCAN ioctl to /dev/ksm.
kvm sets its parameters which specify the frequency of scan operation.
Then, it tries to determine periodically from the shadow page tables
about the guest memory region, and registers them with the /dev/ksm.
The scanner as configured will scan the registered areas and will
create COW shared pages for identical pages.
Am I right ?

Doesn't KSM notifies KVM about the shared pages so that KVM can update
its sptes accordingly or is it done by KSM itself ?

What about KSM being used by someone other than KVM ? Does KSM updates
the ptes of the shared pages itself ?


>> Where are the shared pages kept ? In kernel memory ? Aren't the shared
>> pages always pinned in RAM (due to same reasons for pinned shadowed
>> pages) ?
>>
>
> in the version that was sent to the list it was kernel memory (meaning
> shared pages are not swappable
> (just the pages that are shared not the pages that we scan, when they are
> split beacuse of copy on write it become swappable again
> new version that i will send soon the pages are normal anonymous/userspace
> memory that is swappable
>

What is the strategy/method which you will use to represent the shared
memory as normal anonymous/userspace memory ? Then, these pages must
be staying at one of the guest's address-space (whose pages have been
shared) ?


>> How much is the overhead involved due to this ?
>>
>
> depeand on the speed you tell it to scan, but the overhead is about ~5% for
> common cases

Can I know the typical values of the parameters : sleep time, no. of
pages to scan, which you used to arrive at the above mentioned
overhead.


-- 
Regards,
Sukanto Ghosh

Re: KSM Algorithm

[Izik Eidus]

ציטוט Sukanto Ghosh:
>>> Are every guest pages scanned in KVM while using KSM or page-scanning
>>> and sharing is triggered on some event (low memory, etc) ?
>>>
>>>       
>> no, the scanning run all the time (with number pages to scan and sleep
>> parameters...)
>>     
>
> Does the scanner(s) run as separate kernel threads ?\
>   
it can run as kernel thread / or by ioctl runing from userspace
>
>   
>>> Is sharing done only between the pages which have been registered via
>>> KSM_REGISTER_MEMORY_REGION ?
>>>
>>>       
>> yes
>>
>>     
>>> What are these for ? KSM_CREATE_SHARED_MEMORY_AREA and KSM_CREATE_SCAN ?
>>>
>>>       
>> KSM_CREATE_SHARED_MEMORY_AREA - to register memory area to be scanned for
>> identical pages
>> KSM_CREATE_SCAN - to create the scanner that scan for this pages
>>     
>
>
> So kvm will create a scanner using KSM_CREATE_SCAN ioctl to /dev/ksm.
> kvm sets its parameters which specify the frequency of scan operation.
> Then, it tries to determine periodically from the shadow page tables
> about the guest memory region, and registers them with the /dev/ksm.
> The scanner as configured will scan the registered areas and will
> create COW shared pages for identical pages.
> Am I right ?
>   

yea

> Doesn't KSM notifies KVM about the shared pages so that KVM can update
> its sptes accordingly or is it done by KSM itself ?
>   

when using kvm, mmu notifiers is a must for ksm, (mmu notifiers update 
kvm about the changes in the host page table)

> What about KSM being used by someone other than KVM ? Does KSM updates
> the ptes of the shared pages itself ?
>   

it can be used by any application, it update the ptes of the host, what 
you mean by the shared pages itself?

>
>   
>>> Where are the shared pages kept ? In kernel memory ? Aren't the shared
>>> pages always pinned in RAM (due to same reasons for pinned shadowed
>>> pages) ?
>>>
>>>       
>> in the version that was sent to the list it was kernel memory (meaning
>> shared pages are not swappable
>> (just the pages that are shared not the pages that we scan, when they are
>> split beacuse of copy on write it become swappable again
>> new version that i will send soon the pages are normal anonymous/userspace
>> memory that is swappable
>>
>>     
>
> What is the strategy/method which you will use to represent the shared
> memory as normal anonymous/userspace memory ? Then, these pages must
> be staying at one of the guest's address-space (whose pages have been
>   
> shared) ?
>   


it possible due to another patch that i need to send, that allow modules 
register new reverse mapping call backs...,

>
>   
>>> How much is the overhead involved due to this ?
>>>
>>>       
>> depeand on the speed you tell it to scan, but the overhead is about ~5% for
>> common cases
>>     
>
> Can I know the typical values of the parameters : sleep time, no. of
> pages to scan, which you used to arrive at the above mentioned
> overhead.
>   

i think it is about 256 2000 (256 pages per 2000 usleep)
(note that most of the cpu is acutlay taken by the copying of the pages 
when a new shared page is created, i have possible way to change it and 
reduce the cpu even more
but i dont know if i want to do it) (it add more IFs to the fast path 
inside the mm)


>
>   

Re: KSM Algorithm

[Sukanto Ghosh]

>> Doesn't KSM notifies KVM about the shared pages so that KVM can update
>> its sptes accordingly or is it done by KSM itself ?
>>
>
> when using kvm, mmu notifiers is a must for ksm, (mmu notifiers update kvm
> about the changes in the host page table)
>
>> What about KSM being used by someone other than KVM ? Does KSM updates
>> the ptes of the shared pages itself ?
>>
>
> it can be used by any application, it update the ptes of the host, what you
> mean by the shared pages itself?

by "itself" I meant 'ksm'. So ksm will take care of updating the ptes
of the shared guest pages.


>
>>
>>
>>>>
>>>> Where are the shared pages kept ? In kernel memory ? Aren't the shared
>>>> pages always pinned in RAM (due to same reasons for pinned shadowed
>>>> pages) ?
>>>>
>>>>
>>>
>>> in the version that was sent to the list it was kernel memory (meaning
>>> shared pages are not swappable
>>> (just the pages that are shared not the pages that we scan, when they are
>>> split beacuse of copy on write it become swappable again
>>> new version that i will send soon the pages are normal
>>> anonymous/userspace
>>> memory that is swappable
>>>
>>>
>>
>> What is the strategy/method which you will use to represent the shared
>> memory as normal anonymous/userspace memory ? Then, these pages must
>> be staying at one of the guest's address-space (whose pages have been
>>  shared) ?
>>
>
>
> it possible due to another patch that i need to send, that allow modules
> register new reverse mapping call backs...,
>
ok

but in whose address-space will these shared pages stay ?


>>
>>
>>>>
>>>> How much is the overhead involved due to this ?
>>>>
>>>>
>>>
>>> depeand on the speed you tell it to scan, but the overhead is about ~5%
>>> for
>>> common cases
>>>
>>
>> Can I know the typical values of the parameters : sleep time, no. of
>> pages to scan, which you used to arrive at the above mentioned
>> overhead.
>>
>
> i think it is about 256 2000 (256 pages per 2000 usleep)
> (note that most of the cpu is acutlay taken by the copying of the pages when
> a new shared page is created, i have possible way to change it and reduce
> the cpu even more
> but i dont know if i want to do it) (it add more IFs to the fast path inside
> the mm)
>
>
>>
>>
>
>

Thanks :)

-- 
Regards,
Sukanto Ghosh

Re: KSM Algorithm

[Sukanto Ghosh]

got it. thanks

On Fri, Jul 11, 2008 at 12:50 AM, Izik Eidus <izik@qumranet.com> wrote:
> ציטוט Sukanto Ghosh:
>>>>
>>>> Doesn't KSM notifies KVM about the shared pages so that KVM can update
>>>> its sptes accordingly or is it done by KSM itself ?
>>>>
>>>>
>>>
>>> when using kvm, mmu notifiers is a must for ksm, (mmu notifiers update
>>> kvm
>>> about the changes in the host page table)
>>>
>>>
>>>>
>>>> What about KSM being used by someone other than KVM ? Does KSM updates
>>>> the ptes of the shared pages itself ?
>>>>
>>>>
>>>
>>> it can be used by any application, it update the ptes of the host, what
>>> you
>>> mean by the shared pages itself?
>>>
>>
>> by "itself" I meant 'ksm'. So ksm will take care of updating the ptes
>> of the shared guest pages.
>>
>
> yes
>
>>
>>
>>>>
>>>>
>>>>>>
>>>>>> Where are the shared pages kept ? In kernel memory ? Aren't the shared
>>>>>> pages always pinned in RAM (due to same reasons for pinned shadowed
>>>>>> pages) ?
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>> in the version that was sent to the list it was kernel memory (meaning
>>>>> shared pages are not swappable
>>>>> (just the pages that are shared not the pages that we scan, when they
>>>>> are
>>>>> split beacuse of copy on write it become swappable again
>>>>> new version that i will send soon the pages are normal
>>>>> anonymous/userspace
>>>>> memory that is swappable
>>>>>
>>>>>
>>>>>
>>>>
>>>> What is the strategy/method which you will use to represent the shared
>>>> memory as normal anonymous/userspace memory ? Then, these pages must
>>>> be staying at one of the guest's address-space (whose pages have been
>>>>  shared) ?
>>>>
>>>>
>>>
>>> it possible due to another patch that i need to send, that allow modules
>>> register new reverse mapping call backs...,
>>>
>>>
>>
>> ok
>>
>> but in whose address-space will these shared pages stay ?
>>
>>
>
> if we have 5 applications sharing the same page, we will have the page stay
> in 5 diffrent address-spaces...
>
>>
>>>>
>>>>
>>>>>>
>>>>>> How much is the overhead involved due to this ?
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>> depeand on the speed you tell it to scan, but the overhead is about ~5%
>>>>> for
>>>>> common cases
>>>>>
>>>>>
>>>>
>>>> Can I know the typical values of the parameters : sleep time, no. of
>>>> pages to scan, which you used to arrive at the above mentioned
>>>> overhead.
>>>>
>>>>
>>>
>>> i think it is about 256 2000 (256 pages per 2000 usleep)
>>> (note that most of the cpu is acutlay taken by the copying of the pages
>>> when
>>> a new shared page is created, i have possible way to change it and reduce
>>> the cpu even more
>>> but i dont know if i want to do it) (it add more IFs to the fast path
>>> inside
>>> the mm)
>>>
>>>
>>>
>>>>
>>>>
>>>
>>>
>>
>> Thanks :)
>>
>>
>
>



-- 
Regards,
Sukanto Ghosh

Re: KSM Algorithm

[Sukanto Ghosh]

One more query, what if multiple processes call ioctl KSM_CREATE_SCAN
? Will there be multiple scanners ?

Consider a scenario where two processes A & B separately call
KSM_CREATE_SCAN and then start registering some memory pages/areas via
KSM_CREATE_SHARED_MEMORY_AREA ioctl.
Lets say A registers 4 pages having content X, Y, Z and X . And,
process B registers 2 pages having content Z and X.
So, will there be only single copy each of X, Y and Z in the entire
system or will they be kept separately i.e the scanner for A maintains
X, Y, Z single copy each and scanner for B maintains X and Z
separately.


-- 
Regards,
Sukanto Ghosh

Re: KSM Algorithm

[Izik Eidus]

ציטוט Sukanto Ghosh:
> One more query, what if multiple processes call ioctl KSM_CREATE_SCAN
> ? Will there be multiple scanners ?
>   
yes

> Consider a scenario where two processes A & B separately call
> KSM_CREATE_SCAN and then start registering some memory pages/areas via
> KSM_CREATE_SHARED_MEMORY_AREA ioctl.
> Lets say A registers 4 pages having content X, Y, Z and X . And,
> process B registers 2 pages having content Z and X.
> So, will there be only single copy each of X, Y and Z in the entire
> system or will they be kept separately i.e the scanner for A maintains
> X, Y, Z single copy each and scanner for B maintains X and Z
> separately.
>   
there will be only one copy,
ksm is multi threaded safe.

>
>   

Re: KSM Algorithm

[Izik Eidus]

ציטוט Sukanto Ghosh:
>>> Doesn't KSM notifies KVM about the shared pages so that KVM can update
>>> its sptes accordingly or is it done by KSM itself ?
>>>
>>>       
>> when using kvm, mmu notifiers is a must for ksm, (mmu notifiers update kvm
>> about the changes in the host page table)
>>
>>     
>>> What about KSM being used by someone other than KVM ? Does KSM updates
>>> the ptes of the shared pages itself ?
>>>
>>>       
>> it can be used by any application, it update the ptes of the host, what you
>> mean by the shared pages itself?
>>     
>
> by "itself" I meant 'ksm'. So ksm will take care of updating the ptes
> of the shared guest pages.
>   

yes

>
>   
>>>       
>>>>> Where are the shared pages kept ? In kernel memory ? Aren't the shared
>>>>> pages always pinned in RAM (due to same reasons for pinned shadowed
>>>>> pages) ?
>>>>>
>>>>>
>>>>>           
>>>> in the version that was sent to the list it was kernel memory (meaning
>>>> shared pages are not swappable
>>>> (just the pages that are shared not the pages that we scan, when they are
>>>> split beacuse of copy on write it become swappable again
>>>> new version that i will send soon the pages are normal
>>>> anonymous/userspace
>>>> memory that is swappable
>>>>
>>>>
>>>>         
>>> What is the strategy/method which you will use to represent the shared
>>> memory as normal anonymous/userspace memory ? Then, these pages must
>>> be staying at one of the guest's address-space (whose pages have been
>>>  shared) ?
>>>
>>>       
>> it possible due to another patch that i need to send, that allow modules
>> register new reverse mapping call backs...,
>>
>>     
> ok
>
> but in whose address-space will these shared pages stay ?
>
>   

if we have 5 applications sharing the same page, we will have the page 
stay in 5 diffrent address-spaces...

>   
>>>       
>>>>> How much is the overhead involved due to this ?
>>>>>
>>>>>
>>>>>           
>>>> depeand on the speed you tell it to scan, but the overhead is about ~5%
>>>> for
>>>> common cases
>>>>
>>>>         
>>> Can I know the typical values of the parameters : sleep time, no. of
>>> pages to scan, which you used to arrive at the above mentioned
>>> overhead.
>>>
>>>       
>> i think it is about 256 2000 (256 pages per 2000 usleep)
>> (note that most of the cpu is acutlay taken by the copying of the pages when
>> a new shared page is created, i have possible way to change it and reduce
>> the cpu even more
>> but i dont know if i want to do it) (it add more IFs to the fast path inside
>> the mm)
>>
>>
>>     
>>>       
>>     
>
> Thanks :)
>
>   

Re: KSM Algorithm

[Sukanto Ghosh]

Going through your slide "increasing the virtual machine density with
ksm" I got an idea about how KSM works internally.

1. Scan registered memory area
2. During scan of every page P, generate
    hashval = hashfn(content of P)
3. The hashval is used as an index into the hashtable, the pfn of P is
added to the list at hashtable[hashval]
4. if there are other pfns in the list, do full comparison of  both
the newly added page P and the prev page (say Q)
5. if both are same merge them

what if they are not same ?
will the pfn of P still remain in the list of hashtable[hashval] ?

say the list at hashtable[hashval] is like -> Q1 -> Q2 -> Q3
where Qn is the pfn of the pages having hash-value =  'hashval' ,
while comparing with the contents of a new page P, which of these Qn's
will be used ? (I think the ans to prev ques will answer this)


-- 
Thanks and Regards,
Sukanto Ghosh