From patchwork Wed Jul 31 06:49:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Li X-Patchwork-Id: 13748192 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 13770C52D1D for ; Wed, 31 Jul 2024 06:49:43 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 17D636B0089; Wed, 31 Jul 2024 02:49:28 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0DFA56B0093; Wed, 31 Jul 2024 02:49:28 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D86F06B0098; Wed, 31 Jul 2024 02:49:27 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 96C316B0089 for ; Wed, 31 Jul 2024 02:49:27 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 1CA1C8015F for ; Wed, 31 Jul 2024 06:49:27 +0000 (UTC) X-FDA: 82399121574.27.022A852 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf26.hostedemail.com (Postfix) with ESMTP id 5806E14000D for ; Wed, 31 Jul 2024 06:49:25 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=itCPSWVG; spf=pass (imf26.hostedemail.com: domain of chrisl@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=chrisl@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1722408537; a=rsa-sha256; cv=none; b=8n46e2IPpjjyhQPhdrUp1UI/b9YxH5xWaJJsa3f+DDvdIZN9MiR9H2cKUu88e6MUHAflbG rmA5Y5oqUacVFtQdZ0ngobQ+XUXxBBZd+uDiEFE0R5EIedbt/Hn6GyI+Ygp0LxWYw1b0Cy nPbVaLxjK+MGwIJf1wqKZqbiGkNcw/E= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=itCPSWVG; spf=pass (imf26.hostedemail.com: domain of chrisl@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=chrisl@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1722408537; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=/UxfJ0LXr9hn9n0h8ZVipttrVk9Nbw8TQC+goHuxA3g=; b=gPl+jv9OUH2CafHjiNiVDeZCZwCidqzyIfLULUcKSuOEdzooTPVdflYqAY16HdmPYzVaje oolpSMMtxieHNPH/XGOjTHwruxDfmybuMNkpRemZ/jh0F8toe8ek3Hd6JZ167zSAHZtItO 0L4lEvgtiknaY/PFB1WUaBnR1ercI78= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 56A51621FB; Wed, 31 Jul 2024 06:49:24 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id C4391C4AF14; Wed, 31 Jul 2024 06:49:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1722408564; bh=LMjsqNTIwXS2shaii6dMa6mkdJXeL7A42/t9cu9stO0=; h=From:Date:Subject:References:In-Reply-To:To:Cc:From; b=itCPSWVG1mWJFeRuT4Y6xvyqL/gB+zuPWdzR33gpL1Asheo80VUsMCQHBVfoZArOk A61aAkf+gAfsUAp6AjgSvGn71FnPDV8s4sgoFmId49e2kUoTzC3ziLTPzqiUhM4Sn9 i0vulb+sGgvlwyMr9an1j5zyq4a5NN5E37YRkg1FJTzPgTo6FZNIFwMUgdAP1KcRMy G+kMbs3mIKIMdqYCzCbyamHCcNTZNoDebnkDkKEnhPjPVFWespNM55cOxnPgHrG09Y 4ZRt5i4lV1uxB+J/7BDfyDBItiKzUJEv6qUOdjqdxgIy1zIJjYIG/LhUmvdNj0eVgN dHPh1Bf9yuX1g== From: chrisl@kernel.org Date: Tue, 30 Jul 2024 23:49:19 -0700 Subject: [PATCH v5 7/9] mm: swap: add a fragment cluster list MIME-Version: 1.0 Message-Id: <20240730-swap-allocator-v5-7-cb9c148b9297@kernel.org> References: <20240730-swap-allocator-v5-0-cb9c148b9297@kernel.org> In-Reply-To: <20240730-swap-allocator-v5-0-cb9c148b9297@kernel.org> To: Andrew Morton Cc: Kairui Song , Hugh Dickins , Ryan Roberts , "Huang, Ying" , Kalesh Singh , linux-kernel@vger.kernel.org, linux-mm@kvack.org, Chris Li , Barry Song X-Mailer: b4 0.13.0 X-Stat-Signature: ujjkppg5cqty9dtdsdh3qsdurw7zmpry X-Rspamd-Queue-Id: 5806E14000D X-Rspam-User: X-Rspamd-Server: rspam10 X-HE-Tag: 1722408565-902456 X-HE-Meta: U2FsdGVkX19qEC48QNt02bYUGuJzez5d/2iGotYlyuYTKYj2D79a1EOkKDwzicY30hl6zceVwg2azZdUW8zZOiHTSjKbbCbVFk3VqRk2UIfLQmTQIxW5m6z8egnHiPsfsrgMTpcPjEpHx0jMqE8IwOO+LAmtefa8Uqas9tfpZcYBNLRxeuNSbf8AwPbyc3qWC/AjtlWIK9cpmKIk9iD0Z5mDtwaA3eR9Lp/hn0V4WJZagxEQeQiLzkoeRnluZ5S0V3YWFI9hD/x9Nt/2G7gqB7eL8kXEbC29cP1vYEYvc0qgAHlr0spWWCBy/FPaOkMbovbmQ6U3F7cisSJ3VtuBlTNgmq7H7jmJ/aYkXBtLt9Bk1Wbdn+RcDnY+IAgw699sKj5rhczYMP0f4K/Z3GHzSpQvlW13nvvgt18Rii1eAtuVbic/ual5smIZ/mkPAMzYiBRdPWvjyPjyJnS3ZxNYZk5JvbNLiN6jYxmykMAzA+Q+tgsngGDT8qsgNSfTE9NoIqF24nAg8aWPydhguVL06vir9lhErCTmn3rSonGPV63doM3L7C10VrBKKtrKQIS7tDeDchnB6mgRhwcFZ8yk+zXM1l0rbzSCTxBgzek0/B5s6Y8y2+WpzOQswuTdhSnUL2Omi7ZBaDqk8Skv/E38ScBEANkzosvl4AQfUCmqPeYut+2islGmonepx3GIJ5ZFyObdYpUtLjx5adGzIRfKORcBFVDLGR1aZ7OBFzxqlQ2SPpDR6b5rfsqUO8xpYFIieTsOMCxI51nlYVfMc+z3t8mfay3QB4dgcJcCUWCzf1fKoblEx2tkkVwbk6DgAfh2Uw8Kk20VcMrzrzulskpx5zpAbkOzrkPnoSsJiPD4g2QF15JSWDnVg7OmjpJnalSOl9N9Dx2f1G2WKAFocSmmzajExw30o2kVnpWIskrm1cnicY0OKKtX3WWFS96HtEzT41/hv3bDJUgHC+f7ewd q3JJJCX5 k4d29VoWqU981xIEVsF8oFt+Wx9l08O5ZJ5Ust/eXIRcSu1gr4TVYTxCm0oRrf8jwZgOQxryCjCFHlDe8vrOv0fOiBuUL0iFF6re1QLXOa/3yckzZShT5Kgm0pCglm3FrybNPl2TCre1F48+NJSSHwVOXU48kTfnpYBGms/7+X0BH1aUCH3Q1ejIgOKaDTEUirPAzL9OJmzYwFjREu1m9IUaBmN7aeEYDa0scEvlNC175D16UFtF/kDtOdQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: From: Kairui Song Now swap cluster allocator arranges the clusters in LRU style, so the "cold" cluster stay at the head of nonfull lists are the ones that were used for allocation long time ago and still partially occupied. So if allocator can't find enough contiguous slots to satisfy an high order allocation, it's unlikely there will be slot being free on them to satisfy the allocation, at least in a short period. As a result, nonfull cluster scanning will waste time repeatly scanning the unusable head of the list. Also, multiple CPUs could content on the same head cluster of nonfull list. Unlike free clusters which are removed from the list when any CPU starts using it, nonfull cluster stays on the head. So introduce a new list frag list, all scanned nonfull clusters will be moved to this list. Both for avoiding repeated scanning and contention. Frag list is still used as fallback for allocations, so if one CPU failed to allocate one order of slots, it can still steal other CPU's clusters. And order 0 will favor the fragmented clusters to better protect nonfull clusters If any slots on a fragment list are being freed, move the fragment list back to nonfull list indicating it worth another scan on the cluster. Compared to scan upon freeing a slot, this keep the scanning lazy and save some CPU if there are still other clusters to use. It may seems unneccessay to keep the fragmented cluster on list at all if they can't be used for specific order allocation. But this will start to make sense once reclaim dring scanning is ready. Signed-off-by: Kairui Song --- include/linux/swap.h | 3 +++ mm/swapfile.c | 41 +++++++++++++++++++++++++++++++++++++---- 2 files changed, 40 insertions(+), 4 deletions(-) diff --git a/include/linux/swap.h b/include/linux/swap.h index 6716ef236766..5a14b6c65949 100644 --- a/include/linux/swap.h +++ b/include/linux/swap.h @@ -259,6 +259,7 @@ struct swap_cluster_info { }; #define CLUSTER_FLAG_FREE 1 /* This cluster is free */ #define CLUSTER_FLAG_NONFULL 2 /* This cluster is on nonfull list */ +#define CLUSTER_FLAG_FRAG 4 /* This cluster is on nonfull list */ /* * The first page in the swap file is the swap header, which is always marked @@ -299,6 +300,8 @@ struct swap_info_struct { struct list_head free_clusters; /* free clusters list */ struct list_head nonfull_clusters[SWAP_NR_ORDERS]; /* list of cluster that contains at least one free slot */ + struct list_head frag_clusters[SWAP_NR_ORDERS]; + /* list of cluster that are fragmented or contented */ unsigned int lowest_bit; /* index of first free in swap_map */ unsigned int highest_bit; /* index of last free in swap_map */ unsigned int pages; /* total of usable pages of swap */ diff --git a/mm/swapfile.c b/mm/swapfile.c index 4c0fc0409d3c..eb3e387e86b2 100644 --- a/mm/swapfile.c +++ b/mm/swapfile.c @@ -572,7 +572,10 @@ static void dec_cluster_info_page(struct swap_info_struct *p, if (!(ci->flags & CLUSTER_FLAG_NONFULL)) { VM_BUG_ON(ci->flags & CLUSTER_FLAG_FREE); - list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]); + if (ci->flags & CLUSTER_FLAG_FRAG) + list_move_tail(&ci->list, &p->nonfull_clusters[ci->order]); + else + list_add_tail(&ci->list, &p->nonfull_clusters[ci->order]); ci->flags = CLUSTER_FLAG_NONFULL; } } @@ -610,7 +613,8 @@ static inline void cluster_alloc_range(struct swap_info_struct *si, struct swap_ ci->count += nr_pages; if (ci->count == SWAPFILE_CLUSTER) { - VM_BUG_ON(!(ci->flags & (CLUSTER_FLAG_FREE | CLUSTER_FLAG_NONFULL))); + VM_BUG_ON(!(ci->flags & + (CLUSTER_FLAG_FREE | CLUSTER_FLAG_NONFULL | CLUSTER_FLAG_FRAG))); list_del(&ci->list); ci->flags = 0; } @@ -666,6 +670,7 @@ static unsigned long cluster_alloc_swap_entry(struct swap_info_struct *si, int o struct percpu_cluster *cluster; struct swap_cluster_info *ci, *n; unsigned int offset, found = 0; + LIST_HEAD(fraged); new_cluster: lockdep_assert_held(&si->lock); @@ -686,13 +691,29 @@ static unsigned long cluster_alloc_swap_entry(struct swap_info_struct *si, int o if (order < PMD_ORDER) { list_for_each_entry_safe(ci, n, &si->nonfull_clusters[order], list) { + list_move_tail(&ci->list, &fraged); + ci->flags = CLUSTER_FLAG_FRAG; offset = alloc_swap_scan_cluster(si, cluster_offset(si, ci), &found, order, usage); if (found) - goto done; + break; } + + if (!found) { + list_for_each_entry_safe(ci, n, &si->frag_clusters[order], list) { + offset = alloc_swap_scan_cluster(si, cluster_offset(si, ci), + &found, order, usage); + if (found) + break; + } + } + + list_splice_tail(&fraged, &si->frag_clusters[order]); } + if (found) + goto done; + if (!list_empty(&si->discard_clusters)) { /* * we don't have free cluster but have some clusters in @@ -706,7 +727,17 @@ static unsigned long cluster_alloc_swap_entry(struct swap_info_struct *si, int o if (order) goto done; + /* Order 0 stealing from higher order */ for (int o = 1; o < PMD_ORDER; o++) { + if (!list_empty(&si->frag_clusters[o])) { + ci = list_first_entry(&si->frag_clusters[o], + struct swap_cluster_info, list); + offset = alloc_swap_scan_cluster(si, cluster_offset(si, ci), &found, + 0, usage); + VM_BUG_ON(!found); + goto done; + } + if (!list_empty(&si->nonfull_clusters[o])) { ci = list_first_entry(&si->nonfull_clusters[o], struct swap_cluster_info, list); @@ -3019,8 +3050,10 @@ static int setup_swap_map_and_extents(struct swap_info_struct *p, INIT_LIST_HEAD(&p->free_clusters); INIT_LIST_HEAD(&p->discard_clusters); - for (i = 0; i < SWAP_NR_ORDERS; i++) + for (i = 0; i < SWAP_NR_ORDERS; i++) { INIT_LIST_HEAD(&p->nonfull_clusters[i]); + INIT_LIST_HEAD(&p->frag_clusters[i]); + } for (i = 0; i < swap_header->info.nr_badpages; i++) { unsigned int page_nr = swap_header->info.badpages[i];