Re: [PATCH v18 05/10] xbitmap: add more operations
On Thu, Dec 07, 2017 at 08:01:24PM +0800, Wei Wang wrote:
> On 12/03/2017 09:50 AM, Tetsuo Handa wrote:
> > Matthew Wilcox wrote:
> > > On Fri, Dec 01, 2017 at 03:09:08PM +, Wang, Wei W wrote:
> > > > On Friday, December 1, 2017 9:02 PM, Tetsuo Handa wrote:
> > > > > If start == end is legal,
> > > > >
> > > > > for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
> > > > >
> > > > > makes this loop do nothing because 10 < 10 is false.
> > > > How about "start <= end "?
> > > Don't ask Tetsuo for his opinion, write some userspace code that uses it.
> > >
> > Please be sure to prepare for "end == -1UL" case, for "start < end" will
> > become
> > true when "start = (start | (IDA_BITMAP_BITS - 1)) + 1" made "start == 0"
> > due to
> > overflow.
>
> I think there is one more corner case with this API: searching for bit "1"
> from [0, ULONG_MAX] while no bit is set in the range, there appear to be no
> possible value that we can return (returning "end + 1" will be "ULONG_MAX +
> 1", which is 0)
> I plan to make the "end" be exclusive of the searching, that is, [start,
> end), and return "end" if no such bit is found.
>
> For cases like [16, 16), returning 16 doesn't mean bit 16 is 1 or 0, it
> simply means there is no bits to search in the given range, since 16 is
> exclusive.
>
> Please let me know if you have a different thought.
>
> Best,
> Wei
Matthew is right though - you want to include tests for all
these corner cases.
___
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
Re: [PATCH v18 05/10] xbitmap: add more operations
On 12/03/2017 09:50 AM, Tetsuo Handa wrote:
Matthew Wilcox wrote:
On Fri, Dec 01, 2017 at 03:09:08PM +, Wang, Wei W wrote:
On Friday, December 1, 2017 9:02 PM, Tetsuo Handa wrote:
If start == end is legal,
for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
makes this loop do nothing because 10 < 10 is false.
How about "start <= end "?
Don't ask Tetsuo for his opinion, write some userspace code that uses it.
Please be sure to prepare for "end == -1UL" case, for "start < end" will become
true when "start = (start | (IDA_BITMAP_BITS - 1)) + 1" made "start == 0" due to
overflow.
I think there is one more corner case with this API: searching for bit
"1" from [0, ULONG_MAX] while no bit is set in the range, there appear
to be no possible value that we can return (returning "end + 1" will be
"ULONG_MAX + 1", which is 0)
I plan to make the "end" be exclusive of the searching, that is, [start,
end), and return "end" if no such bit is found.
For cases like [16, 16), returning 16 doesn't mean bit 16 is 1 or 0, it
simply means there is no bits to search in the given range, since 16 is
exclusive.
Please let me know if you have a different thought.
Best,
Wei
___
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
Re: [PATCH v18 05/10] xbitmap: add more operations
On Fri, Dec 01, 2017 at 03:09:08PM +, Wang, Wei W wrote:
> On Friday, December 1, 2017 9:02 PM, Tetsuo Handa wrote:
> > If start == end is legal,
> >
> >for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
> >
> > makes this loop do nothing because 10 < 10 is false.
>
> How about "start <= end "?
Don't ask Tetsuo for his opinion, write some userspace code that uses it.
___
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
RE: [PATCH v18 05/10] xbitmap: add more operations
On Friday, December 1, 2017 9:02 PM, Tetsuo Handa wrote:
> Wei Wang wrote:
> > On 11/30/2017 06:34 PM, Tetsuo Handa wrote:
> > > Wei Wang wrote:
> > >> + * @start: the start of the bit range, inclusive
> > >> + * @end: the end of the bit range, inclusive
> > >> + *
> > >> + * This function is used to clear a bit in the xbitmap. If all the
> > >> +bits of the
> > >> + * bitmap are 0, the bitmap will be freed.
> > >> + */
> > >> +void xb_clear_bit_range(struct xb *xb, unsigned long start,
> > >> +unsigned long end) {
> > >> +struct radix_tree_root *root = >xbrt;
> > >> +struct radix_tree_node *node;
> > >> +void **slot;
> > >> +struct ida_bitmap *bitmap;
> > >> +unsigned int nbits;
> > >> +
> > >> +for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) +
> > >> 1) {
> > >> +unsigned long index = start / IDA_BITMAP_BITS;
> > >> +unsigned long bit = start % IDA_BITMAP_BITS;
> > >> +
> > >> +bitmap = __radix_tree_lookup(root, index, , );
> > >> +if (radix_tree_exception(bitmap)) {
> > >> +unsigned long ebit = bit + 2;
> > >> +unsigned long tmp = (unsigned long)bitmap;
> > >> +
> > >> +nbits = min(end - start + 1, BITS_PER_LONG -
> > >> ebit);
> > > "nbits = min(end - start + 1," seems to expect that start == end is
> > > legal for clearing only 1 bit. But this function is no-op if start == end.
> > > Please clarify what "inclusive" intended.
> >
> > If xb_clear_bit_range(xb,10,10), then it is effectively the same as
> > xb_clear_bit(10). Why would it be illegal?
> >
> > "@start inclusive" means that the @start will also be included to be
> > cleared.
>
> If start == end is legal,
>
>for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
>
> makes this loop do nothing because 10 < 10 is false.
How about "start <= end "?
Best,
Wei
___
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
Re: [PATCH v18 05/10] xbitmap: add more operations
On Fri, Dec 01, 2017 at 10:02:01PM +0900, Tetsuo Handa wrote:
> If start == end is legal,
>
>for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
>
> makes this loop do nothing because 10 < 10 is false.
... and this is why we add tests to the test-suite!
___
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
Re: [PATCH v18 05/10] xbitmap: add more operations
On 11/30/2017 06:34 PM, Tetsuo Handa wrote:
Wei Wang wrote:
+ * @start: the start of the bit range, inclusive
+ * @end: the end of the bit range, inclusive
+ *
+ * This function is used to clear a bit in the xbitmap. If all the bits of the
+ * bitmap are 0, the bitmap will be freed.
+ */
+void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end)
+{
+ struct radix_tree_root *root = >xbrt;
+ struct radix_tree_node *node;
+ void **slot;
+ struct ida_bitmap *bitmap;
+ unsigned int nbits;
+
+ for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
+ unsigned long index = start / IDA_BITMAP_BITS;
+ unsigned long bit = start % IDA_BITMAP_BITS;
+
+ bitmap = __radix_tree_lookup(root, index, , );
+ if (radix_tree_exception(bitmap)) {
+ unsigned long ebit = bit + 2;
+ unsigned long tmp = (unsigned long)bitmap;
+
+ nbits = min(end - start + 1, BITS_PER_LONG - ebit);
"nbits = min(end - start + 1," seems to expect that start == end is legal
for clearing only 1 bit. But this function is no-op if start == end.
Please clarify what "inclusive" intended.
If xb_clear_bit_range(xb,10,10), then it is effectively the same as
xb_clear_bit(10). Why would it be illegal?
"@start inclusive" means that the @start will also be included to be
cleared.
+static inline __always_inline void bitmap_clear(unsigned long *map,
+ unsigned int start,
+ unsigned int nbits)
+{
+ if (__builtin_constant_p(nbits) && nbits == 1)
+ __clear_bit(start, map);
+ else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
+__builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
It looks strange to apply __builtin_constant_p test to variables after "& 7".
I think this is normal - if the variables are known at compile time, the
calculation will be done at compile time (termed constant folding).
Best,
Wei
___
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
Re: [PATCH v18 05/10] xbitmap: add more operations
On Thu, Nov 30, 2017 at 10:35:03PM +0900, Tetsuo Handa wrote: > According to xb_set_bit(), it seems to me that we are trying to avoid memory > allocation > for "struct ida_bitmap" when all set bits within a 1024-bits bitmap reside in > the first > 61 bits. > > But does such saving help? Is there characteristic bias that majority of set > bits resides > in the first 61 bits, for "bit" is "unsigned long" which holds a page number > (isn't it)? > If no such bias, wouldn't eliminating radix_tree_exception() case and always > storing > "struct ida_bitmap" simplifies the code (and make the processing faster)? It happens all the time. The vast majority of users of the IDA set low bits. Also, it's the first 62 bits -- going up to 63 bits with the XArray rewrite. I do plan to redo the xbitmap on top of the XArray; I'm just trying to get the XArray merged first. The IDA and xbitmap code will share much more code when that happens. ___ Virtualization mailing list Virtualization@lists.linux-foundation.org https://lists.linuxfoundation.org/mailman/listinfo/virtualization
