From patchwork Tue Jul 18 12:05:56 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gavin Guo X-Patchwork-Id: 790219 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=lists.ubuntu.com (client-ip=91.189.94.19; helo=huckleberry.canonical.com; envelope-from=kernel-team-bounces@lists.ubuntu.com; receiver=) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=canonical-com.20150623.gappssmtp.com header.i=@canonical-com.20150623.gappssmtp.com header.b="CIyYQTXd"; dkim-atps=neutral Received: from huckleberry.canonical.com (huckleberry.canonical.com [91.189.94.19]) by ozlabs.org (Postfix) with ESMTP id 3xBf6m3sn9z9rxl; Tue, 18 Jul 2017 22:07:28 +1000 (AEST) Received: from localhost ([127.0.0.1] helo=huckleberry.canonical.com) by huckleberry.canonical.com with esmtp (Exim 4.76) (envelope-from ) id 1dXRHh-0004TE-Od; Tue, 18 Jul 2017 12:07:25 +0000 Received: from mail-pf0-f180.google.com ([209.85.192.180]) by huckleberry.canonical.com with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.76) (envelope-from ) id 1dXRGr-0003s3-0j for kernel-team@lists.ubuntu.com; Tue, 18 Jul 2017 12:06:33 +0000 Received: by mail-pf0-f180.google.com with SMTP id o88so4179789pfk.3 for ; Tue, 18 Jul 2017 05:06:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=canonical-com.20150623.gappssmtp.com; s=20150623; h=from:to:subject:date:message-id:in-reply-to:references; bh=rOARIUQzsGB3Qcux2PAYShG4DgTqfBKuMoRB5T1UYKg=; b=CIyYQTXdcuFYb9Is13Py2oO4xzobTIQecbA5kk+6AzKLdwGeG19t8r1iZxccjBCUMp ycXGp8zPVbAQ+gc2hUD6zXzViW1JmSXqvftIZiw3n52gWOoAX5Tz8cz52WHN5RCaxkFX RqIB71XyndQy/Wb9aVuKjHe8hzHNftEimItb7Og4YlNio9PB/h5Uxur6tQRcrK2Md3vO ewIJjv6W2gwclzyI+i22mw5xCzltTTjR1NbXo/dIgQWXDSW/A9qWTJXH7lt2xeQ4uMOv KX/Aok+sQsSQWhNhdvQyjZ7yxpOmLr/lnm0QErUdEdMjhLahGnwiMlwBmmoi6Sfwz94Z Rg4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=rOARIUQzsGB3Qcux2PAYShG4DgTqfBKuMoRB5T1UYKg=; b=LPXiOCOKHyT5TbZ1V42RyE8fBYTObzXtZKqumlayA21rH6vgEBjg9FfiA7BfGZiZUK e1gJfhQihsdQkWBY4XExd2yZL453od5lsSHLitZcWKyGv4zZY3Q2lhzu9ozlKAnXUMOr Xq45onrDImsjaDpmtabR4ORlmCQC9G+cQghrWBMIpTwBVMoYeVLMK3VjllIIFrQVYqza EN6ci8lQNHl5m+o9YX6rFPv98pi23Pni+3dAdWTzBMNivlMmj6lZQxC0tCl0a1KIXuRW nECAKoWTxEBAEumAXmGp4XcAA21qzjaUWt+m8V3zqOi81lB5VArSAY+1EcRelEWCIm4r hQjg== X-Gm-Message-State: AIVw111OAiVczkh8hFQq7Vy4dMN9e6Mr7RTNWybDe7xY8/CMLw9V5MHM aXru9An/L/C6A3C2CBQ= X-Received: by 10.99.228.69 with SMTP id i5mr1350633pgk.192.1500379591289; Tue, 18 Jul 2017 05:06:31 -0700 (PDT) Received: from gavin-P70.buildd (114-35-245-81.HINET-IP.hinet.net. [114.35.245.81]) by smtp.gmail.com with ESMTPSA id k19sm5771047pfk.16.2017.07.18.05.06.29 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 18 Jul 2017 05:06:30 -0700 (PDT) From: Gavin Guo To: kernel-team@lists.ubuntu.com Subject: [SRU][Yakkety][PATCH 5/5] ksm: optimize refile of stable_node_dup at the head of the chain Date: Tue, 18 Jul 2017 20:05:56 +0800 Message-Id: <1500379557-13503-20-git-send-email-gavin.guo@canonical.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1500379557-13503-1-git-send-email-gavin.guo@canonical.com> References: <1500379557-13503-1-git-send-email-gavin.guo@canonical.com> X-BeenThere: kernel-team@lists.ubuntu.com X-Mailman-Version: 2.1.14 Precedence: list List-Id: Kernel team discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: kernel-team-bounces@lists.ubuntu.com Sender: kernel-team-bounces@lists.ubuntu.com From: Andrea Arcangeli BugLink: http://bugs.launchpad.net/bugs/1680513 If a candidate stable_node_dup has been found and it can accept further merges it can be refiled to the head of the list to speedup next searches without altering which dup is found and how the dups accumulate in the chain. We already refiled it back to the head in the prune_stale_stable_nodes case, but we didn't refile it if not pruning (which is more common). And we also refiled it when it was already at the head which is unnecessary (in the prune_stale_stable_nodes case, nr > 1 means there's more than one dup in the chain, it doesn't mean it's not already at the head of the chain). The stable_node_chain list is single threaded and there's no SMP locking contention so it should be faster to refile it to the head of the list also if prune_stale_stable_nodes is false. Profiling shows the refile happens 1.9% of the time when a dup is found with a max_page_sharing limit setting of 3 (with max_page_sharing of 2 the refile never happens of course as there's never space for one more merge) which is reasonably low. At higher max_page_sharing values it should be much less frequent. This is just an optimization. Link: http://lkml.kernel.org/r/20170518173721.22316-4-aarcange@redhat.com Signed-off-by: Andrea Arcangeli Cc: Evgheni Dereveanchin Cc: Andrey Ryabinin Cc: Petr Holasek Cc: Hugh Dickins Cc: Arjan van de Ven Cc: Davidlohr Bueso Cc: Gavin Guo Cc: Jay Vosburgh Cc: Mel Gorman Cc: Dan Carpenter Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds (cherry picked from commit 80b18dfa53bbb03085eba6401f5d29dad49205b7) Signed-off-by: Gavin Guo --- mm/ksm.c | 35 +++++++++++++++++++++++------------ 1 file changed, 23 insertions(+), 12 deletions(-) diff --git a/mm/ksm.c b/mm/ksm.c index 470f28ba040f..4a72634846d3 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -1337,13 +1337,14 @@ struct page *stable_node_dup(struct stable_node **_stable_node_dup, put_page(_tree_page); } - /* - * nr is relevant only if prune_stale_stable_nodes is true, - * otherwise we may break the loop at nr == 1 even if there - * are multiple entries. - */ - if (prune_stale_stable_nodes && found) { - if (nr == 1) { + if (found) { + /* + * nr is counting all dups in the chain only if + * prune_stale_stable_nodes is true, otherwise we may + * break the loop at nr == 1 even if there are + * multiple entries. + */ + if (prune_stale_stable_nodes && nr == 1) { /* * If there's not just one entry it would * corrupt memory, better BUG_ON. In KSM @@ -1374,12 +1375,22 @@ struct page *stable_node_dup(struct stable_node **_stable_node_dup, * time. */ stable_node = NULL; - } else if (__is_page_sharing_candidate(found, 1)) { + } else if (stable_node->hlist.first != &found->hlist_dup && + __is_page_sharing_candidate(found, 1)) { /* - * Refile our candidate at the head - * after the prune if our candidate - * can accept one more future sharing - * in addition to the one underway. + * If the found stable_node dup can accept one + * more future merge (in addition to the one + * that is underway) and is not at the head of + * the chain, put it there so next search will + * be quicker in the !prune_stale_stable_nodes + * case. + * + * NOTE: it would be inaccurate to use nr > 1 + * instead of checking the hlist.first pointer + * directly, because in the + * prune_stale_stable_nodes case "nr" isn't + * the position of the found dup in the chain, + * but the total number of dups in the chain. */ hlist_del(&found->hlist_dup); hlist_add_head(&found->hlist_dup,