On Fri, Aug 26, 2011 at 07:45:04PM +0530, Prateek Sharma wrote:
> 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?
No, to the contrary. An item should be in the unstable OR the stable
tree at one given time, not both.
> 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 ).
The hashtable would have to be very large to be efficient. The CPU
consumption you see if more likely caused by KSM comparing pages. You
can verify that with the perf tool.
--
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
