From: "Figo.zhang" <figo1802@gmail.com>
To: Timofey Titovets <nefelim4ag@gmail.com>
Cc: "Kyeongdon Kim" <kyeongdon.kim@lge.com>,
"Andrew Morton" <akpm@linux-foundation.org>,
"Andrea Arcangeli" <aarcange@redhat.com>,
"Minchan Kim" <minchan@kernel.org>,
broonie@kernel.org, "Michal Hocko" <mhocko@suse.com>,
"Ingo Molnar" <mingo@kernel.org>,
"Jérôme Glisse" <jglisse@redhat.com>,
"Arvind Yadav" <arvind.yadav.cs@gmail.com>,
imbrenda@linux.vnet.ibm.com, kirill.shutemov@linux.intel.com,
bongkyu.kim@lge.com, "Linux MM" <linux-mm@kvack.org>,
"Linux Kernel" <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v2] ksm : use checksum and memcmp for rb_tree
Date: Thu, 16 Nov 2017 08:44:18 +0800 [thread overview]
Message-ID: <CAF7GXvrw3EV_GG5Nr6CC=o1Ei=8a7fHT-WOLzJzPo5t+-wAbVw@mail.gmail.com> (raw)
In-Reply-To: <CAGqmi77HCNiO=5Xc=c4CSHS1OioXX86bHynt560umsPZCu5n2A@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 8790 bytes --]
it seems violate the patent which hold by vmware, the patent is: US
6789156B1
the majority assertion of this patent is that compare the content of
2 pages with HASH/Checksum algorithm in operation system.
2017-11-16 5:25 GMT+08:00 Timofey Titovets <nefelim4ag@gmail.com>:
> Reviewed-by: Timofey Titovets <nefelim4ag@gmail.com>
>
> 2017-11-15 6:19 GMT+03:00 Kyeongdon Kim <kyeongdon.kim@lge.com>:
> > The current ksm is using memcmp to insert and search 'rb_tree'.
> > It does cause very expensive computation cost.
> > In order to reduce the time of this operation,
> > we have added a checksum to traverse.
> >
> > Nearly all 'rb_node' in stable_tree_insert() function
> > can be inserted as a checksum, most of it is possible
> > in unstable_tree_search_insert() function.
> > In stable_tree_search() function, the checksum may be an additional.
> > But, checksum check duration is extremely small.
> > Considering the time of the whole cmp_and_merge_page() function,
> > it requires very little cost on average.
> >
> > Using this patch, we compared the time of ksm_do_scan() function
> > by adding kernel trace at the start-end position of operation.
> > (ARM 32bit target android device,
> > over 1000 sample time gap stamps average)
> >
> > On original KSM scan avg duration = 0.0166893 sec
> > 14991.975619 : ksm_do_scan_start: START: ksm_do_scan
> > 14991.990975 : ksm_do_scan_end: END: ksm_do_scan
> > 14992.008989 : ksm_do_scan_start: START: ksm_do_scan
> > 14992.016839 : ksm_do_scan_end: END: ksm_do_scan
> > ...
> >
> > On patch KSM scan avg duration = 0.0041157 sec
> > 41081.46131 : ksm_do_scan_start : START: ksm_do_scan
> > 41081.46636 : ksm_do_scan_end : END: ksm_do_scan
> > 41081.48476 : ksm_do_scan_start : START: ksm_do_scan
> > 41081.48795 : ksm_do_scan_end : END: ksm_do_scan
> > ...
> >
> > We have tested randomly so many times for the stability
> > and couldn't see any abnormal issue until now.
> > Also, we found out this patch can make some good advantage
> > for the power consumption than KSM default enable.
> >
> > v1 -> v2
> > - add comment for oldchecksum value
> > - move the oldchecksum value out of union
> > - remove check code regarding checksum 0 in stable_tree_search()
> >
> > link to v1 : https://lkml.org/lkml/2017/10/30/251
> >
> > Signed-off-by: Kyeongdon Kim <kyeongdon.kim@lge.com>
> > ---
> > mm/ksm.c | 48 ++++++++++++++++++++++++++++++++++++++++++++----
> > 1 file changed, 44 insertions(+), 4 deletions(-)
> >
> > diff --git a/mm/ksm.c b/mm/ksm.c
> > index be8f457..9280569 100644
> > --- a/mm/ksm.c
> > +++ b/mm/ksm.c
> > @@ -134,6 +134,7 @@ struct ksm_scan {
> > * @kpfn: page frame number of this ksm page (perhaps temporarily on
> wrong nid)
> > * @chain_prune_time: time of the last full garbage collection
> > * @rmap_hlist_len: number of rmap_item entries in hlist or
> STABLE_NODE_CHAIN
> > + * @oldchecksum: previous checksum of the page about a stable_node
> > * @nid: NUMA node id of stable tree in which linked (may not match
> kpfn)
> > */
> > struct stable_node {
> > @@ -159,6 +160,7 @@ struct stable_node {
> > */
> > #define STABLE_NODE_CHAIN -1024
> > int rmap_hlist_len;
> > + u32 oldchecksum;
> > #ifdef CONFIG_NUMA
> > int nid;
> > #endif
> > @@ -1522,7 +1524,7 @@ static __always_inline struct page *chain(struct
> stable_node **s_n_d,
> > * This function returns the stable tree node of identical content if
> found,
> > * NULL otherwise.
> > */
> > -static struct page *stable_tree_search(struct page *page)
> > +static struct page *stable_tree_search(struct page *page, u32 checksum)
> > {
> > int nid;
> > struct rb_root *root;
> > @@ -1550,6 +1552,18 @@ static struct page *stable_tree_search(struct
> page *page)
> >
> > cond_resched();
> > stable_node = rb_entry(*new, struct stable_node, node);
> > +
> > + /* first make rb_tree by checksum */
> > + if (checksum < stable_node->oldchecksum) {
> > + parent = *new;
> > + new = &parent->rb_left;
> > + continue;
> > + } else if (checksum > stable_node->oldchecksum) {
> > + parent = *new;
> > + new = &parent->rb_right;
> > + continue;
> > + }
> > +
> > stable_node_any = NULL;
> > tree_page = chain_prune(&stable_node_dup, &stable_node,
> root);
> > /*
> > @@ -1768,7 +1782,7 @@ static struct page *stable_tree_search(struct page
> *page)
> > * This function returns the stable tree node just allocated on success,
> > * NULL otherwise.
> > */
> > -static struct stable_node *stable_tree_insert(struct page *kpage)
> > +static struct stable_node *stable_tree_insert(struct page *kpage, u32
> checksum)
> > {
> > int nid;
> > unsigned long kpfn;
> > @@ -1792,6 +1806,18 @@ static struct stable_node
> *stable_tree_insert(struct page *kpage)
> > cond_resched();
> > stable_node = rb_entry(*new, struct stable_node, node);
> > stable_node_any = NULL;
> > +
> > + /* first make rb_tree by checksum */
> > + if (checksum < stable_node->oldchecksum) {
> > + parent = *new;
> > + new = &parent->rb_left;
> > + continue;
> > + } else if (checksum > stable_node->oldchecksum) {
> > + parent = *new;
> > + new = &parent->rb_right;
> > + continue;
> > + }
> > +
> > tree_page = chain(&stable_node_dup, stable_node, root);
> > if (!stable_node_dup) {
> > /*
> > @@ -1850,6 +1876,7 @@ static struct stable_node
> *stable_tree_insert(struct page *kpage)
> >
> > INIT_HLIST_HEAD(&stable_node_dup->hlist);
> > stable_node_dup->kpfn = kpfn;
> > + stable_node_dup->oldchecksum = checksum;
> > set_page_stable_node(kpage, stable_node_dup);
> > stable_node_dup->rmap_hlist_len = 0;
> > DO_NUMA(stable_node_dup->nid = nid);
> > @@ -1907,6 +1934,19 @@ struct rmap_item *unstable_tree_search_insert(struct
> rmap_item *rmap_item,
> >
> > cond_resched();
> > tree_rmap_item = rb_entry(*new, struct rmap_item, node);
> > +
> > + /* first make rb_tree by checksum */
> > + if (rmap_item->oldchecksum <
> tree_rmap_item->oldchecksum) {
> > + parent = *new;
> > + new = &parent->rb_left;
> > + continue;
> > + } else if (rmap_item->oldchecksum
> > + > tree_rmap_item->oldchecksum) {
> > + parent = *new;
> > + new = &parent->rb_right;
> > + continue;
> > + }
> > +
> > tree_page = get_mergeable_page(tree_rmap_item);
> > if (!tree_page)
> > return NULL;
> > @@ -2031,7 +2071,7 @@ static void cmp_and_merge_page(struct page *page,
> struct rmap_item *rmap_item)
> > }
> >
> > /* We first start with searching the page inside the stable tree
> */
> > - kpage = stable_tree_search(page);
> > + kpage = stable_tree_search(page, rmap_item->oldchecksum);
> > if (kpage == page && rmap_item->head == stable_node) {
> > put_page(kpage);
> > return;
> > @@ -2098,7 +2138,7 @@ static void cmp_and_merge_page(struct page *page,
> struct rmap_item *rmap_item)
> > * node in the stable tree and add both
> rmap_items.
> > */
> > lock_page(kpage);
> > - stable_node = stable_tree_insert(kpage);
> > + stable_node = stable_tree_insert(kpage,
> checksum);
> > if (stable_node) {
> > stable_tree_append(tree_rmap_item,
> stable_node,
> > false);
> > --
> > 2.6.2
> >
> > --
> > To unsubscribe, send a message with 'unsubscribe linux-mm' in
> > the body to majordomo@kvack.org. For more info on Linux MM,
> > see: http://www.linux-mm.org/ .
> > Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>
>
>
> --
> Have a nice day,
> Timofey.
>
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org. For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>
[-- Attachment #2: Type: text/html, Size: 12123 bytes --]
prev parent reply other threads:[~2017-11-16 0:44 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-11-15 3:19 [PATCH v2] ksm : use checksum and memcmp for rb_tree Kyeongdon Kim
2017-11-15 21:25 ` Timofey Titovets
2017-11-16 0:44 ` Figo.zhang [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAF7GXvrw3EV_GG5Nr6CC=o1Ei=8a7fHT-WOLzJzPo5t+-wAbVw@mail.gmail.com' \
--to=figo1802@gmail.com \
--cc=aarcange@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=arvind.yadav.cs@gmail.com \
--cc=bongkyu.kim@lge.com \
--cc=broonie@kernel.org \
--cc=imbrenda@linux.vnet.ibm.com \
--cc=jglisse@redhat.com \
--cc=kirill.shutemov@linux.intel.com \
--cc=kyeongdon.kim@lge.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mhocko@suse.com \
--cc=minchan@kernel.org \
--cc=mingo@kernel.org \
--cc=nefelim4ag@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).