search for: xb_find_next_bit

...ing is zero. Another missing optimisation above is that we always restart the radix tree walk from the top instead of simply moving on to the next bitmap. This is still a thousand times faster than the implementation you posted, but I'd be keen to add that optimisation too. > +/** > + * xb_find_next_bit - find next 1 or 0 in the give range of bits > + * @xb: the xbitmap that the bits reside in > + * @start: the start of the range, inclusive > + * @end: the end of the range, inclusive > + * @set: the polarity (1 or 0) of the next bit to find > + * > + * Return the index of the fou...

...ing is zero. Another missing optimisation above is that we always restart the radix tree walk from the top instead of simply moving on to the next bitmap. This is still a thousand times faster than the implementation you posted, but I'd be keen to add that optimisation too. > +/** > + * xb_find_next_bit - find next 1 or 0 in the give range of bits > + * @xb: the xbitmap that the bits reside in > + * @start: the start of the range, inclusive > + * @end: the end of the range, inclusive > + * @set: the polarity (1 or 0) of the next bit to find > + * > + * Return the index of the fou...

...ed long sg_pfn_start, sg_pfn_end; > > > + void *sg_addr; > > > + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); > > > + > > > + sg_pfn_start = page_xb_start; > > > + while (sg_pfn_start < page_xb_end) { > > > + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, > > > + page_xb_end, 1); > > > + if (sg_pfn_start == page_xb_end + 1) > > > + break; > > > + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, > > > + page_xb_end, 0); > > &gt...

...ed long sg_pfn_start, sg_pfn_end; > > > + void *sg_addr; > > > + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); > > > + > > > + sg_pfn_start = page_xb_start; > > > + while (sg_pfn_start < page_xb_end) { > > > + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, > > > + page_xb_end, 1); > > > + if (sg_pfn_start == page_xb_end + 1) > > > + break; > > > + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, > > > + page_xb_end, 0); > > &gt...

On 12/15/2017 12:29 AM, Tetsuo Handa wrote: > Wei Wang wrote: >> I used the example of xb_clear_bit_range(), and xb_find_next_bit() is >> the same fundamentally. Please let me know if anywhere still looks fuzzy. > I don't think it is the same for xb_find_next_bit() with set == 0. > > + if (radix_tree_exception(bmap)) { > + unsigned long tmp = (unsigned long)bmap; > + unsigned long ebit = bit + 2;...

...void *sg_addr; > > > > > + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); > > > > > + > > > > > + sg_pfn_start = page_xb_start; > > > > > + while (sg_pfn_start < page_xb_end) { > > > > > + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, > > > > > + page_xb_end, 1); > > > > > + if (sg_pfn_start == page_xb_end + 1) > > > > > + break; > > > > > + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, > > > &g...

...void *sg_addr; > > > > > + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); > > > > > + > > > > > + sg_pfn_start = page_xb_start; > > > > > + while (sg_pfn_start < page_xb_end) { > > > > > + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, > > > > > + page_xb_end, 1); > > > > > + if (sg_pfn_start == page_xb_end + 1) > > > > > + break; > > > > > + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, > > > &g...

