From patchwork Thu Feb 23 03:04:49 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sergey Senozhatsky X-Patchwork-Id: 13149804 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 668BEC64ED6 for ; Thu, 23 Feb 2023 03:05:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 00F3B6B0083; Wed, 22 Feb 2023 22:05:13 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id F00666B0085; Wed, 22 Feb 2023 22:05:12 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D535E6B0087; Wed, 22 Feb 2023 22:05:12 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id C4FCB6B0083 for ; Wed, 22 Feb 2023 22:05:12 -0500 (EST) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 8D550A0F15 for ; Thu, 23 Feb 2023 03:05:12 +0000 (UTC) X-FDA: 80497065264.30.729685F Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) by imf28.hostedemail.com (Postfix) with ESMTP id A3793C0010 for ; Thu, 23 Feb 2023 03:05:10 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=FukfwasN; spf=pass (imf28.hostedemail.com: domain of senozhatsky@chromium.org designates 209.85.214.182 as permitted sender) smtp.mailfrom=senozhatsky@chromium.org; dmarc=pass (policy=none) header.from=chromium.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1677121510; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=GiCIpL03JBPiX3r0aUEMNZiww2WahzTmtx5CHsJtG58=; b=4pZY+FA1cyA5B4rR7BWwG5WotD+LrlIFpASwP9EL8ZqnoXu0qOqAJnvEoqY5DduKF8pihq O9/qCDOZCFGWbLzTMbqRGNl75LHU300rW17SWtJLOYhcIXgRhcDEsSBHyU1SqtXyHZmheP YAte3NZ6+R+vhWLcfm4xbL4XvmxJ/aA= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=FukfwasN; spf=pass (imf28.hostedemail.com: domain of senozhatsky@chromium.org designates 209.85.214.182 as permitted sender) smtp.mailfrom=senozhatsky@chromium.org; dmarc=pass (policy=none) header.from=chromium.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1677121510; a=rsa-sha256; cv=none; b=C5WP1iBSpCRT+pDWyDH2VU6xyFSudIKLY9UZ7+f3ZU2sjAhYBg/3U2TunH653MXc9PVugl leOlwE+tAHAmzNnjk8E0MZU3/had7F6AUA70ruvEgpkWm9f++GxbPFuYOotPuRhaUERjUO 0+MB5Yc0B1Lz61DqJ4sOxUiTsgWl4iQ= Received: by mail-pl1-f182.google.com with SMTP id ky4so12450731plb.3 for ; Wed, 22 Feb 2023 19:05:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=GiCIpL03JBPiX3r0aUEMNZiww2WahzTmtx5CHsJtG58=; b=FukfwasNWu2Rzz92i5So8JtB90Utw+Izt47hiVM88qDg1BDIfH+2JocdZt1RMXn+V/ 4dm6ceSVu9mc/bdHNTCeWGCNCPyvnKlp70VGAgY9rIQj+GssKAweQyHmVuNintyLSZId fBGzg7ROy/QxWOcEJqobjmpM/xp/ZJgkisuco= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=GiCIpL03JBPiX3r0aUEMNZiww2WahzTmtx5CHsJtG58=; b=TYYe1GGYlvwe35btmUoBsWQcIuMCQUjNZfmrOkdEv+MDachh7vCLSK20WIx+yYXUIB D/8SdxdqY3RzsBXgMfu3IUDQUSyGThy6ibl4i2L791H3gl2qqj6qBeVN0l/SvXr5licB mVCZU/wrYimp8jlNRNokSiw9EX5+WDcxXUFLIcvLytPqePcJyAeoFHhVO/RPYaeQ/QJR w5wIXdulVbo2tqybN3cHOCSCKUMCsDydmzudfC7jbSKwtbg9VGy572BLq8ZLNG8+gQs+ w2JtU+tn44LEUcopqqZw56l4OyEOg4J8bRIhv4dICy6qMCms4SXfyxCR26cwiuw2tl/T s0iA== X-Gm-Message-State: AO0yUKV+mpqtyURDWPCYeQ0JdiRt8uMrcswsoEEZ/TiBL4EGaeR+JPmT AnShhH4xvOOVUNLWEHtfZ7sTpw== X-Google-Smtp-Source: AK7set8sb4kTJVjexH2DXpQTOdukrnurX2LTxpUBToPlcF9kX7HONNbD7HTaLTBbcSMjfIIg4eb4VA== X-Received: by 2002:a17:903:284:b0:19a:9797:1631 with SMTP id j4-20020a170903028400b0019a97971631mr10850314plr.3.1677121509605; Wed, 22 Feb 2023 19:05:09 -0800 (PST) Received: from tigerii.tok.corp.google.com ([2401:fa00:8f:203:6de2:9e85:b508:57b8]) by smtp.gmail.com with ESMTPSA id jl21-20020a170903135500b0019926c77577sm608520plb.90.2023.02.22.19.05.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Feb 2023 19:05:09 -0800 (PST) From: Sergey Senozhatsky To: Minchan Kim , Andrew Morton Cc: Yosry Ahmed , linux-kernel@vger.kernel.org, linux-mm@kvack.org, Sergey Senozhatsky Subject: [PATCHv2 4/6] zsmalloc: rework compaction algorithm Date: Thu, 23 Feb 2023 12:04:49 +0900 Message-Id: <20230223030451.543162-5-senozhatsky@chromium.org> X-Mailer: git-send-email 2.39.2.637.g21b0678d19-goog In-Reply-To: <20230223030451.543162-1-senozhatsky@chromium.org> References: <20230223030451.543162-1-senozhatsky@chromium.org> MIME-Version: 1.0 X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: A3793C0010 X-Rspam-User: X-Stat-Signature: q889duh9ieyyrkb4krm94rq9frwxypro X-HE-Tag: 1677121510-956662 X-HE-Meta: U2FsdGVkX19h0ZhY5+ZEXrOTDJZnZyw/9FNm/cFF7hdY3JQ5bW+078z7E5C1i1LSFmkziy0UvHfik0NKdpEX2Aaips8fN7fUKgNfvQbVmGrIkAbL/mIC+0k7bNSoz2OPyCXmHiGGc3AIFpuzBTNHLFKdhEkLs9u6dmCFyV17iYZ//0el21L/Lymbvh7P1iwg4/QdF7KuZiqPyRzM2jmW6Mm/5tX2d/X0ZLDszaajeLyO2K1yfXuTe/NrdaYuRnx92iVabVYGHZF6j/IsNp4zpO/cKps+BDo9lowElpkyij4jPqeIbMe1c5UfJMTrtqA4NWulVtLSoKwEfqAG+kRk2BJxZhA1fAZ82xdkJQBOzLFSrjGL8D9cJHjRqjNDt3O1XFgYvdXq8MBjTQzMTB1nyYSARWPxw3jJ3fHWM/vbljfNMKAt2OE3OqhKdQTtel237vyttuoCnAZhXcI3tYf5XrS5fkLfZp5xm9nrLKdss3zFAgN/J47S/BWrQV7f1Yh1bjbxz6ArVHjbv0RW4kt/L9jkIQQINWbFvTvD41go1Z86CNWoFtJF7RWfZhnYoibO9F1bR9GH3JAaOkx2V69xn6vB1EUesWGqAxr3JE0yCZ2dt2phvBbCi3DLEvOikke3uR7j0uPK28+WDdvuVNg3ZIMEz4Cwl3PNL7jwlP/lyc+eHEAsz59EvX7jZKzZvPprx0Jv9PZHLw1d9hU8JICjHWBm22oFjzSdyCDdcJiNPGjQqIMqvRo0fRMo5Lk8/GoV/K+QlA3lTeRwFR6RHqprwioXDg44jSJh4JL316BWbHGoogQTE9E1CXleo/X0G5ImHVHP+k4kCtrEXeijtGKnkPeRDMZZ/cndixB/PVPj2vcRHOnymR6/T0jJ6h2H8C2TsLVJwS+dAbUqTbiR5FY2nubT7R8hX4AnQE8cNpq7d2nCj4j38ecHds/PfM+AJ5RuTJqPp764SKarD3SN5I4 OT/3wd4D zXruhXgmktJWSmRb33FuVs9iAQE0iL2PqY2cmlDMMmb4+wTU5w1fMP9zkZ4EoRol0CkPzMI8sy6o483Iq5mdEx3MW2Wqx6kMjeTBRg9cWzwXRzxpvLl/OB9rVOmwOxdZDGJFmqDdN6rtRdCxq4lj0Q+Gnyp0zAc/wEtVbct/VLRV2X63rd/wTSZucWqsQFD1bG+YiudZJNDUBFN67oVt5+xLq2HmSiwzmRC82qq1SMkNwKAhj9WxTEzVOwW2+TK2ujdwJlhF4/Pn6PAWRPYaHSMR7UDsMvVl37yglMm8ujbOw1NdnftAKoM3IL02U8BBS6HINqWHOPgs1YUtSKQUhlz5C3r6T4DBG9hKn64ulogSM7nOg3tG64DvH9NeufAIzcKP7QdVjY10R+1U= X-Bogosity: Ham, tests=bogofilter, spamicity=0.003454, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: The zsmalloc compaction algorithm has the potential to waste some CPU cycles, particularly when compacting pages within the same fullness group. This is due to the way it selects the head page of the fullness list for source and destination pages, and how it reinserts those pages during each iteration. The algorithm may first use a page as a migration destination and then as a migration source, leading to an unnecessary back-and-forth movement of objects. Consider the following fullness list: PageA PageB PageC PageD PageE During the first iteration, the compaction algorithm will select PageA as the source and PageB as the destination. All of PageA's objects will be moved to PageB, and then PageA will be released while PageB is reinserted into the fullness list. PageB PageC PageD PageE During the next iteration, the compaction algorithm will again select the head of the list as the source and destination, meaning that PageB will now serve as the source and PageC as the destination. This will result in the objects being moved away from PageB, the same objects that were just moved to PageB in the previous iteration. To prevent this avalanche effect, the compaction algorithm should not reinsert the destination page between iterations. By doing so, the most optimal page will continue to be used and its usage ratio will increase, reducing internal fragmentation. The destination page should only be reinserted into the fullness list if: - It becomes full - No source page is available. Signed-off-by: Sergey Senozhatsky --- mm/zsmalloc.c | 82 ++++++++++++++++++++++++--------------------------- 1 file changed, 38 insertions(+), 44 deletions(-) diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c index 1a92ebe338eb..eacf9e32da5c 100644 --- a/mm/zsmalloc.c +++ b/mm/zsmalloc.c @@ -1786,15 +1786,14 @@ struct zs_compact_control { int obj_idx; }; -static int migrate_zspage(struct zs_pool *pool, struct size_class *class, - struct zs_compact_control *cc) +static void migrate_zspage(struct zs_pool *pool, struct size_class *class, + struct zs_compact_control *cc) { unsigned long used_obj, free_obj; unsigned long handle; struct page *s_page = cc->s_page; struct page *d_page = cc->d_page; int obj_idx = cc->obj_idx; - int ret = 0; while (1) { handle = find_alloced_obj(class, s_page, &obj_idx); @@ -1807,10 +1806,8 @@ static int migrate_zspage(struct zs_pool *pool, struct size_class *class, } /* Stop if there is no more space */ - if (zspage_full(class, get_zspage(d_page))) { - ret = -ENOMEM; + if (zspage_full(class, get_zspage(d_page))) break; - } used_obj = handle_to_obj(handle); free_obj = obj_malloc(pool, get_zspage(d_page), handle); @@ -1823,8 +1820,6 @@ static int migrate_zspage(struct zs_pool *pool, struct size_class *class, /* Remember last position in this iteration */ cc->s_page = s_page; cc->obj_idx = obj_idx; - - return ret; } static struct zspage *isolate_src_zspage(struct size_class *class) @@ -2228,57 +2223,56 @@ static unsigned long __zs_compact(struct zs_pool *pool, * as well as zpage allocation/free */ spin_lock(&pool->lock); - while ((src_zspage = isolate_src_zspage(class))) { - /* protect someone accessing the zspage(i.e., zs_map_object) */ - migrate_write_lock(src_zspage); - - if (!zs_can_compact(class)) - break; - - cc.obj_idx = 0; - cc.s_page = get_first_page(src_zspage); - - while ((dst_zspage = isolate_dst_zspage(class))) { - migrate_write_lock_nested(dst_zspage); - + while (1) { + if (!dst_zspage) { + dst_zspage = isolate_dst_zspage(class); + if (!dst_zspage) + goto out; + migrate_write_lock(dst_zspage); cc.d_page = get_first_page(dst_zspage); - /* - * If there is no more space in dst_page, resched - * and see if anyone had allocated another zspage. - */ - if (!migrate_zspage(pool, class, &cc)) - break; + } + if (!zs_can_compact(class)) { putback_zspage(class, dst_zspage); migrate_write_unlock(dst_zspage); - dst_zspage = NULL; - if (spin_is_contended(&pool->lock)) - break; + goto out; } - /* Stop if we couldn't find slot */ - if (dst_zspage == NULL) - break; + src_zspage = isolate_src_zspage(class); + if (!src_zspage) { + putback_zspage(class, dst_zspage); + migrate_write_unlock(dst_zspage); + goto out; + } - putback_zspage(class, dst_zspage); - migrate_write_unlock(dst_zspage); + migrate_write_lock_nested(src_zspage); + + cc.obj_idx = 0; + cc.s_page = get_first_page(src_zspage); + migrate_zspage(pool, class, &cc); if (putback_zspage(class, src_zspage) == ZS_INUSE_RATIO_0) { migrate_write_unlock(src_zspage); free_zspage(pool, class, src_zspage); pages_freed += class->pages_per_zspage; - } else + } else { migrate_write_unlock(src_zspage); - spin_unlock(&pool->lock); - cond_resched(); - spin_lock(&pool->lock); - } + } - if (src_zspage) { - putback_zspage(class, src_zspage); - migrate_write_unlock(src_zspage); - } + if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100 + || spin_is_contended(&pool->lock)) { + putback_zspage(class, dst_zspage); + migrate_write_unlock(dst_zspage); + dst_zspage = NULL; + } + if (!dst_zspage) { + spin_unlock(&pool->lock); + cond_resched(); + spin_lock(&pool->lock); + } + } +out: spin_unlock(&pool->lock); return pages_freed;