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 bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id C69BECDB466 for ; Wed, 11 Oct 2023 17:29:14 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:Cc:To:From:Subject:Message-ID: Mime-Version:Date:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To: References:List-Owner; bh=EceH6E4FTiKBTunmoz171/5rj12Inubwo+OstDz43tk=; b=Szk nBLU7oWnhRwFtIAp6xiP8+Huli3EMVQ291Z5O6h7EYwT4Lm4Y77DSy+SeZ1vosdR8sGrLNeW4eQdf HYsgsn7zWti8vU8gTt2X1fqh6EDKWaoufghyd0dpyOcnDzjTdVj70ZxaXNlpPTNyN1d2mA7j+eifU fGRNCvRGM6dZZ/YcegohruiMTwmepjDGNPPdW9q8pJLsu/KI/52KnJFhMhYx3AGBQIY+eqqY3gGKv P80c+QERDU0B30zUjwpfzbKSMfckEGWtlPj5/GPLU/078suQqoOdXqGppsDls3QnsJdx/SnO09/bB 5aPKJswLLrypzOg7NaChczKWX3CRKiw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.96 #2 (Red Hat Linux)) id 1qqd0p-00GL0R-2T; Wed, 11 Oct 2023 17:28:47 +0000 Received: from mail-yw1-x1149.google.com ([2607:f8b0:4864:20::1149]) by bombadil.infradead.org with esmtps (Exim 4.96 #2 (Red Hat Linux)) id 1qqd0m-00GKzS-1A for linux-arm-kernel@lists.infradead.org; Wed, 11 Oct 2023 17:28:46 +0000 Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-5a7af53bde4so1481557b3.0 for ; Wed, 11 Oct 2023 10:28:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1697045321; x=1697650121; darn=lists.infradead.org; h=cc:to:from:subject:message-id:mime-version:date:from:to:cc:subject :date:message-id:reply-to; bh=LwuwjmnVQtXjn+X5MfT/OJgDNhPxUAgxvbWJ6WO5//o=; b=SimTJhvBzOE6DrP9CWwXfz+2y2ikEGY5uG1PxmmjcpLa13omhWE46d3z2fOLfzL3wc R2QmaSee8RHIpQ+utSoCztQW6xXzW5z6cYxjTiLIGOiyeALGeYvb8H/gfpqaY4YaoB3D NFqf3TteV4KMKgrJpeIof4oT8m3luB8XXu38DduDi3f11ERAb4juU0IX43jR/7E9/7YL IiNu1KRc9nGgbcs7LSTNxqayl5ZvFUns3HBTz2jici6+tNk7CUcWtJd32fYKVL0MJbiA zyBJOe8Iqd+u8G7vpbrh0sYJksOJ+KnDUbVamKGbbSJbEMcPjrMbsnBTMC7t+VeVgQ6W dwIw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697045321; x=1697650121; h=cc:to:from:subject:message-id:mime-version:date:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=LwuwjmnVQtXjn+X5MfT/OJgDNhPxUAgxvbWJ6WO5//o=; b=m3w2S4Mz5oG9Uw4O5XI/aXvdFhXN2jWO5co2rqNLe2QhgwUC287NTmmIl4KWYVrJ0v KSaGrhIbL8XY4MBWcThKUq7ZM10FQBu/1B2xsF8vVec/5Mtw3E6iUAecQygedrAqXFw5 pQvhFJw5cM7Sc3WhSISiZPhL4IQ6bR9cmcdt4OKvdb+pNnKBM2SRDQjj17q/A+ItEa8L tX0ZJz8M14HnhIYkGAm5G+zfIxwmZeyCre6SZtnCZsxGvkAABtQEcA/L1jQvhIWXeTPQ VgNTVoozYltJvxxbWW32QtGjEHUwJgBk5nYbT1bNXOI7gZNIrJHU1vcKX0/eEU5+Eykp QlnQ== X-Gm-Message-State: AOJu0Yy19UPPhf9E4Tv+HleIRGH8t7UZZKCQ3Rb+XRopox9DjFXZjeXy DWFUJpJc0OjiJcCmBdZgH3Vn4fhdVL4= X-Google-Smtp-Source: AGHT+IFvIDL4pU0iR3JbDQTfyYNeAbR+jnr/Y9Dj6FlrLQu03dzX/AaLuKzGaLQWxlfGgKbV7k2zpTomtb0= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:fe58:8292:66f9:d221]) (user=glider job=sendgmr) by 2002:a25:d4d2:0:b0:d9a:38e4:78b5 with SMTP id m201-20020a25d4d2000000b00d9a38e478b5mr140459ybf.5.1697045321463; Wed, 11 Oct 2023 10:28:41 -0700 (PDT) Date: Wed, 11 Oct 2023 19:28:30 +0200 Mime-Version: 1.0 X-Mailer: git-send-email 2.42.0.609.gbb76f46606-goog Message-ID: <20231011172836.2579017-1-glider@google.com> Subject: [PATCH v7 0/5] Implement MTE tag compression for swapped pages 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-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20231011_102844_438623_F58C5E83 X-CRM114-Status: GOOD ( 16.04 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org Currently, when MTE pages are swapped out, the tags are kept in the memory, occupying PAGE_SIZE/32 bytes per page. This is especially problematic for devices that use zram-backed in-memory swap, because tags stored uncompressed in the heap effectively reduce the available amount of swap memory. The RLE-based algorithm suggested by Evgenii Stepanov and implemented in this patch series is able to efficiently compress fixed-size tag buffers, resulting in practical compression ratio between 2.5x and 4x. In most cases it is possible to store the compressed data in 63-bit Xarray values, resulting in no extra memory allocations. Our measurements show that the proposed algorithm provides better compression than existing kernel compression algorithms (LZ4, LZO, LZ4HC, ZSTD) can offer. To implement compression/decompression, we also extend with methods to read/write bit values at arbitrary places in the map. We refactor arch/arm64/mm/mteswap.c to support both the compressed (CONFIG_ARM64_MTE_COMP) and non-compressed case. For the former, in addition to tag compression, we move tag allocation from kmalloc() to separate kmem caches, providing greater locality and relaxing the alignment requirements. v7: - fixed comments by Yury Norov, Andy Shevchenko, Rasmus Villemoes - added perf tests for bitmap_read()/bitmap_write() - more efficient bitmap_write() implementation (meant to be sent in v5) v6: - fixed comments by Yury Norov - fixed handling of sizes divisible by MTE_GRANULES_PER_PAGE / 2 (caught while testing on a real device) v5: - fixed comments by Andy Shevchenko, Catalin Marinas, and Yury Norov - added support for 16K- and 64K pages - more efficient bitmap_write() implementation v4: - fixed a bunch of comments by Andy Shevchenko and Yury Norov - added Documentation/arch/arm64/mte-tag-compression.rst v3: - as suggested by Andy Shevchenko, use bitmap_get_value()/bitmap_set_value() written by Syed Nayyar Waris - switched to unsigned long to reduce typecasts - simplified the compression code v2: - as suggested by Yuri Norov, replace the poorly implemented struct bitq with Alexander Potapenko (4): lib/test_bitmap: add tests for bitmap_{read,write}() arm64: mte: implement CONFIG_ARM64_MTE_COMP arm64: mte: add a test for MTE tags compression arm64: mte: add compression support to mteswap.c Syed Nayyar Waris (1): lib/bitmap: add bitmap_{read,write}() Documentation/arch/arm64/index.rst | 1 + .../arch/arm64/mte-tag-compression.rst | 266 +++++++++ arch/arm64/Kconfig | 21 + arch/arm64/include/asm/mtecomp.h | 13 + arch/arm64/mm/Makefile | 7 + arch/arm64/mm/mtecomp.c | 524 ++++++++++++++++++ arch/arm64/mm/mtecomp.h | 12 + arch/arm64/mm/mteswap.c | 20 +- arch/arm64/mm/mteswap.h | 12 + arch/arm64/mm/mteswap_comp.c | 60 ++ arch/arm64/mm/mteswap_nocomp.c | 38 ++ arch/arm64/mm/test_mtecomp.c | 377 +++++++++++++ include/linux/bitmap.h | 75 +++ lib/test_bitmap.c | 166 ++++++ 14 files changed, 1581 insertions(+), 11 deletions(-) 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 create mode 100644 arch/arm64/mm/mteswap.h create mode 100644 arch/arm64/mm/mteswap_comp.c create mode 100644 arch/arm64/mm/mteswap_nocomp.c create mode 100644 arch/arm64/mm/test_mtecomp.c -- 2.42.0.609.gbb76f46606-goog _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id DECFBCDB466 for ; Wed, 11 Oct 2023 17:28:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231955AbjJKR2p (ORCPT ); Wed, 11 Oct 2023 13:28:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60548 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230012AbjJKR2o (ORCPT ); Wed, 11 Oct 2023 13:28:44 -0400 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 5258698 for ; Wed, 11 Oct 2023 10:28:42 -0700 (PDT) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-5a7be940fe1so1099547b3.2 for ; Wed, 11 Oct 2023 10:28:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1697045321; x=1697650121; darn=vger.kernel.org; h=cc:to:from:subject:message-id:mime-version:date:from:to:cc:subject :date:message-id:reply-to; bh=LwuwjmnVQtXjn+X5MfT/OJgDNhPxUAgxvbWJ6WO5//o=; b=IXT8uKclxUzwcWT+thJ/UvkoT1GFIWMNl7FNEJIHHUH7bOrDotgNyOcEg9/dt5duHN JVh4l18b32Su5y71VGUwP2lN1G1949xhHN7FxCqSiC6Kh4h1FqTQP1vx063qdv/uc16k XUIJmDYmBPXEkwRH0F90h8Pi96Nc5UYPYMpcNR/4eVSKRm/w2SrBh0kkb9keNcW8L4Zh DI5NnH8MQZxa95v9c3G+pBKbZA8AYUR8p8/KY/yEmor9uz71NkZ+nJo7W1uAzhLQypNH 3dHRIM0ZNzGEVGAYBChpV9QIVrhWeSOcnRl5PcpYpZ0rXaHPFJU+4AdI22P+OFqVBHsT ooag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697045321; x=1697650121; h=cc:to:from:subject:message-id:mime-version:date:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=LwuwjmnVQtXjn+X5MfT/OJgDNhPxUAgxvbWJ6WO5//o=; b=vczjecMVi5GxjSnQQIX4xlw1XS2wenvesquxGadh/I8CsfJ9nv774FijXkpqTMk5lb JtPMT7/oWIJBwr/bFBaz3GgDqPrPnVsKLoZcC2TSXyIZHpsmcwEWBKlOPtFtvRcEJukh ZxCKLDkKIgkYQEdbmLDgGo/IUYEjvB8s0slpfEMNjJbNYmJ1qyQnPb+gM0ZKxr1wNEmY FdUCxpKULvlaIbtgCfdlf9Kbhax4820DgjfVnTbNxT7S5Y/8MmA0BPbpj1I9xMB+0caj bvVkKMONmPVR8LY7CWVbY7hMsc0ALyFS/J90LRe5BOUNUlGGnq0zAbGBJsSEWAO4kyg5 sjpg== X-Gm-Message-State: AOJu0Yztf8G+NEIMlGycjKi/tLj23wGnd9yQHqgI5uczhvEzu/uozcpA 0fjCKSVnrr73jUj0v+sMvFfZ/VaN2l8= X-Google-Smtp-Source: AGHT+IFvIDL4pU0iR3JbDQTfyYNeAbR+jnr/Y9Dj6FlrLQu03dzX/AaLuKzGaLQWxlfGgKbV7k2zpTomtb0= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:fe58:8292:66f9:d221]) (user=glider job=sendgmr) by 2002:a25:d4d2:0:b0:d9a:38e4:78b5 with SMTP id m201-20020a25d4d2000000b00d9a38e478b5mr140459ybf.5.1697045321463; Wed, 11 Oct 2023 10:28:41 -0700 (PDT) Date: Wed, 11 Oct 2023 19:28:30 +0200 Mime-Version: 1.0 X-Mailer: git-send-email 2.42.0.609.gbb76f46606-goog Message-ID: <20231011172836.2579017-1-glider@google.com> Subject: [PATCH v7 0/5] Implement MTE tag compression for swapped pages 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 Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Currently, when MTE pages are swapped out, the tags are kept in the memory, occupying PAGE_SIZE/32 bytes per page. This is especially problematic for devices that use zram-backed in-memory swap, because tags stored uncompressed in the heap effectively reduce the available amount of swap memory. The RLE-based algorithm suggested by Evgenii Stepanov and implemented in this patch series is able to efficiently compress fixed-size tag buffers, resulting in practical compression ratio between 2.5x and 4x. In most cases it is possible to store the compressed data in 63-bit Xarray values, resulting in no extra memory allocations. Our measurements show that the proposed algorithm provides better compression than existing kernel compression algorithms (LZ4, LZO, LZ4HC, ZSTD) can offer. To implement compression/decompression, we also extend with methods to read/write bit values at arbitrary places in the map. We refactor arch/arm64/mm/mteswap.c to support both the compressed (CONFIG_ARM64_MTE_COMP) and non-compressed case. For the former, in addition to tag compression, we move tag allocation from kmalloc() to separate kmem caches, providing greater locality and relaxing the alignment requirements. v7: - fixed comments by Yury Norov, Andy Shevchenko, Rasmus Villemoes - added perf tests for bitmap_read()/bitmap_write() - more efficient bitmap_write() implementation (meant to be sent in v5) v6: - fixed comments by Yury Norov - fixed handling of sizes divisible by MTE_GRANULES_PER_PAGE / 2 (caught while testing on a real device) v5: - fixed comments by Andy Shevchenko, Catalin Marinas, and Yury Norov - added support for 16K- and 64K pages - more efficient bitmap_write() implementation v4: - fixed a bunch of comments by Andy Shevchenko and Yury Norov - added Documentation/arch/arm64/mte-tag-compression.rst v3: - as suggested by Andy Shevchenko, use bitmap_get_value()/bitmap_set_value() written by Syed Nayyar Waris - switched to unsigned long to reduce typecasts - simplified the compression code v2: - as suggested by Yuri Norov, replace the poorly implemented struct bitq with Alexander Potapenko (4): lib/test_bitmap: add tests for bitmap_{read,write}() arm64: mte: implement CONFIG_ARM64_MTE_COMP arm64: mte: add a test for MTE tags compression arm64: mte: add compression support to mteswap.c Syed Nayyar Waris (1): lib/bitmap: add bitmap_{read,write}() Documentation/arch/arm64/index.rst | 1 + .../arch/arm64/mte-tag-compression.rst | 266 +++++++++ arch/arm64/Kconfig | 21 + arch/arm64/include/asm/mtecomp.h | 13 + arch/arm64/mm/Makefile | 7 + arch/arm64/mm/mtecomp.c | 524 ++++++++++++++++++ arch/arm64/mm/mtecomp.h | 12 + arch/arm64/mm/mteswap.c | 20 +- arch/arm64/mm/mteswap.h | 12 + arch/arm64/mm/mteswap_comp.c | 60 ++ arch/arm64/mm/mteswap_nocomp.c | 38 ++ arch/arm64/mm/test_mtecomp.c | 377 +++++++++++++ include/linux/bitmap.h | 75 +++ lib/test_bitmap.c | 166 ++++++ 14 files changed, 1581 insertions(+), 11 deletions(-) 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 create mode 100644 arch/arm64/mm/mteswap.h create mode 100644 arch/arm64/mm/mteswap_comp.c create mode 100644 arch/arm64/mm/mteswap_nocomp.c create mode 100644 arch/arm64/mm/test_mtecomp.c -- 2.42.0.609.gbb76f46606-goog