From patchwork Mon Sep 25 22:16:47 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Timofey Titovets X-Patchwork-Id: 9970517 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id CC767602CB for ; Mon, 25 Sep 2017 22:17:09 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id BF43F28886 for ; Mon, 25 Sep 2017 22:17:09 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id B2BBF28DC4; Mon, 25 Sep 2017 22:17:09 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6169728886 for ; Mon, 25 Sep 2017 22:17:09 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S935804AbdIYWQ6 (ORCPT ); Mon, 25 Sep 2017 18:16:58 -0400 Received: from mail-wr0-f194.google.com ([209.85.128.194]:34783 "EHLO mail-wr0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S935505AbdIYWQ5 (ORCPT ); Mon, 25 Sep 2017 18:16:57 -0400 Received: by mail-wr0-f194.google.com with SMTP id k20so806117wre.1; Mon, 25 Sep 2017 15:16:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id; bh=FqpLWBypnrlvs59Gf0hthQJENTKwazgUNmXr9lLwh54=; b=q47Z1IExc7jeo+bXquKQHg9XuL76csDp7Mt+wwZS5KsWEghiBYrOwJ0QL2BN6qRlL5 BgZEIQK84IpP23qUquFnT4GvunCrx8ZarkfGlm/nqiTIc1BzWM+FzNgJUbGLcNebUjhO AXPiYvzm+nws4duQDh6+7kv0l4snW+m7z8g9AV4PZmCeTiu1T8C5GdjLAdMlsV/F+bIv Xulmqpo1FdGXntKNc2hFR6mVoRu2uPLfCihEYBCez/lJFlYf+ERGSS5sL9dBszGyWI/i kokSlr81pF85YEdNNUPTlR2wEHfl1l0R7TNPdpQ4R1ReDaXBP2AvZYO6c5JsOJGkNmfw KN7Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=FqpLWBypnrlvs59Gf0hthQJENTKwazgUNmXr9lLwh54=; b=V4+bQ1FFgFgHY9KCGe1P1+XGM9aDT8wvr//lQHMb/rIRywMniYmNNN9A9MynDXnu8D OoTvG3GIVjX19CpxO06WwT7fnz28c0RGB9nZXtFP78a8XVOfMidMjQFc1FywjNE6Yne8 v/RmSxRtGLDjpylQkCzRvlBorzSq/7cYLiHc1PWHeInvqySUgEPxevQZxL7ZfkCe2e7i ZVyVYL/2XBswD4vgkb7Wf0AqQCuztsuC8nJIjApcyw7IT+5+AsRobhXy2q84L/vJ2cQe MG/AzSmuubxUzAfC/0euuP1wGAAWgOlF6IKYVpKCxlDKxFeJKwOfU9hCs4aCKLKk2WwC BbjA== X-Gm-Message-State: AHPjjUgtSs2320erQrj94gtdubsFGw75j40C5NPuh0LNJZ6sgmkSJFzH rAO/tbxaWBAmI9RWqKrhPMg= X-Google-Smtp-Source: AOwi7QBMqh6jDY1tJFC7dsKFV0TaKy2HkTXSxvGCrXwzdtS1g+FkGK0wjsaJtw16vM13kQh6g0zR2A== X-Received: by 10.25.211.205 with SMTP id k196mr2549783lfg.210.1506377816192; Mon, 25 Sep 2017 15:16:56 -0700 (PDT) Received: from titovetst-l.lan (nat5-minsk-pool-46-53-216-190.telecom.by. [46.53.216.190]) by smtp.gmail.com with ESMTPSA id x25sm1618374lja.5.2017.09.25.15.16.55 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 25 Sep 2017 15:16:55 -0700 (PDT) From: Timofey Titovets To: linux-mm@kvack.org Cc: linux-kernel@vger.kernel.org, kvm@vger.kernel.org, Timofey Titovets Subject: [RFC PATCH] ksm: add offset arg to memcmp_pages() to speedup comparing Date: Tue, 26 Sep 2017 01:16:47 +0300 Message-Id: <20170925221647.4284-1-nefelim4ag@gmail.com> X-Mailer: git-send-email 2.14.1 Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Currently while search/inserting in RB tree, memcmp used for comparing out of tree pages with in tree pages. But on each step of search memcmp used to compare pages from zero offset, i.e. each time we just ignore forward byte progress. That make some overhead for search in deep RB tree, so store last start offset where no diff in page content. offset aligned to 1024, that a some type of magic value For that value i get ~ same performance in bad case (where offset useless) for memcmp_pages() with offset and without. Signed-off-by: Timofey Titovets --- mm/ksm.c | 32 +++++++++++++++++++++++++------- 1 file changed, 25 insertions(+), 7 deletions(-) -- 2.14.1 diff --git a/mm/ksm.c b/mm/ksm.c index 15dd7415f7b3..63f8b4f0824c 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -991,14 +991,27 @@ static u32 calc_checksum(struct page *page) return checksum; } -static int memcmp_pages(struct page *page1, struct page *page2) +static int memcmp_pages(struct page *page1, struct page *page2, u32 *offset) { + const u32 iter = 1024; char *addr1, *addr2; - int ret; + u32 i = 0; + int ret = 0; + + BUILD_BUG_ON(!IS_ALIGNED(PAGE_SIZE, iter)); addr1 = kmap_atomic(page1); addr2 = kmap_atomic(page2); - ret = memcmp(addr1, addr2, PAGE_SIZE); + if (offset == NULL) { + ret = memcmp(addr1, addr2, PAGE_SIZE); + } else { + if (*offset < PAGE_SIZE) + i = *offset; + for (; i < PAGE_SIZE && ret == 0; i += iter) { + ret = memcmp(&addr1[i], &addr2[i], iter); + } + *offset = i; + } kunmap_atomic(addr2); kunmap_atomic(addr1); return ret; @@ -1006,7 +1019,7 @@ static int memcmp_pages(struct page *page1, struct page *page2) static inline int pages_identical(struct page *page1, struct page *page2) { - return !memcmp_pages(page1, page2); + return !memcmp_pages(page1, page2, NULL); } static int write_protect_page(struct vm_area_struct *vma, struct page *page, @@ -1514,6 +1527,7 @@ static __always_inline struct page *chain(struct stable_node **s_n_d, static struct page *stable_tree_search(struct page *page) { int nid; + u32 diff_offset; struct rb_root *root; struct rb_node **new; struct rb_node *parent; @@ -1532,6 +1546,7 @@ static struct page *stable_tree_search(struct page *page) again: new = &root->rb_node; parent = NULL; + diff_offset = 0; while (*new) { struct page *tree_page; @@ -1590,7 +1605,7 @@ static struct page *stable_tree_search(struct page *page) goto again; } - ret = memcmp_pages(page, tree_page); + ret = memcmp_pages(page, tree_page, &diff_offset); put_page(tree_page); parent = *new; @@ -1760,6 +1775,7 @@ static struct page *stable_tree_search(struct page *page) static struct stable_node *stable_tree_insert(struct page *kpage) { int nid; + u32 diff_offset; unsigned long kpfn; struct rb_root *root; struct rb_node **new; @@ -1773,6 +1789,7 @@ static struct stable_node *stable_tree_insert(struct page *kpage) again: parent = NULL; new = &root->rb_node; + diff_offset = 0; while (*new) { struct page *tree_page; @@ -1819,7 +1836,7 @@ static struct stable_node *stable_tree_insert(struct page *kpage) goto again; } - ret = memcmp_pages(kpage, tree_page); + ret = memcmp_pages(kpage, tree_page, &diff_offset); put_page(tree_page); parent = *new; @@ -1884,6 +1901,7 @@ struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item, struct rb_root *root; struct rb_node *parent = NULL; int nid; + u32 diff_offset = 0; nid = get_kpfn_nid(page_to_pfn(page)); root = root_unstable_tree + nid; @@ -1908,7 +1926,7 @@ struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item, return NULL; } - ret = memcmp_pages(page, tree_page); + ret = memcmp_pages(page, tree_page, &diff_offset); parent = *new; if (ret < 0) {