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 A8A92C00A5A for ; Wed, 18 Jan 2023 00:52:26 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2506D6B0072; Tue, 17 Jan 2023 19:52:26 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 200AB6B0074; Tue, 17 Jan 2023 19:52:26 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0CA016B0075; Tue, 17 Jan 2023 19:52:26 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id F2AC26B0072 for ; Tue, 17 Jan 2023 19:52:25 -0500 (EST) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id D115A80795 for ; Wed, 18 Jan 2023 00:52:25 +0000 (UTC) X-FDA: 80366093850.13.9C09B52 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) by imf11.hostedemail.com (Postfix) with ESMTP id 301C140005 for ; Wed, 18 Jan 2023 00:52:22 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=Eev0f7aY; spf=pass (imf11.hostedemail.com: domain of senozhatsky@chromium.org designates 209.85.214.169 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=1674003143; 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=nkttQsu9CYNbqVs+SWUxgP6kf/grlmJh2/+ItE14A1E=; b=xwp8/je+Mmqb8QnaWhOxaOcJBEo9D83PrAVo+i8D2FNnmmPtE5j3vnRGITGZjQK5cYkwrs bdFos5hewqU8udkc/bcCtAah2phAQn8EBEwk/wN8WpjeCSBlFOYQ3j5cX/TuRyxXFhxSBL shjILuRMZ3Vu8Adu8gXuY+RZ8GKtC34= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=Eev0f7aY; spf=pass (imf11.hostedemail.com: domain of senozhatsky@chromium.org designates 209.85.214.169 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=1674003143; a=rsa-sha256; cv=none; b=pBYvFRnoaX90uLK4xd3b7qw+god1xCl6RHWmCio7mooO+mAtCrjTJzVGDxcmVZYy+cIBON tk70ZqTwJ27zcmQOp6O3xgwSLcFw/4Apajw+WaRelkJ5K+3hArl2GIXvnR2vFKda2AOdKM v8z+t1vwJaOI4RGih7OmOFI24yLow6E= Received: by mail-pl1-f169.google.com with SMTP id p24so35278835plw.11 for ; Tue, 17 Jan 2023 16:52:22 -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=nkttQsu9CYNbqVs+SWUxgP6kf/grlmJh2/+ItE14A1E=; b=Eev0f7aYKnrE4GRG70azP9o2tu74O+ZYXgQ9BucWkBQ5FM/5i2gw0n6a0ytPEDUY34 NqCPhdY234pdbdl4KdLymrKkyHnTuyOC86MzD6DdZt33oz5vpXX+EX/zKeRe6sWnT8ce vxnYh7s6VkjLzd/SF89wzvvgAShJ9gBGQOGmw= 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=nkttQsu9CYNbqVs+SWUxgP6kf/grlmJh2/+ItE14A1E=; b=vRfv4heEph1bAtEduTk6ROL3QMFiRzBaS+ajRk/2nqDKOzCyhCXo/XeGV+5blKVOtV TY0oiwLvEHeGP93P3lgrYfAL3UEvGlA4BKxplFScknDxITHHhW68EK1HndrWOKVL7jjO nr74bMHCb8J/d9DqbOGaF/jucs+qCVDX76qWKmwDgZjmOGeqTTbQKPf692eHvxJEpAwC lAJZ0TBx0Q0L+Rm8vIdXy7/bWgi8lt9QyA+KCJ8pzBnodPRiS97L08I6zSZjuGBKE4ab dotV+wrCP1sRCVxOtrMT/nBofa+LDBNu/mQUgYZ6rzKTK7cQlpqoWEtKS5v9TXPBnF5Z EvFg== X-Gm-Message-State: AFqh2kpsdb8mlUyqRp+L+67e0XxME7hmX9fDT5TmwYMAZhmoy0eGgNpK CPBTwC9hwRpsb7RGVny1vh8SVg== X-Google-Smtp-Source: AMrXdXsY7AyOsWXIqG+pfml6Gremcjag/qdnrV8bvDCBrr5vs4Og1jMyl/Drqe0slS2JWAsgBo6Y/A== X-Received: by 2002:a05:6a20:6f06:b0:ad:5cde:8f05 with SMTP id gt6-20020a056a206f0600b000ad5cde8f05mr4157965pzb.37.1674003142135; Tue, 17 Jan 2023 16:52:22 -0800 (PST) Received: from tigerii.tok.corp.google.com ([2401:fa00:8f:203:10f3:73a5:7e44:adbf]) by smtp.gmail.com with ESMTPSA id u10-20020a17090341ca00b00192f4fbdeb5sm8351461ple.102.2023.01.17.16.52.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 17 Jan 2023 16:52:21 -0800 (PST) From: Sergey Senozhatsky To: Andrew Morton , Minchan Kim Cc: Mike Kravetz , linux-kernel@vger.kernel.org, linux-mm@kvack.org, Sergey Senozhatsky Subject: [PATCHv3 1/4] zsmalloc: rework zspage chain size selection Date: Wed, 18 Jan 2023 09:52:07 +0900 Message-Id: <20230118005210.2814763-2-senozhatsky@chromium.org> X-Mailer: git-send-email 2.39.0.314.g84b9a713c41-goog In-Reply-To: <20230118005210.2814763-1-senozhatsky@chromium.org> References: <20230118005210.2814763-1-senozhatsky@chromium.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 301C140005 X-Stat-Signature: 6hno55n6d6epojoxkqz17pg4ttzi4kaz X-HE-Tag: 1674003142-544156 X-HE-Meta: U2FsdGVkX19grTEuFTpE65w+rpVjVvuh9ypc8HeJLpQrFrTFGexdVdBIqp6DpCsSVHljQ8kj+2JU3QCwnieKxdgo7+g1PqW7araQ7DwQf/rFi968BCTrtamYXBCVCaihjx7OUL36pcLdzsvLQuJCC+V181tUuQP3MqUOSmyY4djGGEqlc5xH5Eky91117tKbdZn6BQ+8NZIkHPovL9qOErs+0WbsVZ1CJ3rRTZL60CWZGNX8cSA4glx0sMH+93+ycCRE3hlW6uNKMi0SgQKjekRSXkZlxeBhwKZCNlXC/LyDtMwscOPVSRca6lO8YpgNsK3p1Ktnv5nFG56omBQKq05VeAsI/8I7j96fWDq528e18eXoKqVPHMcX8Bf4/W8P9TMO3Pl36kv/LH4HrFrvhRgbcAcJCOeGJp5mzH9hlvVsLo2nJ/Y2NSi+RV14SLYL2IJA31CT9iI3twj5HLmvaZA/jnRu+OHOaITn52gvMlCCZht5sVJMVBF3sTyZy+vsLp49bnDzp4FLWMX3uNzq5D8FUG1+bMhANR6xVQKXHDaVx6YV8Vvfs83S4oSRFliOf7DrYVwb1UmleUB9SdhLLaIwrOtAcjqcXVzFFXNRiVPDZG+FpFS45pk82AR757n6B1W0YKCvm1bsVSBEVZ1HOBDL7IW/voIsjNsuFeKfMWpRA0BV4z8n1Y/F7Mcuvn1/bC/bW8AmX5kd6cA52pfXou/aJLROKBFHbcJ4e857FJlEji8SKW4COLFpRj8qKvl/NCyuFQkqhkClDkcafBtcVSIaS07YbSRDaiSshAdsRct6tGJhlGEbdGR3YY7FmE25m7jGxMbTC9pTumSw+BaoLfQ3HEUVF16mXMAJLuzetKjMDbbc40JNrje8jK4MiDSyk0ZwIK7fzcjvt7pwsV3IpRYbxUrY+GRpnAfgF6lpi2SC+oOTMOBVoNouxDNFPFS2FsED8fTp3Mncf9Mczl1 mhsvAVbw FnWqspcgh4l31Z1nXUi/1blkw+DxyR+gvYuq4RbxB/Idg97PSJXOHqQJMlGtv2hLpmXw/rp37y4vafNVZ8wWF2clLaivpKUmCzdZZhKI6GjSsuR2YvNhcEUlHkgf1d9D2Jny/ X-Bogosity: Ham, tests=bogofilter, spamicity=0.003111, 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; /* -- 2.39.0.314.g84b9a713c41-goog