From patchwork Mon Nov 13 10:52:30 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 164406 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b909:0:b0:403:3b70:6f57 with SMTP id t9csp1120636vqg; Mon, 13 Nov 2023 02:54:13 -0800 (PST) X-Google-Smtp-Source: AGHT+IGL2COm5gzFXPG8tOf52O8LMZXu7VlceDFJTAva/Bd5HUb1+dqYqqPI01GPvD/1oyK9Q6Cb X-Received: by 2002:a62:e418:0:b0:6be:23dd:d62c with SMTP id r24-20020a62e418000000b006be23ddd62cmr6450234pfh.2.1699872853039; Mon, 13 Nov 2023 02:54:13 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1699872853; cv=none; d=google.com; s=arc-20160816; b=WOUSb/5UDtAiexPJBswDgM0Jywze3x3MLN3WJeCs8PT6yJbYX4Z2bN9s4GPIQby9ne p7lpfTN+YMyv6Y0U/yM/ePMYMlJZrhLSg6FsVuYzNPYaDhqiJuxDhSxszKvJXwgnJrBr Vro4Q+QKDrPjzrL6bWWwBxT1HUzkLWVVPktEsD4VpkMfl+aBph1FSU8C+ivLTM6cVbkL WpluYGtbVH7LJRlc80hjUYtW+rQkn7ZAI7iuvMQk3nXPD63ZbWsthja4Jagll7E4WtDi bHifVHv3044Ahy9DHhQlHDwwkHfIMlMWf4hYADFf20zMAJytIIgBdHmdsLeo03d8G8Ur 27WA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:dkim-signature; bh=vmgYzX9Gh/HqVCtLQcjUqo5x4uBX58pquJxOOKimeCw=; fh=bwsiIJU4ZySHCYgdbJrawkDYkx7XsqbTjYxIEnch01E=; b=YwEhkgtSKdfrmEvJVV/kHnLhrlEtmTNbG1m1PumQANPZj4+1m/vW0BLgftH/+pni6w ZUqmzoDi8kFGtwZC5FHx76RDBQ5K2Y2ZNaeRW6LgOy8xMkUwMCEl+i+Zx2maPtqc+3Xs 1q0IQQ3+qCvHebiFQIqdr/5tDcL6bqpRLX2qPwzMj+fistW65h3FKi1QVjhB8vtXcu6h jCqZ7jAV9vrcBjIGXSWtDDWQ0sRIY5q4ukb5PGZ6EFjsPjp+zSDJCjGAzVpnEW4O2q9h F6J75YsYkwIlVhHqHTDRkLdveyBPVBU9HzpcuPcjaUXltZ2kP5fFpN3Vs325uC2phZQh dPLQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=2QoMYcIe; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from groat.vger.email (groat.vger.email. [23.128.96.35]) by mx.google.com with ESMTPS id m12-20020a656a0c000000b005acb88d8c15si6023245pgu.386.2023.11.13.02.54.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 13 Nov 2023 02:54:13 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) client-ip=23.128.96.35; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=2QoMYcIe; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by groat.vger.email (Postfix) with ESMTP id 0B0C9806036A; Mon, 13 Nov 2023 02:54:09 -0800 (PST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.11 at groat.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229817AbjKMKws (ORCPT + 29 others); Mon, 13 Nov 2023 05:52:48 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:45060 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229470AbjKMKwp (ORCPT ); Mon, 13 Nov 2023 05:52:45 -0500 Received: from mail-yw1-x114a.google.com (mail-yw1-x114a.google.com [IPv6:2607:f8b0:4864:20::114a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 914E0CB for ; Mon, 13 Nov 2023 02:52:40 -0800 (PST) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-5a828bdcfbaso59113527b3.2 for ; Mon, 13 Nov 2023 02:52:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1699872760; x=1700477560; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=vmgYzX9Gh/HqVCtLQcjUqo5x4uBX58pquJxOOKimeCw=; b=2QoMYcIeBLrGU61miMo3OCQNSU8ZCwdBU2AEd6KxVk6edUaaPBYwPtFXl4WAjdPKXA A6AMLD7waDlJzz6DEBgRLXnP0ELxk+Mb3sszIAqt3drpufc6yiI+BpOpx0M2x2LKW5ua bbwvFqvK6k2TwY+OmkgIJIDbawp0v6+0U5hJrogSIMblVAOr17UMr+t1IPtarVr/ZaLB 4UaMvnGOAvJoDbHhVBQCdScx5X7kyBxgDJeKuq6AG13CgAL1cGGWPT9LYnvOT/kDas9V 3X6sIlyWo1fvxulMAyC8RTuz/t4p2Z0fMqD+UlVCyz0vsyxizvFxK0c6YaM4RAn4WRsE nj/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699872760; x=1700477560; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=vmgYzX9Gh/HqVCtLQcjUqo5x4uBX58pquJxOOKimeCw=; b=OcyGAekz0c6e2jMyh1soiye+1CW0WInjbuvdZYE4GI4d1UgwJL0lQf8PXSIZaNRpTz 4ieg7K9gdewJ4gnniSGpvXUvksEEfKRe0MWdz50LykNKu3q4LtVjeaqMMf4AhsDVvylE xFm2/vry6IwPtvDO999+ziqVmuqNmJubaQ+eaSBi5KMU5hXEr8r63H6pYcxyNKA76J/0 qERVIF2rVoy8R4vBkB6xR7T4mHWjdbcAU+GXiyHzzmff9QKlPM0iMbaNC55L/2lyknPQ brOUgzkmI3offVQs6EmraC31rVzxh4W0fdC/9+7JA3T4WT0614yLpbviH0c3lU9cjX94 rLaA== X-Gm-Message-State: AOJu0YxZZ90sc2zVcvEk8S1zpPp7weVwqmchkGWFbPabX6WZZq30s4VO 8LUavdOnZmgAoqoMM5c69OcZWuiYh3I= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:be07:845d:4221:b15e]) (user=glider job=sendgmr) by 2002:a05:6902:182:b0:d9a:ec95:9687 with SMTP id t2-20020a056902018200b00d9aec959687mr154648ybh.11.1699872759801; Mon, 13 Nov 2023 02:52:39 -0800 (PST) Date: Mon, 13 Nov 2023 11:52:30 +0100 In-Reply-To: <20231113105234.32058-1-glider@google.com> Mime-Version: 1.0 References: <20231113105234.32058-1-glider@google.com> X-Mailer: git-send-email 2.42.0.869.gea05f2083d-goog Message-ID: <20231113105234.32058-2-glider@google.com> Subject: [PATCH v9 1/4] arm64: mte: implement CONFIG_ARM64_MTE_COMP From: Alexander Potapenko To: glider@google.com, catalin.marinas@arm.com, will@kernel.org, pcc@google.com, andreyknvl@gmail.com, andriy.shevchenko@linux.intel.com, aleksander.lobakin@intel.com, linux@rasmusvillemoes.dk, yury.norov@gmail.com, alexandru.elisei@arm.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com, syednwaris@gmail.com, william.gray@linaro.org X-Spam-Status: No, score=-8.4 required=5.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE, USER_IN_DEF_DKIM_WL autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on groat.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (groat.vger.email [0.0.0.0]); Mon, 13 Nov 2023 02:54:09 -0800 (PST) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782445876798154260 X-GMAIL-MSGID: 1782445876798154260 The config implements the algorithm compressing memory tags for ARM MTE during swapping. The algorithm is based on RLE and specifically targets buffers of tags corresponding to a single page. In many cases a buffer can be compressed into 63 bits, making it possible to store it without additional memory allocation. Suggested-by: Evgenii Stepanov Signed-off-by: Alexander Potapenko Acked-by: Catalin Marinas --- v8: - As suggested by Catalin Marinas, only compress tags if they can be stored inline. This simplifies the code drastically. - Update the documentation. - Split off patches introducing bitmap_read()/bitmap_write(). v6: - shuffle bits in inline handles so that they can't be confused with canonical pointers; - use kmem_cache_zalloc() to allocate compressed storage - correctly handle range size overflow - minor documentation fixes, clarify the special cases v5: - make code PAGE_SIZE-agnostic, remove hardcoded constants, updated the docs - implement debugfs interface - Address comments by Andy Shevchenko: - update description of mtecomp.c - remove redundant assignments, simplify mte_tags_to_ranges() - various code simplifications - introduce mtecomp.h - add :export: to Documentation/arch/arm64/mte-tag-compression.rst v4: - Addressed comments by Andy Shevchenko: - expanded "MTE" to "Memory Tagging Extension" in Kconfig - fixed kernel-doc comments, moved them to C source - changed variables to unsigned where applicable - some code simplifications, fewer unnecessary assignments - added the mte_largest_idx_bits() helper - added namespace prefixes to all functions - added missing headers (but removed bits.h) - Addressed comments by Yury Norov: - removed test-only functions from mtecomp.h - dropped the algoritm name (all functions are now prefixed with "mte") - added more comments - got rid of MTE_RANGES_INLINE - renamed bitmap_{get,set}_value() to bitmap_{read,write}() - moved the big comment explaining the algorithm to Documentation/arch/arm64/mte-tag-compression.rst, expanded it, add a link to it from Documentation/arch/arm64/index.rst - removed hardcoded ranges from mte_alloc_size()/mte_size_to_ranges() v3: - Addressed comments by Andy Shevchenko: - use bitmap_{set,get}_value() writte by Syed Nayyar Waris - switched to unsigned long everywhere (fewer casts) - simplified the code, removed redundant checks - dropped ea0_compress_inline() - added bit size constants and helpers to access the bitmap - explicitly initialize all compressed sizes in ea0_compress_to_buf() - initialize all handle bits v2: - as suggested by Yury Norov, switched from struct bitq (which is not needed anymore) to - add missing symbol exports --- Documentation/arch/arm64/index.rst | 1 + .../arch/arm64/mte-tag-compression.rst | 154 +++++++++++ arch/arm64/Kconfig | 11 + arch/arm64/include/asm/mtecomp.h | 39 +++ arch/arm64/mm/Makefile | 1 + arch/arm64/mm/mtecomp.c | 257 ++++++++++++++++++ arch/arm64/mm/mtecomp.h | 12 + 7 files changed, 475 insertions(+) create mode 100644 Documentation/arch/arm64/mte-tag-compression.rst create mode 100644 arch/arm64/include/asm/mtecomp.h create mode 100644 arch/arm64/mm/mtecomp.c create mode 100644 arch/arm64/mm/mtecomp.h diff --git a/Documentation/arch/arm64/index.rst b/Documentation/arch/arm64/index.rst index d08e924204bf1..bf6c1583233a9 100644 --- a/Documentation/arch/arm64/index.rst +++ b/Documentation/arch/arm64/index.rst @@ -19,6 +19,7 @@ ARM64 Architecture legacy_instructions memory memory-tagging-extension + mte-tag-compression perf pointer-authentication ptdump diff --git a/Documentation/arch/arm64/mte-tag-compression.rst b/Documentation/arch/arm64/mte-tag-compression.rst new file mode 100644 index 0000000000000..8fe6b51a9db6d --- /dev/null +++ b/Documentation/arch/arm64/mte-tag-compression.rst @@ -0,0 +1,154 @@ +.. SPDX-License-Identifier: GPL-2.0 + +================================================== +Tag Compression for Memory Tagging Extension (MTE) +================================================== + +This document describes the algorithm used to compress memory tags used by the +ARM Memory Tagging Extension (MTE). + +Introduction +============ + +MTE assigns tags to memory pages: for 4K pages those tags occupy 128 bytes +(256 4-bit tags each corresponding to a 16-byte MTE granule), for 16K pages - +512 bytes, for 64K pages - 2048 bytes. By default, MTE carves out 3.125% (1/16) +of the available physical memory to store the tags. + +When MTE pages are saved to swap, their tags need to be stored in the kernel +memory. If the system swap is used heavily, these tags may take a substantial +portion of the physical memory. To reduce memory waste, ``CONFIG_ARM64_MTE_COMP`` +allows the kernel to store the tags in compressed form. + +Implementation details +====================== + +The algorithm attempts to compress an array of ``MTE_PAGE_TAG_STORAGE`` +tag bytes into a byte sequence that can be stored in an 8-byte pointer. If that +is not possible, the data is stored uncompressed. + +Tag manipulation and storage +---------------------------- + +Tags for swapped pages are stored in an XArray that maps swap entries to 63-bit +values (see ``arch/arm64/mm/mteswap.c``). Bit 0 of these values indicates how +their contents should be treated: + + - 0: value is a pointer to an uncompressed buffer allocated with kmalloc() + (always the case if ``CONFIG_ARM64_MTE_COMP=n``) with the highest bit set + to 0; + - 1: value contains compressed data. + +``arch/arm64/include/asm/mtecomp.h`` declares the following functions that +manipulate with tags: + +- mte_compress() - compresses the given ``MTE_PAGE_TAG_STORAGE``-byte ``tags`` + buffer into a pointer; +- mte_decompress() - decompresses the tags from a pointer; +- mte_is_compressed() - returns ``true`` iff the pointer passed to it should be + treated as compressed data. + +Tag compression +--------------- + +The compression algorithm is a variation of RLE (run-length encoding) and works +as follows (we will be considering 4K pages and 128-byte tag buffers, but the +same approach scales to 16K and 64K pages): + +1. The input array of 128 (``MTE_PAGE_TAG_STORAGE``) bytes is transformed into + tag ranges (two arrays: ``r_tags[]`` containing tag values and ``r_sizes[]`` + containing range lengths) by mte_tags_to_ranges(). Note that + ``r_sizes[]`` sums up to 256 (``MTE_GRANULES_PER_PAGE``). + + If ``r_sizes[]`` consists of a single element + (``{ MTE_GRANULES_PER_PAGE }``), the corresponding range is split into two + halves, i.e.:: + + r_sizes_new[2] = { MTE_GRANULES_PER_PAGE/2, MTE_GRANULES_PER_PAGE/2 }; + r_tags_new[2] = { r_tags[0], r_tags[0] }; + +2. The number of the largest element of ``r_sizes[]`` is stored in + ``largest_idx``. The element itself is thrown away from ``r_sizes[]``, + because it can be reconstructed from the sum of the remaining elements. Note + that now none of the remaining ``r_sizes[]`` elements exceeds + ``MTE_GRANULES_PER_PAGE/2``. + +3. If the number ``N`` of ranges does not exceed ``6``, the ranges can be + compressed into 64 bits. This is done by storing the following values packed + into the pointer (``i`` means a ````-bit unsigned integer) + treated as a bitmap (see ``include/linux/bitmap.h``):: + + bit 0 : (always 1) : i1 + bits 1-3 : largest_idx : i3 + bits 4-27 : r_tags[0..5] : i4 x 6 + bits 28-62 : r_sizes[0..4] : i7 x 5 + bit 63 : (always 0) : i1 + + If N is less than 6, ``r_tags`` and ``r_sizes`` are padded up with zero + values. The unused bits in the pointer, including bit 63, are also set to 0, + so the compressed data can be stored in XArray. + + Range size of ``MTE_GRANULES_PER_PAGE/2`` (at most one) does not fit into + i7 and will be written as 0. This case is handled separately by the + decompressing procedure. + +Tag decompression +----------------- + +The decompression algorithm performs the steps below. + +1. Read the lowest bit of the data from the input buffer and check that it is 1, + otherwise bail out. + +2. Read ``largest_idx``, ``r_tags[]`` and ``r_sizes[]`` from the + input buffer. + + If ``largest_idx`` is zero, and all ``r_sizes[]`` are zero, set + ``r_sizes[0] = MTE_GRANULES_PER_PAGE/2``. + + Calculate the removed largest element of ``r_sizes[]`` as + ``largest = 256 - sum(r_sizes)`` and insert it into ``r_sizes`` at + position ``largest_idx``. + +6. For each ``r_sizes[i] > 0``, add a 4-bit value ``r_tags[i]`` to the output + buffer ``r_sizes[i]`` times. + + +Why these numbers? +------------------ + +To be able to reconstruct ``N`` tag ranges from the compressed data, we need to +store the indicator bit together with ``largest_idx``, ``r_tags[N]``, and +``r_sizes[N-1]`` in 63 bits. +Knowing that the sizes do not exceed ``MTE_PAGE_TAG_STORAGE``, each of them can be +packed into ``S = ilog2(MTE_PAGE_TAG_STORAGE)`` bits, whereas a single tag occupies +4 bits. + +It is evident that the number of ranges that can be stored in 63 bits is +strictly less than 8, therefore we only need 3 bits to store ``largest_idx``. + +The maximum values of ``N`` so that the number ``1 + 3 + N * 4 + (N-1) * S`` of +storage bits does not exceed 63, are shown in the table below:: + + +-----------+-----------------+----+---+-------------------+ + | Page size | Tag buffer size | S | N | Storage bits | + +-----------+-----------------+----+---+-------------------+ + | 4 KB | 128 B | 7 | 6 | 63 = 1+3+6*4+5*7 | + | 16 KB | 512 B | 9 | 5 | 60 = 1+3+5*4+4*9 | + | 64 KB | 2048 B | 11 | 4 | 53 = 1+3+4*4+3*11 | + +-----------+-----------------+----+---+-------------------+ + +Note +---- + +Tag compression and decompression implicitly rely on the fixed MTE tag size +(4 bits) and number of tags per page. Should these values change, the algorithm +may need to be revised. + + +Programming Interface +===================== + + .. kernel-doc:: arch/arm64/include/asm/mtecomp.h + .. kernel-doc:: arch/arm64/mm/mtecomp.c + :export: diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig index 78f20e6327120..c2fbe8e492e00 100644 --- a/arch/arm64/Kconfig +++ b/arch/arm64/Kconfig @@ -2073,6 +2073,17 @@ config ARM64_EPAN if the cpu does not implement the feature. endmenu # "ARMv8.7 architectural features" +config ARM64_MTE_COMP + bool "Tag compression for ARM64 Memory Tagging Extension" + default y + depends on ARM64_MTE + help + Enable tag compression support for ARM64 Memory Tagging Extension. + + Tag buffers corresponding to swapped RAM pages are compressed using + RLE to conserve heap memory. In the common case compressed tags + occupy 2.5x less memory. + config ARM64_SVE bool "ARM Scalable Vector Extension support" default y diff --git a/arch/arm64/include/asm/mtecomp.h b/arch/arm64/include/asm/mtecomp.h new file mode 100644 index 0000000000000..b9a3a921a38d4 --- /dev/null +++ b/arch/arm64/include/asm/mtecomp.h @@ -0,0 +1,39 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#ifndef __ASM_MTECOMP_H +#define __ASM_MTECOMP_H + +#include + +/** + * mte_is_compressed() - check if the supplied pointer contains compressed tags. + * @ptr: pointer returned by kmalloc() or mte_compress(). + * + * Returns: true iff bit 0 of @ptr is 1, which is only possible if @ptr was + * returned by mte_is_compressed(). + */ +static inline bool mte_is_compressed(void *ptr) +{ + return ((unsigned long)ptr & 1); +} + +#if defined(CONFIG_ARM64_MTE_COMP) + +void *mte_compress(u8 *tags); +bool mte_decompress(void *handle, u8 *tags); + +#else + +static inline void *mte_compress(u8 *tags) +{ + return NULL; +} + +static inline bool mte_decompress(void *data, u8 *tags) +{ + return false; +} + +#endif // CONFIG_ARM64_MTE_COMP + +#endif // __ASM_MTECOMP_H diff --git a/arch/arm64/mm/Makefile b/arch/arm64/mm/Makefile index dbd1bc95967d0..46778f6dd83c2 100644 --- a/arch/arm64/mm/Makefile +++ b/arch/arm64/mm/Makefile @@ -10,6 +10,7 @@ obj-$(CONFIG_TRANS_TABLE) += trans_pgd.o obj-$(CONFIG_TRANS_TABLE) += trans_pgd-asm.o obj-$(CONFIG_DEBUG_VIRTUAL) += physaddr.o obj-$(CONFIG_ARM64_MTE) += mteswap.o +obj-$(CONFIG_ARM64_MTE_COMP) += mtecomp.o KASAN_SANITIZE_physaddr.o += n obj-$(CONFIG_KASAN) += kasan_init.o diff --git a/arch/arm64/mm/mtecomp.c b/arch/arm64/mm/mtecomp.c new file mode 100644 index 0000000000000..c948921525030 --- /dev/null +++ b/arch/arm64/mm/mtecomp.c @@ -0,0 +1,257 @@ +// SPDX-License-Identifier: GPL-2.0-only + +/* + * MTE tag compression algorithm. + * See Documentation/arch/arm64/mte-tag-compression.rst for more details. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#include "mtecomp.h" + +#define MTE_BITS_PER_LARGEST_IDX 3 +/* Range size cannot exceed MTE_GRANULES_PER_PAGE / 2. */ +#define MTE_BITS_PER_SIZE (ilog2(MTE_GRANULES_PER_PAGE) - 1) + +/* + * See Documentation/arch/arm64/mte-tag-compression.rst for details on how the + * maximum number of ranges is calculated. + */ +#if defined(CONFIG_ARM64_4K_PAGES) +#define MTE_MAX_RANGES 6 +#elif defined(CONFIG_ARM64_16K_PAGES) +#define MTE_MAX_RANGES 5 +#else +#define MTE_MAX_RANGES 4 +#endif + +/** + * mte_tags_to_ranges() - break @tags into arrays of tag ranges. + * @tags: MTE_GRANULES_PER_PAGE-byte array containing MTE tags. + * @out_tags: u8 array to store the tag of every range. + * @out_sizes: unsigned short array to store the size of every range. + * @out_len: length of @out_tags and @out_sizes (output parameter, initially + * equal to lengths of out_tags[] and out_sizes[]). + * + * This function is exported for testing purposes. + */ +void mte_tags_to_ranges(u8 *tags, u8 *out_tags, unsigned short *out_sizes, + size_t *out_len) +{ + u8 prev_tag = tags[0] / 16; /* First tag in the array. */ + unsigned int cur_idx = 0, i, j; + u8 cur_tag; + + memset(out_tags, 0, array_size(*out_len, sizeof(*out_tags))); + memset(out_sizes, 0, array_size(*out_len, sizeof(*out_sizes))); + + out_tags[cur_idx] = prev_tag; + for (i = 0; i < MTE_GRANULES_PER_PAGE; i++) { + j = i % 2; + cur_tag = j ? (tags[i / 2] % 16) : (tags[i / 2] / 16); + if (cur_tag == prev_tag) { + out_sizes[cur_idx]++; + } else { + cur_idx++; + prev_tag = cur_tag; + out_tags[cur_idx] = prev_tag; + out_sizes[cur_idx] = 1; + } + } + *out_len = cur_idx + 1; +} +EXPORT_SYMBOL_NS(mte_tags_to_ranges, MTECOMP); + +/** + * mte_ranges_to_tags() - fill @tags using given tag ranges. + * @r_tags: u8[] containing the tag of every range. + * @r_sizes: unsigned short[] containing the size of every range. + * @r_len: length of @r_tags and @r_sizes. + * @tags: MTE_GRANULES_PER_PAGE-byte array to write the tags to. + * + * This function is exported for testing purposes. + */ +void mte_ranges_to_tags(u8 *r_tags, unsigned short *r_sizes, size_t r_len, + u8 *tags) +{ + unsigned int i, j, pos = 0; + u8 prev; + + for (i = 0; i < r_len; i++) { + for (j = 0; j < r_sizes[i]; j++) { + if (pos % 2) + tags[pos / 2] = (prev << 4) | r_tags[i]; + else + prev = r_tags[i]; + pos++; + } + } +} +EXPORT_SYMBOL_NS(mte_ranges_to_tags, MTECOMP); + +static void mte_bitmap_write(unsigned long *bitmap, unsigned long value, + unsigned long *pos, unsigned long bits) +{ + bitmap_write(bitmap, value, *pos, bits); + *pos += bits; +} + +/* Compress ranges into an unsigned long. */ +static void mte_compress_to_ulong(size_t len, u8 *tags, unsigned short *sizes, + unsigned long *result) +{ + unsigned long bit_pos = 0; + unsigned int largest_idx, i; + unsigned short largest = 0; + + for (i = 0; i < len; i++) { + if (sizes[i] > largest) { + largest = sizes[i]; + largest_idx = i; + } + } + /* Bit 1 in position 0 indicates compressed data. */ + mte_bitmap_write(result, 1, &bit_pos, 1); + mte_bitmap_write(result, largest_idx, &bit_pos, + MTE_BITS_PER_LARGEST_IDX); + for (i = 0; i < len; i++) + mte_bitmap_write(result, tags[i], &bit_pos, MTE_TAG_SIZE); + if (len == 1) { + /* + * We are compressing MTE_GRANULES_PER_PAGE of identical tags. + * Split it into two ranges containing + * MTE_GRANULES_PER_PAGE / 2 tags, so that it falls into the + * special case described below. + */ + mte_bitmap_write(result, tags[0], &bit_pos, MTE_TAG_SIZE); + i = 2; + } else { + i = len; + } + for (; i < MTE_MAX_RANGES; i++) + mte_bitmap_write(result, 0, &bit_pos, MTE_TAG_SIZE); + /* + * Most of the time sizes[i] fits into MTE_BITS_PER_SIZE, apart from a + * special case when: + * len = 2; + * sizes = { MTE_GRANULES_PER_PAGE / 2, MTE_GRANULES_PER_PAGE / 2}; + * In this case largest_idx will be set to 0, and the size written to + * the bitmap will be also 0. + */ + for (i = 0; i < len; i++) { + if (i != largest_idx) + mte_bitmap_write(result, sizes[i], &bit_pos, + MTE_BITS_PER_SIZE); + } + for (i = len; i < MTE_MAX_RANGES; i++) + mte_bitmap_write(result, 0, &bit_pos, MTE_BITS_PER_SIZE); +} + +/** + * mte_compress() - compress the given tag array. + * @tags: MTE_GRANULES_PER_PAGE-byte array to read the tags from. + * + * Attempts to compress the user-supplied tag array. + * + * Returns: compressed data or NULL. + */ +void *mte_compress(u8 *tags) +{ + unsigned short *r_sizes; + void *result = NULL; + u8 *r_tags; + size_t r_len; + + r_sizes = kmalloc_array(MTE_GRANULES_PER_PAGE, sizeof(unsigned short), + GFP_KERNEL); + r_tags = kmalloc(MTE_GRANULES_PER_PAGE, GFP_KERNEL); + if (!r_sizes || !r_tags) + goto ret; + r_len = MTE_GRANULES_PER_PAGE; + mte_tags_to_ranges(tags, r_tags, r_sizes, &r_len); + if (r_len <= MTE_MAX_RANGES) + mte_compress_to_ulong(r_len, r_tags, r_sizes, + (unsigned long *)&result); +ret: + kfree(r_tags); + kfree(r_sizes); + return result; +} +EXPORT_SYMBOL_NS(mte_compress, MTECOMP); + +static unsigned long mte_bitmap_read(const unsigned long *bitmap, + unsigned long *pos, unsigned long bits) +{ + unsigned long start = *pos; + + *pos += bits; + return bitmap_read(bitmap, start, bits); +} + +/** + * mte_decompress() - decompress the tag array from the given pointer. + * @data: pointer returned by @mte_compress() + * @tags: MTE_GRANULES_PER_PAGE-byte array to write the tags to. + * + * Reads the compressed data and writes it into the user-supplied tag array. + * + * Returns: true on success, false if the passed data is uncompressed. + */ +bool mte_decompress(void *data, u8 *tags) +{ + unsigned short r_sizes[MTE_MAX_RANGES]; + u8 r_tags[MTE_MAX_RANGES]; + unsigned int largest_idx, i; + unsigned long bit_pos = 0; + unsigned long *bitmap; + unsigned short sum; + size_t max_ranges; + + if (!mte_is_compressed(data)) + return false; + + bitmap = (unsigned long *)&data; + max_ranges = MTE_MAX_RANGES; + /* Skip the leading bit indicating the inline case. */ + mte_bitmap_read(bitmap, &bit_pos, 1); + largest_idx = + mte_bitmap_read(bitmap, &bit_pos, MTE_BITS_PER_LARGEST_IDX); + if (largest_idx >= MTE_MAX_RANGES) + return false; + + for (i = 0; i < max_ranges; i++) + r_tags[i] = mte_bitmap_read(bitmap, &bit_pos, MTE_TAG_SIZE); + for (i = 0, sum = 0; i < max_ranges; i++) { + if (i == largest_idx) + continue; + r_sizes[i] = + mte_bitmap_read(bitmap, &bit_pos, MTE_BITS_PER_SIZE); + /* + * Special case: tag array consists of two ranges of + * `MTE_GRANULES_PER_PAGE / 2` tags. + */ + if ((largest_idx == 0) && (i == 1) && (r_sizes[i] == 0)) + r_sizes[i] = MTE_GRANULES_PER_PAGE / 2; + if (!r_sizes[i]) { + max_ranges = i; + break; + } + sum += r_sizes[i]; + } + if (sum >= MTE_GRANULES_PER_PAGE) + return false; + r_sizes[largest_idx] = MTE_GRANULES_PER_PAGE - sum; + mte_ranges_to_tags(r_tags, r_sizes, max_ranges, tags); + return true; +} +EXPORT_SYMBOL_NS(mte_decompress, MTECOMP); diff --git a/arch/arm64/mm/mtecomp.h b/arch/arm64/mm/mtecomp.h new file mode 100644 index 0000000000000..b94cf0384f2af --- /dev/null +++ b/arch/arm64/mm/mtecomp.h @@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#ifndef ARCH_ARM64_MM_MTECOMP_H_ +#define ARCH_ARM64_MM_MTECOMP_H_ + +/* Functions exported from mtecomp.c for test_mtecomp.c. */ +void mte_tags_to_ranges(u8 *tags, u8 *out_tags, unsigned short *out_sizes, + size_t *out_len); +void mte_ranges_to_tags(u8 *r_tags, unsigned short *r_sizes, size_t r_len, + u8 *tags); + +#endif // ARCH_ARM64_MM_TEST_MTECOMP_H_ From patchwork Mon Nov 13 10:52:31 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 164403 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b909:0:b0:403:3b70:6f57 with SMTP id t9csp1120286vqg; Mon, 13 Nov 2023 02:53:08 -0800 (PST) X-Google-Smtp-Source: AGHT+IERVe/8wg6d6w+dJ+13xiXmbZpar3bq218GNODKUyy18Z03BbRk+jo+ZoTR0/xQ0yk/TyAw X-Received: by 2002:aa7:8548:0:b0:68f:b5a3:5ec6 with SMTP id y8-20020aa78548000000b0068fb5a35ec6mr8463793pfn.0.1699872788279; Mon, 13 Nov 2023 02:53:08 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1699872788; cv=none; d=google.com; s=arc-20160816; b=pTkJJHXPVFWP5F3awYFpxNY+OYK6GxVUnW3DIv1mlBQqrV7ivUcUcnni35TiYaDx8C 2LuOxzK3AJYjSFOHvXRqYky/PYmnbq388pNzoMoEwp4WfZS3gpAqza66Kfkx2jLFL78l OdECYd19Lmf03t+YyIK6YfCthhjTbHscG7TdD5SLRkYriVFLb6+m4a8NLvPhr/Nd/w75 U0wVUItaHhCp779oNkySyTp83uWWJDY4/a3/k5cJBvBVh9bVjSeRQkvlkPFBIbjeaGBM 2fgKbAGNIrOGbvtYhTUTOR6mqsReIdJ2bLzKRPUh0qGDiNVcNliGiX3XjqlpSiPbYgXb tQRQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:dkim-signature; bh=98j1gGliRWu5e7QdmSteXe38vUprZ3Olpboza+EuSHs=; fh=bwsiIJU4ZySHCYgdbJrawkDYkx7XsqbTjYxIEnch01E=; b=FrmUaupPWMz7OpLVzCYarIm+ED+obpB+dknFvNivzevCcZ+OxqGEvi1wXI9gP41gs5 ah+NoPtRdjh5rlChpT4Pc7qX2Le0ORBfnR4ZxA463i0MszgEgFyEA74r5AjpT5uu409N oYHa8XXDEI6TdHgRI+nG/H06BiVQTjMDXpnSaETOwk1iJh/rIN36c/HYFveVjHRJo6b7 mhXUKBR0xO5+3zgnoT9p/HHQYXPzADA53bC8eJEi9cunbY9OvF+n0GcJGIJSYvzT1/4x +Q6yPjD1vbRFa7ZxAhrtKcmB3PK0TnaBZAOvHhmS01LodaIUY+gE7S/dQbiSDNeCIlug 78ug== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=MOK8Qitr; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from snail.vger.email (snail.vger.email. [2620:137:e000::3:7]) by mx.google.com with ESMTPS id u2-20020a056a00158200b0069343bdd500si5774191pfk.319.2023.11.13.02.53.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 13 Nov 2023 02:53:08 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=MOK8Qitr; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by snail.vger.email (Postfix) with ESMTP id 8D6168047789; Mon, 13 Nov 2023 02:53:07 -0800 (PST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.11 at snail.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229960AbjKMKw4 (ORCPT + 29 others); Mon, 13 Nov 2023 05:52:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:45070 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229826AbjKMKws (ORCPT ); Mon, 13 Nov 2023 05:52:48 -0500 Received: from mail-wm1-x349.google.com (mail-wm1-x349.google.com [IPv6:2a00:1450:4864:20::349]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 89647CB for ; Mon, 13 Nov 2023 02:52:44 -0800 (PST) Received: by mail-wm1-x349.google.com with SMTP id 5b1f17b1804b1-4083a670d25so28992825e9.0 for ; Mon, 13 Nov 2023 02:52:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1699872763; x=1700477563; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=98j1gGliRWu5e7QdmSteXe38vUprZ3Olpboza+EuSHs=; b=MOK8Qitrqhey2nK0SKvhAmyoBfPXkpvRuakU5nRJIJIlnRdAP166zRI6x9gRykM59Z skrddQs44r0oDbDwhhXX04FDp69/Vvo2t4Ua4+kJ0Mhgk+arqLMIonIa+y8pdoxngVxP HtKB4U0Dbd0c+2rl7ChuXgjZe99y86zVXXBX7a5HG62S3zWGsNsKBSKMLfHserQHrdgd lUlk3fhJUjO+D4BHcdp/TMn6TWCZDpl4yxLL1z5RFCji38EQmmdVoCpG9RXGf6veWCDx owrY9XiMwit6IZAbr8YrW7bGnG2rkLIhec8X1zTXSylxTWbP0hB2zNUtwLJof4kqNQny v7Cw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699872763; x=1700477563; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=98j1gGliRWu5e7QdmSteXe38vUprZ3Olpboza+EuSHs=; b=lgLra/SIi/2Kn5dTSfFnZ4iWFc9YNYE5+aqk4D7vMVuIio6LzIEF6QxRunjBoZXdsM ZQVCdwjeEVdAH7WJt1F2G8RaBzWarwpBch6yz/FoILjyBuTq+CPq/BIVBKYUoxp8wz4U 6ch6bYLTMr2vIFqOojnIAndLeTiwNyM8Ro6V8pr7AqYIsKGIid8huWMy2kYXB6CS1P5d kj9eMXoihrOu+VRrrJ1cYNZZw8DbOZjzCa0XYPBg2bEqiqlhu8yUj6q3NC1ZmwWgIRrG 9pWqkJAM4Gdr5z2M7DyefwgLnuYNW+B+8nOTaMDa7kVECejlbfP1rlG2ftlQqtO+F8Rn 2VuQ== X-Gm-Message-State: AOJu0YxRThgF3pu/LMkfO8kJoJFHajg0v67tRe2w11g6SGri3QVt1WG7 NeqZiYi25GhhPWucZxS+HOMNl0mO6OE= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:be07:845d:4221:b15e]) (user=glider job=sendgmr) by 2002:adf:f94d:0:b0:32f:7d60:d633 with SMTP id q13-20020adff94d000000b0032f7d60d633mr63631wrr.9.1699872762582; Mon, 13 Nov 2023 02:52:42 -0800 (PST) Date: Mon, 13 Nov 2023 11:52:31 +0100 In-Reply-To: <20231113105234.32058-1-glider@google.com> Mime-Version: 1.0 References: <20231113105234.32058-1-glider@google.com> X-Mailer: git-send-email 2.42.0.869.gea05f2083d-goog Message-ID: <20231113105234.32058-3-glider@google.com> Subject: [PATCH v9 2/4] arm64: mte: add a test for MTE tags compression From: Alexander Potapenko To: glider@google.com, catalin.marinas@arm.com, will@kernel.org, pcc@google.com, andreyknvl@gmail.com, andriy.shevchenko@linux.intel.com, aleksander.lobakin@intel.com, linux@rasmusvillemoes.dk, yury.norov@gmail.com, alexandru.elisei@arm.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com, syednwaris@gmail.com, william.gray@linaro.org X-Spam-Status: No, score=-9.6 required=5.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Mon, 13 Nov 2023 02:53:07 -0800 (PST) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782445808689463824 X-GMAIL-MSGID: 1782445808689463824 Ensure that tag sequences containing alternating values are compressed to buffers of expected size and correctly decompressed afterwards. Signed-off-by: Alexander Potapenko Acked-by: Catalin Marinas --- v9: - minor changes to Kconfig description v8: - adapt to the simplified compression algorithm v6: - add test_decompress_invalid() to ensure invalid handles are ignored; - add test_upper_bits(), which is a regression test for a case where an inline handle looked like an out-of-line one; - add test_compress_nonzero() to ensure a full nonzero tag array is compressed correctly; - add test_two_ranges() to test cases when the input buffer is divided into two ranges. v5: - remove hardcoded constants, added test setup/teardown; - support 16- and 64K pages; - replace nested if-clauses with expected_size_from_ranges(); - call mte_release_handle() after tests that perform compression/decompression; - address comments by Andy Shevchenko: - fix include order; - use mtecomp.h instead of function prototypes. v4: - addressed comments by Andy Shevchenko: - expanded MTE to "Memory Tagging Extension" in Kconfig - changed signed variables to unsigned where applicable - added missing header dependencies - addressed comments by Yury Norov: - moved test-only declarations from mtecomp.h into this test - switched to the new "mte"-prefixed function names, dropped the mentions of "EA0" - added test_tag_to_ranges_n() v3: - addressed comments by Andy Shevchenko in another patch: - switched from u64 to unsigned long - added MODULE_IMPORT_NS(MTECOMP) - fixed includes order --- arch/arm64/Kconfig | 11 ++ arch/arm64/mm/Makefile | 1 + arch/arm64/mm/test_mtecomp.c | 364 +++++++++++++++++++++++++++++++++++ 3 files changed, 376 insertions(+) create mode 100644 arch/arm64/mm/test_mtecomp.c diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig index c2fbe8e492e00..92104994aaf18 100644 --- a/arch/arm64/Kconfig +++ b/arch/arm64/Kconfig @@ -2084,6 +2084,17 @@ config ARM64_MTE_COMP RLE to conserve heap memory. In the common case compressed tags occupy 2.5x less memory. +config ARM64_MTE_COMP_KUNIT_TEST + tristate "Test tag compression for ARM64 Memory Tagging Extension" if !KUNIT_ALL_TESTS + default KUNIT_ALL_TESTS + depends on KUNIT && ARM64_MTE_COMP + help + Test MTE compression algorithm enabled by CONFIG_ARM64_MTE_COMP. + + Ensure that certain tag sequences containing alternating values can + be compressed into pointer-size values and correctly decompressed + afterwards. + config ARM64_SVE bool "ARM Scalable Vector Extension support" default y diff --git a/arch/arm64/mm/Makefile b/arch/arm64/mm/Makefile index 46778f6dd83c2..170dc62b010b9 100644 --- a/arch/arm64/mm/Makefile +++ b/arch/arm64/mm/Makefile @@ -11,6 +11,7 @@ obj-$(CONFIG_TRANS_TABLE) += trans_pgd-asm.o obj-$(CONFIG_DEBUG_VIRTUAL) += physaddr.o obj-$(CONFIG_ARM64_MTE) += mteswap.o obj-$(CONFIG_ARM64_MTE_COMP) += mtecomp.o +obj-$(CONFIG_ARM64_MTE_COMP_KUNIT_TEST) += test_mtecomp.o KASAN_SANITIZE_physaddr.o += n obj-$(CONFIG_KASAN) += kasan_init.o diff --git a/arch/arm64/mm/test_mtecomp.c b/arch/arm64/mm/test_mtecomp.c new file mode 100644 index 0000000000000..e8aeb7607ff41 --- /dev/null +++ b/arch/arm64/mm/test_mtecomp.c @@ -0,0 +1,364 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Test cases for MTE tags compression algorithm. + */ + +#include +#include +#include +#include +#include + +#include + +#include + +#include "mtecomp.h" + +/* Per-test storage allocated in mtecomp_test_init(). */ +struct test_data { + u8 *tags, *dtags; + unsigned short *r_sizes; + size_t r_len; + u8 *r_tags; +}; + +/* + * Split td->tags to ranges stored in td->r_tags, td->r_sizes, td->r_len, + * then convert those ranges back to tags stored in td->dtags. + */ +static void tags_to_ranges_to_tags_helper(struct kunit *test) +{ + struct test_data *td = test->priv; + + mte_tags_to_ranges(td->tags, td->r_tags, td->r_sizes, &td->r_len); + mte_ranges_to_tags(td->r_tags, td->r_sizes, td->r_len, td->dtags); + KUNIT_EXPECT_EQ(test, memcmp(td->tags, td->dtags, MTE_PAGE_TAG_STORAGE), + 0); +} + +/* + * Test that mte_tags_to_ranges() produces a single range for a zero-filled tag + * buffer. + */ +static void test_tags_to_ranges_zero(struct kunit *test) +{ + struct test_data *td = test->priv; + + memset(td->tags, 0, MTE_PAGE_TAG_STORAGE); + tags_to_ranges_to_tags_helper(test); + + KUNIT_EXPECT_EQ(test, td->r_len, 1); + KUNIT_EXPECT_EQ(test, td->r_tags[0], 0); + KUNIT_EXPECT_EQ(test, td->r_sizes[0], MTE_GRANULES_PER_PAGE); +} + +/* + * Test that a small number of different tags is correctly transformed into + * ranges. + */ +static void test_tags_to_ranges_simple(struct kunit *test) +{ + struct test_data *td = test->priv; + const u8 ex_tags[] = { 0xa, 0x0, 0xa, 0xb, 0x0 }; + const unsigned short ex_sizes[] = { 1, 2, 2, 1, + MTE_GRANULES_PER_PAGE - 6 }; + + memset(td->tags, 0, MTE_PAGE_TAG_STORAGE); + td->tags[0] = 0xa0; + td->tags[1] = 0x0a; + td->tags[2] = 0xab; + tags_to_ranges_to_tags_helper(test); + + KUNIT_EXPECT_EQ(test, td->r_len, 5); + KUNIT_EXPECT_EQ(test, memcmp(td->r_tags, ex_tags, sizeof(ex_tags)), 0); + KUNIT_EXPECT_EQ(test, memcmp(td->r_sizes, ex_sizes, sizeof(ex_sizes)), + 0); +} + +/* Test that repeated 0xa0 byte produces MTE_GRANULES_PER_PAGE ranges of length 1. */ +static void test_tags_to_ranges_repeated(struct kunit *test) +{ + struct test_data *td = test->priv; + + memset(td->tags, 0xa0, MTE_PAGE_TAG_STORAGE); + tags_to_ranges_to_tags_helper(test); + + KUNIT_EXPECT_EQ(test, td->r_len, MTE_GRANULES_PER_PAGE); +} + +/* Generate a buffer that will contain @nranges of tag ranges. */ +static void gen_tag_range_helper(u8 *tags, int nranges) +{ + unsigned int i; + + memset(tags, 0, MTE_PAGE_TAG_STORAGE); + if (nranges > 1) { + nranges--; + for (i = 0; i < nranges / 2; i++) + tags[i] = 0xab; + if (nranges % 2) + tags[nranges / 2] = 0xa0; + } +} + +/* + * Test that mte_tags_to_ranges()/mte_ranges_to_tags() work for various + * r_len values. + */ +static void test_tag_to_ranges_n(struct kunit *test) +{ + struct test_data *td = test->priv; + unsigned int i, j, sum; + + for (i = 1; i <= MTE_GRANULES_PER_PAGE; i++) { + gen_tag_range_helper(td->tags, i); + tags_to_ranges_to_tags_helper(test); + sum = 0; + for (j = 0; j < td->r_len; j++) + sum += td->r_sizes[j]; + KUNIT_EXPECT_EQ(test, sum, MTE_GRANULES_PER_PAGE); + } +} + +/* + * Check that the tag buffer in test->priv can be compressed and decompressed + * without changes. + */ +static void *compress_decompress_helper(struct kunit *test) +{ + struct test_data *td = test->priv; + void *handle; + + handle = mte_compress(td->tags); + KUNIT_EXPECT_EQ(test, (unsigned long)handle & BIT_ULL(63), 0); + if (handle) { + KUNIT_EXPECT_TRUE(test, mte_decompress(handle, td->dtags)); + KUNIT_EXPECT_EQ(test, memcmp(td->tags, td->dtags, MTE_PAGE_TAG_STORAGE), + 0); + } + return handle; +} + +/* Test that a zero-filled array is compressed into inline storage. */ +static void test_compress_zero(struct kunit *test) +{ + struct test_data *td = test->priv; + void *handle; + + memset(td->tags, 0, MTE_PAGE_TAG_STORAGE); + handle = compress_decompress_helper(test); + /* Tags are stored inline. */ + KUNIT_EXPECT_TRUE(test, mte_is_compressed(handle)); +} + +/* Test that a 0xaa-filled array is compressed into inline storage. */ +static void test_compress_nonzero(struct kunit *test) +{ + struct test_data *td = test->priv; + void *handle; + + memset(td->tags, 0xaa, MTE_PAGE_TAG_STORAGE); + handle = compress_decompress_helper(test); + /* Tags are stored inline. */ + KUNIT_EXPECT_TRUE(test, mte_is_compressed(handle)); +} + +/* + * Test that two tag ranges are compressed into inline storage. + * + * This also covers a special case where both ranges contain + * `MTE_GRANULES_PER_PAGE / 2` tags and overflow the designated range size. + */ +static void test_two_ranges(struct kunit *test) +{ + struct test_data *td = test->priv; + void *handle; + unsigned int i; + size_t r_len = 2; + unsigned char r_tags[2] = { 0xe, 0x0 }; + unsigned short r_sizes[2]; + + for (i = 1; i < MTE_GRANULES_PER_PAGE; i++) { + r_sizes[0] = i; + r_sizes[1] = MTE_GRANULES_PER_PAGE - i; + mte_ranges_to_tags(r_tags, r_sizes, r_len, td->tags); + handle = compress_decompress_helper(test); + KUNIT_EXPECT_TRUE(test, mte_is_compressed(handle)); + } +} + +/* + * Test that a very small number of tag ranges ends up compressed into 8 bytes. + */ +static void test_compress_simple(struct kunit *test) +{ + struct test_data *td = test->priv; + void *handle; + + memset(td->tags, 0, MTE_PAGE_TAG_STORAGE); + td->tags[0] = 0xa0; + td->tags[1] = 0x0a; + + handle = compress_decompress_helper(test); + /* Tags are stored inline. */ + KUNIT_EXPECT_TRUE(test, mte_is_compressed(handle)); +} + +/* + * Test that a buffer containing @nranges ranges compresses into @exp_size + * bytes and decompresses into the original tag sequence. + */ +static void compress_range_helper(struct kunit *test, int nranges, + bool exp_inl) +{ + struct test_data *td = test->priv; + void *handle; + + gen_tag_range_helper(td->tags, nranges); + handle = compress_decompress_helper(test); + KUNIT_EXPECT_EQ(test, mte_is_compressed(handle), exp_inl); +} + +static inline size_t max_inline_ranges(void) +{ +#if defined CONFIG_ARM64_4K_PAGES + return 6; +#elif defined(CONFIG_ARM64_16K_PAGES) + return 5; +#else + return 4; +#endif +} + +/* + * Test that every number of tag ranges is correctly compressed and + * decompressed. + */ +static void test_compress_ranges(struct kunit *test) +{ + unsigned int i; + bool exp_inl; + + for (i = 1; i <= MTE_GRANULES_PER_PAGE; i++) { + exp_inl = i <= max_inline_ranges(); + compress_range_helper(test, i, exp_inl); + } +} + +/* + * Test that invalid handles are ignored by mte_decompress(). + */ +static void test_decompress_invalid(struct kunit *test) +{ + void *handle1 = (void *)0xeb0b0b0100804020; + void *handle2 = (void *)0x6b0b0b010080402f; + struct test_data *td = test->priv; + + /* handle1 has bit 0 set to 1. */ + KUNIT_EXPECT_FALSE(test, mte_decompress(handle1, td->dtags)); + /* + * handle2 is an inline handle, but its largest_idx (bits 1..3) + * is out of bounds for the inline storage. + */ + KUNIT_EXPECT_FALSE(test, mte_decompress(handle2, td->dtags)); +} + +/* + * Test that compressed inline tags cannot be confused with out-of-line + * pointers. + * + * Compressed values are written from bit 0 to bit 63, so the size of the last + * tag range initially ends up in the upper bits of the inline representation. + * Make sure mte_compress() rearranges the bits so that the resulting handle does + * not have 0b0111 as the upper four bits. + */ +static void test_upper_bits(struct kunit *test) +{ + struct test_data *td = test->priv; + void *handle; + unsigned char r_tags[6] = { 7, 0, 7, 0, 7, 0 }; + unsigned short r_sizes[6] = { 1, 1, 1, 1, 1, 1 }; + size_t r_len; + + /* Maximum number of ranges that can be encoded inline. */ + r_len = max_inline_ranges(); + /* Maximum range size possible, will be omitted. */ + r_sizes[0] = MTE_GRANULES_PER_PAGE / 2 - 1; + /* A number close to r_sizes[0] that has most of its bits set. */ + r_sizes[r_len - 1] = MTE_GRANULES_PER_PAGE - r_sizes[0] - r_len + 2; + + mte_ranges_to_tags(r_tags, r_sizes, r_len, td->tags); + handle = compress_decompress_helper(test); + KUNIT_EXPECT_TRUE(test, mte_is_compressed(handle)); +} + +static void mtecomp_dealloc_testdata(struct test_data *td) +{ + kfree(td->tags); + kfree(td->dtags); + kfree(td->r_sizes); + kfree(td->r_tags); +} + +static int mtecomp_test_init(struct kunit *test) +{ + struct test_data *td; + + td = kmalloc(sizeof(struct test_data), GFP_KERNEL); + if (!td) + return 1; + td->tags = kmalloc(MTE_PAGE_TAG_STORAGE, GFP_KERNEL); + if (!td->tags) + goto error; + td->dtags = kmalloc(MTE_PAGE_TAG_STORAGE, GFP_KERNEL); + if (!td->dtags) + goto error; + td->r_len = MTE_GRANULES_PER_PAGE; + td->r_sizes = kmalloc_array(MTE_GRANULES_PER_PAGE, + sizeof(unsigned short), GFP_KERNEL); + if (!td->r_sizes) + goto error; + td->r_tags = kmalloc(MTE_GRANULES_PER_PAGE, GFP_KERNEL); + if (!td->r_tags) + goto error; + test->priv = (void *)td; + return 0; +error: + mtecomp_dealloc_testdata(td); + return 1; +} + +static void mtecomp_test_exit(struct kunit *test) +{ + struct test_data *td = test->priv; + + mtecomp_dealloc_testdata(td); +} + +static struct kunit_case mtecomp_test_cases[] = { + KUNIT_CASE(test_tags_to_ranges_zero), + KUNIT_CASE(test_tags_to_ranges_simple), + KUNIT_CASE(test_tags_to_ranges_repeated), + KUNIT_CASE(test_tag_to_ranges_n), + KUNIT_CASE(test_compress_zero), + KUNIT_CASE(test_compress_nonzero), + KUNIT_CASE(test_two_ranges), + KUNIT_CASE(test_compress_simple), + KUNIT_CASE(test_compress_ranges), + KUNIT_CASE(test_decompress_invalid), + KUNIT_CASE(test_upper_bits), + {} +}; + +static struct kunit_suite mtecomp_test_suite = { + .name = "mtecomp", + .init = mtecomp_test_init, + .exit = mtecomp_test_exit, + .test_cases = mtecomp_test_cases, +}; +kunit_test_suites(&mtecomp_test_suite); + +MODULE_IMPORT_NS(MTECOMP); +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Alexander Potapenko "); From patchwork Mon Nov 13 10:52:32 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 164404 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b909:0:b0:403:3b70:6f57 with SMTP id t9csp1120366vqg; Mon, 13 Nov 2023 02:53:19 -0800 (PST) X-Google-Smtp-Source: AGHT+IEVQRedqC3DofN4MjxMOZI/dat64N9w78LcR85JGoCXyS8syQA9CuE3tbQbBx3na7yPLO4U X-Received: by 2002:a17:903:22c6:b0:1cc:e66:372e with SMTP id y6-20020a17090322c600b001cc0e66372emr8321087plg.20.1699872799684; Mon, 13 Nov 2023 02:53:19 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1699872799; cv=none; d=google.com; s=arc-20160816; b=NXCl5hY1H6cQFXp5mt3r+OXwLEX8q6W0YYpDLDx4uCllqnHQTaHOQRtiYK0OcVz5JZ /hNiv4VQyEPNF5FnqZDX/gYYU/J5Q+6yEe5KSlQ2BnNIxmeenROkOahXJtXagLhb5hK0 fsbbwr4/fiMqN/zt0v0AfSHyn6CgB82N/a2aooLnGsqaBL9EatrC4dIa1QaQxrfj2T7e L/N+CC8F/JefsFO8Aq9uovKHhsqu1eH12pM7wbFLUecE7FEMY1JmwA4S8No/bVvn2Ls0 CmADc9pFGAvefL6Xevw8cL5xL2vNawJsjZjKWIOElOCNw87uP8gj1xqXNzmNBe41MrFe A5KA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:dkim-signature; bh=Zy+PlU+FeLCVAtPuXK15UDcGql8UQVRw/kwgKDnnM+M=; fh=bwsiIJU4ZySHCYgdbJrawkDYkx7XsqbTjYxIEnch01E=; b=HFN8fHyEfHhUaRJ8pKmn1x9uvLpxLBW0SFVAGu0HCZbSIDPtJ8KJO08ezlJ6WO0Rs4 4zHM0Mfix8wQGwQvaHqdgbAMsbLATjWkSscFCuqbP+yT1NNIj2AnoV5KIQIGj0j3zeVL XeqY/WTBaaAS+Vl1QuEq8sJPO+h2c4dpDy5xAo0PyNUctNCdo2O65KR6vmFoQ8EKe13P 0UAqFgu5CRpflG3FlCX0dW6w+jw+DJGsBh3cYCbe3gTcJS+3newjufoPwkKf4p+6ZDOJ oNQa/aSgmpwz07/F43C8rBUZU37RlXZBS77X3ujAm8NE3izRUn3auud8IkR7ZCRudAvK 2+QQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=jcXleIbK; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from snail.vger.email (snail.vger.email. [2620:137:e000::3:7]) by mx.google.com with ESMTPS id o16-20020a170902d4d000b001c3411c9b83si5754043plg.454.2023.11.13.02.53.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 13 Nov 2023 02:53:19 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=jcXleIbK; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by snail.vger.email (Postfix) with ESMTP id BF253804754A; Mon, 13 Nov 2023 02:53:18 -0800 (PST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.11 at snail.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230029AbjKMKxD (ORCPT + 29 others); Mon, 13 Nov 2023 05:53:03 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:45078 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229470AbjKMKwt (ORCPT ); Mon, 13 Nov 2023 05:52:49 -0500 Received: from mail-yb1-xb49.google.com (mail-yb1-xb49.google.com [IPv6:2607:f8b0:4864:20::b49]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4CFDD10D3 for ; Mon, 13 Nov 2023 02:52:46 -0800 (PST) Received: by mail-yb1-xb49.google.com with SMTP id 3f1490d57ef6-dae71322ed4so5177375276.1 for ; Mon, 13 Nov 2023 02:52:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1699872765; x=1700477565; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=Zy+PlU+FeLCVAtPuXK15UDcGql8UQVRw/kwgKDnnM+M=; b=jcXleIbKF8S2B4SR0ReqNqFTWLAyAr6Vp+FcbJIZPwfNWTEP9W19erEHYA5h9hVE4j 07N9i77xyKYsEB/sIJYsii5BSb+aHV8eJlr8ZW0HvxI73J4id7q40mkP9e60FHdkWPfd PVXJbo2J1PJcPcgZWhWdMENyL8g00IhFENV+o0PvMihBJVrA4W1LwVLM51YdeZ6hh9zA LypJHGaP139EFoL9cNvsS9r8Zv4u891zjw7L3ETaFAKRRNAE7x7EUCctn3N8ik4ZIUm8 vyMts8MvZYMTu0Ah0W42ux4A9F03kSCPtLRgAN14dmWnEAjwMO1brWNMRKOg8uBeQ6I9 CoSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699872765; x=1700477565; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=Zy+PlU+FeLCVAtPuXK15UDcGql8UQVRw/kwgKDnnM+M=; b=ZoHnvk9/QgJ83Hi447/et47lZYoYGWSOOqemz30bE582gJsIPaaB1bOtfQ4coWU6Ug F3KFJQMCP4aaR7SDNnK4vN0XJwzVZEkS1193VoGuNmz7lJ24QwJe98jd9tRoqtSkCkDb epV71J2i4O9CRSV5eYn1XoA9jzBJa6dxeSRhlnpwwS8g+iDSqG7ogPRKwDrg0lTVb1/g hU1jrYvOZGfdMRm+bfLIV5sIjk8QE6jldYe+Y3q5//0j6QrsKNyU/w/Jvf9WsMFTjwJG woy6iQ+1H80EWW/ZsrhkFyYTwgoQ6w7GsXxp5R5xTnTtHvmvXDorqNFkH+JZdhXimpwb z0Vg== X-Gm-Message-State: AOJu0YzNX09Ie7PpbCs1zVJj1aa5iMfii9DgM5NIDq4TT2KGrz7eRqDg p5oW4dOPE1F0C/yfSOz1S01gyWdghxY= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:be07:845d:4221:b15e]) (user=glider job=sendgmr) by 2002:a25:2e4b:0:b0:dae:e8dc:c026 with SMTP id b11-20020a252e4b000000b00daee8dcc026mr153989ybn.13.1699872765517; Mon, 13 Nov 2023 02:52:45 -0800 (PST) Date: Mon, 13 Nov 2023 11:52:32 +0100 In-Reply-To: <20231113105234.32058-1-glider@google.com> Mime-Version: 1.0 References: <20231113105234.32058-1-glider@google.com> X-Mailer: git-send-email 2.42.0.869.gea05f2083d-goog Message-ID: <20231113105234.32058-4-glider@google.com> Subject: [PATCH v9 3/4] arm64: mte: add compression support to mteswap.c From: Alexander Potapenko To: glider@google.com, catalin.marinas@arm.com, will@kernel.org, pcc@google.com, andreyknvl@gmail.com, andriy.shevchenko@linux.intel.com, aleksander.lobakin@intel.com, linux@rasmusvillemoes.dk, yury.norov@gmail.com, alexandru.elisei@arm.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com, syednwaris@gmail.com, william.gray@linaro.org X-Spam-Status: No, score=-9.6 required=5.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF, RCVD_IN_DNSWL_BLOCKED,SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Mon, 13 Nov 2023 02:53:18 -0800 (PST) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782445820793238620 X-GMAIL-MSGID: 1782445820793238620 Update mteswap.c to perform inline compression of memory tags when possible. If CONFIG_ARM64_MTE_COMP is enabled, mteswap.c will attempt to compress saved tags for a struct page and store them directly in Xarray entry instead of wasting heap space. Soon after booting Android, tag compression saves ~2x memory previously spent by mteswap.c on tag allocations. On a moderately loaded device with ~20% tagged pages, this leads to saving several megabytes of kernel heap: # cat /sys/kernel/debug/mteswap/stats 8 bytes: 102496 allocations, 67302 deallocations 128 bytes: 212234 allocations, 178278 deallocations uncompressed tag storage size: 8851200 compressed tag storage size: 4346368 (statistics collection is introduced in the following patch) Signed-off-by: Alexander Potapenko Reviewed-by: Catalin Marinas --- v9: - as requested by Yury Norov, split off statistics collection into a separate patch - minor fixes v8: - adapt to the new compression API, abandon mteswap_{no,}comp.c - move stats collection to mteswap.c v5: - drop a dead variable from _mte_free_saved_tags() in mteswap_comp.c - ensure MTE compression works with arbitrary page sizes - update patch description v4: - minor code simplifications suggested by Andy Shevchenko, added missing header dependencies - changed compression API names to reflect modifications made to memcomp.h (as suggested by Yury Norov) v3: - Addressed comments by Andy Shevchenko in another patch: - fixed includes order - replaced u64 with unsigned long - added MODULE_IMPORT_NS(MTECOMP) --- arch/arm64/mm/mteswap.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) diff --git a/arch/arm64/mm/mteswap.c b/arch/arm64/mm/mteswap.c index a31833e3ddc54..70f5c8ecd640d 100644 --- a/arch/arm64/mm/mteswap.c +++ b/arch/arm64/mm/mteswap.c @@ -6,6 +6,8 @@ #include #include #include +#include +#include "mtecomp.h" static DEFINE_XARRAY(mte_pages); @@ -17,12 +19,13 @@ void *mte_allocate_tag_storage(void) void mte_free_tag_storage(char *storage) { - kfree(storage); + if (!mte_is_compressed(storage)) + kfree(storage); } int mte_save_tags(struct page *page) { - void *tag_storage, *ret; + void *tag_storage, *compressed_storage, *ret; if (!page_mte_tagged(page)) return 0; @@ -32,6 +35,11 @@ int mte_save_tags(struct page *page) return -ENOMEM; mte_save_page_tags(page_address(page), tag_storage); + compressed_storage = mte_compress(tag_storage); + if (compressed_storage) { + mte_free_tag_storage(tag_storage); + tag_storage = compressed_storage; + } /* lookup the swap entry.val from the page */ ret = xa_store(&mte_pages, page_swap_entry(page).val, tag_storage, @@ -50,13 +58,20 @@ int mte_save_tags(struct page *page) void mte_restore_tags(swp_entry_t entry, struct page *page) { void *tags = xa_load(&mte_pages, entry.val); + void *tag_storage = NULL; if (!tags) return; if (try_page_mte_tagging(page)) { + if (mte_is_compressed(tags)) { + tag_storage = mte_allocate_tag_storage(); + mte_decompress(tags, tag_storage); + tags = tag_storage; + } mte_restore_page_tags(page_address(page), tags); set_page_mte_tagged(page); + mte_free_tag_storage(tag_storage); } } From patchwork Mon Nov 13 10:52:33 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 164405 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b909:0:b0:403:3b70:6f57 with SMTP id t9csp1120535vqg; Mon, 13 Nov 2023 02:53:54 -0800 (PST) X-Google-Smtp-Source: AGHT+IHGITqxhW/km1+DiLE/Wf9JGHMwhTDFxUlfamZ7gH382u4I8apxTiX6+FhvX+q448JezQJ5 X-Received: by 2002:a17:902:9045:b0:1cc:ec22:5a40 with SMTP id w5-20020a170902904500b001ccec225a40mr6145226plz.26.1699872834521; Mon, 13 Nov 2023 02:53:54 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1699872834; cv=none; d=google.com; s=arc-20160816; b=JfjFqVYXd2cC/ykJyiGsbfojS76kETajQ0QiHYK/0dQ7woCTN7+E12iluvKlWQm0y3 jtBH90o/XA5rcwIJBC8OHCXY5wpyT2RfwTrJ/Ja1EAZJIh3Eos7EonbgQIwgV9ufuK7X mV+a3vS1B8pVuTZ++jVCIfseiWJ9Ir194Z+bnFhffDoQzgnb7tGCHmC6GHE2Kz4nFaJC FQ5yB1oEKQmHAPNfMeMj31Tv9lcpc2d5VhJGWqxnzzBIHQ7xL4f2EX2U8I+VRXyIIepE HsYzb+i4BY3BtHHoPsufzc7wl6xFVuSNyExdH/waJrJbF61xLDvACPOMQXSSgQIPi3c9 6ViA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:dkim-signature; bh=VDcV3BFKliyvk3m2f2FefNzqSIhogLXHnswK1EPVrVs=; fh=bwsiIJU4ZySHCYgdbJrawkDYkx7XsqbTjYxIEnch01E=; b=AKUT7n99zyEAaPbi0h+iFAnRySEMNSH8/VpMIGE4reLUWgoRtoCsMybmwQTkCwpvYE jHoSfyKhs/xkp/z+8+lyQCYcPVOao+QM6vmpKAUNarq0mNPa+VKM62etbHEjm9WNQMm3 lYN1UN5cn5PJV58TjXjCtkvKeCjKNm0urm6iXO1t6pb48/vxgqK1eKMHuu1//ibQHPPB k4It98FXnGrsUjSZCSTu2jY2l/zjGtGZjYT+Ttuzh+1fnTEDEor4Vk6tA+gJhW56N02s qDPFyizhvGqtU8pgFJMlGz+s/ocff3EpY9whEKu4LgRMh/to/+UCOuGr1eeGqwZVp3vY nm/A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=umg2VFCe; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from agentk.vger.email (agentk.vger.email. [2620:137:e000::3:2]) by mx.google.com with ESMTPS id k18-20020a170902c41200b001c5f37aeebdsi6002227plk.579.2023.11.13.02.53.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 13 Nov 2023 02:53:54 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) client-ip=2620:137:e000::3:2; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=umg2VFCe; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by agentk.vger.email (Postfix) with ESMTP id B398C805AA1B; Mon, 13 Nov 2023 02:53:51 -0800 (PST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.11 at agentk.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229941AbjKMKw7 (ORCPT + 29 others); Mon, 13 Nov 2023 05:52:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57138 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229876AbjKMKwy (ORCPT ); Mon, 13 Nov 2023 05:52:54 -0500 Received: from mail-yw1-x114a.google.com (mail-yw1-x114a.google.com [IPv6:2607:f8b0:4864:20::114a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id ED1AC10DA for ; Mon, 13 Nov 2023 02:52:48 -0800 (PST) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-5afc00161daso49106677b3.1 for ; Mon, 13 Nov 2023 02:52:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1699872768; x=1700477568; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=VDcV3BFKliyvk3m2f2FefNzqSIhogLXHnswK1EPVrVs=; b=umg2VFCevPK8XgR7KtQ34k/kP9TfBl83RLhwyQ56qxlcVvuZ9AnEPfTzo9uaVyl0uA Ou/AG25mtBAmS7xuz+3SKi1sAgp8bS10O0aR3pJ7yvOiKKyV5zgTMSIAQQ9PHDlSkaGD YurIVeo2FXyYAd894rsDilMHYvMmAjIonyKzw1A9tYT7owBkR/V0awvDcRDjvCz82WKM s0uqUfyE0cQIoIAy4cm39kKSfoxyTo80qN4pHXREqA3lrS1CR0gorcIcxec4JUaLkqn/ 9vxHqkeLFCjvAP8iEsmS+VBX5qMVQls6pvkfPpjNjUgDLuEimvvRZbaCnyBITV2nQQe0 oXRQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699872768; x=1700477568; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=VDcV3BFKliyvk3m2f2FefNzqSIhogLXHnswK1EPVrVs=; b=tzUJqi69ThFseyGuo+6vOzv5qKqwhXBPj12SYY2goJk5IVM4TE0iYD9O+0XdON5IZx UiDkQID+l5+mQ1muX3YFo8NLi45z/3wEW+uVOF5+CvMZYBSTA5w+m7C9Y8NdAYbm6rGn M+8SkXg+PlZqlujftEOnTTMKOWjr5VixJUV8uXm65VuqhZAubZw3KDuxP3Byb5+CAZ5z KKRb3sHQqiinvCC/mF+gyOS8RnjXKEC1AGCxUp6nQ47d7JsKc1uDwLLREaP/LzFSsFzm 3G/iR99n+BikIuj3OuQt10Pg2Il2Ny2jJyYxl+fcP1k8KCPQuyvvg3OiGZRmwpkt+kWj AYyA== X-Gm-Message-State: AOJu0YyFCLmbtleQqBHDa8ZrmhFvWxVNVFBeQpsOaMcCVWd6puBEZ3Nc NCm8JUc2qxJ9CVsoETaHJ1b4uTbr0mk= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:be07:845d:4221:b15e]) (user=glider job=sendgmr) by 2002:a81:914e:0:b0:5a7:db29:40e3 with SMTP id i75-20020a81914e000000b005a7db2940e3mr176202ywg.7.1699872768212; Mon, 13 Nov 2023 02:52:48 -0800 (PST) Date: Mon, 13 Nov 2023 11:52:33 +0100 In-Reply-To: <20231113105234.32058-1-glider@google.com> Mime-Version: 1.0 References: <20231113105234.32058-1-glider@google.com> X-Mailer: git-send-email 2.42.0.869.gea05f2083d-goog Message-ID: <20231113105234.32058-5-glider@google.com> Subject: [PATCH v9 4/4] arm64: mte: implement CONFIG_ARM64_MTE_SWAP_STATS From: Alexander Potapenko To: glider@google.com, catalin.marinas@arm.com, will@kernel.org, pcc@google.com, andreyknvl@gmail.com, andriy.shevchenko@linux.intel.com, aleksander.lobakin@intel.com, linux@rasmusvillemoes.dk, yury.norov@gmail.com, alexandru.elisei@arm.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com, syednwaris@gmail.com, william.gray@linaro.org X-Spam-Status: No, score=-8.4 required=5.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE, USER_IN_DEF_DKIM_WL autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on agentk.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (agentk.vger.email [0.0.0.0]); Mon, 13 Nov 2023 02:53:51 -0800 (PST) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782445856988003434 X-GMAIL-MSGID: 1782445856988003434 Provide a config to collect the usage statistics for ARM MTE tag compression. This patch introduces allocation/deallocation counters for buffers that were stored uncompressed (and thus occupy 128 bytes of heap plus the Xarray overhead to store a pointer) and those that were compressed into 8-byte pointers (effectively using 0 bytes of heap in addition to the Xarray overhead). The counters are exposed to the userspace via /sys/kernel/debug/mteswap/stats: # cat /sys/kernel/debug/mteswap/stats 8 bytes: 102496 allocations, 67302 deallocations 128 bytes: 212234 allocations, 178278 deallocations uncompressed tag storage size: 8851200 compressed tag storage size: 4346368 Suggested-by: Yury Norov Signed-off-by: Alexander Potapenko Acked-by: Catalin Marinas --- This patch was split off from the "arm64: mte: add compression support to mteswap.c" patch (https://lore.kernel.org/linux-arm-kernel/ZUVulBKVYK7cq2rJ@yury-ThinkPad/T/#m819ec30beb9de53d5c442f7e3247456f8966d88a) v9: - add this patch, put the stats behind a separate config, mention /sys/kernel/debug/mteswap/stats in the documentation --- .../arch/arm64/mte-tag-compression.rst | 12 +++ arch/arm64/Kconfig | 15 +++ arch/arm64/mm/mteswap.c | 93 ++++++++++++++++++- 3 files changed, 118 insertions(+), 2 deletions(-) diff --git a/Documentation/arch/arm64/mte-tag-compression.rst b/Documentation/arch/arm64/mte-tag-compression.rst index 8fe6b51a9db6d..4c25b96f7d4b5 100644 --- a/Documentation/arch/arm64/mte-tag-compression.rst +++ b/Documentation/arch/arm64/mte-tag-compression.rst @@ -145,6 +145,18 @@ Tag compression and decompression implicitly rely on the fixed MTE tag size (4 bits) and number of tags per page. Should these values change, the algorithm may need to be revised. +Stats +===== + +When `CONFIG_ARM64_MTE_SWAP_STATS` is enabled, `arch/arm64/mm/mteswap.c` exports +usage statistics for tag compression used when swapping tagged pages. The data +can be accessed via debugfs:: + + # cat /sys/kernel/debug/mteswap/stats + 8 bytes: 10438 allocations, 10417 deallocations + 128 bytes: 26180 allocations, 26179 deallocations + uncompressed tag storage size: 2816 + compressed tag storage size: 128 Programming Interface ===================== diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig index 92104994aaf18..60c969bd4078b 100644 --- a/arch/arm64/Kconfig +++ b/arch/arm64/Kconfig @@ -2095,6 +2095,21 @@ config ARM64_MTE_COMP_KUNIT_TEST be compressed into pointer-size values and correctly decompressed afterwards. +config ARM64_MTE_SWAP_STATS + bool "Collect usage statistics of tag compression for swapped MTE tags" + default y + depends on ARM64_MTE && ARM64_MTE_COMP + help + Collect usage statistics for ARM64 MTE tag compression during swapping. + + Adds allocation/deallocation counters for buffers that were stored + uncompressed (and thus occupy 128 bytes of heap plus the Xarray + overhead to store a pointer) and those that were compressed into + 8-byte pointers (effectively using 0 bytes of heap in addition to + the Xarray overhead). + The counters are exposed to the userspace via + /sys/kernel/debug/mteswap/stats. + config ARM64_SVE bool "ARM Scalable Vector Extension support" default y diff --git a/arch/arm64/mm/mteswap.c b/arch/arm64/mm/mteswap.c index 70f5c8ecd640d..1c6c78b9a9037 100644 --- a/arch/arm64/mm/mteswap.c +++ b/arch/arm64/mm/mteswap.c @@ -1,5 +1,6 @@ // SPDX-License-Identifier: GPL-2.0-only +#include #include #include #include @@ -11,16 +12,54 @@ static DEFINE_XARRAY(mte_pages); +enum mteswap_counters { + MTESWAP_CTR_INLINE = 0, + MTESWAP_CTR_OUTLINE, + MTESWAP_CTR_SIZE +}; + +#if defined(CONFIG_ARM64_MTE_SWAP_STATS) +static atomic_long_t alloc_counters[MTESWAP_CTR_SIZE]; +static atomic_long_t dealloc_counters[MTESWAP_CTR_SIZE]; + +static void inc_alloc_counter(int kind) +{ + atomic_long_inc(&alloc_counters[kind]); +} + +static void inc_dealloc_counter(int kind) +{ + atomic_long_inc(&dealloc_counters[kind]); +} +#else +static void inc_alloc_counter(int kind) +{ +} + +static void inc_dealloc_counter(int kind) +{ +} +#endif + void *mte_allocate_tag_storage(void) { + void *ret; + /* tags granule is 16 bytes, 2 tags stored per byte */ - return kmalloc(MTE_PAGE_TAG_STORAGE, GFP_KERNEL); + ret = kmalloc(MTE_PAGE_TAG_STORAGE, GFP_KERNEL); + if (ret) + inc_alloc_counter(MTESWAP_CTR_OUTLINE); + return ret; } void mte_free_tag_storage(char *storage) { - if (!mte_is_compressed(storage)) + if (!mte_is_compressed(storage)) { kfree(storage); + inc_dealloc_counter(MTESWAP_CTR_OUTLINE); + } else { + inc_dealloc_counter(MTESWAP_CTR_INLINE); + } } int mte_save_tags(struct page *page) @@ -39,6 +78,7 @@ int mte_save_tags(struct page *page) if (compressed_storage) { mte_free_tag_storage(tag_storage); tag_storage = compressed_storage; + inc_alloc_counter(MTESWAP_CTR_INLINE); } /* lookup the swap entry.val from the page */ @@ -98,3 +138,52 @@ void mte_invalidate_tags_area(int type) } xa_unlock(&mte_pages); } + +#if defined(CONFIG_ARM64_MTE_SWAP_STATS) +/* DebugFS interface. */ +static int stats_show(struct seq_file *seq, void *v) +{ + unsigned long total_mem_alloc = 0, total_mem_dealloc = 0; + unsigned long total_num_alloc = 0, total_num_dealloc = 0; + unsigned long sizes[2] = { 8, MTE_PAGE_TAG_STORAGE }; + long alloc, dealloc; + unsigned long size; + int i; + + for (i = 0; i < MTESWAP_CTR_SIZE; i++) { + alloc = atomic_long_read(&alloc_counters[i]); + dealloc = atomic_long_read(&dealloc_counters[i]); + total_num_alloc += alloc; + total_num_dealloc += dealloc; + size = sizes[i]; + /* + * Do not count 8-byte buffers towards compressed tag storage + * size. + */ + if (i) { + total_mem_alloc += (size * alloc); + total_mem_dealloc += (size * dealloc); + } + seq_printf(seq, + "%lu bytes:\t%lu allocations,\t%lu deallocations\n", + size, alloc, dealloc); + } + seq_printf(seq, "uncompressed tag storage size:\t%lu\n", + (total_num_alloc - total_num_dealloc) * + MTE_PAGE_TAG_STORAGE); + seq_printf(seq, "compressed tag storage size:\t%lu\n", + total_mem_alloc - total_mem_dealloc); + return 0; +} +DEFINE_SHOW_ATTRIBUTE(stats); + +static int mteswap_init(void) +{ + struct dentry *mteswap_dir; + + mteswap_dir = debugfs_create_dir("mteswap", NULL); + debugfs_create_file("stats", 0444, mteswap_dir, NULL, &stats_fops); + return 0; +} +module_init(mteswap_init); +#endif