From patchwork Mon Jul 17 11:37: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: 121225 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:c923:0:b0:3e4:2afc:c1 with SMTP id j3csp1055365vqt; Mon, 17 Jul 2023 04:46:25 -0700 (PDT) X-Google-Smtp-Source: APBJJlEmgXh++ri6FXmsLxf/7u4xfAsE+Tu0LKcUWzpZuTmqJLhCn8QnzrMPP+OqhTu+T/FuasS4 X-Received: by 2002:ac2:5b10:0:b0:4fb:7888:7e6d with SMTP id v16-20020ac25b10000000b004fb78887e6dmr6720933lfn.46.1689594384981; Mon, 17 Jul 2023 04:46:24 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689594384; cv=none; d=google.com; s=arc-20160816; b=VCywN3J3lUjKj8bsSIkbmRlMRMX2OIWtn38dIfakb2SD2hUQXVZXTCnpPha7aFXdVY jpVAmOsGV7YSvdQa9WXJUaKfkmCbBDalEZrOUaKxAQPqE43TPmEbUrVxiVk79dbTlk2E xDCbVCqzfQnsFZ5UrZWhQnUAtXo7Ma6QPxeciyaYeH0TNPffdHHfA/WF9ztgXl3dExfh cU/7rcQlv77amWbAkaJS/9xG1ciUHnUgc0Gfh+X6wV3KteiKBe7tUYEG7eoap4c1EPFn nNHyHxS/RoRvAVYAEtR6q7kcddkV+pfrYTQnNCc+q9+QxfLmT/fVnv8ZuYZwFGyKOEPT tZLA== 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=FGuCnRoGjtuxCyYZwSXlSd4VQfcsRWWQdyiV1Wnie4Q=; fh=JgIgyeVfHwvOXq2SUW9xixt7IvWppQhIeupjE3HP1BQ=; b=k2KBbX8ZrOF7BInPIbBIU3oxmaEUoAEo+BwKvgvcUSoDGVCsVT+sD3oDZLvutybuk1 bVRCzvOeW4krwp9UKA/CDQHE4CrRgb6P/oPnq+LUzPlsQ0m3hJxAMJb6hC6U265fELVo ZXzdd2OKZKhK6qRVEgitWPSR5s0Wzd86hhDZ2MWiy4L7PB3A35F397KGxgX2cYjrZphB YBBdLC9+LjOi4CRI41MegofJholDkPsLy3pc4otL4NrkhPYF0mOUkLKycuSl7eUcCPaB pQCLoG5qJVpD7ybcA8bnsPtLGHIhqGe4SibzVix3n38yGI8DSzdKKApvCBJZkG18hmHg 6qSw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=lOGtagPB; 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 n17-20020aa7c451000000b0051df73ddeffsi13727460edr.358.2023.07.17.04.46.00; Mon, 17 Jul 2023 04:46:24 -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=lOGtagPB; 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 S229669AbjGQLhY (ORCPT + 99 others); Mon, 17 Jul 2023 07:37:24 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46734 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230169AbjGQLhT (ORCPT ); Mon, 17 Jul 2023 07:37:19 -0400 Received: from mail-ed1-x549.google.com (mail-ed1-x549.google.com [IPv6:2a00:1450:4864:20::549]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B8BBBBF for ; Mon, 17 Jul 2023 04:37:17 -0700 (PDT) Received: by mail-ed1-x549.google.com with SMTP id 4fb4d7f45d1cf-51e278a3a2dso2963097a12.3 for ; Mon, 17 Jul 2023 04:37:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689593836; x=1692185836; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=FGuCnRoGjtuxCyYZwSXlSd4VQfcsRWWQdyiV1Wnie4Q=; b=lOGtagPBwApVjfpfXneYZBu8MWYD1OliVo2uXXUvPFvV6+APoIbAw6+/k3YWQj3eId ++zdOrcTldnSRQnleASyL9AkS3sHtgDNjCJqdxPyeYFLbcNbm7H47WMPCrL025NnVhlV G1Qol0TNu5t6DU2yoyQVV2/M6YY2bbB1S6KNkkNOFhBw/Gi3exXLENY44qDhbiI+qFGh XTOGJBYScj/gFqOpJMAG1/JvF8wnIW5CuArTM2y25y2u8rr7pO8KA2XD2gxTxG4FbLph Yo+NTPG4cWlDz+nePnG/bgJtDwcLrzw/IHDxEArbQPROIOahGhUPuqygOW0gEksJ4t/k Sb+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689593836; x=1692185836; 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=FGuCnRoGjtuxCyYZwSXlSd4VQfcsRWWQdyiV1Wnie4Q=; b=NHyjQM2ejPJiIBl/l4pJ9XcuK23hDk2cGV/X0flQGqtHXdrJm5cV22wHQ9c4i7fKjX r9PmCCME+SMGXAvmS1y39FEQU47z7uy2u3c4ZVLfy5q36bOs20dls1iPinJ6NntKrhIl juR8OA5LMY0Gxgeg8Wlj07duxZID41YBeuuM9jMwpGNCZe7F6npq4azMwtaK2XwXDEEF pbSwUyPKTXCCxb9RjgytKDNsjUUvu1zWaMKahw9DMn5G5ZSpbS+dmWY4a2s6HmKs1hhX Xp/RaGTkOPf8q6Us6gKNGyoWCXFvl5FLRpfDTon18yUhHz7VtwBX0thc/YjSo8jU1Z++ WekQ== X-Gm-Message-State: ABy/qLbhiupnYWHk834VLrIaTHUT/96cV8LvnrwJoU7LBRZQDD+3wU6t 7jPoxaJ86vUp6cf6nHOcblk4PZTPnYc= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:3b6e:8102:6db8:d83f]) (user=glider job=sendgmr) by 2002:a50:c310:0:b0:51b:ee9e:aad2 with SMTP id a16-20020a50c310000000b0051bee9eaad2mr66529edb.0.1689593835900; Mon, 17 Jul 2023 04:37:15 -0700 (PDT) Date: Mon, 17 Jul 2023 13:37:04 +0200 In-Reply-To: <20230717113709.328671-1-glider@google.com> Mime-Version: 1.0 References: <20230717113709.328671-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230717113709.328671-2-glider@google.com> Subject: [PATCH v3 1/5] lib/bitmap: add bitmap_{set,get}_value() 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, syednwaris@gmail.com, william.gray@linaro.org, Arnd Bergmann 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: 1771668122144434414 X-GMAIL-MSGID: 1771668122144434414 The two new functions allow setting/getting values of length up to BITS_PER_LONG bits at arbitrary position in the bitmap. The code was taken from "bitops: Introduce the for_each_set_clump macro" by Syed Nayyar Waris with a couple of minor changes: - instead of using roundup(), which adds an unnecessary dependency on , we calculate space as BITS_PER_LONG-offset; - indentation is reduced by not using else-clauses (suggested by checkpatch for bitmap_get_value()) Cc: Arnd Bergmann Signed-off-by: Syed Nayyar Waris Signed-off-by: William Breathitt Gray Link: https://lore.kernel.org/lkml/fe12eedf3666f4af5138de0e70b67a07c7f40338.1592224129.git.syednwaris@gmail.com/ Suggested-by: Yury Norov Signed-off-by: Alexander Potapenko --- include/linux/bitmap.h | 57 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 03644237e1efb..4559366084988 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -76,7 +76,11 @@ struct device; * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst * 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_get_value(map, start, nbits) Get bit value of size 'nbits' + * from map at start * bitmap_set_value8(map, value, start) Set 8bit value to map at start + * bitmap_set_value(map, value, start, nbits) Set bit value of size 'nbits' + * of map at start * * Note, bitmap_zero() and bitmap_fill() operate over the region of * unsigned longs, that is, bits behind bitmap till the unsigned long @@ -583,6 +587,31 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map, return (map[index] >> offset) & 0xFF; } +/** + * bitmap_get_value - get a value of n-bits from the memory region + * @map: address to the bitmap memory region + * @start: bit offset of the n-bit value + * @nbits: size of value in bits + * + * Returns value of nbits located at the @start bit offset within the @map + * memory region. + */ +static inline unsigned long bitmap_get_value(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 space = BITS_PER_LONG - offset; + unsigned long value_low, value_high; + + if (space >= nbits) + return (map[index] >> offset) & GENMASK(nbits - 1, 0); + value_low = map[index] & BITMAP_FIRST_WORD_MASK(start); + value_high = map[index + 1] & BITMAP_LAST_WORD_MASK(start + nbits); + return (value_low >> offset) | (value_high << space); +} + /** * bitmap_set_value8 - set an 8-bit value within a memory region * @map: address to the bitmap memory region @@ -599,6 +628,34 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value, map[index] |= value << offset; } +/** + * bitmap_set_value - set n-bit value within a memory region + * @map: address to the bitmap memory region + * @value: value of nbits + * @start: bit offset of the n-bit value + * @nbits: size of value in bits + */ +static inline void bitmap_set_value(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; + const unsigned long space = BITS_PER_LONG - offset; + + value &= GENMASK(nbits - 1, 0); + + if (space >= nbits) { + map[index] &= ~(GENMASK(nbits + offset - 1, offset)); + map[index] |= value << offset; + return; + } + map[index] &= ~BITMAP_FIRST_WORD_MASK(start); + map[index] |= value << offset; + map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits); + map[index + 1] |= (value >> space); +} + #endif /* __ASSEMBLY__ */ #endif /* __LINUX_BITMAP_H */ From patchwork Mon Jul 17 11:37: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: 121228 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:c923:0:b0:3e4:2afc:c1 with SMTP id j3csp1058925vqt; Mon, 17 Jul 2023 04:54:15 -0700 (PDT) X-Google-Smtp-Source: APBJJlGTd99OcYT2pNijnc4/r+xXQLBr/3EG8x71QEIKuJYCIfxMvLUGDGlaxdz7CyTPdhL2nVbF X-Received: by 2002:a05:6830:1d75:b0:6b9:5810:84d2 with SMTP id l21-20020a0568301d7500b006b9581084d2mr10628815oti.6.1689594855731; Mon, 17 Jul 2023 04:54:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689594855; cv=none; d=google.com; s=arc-20160816; b=DLGekixtOJa4zwl8f3UHbLZWmLdVyGlHHgaMZdWIVROrLK/E6KbTDz2CsYwTtqeSl7 1BEve2IO64Z00MFq5BC9tjNAimPgsQkndWCaoWYRmqVnQSTQZ70T6eJl/SO3iQ3+4tEx OKCD+zjEaD7/IZCqvQxrS4L0rczn48QaQjr1GbRjwNEIYn1OJmZGA9spKsjWRqNddRdr 3Wo3hJe/SNdUopA4TwdXnaU47YbQAnvtEBTaBZMXYQ8Fz7qyD2MYxz+OvyzEMIQnvOzF Vw4SzeCY05snHD2cjRp9aQio0LsmlWtLe15k3B1A47P/P75CIXDRRZ/EbalsEmsBkWjv No4A== 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=S4GzxuyU3vJn9v8U3mWqzLaFXfnE9ofQM/5FOa6/PYw=; fh=O56S7FQoQXDYw0ENjMcjZy7yKrdXtC51zI+f09bWPts=; b=WVyc5SJXEHosmq7pefC2nXLoimrWvefR2D/sX03aJH5Zx7nip/45bPmRdFcVF1pic+ 3VJV6LPuyOovwOYDHfQmWnHNnQpyaUpyOp5X1AKvAh6ogxeMYxjGf4DeFH/a8AfovPKn gBSIUxSJIvHm7LIIHQAEHLgNLsQCUD58fBk1S+J8YOGH4CKmRIHMyIyVEzwLLOLjkGOK FahBOWbta/uD5U8bRueRj0642lAjspkj/neGrdr9+x+IQmznoeCPzWdaZ9BK2S0bXdgQ RW6mg9R3poseDEsg+dArRlyZ1gWAwDKAeHjcgDtvb4A8pIwUdo79rOej592fSmSsmjWf Lrdg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=TRhADAln; 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 c5-20020a6566c5000000b0055c0477e26dsi10988198pgw.475.2023.07.17.04.54.02; Mon, 17 Jul 2023 04:54: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=TRhADAln; 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 S230272AbjGQLh0 (ORCPT + 99 others); Mon, 17 Jul 2023 07:37:26 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46782 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230260AbjGQLhX (ORCPT ); Mon, 17 Jul 2023 07:37:23 -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 A789C10CF for ; Mon, 17 Jul 2023 04:37:20 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-57745160c1dso41998677b3.2 for ; Mon, 17 Jul 2023 04:37:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689593840; x=1692185840; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=S4GzxuyU3vJn9v8U3mWqzLaFXfnE9ofQM/5FOa6/PYw=; b=TRhADAlnuCLbiGu1Z8fSaZaO8ThyU1u4h/oqBA8WWnXEPQrIlWo4fAT5TGnCam3mI4 PScfWARXctzZJoglFnaeX4/4mXUgNbsR5JyhvUQAug+Vv3KpeCt3WCj5Fm1poyP+huJ7 Fou4az0geM/C601sPT5rGVu2sYmfvq3oHsY2eBMXkhwYVp1cfyiGhxorRMM7lmrH9X0d OgW1NntxVRPZwEGrFfjEWlXZZ4fzEJSH/PWgVvRG+IPW4A3SRs9WTQqab6DqdxHhiaHu InkzhF7rowEHA7zC8IpLrEcQVL23wiD5U+B+UWJbhxSkiEDPR3kNDORikeMRKxcUZUL0 d9hg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689593840; x=1692185840; 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=S4GzxuyU3vJn9v8U3mWqzLaFXfnE9ofQM/5FOa6/PYw=; b=GICJEvwxB7dZz0Pipj65haK9JOQl5ZuM9IAnV07xZdc7grZ09sPW+6dlbS4PpKyE8H oAd7shX1xeYlGx/OQVcjas171Vq3vq/Nfv/K39XhnM4nhdX5KzvYzoz1k0duTztgIHNj 5MQl5C9VFCQZMk2v9FBMjEjGbE1mcxSMlCs3FVDqmz5It9O1S7MJrt+JWIT3qPlVDtHq mB+n8Cx3N0bcJEeQtMURL42FZxuV91DOcXq7F1xouRyrDOp5Pcxf3wJNF1Qnroih2Qs/ oRv9bSt1ifi2ZFormxNqU3/rKqqfleQK39GvqcADtHxE/iVOpDYrKNcObPtAys4dhKKu CWbQ== X-Gm-Message-State: ABy/qLYW6JBEOtOKSGsHCa1j32T/3QCIx1rWx1S4ulWXsMD2S/8BexdV 3lWkoxNmJp++c5R/cx74Bg9yV/UzzCg= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:3b6e:8102:6db8:d83f]) (user=glider job=sendgmr) by 2002:a81:ad5d:0:b0:573:285a:c2a3 with SMTP id l29-20020a81ad5d000000b00573285ac2a3mr126417ywk.1.1689593839923; Mon, 17 Jul 2023 04:37:19 -0700 (PDT) Date: Mon, 17 Jul 2023 13:37:05 +0200 In-Reply-To: <20230717113709.328671-1-glider@google.com> Mime-Version: 1.0 References: <20230717113709.328671-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230717113709.328671-3-glider@google.com> Subject: [PATCH v3 2/5] lib/test_bitmap: add tests for bitmap_{set,get}_value() 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, 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771668615132000043 X-GMAIL-MSGID: 1771668615132000043 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 Reviewed-by: Andy Shevchenko --- This patch was previously called "lib/test_bitmap: add tests for bitmap_{set,get}_value_unaligned" v3: - switch to using bitmap_{set,get}_value() - change the expected bit pattern in test_set_get_value(), as the test was incorrectly assuming 0 is the LSB. --- lib/test_bitmap.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 187f5b2db4cf1..c2ab54040c249 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,25 @@ static void __init test_bitmap_const_eval(void) BUILD_BUG_ON(~var != ~BIT(25)); } +static void __init test_set_get_value(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(bitmap, 0b10101UL, i, 5); + val = bitmap_get_value(bitmap, i, 5); + expect_eq_ulong(0b10101UL, val); + bitmap_set_value(bitmap, 0b101UL, i + 5, 3); + val = bitmap_get_value(bitmap, i + 5, 3); + expect_eq_ulong(0b101UL, val); + val = bitmap_get_value(bitmap, i, 8); + expect_eq_ulong(0b10110101UL, val); + } +} + static void __init selftest(void) { test_zero_clear(); @@ -1249,6 +1280,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(); } KSTM_MODULE_LOADERS(test_bitmap); From patchwork Mon Jul 17 11:37:06 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 121226 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:c923:0:b0:3e4:2afc:c1 with SMTP id j3csp1055464vqt; Mon, 17 Jul 2023 04:46:33 -0700 (PDT) X-Google-Smtp-Source: APBJJlGrc0X8q/PBGG5PLettRAcUMvFDYCLHZOkYH2hCXDFUCu1OmvvZpd7hDG0h/D/Cx1nAvjI+ X-Received: by 2002:a17:906:9b:b0:993:fdb4:327f with SMTP id 27-20020a170906009b00b00993fdb4327fmr11529166ejc.4.1689594392800; Mon, 17 Jul 2023 04:46:32 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689594392; cv=none; d=google.com; s=arc-20160816; b=rvW8muEuXlptXm5X98q9b70OCt9nGkfTxqQUot1LdYNdJPUxHM/E8A19UUJ72SkZ8c Ijb0JtBaXPp6cFRwoJa4nyhGTW3YYw/fYsAUknq7DsJR3kc2TyUt1brB6sFfJnUNYwqm KcvO5LwCmdrV2wQvrYzpFEjPYTf62LJrnMLWDE6Z9HwBg4JQ6weklMo+oUVtQefPKNpy 2Xy9CeMNS9P45d1s5KIi9dvYnX+v0T0y0lsKbosaJKICxD0a0EzOinHPro6ZUNsahBeN MMigKEuyyExXMU8fUcUH46MIp/zYVq0f7kW3mpo+zARkjO9cDXm3xxqXC4Zdr0mJcMPR jDFA== 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=NvRbZSqEbEgNjBWP4zI9nPh29npYLZUXp+boFRM8PZk=; fh=O56S7FQoQXDYw0ENjMcjZy7yKrdXtC51zI+f09bWPts=; b=jVUtj9SGRA3GSEsBtuZ2evlgasb3MWkmYi0F+gChTbaPdYeA1/D5AqtY+RO+ZW7Ax3 reUaTrTlm2UgUSHFDehz51cf5b0z3vHqtSfwTP/1s4+Gf6uRvhCxTKKBZ/nynL1xWUFl yOZ+Z4s+yA43sq5FQbLQjnmUsfp5ukGWkYYeEEAa+55OpUXO/j/vvwZo0Kv8eX6LaXI/ aWRr9+ugG+fi6zdsgTVJIO0spUgw08ladrjQJzyxST7ATZQw+QfAPlMushTeNbdVkLqG vq5IvSNV9DSqmJgcYr+keUniPHYsnG+98ojwHsXFQG1AC7i73Ybs4qFrkzCwZNqWm3Fm vuyQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=jF7VApe1; 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 q13-20020a1709060e4d00b0099396547000si11847055eji.767.2023.07.17.04.46.08; Mon, 17 Jul 2023 04:46:32 -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=jF7VApe1; 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 S230266AbjGQLhg (ORCPT + 99 others); Mon, 17 Jul 2023 07:37:36 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46932 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230296AbjGQLh2 (ORCPT ); Mon, 17 Jul 2023 07:37:28 -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 B5B0FE4C for ; Mon, 17 Jul 2023 04:37:23 -0700 (PDT) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-57704aa6c69so39297577b3.0 for ; Mon, 17 Jul 2023 04:37:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689593843; x=1692185843; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=NvRbZSqEbEgNjBWP4zI9nPh29npYLZUXp+boFRM8PZk=; b=jF7VApe1WMvap5r7aHtsDGd9DLDWTVOxGXp1d7AH4N9GnRhRynH1GkgpQsmTw55xOw V3Tt/ED+0RfjpkBwjfu55EfMPv77klLgOMrExaQL6f+WARHhUcWP/0yMqNthXUkGTyWS GobkMIzZluNDGhLBJ97d8TIVZkzs4+bmrP2dd6zwuSjIclrP61ntl+JvVK8nbNkvRDLd KCi/BuKmT9+MTBAUyPpMm3iPAgq5ij4CE1Thypub5LiyI+v9DlMlUD2cFrpR0HHdqiTV YZdqM8R0dfb7mptP+jXX/0+vQAzwq5cjhzU6Go+Yy/S5VmqcVmrtU/LQClV7vlDpRcdY donA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689593843; x=1692185843; 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=NvRbZSqEbEgNjBWP4zI9nPh29npYLZUXp+boFRM8PZk=; b=FiQHxCnCvT6SprVPFhYlG4Xp9r9GYBCDx6rut0qmUaF//gjA50KAVoY5seQ/7bdSRU v7cpJRCWYkREO1g5xX6lJhbFWxZx6dZsuuTyP0adnIw2YL634n8VVoeDw6oBGoKvy1yP 3XUPa/p/SLdIsQ0s3iXcfgjEXEgQa70IKsdPQbHoO888xU6T3CAoY1w57lRgjanU4bvV udAe/8jiELKqQ0K+epd1N0dUyRGdqkN45tOi4EYxCayCBdzIgUKSIEdKnFAI6nBtJA8S 8mo3KAcAui6m2pUkil4sj6Jkg8tZZ8v3fV4gvysjvwmVkoCzWfb69c61tWIarQQXL09h 4oVQ== X-Gm-Message-State: ABy/qLZ+VCvhOQEprV2q2WC73MpncIQCY3qmLIzWwFqbWwoNT8bQMh94 JbBCu+0I+GOPa5SZ5dCtoy4WCREphVg= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:3b6e:8102:6db8:d83f]) (user=glider job=sendgmr) by 2002:a25:100a:0:b0:c2c:1b68:99b6 with SMTP id 10-20020a25100a000000b00c2c1b6899b6mr106384ybq.6.1689593842870; Mon, 17 Jul 2023 04:37:22 -0700 (PDT) Date: Mon, 17 Jul 2023 13:37:06 +0200 In-Reply-To: <20230717113709.328671-1-glider@google.com> Mime-Version: 1.0 References: <20230717113709.328671-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230717113709.328671-4-glider@google.com> Subject: [PATCH v3 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, 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771668130071300088 X-GMAIL-MSGID: 1771668130071300088 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 --- 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 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 | 406 +++++++++++++++++++++++++++++++ 4 files changed, 477 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 a2511b30d0f67..52cdc7603cf7c 100644 --- a/arch/arm64/Kconfig +++ b/arch/arm64/Kconfig @@ -2093,6 +2093,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..0c444c0d4ac04 --- /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(). + */ +unsigned long 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(unsigned long handle, u8 *tags); + +/* + * ea0_release_handle() - release the handle returned by ea0_compress(). + * @handle: handle returned by ea0_compress(). + */ +void ea0_release_handle(unsigned long 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(unsigned long 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..50a379c035aee --- /dev/null +++ b/arch/arm64/mm/mtecomp.c @@ -0,0 +1,406 @@ +// 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 + * ea0_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 + +#include + +/* The handle must fit into an Xarray value. */ +#define HANDLE_MASK GENMASK_ULL(62, 0) + +/* Out-of-line handles have 0b111 in bits 62..60. */ +#define NOINLINE_MASK GENMASK_ULL(62, 60) + +/* Cache index is stored in the lowest pointer bits. */ +#define CACHE_ID_MASK GENMASK_ULL(2, 0) + +/* + * Four separate caches to store out-of-line data: + * 0: mte-tags-128 + * 1: mte-tags-16 + * 2: mte-tags-32 + * 3: mte-tags-64 + */ +#define NUM_CACHES 4 +static struct kmem_cache *mtecomp_caches[NUM_CACHES]; + +/* + * Sizes of compressed values. + */ +#define BITS_PER_TAG 4 +#define BITS_PER_SIZE 7 +#define BITS_PER_LARGEST_IDX_INLINE 4 +#define BITS_PER_LARGEST_IDX 6 + +/* Translate allocation size into mtecomp_caches[] index. */ +static int ea0_size_to_cache_id(int len) +{ + if (len < 128) + return fls(len >> 4); + return 0; +} + +/* Translate mtecomp_caches[] index into allocation size. */ +static int ea0_cache_id_to_size(int id) +{ + if (id == 0) + return 128; + return 8 << id; +} + +/* Transform tags into tag ranges. */ +void ea0_tags_to_ranges(u8 *tags, u8 *out_tags, short *out_sizes, int *out_len) +{ + u8 prev_tag = U8_MAX; + int cur_idx = -1; + u8 cur_tag; + int i, j; + + memset(out_tags, 0, array_size(*out_len, sizeof(*out_tags))); + memset(out_sizes, 0, array_size(*out_len, sizeof(*out_sizes))); + + for (i = 0; i < MTE_PAGE_TAG_STORAGE; i++) { + for (j = 0; j < 2; j++) { + cur_tag = j ? (tags[i] % 16) : (tags[i] / 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(ea0_tags_to_ranges, MTECOMP); + +/* 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) + tags[pos / 2] = (prev << 4) | r_tags[i]; + else + prev = r_tags[i]; + pos++; + } + } +} +EXPORT_SYMBOL_NS(ea0_ranges_to_tags, MTECOMP); + +/* 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; + } +} +#define RANGES_INLINE ea0_size_to_ranges(8) + +/* Is the data stored inline in the handle itself? */ +static bool ea0_is_inline(unsigned long handle) +{ + return (handle & NOINLINE_MASK) != NOINLINE_MASK; +} + +/* Get the size of the buffer backing @handle. */ +int ea0_storage_size(unsigned long handle) +{ + if (ea0_is_inline(handle)) + return 8; + return ea0_cache_id_to_size(handle & CACHE_ID_MASK); +} +EXPORT_SYMBOL_NS(ea0_storage_size, MTECOMP); + +static void bitmap_write(unsigned long *bitmap, unsigned long value, + unsigned long *pos, unsigned long bits) +{ + bitmap_set_value(bitmap, value, *pos, bits); + *pos += bits; +} + +/* Compress ranges into the buffer that can accommodate up to max_ranges. */ +static void ea0_compress_to_buf(int len, u8 *tags, short *sizes, + unsigned long *bitmap, int max_ranges) +{ + unsigned long bit_pos = 0, l_bits; + int largest_idx = -1, i; + short largest = 0; + + for (i = 0; i < len; i++) { + if (sizes[i] > largest) { + largest = sizes[i]; + largest_idx = i; + } + } + l_bits = (max_ranges == RANGES_INLINE) ? BITS_PER_LARGEST_IDX_INLINE : + BITS_PER_LARGEST_IDX; + bitmap_write(bitmap, largest_idx, &bit_pos, l_bits); + for (i = 0; i < len; i++) + bitmap_write(bitmap, tags[i], &bit_pos, BITS_PER_TAG); + for (i = len; i < max_ranges; i++) + bitmap_write(bitmap, 0, &bit_pos, BITS_PER_TAG); + for (i = 0; i < len; i++) { + if (i == largest_idx) + continue; + bitmap_write(bitmap, sizes[i], &bit_pos, BITS_PER_SIZE); + } + for (i = len; i < max_ranges; i++) + bitmap_write(bitmap, 0, &bit_pos, BITS_PER_SIZE); +} + +/* Compress @tags and return a handle. */ +unsigned long 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); + unsigned long *storage; + /* + * ea0_compress_to_buf() only initializes the bits that ea0_decompress() + * will read. But when the tags are stored in the handle itself, it must + * have all its bits initialized. + */ + unsigned long result = 0; + + ea0_tags_to_ranges(tags, r_tags, r_sizes, &r_len); + alloc_size = ea0_alloc_size(r_len); + if (alloc_size == 8) { + ea0_compress_to_buf(r_len, r_tags, r_sizes, &result, + RANGES_INLINE); + return result; + } + 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) { + /* alloc_size is always a multiple of sizeof(unsigned long). */ + ea0_compress_to_buf(r_len, r_tags, r_sizes, storage, + ea0_size_to_ranges(alloc_size)); + return ((unsigned long)storage | cache_id) & HANDLE_MASK; + } + memcpy(storage, tags, alloc_size); + return (unsigned long)storage & HANDLE_MASK; +} +EXPORT_SYMBOL_NS(ea0_compress, MTECOMP); + +static unsigned long bitmap_read(const unsigned long *bitmap, + unsigned long *pos, unsigned long bits) +{ + unsigned long result; + + result = bitmap_get_value(bitmap, *pos, bits); + *pos += bits; + return result; +} + +/* Decompress the contents of the given buffer into @tags. */ +static bool ea0_decompress_from_buf(const unsigned long *bitmap, int max_ranges, + u8 *tags) +{ + int largest_idx, i; + short r_sizes[46], sum = 0; + u8 r_tags[46]; + unsigned long bit_pos = 0, l_bits; + + l_bits = (max_ranges == RANGES_INLINE) ? BITS_PER_LARGEST_IDX_INLINE : + BITS_PER_LARGEST_IDX; + largest_idx = bitmap_read(bitmap, &bit_pos, l_bits); + for (i = 0; i < max_ranges; i++) + r_tags[i] = bitmap_read(bitmap, &bit_pos, BITS_PER_TAG); + for (i = 0; i < max_ranges; i++) { + if (i == largest_idx) + continue; + r_sizes[i] = bitmap_read(bitmap, &bit_pos, BITS_PER_SIZE); + if (!r_sizes[i]) { + max_ranges = 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, max_ranges, tags); + return true; +} + +/* Get pointer to the out-of-line storage from a handle. */ +static void *ea0_storage(unsigned long 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(unsigned long handle, u8 *tags) +{ + unsigned long *storage = ea0_storage(handle); + int size = ea0_storage_size(handle); + + if (size == 128) { + memcpy(tags, storage, size); + return true; + } + if (size == 8) + return ea0_decompress_from_buf(&handle, RANGES_INLINE, tags); + return ea0_decompress_from_buf(storage, ea0_size_to_ranges(size), tags); +} +EXPORT_SYMBOL_NS(ea0_decompress, MTECOMP); + +/* Release the memory referenced by @handle. */ +void ea0_release_handle(unsigned long handle) +{ + void *storage = ea0_storage(handle); + int size = ea0_storage_size(handle); + struct kmem_cache *c; + + if (!storage) + return; + + c = mtecomp_caches[ea0_size_to_cache_id(size)]; + kmem_cache_free(c, storage); +} +EXPORT_SYMBOL_NS(ea0_release_handle, MTECOMP); + +/* Set up mtecomp_caches[]. */ +static int mtecomp_init(void) +{ + char name[16]; + int size; + int i; + + BUILD_BUG_ON(MTE_PAGE_TAG_STORAGE != 128); + 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 Mon Jul 17 11:37:07 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 121223 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:c923:0:b0:3e4:2afc:c1 with SMTP id j3csp1055224vqt; Mon, 17 Jul 2023 04:46:07 -0700 (PDT) X-Google-Smtp-Source: APBJJlF4LbzF3x1r9Jeawy+XiIVxB9rdl9z0cYL+FaOirifgs4g4ODOsOI6a2wHFBRvGzpl+k9bN X-Received: by 2002:a17:906:64cf:b0:994:13c3:2f89 with SMTP id p15-20020a17090664cf00b0099413c32f89mr11338911ejn.27.1689594367093; Mon, 17 Jul 2023 04:46:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689594367; cv=none; d=google.com; s=arc-20160816; b=K730KDQumao1+U6kC4hn7nXb/KI23OF2NSCmS97eZcIB6NK2Wyvl9tzAv5ORBJUlxq KEPtGpsi1nY9k2jIPw2IimJYWKhSzDTbDRhQoSYnLoBZuYVAfMRB2umtQvxnxNEFr+dB Cz1YaTvB53wxOPUACyXhRNAq2a+JpKwMtWLmvNeZ8VDNpwgmG0h+IGV5281Q+0abwTn8 HDQ1LoCQebKo0jTMW4ycPZpe8wN/BhSt8wKxJbT77M0U38WRUfNK2MEhCvwc7CnZYOIV fwv6fJzmQNR1fFhXFm6+FqCpWMsOOSTnrd41X+402vKQof0S2QJa4MEAqcDeVeIJfI/Y Qnvw== 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=dxhXbzRzEXNMQJKI4jN/6duvQjIZi8dRPcJNuvEcxk0=; fh=O56S7FQoQXDYw0ENjMcjZy7yKrdXtC51zI+f09bWPts=; b=qmep+8v33XueoC7Nuy4oMsZ2Et0f1gFU2SCpPzEgPzmQUUtteWdBxMwHH8nO2J2P4P 2Ks+v5/JlDk5tHrDnW8/cyhpDM8fcakc1l9TylsIJeTa+/9hVNzStSebQkkePffHvoW4 UIKqACilRnHpKI+yGGPHN3iiOGEbPhnJJZIWOe+9ObSJHWZjVgeDuSEUbKozgDiowtLH NhglLZK77NQLMKckWd5fjq8zpEO3LzVs2EX8wMCPXDFb3tq5s7HHULYHGkBJus78S+n6 go+krIqvsaC1sQYUUn+5b6h/jqKYBRHcwD0mPQaIocnetHugw1J+onZ7kVeLoW26vOE5 14lg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=Yj3KZF9x; 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 h3-20020a1709067cc300b00992c22a6857si13526062ejp.199.2023.07.17.04.45.41; Mon, 17 Jul 2023 04:46:07 -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=Yj3KZF9x; 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 S230336AbjGQLhj (ORCPT + 99 others); Mon, 17 Jul 2023 07:37:39 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46952 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230326AbjGQLhf (ORCPT ); Mon, 17 Jul 2023 07:37:35 -0400 Received: from mail-ej1-x649.google.com (mail-ej1-x649.google.com [IPv6:2a00:1450:4864:20::649]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C670A10FB for ; Mon, 17 Jul 2023 04:37:27 -0700 (PDT) Received: by mail-ej1-x649.google.com with SMTP id a640c23a62f3a-99388334de6so250018966b.0 for ; Mon, 17 Jul 2023 04:37:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689593846; x=1692185846; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=dxhXbzRzEXNMQJKI4jN/6duvQjIZi8dRPcJNuvEcxk0=; b=Yj3KZF9xhrnATVqtjzVrgRfACSYo06veH+hKGbTh+/ol0JW3he8L6TOacW/5oHw3VU z04ah5o2UotYtUIJYGqwDIJMe3tWSLWEsM8PP+UOGP1oWE8aLis64hG4VYzJNf8hb5F/ KYn0Q9gbMYYc26OeWLOSkWZbkiFezxR7alAwcgc7iCsjIG0VsDvwG0z6oBE8r8ZjqpZu Hotz0uK+/VLUyK16NP8my5LEQiw32jw4bZk1/nJMpMubSXWSUAbXTjQ+s9XJ3rA78Csr sWzjaTZxBk0fz8cAkeaBjhDoTxfBt5qD6XBWLrgPyLWdaFVx0+xrgfKEAF46b4wjJCvT IviQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689593846; x=1692185846; 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=dxhXbzRzEXNMQJKI4jN/6duvQjIZi8dRPcJNuvEcxk0=; b=WZHJca7CMilEfmV8vbZ9BmvIVlZyZnrI6+T8KIDJUHGcJ3rNam3lWP9TzNm858Dzxz +Zq1Z2zIvdMJ6h1excUiTB79HGu21ZmwcveSFOXolZT5psAdTXF7j+sT/kY3JOvc0NDT cwbtAY/bdFw50UZn5+rQWmnCtDD48H+uxaIFdxgSJPW497p9jCLfuW28rg61xWzPYwc0 q+haOtWdsk6shHOw+S9EZ37l8hab4EP+TcGkp99Er57Tbrb3Z36MITM0nCpKKg6sUlwc WcU+pAsL5JNbUtH7m9VjPhnDoZUZffnwu8vEVFmt/GUZfKzJuX7lpaaKtM1AvFfanjDp 68fw== X-Gm-Message-State: ABy/qLbCHHCmFtSTlzxQ33/n/KlsRF3PE0U4OepsNzOGLscO7KG9y62C V8UWSvaIHfoeOlwRbu0KQMaKWgqdkLM= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:3b6e:8102:6db8:d83f]) (user=glider job=sendgmr) by 2002:a17:907:270d:b0:994:4edd:34a2 with SMTP id w13-20020a170907270d00b009944edd34a2mr30786ejk.2.1689593846330; Mon, 17 Jul 2023 04:37:26 -0700 (PDT) Date: Mon, 17 Jul 2023 13:37:07 +0200 In-Reply-To: <20230717113709.328671-1-glider@google.com> Mime-Version: 1.0 References: <20230717113709.328671-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230717113709.328671-5-glider@google.com> Subject: [PATCH v3 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, 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771668103236159103 X-GMAIL-MSGID: 1771668103236159103 Ensure that tag sequences containing alternating values are compressed to buffers of expected size and correctly decompressed afterwards. Signed-off-by: Alexander Potapenko --- 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 | 10 ++ arch/arm64/mm/Makefile | 1 + arch/arm64/mm/test_mtecomp.c | 177 +++++++++++++++++++++++++++++++++++ 3 files changed, 188 insertions(+) create mode 100644 arch/arm64/mm/test_mtecomp.c diff --git a/arch/arm64/Kconfig b/arch/arm64/Kconfig index 52cdc7603cf7c..a6f1a36e8d27b 100644 --- a/arch/arm64/Kconfig +++ b/arch/arm64/Kconfig @@ -2103,6 +2103,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..bb71c6224e34a --- /dev/null +++ b/arch/arm64/mm/test_mtecomp.c @@ -0,0 +1,177 @@ +// 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]; + unsigned long 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]; + unsigned long 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]; + unsigned long 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_IMPORT_NS(MTECOMP); +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Alexander Potapenko "); From patchwork Mon Jul 17 11:37:08 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 121224 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:c923:0:b0:3e4:2afc:c1 with SMTP id j3csp1055358vqt; Mon, 17 Jul 2023 04:46:25 -0700 (PDT) X-Google-Smtp-Source: APBJJlE+eXzw+/mBMLHEvp3q1XGaVV7Xa8Fkhs7mnOW5lDdaY625kmRHDxXy9hhLRtkMcDluLrI4 X-Received: by 2002:a17:906:19b:b0:994:1844:549c with SMTP id 27-20020a170906019b00b009941844549cmr11362242ejb.0.1689594384775; Mon, 17 Jul 2023 04:46:24 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689594384; cv=none; d=google.com; s=arc-20160816; b=Jf1JbJh4g9DEZpbZqKCVGf0E2we1ac1tB4dArBybASyYG+sW4iTk/sXEuuRe951bil 56QUc2kdXyeNzwbNl4D92C1eJr8g/T5rynZGl9Jh3bPlKflzuNVvWNATek5Av79y41hq oqYoV3qe80vdxm6r1/jLjdx+ZmYONqRV3s8+aIuifau91t8Lr7MzrV9cRl8I9e/ozbMA BgkH9Vk/pzspd83p5BpF6DTjq3Q7fgoTpvqte4tR9sZjviKQ13/Ge9HJmUogEGPeFiQg eWhqALvoUJci61Z1KGnieMojhLWwRjlI2zPEuWm+i5b5VqshOohsrxchwFD1C2BE5YjD CDfA== 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=rcW4dTWuK29JOsV2I2tZPVBrCL3mh4Imj+/5bJ9CoOk=; fh=O56S7FQoQXDYw0ENjMcjZy7yKrdXtC51zI+f09bWPts=; b=KTTCDAdyuOAJk2gbFiqEmDpLl3zR087wlWNs2ax3dLgF3n+pqwpVB+ZCa1hoiRK1Pv HxG+8chlp26C4Z5Osi2B+hcXyVaILTSX2oOU1uazXSqmaCooS0lOWoCpED8aYkvUi+dq TW98tgU+cI8ZV61i+5JWIly/FPAnzVeDthU6WINA/81eSiL73k1e0OpFk5bIfSLxEduS wkLIzcRL7jgH0GchQrPUf/B9ySTuxXI/gt7/QnmdFuQ5WdHB7eH1aA1QovvG0coKcOot KzONsHi+p4EAmnBbxOlDaxZQGjD1jS0bn6ma4uaEpjVDmHe2a/OcjYCu9EScGsVAUF1G TWFA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20221208 header.b=gdizMM9J; 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 u16-20020a170906409000b00993b02dd96dsi15129346ejj.372.2023.07.17.04.46.00; Mon, 17 Jul 2023 04:46:24 -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=gdizMM9J; 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 S230364AbjGQLhm (ORCPT + 99 others); Mon, 17 Jul 2023 07:37:42 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47088 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230303AbjGQLhg (ORCPT ); Mon, 17 Jul 2023 07:37:36 -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 84FAF170D for ; Mon, 17 Jul 2023 04:37:30 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-57704af0e64so40031707b3.0 for ; Mon, 17 Jul 2023 04:37:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1689593849; x=1692185849; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=rcW4dTWuK29JOsV2I2tZPVBrCL3mh4Imj+/5bJ9CoOk=; b=gdizMM9JyFRaSyLcM5RbfD5tdIJu0mKai4Fl0ObvuOf0O+6+HTWyseniNFOwWjh3Qw fQzlw0f8mj2Ty4njDT81A7x0jBPrrVHBaCiBSek6cmPi9tsBRAxPpJ9cw6SuET75wgY3 vk29kv+TX/1lm1/9tHeZLrieK/MaSI+20x0iOVdm3B1NwzNpkjNA4U2+WtNFDuAuRVjo c0+PUisiBVn5cqCUfbCfUyoMEvB5aS8I39dXhgD1Oz6WcuQ1U8FGP6jSXnP79P6zvmB4 1q4XuzwuWUCPj7nklypjtmX/4s7wJwxGiIuOOMkuuvKZwTsheaK1x9w0oa6h7LRQdpLZ xhWA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689593849; x=1692185849; 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=rcW4dTWuK29JOsV2I2tZPVBrCL3mh4Imj+/5bJ9CoOk=; b=E4NmBkV2Aog/6Ez8lSOc1V+WWGsKHLjZ65t8GT/G/LFM2k5wNgh/yrmFMjVfSvM3eZ VG7welrcc/FURuIXVB0l8OMfZ3Iz7WrraAhRSR9CJYSGN/KTT44bUfw38U+75sEinBYg SAwSPTcSI6D1yK47VXjOm6t0x+Rm4wdgbZ2J0f3Fv1jfKgQ9D1GGNbAHVG024WayglJ7 5KRX9qo6xxa3en+Qq+Rau2IVlelzURR3wWmjm2T/hH1HlJ8xs+3fizdQUi+3IbH6NtJh WyMZBFCJPAYbSAqhXhlX5W60gUw/oLyjdobqY0g3bX3W3sTRjvJDmFYC2yueDhuGkF9b 2HlQ== X-Gm-Message-State: ABy/qLaRLb0Tnq03jSiZoyUbPaiocW80hGe7Nf0FZPhEID3sf/Tfz16q knb/HQrfGkUd2tbUG8Yg4qI6P6LOeMM= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:3b6e:8102:6db8:d83f]) (user=glider job=sendgmr) by 2002:a81:de05:0:b0:576:d9ec:3350 with SMTP id k5-20020a81de05000000b00576d9ec3350mr150011ywj.10.1689593849601; Mon, 17 Jul 2023 04:37:29 -0700 (PDT) Date: Mon, 17 Jul 2023 13:37:08 +0200 In-Reply-To: <20230717113709.328671-1-glider@google.com> Mime-Version: 1.0 References: <20230717113709.328671-1-glider@google.com> X-Mailer: git-send-email 2.41.0.255.g8b1d071c50-goog Message-ID: <20230717113709.328671-6-glider@google.com> Subject: [PATCH v3 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, 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-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1771668121576647725 X-GMAIL-MSGID: 1771668121576647725 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 --- 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/Makefile | 5 ++++ arch/arm64/mm/mteswap.c | 20 ++++++------- arch/arm64/mm/mteswap.h | 12 ++++++++ arch/arm64/mm/mteswap_comp.c | 52 ++++++++++++++++++++++++++++++++++ arch/arm64/mm/mteswap_nocomp.c | 38 +++++++++++++++++++++++++ 5 files changed, 116 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..9d8f87fd191a2 100644 --- a/arch/arm64/mm/mteswap.c +++ b/arch/arm64/mm/mteswap.c @@ -5,8 +5,11 @@ #include #include #include + #include +#include "mteswap.h" + static DEFINE_XARRAY(mte_pages); void *mte_allocate_tag_storage(void) @@ -27,20 +30,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 +54,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 +62,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 +76,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..7a369c3fb9c94 --- /dev/null +++ b/arch/arm64/mm/mteswap_comp.c @@ -0,0 +1,52 @@ +// 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]; + unsigned long 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) +{ + unsigned long 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); + } +} +MODULE_IMPORT_NS(MTECOMP); diff --git a/arch/arm64/mm/mteswap_nocomp.c b/arch/arm64/mm/mteswap_nocomp.c new file mode 100644 index 0000000000000..32733998b1879 --- /dev/null +++ b/arch/arm64/mm/mteswap_nocomp.c @@ -0,0 +1,38 @@ +// 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); + } +}