...RT_SYMBOL(xb_clear_bit_range); + +/** * xb_test_bit - test a bit in the xbitmap * @xb: the xbitmap tree used to record the bit * @bit: index of the bit to test @@ -143,6 +229,87 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit) } EXPORT_SYMBOL(xb_test_bit); +static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, + unsigned long end, bool set) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bmap; + unsigned long ret = end; + + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) +...

...S - bit); + + if (nbits != IDA_BITMAP_BITS) + bitmap_clear(bitmap->bitmap, bit, nbits); + + if (nbits == IDA_BITMAP_BITS || + bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { + kfree(bitmap); + __radix_tree_delete(root, node, slot); + } + } + } +} + +static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, + unsigned long end, bool set) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bmap; + unsigned long ret = end + 1; + + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1...

...3, 1024) are all 0s. - The starting bit 66 already exceeds the the exceptional entry bit range [0, 62], and with the fact that the rest of bits are all 0s, so it is time to just "continue", which goes to the second range [1024, 2048) I used the example of xb_clear_bit_range(), and xb_find_next_bit() is the same fundamentally. Please let me know if anywhere still looks fuzzy. > >> if (set) >> ret = find_next_bit(&tmp, >> BITS_PER_LONG, ebit); >> else >>...

...fn_start, sg_pfn_end; >>>> + void *sg_addr; >>>> + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); >>>> + >>>> + sg_pfn_start = page_xb_start; >>>> + while (sg_pfn_start < page_xb_end) { >>>> + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, >>>> + page_xb_end, 1); >>>> + if (sg_pfn_start == page_xb_end + 1) >>>> + break; >>>> + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, >>>> + page_xb_end, 0); &gt...

...rn false; + if (radix_tree_exception(bitmap)) { + bit += RADIX_TREE_EXCEPTIONAL_SHIFT; + if (bit > BITS_PER_LONG) + return false; + return (unsigned long)bitmap & (1UL << bit); + } + + return test_bit(bit, bitmap->bitmap); +} +EXPORT_SYMBOL(xb_test_bit); + +static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, + unsigned long end, bool set) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bmap; + unsigned long ret = end + 1; + + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1...

...queue *vq, + unsigned long page_xb_start, + unsigned long page_xb_end) +{ + unsigned long sg_pfn_start, sg_pfn_end; + void *sg_addr; + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); + + sg_pfn_start = page_xb_start; + while (sg_pfn_start < page_xb_end) { + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, + page_xb_end, 1); + if (sg_pfn_start == page_xb_end + 1) + break; + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, + page_xb_end, 0); + sg_addr = pfn_to_kaddr(sg_pfn_start); + sg_len = (sg_pfn_end - sg_pfn_start) <&lt...

...her in the previous implementation; 2) Simpler function to get the free page block. v7->v8: 1) Use only one chunk format, instead of two. 2) re-write the virtio-balloon implementation patch. 3) commit changes 4) patch re-org Matthew Wilcox (1): Introduce xbitmap Wei Wang (4): xbitmap: add xb_find_next_bit() and xb_zero() virtio-balloon: VIRTIO_BALLOON_F_SG mm: support reporting free page blocks virtio-balloon: VIRTIO_BALLOON_F_FREE_PAGE_VQ drivers/virtio/virtio_balloon.c | 302 +++++++++++++++++++++++++++++++----- include/linux/mm.h | 7 + include/linux/mmzone.h...

...her in the previous implementation; 2) Simpler function to get the free page block. v7->v8: 1) Use only one chunk format, instead of two. 2) re-write the virtio-balloon implementation patch. 3) commit changes 4) patch re-org Matthew Wilcox (1): Introduce xbitmap Wei Wang (4): xbitmap: add xb_find_next_bit() and xb_zero() virtio-balloon: VIRTIO_BALLOON_F_SG mm: support reporting free page blocks virtio-balloon: VIRTIO_BALLOON_F_FREE_PAGE_VQ drivers/virtio/virtio_balloon.c | 302 +++++++++++++++++++++++++++++++----- include/linux/mm.h | 7 + include/linux/mmzone.h...

...> + unsigned long page_xb_end) > +{ > + unsigned long sg_pfn_start, sg_pfn_end; > + void *sg_addr; > + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); > + > + sg_pfn_start = page_xb_start; > + while (sg_pfn_start < page_xb_end) { > + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, > + page_xb_end, 1); > + if (sg_pfn_start == page_xb_end + 1) > + break; > + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, > + page_xb_end, 0); > + sg_addr = pfn_to_kaddr(sg_pfn_start); > + sg_len =...

...> + unsigned long page_xb_end) > +{ > + unsigned long sg_pfn_start, sg_pfn_end; > + void *sg_addr; > + uint32_t sg_len, sg_max_len = round_down(UINT_MAX, PAGE_SIZE); > + > + sg_pfn_start = page_xb_start; > + while (sg_pfn_start < page_xb_end) { > + sg_pfn_start = xb_find_next_bit(&vb->page_xb, sg_pfn_start, > + page_xb_end, 1); > + if (sg_pfn_start == page_xb_end + 1) > + break; > + sg_pfn_end = xb_find_next_bit(&vb->page_xb, sg_pfn_start + 1, > + page_xb_end, 0); > + sg_addr = pfn_to_kaddr(sg_pfn_start); > + sg_len =...

...@end: the end of the range, exclusive >> + * >> + * Returns: the index of the found bit, or @end + 1 if no such bit is found. >> + */ >> +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, >> + unsigned long end) >> +{ >> + return xb_find_next_bit(xb, start, end, 1); >> +} > Won't "exclusive" loose ability to handle ULONG_MAX ? Since this is a > library module, missing ability to handle ULONG_MAX sounds like an omission. > Shouldn't we pass (or return) whether "found or not" flag (e.g. strtoul() in...

...) Use only one chunk format, instead of two. 2) re-write the virtio-balloon implementation patch. 3) commit changes 4) patch re-org Liang Li (1): virtio-balloon: deflate via a page list Matthew Wilcox (1): Introduce xbitmap Wei Wang (6): virtio-balloon: coding format cleanup xbitmap: add xb_find_next_bit() and xb_zero() virtio-balloon: VIRTIO_BALLOON_F_SG mm: support reporting free page blocks mm: export symbol of next_zone and first_online_pgdat virtio-balloon: VIRTIO_BALLOON_F_CMD_VQ drivers/virtio/virtio_balloon.c | 414 ++++++++++++++++++++++++++++++++---- drivers/virtio/virtio_ri...

...) Use only one chunk format, instead of two. 2) re-write the virtio-balloon implementation patch. 3) commit changes 4) patch re-org Liang Li (1): virtio-balloon: deflate via a page list Matthew Wilcox (1): Introduce xbitmap Wei Wang (6): virtio-balloon: coding format cleanup xbitmap: add xb_find_next_bit() and xb_zero() virtio-balloon: VIRTIO_BALLOON_F_SG mm: support reporting free page blocks mm: export symbol of next_zone and first_online_pgdat virtio-balloon: VIRTIO_BALLOON_F_CMD_VQ drivers/virtio/virtio_balloon.c | 414 ++++++++++++++++++++++++++++++++---- drivers/virtio/virtio_ri...