On Fri, Aug 26, 2011 at 5:09 PM, Marcelo Tosatti <mtosatti@xxxxxxxxxx> wrote:
> On Thu, Aug 25, 2011 at 12:03:47PM +0530, Prateek Sharma wrote:
>> Hello everyone .
>> I've been trying to understand how KSM works (i want to make some
>> modifications / implement some optimizations) .
>> One thing that struck me odd was the high number of calls to
>> remove_rmap_item_from_tree .
>> Particularly, this instance in cmp_and_merge_page :
>>
>> /*
>> * As soon as we merge this page, we want to remove the
>> * rmap_item of the page we have merged with from the unstable
>> * tree, and insert it instead as new node in the stable tree.
>> */
>> if (kpage) {
>> remove_rmap_item_from_tree(tree_rmap_item);
>>
>> lock_page(kpage);
>> stable_node = stable_tree_insert(kpage);
>> if (stable_node) {
>> stable_tree_append(tree_rmap_item, stable_node);
>> stable_tree_append(rmap_item, stable_node);
>> }
>>
>> Here, from i understand, we've found a match in the unstable tree, and
>> are adding a stable node in the stable tree.
>> My question is: why do we need to remove the rmap_item from unstable
>> tree here? At the end of a scan we are erasing the unstable tree
>> anyway.
>
> It does not make sense for the item to be in the unstable tree anymore:
> it now represents two write protected pages, so should reside in the
> stable tree.
>
>> Also, all searches first consider the stable tree , and then
>> the unstable tree.
>> What will happen if we find a match in the unstable tree, and simply
>> update tree_rmap_item to point to a stable_node ?
>
> I suppose its simpler to remove from unstable and add to stable tree.
>
Thank you for responding!
I can thus assume that keeping rmap_items in both the stable and
unstable trees wont damage the correctness of the program?
Speaking of trees , i am wondering why KSM uses trees for pages,
instead of hashtables? Log(n) operations for everything seems to be
pretty expensive. (KSM uses around 10% CPU on my machines ).
>>
>> Thanks for reading. I'd love to share the ideas i have for (attempting
>> to) improve KSM, if anyone is interested.
>>
>> Prateek
>
--
To unsubscribe from this list: send the line "unsubscribe kvm" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
