search for: find_next_zero_bit

...if (radix_tree_exception(bmap)) { > + unsigned long tmp = (unsigned long)bmap; > + unsigned long ebit = bit + 2; > + > + if (ebit >= BITS_PER_LONG) > + continue; > + if (set) > + ret = find_next_bit(&tmp, BITS_PER_LONG, ebit); > + else > + ret = find_next_zero_bit(&tmp, BITS_PER_LONG, > + ebit); > + if (ret < BITS_PER_LONG) > + return ret - 2 + IDA_BITMAP_BITS * index; > > What I'm saying is that find_next_zero_bit() will not be called if you do > "if (ebit >= BITS_PER_LONG) continue;" before calling find...

...ally. Please let me know if anywhere still looks fuzzy. > >> if (set) >> ret = find_next_bit(&tmp, >> BITS_PER_LONG, ebit); >> else >> ret = find_next_zero_bit(&tmp, >> BITS_PER_LONG, >> ebit); >> if (ret < BITS_PER_LONG) >> return ret - 2 + ida_start; >> } else if (bitmap) { >>...

...= bit + 2; if (ebit >= BITS_PER_LONG) continue; if (set) ret = find_next_bit(&tmp, BITS_PER_LONG, ebit); else ret = find_next_zero_bit(&tmp, BITS_PER_LONG, ebit); if (ret < BITS_PER_LONG) return ret - 2 + ida_start; } else if (bitmap) { if (set)...

...from using git checkout to change to a new branch; the change needed to checkout 208 files out of about 1600 total files. du(1) reports that the checkout is about 14 megs; the alternates for that tree have about 60 megs of git packs. As you can see btrfs_find_space_cluster(), find_next_bit() and find_next_zero_bit() use most of the sys cpu. That patterns seems to hold whenever I run perf top during such operations. Box is x86_32, pentium3m. -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6

This patch series enhances the existing virtio-balloon with the following new features: 1) fast ballooning: transfer ballooned pages between the guest and host in chunks using sgs, instead of one array each time; and 2) free page block reporting: a new virtqueue to report guest free pages to the host. The second feature can be used to accelerate live migration of VMs. Here are some details: Live

This patch series enhances the existing virtio-balloon with the following new features: 1) fast ballooning: transfer ballooned pages between the guest and host in chunks using sgs, instead of one array each time; and 2) free page block reporting: a new virtqueue to report guest free pages to the host. The second feature can be used to accelerate live migration of VMs. Here are some details: Live

