From patchwork Mon Jan 9 03:38:35 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sergey Senozhatsky X-Patchwork-Id: 13092910 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 2C5D6C54EBD for ; Mon, 9 Jan 2023 03:39:14 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8F6978E0003; Sun, 8 Jan 2023 22:39:13 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 8A7068E0001; Sun, 8 Jan 2023 22:39:13 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 76FB68E0003; Sun, 8 Jan 2023 22:39:13 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 669948E0001 for ; Sun, 8 Jan 2023 22:39:13 -0500 (EST) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 369A41A023B for ; Mon, 9 Jan 2023 03:39:13 +0000 (UTC) X-FDA: 80333854986.03.43976E3 Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) by imf26.hostedemail.com (Postfix) with ESMTP id 85FBC140004 for ; Mon, 9 Jan 2023 03:39:11 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=XjU2WoqB; spf=pass (imf26.hostedemail.com: domain of senozhatsky@chromium.org designates 209.85.214.171 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=1673235551; a=rsa-sha256; cv=none; b=BbPEgynrWNiNSiUXvs6tDInuo5ahJiKEieYHTsIfw6V9343jTJKF1F6Zh2WA4vdJMBnCRR EV9LLbCnLwT8XYuJhFskxajjrPgmBBigzdxBiaEHSZr/7/F1ORElJy/x9xsWV/Dm6YdofE F2eqAAjhzin+RjH2FZhJZQy5n04tmjs= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=XjU2WoqB; spf=pass (imf26.hostedemail.com: domain of senozhatsky@chromium.org designates 209.85.214.171 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=1673235551; 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=uJf7dha5k2JA9z4OES9HOIhzl7+lcnfFyGyI5I7+NCk=; b=t3Tx1b5JR0TvLPGaVitqJo53EIcg6WS8q9U6vQerM20nKmmprNxEsEo2U3dJjKYz9iufBN DdeodO7QH8Hgrlnnln/cqnuGYgRFap8UDEXqFT9aIQjfc8kr8lMLo5Hkn5W3bHEpNPIufy f1P+Xfm9Aj9WhR0TJsR1N5aFHzxuOb4= Received: by mail-pl1-f171.google.com with SMTP id c6so8177711pls.4 for ; Sun, 08 Jan 2023 19:39:11 -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=uJf7dha5k2JA9z4OES9HOIhzl7+lcnfFyGyI5I7+NCk=; b=XjU2WoqBTvgShhdfuAbe+bCsbpszVIl+NO3iYTEPFSxxWxCQmQ0Sc02kQvqBLet9LA 78GlE/1M9AvlvigUsXRKDG2MKRXDr0Kadg8EX9IXlzjW9ZFkPPsFjLtq7PE9YrHnH0+C weFW+9evp3q545nBXO0snJPIvzB+qEb8Gz3qM= 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=uJf7dha5k2JA9z4OES9HOIhzl7+lcnfFyGyI5I7+NCk=; b=GlBSb5FamoMs/groPnuhEwIOpHQ/lXAcp7t+N4H147erhjkIQDJaQ+yPuQotSlaR00 B3bpihmn8LaHvdaWnZgxZx4t2SnPEpIG02be5bbwqSbWqaPssf0P9Bor1x90JiKUWtBT yLymlGvgYpYQj0V5loq8wszlei56yZWeG6j5VNkBjPbDU//EKdBOJ67++tQu79CmQnzK S2/ra8le6BloMdRgWBDjO68hGOvPTYVIWGbmTv9W+QPnWrF0AzTg5QQFIQv+6kesIWcC 5yFC/ACHvlSu99l0EsswYCsvG39UxgUbgkfy2hZDrluqpvusVn1vxVssKiYbTvr/D5v0 sLCA== X-Gm-Message-State: AFqh2kpOidrx/0eExfzclgoOjiXM7qq07+aq32zMxfzn6zQZZAJKyMom QRYUsrGvCQPaeOgQ5P3DBsxKSIFGY2Mavd1N X-Google-Smtp-Source: AMrXdXudxT6l1K3qFdscG3iOXMYQPHFdnQlKnpz72FQuGvE58k91OPIVpRStqcuSy21PbOJv/Y8mFA== X-Received: by 2002:a17:902:b78c:b0:193:1fc5:f611 with SMTP id e12-20020a170902b78c00b001931fc5f611mr6023821pls.38.1673235550467; Sun, 08 Jan 2023 19:39:10 -0800 (PST) Received: from tigerii.tok.corp.google.com ([2401:fa00:8f:203:5ec1:f8d2:ce47:7ddc]) by smtp.gmail.com with ESMTPSA id u5-20020a170902e80500b00189529ed580sm4896685plg.60.2023.01.08.19.39.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 08 Jan 2023 19:39:09 -0800 (PST) From: Sergey Senozhatsky To: Minchan Kim , Andrew Morton Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org, Sergey Senozhatsky Subject: [PATCHv2 1/4] zsmalloc: rework zspage chain size selection Date: Mon, 9 Jan 2023 12:38:35 +0900 Message-Id: <20230109033838.2779902-2-senozhatsky@chromium.org> X-Mailer: git-send-email 2.39.0.314.g84b9a713c41-goog In-Reply-To: <20230109033838.2779902-1-senozhatsky@chromium.org> References: <20230109033838.2779902-1-senozhatsky@chromium.org> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Queue-Id: 85FBC140004 X-Rspamd-Server: rspam01 X-Stat-Signature: htubnwtf7n1bgame9t7b63p39qynsfyg X-HE-Tag: 1673235551-343035 X-HE-Meta: U2FsdGVkX1/gEqLX72Qd+WhyT8C4XLP0nGuVWqxoNFO/iPC5aS4szS1TOG+pcuwD8NkjTc+zj2JuxatdMsN6mMz20WaXVxDPtwAKwac0D0nX4VTJBlmxvROqGsLo7zbsyth/K6Uv7AlRN+ykhAdu4FHZd2xF64mg7lq+nbXOov6E53lK2RHF4E4NMduexuGsMBeiZEBqGBLlDDDMupGPYcLkcNRIs8NsqZJc9QAwiWrCwYtR5Z3pqtdBG/5KIUu1p9enWbV7CLuwuOK88PaS4wPtA2v5p5CrBMzupp2sUf3fyf+8T6l1pnVvPjVM0Ys6dxPaN7Ovk9TycG0dtI2BIvtt7VyRq8BUn7JfxukWdant4xZx/8b/Xdn2I227IxNmX/Nmtbrbq6/KmVI+iN+7f3OWOveRjBi4YoS//f4Ycltj9WW++ovNV+RJt+t5W+XsZR0+rjrXA2hIyDeA4wSETon2zdBvzvXKMs5nmVNddhhi5BjXG2f0UPU2IRckxB+6Oa0IW2tqfFcP+3mcCN+4SKEEYnYCIzEy/Yd4R7lVwWyxaKSuypI3KTd6pF4BdkOtoMeKrmwRog/gZ31n6Tz1Tp6fKTAS4+RON56TrgIto/DvtaI3fAu3ebCCq4JSpmt1FC2QzmpvWgmx6yhRgJ3muLi3c4+IQC9m0sZ4KVS+XQ9cQeTNS86zKJ850KneRKJZjiVewWJN87Yz+VqFmNWn1reVPCoLkcMmjtdRxVQa20PIqf+YDDDj9KdEpww5UiHGZnmxNIU1dAEH//LWC5vHV601d20NmSTWbdpowJpnwA9llI6VdLxXAVM0v20ZsziHcuZBxKaU6TCe/5Oxg+hHmxr0NxhR7cgND7Lx6HTLzMM6o3wxyC9tRx95i4xx6M3Mq8oRwkuJBIY8ZDi6bAr5t9l1k9fYWcoF71VycuUBHwvq14hs5BdZt6inVm8k0Jze3moMFtiMcMjOh1++1cq 6h8SyvPy /aqEAPOHhQbYLg+qo3Qs1jJJW+6E7JQhQ5F6HL4XHC10J7qBPH5u5B9hvH1NR9XCBt9ledAZls5b9xslN+RLloNdJvBAHTbQgj4G1f77tRjc39zZuxQsxkV5iILob8xbrPoFu X-Bogosity: Ham, tests=bogofilter, spamicity=0.000028, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Computers are bad at division. We currently decide the best zspage chain size (max number of physical pages per-zspage) by looking at a `used percentage` value. This is not enough as we lose precision during usage percentage calculations For example, let's look at size class 208: pages per zspage wasted bytes used% 1 144 96 2 80 99 3 16 99 4 160 99 Current algorithm will select 2 page per zspage configuration, as it's the first one to reach 99%. However, 3 pages per zspage waste less memory. Change algorithm and select zspage configuration that has lowest wasted value. Signed-off-by: Sergey Senozhatsky Acked-by: Minchan Kim --- mm/zsmalloc.c | 56 +++++++++++++++++---------------------------------- 1 file changed, 19 insertions(+), 37 deletions(-) diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c index 6aafacd664fc..effe10fe76e9 100644 --- a/mm/zsmalloc.c +++ b/mm/zsmalloc.c @@ -802,42 +802,6 @@ static enum fullness_group fix_fullness_group(struct size_class *class, return newfg; } -/* - * We have to decide on how many pages to link together - * to form a zspage for each size class. This is important - * to reduce wastage due to unusable space left at end of - * each zspage which is given as: - * wastage = Zp % class_size - * usage = Zp - wastage - * where Zp = zspage size = k * PAGE_SIZE where k = 1, 2, ... - * - * For example, for size class of 3/8 * PAGE_SIZE, we should - * link together 3 PAGE_SIZE sized pages to form a zspage - * since then we can perfectly fit in 8 such objects. - */ -static int get_pages_per_zspage(int class_size) -{ - int i, max_usedpc = 0; - /* zspage order which gives maximum used size per KB */ - int max_usedpc_order = 1; - - for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) { - int zspage_size; - int waste, usedpc; - - zspage_size = i * PAGE_SIZE; - waste = zspage_size % class_size; - usedpc = (zspage_size - waste) * 100 / zspage_size; - - if (usedpc > max_usedpc) { - max_usedpc = usedpc; - max_usedpc_order = i; - } - } - - return max_usedpc_order; -} - static struct zspage *get_zspage(struct page *page) { struct zspage *zspage = (struct zspage *)page_private(page); @@ -2318,6 +2282,24 @@ static int zs_register_shrinker(struct zs_pool *pool) pool->name); } +static int calculate_zspage_chain_size(int class_size) +{ + int i, min_waste = INT_MAX; + int chain_size = 1; + + for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) { + int waste; + + waste = (i * PAGE_SIZE) % class_size; + if (waste < min_waste) { + min_waste = waste; + chain_size = i; + } + } + + return chain_size; +} + /** * zs_create_pool - Creates an allocation pool to work from. * @name: pool name to be created @@ -2362,7 +2344,7 @@ struct zs_pool *zs_create_pool(const char *name) size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA; if (size > ZS_MAX_ALLOC_SIZE) size = ZS_MAX_ALLOC_SIZE; - pages_per_zspage = get_pages_per_zspage(size); + pages_per_zspage = calculate_zspage_chain_size(size); objs_per_zspage = pages_per_zspage * PAGE_SIZE / size; /*