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: 13311994 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 6E342EB64DD for ; Thu, 13 Jul 2023 12:58:01 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:Cc:To:From:Subject:Message-ID: References:Mime-Version:In-Reply-To:Date:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=zbmNfzdlJ/Te5BESmFRtMTuFAJOMN/AhcRdDFxNkV0I=; b=Z1/qyo6S9JMzdyMZct7AYyYl05 J4oLhn61Xc1iab4PYRM3A7BENwmtxIE8mhZVldvH91KDF8yFS8HT7xWttx7eRicJz0ZD9k8NTDr69 K/U+w1aYqfVqnO3E28s701N51aqXIz+a2s0fk43VgwvuS7QcJEYqpMiknVUzOtV1jWIQ5a2s98Zz5 27U/XmQet9eKsyFBU9fFSuWWiaN3+3EYv5jbOFSx3mFx/jz2lGRrGFdKr3uDMG2DGSrssLezqzMKZ CnQvOGs7mGLWOy7L72dMAOME42yPr+CJBRFJScngZgkbdT3Xo9ARsZad48MEanOAzXwbeRqE/WqLj tHTs3/GA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.96 #2 (Red Hat Linux)) id 1qJvsz-003Jh1-02; Thu, 13 Jul 2023 12:57:33 +0000 Received: from mail-ed1-x549.google.com ([2a00:1450:4864:20::549]) by bombadil.infradead.org with esmtps (Exim 4.96 #2 (Red Hat Linux)) id 1qJvsw-003JgL-1w for linux-arm-kernel@lists.infradead.org; Thu, 13 Jul 2023 12:57:32 +0000 Received: by mail-ed1-x549.google.com with SMTP id 4fb4d7f45d1cf-506b21104faso443088a12.1 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=LLCRD4ohzCypO3h4r0aHMThVWqZUSBsmjFdgtT+djpjn7j42lUrtCKfhWCppCZv2LN +uE1lqfYd7CNHGU6h+qr9op7xWHNsJ8uWvOAjzKaOvBlnazZOX/PjHVPaM8nx0WpsHAV Bg8CdkEP+HQwQex4CuNWBx7fa8iWdC+9HLZ8LHzxj214vtMWKfbbqsJyRofbkx0HBvbV +ZGSHaU0KSVlhRr+9zJPR5V6944avcDl9gpBX8zZWZFyVJN1qSZ6iL5GboRNmtzLLj4w p75z7tsDRFtrljUsrubz15ownE+Fq0wbzFwKZkpLhUmCZFWf0WqcmpHj+JJ+ABmJ7Srq WfAw== X-Gm-Message-State: ABy/qLYv0mxaX9Yp0Qdg/UGsV5vJWaC1xWy+9w978I5KxzHGLTFokV93 NVPoJIsWuz9mJ+JR+qbM6mO13hGfD7w= X-Google-Smtp-Source: APBJJlEzRUl9pOBtatK4TP7+ubEzsIeS9vByW92Acf7+09gdvZcE2hYQqa4F1F4VhS3O4Pv4tFWgxxihdQs= 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-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20230713_055730_643319_0E12971C X-CRM114-Status: GOOD ( 13.83 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org 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 */