...it, gfp_t gfp); bool xb_test_bit(const struct xb *xb, unsigned long bit); -int xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_clear_bit(struct xb *xb, unsigned long bit); +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, + unsigned long end); +unsigned long xb_find_next_zero_bit(struct xb *xb, unsigned long start, + unsigned long end); +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end); static inline bool xb_empty(const struct xb *xb) { diff --git a/lib/xbitmap.c b/lib/xbitmap.c index 182aa29..10df879 100644 --- a/lib/xbitmap.c +++ b...

...lookup(root, index, &node, &slot); + if (radix_tree_exception(bmap)) { + unsigned long tmp = (unsigned long)bmap; + unsigned long ebit = bit + 2; + + if (ebit >= BITS_PER_LONG) + continue; + if (set) + ret = find_next_bit(&tmp, BITS_PER_LONG, ebit); + else + ret = find_next_zero_bit(&tmp, BITS_PER_LONG, + ebit); + if (ret < BITS_PER_LONG) + return ret - 2 + IDA_BITMAP_BITS * index; + } else if (bmap) { + if (set) + ret = find_next_bit(bmap->bitmap, + IDA_BITMAP_BITS, bit); + else + ret = find_next_zero_bit(bmap->bitmap, + IDA...

...ional path; > > - remove xb_preload_and_set(); > > - reimplement xb_clear_bit_range to make its usage close to > > bitmap_clear; > > - rename xb_find_next_set_bit to xb_find_set, and re-implement it > > in a style close to find_next_bit; > > - rename xb_find_next_zero_bit to xb_find_clear, and re-implement > > it in a stytle close to find_next_zero_bit; > > - separate the implementation of xb_find_set and xb_find_clear for > > the convenience of future updates. > > Removing exceptional path made this patch easier to read. > But wha...

...ional path; > > - remove xb_preload_and_set(); > > - reimplement xb_clear_bit_range to make its usage close to > > bitmap_clear; > > - rename xb_find_next_set_bit to xb_find_set, and re-implement it > > in a style close to find_next_bit; > > - rename xb_find_next_zero_bit to xb_find_clear, and re-implement > > it in a stytle close to find_next_zero_bit; > > - separate the implementation of xb_find_set and xb_find_clear for > > the convenience of future updates. > > Removing exceptional path made this patch easier to read. > But wha...

...exceptional path; >> - remove xb_preload_and_set(); >> - reimplement xb_clear_bit_range to make its usage close to >> bitmap_clear; >> - rename xb_find_next_set_bit to xb_find_set, and re-implement it >> in a style close to find_next_bit; >> - rename xb_find_next_zero_bit to xb_find_clear, and re-implement >> it in a stytle close to find_next_zero_bit; >> - separate the implementation of xb_find_set and xb_find_clear for >> the convenience of future updates. > Removing exceptional path made this patch easier to read. > But what I meant...

...exceptional path; >> - remove xb_preload_and_set(); >> - reimplement xb_clear_bit_range to make its usage close to >> bitmap_clear; >> - rename xb_find_next_set_bit to xb_find_set, and re-implement it >> in a style close to find_next_bit; >> - rename xb_find_next_zero_bit to xb_find_clear, and re-implement >> it in a stytle close to find_next_zero_bit; >> - separate the implementation of xb_find_set and xb_find_clear for >> the convenience of future updates. > Removing exceptional path made this patch easier to read. > But what I meant...

...e eXtensible Bitmap is a sparse bitmap representation which is efficient for set bits which tend to cluster. It supports up to 'unsigned long' worth of bits, and this commit adds the bare bones -- xb_set_bit(), xb_clear_bit(), xb_clear_bit_range(), xb_test_bit(), xb_find_next_set_bit(), xb_find_next_zero_bit(). More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) add Tags to help searching. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox...

I''m using btrfs on two devices here, /usr on sda3 and /home on sdb (dm-crypt device on the whole disk). With btrfs-master the whole system hangs when accessing /home. The system hangs when I''m logging in into my account with KDE and is easily reproducible with dbench. On /usr the hangs appeared also but not as often as on the /home-device. I''ve tested on a third

...; size) { >> + next_one = find_next_bit(bmap, size, pos); >> + /* >> + * No "1" bit found, which means that there is no pfn >> + * recorded in the rest of this bmap. >> + */ >> + if (next_one == size) >> + break; >> + next_zero = find_next_zero_bit(bmap, size, next_one + 1); >> + /* >> + * A bit in page_bmap corresponds to a page of PAGE_SIZE. >> + * Convert it to be pages of 4KB balloon page size when >> + * adding it to a chunk. > This looks wrong. add_one_chunk assumes size in bytes. So should be just >...

...3029] Jun 19 14:22:45 posta2 kernel: [885017.413032] Pid: 11955, comm: dovecot-lda Tainted: G E 3.0.101-0.46-default #1 IBM BladeCenter HS22 -[7870H5G]-/68Y813 8 Jun 19 14:22:45 posta2 kernel: [885017.413037] RIP: 0010:[<ffffffff81257b07>] [<ffffffff81257b07>] find_next_zero_bit+0x67/0xc0 Jun 19 14:22:45 posta2 kernel: [885017.413046] RSP: 0018:ffff88006cc855f0 EFLAGS: 00000287 Jun 19 14:22:45 posta2 kernel: [885017.413049] RAX: 0000000000006f30 RBX: ffffffff8118b348 RCX: 0000000000000010 Jun 19 14:22:45 posta2 kernel: [885017.413051] RDX: 0001000000000000 RSI...

...ze; > + > + while (pos < size) { > + next_one = find_next_bit(bmap, size, pos); > + /* > + * No "1" bit found, which means that there is no pfn > + * recorded in the rest of this bmap. > + */ > + if (next_one == size) > + break; > + next_zero = find_next_zero_bit(bmap, size, next_one + 1); > + /* > + * A bit in page_bmap corresponds to a page of PAGE_SIZE. > + * Convert it to be pages of 4KB balloon page size when > + * adding it to a chunk. This looks wrong. add_one_chunk assumes size in bytes. So should be just PAGE_SIZE. > + */...

...ze; > + > + while (pos < size) { > + next_one = find_next_bit(bmap, size, pos); > + /* > + * No "1" bit found, which means that there is no pfn > + * recorded in the rest of this bmap. > + */ > + if (next_one == size) > + break; > + next_zero = find_next_zero_bit(bmap, size, next_one + 1); > + /* > + * A bit in page_bmap corresponds to a page of PAGE_SIZE. > + * Convert it to be pages of 4KB balloon page size when > + * adding it to a chunk. This looks wrong. add_one_chunk assumes size in bytes. So should be just PAGE_SIZE. > + */...

...bmap, > + unsigned long len) > +{ > + unsigned long pos = 0, end = len * BITS_PER_BYTE; > + > + while (pos < end) { > + unsigned long one = find_next_bit(bmap, end, pos); > + > + if (one < end) { > + unsigned long chunk_size, zero; > + > + zero = find_next_zero_bit(bmap, end, one + 1); zero and one are unhelpful names unless they equal 0 and 1. current/next? > + if (zero >= end) > + chunk_size = end - one; > + else > + chunk_size = zero - one; > + > + if (chunk_size) > + add_one_chunk(vb, vq, PAGE_CHUNK_TYPE_BALLOON,...

...bmap, > + unsigned long len) > +{ > + unsigned long pos = 0, end = len * BITS_PER_BYTE; > + > + while (pos < end) { > + unsigned long one = find_next_bit(bmap, end, pos); > + > + if (one < end) { > + unsigned long chunk_size, zero; > + > + zero = find_next_zero_bit(bmap, end, one + 1); zero and one are unhelpful names unless they equal 0 and 1. current/next? > + if (zero >= end) > + chunk_size = end - one; > + else > + chunk_size = zero - one; > + > + if (chunk_size) > + add_one_chunk(vb, vq, PAGE_CHUNK_TYPE_BALLOON,...