| Message ID | 20220713163201.136202-1-sebastian.fricke@collabora.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | RkVDEC HEVC driver | expand |
On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote: > Add a new helper to set variable length values within a bitmap, that can > overflow the borders of a single BITS_PER_LONG container. > This function makes it easier to write values to hardware memory blobs that > do not require alignment. > > Add tests to the lib/test_bitmap.c kselftest module to verify proper function. > > Signed-off-by: Sebastian Fricke <sebastian.fricke@collabora.com> > --- > include/linux/bitmap.h | 40 +++++++++++++++++++++++++++++++++++ > lib/test_bitmap.c | 48 ++++++++++++++++++++++++++++++++++++++++++ > 2 files changed, 88 insertions(+) > > diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h > index 2e6cd5681040..9f8d635b70a9 100644 > --- a/include/linux/bitmap.h > +++ b/include/linux/bitmap.h > @@ -76,6 +76,7 @@ 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_set_value(map, value, start, nbits) Set a variable length 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 > @@ -573,6 +574,45 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value, > map[index] |= value << offset; > } > > +/** > + * bitmap_set_value - set a variable length value within a memory region > + * @map: address to the bitmap memory region > + * @value: the variable length value > + * @start: bit offset of the value > + * @length: Length of the value There's no such thing like a length of value. Data structures and types have size, and arrays have length. > + */ > +static inline void bitmap_set_value(unsigned long *map, unsigned long value, > + unsigned long start, unsigned char length) > +{ > + size_t index = BIT_WORD(start); > + unsigned long offset = start % BITS_PER_LONG; > + int diff_to_max = 0; > + > + if (!length) > + return; > + > + 2nd empty line is not needed. Actually, all this chunk is not needed because 'while (length > 0)' will do the work. > + if (length < BITS_PER_LONG) > + value &= (BIT(length) - 1); > + > + while (length > 0) { > + diff_to_max = BITS_PER_LONG - offset; > + map[index] &= ~((BIT(length) - 1) << offset); > + if (length > diff_to_max) { > + unsigned long tmp = value & (BIT(diff_to_max) - 1); We have GENMASK() for this. > + > + map[index] |= tmp << offset; > + value >>= diff_to_max; > + length -= diff_to_max; > + index += 1; > + offset = 0; > + } else { > + map[index] |= value << offset; > + length = 0; > + } > + } I have a strong feeling that this can be written much simpler... But anyways, this is not suitable for generic bitmaps because this bitmap_set_value() is limited with a single words. All bitmap functions that copy data to/from bitmap are able to work with bigger chunks. (With the exception of bitmap_{set,get}_value8, which doesn't allow unaligned accesses.) What you want is to copy bits to the dst bitmap starting from the offset, right? It's very similar to what bitmap_set() does, except that it always 'copies' ~0UL. I'd suggest you to try implementing bitmap_copy_from(dst, src, dst_off, len) or even bitmap_copy_from(dst, dst_off, src, src_off, len) if you expect that you'll need more flexibility in the future. This bitmap_copy_from() may be based, for example, on extended version of __bitmap_set(): void __bitmap_set(unsigned long *dst, unsigned long *src, unsigned int start, int len) Thanks, Yury > +} > + > #endif /* __ASSEMBLY__ */ > > #endif /* __LINUX_BITMAP_H */ > diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c > index d5923a640457..509317ad2f72 100644 > --- a/lib/test_bitmap.c > +++ b/lib/test_bitmap.c > @@ -869,6 +869,53 @@ static void __init test_bitmap_print_buf(void) > } > } > > +struct test_bitmap_set_value_sample { > + unsigned long value[2]; > + unsigned char length[2]; > + unsigned int offset[2]; > + unsigned long expected[2][2]; > + int amount; > +}; > + > +static const struct test_bitmap_set_value_sample test_set[] __initconst = { > + /* Check that multiple values can be chained up */ > + { {10, 20}, {4, 5}, {0, 4}, {{10, 330}}, 2 }, > + /* Check that a value can be set across two BITS_PER_LONG chunks */ > + { {10, 6}, {4, 3}, {0, 63}, {{10, 10}, {0, 3}}, 2 }, > + /* Set a value with length shorter than the given length */ > + { {3, 6}, {4, 10}, {0, 4}, {{3, 99}}, 1 }, > + /* Set a value with length longer than the given length */ > + { {15}, {2}, {0}, {{3}}, 1 }, > + /* Check that values are properly overwritten */ > + { {15, 12}, {4, 4}, {0, 2}, {{15, 51}}, 2 }, > + /* Check that a set without a length doesn't change anything */ > + { {10}, {0}, {0}, {{0}}, 1 }, > +}; > + > +static void __init test_bitmap_set_value(void) > +{ > + int i, j, k; > + int correct_tests = 0; > + > + for (i = 0; i < ARRAY_SIZE(test_set); i++) { > + const struct test_bitmap_set_value_sample *t = &test_set[i]; > + int test_correct = 1; > + DECLARE_BITMAP(map, BITS_PER_LONG * 2); > + > + bitmap_zero(map, BITS_PER_LONG * 2); > + for (j = 0; j < t->amount; j++) { > + bitmap_set_value(map, t->value[j], t->offset[j], t->length[j]); > + for (k = 0; k < 2; k++) { > + if (expect_eq_uint(map[k], t->expected[k][j])) > + test_correct = 0; > + } > + } > + if (test_correct) > + correct_tests += 1; > + } > + pr_err("set_value: %d/%ld tests correct\n", correct_tests, ARRAY_SIZE(test_set)); > +} > + > static void __init selftest(void) > { > test_zero_clear(); > @@ -884,6 +931,7 @@ static void __init selftest(void) > test_for_each_set_clump8(); > test_bitmap_cut(); > test_bitmap_print_buf(); > + test_bitmap_set_value(); > } > > KSTM_MODULE_LOADERS(test_bitmap); > -- > 2.25.1
On Wed, Jul 13, 2022 at 8:56 PM Yury Norov <yury.norov@gmail.com> wrote: > On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote: ... > I'd suggest you to try implementing > bitmap_copy_from(dst, src, dst_off, len) > or even > bitmap_copy_from(dst, dst_off, src, src_off, len) > if you expect that you'll need more flexibility in the future. Do you think it would be useful? We have bitmap_replace() & bitmap_remap(). Wouldn't that be enough?
On Wed, Jul 13, 2022 at 09:10:33PM +0200, Andy Shevchenko wrote: > On Wed, Jul 13, 2022 at 8:56 PM Yury Norov <yury.norov@gmail.com> wrote: > > On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote: > > ... > > > I'd suggest you to try implementing > > bitmap_copy_from(dst, src, dst_off, len) > > or even > > bitmap_copy_from(dst, dst_off, src, src_off, len) > > if you expect that you'll need more flexibility in the future. > > Do you think it would be useful? > > We have bitmap_replace() & bitmap_remap(). Wouldn't that be enough? bitmap_replace and bitmap_remap have no an 'offset' parameter.
On Wed, Jul 13, 2022 at 9:44 PM Yury Norov <yury.norov@gmail.com> wrote: > On Wed, Jul 13, 2022 at 09:10:33PM +0200, Andy Shevchenko wrote: > > On Wed, Jul 13, 2022 at 8:56 PM Yury Norov <yury.norov@gmail.com> wrote: > > > On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote: > > > > ... > > > > > I'd suggest you to try implementing > > > bitmap_copy_from(dst, src, dst_off, len) > > > or even > > > bitmap_copy_from(dst, dst_off, src, src_off, len) > > > if you expect that you'll need more flexibility in the future. > > > > Do you think it would be useful? > > > > We have bitmap_replace() & bitmap_remap(). Wouldn't that be enough? > > bitmap_replace and bitmap_remap have no an 'offset' parameter. True. But then it's a bit too generic to have this src_off, no? I would rather expect for asymmetrical bitmaps that the other side will be either one of the fixed width types (it makes sense to have for 32- or 64-bit arguments. When you have a source bitmap of x bits and you would like to copy it into a y-bit one, I would think that either you have a small amount of bits in x anyway, or x is a full-sized bitmap (same order as y). Also keep in mind that granularity is long, so less than long it makes no sense. bitmap_copy_from_T(unsigned long *map, start, len, T src), where T is type, start is the offset in map, len is the amount of bits from src starting from 0. That's what is required in most of the cases I believe.
On Wed, Jul 13, 2022 at 10:14:24PM +0200, Andy Shevchenko wrote: > On Wed, Jul 13, 2022 at 9:44 PM Yury Norov <yury.norov@gmail.com> wrote: > > On Wed, Jul 13, 2022 at 09:10:33PM +0200, Andy Shevchenko wrote: > > > On Wed, Jul 13, 2022 at 8:56 PM Yury Norov <yury.norov@gmail.com> wrote: > > > > On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote: > > > > > > ... > > > > > > > I'd suggest you to try implementing > > > > bitmap_copy_from(dst, src, dst_off, len) > > > > or even > > > > bitmap_copy_from(dst, dst_off, src, src_off, len) > > > > if you expect that you'll need more flexibility in the future. > > > > > > Do you think it would be useful? > > > > > > We have bitmap_replace() & bitmap_remap(). Wouldn't that be enough? > > > > bitmap_replace and bitmap_remap have no an 'offset' parameter. > > True. > > But then it's a bit too generic to have this src_off, no? That's why I said: > > > > if you expect that you'll need more flexibility in the future. My preferred option is bitmap_copy_from(dst, src, dst_off, len). > I would rather expect for asymmetrical bitmaps that the other side > will be either one of the fixed width types (it makes sense to have > for 32- or 64-bit arguments. Look at patch #6 - it copies 1,4,5,9,10,32,37... - pretty much a random number number of bits. > When you have a source bitmap of x bits and you would like to copy it > into a y-bit one, I would think that either you have a small amount of > bits in x anyway, or x is a full-sized bitmap (same order as y). It sounds like a speculation to me. Why shouldn't we let people to copy with an offset any number of bits? > Also > keep in mind that granularity is long, so less than long it makes no > sense. > > bitmap_copy_from_T(unsigned long *map, start, len, T src), > > where T is type, start is the offset in map, len is the amount of bits > from src starting from 0. That's what is required in most of the cases > I believe. But not in Sebastian's case, according to patch #6. Thanks, Yury
On Wed, Jul 13, 2022 at 01:42:17PM -0700, Yury Norov wrote: > On Wed, Jul 13, 2022 at 10:14:24PM +0200, Andy Shevchenko wrote: > > On Wed, Jul 13, 2022 at 9:44 PM Yury Norov <yury.norov@gmail.com> wrote: > > > On Wed, Jul 13, 2022 at 09:10:33PM +0200, Andy Shevchenko wrote: > > > > On Wed, Jul 13, 2022 at 8:56 PM Yury Norov <yury.norov@gmail.com> wrote: > > > > > On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote: ... > > > > > I'd suggest you to try implementing > > > > > bitmap_copy_from(dst, src, dst_off, len) > > > > > or even > > > > > bitmap_copy_from(dst, dst_off, src, src_off, len) > > > > > if you expect that you'll need more flexibility in the future. > > > > > > > > Do you think it would be useful? > > > > > > > > We have bitmap_replace() & bitmap_remap(). Wouldn't that be enough? > > > > > > bitmap_replace and bitmap_remap have no an 'offset' parameter. > > > > True. > > > > But then it's a bit too generic to have this src_off, no? > > That's why I said: > > > > > > if you expect that you'll need more flexibility in the future. > > My preferred option is bitmap_copy_from(dst, src, dst_off, len). > > > I would rather expect for asymmetrical bitmaps that the other side > > will be either one of the fixed width types (it makes sense to have > > for 32- or 64-bit arguments. > > Look at patch #6 - it copies 1,4,5,9,10,32,37... - pretty much a random > number number of bits. It's too poor randomness, as u64 covers all what in patch 6. > > When you have a source bitmap of x bits and you would like to copy it > > into a y-bit one, I would think that either you have a small amount of > > bits in x anyway, or x is a full-sized bitmap (same order as y). > > It sounds like a speculation to me. Why shouldn't we let people to > copy with an offset any number of bits? Because it's a common case. You have a value in the register / variable, which naturally is one of the POD types. Now you want to inject this into bitmap at the arbitrary offset. Value itself also needs to be variadic size in bits. Basically what he is trying to achieve is something like bitfield.h API over bitmaps. Dunno, if actually bitfield.h in the certain driver wouldn't be enough. > > Also > > keep in mind that granularity is long, so less than long it makes no > > sense. > > > > bitmap_copy_from_T(unsigned long *map, start, len, T src), > > > > where T is type, start is the offset in map, len is the amount of bits > > from src starting from 0. That's what is required in most of the cases > > I believe. > > But not in Sebastian's case, according to patch #6. I think it's a case, see above.
Hey Yury and Andy, thanks for you review and discussion, after some further communication with Nicolas Dufresne and Andrzej Pietrasiewicz, we came to the conclusion that I will prepare a more general bit-writer API, which fits better to the use-case we have on a lot of multimedia hardware. I'll probably reuse the bitmap API as the backbone of that implementation and use the `*_set8` to write the content back to memory, but as we have a few more potential users for such an API, I'll strive towards creating a new kernel API instead of extending an existing API that isn't designed for our use-case. Thanks a lot for your input and ideas. Greetings, Sebastian On 14.07.2022 14:24, Andy Shevchenko wrote: >On Wed, Jul 13, 2022 at 01:42:17PM -0700, Yury Norov wrote: >> On Wed, Jul 13, 2022 at 10:14:24PM +0200, Andy Shevchenko wrote: >> > On Wed, Jul 13, 2022 at 9:44 PM Yury Norov <yury.norov@gmail.com> wrote: >> > > On Wed, Jul 13, 2022 at 09:10:33PM +0200, Andy Shevchenko wrote: >> > > > On Wed, Jul 13, 2022 at 8:56 PM Yury Norov <yury.norov@gmail.com> wrote: >> > > > > On Wed, Jul 13, 2022 at 06:31:59PM +0200, Sebastian Fricke wrote: > >... > >> > > > > I'd suggest you to try implementing >> > > > > bitmap_copy_from(dst, src, dst_off, len) >> > > > > or even >> > > > > bitmap_copy_from(dst, dst_off, src, src_off, len) >> > > > > if you expect that you'll need more flexibility in the future. >> > > > >> > > > Do you think it would be useful? >> > > > >> > > > We have bitmap_replace() & bitmap_remap(). Wouldn't that be enough? >> > > >> > > bitmap_replace and bitmap_remap have no an 'offset' parameter. >> > >> > True. >> > >> > But then it's a bit too generic to have this src_off, no? >> >> That's why I said: >> >> > > > > if you expect that you'll need more flexibility in the future. >> >> My preferred option is bitmap_copy_from(dst, src, dst_off, len). >> >> > I would rather expect for asymmetrical bitmaps that the other side >> > will be either one of the fixed width types (it makes sense to have >> > for 32- or 64-bit arguments. >> >> Look at patch #6 - it copies 1,4,5,9,10,32,37... - pretty much a random >> number number of bits. > >It's too poor randomness, as u64 covers all what in patch 6. > >> > When you have a source bitmap of x bits and you would like to copy it >> > into a y-bit one, I would think that either you have a small amount of >> > bits in x anyway, or x is a full-sized bitmap (same order as y). >> >> It sounds like a speculation to me. Why shouldn't we let people to >> copy with an offset any number of bits? > >Because it's a common case. You have a value in the register / variable, which >naturally is one of the POD types. Now you want to inject this into bitmap at >the arbitrary offset. Value itself also needs to be variadic size in bits. > >Basically what he is trying to achieve is something like bitfield.h API over >bitmaps. Dunno, if actually bitfield.h in the certain driver wouldn't be >enough. > >> > Also >> > keep in mind that granularity is long, so less than long it makes no >> > sense. >> > >> > bitmap_copy_from_T(unsigned long *map, start, len, T src), >> > >> > where T is type, start is the offset in map, len is the amount of bits >> > from src starting from 0. That's what is required in most of the cases >> > I believe. >> >> But not in Sebastian's case, according to patch #6. > >I think it's a case, see above. > >-- >With Best Regards, >Andy Shevchenko > >
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 2e6cd5681040..9f8d635b70a9 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -76,6 +76,7 @@ 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_set_value(map, value, start, nbits) Set a variable length 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 @@ -573,6 +574,45 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value, map[index] |= value << offset; } +/** + * bitmap_set_value - set a variable length value within a memory region + * @map: address to the bitmap memory region + * @value: the variable length value + * @start: bit offset of the value + * @length: Length of the value + */ +static inline void bitmap_set_value(unsigned long *map, unsigned long value, + unsigned long start, unsigned char length) +{ + size_t index = BIT_WORD(start); + unsigned long offset = start % BITS_PER_LONG; + int diff_to_max = 0; + + if (!length) + return; + + + if (length < BITS_PER_LONG) + value &= (BIT(length) - 1); + + while (length > 0) { + diff_to_max = BITS_PER_LONG - offset; + map[index] &= ~((BIT(length) - 1) << offset); + if (length > diff_to_max) { + unsigned long tmp = value & (BIT(diff_to_max) - 1); + + map[index] |= tmp << offset; + value >>= diff_to_max; + length -= diff_to_max; + index += 1; + offset = 0; + } else { + map[index] |= value << offset; + length = 0; + } + } +} + #endif /* __ASSEMBLY__ */ #endif /* __LINUX_BITMAP_H */ diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index d5923a640457..509317ad2f72 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -869,6 +869,53 @@ static void __init test_bitmap_print_buf(void) } } +struct test_bitmap_set_value_sample { + unsigned long value[2]; + unsigned char length[2]; + unsigned int offset[2]; + unsigned long expected[2][2]; + int amount; +}; + +static const struct test_bitmap_set_value_sample test_set[] __initconst = { + /* Check that multiple values can be chained up */ + { {10, 20}, {4, 5}, {0, 4}, {{10, 330}}, 2 }, + /* Check that a value can be set across two BITS_PER_LONG chunks */ + { {10, 6}, {4, 3}, {0, 63}, {{10, 10}, {0, 3}}, 2 }, + /* Set a value with length shorter than the given length */ + { {3, 6}, {4, 10}, {0, 4}, {{3, 99}}, 1 }, + /* Set a value with length longer than the given length */ + { {15}, {2}, {0}, {{3}}, 1 }, + /* Check that values are properly overwritten */ + { {15, 12}, {4, 4}, {0, 2}, {{15, 51}}, 2 }, + /* Check that a set without a length doesn't change anything */ + { {10}, {0}, {0}, {{0}}, 1 }, +}; + +static void __init test_bitmap_set_value(void) +{ + int i, j, k; + int correct_tests = 0; + + for (i = 0; i < ARRAY_SIZE(test_set); i++) { + const struct test_bitmap_set_value_sample *t = &test_set[i]; + int test_correct = 1; + DECLARE_BITMAP(map, BITS_PER_LONG * 2); + + bitmap_zero(map, BITS_PER_LONG * 2); + for (j = 0; j < t->amount; j++) { + bitmap_set_value(map, t->value[j], t->offset[j], t->length[j]); + for (k = 0; k < 2; k++) { + if (expect_eq_uint(map[k], t->expected[k][j])) + test_correct = 0; + } + } + if (test_correct) + correct_tests += 1; + } + pr_err("set_value: %d/%ld tests correct\n", correct_tests, ARRAY_SIZE(test_set)); +} + static void __init selftest(void) { test_zero_clear(); @@ -884,6 +931,7 @@ static void __init selftest(void) test_for_each_set_clump8(); test_bitmap_cut(); test_bitmap_print_buf(); + test_bitmap_set_value(); } KSTM_MODULE_LOADERS(test_bitmap);
Add a new helper to set variable length values within a bitmap, that can overflow the borders of a single BITS_PER_LONG container. This function makes it easier to write values to hardware memory blobs that do not require alignment. Add tests to the lib/test_bitmap.c kselftest module to verify proper function. Signed-off-by: Sebastian Fricke <sebastian.fricke@collabora.com> --- include/linux/bitmap.h | 40 +++++++++++++++++++++++++++++++++++ lib/test_bitmap.c | 48 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 88 insertions(+)