From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 0A116E94139 for ; Fri, 6 Oct 2023 22:36:28 +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:In-Reply-To:MIME-Version:References: Message-ID:Subject:Cc:To:From:Date:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=7n2ujRt1k78xkayQl7EbvkTjowJBnhMmsKrK0J6UNtE=; b=Amy0AGaQah5egn nvTO7UWmbq55e+Iy/vxeK+EgVoL7WQypbNb1goNFNDbvbMHyi28SkWWdAr+DXpojF5tfuLGHlWyhu PWWd0czDQ8I/fXnZkj4FS1Rs3/VGqQt6lhfxeQ7F6ZuhBzEfIIPqO4gPH5145UxGwvo1IkfSEIWIf gNj/Rixrd/vchR52T0L+lwGWhrGSsXB+NMSBZwPS4UoPTxcUQQGWBruLM8y03+A2HgOKlJxILLQMT vmvIGYTJAvquv4YHR4/EQ/Y2aNcmZqumi+sXcCkZGUm+4B5BA6I1dRlE9bgpyQRJcvRihb+5ZjWnj pikTWhAybpq30fMutA6A==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.96 #2 (Red Hat Linux)) id 1qotQM-006b2a-0z; Fri, 06 Oct 2023 22:35:58 +0000 Received: from mail-vs1-xe2f.google.com ([2607:f8b0:4864:20::e2f]) by bombadil.infradead.org with esmtps (Exim 4.96 #2 (Red Hat Linux)) id 1qotQJ-006b1H-0A for linux-arm-kernel@lists.infradead.org; Fri, 06 Oct 2023 22:35:56 +0000 Received: by mail-vs1-xe2f.google.com with SMTP id ada2fe7eead31-4529d1238a9so1229115137.3 for ; Fri, 06 Oct 2023 15:35:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1696631751; x=1697236551; darn=lists.infradead.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=llH4t7J63AaEPzQkwWh0fjeekIthRYPqlI68ZdJOsjQ=; b=YjyZhyB58R5aU1wvS2x3a62Vh3mDGoRz6+Cp9BF0evuqv/n+n7yKrNWQc2NuoEmsbQ x2LCYTuqyEIxVtxnR3GCxfJ0V4telpbjN3Ta3R6n7nvX8EUpGWBiSmLD/gQBU0FSLrer CeSShU3M/06WmpcJpMF1n6SEIFnv2VDKQudG54Qlr22y4tPB7dQcr64gp7t7bR6fGQbN v12Wh7Fl8+alQy5AzYh96cWfPZkEzoBGwYbGiX6YcCca9YlEf4MtTsWMfZ22w+on7u2e kxn838lVWI2XSNy/W11xVSWwROSMScnH5xT9PW1YLs6h0eNywK4TN7i6ik7NZDXOcqDl TJRw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696631751; x=1697236551; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=llH4t7J63AaEPzQkwWh0fjeekIthRYPqlI68ZdJOsjQ=; b=SlvIyh/ngv6wk7ZysIAkrS2lLwWPWSWH/P4XBSwrALBuDTmgiHqhzHko/KNISOmyUs xM7VqQiLVaTXOemB3YQqXl9mmnf6BNThCrl0H8TP2+BjsKyJ1C3C/b58OIyF1Jh/GAXL xZp3PQrSeQm4ZNogTzr4UjK4XcoEYpEOnbCGnWNWpBirzuosL7OmtWDc6rsEtLAAWPHd kFt4bYT2q8UJOWQYHgjkqHjlqugd4R3IzsC9lPIWzxttJF+Pgx9d1u3antorSOUcZPRl Uaz0gPkf/8uJufvz5UkcnmjiIMQXoDWWPFkLpERxLkzc1CA/4nW76FSHBiNglUY8ONjc R40A== X-Gm-Message-State: AOJu0YwbJenltEGZ8RKH0knVcEj6Be18Pxi5g6/YdxhryQhr1y08TCec mLOXAFLb+W4sjNdY2IkKBpg= X-Google-Smtp-Source: AGHT+IF76BQbr6TEh2xS8UxB+3VzLAy48WDx4mw3mjz7pDVPFP0whbNxrGwZ7qiuBfoBksODoqduKA== X-Received: by 2002:a67:de97:0:b0:44e:e7d7:6847 with SMTP id r23-20020a67de97000000b0044ee7d76847mr9518443vsk.7.1696631751349; Fri, 06 Oct 2023 15:35:51 -0700 (PDT) Received: from localhost ([2607:fb90:be24:c307:bb4d:85d4:4340:a030]) by smtp.gmail.com with ESMTPSA id n3-20020a67e043000000b004527ba543c6sm1084717vsl.1.2023.10.06.15.35.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 06 Oct 2023 15:35:50 -0700 (PDT) Date: Fri, 6 Oct 2023 15:35:49 -0700 From: Yury Norov To: Alexander Potapenko Cc: catalin.marinas@arm.com, will@kernel.org, pcc@google.com, andreyknvl@gmail.com, andriy.shevchenko@linux.intel.com, aleksander.lobakin@intel.com, linux@rasmusvillemoes.dk, linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, eugenis@google.com, syednwaris@gmail.com, william.gray@linaro.org, Arnd Bergmann Subject: Re: [PATCH v6 1/5] lib/bitmap: add bitmap_{read,write}() Message-ID: References: <20231006134529.2816540-1-glider@google.com> <20231006134529.2816540-2-glider@google.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20231006134529.2816540-2-glider@google.com> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20231006_153555_089499_4E0251A9 X-CRM114-Status: GOOD ( 37.35 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org On Fri, Oct 06, 2023 at 03:45:25PM +0200, Alexander Potapenko wrote: > From: Syed Nayyar Waris > > The two new functions allow reading/writing 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 number of changes and simplifications: > - 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()); > - bitmap_get_value()/bitmap_set_value() are renamed to bitmap_read() > and bitmap_write(); > - some redundant computations are omitted. > > 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 > Co-developed-by: Alexander Potapenko > Signed-off-by: Alexander Potapenko > > --- > This patch was previously called "lib/bitmap: add > bitmap_{set,get}_value()" > (https://lore.kernel.org/lkml/20230720173956.3674987-2-glider@google.com/) > > v6: > - As suggested by Yury Norov, do not require bitmap_read(..., 0) to > return 0. > > v5: > - Address comments by Yury Norov: > - updated code comments and patch title/description > - replace GENMASK(nbits - 1, 0) with BITMAP_LAST_WORD_MASK(nbits) > - more compact bitmap_write() implementation > > v4: > - Address comments by Andy Shevchenko and Yury Norov: > - prevent passing values >= 64 to GENMASK() > - fix commit authorship > - change comments > - check for unlikely(nbits==0) > - drop unnecessary const declarations > - fix kernel-doc comments > - rename bitmap_{get,set}_value() to bitmap_{read,write}() > --- > include/linux/bitmap.h | 68 ++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 68 insertions(+) > > diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h > index 03644237e1efb..e72c054d21d48 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_read(map, start, nbits) Read an nbits-sized value from > + * map at start > * bitmap_set_value8(map, value, start) Set 8bit value to map at start > + * bitmap_write(map, value, start, nbits) Write an nbits-sized value to > + * 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,33 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map, > return (map[index] >> offset) & 0xFF; > } > > +/** > + * bitmap_read - read 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, nonzero, up to BITS_PER_LONG > + * > + * Returns: value of nbits located at the @start bit offset within the @map > + * memory region. > + */ > +static inline unsigned long bitmap_read(const unsigned long *map, > + unsigned long start, > + unsigned long nbits) > +{ > + size_t index = BIT_WORD(start); > + unsigned long offset = start % BITS_PER_LONG; > + unsigned long space = BITS_PER_LONG - offset; > + unsigned long value_low, value_high; > + > + if (unlikely(!nbits)) > + return 0; > + 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 +630,43 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value, > map[index] |= value << offset; > } > > +/** > + * bitmap_write - write n-bit value within a memory region > + * @map: address to the bitmap memory region > + * @value: value to write, clamped to nbits > + * @start: bit offset of the n-bit value > + * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG. > + * > + * bitmap_write() behaves similarly to @nbits calls of assign_bit(), i.e. bits > + * beyond @nbits are ignored: > + * > + * for (bit = 0; bit < nbits; bit++) > + * assign_bit(start + bit, bitmap, val & BIT(bit)); __assign_bit() > + */ 'behaves similarly' sounds like an understatement. I think, it behaves much faster because it can assign up to 64 bits at once, not mentioning the pressure on cache lines traffic. How faster - that's a good question. I'd be really pleased if you add a performance test for bitmap_write/read. Or I can do it myself later. You can find examples in the same lib/test_bitmap.c. > +static inline void bitmap_write(unsigned long *map, > + unsigned long value, > + unsigned long start, unsigned long nbits) > +{ > + size_t index = BIT_WORD(start); > + unsigned long offset = start % BITS_PER_LONG; > + unsigned long space = BITS_PER_LONG - offset; > + unsigned long mask; > + > + if (unlikely(!nbits)) > + return; can you please add more empty lines to separate blocks visually? > + mask = BITMAP_LAST_WORD_MASK(nbits); > + value &= mask; > + if (space >= nbits) { > + map[index] &= ~(mask << 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); > +} I compiled the below fix on spark64 BE machine: --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -608,7 +608,7 @@ static inline unsigned long bitmap_read(const unsigned long *map, if (unlikely(!nbits)) return 0; if (space >= nbits) - return (map[index] >> offset) & GENMASK(nbits - 1, 0); + return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits); 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); @@ -661,9 +661,9 @@ static inline void bitmap_write(unsigned long *map, map[index] |= value << offset; return; } - map[index] &= ~BITMAP_FIRST_WORD_MASK(start); + map[index] &= BITMAP_LAST_WORD_MASK(start); map[index] |= value << offset; - map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits); + map[index + 1] &= BITMAP_FIRST_WORD_MASK(start + nbits); map[index + 1] |= (value >> space); } All the tests are passed just as before, and there's no any difference reported by bloat-o-meter. Can you please use non-negation versions as they are more straightforward? > + > #endif /* __ASSEMBLY__ */ > > #endif /* __LINUX_BITMAP_H */ > -- > 2.42.0.609.gbb76f46606-goog _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel