lkml.org 
[lkml]   [2017]   [Dec]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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

\
 
 \ /
  Last update: 2017-12-22 09:43    [W:0.306 / U:0.316 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site