From mboxrd@z Thu Jan 1 00:00:00 1970 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 133F6EE3F09 for ; Tue, 12 Sep 2023 17:56:15 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8BA016B0132; Tue, 12 Sep 2023 13:56:14 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 86A1A6B0133; Tue, 12 Sep 2023 13:56:14 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 731E86B0134; Tue, 12 Sep 2023 13:56:14 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 648176B0132 for ; Tue, 12 Sep 2023 13:56:14 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 2CEBA401A4 for ; Tue, 12 Sep 2023 17:56:14 +0000 (UTC) X-FDA: 81228699468.09.57597AA Received: from mail-qv1-f54.google.com (mail-qv1-f54.google.com [209.85.219.54]) by imf08.hostedemail.com (Postfix) with ESMTP id 059BC160022 for ; Tue, 12 Sep 2023 17:56:11 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=cmpxchg-org.20230601.gappssmtp.com header.s=20230601 header.b=VIVUev5z; spf=pass (imf08.hostedemail.com: domain of hannes@cmpxchg.org designates 209.85.219.54 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org; dmarc=pass (policy=none) header.from=cmpxchg.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1694541372; 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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=X4IhYeB0YxtIaCDBZz0UEzpIO0PR5QWLYjcVC9SEpKA=; b=QIfO+2v9P2QyzIJUezkgxPahu03qBQ0MPVmUjimpwNzCKDf23UyCB+f+ThsF3Uu6ov7k1X azgWTYH5sGMjbO4ID9mZHwNRTZUDd5UcasW4WkPTbBhMa4IP2U/t1KisxtNUant4pb0DY8 iVnBqDeL+Q8ZLJUJXxqIHmKyswmLyaQ= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1694541372; a=rsa-sha256; cv=none; b=QA+jeE+f/QEDAJoObe0/SLwwAZtzAJtgp7QTcB0TVz6//rnHIoIW7TUiQdOhLquwYMZK3H Wj1EcBSl5255qWsuWpizOnlhKNZp8u+OPt3kmq/3HVzp14xvMTanXFab4O/GoEo9oPVg66 J0/O7HSqcjFOHdrilOS60Y7HYi/ke9E= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=cmpxchg-org.20230601.gappssmtp.com header.s=20230601 header.b=VIVUev5z; spf=pass (imf08.hostedemail.com: domain of hannes@cmpxchg.org designates 209.85.219.54 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org; dmarc=pass (policy=none) header.from=cmpxchg.org Received: by mail-qv1-f54.google.com with SMTP id 6a1803df08f44-6556d05a55fso31923646d6.3 for ; Tue, 12 Sep 2023 10:56:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cmpxchg-org.20230601.gappssmtp.com; s=20230601; t=1694541371; x=1695146171; darn=kvack.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=X4IhYeB0YxtIaCDBZz0UEzpIO0PR5QWLYjcVC9SEpKA=; b=VIVUev5zU2iARmGKpOHb2cOcQLj6ecBF1X7TXrzCIBulS4h1PyAeHsTf8mjg27t8jO kUln1Xxm1xloee5zsPwZiq9rCtftOq+DCie1URyxBmExk6hYbd51NRqxoXXCLUbAcnPh SHNdUPygOJpjZ8BXsqrHUGTKfsMUdhNydOEIoC90+2P/iZ5S1R1m5IvSru3/F1l3q6LL wOX5G8o+BUEaG7qKI+Eh/L3sGBL0/5s+CcCkBhVP6HzpymIL3gvpJs8StQiPPZTgYjb0 nX8PjgaFWRpvnddHdEhOUUdmtNE7PZHrqa9M4ufzuIMRN20xbwtdYyXEAT26SdvRtgPn bM6g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1694541371; x=1695146171; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=X4IhYeB0YxtIaCDBZz0UEzpIO0PR5QWLYjcVC9SEpKA=; b=AS0Qg3LZKLXJv5/82lQ9WR94Zeuvp2DNOlw/Q8zftbuP6yvIkzxzdu60Svpg/19jPV 8y+yR/ZHMaMtj0QDGZGDXQZalTDmP9vW1x/L4JMPz30N/rvnM5vpud1tgrzeK0OqB+of ChjM1vnYHDK5H1jAplOiiCJzUr8dDnCIuEmmE/Wx0QBy7QaRn/lKJ4F63Q640XutJiV8 RTXkteciSNrqrVC8KjW2ae3nlVNo7tMo9e4GjDPqndS8/xwT6RqVLvwPRAPidFoxWe+A 0AWBLH85SgPC+PHOU6hmLSbTCfYq6EXGFTjlQ7/ucJWBrKXwqpr/EZdxd2XisCbgX/Uz GHTg== X-Gm-Message-State: AOJu0YyasKNR2FC/lWTV6Z9eh8LD9anunb8aG8DphTOjSI0EsgtYNIiF VepB4qzXu1T37e8e6ZZ7dZGLiA== X-Google-Smtp-Source: AGHT+IHMl4rjeTD1z5d9sbmC4XZdGewFfSDjPv1SOboURcLudwLKitRMq75HOOrGTQ9kiILB0EdT5Q== X-Received: by 2002:a05:6214:4a04:b0:64f:5729:7994 with SMTP id pg4-20020a0562144a0400b0064f57297994mr193814qvb.30.1694541370968; Tue, 12 Sep 2023 10:56:10 -0700 (PDT) Received: from localhost (2603-7000-0c01-2716-3012-16a2-6bc2-2937.res6.spectrum.com. [2603:7000:c01:2716:3012:16a2:6bc2:2937]) by smtp.gmail.com with ESMTPSA id a17-20020a0ce391000000b006418c076f59sm3760138qvl.100.2023.09.12.10.56.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Sep 2023 10:56:10 -0700 (PDT) Date: Tue, 12 Sep 2023 13:56:10 -0400 From: Johannes Weiner To: Zi Yan Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, Zi Yan , Ryan Roberts , Andrew Morton , "Matthew Wilcox (Oracle)" , David Hildenbrand , "Yin, Fengwei" , Yu Zhao , Vlastimil Babka , Baolin Wang , Kemeng Shi , Mel Gorman , Rohan Puri , Mcgrof Chamberlain , Adam Manzanares , John Hubbard Subject: Re: [RFC PATCH 3/4] mm/compaction: optimize >0 order folio compaction by sorting source pages. Message-ID: <20230912175610.GC34089@cmpxchg.org> References: <20230912162815.440749-1-zi.yan@sent.com> <20230912162815.440749-4-zi.yan@sent.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230912162815.440749-4-zi.yan@sent.com> X-Rspamd-Queue-Id: 059BC160022 X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: gr8sddfrww4baky3kxh6yd36nefoeoek X-HE-Tag: 1694541371-61935 X-HE-Meta: U2FsdGVkX183ETzkBy5ZaVbPVhhlX6zHRTPDdTvq/yKZDl6mBZaO3dbU7R882hyItI3CsKrR9/vSfVW4O0TelbctTPWRylWPqIdjLOFMsKaExHhWm0jXcw8AjvA1bXvIM6mB4KjyDiYyuB+MoyDg3HW8jWiFhXjpKR5rTQhQJSE4FcaJBGbzAok1z5C8U0SBXI1wMJpP7N55J+54GNdVw5ItZUyweAaFXlEYGq99onFojFoEisBHoXqzW/yVijIrNJJGAkglf0vbecM4QmPymQ+DV6CFCPntRiztKA8i4jl1YphHyQChmT16rUakJ+jOTLA7VvfUJ9bfvl0fr6NWOnT7d7DZ8yhLRPNUKQE2vkIaxti6eToXyu0eDBgmohOTSA/lmzHZGhHRhcRlem8uJXS5lZQbDJzQx4d8aKPSmMvMBINMlBAOKDMAu97nz8OyHKZuj0tYZWiEfkxgJd1nOecz4ufml2JKu9nWK+dZ+RLCI52Cebt9Ox431/DewgnsvCvet3ScnxkOpbe/sQdmq4g45oKeomhddOXrizxbDNRdrRW8544VRwG9YQTUZaWtGVr4n0rDftT+MvVc0wu+4rcZ9qEX/6A0zsq1nZOLFDCKNeCslTuw2ixPAMAbsOuz9mYjrnQn8QUNNt45L+0FMnCCik/lRIbneT64e1vznCpKjAnShY6iHVBTwiRmjw8L5en3W3+k7cBRM/0mmQRP7mbfwhcACEm2im3xGqY1O+8AeAT9OSZAfJJNem6w2/if8SiIiXfRbRTWapTDrNOJVp5s/mdGkp+BIIj3Qd+Ae49Nk/GdedliY8tXvt9c5Xlg0QLDEDbxA8SfSi5xcBSSQdMIWGZHB/6W3pqk9oLtwNmwmuMrqnHp4u/Exj49hsx7QxhTO0dnNkHmFDf/lZ2tsNPYwPb+gYIWW/9totdGBuKjoJssH9MvXPachz1iFhBGbfEHyYj29vd6pTOQcMl bYIgPdNQ 2WAYXF90bdJPcBkU3p3ukTmcT67x7wLLJmYngoGj1u5Z73wVl4LZqQMVwYGpUA/b00NVtbGLzvAFkUl4U8gtClFD9TRaMLHkys/Zd0GVuq8oQwJ8x2NGFD5J9GY2h8AV3i0x21RghV/k6LExJGKwhF6vToQilYvLwNPNTR8OV1nYZfaGhuSvQIridgAvWhPZXalbZPUTVV3IxUdfs3Hoijw+cWVyjDm7IcuyitZ0u0HO3h4kxqT5Rwirgjm01e0bzU3ZnyIcBMnxv4obyaDcMho5dqXw+fnvYKjvJQf+NxTs5sEjxNMDFHuTgeYrXs3HRYwXBaaxrpYK2x6JjbW7Gr7OumpUn/gQj+wURWilXvcet1dLUGR88h7ieUP+ZTtHYcWGAOD0zRtwaZMWQbk94A2iiK4wFL0n593qD7Tiw7NL2+pSPknktSBdMlugXiBEq8oNNm+L+ATNSZaxjHxjkFcB5z1QET5ASc8qGdnQtGL+omEnxJ5aFb3HWDw== 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: On Tue, Sep 12, 2023 at 12:28:14PM -0400, Zi Yan wrote: > From: Zi Yan > > It should maximize high order free page use and minimize free page splits. > It might be useful before free page merging is implemented. The premise sounds reasonable to me: start with the largest chunks in the hope of producing the desired block size before having to piece things together from the order-0s dribbles. > @@ -145,6 +145,38 @@ static void sort_free_pages(struct list_head *src, struct free_list *dst) > } > } > > +static void sort_folios_by_order(struct list_head *pages) > +{ > + struct free_list page_list[MAX_ORDER + 1]; > + int order; > + struct folio *folio, *next; > + > + for (order = 0; order <= MAX_ORDER; order++) { > + INIT_LIST_HEAD(&page_list[order].pages); > + page_list[order].nr_free = 0; > + } > + > + list_for_each_entry_safe(folio, next, pages, lru) { > + order = folio_order(folio); > + > + if (order > MAX_ORDER) > + continue; > + > + list_move(&folio->lru, &page_list[order].pages); > + page_list[order].nr_free++; > + } > + > + for (order = MAX_ORDER; order >= 0; order--) { > + if (page_list[order].nr_free) { > + > + list_for_each_entry_safe(folio, next, > + &page_list[order].pages, lru) { > + list_move_tail(&folio->lru, pages); > + } > + } > + } > +} > + > #ifdef CONFIG_COMPACTION > bool PageMovable(struct page *page) > { > @@ -2636,6 +2668,8 @@ compact_zone(struct compact_control *cc, struct capture_control *capc) > pageblock_start_pfn(cc->migrate_pfn - 1)); > } > > + sort_folios_by_order(&cc->migratepages); Would it make sense to have isolate_migratepages_block() produce a sorted list already? By collecting into a struct free_list in there and finishing with that `for (order = MAX...) list_add_tail()' loop. That would save quite a bit of shuffling around. Compaction can be hot, and is expected to get hotter with growing larger order pressure. The contig allocator doesn't care about ordering, but it should be possible to gate the sorting reasonably on !cc->alloc_contig. An optimization down the line could be to skip the sorted list assembly for the compaction case entirely, have compact_zone() work directly on struct free_list, starting with the highest order and checking compact_finished() in between orders.