From patchwork Mon Oct 2 12:58:58 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Timofey Titovets X-Patchwork-Id: 9980805 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 A0CE860384 for ; Mon, 2 Oct 2017 12:59:20 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9412D2018E for ; Mon, 2 Oct 2017 12:59:20 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 88E54207A7; Mon, 2 Oct 2017 12:59:20 +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 22B342018E for ; Mon, 2 Oct 2017 12:59:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751104AbdJBM7I (ORCPT ); Mon, 2 Oct 2017 08:59:08 -0400 Received: from mail-wm0-f67.google.com ([74.125.82.67]:50375 "EHLO mail-wm0-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750929AbdJBM7G (ORCPT ); Mon, 2 Oct 2017 08:59:06 -0400 Received: by mail-wm0-f67.google.com with SMTP id u138so10361387wmu.5; Mon, 02 Oct 2017 05:59:05 -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=0X7lPmYhZc0UkosU/tTT+J3M2PbJKhnKZmktpIGgVCQ=; b=dZ8P4XfLGl+Jk2YIYm+Y9fvJgYMqPTa2q1SyiMSa4omEdRN3Go8vuznwZRYSKwuHVM msF2SpyfmdGWn/YagIZEFp2BPsbnMvghKPN0gQf1zvR/G2Pje8ijI9HJocMph8ljuUE2 O5mznY/mRTQz2VU4lAq3nY5gCmsw0YCy++p3E7JRRQuQeu+qQEcBUEO0T0GoSUuiK0JA qlwQ1GSSBNwhrKK/i+c3/T6u/4DlWxSDZYhjAw9oYyPeg+jEhkTKPaE4r7lMpvcj15gH m/oTBG2PzzYT4nAEqLuG11vDwpWqYIlw4umi9JaP2eW0Out9hx/L4pzDeDPGqU08vV5s RrHA== 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=0X7lPmYhZc0UkosU/tTT+J3M2PbJKhnKZmktpIGgVCQ=; b=CLHCqqJlWqMFKPBtgG+6VB35lX+9/rv1BPSQ+xYLN7V0CVSjEF5NwA7vy6mkgmT00m 5Q3nceMndhT4GLodN+xLJHGS2ZIywW6Kmi11QS1bond5X/3EUl14DTNILgjTwWye1s+v kSqgGPXTmDySlyanFLKUrrrcsY7iLpaLY8Ajcgicfh8OmqFKtgmROPIVdrjcrpvCPdbi 8q52RVJIP5hsA4IcSkI+BhQVGiGoImdJa9/vZLMtlx2RIrFFLVOLmvDe9MWtJqvHD9Zq CjMFgmzy2Z5mIcPJguC0GZhjLyWSC45/fPPgd4/vRXYKJ4yR07/hVh8U9fgo/MvkWQY4 BrsQ== X-Gm-Message-State: AMCzsaXN81rtGUtSZAKCJyvbMdTELDA1yjIxWCUeXD5ceHlMeNcasuJp 8FKrisPL2tFed0mz2Q8AIiE= X-Google-Smtp-Source: AOwi7QAAP6nsMUYY4ZgT2Slkn+nM1+GMmI48/gemLyQxdWvrZzJQjbdiFpJH5lKAZt9nO6dLcjA5sw== X-Received: by 10.28.26.140 with SMTP id a134mr11693316wma.90.1506949144969; Mon, 02 Oct 2017 05:59:04 -0700 (PDT) Received: from titovetst-l.itransition.corp ([93.171.6.182]) by smtp.gmail.com with ESMTPSA id i65sm5665916wmg.42.2017.10.02.05.59.03 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 02 Oct 2017 05:59:04 -0700 (PDT) From: Timofey Titovets To: linux-mm@kvack.org Cc: linux-kernel@vger.kernel.org, kvm@vger.kernel.org, Timofey Titovets Subject: [RFC v2 PATCH] ksm: add offset arg to memcmp_pages() to speedup comparing Date: Mon, 2 Oct 2017 15:58:58 +0300 Message-Id: <20171002125858.12751-1-nefelim4ag@gmail.com> X-Mailer: git-send-email 2.14.2 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 compare step memcmp for pages start at zero offset, i.e. that just ignore forward progress. That make some overhead for search in deep RB tree and/or with bit pages (4KiB+), so store last start offset where no diff in page content. Added: memcmpe() iter 1024 - that a some type of magic value max_offset_error - 8 - acceptable error level for offset. With that patch i get ~ same performance in bad case (where offset useless) on tiny tree and default 4KiB pages. So that just RFC, i.e. does that type of optimization make a sense? Thanks. Changes: v1 -> v2: Add: configurable max_offset_error Move logic to memcmpe() Signed-off-by: Timofey Titovets --- mm/ksm.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 55 insertions(+), 6 deletions(-) diff --git a/mm/ksm.c b/mm/ksm.c index 15dd7415f7b3..780630498de8 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -991,14 +991,58 @@ static u32 calc_checksum(struct page *page) return checksum; } -static int memcmp_pages(struct page *page1, struct page *page2) + +/* + * memcmp used to compare pages in RB-tree + * but on every step down the tree forward progress + * just has been ignored, that make performance pitfall + * on deep tree and/or big pages (ex. 4KiB+) + * + * Fix that by add memcmp wrapper that will try to guess + * where difference happens, to only scan from that offset against + * next pages + */ + +static int memcmpe(const void *p, const void *q, const u32 len, + u32 *offset) +{ + const u32 max_offset_error = 8; + u32 iter = 1024, i = 0; + int ret; + + if (offset == NULL) + return memcmp(p, q, len); + + if (*offset < len) + i = *offset; + + while (i < len) { + iter = min_t(u32, iter, len - i); + ret = memcmp(p, q, iter); + + if (ret) { + iter = iter >> 1; + if (iter < max_offset_error) + break; + continue; + } + + i += iter; + } + + *offset = i; + + return ret; +} + +static int memcmp_pages(struct page *page1, struct page *page2, u32 *offset) { char *addr1, *addr2; int ret; addr1 = kmap_atomic(page1); addr2 = kmap_atomic(page2); - ret = memcmp(addr1, addr2, PAGE_SIZE); + ret = memcmpe(addr1, addr2, PAGE_SIZE, offset); kunmap_atomic(addr2); kunmap_atomic(addr1); return ret; @@ -1006,7 +1050,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 +1558,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 +1577,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 +1636,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 +1806,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 +1820,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 +1867,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 +1932,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 +1957,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) {