From patchwork Thu Jul 13 12:57:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 119882 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp1820707vqm; Thu, 13 Jul 2023 06:21:48 -0700 (PDT) X-Google-Smtp-Source: APBJJlFBDDxhGRNSS+Bd7ffFslNlBfHiUxmFAAw4MDvubzoEyP9B5UsVyiyWlVPbhwD9PIuwFk5P X-Received: by 2002:a17:906:8b:b0:994:13c3:2f89 with SMTP id 11-20020a170906008b00b0099413c32f89mr2296507ejc.27.1689254508250; Thu, 13 Jul 2023 06:21:48 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689254508; cv=none; d=google.com; s=arc-20160816; b=T14CJ1+6CfAhrZZYFMaLTihW66dPRwhg1ZA8qYJB0vpd/yHpGbP22mzkPWJ9sNqKVl C+OYJXcdEsiWhAmq7Tv9a9zMb/yLbtvca4QqwUCBqETGlkt/2olSnat4nTCdFPyCHziM vJIV71D+bCO0AEapXE80CX1drJgM0+j2MT0gkoiRNaGfATvMV3h+xIFUuGGQ6MxQpsxX TXsAsnXsaL3V7k9JlGyAo5YpWKZplY0LvkZahrukVkCRtvncaIogTczfEu8CMvR0HmOY sODdaxY4upN722YTqxSTWCD5kHXtw9SjWT8AOJZFkyiiIVx1SNpQauxWGIGjDCt44XrA n5eg== 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=G3X9aMNtf+Y4a1BkuoJTavkrfHeiL0YXiMZI9eN5sqI=; fh=w2imRfrBx7xgrqExMhNQwXd/bCFo2iqBwf34S5/AxrI=; b=qQAGrXykO3iSqH2zdK6ir+VqgpxnRIrad3wH/mlb0pn2SuVA73VABPYi3rROztj5JA VRqT9t5eBeWbsOSmBiUN+VzIGFaCU6+hglZJKWAr3I0GTpaEx85rqeKmnIwaAMHamJ4l IRYRgi3pqLEyeWgPaatk+lv6yx0wbviSBOjIdLpCFkeEG6TO9ooqtVBSEz0qfTDl7Gk2 +z+ro+Nk8c55pgepuoMNuJvb1JRJKQnt6Y+9Xa6JGF4FIdoSen4O3pXLXSu/bqHKnA2N hxMMyPgCMfYq6c3CQgqDBASmr38LgZsf0+p9vYoW+fex7+r/aNXfJYNi9q/6733Kja9q oDJA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=SdKzR7yT; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 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 (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id j22-20020a170906411600b0099396547003si6987177ejk.774.2023.07.13.06.21.24; Thu, 13 Jul 2023 06:21:48 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=SdKzR7yT; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234850AbjGMM5e (ORCPT + 99 others); Thu, 13 Jul 2023 08:57:34 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36388 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234712AbjGMM5c (ORCPT ); Thu, 13 Jul 2023 08:57:32 -0400 Received: from mail-ed1-x54a.google.com (mail-ed1-x54a.google.com [IPv6:2a00:1450:4864:20::54a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B71F626B0 for ; Thu, 13 Jul 2023 05:57:29 -0700 (PDT) Received: by mail-ed1-x54a.google.com with SMTP id 4fb4d7f45d1cf-51e52b1fb4fso439114a12.3 for ; Thu, 13 Jul 2023 05:57:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689253048; x=1691845048; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=G3X9aMNtf+Y4a1BkuoJTavkrfHeiL0YXiMZI9eN5sqI=; b=SdKzR7yTSRRtkPH8PaZdS44fFu2DNGPv2/dy6ooEfMC7KJ2FOiE5d/H6k3NmPaBm4O amJ2UuqzibTpzA8DKvuhZxz1Sss1X4pLbm9EFZq/uOLe3QJvWpnJQrcAsBCpnWPqt4oE g64n0rY7HOaFQe0pg1Uin9savcYzWGMBM2Z7Wum8Xa6yIhZ+HEbUaUKwoPUIKGZlU8RA zlJY9rkKJ3DJKlpadBNHtcnDefxevG7PGdH9J+mbkOQKX7WFxfimK/ImWb0LWPwkwY3z 9a8z/PRJDF3l0fJ4S6L5esnKmpUi7uxVMp34zTDhtDoAmSIaJgbArKdR6Y1rfRrFKUte U1lg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689253048; x=1691845048; 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=G3X9aMNtf+Y4a1BkuoJTavkrfHeiL0YXiMZI9eN5sqI=; b=Rgox4YWTHBLUBGkqy2iPczWUqypJXsjZAqZWVK7TGAwlEtjR5rBCzI7GhJszjv9UCK gyb0Dyx/c+3N/BvMH3EWxfxjj4lCIl93d+X5oeYDsdzC2AZFjNmJ/PXS3S3LQUNquBB4 Z5rhTy9RXmBg0WB6BcOysGtRHQ2L64fHRW0DvtVsBWdZFMfEnk/jL+7Q+JtieT99K1Y9 PZVlSNs3tuJqSUt8eHl87Zt2JQq9jGA22UCiqkWCNJqbcAlhljGmZJQ6Y2TqBcaAEmni rrwAVgxDGKsgJpKQHMoN4JOhJdYpjyaZ4/K6KeRzaURPPN3cVkzq5rJ1jjdUvl7j6mK9 I6Nw== X-Gm-Message-State: ABy/qLZ6H58jEninRFsdDP8/CtOkl6ezGNkXd2jpjBc0BSlt2epppv/4 0vPcpe3144VLJa6ZnR4ib1Si8UzVz+8= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:7a88:66b7:31e5:7d85]) (user=glider job=sendgmr) by 2002:a50:99d3:0:b0:50b:c88a:f7cd with SMTP id n19-20020a5099d3000000b0050bc88af7cdmr8273edb.4.1689253048201; Thu, 13 Jul 2023 05:57:28 -0700 (PDT) Date: Thu, 13 Jul 2023 14:57:01 +0200 In-Reply-To: <20230713125706.2884502-1-glider@google.com> Mime-Version: 1.0 References: <20230713125706.2884502-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230713125706.2884502-2-glider@google.com> Subject: [v2 1/5] lib/bitmap: add bitmap_{set,get}_value_unaligned() 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, linux@rasmusvillemoes.dk, yury.norov@gmail.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771311735178941579 X-GMAIL-MSGID: 1771311735178941579 The two new functions allow setting/getting values of length up to BITS_PER_LONG bits at arbitrary position in the bitmap. Suggested-by: Yury Norov Signed-off-by: Alexander Potapenko --- include/linux/bitmap.h | 63 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 03644237e1efb..8e36ce07bafd4 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -77,6 +77,8 @@ struct device; * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst * bitmap_get_value8(map, start) Get 8bit value from map at start * bitmap_set_value8(map, value, start) Set 8bit value to map at start + * bitmap_get_value_unaligned(map, start, nbits) Get value up to BITS_PER_LONG + * bitmap_set_value_unaligned(map, value, start, nbits) Set value up to BITS_PER_LONG * * Note, bitmap_zero() and bitmap_fill() operate over the region of * unsigned longs, that is, bits behind bitmap till the unsigned long @@ -583,6 +585,35 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map, return (map[index] >> offset) & 0xFF; } +/** + * bitmap_get_value_unaligned - get an @nbits-bit value within a memory region + * @map: address to the bitmap memory region + * @start: bit offset of the value; may not be a multiple of 8 + * @nbits: number of bits to get + * + * Returns the @nbits-sized value located at the @start bit offset within the + * @map memory region. + */ +static inline unsigned long bitmap_get_value_unaligned(const unsigned long *map, + unsigned long start, + unsigned long nbits) +{ + const size_t index = BIT_WORD(start); + const unsigned long offset = start % BITS_PER_LONG; + const unsigned long carry = (offset + nbits) % BITS_PER_LONG; + unsigned long hi, lo, result; + + if (offset + nbits <= BITS_PER_LONG) { + result = map[index] >> (BITS_PER_LONG - offset - nbits); + return result & BITMAP_LAST_WORD_MASK(nbits); + } + + hi = map[index] & BITMAP_LAST_WORD_MASK(BITS_PER_LONG - offset); + lo = map[index + 1] & BITMAP_FIRST_WORD_MASK(BITS_PER_LONG - carry); + lo >>= (BITS_PER_LONG - carry); + return (hi << carry) | lo; +} + /** * bitmap_set_value8 - set an 8-bit value within a memory region * @map: address to the bitmap memory region @@ -599,6 +630,38 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value, map[index] |= value << offset; } +/** + * bitmap_set_value_unaligned - set an @nbits-bit value within a memory region + * @map: address to the bitmap memory region + * @value: the value up to BITS_PER_LONG bits (will be clamped to @nbits) + * @start: bit offset of the value; may not be a multiple of 8 + * @nbits: number of bits to set + */ +static inline void bitmap_set_value_unaligned(unsigned long *map, + unsigned long value, + unsigned long start, + unsigned long nbits) +{ + const size_t index = BIT_WORD(start); + const unsigned long offset = start % BITS_PER_LONG; + unsigned long mask = BITMAP_LAST_WORD_MASK(nbits); + const unsigned long carry = (offset + nbits) % BITS_PER_LONG; + + value &= mask; + if (offset + nbits <= BITS_PER_LONG) { + value <<= (BITS_PER_LONG - offset - nbits); + mask <<= (BITS_PER_LONG - offset - nbits); + map[index] &= ~mask; + map[index] |= value; + return; + } + map[index] &= ~BITMAP_LAST_WORD_MASK(BITS_PER_LONG - offset); + map[index] |= (value >> (carry)); + value &= BITMAP_LAST_WORD_MASK(carry); + map[index + 1] &= ~BITMAP_FIRST_WORD_MASK(BITS_PER_LONG - carry); + map[index + 1] |= value << (BITS_PER_LONG - carry); +} + #endif /* __ASSEMBLY__ */ #endif /* __LINUX_BITMAP_H */ From patchwork Thu Jul 13 12:57:02 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 119872 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp1818875vqm; Thu, 13 Jul 2023 06:18:57 -0700 (PDT) X-Google-Smtp-Source: APBJJlHMD3wXMzubm2h5zrGdka9Mv+LC7HoEaohJZ2usdCcrzc1vw42PaeUi3v8m0tXQmkBlL3l/ X-Received: by 2002:aa7:cd78:0:b0:51e:da3:1585 with SMTP id ca24-20020aa7cd78000000b0051e0da31585mr2398776edb.9.1689254337452; Thu, 13 Jul 2023 06:18:57 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689254337; cv=none; d=google.com; s=arc-20160816; b=JTE+1LxoD6FK57WxAZHT/4eBEqF69yAETspwWIFTvAIfu0CZN5lGz1YyXPwbY4WXjl jcz3+rlUlDNwBQDNqhjLFflwH7JhGJToN/zbdWQN/EyltHzlQm7PU0VbV/U58ZpGBBIU wd6Ffd033H+aZQsBFvqd83ZfGa4nwpuBiJp3wWZfu7b0IxtGPXP4/RGJTn5VJsetE8tW zAkterbAw8vhqFpdCxpka0KLIAtIFRnunvNI/qFHchOm/y3IQuvAceXmBq4zE3W4Lacq 8wliGPJqiV0fQBBu2TBwfhayAceX6OdPfyMjdehQnVl7kHzWlgn5Ya76eOGdAdk1dmOO oyHQ== 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=jmq0b/Ecy0ZNTUuWhSR14tYQI4JHnYovo+aDrld9UN0=; fh=w2imRfrBx7xgrqExMhNQwXd/bCFo2iqBwf34S5/AxrI=; b=kD72zoxuNIW0mHGL+bidyaM3qY/fK+6JLDuU1XwruOvIV6Pzfm/QorOp4MEjV1irH+ FYT3ccSFbGAuVpIQXuhUlxu5KSEojLQj95VltlYgzTzshzcxaeMId4Bpzo/a6tFuTbrO KAJYyPy38RPPLC8nA46tVASDiTzR0J14cIrmLTWBBmTi/jt8pGgzS+Mc9EkUJekXS+Uu 8kcHcrqeAzX5b8/l1Ehc6FaeMMQngv3KYsAo6kziuthTyR7Xs0NwKdxsZlLtxhKzXyRg 0jsNK+RgOXTyyddWsUiUaNWUBhmprQHU7f+961e2JMGo2pIb0KNUt4AK7DpA1BCpeBSU 0c8A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=CgGc1u5q; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 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 (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id v13-20020aa7d80d000000b0051fde01961dsi4302970edq.667.2023.07.13.06.18.33; Thu, 13 Jul 2023 06:18:57 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=CgGc1u5q; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234892AbjGMM5p (ORCPT + 99 others); Thu, 13 Jul 2023 08:57:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36432 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234869AbjGMM5f (ORCPT ); Thu, 13 Jul 2023 08:57:35 -0400 Received: from mail-ed1-x54a.google.com (mail-ed1-x54a.google.com [IPv6:2a00:1450:4864:20::54a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A233D1BEB for ; Thu, 13 Jul 2023 05:57:33 -0700 (PDT) Received: by mail-ed1-x54a.google.com with SMTP id 4fb4d7f45d1cf-51e288d2a40so428793a12.1 for ; Thu, 13 Jul 2023 05:57:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689253052; x=1691845052; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=jmq0b/Ecy0ZNTUuWhSR14tYQI4JHnYovo+aDrld9UN0=; b=CgGc1u5qyG9QHrPLJIfRm5/iPctCseTN5qUO7jdfNfbBcVi7VSxsjYA0omtf3+hxMV cXIv7arRK7gICiBo+wRZ0QeyQM5TkdW7LR6MVSqklD70rENHC3Kn/OtihQiIfy9xaTzN wW1b3m2v3U+lURK1LCBKW57m2ukspaRu3Y2VcJaSk1BrbVheIGUBDjMQNvUI6bj/s6Gn nguC8zsoqWo8SifiF54s/ew9mLcz7zKfklVijPUvCFpOFSCLihYXTnHFenJclDY06PxO /stMdLKDH8TjLnFVY9UeQTLsN2IhCEKY0G+QXw3TBsoATXET5UrQenfGfZNKL2ULWiKi IhoA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689253052; x=1691845052; 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=jmq0b/Ecy0ZNTUuWhSR14tYQI4JHnYovo+aDrld9UN0=; b=ZFwwwloSREP5JtZO6JrzwfOSdv+5khZXltKsKgQ3TuRH75dz315QRtcUqenaPEsgVq 2HJ46fd1exA1xf69oYfzUPpViPGrN6vSZVuAGSYrx7R6JOwiv754JvlbGXjdYix+kDCB E8go6dpNI9XoYYURiXL7vvo5E2UMBngA0vYknlfNhcY7iRgjuOAUYbbw9c/THz3/4ySp iNyVYQUDKwYXnDW/SsIdU8RFTUhURJyiOLGPV6l/5nNA8yRDLNDf3rnxLjTT90WZztu7 phwPWZbHMUwxomQKE/FxwIweMV5lOXoDmLAUJRHHtxCEYAS4TTqDAbsNi2Brjr3M6o5k zsJw== X-Gm-Message-State: ABy/qLZ3Rb0YIZnwZNbPiDu932z2HNnIo/Eb9bHOhFDCn3aZsfyM98yP Rfp1wZFqduw5R1ihPna3zCV5YnBOIfs= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:7a88:66b7:31e5:7d85]) (user=glider job=sendgmr) by 2002:a50:f688:0:b0:51e:23e9:5c85 with SMTP id d8-20020a50f688000000b0051e23e95c85mr7587edn.6.1689253052246; Thu, 13 Jul 2023 05:57:32 -0700 (PDT) Date: Thu, 13 Jul 2023 14:57:02 +0200 In-Reply-To: <20230713125706.2884502-1-glider@google.com> Mime-Version: 1.0 References: <20230713125706.2884502-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230713125706.2884502-3-glider@google.com> Subject: [v2 2/5] lib/test_bitmap: add tests for bitmap_{set,get}_value_unaligned 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, linux@rasmusvillemoes.dk, yury.norov@gmail.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771311555703895857 X-GMAIL-MSGID: 1771311555703895857 Add basic tests ensuring that values can be added at arbitrary positions of the bitmap, including those spanning into the adjacent unsigned longs. Signed-off-by: Alexander Potapenko --- lib/test_bitmap.c | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 187f5b2db4cf1..8ca61f6e7f26e 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -71,6 +71,17 @@ __check_eq_uint(const char *srcfile, unsigned int line, return true; } +static bool __init +__check_eq_ulong(const char *srcfile, unsigned int line, + const unsigned long exp_ulong, unsigned long x) +{ + if (exp_ulong != x) { + pr_err("[%s:%u] expected %lu, got %lu\n", + srcfile, line, exp_ulong, x); + return false; + } + return true; +} static bool __init __check_eq_bitmap(const char *srcfile, unsigned int line, @@ -186,6 +197,7 @@ __check_eq_str(const char *srcfile, unsigned int line, }) #define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__) +#define expect_eq_ulong(...) __expect_eq(ulong, ##__VA_ARGS__) #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__) #define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__) #define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__) @@ -1222,6 +1234,26 @@ static void __init test_bitmap_const_eval(void) BUILD_BUG_ON(~var != ~BIT(25)); } +static void __init test_set_get_value_unaligned(void) +{ + DECLARE_BITMAP(bitmap, BITS_PER_LONG * 2); + unsigned long val; + int i; + + for (i = 0; i < BITS_PER_LONG * 2 - 7; i++) { + bitmap_zero(bitmap, BITS_PER_LONG * 2); + bitmap_set_value_unaligned(bitmap, 0b10101UL, i, 5); + val = bitmap_get_value_unaligned(bitmap, i, 5); + expect_eq_ulong(0b10101UL, val); + bitmap_set_value_unaligned(bitmap, 0b101UL, i + 5, 3); + val = bitmap_get_value_unaligned(bitmap, i + 5, 3); + expect_eq_ulong(0b101UL, val); + val = bitmap_get_value_unaligned(bitmap, i, 8); + expect_eq_ulong(0b10101101UL, val); + } +} + + static void __init selftest(void) { test_zero_clear(); @@ -1249,6 +1281,8 @@ static void __init selftest(void) test_for_each_clear_bitrange_from(); test_for_each_set_clump8(); test_for_each_set_bit_wrap(); + + test_set_get_value_unaligned(); } KSTM_MODULE_LOADERS(test_bitmap); From patchwork Thu Jul 13 12:57:03 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 119883 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp1821014vqm; Thu, 13 Jul 2023 06:22:16 -0700 (PDT) X-Google-Smtp-Source: APBJJlHzaF90Ng/ZClgq+4SCO4s2V99ztSMd5ncFtyHjmAWbslKTRc48IqgWmM9XhXIh0/dNkw6P X-Received: by 2002:a17:906:9614:b0:965:d18b:f03a with SMTP id s20-20020a170906961400b00965d18bf03amr1395894ejx.58.1689254535685; Thu, 13 Jul 2023 06:22:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689254535; cv=none; d=google.com; s=arc-20160816; b=R5kknPR70OwYLBTZcfyKqXDGFKQBmMQ3QZ/6GzXZmUe/gxvDuk5fMp/Bp1gpuZLmSd F+GvvyhuowWg1g9P5EsgUCAj1u9LubGTanN3oppZISoxvR0zl3g2pB7FUXiSsAe5Bbzo mVedcUXLvEcx3aH5K35/pTIRxRAg9ut4VGJhl1TLKYIXRYYPIXF7uqlBLl1mb30T425u dLVbhjFTBxGW9bC/gI3hcwr91QNetG9sszwKW1Q23rdC8JqkPOJl3n2a4q1SWuTbxqDH 7X80lVs50IOKgCVqoAqthPKwhby/KnaUptDnIkpH1oTAF+kAalfmVDgYSaItZgc11Zum N78w== 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=gj4eacZ7u0TYs1+VtoNyY+f/L6MZ9TJLIuNpJdtqlH8=; fh=w2imRfrBx7xgrqExMhNQwXd/bCFo2iqBwf34S5/AxrI=; b=yyTIIkPliE1doc6Pzedm/qE/cJ52TT3+OlCXg6FXOaIabLuVhUe5Tt8WOdixyQF7ad QCrsqyGgND7bp5hI12f3ic/XCK2g7x7IQ4153WlsWhg/epWysbMVOfJxyu9hBYcwAZlL OMTQrOt1hdn0NWtPRXF1/n5W2+YLUA69wxc9+G4D/H8rYvpjaZ3S8Kz8jWcVM2ViT+tu xyhL4cQe0aGTeS1lrCZOg+bqQEbYvW/YEfvyMjs9kFlt6osZVCB1Fz+SvEOc0+KwWrpN wOwsYiSgsMbTqjhFyzlYfOtDcOXs+qJ8/J7bNDWJ2GIJCFKNl8QKqpah+zJbupqn1fDh iWVg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=vWSzm6Vm; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 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 (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id j13-20020a170906094d00b00992d262f9f7si7369574ejd.933.2023.07.13.06.21.49; Thu, 13 Jul 2023 06:22:15 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=vWSzm6Vm; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234893AbjGMM5u (ORCPT + 99 others); Thu, 13 Jul 2023 08:57:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36450 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234059AbjGMM5i (ORCPT ); Thu, 13 Jul 2023 08:57:38 -0400 Received: from mail-yb1-xb4a.google.com (mail-yb1-xb4a.google.com [IPv6:2607:f8b0:4864:20::b4a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D2BE0173B for ; Thu, 13 Jul 2023 05:57:35 -0700 (PDT) Received: by mail-yb1-xb4a.google.com with SMTP id 3f1490d57ef6-c6dd0e46a52so596908276.2 for ; Thu, 13 Jul 2023 05:57:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689253055; x=1691845055; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=gj4eacZ7u0TYs1+VtoNyY+f/L6MZ9TJLIuNpJdtqlH8=; b=vWSzm6VmSUHA1eKL56ezPYbSxbiC4K2GMyF9+/+iS1xukhlImcrV8hhIQKjKxrkKtr RXwzzKVIU9lSsP4iQjQjHRJ2L8rG9Svuhpb1PHBcVU/abOFQKT6MQQClFj/F/pAPvMXJ dLr7katuacqVhZiYQrzyn3vRjR7P3uyYSce8Efg/KnBxau//aNmCIJVG7Zzoh6Qf8XWv UXEpNsagWFCUiCdpvlWZYXJLDgKj0QrvUUZRntY8Xp3jNz3YKj8Ez57uv+WWmSHzY2eu 8BCChYRDAJ2jr9aZbn48Qynyz+/WDqFRLwOYhFX+hju1EIpoO/lqyU6/ujBzrjrslw3V V7sw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689253055; x=1691845055; 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=gj4eacZ7u0TYs1+VtoNyY+f/L6MZ9TJLIuNpJdtqlH8=; b=UyLiloJdbcO5ewyj8NVKvhy3vc834Ids0t3hZmL7MU5O+ARtZ7oeQY+tavXqRVJgat 9XLYoeephZXItbBME7qiyHMpORxRex+zoYY657Hw2kPRWxftDOp/Ys/5UdR/wSyjlpqR ZEg41TNrFaVghmdKHTAWRJrTOvNvfqBaFCrR8E6ryK2miN+MhLLmziqTVqT0BUcCBSpS Hf7XMyTq2WYStTg2+EiF8jiXswBEvIysvhwM66So7Wn+jYERFb35UmO77jtYxBrPHKoh 8rGnQKetBl/yGlsyABMqgyV4jQTpVuG7clHCYpsiFlOJGtnJWMoZ0Lwj6nl09VoVM+n9 mv9A== X-Gm-Message-State: ABy/qLZXeiu/Yxe6ZHiO+qxKApe2vgskV9h9KdW0h6UcquI6SYkKS6S8 GAKGzG+YVdUam1n1BALnBtGDZ5bWKfY= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:7a88:66b7:31e5:7d85]) (user=glider job=sendgmr) by 2002:a05:6902:1ce:b0:c85:d53:2aef with SMTP id u14-20020a05690201ce00b00c850d532aefmr6871ybh.12.1689253055149; Thu, 13 Jul 2023 05:57:35 -0700 (PDT) Date: Thu, 13 Jul 2023 14:57:03 +0200 In-Reply-To: <20230713125706.2884502-1-glider@google.com> Mime-Version: 1.0 References: <20230713125706.2884502-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230713125706.2884502-4-glider@google.com> Subject: [v2 3/5] 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, linux@rasmusvillemoes.dk, yury.norov@gmail.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771311763717917177 X-GMAIL-MSGID: 1771311763717917177 The config implements the EA0 algorithm suggested by Evgenii Stepanov to compress the memory tags for ARM MTE during swapping. The algorithm is based on RLE and specifically targets 128-byte buffers of tags corresponding to a single page. In the common case 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 --- v2: - as suggested by Yuri Norov, switched from struct bitq (which is not needed anymore) to - add missing symbol exports --- arch/arm64/Kconfig | 10 + arch/arm64/include/asm/mtecomp.h | 60 +++++ arch/arm64/mm/Makefile | 1 + arch/arm64/mm/mtecomp.c | 412 +++++++++++++++++++++++++++++++ 4 files changed, 483 insertions(+) create mode 100644 arch/arm64/include/asm/mtecomp.h create mode 100644 arch/arm64/mm/mtecomp.c diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig index 7856c3a3e35af..0aa727888e746 100644 --- a/arch/arm64/Kconfig +++ b/arch/arm64/Kconfig @@ -2091,6 +2091,16 @@ 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 MTE" + default y + depends on ARM64_MTE + help + Enable tag compression support for ARM64 MTE. + + 128-byte tag buffers corresponding to 4K pages can be compressed using + the EA0 algorithm to save heap 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..65a3730cc50d9 --- /dev/null +++ b/arch/arm64/include/asm/mtecomp.h @@ -0,0 +1,60 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#ifndef __ASM_MTECOMP_H +#define __ASM_MTECOMP_H + +#include + +/* + * ea0_compress() - compress the given tag array. + * @tags: 128-byte array to read the tags from. + * + * Compresses the tags and returns a 64-bit opaque handle pointing to the + * tag storage. May allocate memory, which is freed by @ea0_release_handle(). + */ +u64 ea0_compress(u8 *tags); + +/* + * ea0_decompress() - decompress the tag array addressed by the handle. + * @handle: handle returned by @ea0_decompress() + * @tags: 128-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 on error. + */ +bool ea0_decompress(u64 handle, u8 *tags); + +/* + * ea0_release_handle() - release the handle returned by ea0_compress(). + * @handle: handle returned by ea0_compress(). + */ +void ea0_release_handle(u64 handle); + +/* Functions below are exported for testing purposes. */ + +/* + * ea0_storage_size() - calculate the memory occupied by compressed tags. + * @handle: storage handle returned by ea0_compress. + */ +int ea0_storage_size(u64 handle); + +/* + * ea0_tags_to_ranges() - break @tags into arrays of tag ranges. + * @tags: 128-byte array containing 256 MTE tags. + * @out_tags: u8 array to store the tag of every range. + * @out_sizes: u16 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[]). + */ +void ea0_tags_to_ranges(u8 *tags, u8 *out_tags, short *out_sizes, int *out_len); + +/* + * ea0_ranges_to_tags() - fill @tags using given tag ranges. + * @r_tags: u8[256] containing the tag of every range. + * @r_sizes: u16[256] containing the size of every range. + * @r_len: length of @r_tags and @r_sizes. + * @tags: 128-byte array to write the tags to. + */ +void ea0_ranges_to_tags(u8 *r_tags, short *r_sizes, int r_len, u8 *tags); + +#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..e6c1026bd7e89 --- /dev/null +++ b/arch/arm64/mm/mtecomp.c @@ -0,0 +1,412 @@ +// SPDX-License-Identifier: GPL-2.0-only + +/* + * MTE tag compression algorithm. + * Proposed by Evgenii Stepanov + */ + +/* + * EA0 stands for "Evgenii's Algorithm 0", as the initial proposal contained two + * compression algorithms. + * + * The algorithm attempts to compress a 128-byte (MTE_GRANULES_PER_PAGE / 2) + * array of tags into a smaller byte sequence that can be stored in a + * 16-, 32-, or 64-byte buffer. A special case is storing the tags inline in + * an 8-byte pointer. + * + * We encapsulate tag storage memory management in this module, because it is + * tightly coupled with the pointer representation. + * ea0_compress(*tags) takes a 128-byte buffer and returns an opaque value + * that can be stored in Xarray + * ea_decompress(*ptr, *tags) takes the opaque value and loads the tags into + * the provided 128-byte buffer. + * + * + * + * The compression algorithm works as follows. + * + * 1. The input array of 128 bytes is transformed into tag ranges (two arrays: + * @r_tags containing tag values and @r_sizes containing range lengths) by + * ea0_tags_to_ranges(). Note that @r_sizes sums up to 256. + * + * 2. Depending on the number N of ranges, the following storage class is picked: + * N <= 6: 8 bytes (inline case, no allocation required); + * 6 < N <= 11: 16 bytes + * 11 < N <= 23: 32 bytes + * 23 < N <= 46: 64 bytes + * 46 < N: 128 bytes (no compression will be performed) + * + * 3. 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 is greater than 127. + * + * 4. For the inline case, the following values are stored in the 8-byte handle: + * largest_idx : i4 + * r_tags[0..5] : i4 x 6 + * r_sizes[0..4] : i7 x 5 + * (if N is less than 6, @r_tags and @r_sizes are padded up with zero values) + * + * Because @largest_idx is <= 5, bit 63 of the handle is always 0 (so it can + * be stored in the Xarray), and bits 62..60 cannot all be 1, so it can be + * distinguished from a kernel pointer. + * + * 5. For the out-of-line case, the storage is allocated from one of the + * "mte-tags-{16,32,64,128}" kmem caches. The resulting pointer is aligned + * on 8 bytes, so its bits 2..0 can be used to store the size class: + * - 0 for 128 bytes + * - 1 for 16 + * - 2 for 32 + * - 4 for 64. + * Bit 63 of the pointer is zeroed out, so that it can be stored in Xarray. + * + * 6. The data layout in the allocated storage is as follows: + * largest_idx : i6 + * r_tags[0..N] : i4 x N + * r_sizes[0..N-1] : i7 x (N-1) + * + * + * + * The decompression algorithm performs the steps below. + * + * 1. Decide if data is stored inline (bits 62..60 of the handle != 0b111) or + * out-of line. + * + * 2. For the inline case, treat the handle itself as the input buffer. + * + * 3. For the out-of-line case, look at bits 2..0 of the handle to understand + * the input buffer length. To obtain the pointer to the input buffer, unset + * bits 2..0 of the handle and set bit 63. + * + * 4. If the input buffer is 128 byte long, copy its contents to the output + * buffer. + * + * 5. Otherwise, read @largest_idx, @r_tags and @r_sizes from the input buffer. + * Calculate the removed largest element of @r_sizes: + * largest = 256 - sum(r_sizes) + * and insert it into @r_sizes at position @largest_idx. + * + * 6. While @r_sizes[i] > 0, add a 4-bit value @r_tags[i] to the output buffer + * @r_sizes[i] times. + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +/* The handle must fit into an Xarray value. */ +#define HANDLE_MASK ~(BIT_ULL(63)) + +/* Out-of-line handles have 0b111 in bits 62..60. */ +#define NOINLINE_MASK (BIT_ULL(62) | BIT_ULL(61) | BIT_ULL(60)) + +/* Cache index is stored in the lowest pointer bits. */ +#define CACHE_ID_MASK (BIT_ULL(2) | BIT_ULL(1) | BIT_ULL(0)) + +/* Four separate caches to store out-of-line data. */ +#define NUM_CACHES 4 +static struct kmem_cache *mtecomp_caches[NUM_CACHES]; + +/* Translate allocation size into mtecomp_caches[] index. */ +static int ea0_size_to_cache_id(int len) +{ + switch (len) { + case 16: + return 1; + case 32: + return 2; + case 64: + return 3; + default: + return 0; + } +} + +/* Translate mtecomp_caches[] index into allocation size. */ +static int ea0_cache_id_to_size(int id) +{ + switch (id) { + case 1: + return 16; + case 2: + return 32; + case 3: + return 64; + default: + return 128; + } +} + +/* Transform tags into tag ranges. */ +void ea0_tags_to_ranges(u8 *tags, u8 *out_tags, short *out_sizes, int *out_len) +{ + u8 prev_tag = 0xff; + int cur_idx = -1; + u8 cur_tag; + int i; + + memset(out_tags, 0, *out_len * sizeof(*out_tags)); + memset(out_sizes, 0, *out_len * sizeof(*out_sizes)); + for (i = 0; i < MTE_GRANULES_PER_PAGE; i++) { + cur_tag = tags[i / 2]; + if (i % 2) + cur_tag = cur_tag % 16; + else + cur_tag = cur_tag / 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(ea0_tags_to_ranges); + +/* Transform tag ranges back into tags. */ +void ea0_ranges_to_tags(u8 *r_tags, short *r_sizes, int r_len, u8 *tags) +{ + 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 == 0) + prev = r_tags[i]; + else + tags[pos / 2] = (prev << 4) | r_tags[i]; + pos++; + } + } +} +EXPORT_SYMBOL(ea0_ranges_to_tags); + +/* Translate @num_ranges into the allocation size needed to hold them. */ +static int ea0_alloc_size(int num_ranges) +{ + if (num_ranges <= 6) + return 8; + if (num_ranges <= 11) + return 16; + if (num_ranges <= 23) + return 32; + if (num_ranges <= 46) + return 64; + return 128; +} + +/* Translate allocation size into maximum number of ranges that it can hold. */ +static int ea0_size_to_ranges(int size) +{ + switch (size) { + case 8: + return 6; + case 16: + return 11; + case 32: + return 23; + case 64: + return 46; + default: + return 0; + } +} + +/* Is the data stored inline in the handle itself? */ +static bool ea0_is_inline(u64 handle) +{ + return (handle & NOINLINE_MASK) != NOINLINE_MASK; +} + +/* Get the size of the buffer backing @handle. */ +int ea0_storage_size(u64 handle) +{ + if (ea0_is_inline(handle)) + return 8; + return ea0_cache_id_to_size(handle & CACHE_ID_MASK); +} +EXPORT_SYMBOL(ea0_storage_size); + +/* Compress ranges into the buffer of the given length. */ +static void ea0_compress_to_buf(int len, u8 *tags, short *sizes, u8 *buf, + int buflen) +{ + int largest_idx = -1, i; + short largest = 0; + unsigned long bit_pos = 0; + + for (i = 0; i < len; i++) { + if (i == len) + break; + if (sizes[i] > largest) { + largest = sizes[i]; + largest_idx = i; + } + } + if (len <= 6) { + /* Inline case, @buflen <= 8. */ + bitmap_set_value_unaligned((unsigned long *)buf, largest_idx, + bit_pos, 4); + bit_pos += 4; + } else { + bitmap_set_value_unaligned((unsigned long *)buf, largest_idx, + bit_pos, 6); + bit_pos += 6; + } + for (i = 0; i < len; i++) { + bitmap_set_value_unaligned((unsigned long *)buf, tags[i], + bit_pos, 4); + bit_pos += 4; + } + for (i = len; i < ea0_size_to_ranges(buflen); i++) { + bitmap_set_value_unaligned((unsigned long *)buf, 0, bit_pos, 4); + bit_pos += 4; + } + for (i = 0; i < len; i++) { + if (i == largest_idx) + continue; + bitmap_set_value_unaligned((unsigned long *)buf, sizes[i], + bit_pos, 7); + bit_pos += 7; + } +} + +/* Compress the data inline. */ +static u64 ea0_compress_inline(int len, u8 *tags, short *sizes) +{ + u64 result; + + ea0_compress_to_buf(len, tags, sizes, (u8 *)&result, sizeof(result)); + result = be64_to_cpu(result); + return result; +} + +/* Compress @tags and return a handle. */ +u64 ea0_compress(u8 *tags) +{ + int alloc_size, cache_id; + struct kmem_cache *cache; + short r_sizes[256]; + u8 r_tags[256]; + int r_len = ARRAY_SIZE(r_tags); + u8 *storage; + + ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len); + alloc_size = ea0_alloc_size(r_len); + if (alloc_size == 8) + return ea0_compress_inline(r_len, r_tags, r_sizes); + cache_id = ea0_size_to_cache_id(alloc_size); + cache = mtecomp_caches[cache_id]; + storage = kmem_cache_alloc(cache, GFP_KERNEL); + if (alloc_size < 128) { + ea0_compress_to_buf(r_len, r_tags, r_sizes, storage, + alloc_size); + return ((u64)storage | cache_id) & HANDLE_MASK; + } + memcpy(storage, tags, alloc_size); + return (u64)storage & HANDLE_MASK; +} +EXPORT_SYMBOL(ea0_compress); + +/* Decompress the contents of the given buffer into @tags. */ +static bool ea0_decompress_from_buf(u8 *buf, int buflen, u8 *tags) +{ + int largest_idx, i, r_len = ea0_size_to_ranges(buflen); + short r_sizes[46], sum = 0; + u8 r_tags[46]; + unsigned long bit_pos = 0, l_bits = (buflen == 8) ? 4 : 6; + + largest_idx = bitmap_get_value_unaligned((unsigned long *)buf, bit_pos, + l_bits); + bit_pos += l_bits; + for (i = 0; i < r_len; i++) { + r_tags[i] = bitmap_get_value_unaligned((unsigned long *)buf, + bit_pos, 4); + bit_pos += 4; + } + for (i = 0; i < r_len; i++) { + if (i == largest_idx) + continue; + r_sizes[i] = bitmap_get_value_unaligned((unsigned long *)buf, + bit_pos, 7); + bit_pos += 7; + if (!r_sizes[i]) { + r_len = i; + break; + } + sum += r_sizes[i]; + } + if (sum >= 256) + return false; + r_sizes[largest_idx] = 256 - sum; + ea0_ranges_to_tags(r_tags, r_sizes, r_len, tags); + return true; +} + +/* Get pointer to the out-of-line storage from a handle. */ +static void *ea0_storage(u64 handle) +{ + if (ea0_is_inline(handle)) + return NULL; + return (void *)((handle & (~CACHE_ID_MASK)) | BIT_ULL(63)); +} + +/* Decompress tags from the buffer referenced by @handle. */ +bool ea0_decompress(u64 handle, u8 *tags) +{ + u8 *storage = ea0_storage(handle); + int size = ea0_storage_size(handle); + + if (size == 128) { + memcpy(tags, storage, size); + return true; + } + if (size == 8) { + handle = cpu_to_be64(handle); + return ea0_decompress_from_buf((u8 *)&handle, sizeof(handle), + tags); + } + return ea0_decompress_from_buf(storage, size, tags); +} +EXPORT_SYMBOL(ea0_decompress); + +/* Release the memory referenced by @handle. */ +void ea0_release_handle(u64 handle) +{ + void *storage = ea0_storage(handle); + int size = ea0_storage_size(handle); + struct kmem_cache *c; + + if (!handle || !storage) + return; + + c = mtecomp_caches[ea0_size_to_cache_id(size)]; + kmem_cache_free(c, storage); +} +EXPORT_SYMBOL(ea0_release_handle); + +/* Set up mtecomp_caches[]. */ +static int mtecomp_init(void) +{ + char name[16]; + int size; + int i; + + for (i = 0; i < NUM_CACHES; i++) { + size = ea0_cache_id_to_size(i); + snprintf(name, ARRAY_SIZE(name), "mte-tags-%d", size); + mtecomp_caches[i] = + kmem_cache_create(name, size, size, 0, NULL); + } + return 0; +} + +module_init(mtecomp_init); From patchwork Thu Jul 13 12:57:04 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 119874 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp1819678vqm; Thu, 13 Jul 2023 06:20:13 -0700 (PDT) X-Google-Smtp-Source: APBJJlH7SEIhFlPntOD8aeCycmFbMmtz51H2+o08C5K7LO4yGwiuYDDRQIpU2Lr/U2y0YA4bIR0g X-Received: by 2002:aa7:c696:0:b0:51d:9127:b61d with SMTP id n22-20020aa7c696000000b0051d9127b61dmr1610368edq.25.1689254412721; Thu, 13 Jul 2023 06:20:12 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689254412; cv=none; d=google.com; s=arc-20160816; b=hx8Qry6jpMLdNLYZkmnw61/O5WQYfReqkkdRP9CPNzPnhN/rvbFD6PDrBAN5Qt7gD5 asNJO7bBvhJxjhvIde2zru2vOEhZykuaRzCYO8jARIQao8CaMbPEq3o1R1Ox5czINv6w 1ns3gC50h1jIHYvtFkIFopYdATSUYF8/wqX2n0y7L4ebUsNio593rEqIToFDr5N4bG7b 1cmCULN92plXU8e1v2s9WdmZzIXH3ZoNmebLHom3kccBzjD+6EU7F6/iqFt1xaaeR5co MQk/14l4uwS5v1nn6anwga9krSm73C/1uLNskiu4S+/bl2bwYnZ4WCf7GBL2XvGTT81b ykTQ== 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=d0jpwRf4aooZIScI07t3xs6wVcncXV8ha+jtsM7z/nQ=; fh=w2imRfrBx7xgrqExMhNQwXd/bCFo2iqBwf34S5/AxrI=; b=BsylRUVP5rNZ4orfS5epLqiDHovNtJQmbTg6hUwg47Et/cfrF1l1TwLHq5KTrYiLti LT8Q2WLDBnefRcBcfDKU6/69aO+Oh7Bhf/lG5Y8j3sWgGa6xWRHsLxOMWt9BgvcoKFsZ Ix4Qdh1cr5Wc7OHZXfwZpxAgz8INVCtiiiXBl1kGBVHAUCM9vrx/yoaFNTL3bSbwdH+K Fe1kGRlYE16q5arD2fr5hzjuOsO0Q/5quMjp1ghdbKAnbideEd+I625wRBIxURznBde0 zufoBR4/BkYxDHr1zF8YKIQtjJjvOCDN6PXALfNMpLqfT4DI7qtsmT32vZrCE/KUaEXP zcDg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=nFut6631; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 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 (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id r4-20020aa7cb84000000b0051e248ee5c1si582029edt.670.2023.07.13.06.19.48; Thu, 13 Jul 2023 06:20:12 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=nFut6631; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234926AbjGMM5w (ORCPT + 99 others); Thu, 13 Jul 2023 08:57:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36482 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234872AbjGMM5k (ORCPT ); Thu, 13 Jul 2023 08:57:40 -0400 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BD27C1BF2 for ; Thu, 13 Jul 2023 05:57:38 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-57745160c1dso5380217b3.2 for ; Thu, 13 Jul 2023 05:57:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689253058; x=1691845058; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=d0jpwRf4aooZIScI07t3xs6wVcncXV8ha+jtsM7z/nQ=; b=nFut6631mjTAOgoR2gmPO5GuPVrlue6cjFmK0Ckm5EHc1cyNxNvCm7zUisrJUudi1Q RaJfyJrG0ZyT23FTrv4ZQ2u3vCeDeY9i+LFL+UjY3Ji2cDc16BUgWsvwdFpI6dmskqxV zN/V0IGNr3ysyGnjLnXraW1y0c5RTebqiT/GgQ57HeRuBFGmUSpeB95fetfLdjYshFGb iiGAtpAwoa74rMDdCjZ1VL4Ta9wx8L6QFix6f8AyL/hxxrU7NhonaHUwja4szt1l38Yq yiTc6BEfBm1Fug9yt3vIEsAw7Abg6UTXnQGxowd/VeOy+l0ArYkwl7tAJuwQQ/E+b8wj Lorg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689253058; x=1691845058; 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=d0jpwRf4aooZIScI07t3xs6wVcncXV8ha+jtsM7z/nQ=; b=fq17y5ugWHfWe8NUmTwVSJwx6zkHX2BDTyEvIruw0nh5iCduOv+tB6/d9lR20C77JC nADrGEjjpP2pkP4eqFc0J7hUElALKflto2KmA/udfWLi9dEQ8VUVCfXju5NKIqMlJPVs KqkENuPtue+6NsyhZQCuYZru0NYe6P6vW8QJiQ2vCq70suN5XfHyCBv2cNEbEU/dj6ni 7nJrSx4S8IcqELnQNXjZdXwBmJYxLAz/vFxyU8fxsO3xV/jwvK2WR82TAloRDRcnMiR0 miHR5e7lKMSMKnAO40lS6Ixb7qV50xrscVZHZ+DSiO8sMRzo4lP5GSEBT21SxoCKPUxb cVGA== X-Gm-Message-State: ABy/qLYAuSvi1D5rdccn/Dong7gXtVW+l0m2bbgeoqKfJByl/WWXMZmG AZ/BGw30Q28nCTUnKsMG+NI7RRowZoo= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:7a88:66b7:31e5:7d85]) (user=glider job=sendgmr) by 2002:a05:6902:1c4:b0:cab:9746:ef0e with SMTP id u4-20020a05690201c400b00cab9746ef0emr6467ybh.12.1689253058041; Thu, 13 Jul 2023 05:57:38 -0700 (PDT) Date: Thu, 13 Jul 2023 14:57:04 +0200 In-Reply-To: <20230713125706.2884502-1-glider@google.com> Mime-Version: 1.0 References: <20230713125706.2884502-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230713125706.2884502-5-glider@google.com> Subject: [v2 4/5] 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, linux@rasmusvillemoes.dk, yury.norov@gmail.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771311635075944387 X-GMAIL-MSGID: 1771311635075944387 Ensure that tag sequences containing alternating values are compressed to buffers of expected size and correctly decompressed afterwards. Signed-off-by: Alexander Potapenko --- arch/arm64/Kconfig | 10 ++ arch/arm64/mm/Makefile | 1 + arch/arm64/mm/test_mtecomp.c | 175 +++++++++++++++++++++++++++++++++++ 3 files changed, 186 insertions(+) create mode 100644 arch/arm64/mm/test_mtecomp.c diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig index 0aa727888e746..9473c1e2e8593 100644 --- a/arch/arm64/Kconfig +++ b/arch/arm64/Kconfig @@ -2101,6 +2101,16 @@ config ARM64_MTE_COMP 128-byte tag buffers corresponding to 4K pages can be compressed using the EA0 algorithm to save heap memory. +config ARM64_MTE_COMP_KUNIT_TEST + tristate "Test tag compression for ARM64 MTE" if !KUNIT_ALL_TESTS + default KUNIT_ALL_TESTS + depends on KUNIT && ARM64_MTE_COMP + help + Test EA0 compression algorithm enabled by CONFIG_ARM64_MTE_COMP. + + Ensure that tag sequences containing alternating values are compressed + to buffers of expected size 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..67bef6f28dac4 --- /dev/null +++ b/arch/arm64/mm/test_mtecomp.c @@ -0,0 +1,175 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Test cases for EA0, the compression algorithm for MTE tags. + */ + +#include +#include +#include +#include + +/* + * Test that ea0_tags_to_ranges() produces a single range for a zero-filled tag + * buffer. + */ +static void test_tags_to_ranges_zero(struct kunit *test) +{ + u8 tags[128], dtags[128]; + short r_sizes[256]; + int r_len = 256; + u8 r_tags[256]; + + memset(tags, 0, 128); + ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len); + KUNIT_EXPECT_EQ(test, r_len, 1); + KUNIT_EXPECT_EQ(test, r_tags[0], 0); + KUNIT_EXPECT_EQ(test, r_sizes[0], 256); + ea0_ranges_to_tags(r_tags, r_sizes, r_len, dtags); + KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0); +} + +/* + * Test that a small number of different tags is correctly transformed into + * ranges. + */ +static void test_tags_to_ranges_simple(struct kunit *test) +{ + u8 tags[128], dtags[128]; + const u8 ex_tags[] = { 0xa, 0x0, 0xa, 0xb, 0x0 }; + const short ex_sizes[] = { 1, 2, 2, 1, 250 }; + short r_sizes[256]; + int r_len = 256; + u8 r_tags[256]; + + memset(tags, 0, 128); + tags[0] = 0xa0; + tags[1] = 0x0a; + tags[2] = 0xab; + ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len); + KUNIT_EXPECT_EQ(test, r_len, 5); + KUNIT_EXPECT_EQ(test, memcmp(r_tags, ex_tags, sizeof(ex_tags)), 0); + KUNIT_EXPECT_EQ(test, memcmp(r_sizes, ex_sizes, sizeof(ex_sizes)), 0); + ea0_ranges_to_tags(r_tags, r_sizes, r_len, dtags); + KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0); +} + +/* Test that repeated 0xa0 byte produces 256 ranges of length 1. */ +static void test_tags_to_ranges_repeated(struct kunit *test) +{ + u8 tags[128], dtags[128]; + short r_sizes[256]; + int r_len = 256; + u8 r_tags[256]; + + memset(tags, 0xa0, 128); + ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len); + KUNIT_EXPECT_EQ(test, r_len, 256); + ea0_ranges_to_tags(r_tags, r_sizes, r_len, dtags); + KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0); +} + +/* Test that a zero-filled array is compressed into inline storage. */ +static void test_compress_zero(struct kunit *test) +{ + u8 tags[128], dtags[128]; + u64 handle; + + memset(tags, 0, 128); + handle = ea0_compress(tags); + KUNIT_EXPECT_EQ(test, handle & BIT_ULL(63), 0); + /* Tags are stored inline. */ + KUNIT_EXPECT_EQ(test, ea0_storage_size(handle), 8); + KUNIT_EXPECT_TRUE(test, ea0_decompress(handle, dtags)); + KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0); +} + +/* + * Test that a very small number of tag ranges ends up compressed into 8 bytes. + */ +static void test_compress_simple(struct kunit *test) +{ + u8 tags[128], dtags[128]; + u64 handle; + + memset(tags, 0, 128); + tags[0] = 0xa0; + tags[1] = 0x0a; + tags[2] = 0xab; + + handle = ea0_compress(tags); + KUNIT_EXPECT_EQ(test, handle & BIT_ULL(63), 0); + /* Tags are stored inline. */ + KUNIT_EXPECT_EQ(test, ea0_storage_size(handle), 8); + KUNIT_EXPECT_TRUE(test, ea0_decompress(handle, dtags)); + KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0); +} + +/* + * Generate a buffer that will contain @nranges of tag ranges, test that it + * compresses into @exp_size bytes and decompresses into the original tag + * sequence. + */ +static void compress_range_helper(struct kunit *test, int nranges, int exp_size) +{ + u8 tags[128], dtags[128]; + u64 handle; + int i; + + memset(tags, 0, 128); + + if (nranges > 1) { + nranges--; + for (i = 0; i < nranges / 2; i++) + tags[i] = 0xab; + if (nranges % 2) + tags[nranges / 2] = 0xa0; + } + + handle = ea0_compress(tags); + KUNIT_EXPECT_EQ(test, handle & BIT_ULL(63), 0); + KUNIT_EXPECT_EQ(test, ea0_storage_size(handle), exp_size); + KUNIT_EXPECT_TRUE(test, ea0_decompress(handle, dtags)); + KUNIT_EXPECT_EQ(test, memcmp(tags, dtags, 128), 0); +} + +/* + * Test that every number of tag ranges is correctly compressed and + * decompressed. + */ +static void test_compress_ranges(struct kunit *test) +{ + int i, exp_size; + + for (i = 1; i <= 256; i++) { + if (i < 7) + exp_size = 8; + else if (i < 12) + exp_size = 16; + else if (i < 24) + exp_size = 32; + else if (i < 47) + exp_size = 64; + else + exp_size = 128; + compress_range_helper(test, i, exp_size); + } +} + +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_compress_zero), + KUNIT_CASE(test_compress_simple), + KUNIT_CASE(test_compress_ranges), + {} +}; + +static struct kunit_suite mtecomp_test_suite = { + .name = "mtecomp", + .test_cases = mtecomp_test_cases, +}; +kunit_test_suites(&mtecomp_test_suite); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Alexander Potapenko "); From patchwork Thu Jul 13 12:57:05 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 119862 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp1807962vqm; Thu, 13 Jul 2023 06:04:20 -0700 (PDT) X-Google-Smtp-Source: APBJJlHkKlAVCa2T4zZM9gunwAysDsF9Aoj6vqkpw7PmA1Ny1Sx78TV4yQBd7/OvgoGDkLnqdDK7 X-Received: by 2002:a05:6358:99a5:b0:129:c6d6:ce40 with SMTP id j37-20020a05635899a500b00129c6d6ce40mr2569512rwb.15.1689253459946; Thu, 13 Jul 2023 06:04:19 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689253459; cv=none; d=google.com; s=arc-20160816; b=R59wcyodqYPLHD2xQuI552FavgkQsGQET9oL5duCl3UTFU2uZxdaMmnLToYoXI2pFw kQzYBxlcJ897jIIZpeeewkLL1ZxRjpnN1VbQ0kEoqFuFDXZ7IngV52Adpeq9tO5tn5nm mSKwQYgM/QWpnCcs9CB6N9WtvdB4HnJenrJMHhDW9ztQoMaSIsSjYY12L51i/2OfWBaX VHYZp9lJFnrtqC0USnxq/hUbZbc9T3STwzh+maCffCG/TJ1lilEYh8tXxtIO5rPE0jIn a1vueYTpUNzW8CkCX1E7mFUxC9PIXORco19R91RdNKLTfcyLD9h9lrUWPO2v+8yKFv4O PLvQ== 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=GOfdDj4t/4l0qN/MzMyGSYQ+xos/zeOUfaRubiCXYXI=; fh=w2imRfrBx7xgrqExMhNQwXd/bCFo2iqBwf34S5/AxrI=; b=wGNo613j4cMypcaz9JdEU6EXPRUP+63PvP7Nl7lqp/vfQ9tD15rwjfihoZf4cvSpMh Oxync+xIon7JW5tKn8D4TREkFotxv3adnTLQEsYjOoySgrvAF3E8AT1hISw3Wlo0tJ0i W3Lr1pbZ8nTn8jVkAy5gcYX7djU4SoRBix13QK+rxLzyGMGmgwpGe0tvcgtrXWApaQo6 iVGhG2UqcKIGTfX/7RQ/7ie+agTesmgLclSXNWFs40blT2AdyZktct8vj2KifxNT2+t5 7SdCJTePnsVn9M0geD4Xnwmjazwu+bXa6RSucRe2glYn/RSrLyTeQxBBINhYEbI0EFMR MAJA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=fkNAaakh; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 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 (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id g4-20020a635204000000b0055b5f13dd64si5154573pgb.92.2023.07.13.06.04.04; Thu, 13 Jul 2023 06:04:19 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=fkNAaakh; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234417AbjGMM6H (ORCPT + 99 others); Thu, 13 Jul 2023 08:58:07 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36654 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234891AbjGMM5p (ORCPT ); Thu, 13 Jul 2023 08:57:45 -0400 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9FCE42702 for ; Thu, 13 Jul 2023 05:57:41 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-579e9b95b86so5507107b3.1 for ; Thu, 13 Jul 2023 05:57:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689253060; x=1691845060; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=GOfdDj4t/4l0qN/MzMyGSYQ+xos/zeOUfaRubiCXYXI=; b=fkNAaakhJhj14joU9vjShVN1J78/4ao4j4r/p0M09hqWWrtvYQsGmFffwTbIc+z21k OzoCWRoZ9KXixeBMf8N4Ri/coa/+8/xhR9EKxTNP8sfg3qpJat0FAxgDfcso3YLSRxuh tY3+AZS3TUi6H9CqRMIO6SNQKVGT6MR1mFawBy7pnitaqt3ZGBxlgndqmv2HJtMKJA43 U3PMN16S19MICAm06IGvBgzUo76/EVqARHIYt3KZurXU3HFFjt3/XW6jXM66vj5+t1kA 5Fj1MEGzbzeQH4Mmxx1jNONJ0i9fxqfaD+AdEi66+pcUHkQ3G3yvhO7pNJTb2WABE3b5 KE4w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689253060; x=1691845060; 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=GOfdDj4t/4l0qN/MzMyGSYQ+xos/zeOUfaRubiCXYXI=; b=QsKjDzfRn9yzjcgStmpJJ65+l4S4uYgZV2OuIGQW8kL6rQB/BnmHvPHX+/VidsPD9O LxyvsJla2oCDNtdHc7unkc6zONId2wk4/y89fqRepaOTxM4CzzM4MNG+6Sf7gSDz8V2a DRqhtfB/Azi58ZxPKuVybetbW8Hj5roOE4+3AjFKQP7m+r2i3c0Dpdb0k+Hf/K7g5K8t ejnYffAyY8NY9UVNlvISNyGjooTApw4SO7SVxyo9piksH11JTQ8nNxHHUBKLmrJbxcJd /HSAkzuU4qcwtoYLpCIhU/sLUaSEEv4v1z2B7lNvR0b2q+cGZGavKAgdRo2Ufg3wK6K4 Kbjw== X-Gm-Message-State: ABy/qLY9IQOeGJd6PH7qRcIoBPsOrt3ljQ/8r3uhLBf2moeJy6CSvr+o Fouzi3+32DFdeBBERN7R/SBaxclkDAw= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:7a88:66b7:31e5:7d85]) (user=glider job=sendgmr) by 2002:a81:8b48:0:b0:570:b1:ca37 with SMTP id e8-20020a818b48000000b0057000b1ca37mr13111ywk.5.1689253060736; Thu, 13 Jul 2023 05:57:40 -0700 (PDT) Date: Thu, 13 Jul 2023 14:57:05 +0200 In-Reply-To: <20230713125706.2884502-1-glider@google.com> Mime-Version: 1.0 References: <20230713125706.2884502-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230713125706.2884502-6-glider@google.com> Subject: [v2 5/5] 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, linux@rasmusvillemoes.dk, yury.norov@gmail.com Cc: linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771310635867318589 X-GMAIL-MSGID: 1771310635867318589 Define the internal mteswap.h interface: - _mte_alloc_and_save_tags() - _mte_free_saved_tags() - _mte_restore_tags() , that encapsulates saving tags for a struct page (together with memory allocation), restoring tags, and deleting the storage allocated for them. These functions accept opaque pointers, which may point to 128-byte tag buffers, as well as smaller buffers containing compressed tags, or have compressed tags stored directly in them. The existing code from mteswap.c operating with uncompressed tags is split away into mteswap_nocomp.c, and the newly introduced mteswap_comp.c provides compression with the EA0 algorithm. The latter implementation is picked if CONFIG_ARM64_MTE_COMP=y. Soon after booting Android, tag compression saves ~2.5x memory previously spent by mteswap.c on tag allocations. With the growing uptime, the savings reach 20x and even more. Signed-off-by: Alexander Potapenko --- arch/arm64/mm/Makefile | 5 ++++ arch/arm64/mm/mteswap.c | 19 ++++++------- arch/arm64/mm/mteswap.h | 12 ++++++++ arch/arm64/mm/mteswap_comp.c | 50 ++++++++++++++++++++++++++++++++++ arch/arm64/mm/mteswap_nocomp.c | 37 +++++++++++++++++++++++++ 5 files changed, 112 insertions(+), 11 deletions(-) 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 diff --git a/arch/arm64/mm/Makefile b/arch/arm64/mm/Makefile index 170dc62b010b9..46a798e2b67cb 100644 --- a/arch/arm64/mm/Makefile +++ b/arch/arm64/mm/Makefile @@ -11,6 +11,11 @@ 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 +ifdef CONFIG_ARM64_MTE_COMP +obj-$(CONFIG_ARM64_MTE) += mteswap_comp.o +else +obj-$(CONFIG_ARM64_MTE) += mteswap_nocomp.o +endif obj-$(CONFIG_ARM64_MTE_COMP_KUNIT_TEST) += test_mtecomp.o KASAN_SANITIZE_physaddr.o += n diff --git a/arch/arm64/mm/mteswap.c b/arch/arm64/mm/mteswap.c index cd508ba80ab1b..e072c1209fbb6 100644 --- a/arch/arm64/mm/mteswap.c +++ b/arch/arm64/mm/mteswap.c @@ -7,6 +7,8 @@ #include #include +#include "mteswap.h" + static DEFINE_XARRAY(mte_pages); void *mte_allocate_tag_storage(void) @@ -27,20 +29,18 @@ int mte_save_tags(struct page *page) if (!page_mte_tagged(page)) return 0; - tag_storage = mte_allocate_tag_storage(); + tag_storage = _mte_alloc_and_save_tags(page); if (!tag_storage) return -ENOMEM; - mte_save_page_tags(page_address(page), tag_storage); - /* page_private contains the swap entry.val set in do_swap_page */ ret = xa_store(&mte_pages, page_private(page), tag_storage, GFP_KERNEL); if (WARN(xa_is_err(ret), "Failed to store MTE tags")) { - mte_free_tag_storage(tag_storage); + _mte_free_saved_tags(tag_storage); return xa_err(ret); } else if (ret) { /* Entry is being replaced, free the old entry */ - mte_free_tag_storage(ret); + _mte_free_saved_tags(ret); } return 0; @@ -53,10 +53,7 @@ void mte_restore_tags(swp_entry_t entry, struct page *page) if (!tags) return; - if (try_page_mte_tagging(page)) { - mte_restore_page_tags(page_address(page), tags); - set_page_mte_tagged(page); - } + _mte_restore_tags(tags, page); } void mte_invalidate_tags(int type, pgoff_t offset) @@ -64,7 +61,7 @@ void mte_invalidate_tags(int type, pgoff_t offset) swp_entry_t entry = swp_entry(type, offset); void *tags = xa_erase(&mte_pages, entry.val); - mte_free_tag_storage(tags); + _mte_free_saved_tags(tags); } void mte_invalidate_tags_area(int type) @@ -78,7 +75,7 @@ void mte_invalidate_tags_area(int type) xa_lock(&mte_pages); xas_for_each(&xa_state, tags, last_entry.val - 1) { __xa_erase(&mte_pages, xa_state.xa_index); - mte_free_tag_storage(tags); + _mte_free_saved_tags(tags); } xa_unlock(&mte_pages); } diff --git a/arch/arm64/mm/mteswap.h b/arch/arm64/mm/mteswap.h new file mode 100644 index 0000000000000..bf25f2b3e75a4 --- /dev/null +++ b/arch/arm64/mm/mteswap.h @@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#ifndef ARCH_ARM64_MM_MTESWAP_H_ +#define ARCH_ARM64_MM_MTESWAP_H_ + +#include + +void *_mte_alloc_and_save_tags(struct page *page); +void _mte_free_saved_tags(void *tags); +void _mte_restore_tags(void *tags, struct page *page); + +#endif // ARCH_ARM64_MM_MTESWAP_H_ diff --git a/arch/arm64/mm/mteswap_comp.c b/arch/arm64/mm/mteswap_comp.c new file mode 100644 index 0000000000000..bc2591f8d4f35 --- /dev/null +++ b/arch/arm64/mm/mteswap_comp.c @@ -0,0 +1,50 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* MTE tag storage management with EA0 compression. */ + +#include +#include +#include +#include +#include +#include +#include + +#include "mteswap.h" + +void *_mte_alloc_and_save_tags(struct page *page) +{ + u8 tags[128]; + u64 handle; + + mte_save_page_tags(page_address(page), tags); + handle = ea0_compress(tags); + return xa_mk_value(handle); +} + +void _mte_free_saved_tags(void *storage) +{ + unsigned long handle = xa_to_value(storage); + int size; + + if (!handle) + return; + size = ea0_storage_size(handle); + ea0_release_handle(handle); +} + +void _mte_restore_tags(void *tags, struct page *page) +{ + u64 handle = xa_to_value(tags); + u8 tags_decomp[128]; + + if (!handle) + return; + + if (try_page_mte_tagging(page)) { + if (!ea0_decompress(handle, tags_decomp)) + return; + mte_restore_page_tags(page_address(page), tags_decomp); + set_page_mte_tagged(page); + } +} diff --git a/arch/arm64/mm/mteswap_nocomp.c b/arch/arm64/mm/mteswap_nocomp.c new file mode 100644 index 0000000000000..efcdac88b342d --- /dev/null +++ b/arch/arm64/mm/mteswap_nocomp.c @@ -0,0 +1,37 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* MTE tag storage management without compression support. */ + +#include +#include +#include +#include +#include +#include + +#include "mteswap.h" + +void *_mte_alloc_and_save_tags(struct page *page) +{ + void *storage; + + storage = mte_allocate_tag_storage(); + if (!storage) + return NULL; + + mte_save_page_tags(page_address(page), storage); + return storage; +} + +void _mte_free_saved_tags(void *storage) +{ + mte_free_tag_storage(storage); +} + +void _mte_restore_tags(void *tags, struct page *page) +{ + if (try_page_mte_tagging(page)) { + mte_restore_page_tags(page_address(page), tags); + set_page_mte_tagged(page); + } +}