[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations
On 12/21/2017 10:37 PM, Tetsuo Handa wrote:
Matthew Wilcox wrote:+/** + * xb_find_set - find the next set bit in a range of bits + * @xb: the xbitmap to search from + * @offset: the offset in the range to start searching + * @size: the size of the range + * + * Returns: the found bit or, @size if no set bit is found. + */ +unsigned long xb_find_set(struct xb *xb, unsigned long size, + unsigned long offset) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void __rcu **slot; + struct ida_bitmap *bitmap; + unsigned long index = offset / IDA_BITMAP_BITS; + unsigned long index_end = size / IDA_BITMAP_BITS; + unsigned long bit = offset % IDA_BITMAP_BITS; + + if (unlikely(offset >= size)) + return size; + + while (index <= index_end) { + unsigned long ret; + unsigned int nbits = size - index * IDA_BITMAP_BITS; + + bitmap = __radix_tree_lookup(root, index, &node, &slot); + + if (!node && !bitmap) + return size; + + if (bitmap) { + if (nbits > IDA_BITMAP_BITS) + nbits = IDA_BITMAP_BITS; + + ret = find_next_bit(bitmap->bitmap, nbits, bit); + if (ret != nbits) + return ret + index * IDA_BITMAP_BITS; + } + bit = 0; + index++; + } + + return size; +} +EXPORT_SYMBOL(xb_find_set);This is going to be slower than the implementation I sent yesterday. If I call: xb_init(xb); xb_set_bit(xb, ULONG_MAX); xb_find_set(xb, ULONG_MAX, 0); it's going to call __radix_tree_lookup() 16 quadrillion times. My implementation will walk the tree precisely once.Yes. Wei's patch still can not work. We should start reviewing Matthew's implementation.
It runs without any issue on my machine. I didn't generate an "xbitmap" executable (I just found adding xbitmap executable causes a build error due to a Makefile error), instead, I tested it within "main" and it passed all the tests.
Matthew has implemented a new version, let's start from there. Best, Wei
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]