search for: radix_tree_exception

...**slot; > + struct ida_bitmap *bitmap; > + unsigned long ebit; > + > + bit %= IDA_BITMAP_BITS; > + ebit = bit + 2; > + > + err = __radix_tree_create(root, index, 0, &node, &slot); > + if (err) > + return err; > + bitmap = rcu_dereference_raw(*slot); > + if (radix_tree_exception(bitmap)) { > + unsigned long tmp = (unsigned long)bitmap; > + > + if (ebit < BITS_PER_LONG) { > + tmp |= 1UL << ebit; > + rcu_assign_pointer(*slot, (void *)tmp); > + return 0; > + } > + bitmap = this_cpu_xchg(ida_bitmap, NULL); > + if (!bitmap) Please...

...**slot; > + struct ida_bitmap *bitmap; > + unsigned long ebit; > + > + bit %= IDA_BITMAP_BITS; > + ebit = bit + 2; > + > + err = __radix_tree_create(root, index, 0, &node, &slot); > + if (err) > + return err; > + bitmap = rcu_dereference_raw(*slot); > + if (radix_tree_exception(bitmap)) { > + unsigned long tmp = (unsigned long)bitmap; > + > + if (ebit < BITS_PER_LONG) { > + tmp |= 1UL << ebit; > + rcu_assign_pointer(*slot, (void *)tmp); > + return 0; > + } > + bitmap = this_cpu_xchg(ida_bitmap, NULL); > + if (!bitmap) Please...

...mp;xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned long ebit; + + bit %= IDA_BITMAP_BITS; + ebit = bit + 2; + + err = __radix_tree_create(root, index, 0, &node, &slot); + if (err) + return err; + bitmap = rcu_dereference_raw(*slot); + if (radix_tree_exception(bitmap)) { + unsigned long tmp = (unsigned long)bitmap; + + if (ebit < BITS_PER_LONG) { + tmp |= 1UL << ebit; + rcu_assign_pointer(*slot, (void *)tmp); + return 0; + } + bitmap = this_cpu_xchg(ida_bitmap, NULL); + if (!bitmap) + return -EAGAIN; + memset(bitmap, 0, sizeof(*bit...

...); } -static bool __radix_tree_delete(struct radix_tree_root *root, - struct radix_tree_node *node, void __rcu **slot) +bool __radix_tree_delete(struct radix_tree_root *root, + struct radix_tree_node *node, void __rcu **slot) { void *old = rcu_dereference_raw(*slot); int exceptional = radix_tree_exceptional_entry(old) ? -1 : 0; @@ -2005,6 +2020,38 @@ static bool __radix_tree_delete(struct radix_tree_root *root, } /** + * xb_preload - preload for xb_set_bit() + * @gfp_mask: allocation mask to use for preloading + * + * Preallocate memory to use for the next call to xb_set_bit(). On success, + *...

...); } -static bool __radix_tree_delete(struct radix_tree_root *root, - struct radix_tree_node *node, void __rcu **slot) +bool __radix_tree_delete(struct radix_tree_root *root, + struct radix_tree_node *node, void __rcu **slot) { void *old = rcu_dereference_raw(*slot); int exceptional = radix_tree_exceptional_entry(old) ? -1 : 0; @@ -2137,6 +2148,130 @@ int ida_pre_get(struct ida *ida, gfp_t gfp) } EXPORT_SYMBOL(ida_pre_get); +void xb_preload(gfp_t gfp) +{ + __radix_tree_preload(gfp, XB_PRELOAD_SIZE); + if (!this_cpu_read(ida_bitmap)) { + struct ida_bitmap *bitmap = kmalloc(sizeof(*bitmap), gfp);...

...t ret = 0; > + unsigned long index = bit / IDA_BITMAP_BITS; > + struct radix_tree_root *root = &xb->xbrt; > + struct radix_tree_node *node; > + void **slot; > + struct ida_bitmap *bitmap; > + unsigned long ebit, tmp; > + > + bit %= IDA_BITMAP_BITS; > + ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT; > + > + switch (ops) { > + case XB_SET: > + ret = __radix_tree_create(root, index, 0, &node, &slot); > + if (ret) > + return ret; > + bitmap = rcu_dereference_raw(*slot); > + if (radix_tree_exception(bitmap)) { > + tmp = (unsigned long)bitmap; &gt...

...t ret = 0; > + unsigned long index = bit / IDA_BITMAP_BITS; > + struct radix_tree_root *root = &xb->xbrt; > + struct radix_tree_node *node; > + void **slot; > + struct ida_bitmap *bitmap; > + unsigned long ebit, tmp; > + > + bit %= IDA_BITMAP_BITS; > + ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT; > + > + switch (ops) { > + case XB_SET: > + ret = __radix_tree_create(root, index, 0, &node, &slot); > + if (ret) > + return ret; > + bitmap = rcu_dereference_raw(*slot); > + if (radix_tree_exception(bitmap)) { > + tmp = (unsigned long)bitmap; &gt...

...gt;> + 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, &node, &slot); >> + 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); >> + >> + if (ebit >= BITS_PER_LONG) > What happens if we hit this "continue;" when...

...(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, &node, &slot); >>>> + 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); >>>> + >>>> + if (ebit >= BITS_PER_LONG) >>&gt...

...for (; end < start; 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, &node, &slot); if (radix_tree_exception(bitmap)) { unsigned long ebit = bit + 2; unsigned long tmp = (unsigned long)bitmap; if (ebit >= BITS_PER_LONG) continue; tmp &= ... something ...;...

...for (; end < start; 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, &node, &slot); if (radix_tree_exception(bitmap)) { unsigned long ebit = bit + 2; unsigned long tmp = (unsigned long)bitmap; if (ebit >= BITS_PER_LONG) continue; tmp &= ... something ...;...

...mp;xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned long ebit; + + bit %= IDA_BITMAP_BITS; + ebit = bit + 2; + + err = __radix_tree_create(root, index, 0, &node, &slot); + if (err) + return err; + bitmap = rcu_dereference_raw(*slot); + if (radix_tree_exception(bitmap)) { + unsigned long tmp = (unsigned long)bitmap; + + if (ebit < BITS_PER_LONG) { + tmp |= 1UL << ebit; + rcu_assign_pointer(*slot, (void *)tmp); + return 0; + } + bitmap = this_cpu_xchg(ida_bitmap, NULL); + if (!bitmap) + return -EAGAIN; + memset(bitmap, 0, sizeof(*bit...

...ed long bit) > +{ > + unsigned long index = bit / IDA_BITMAP_BITS; > + const struct radix_tree_root *root = &xb->xbrt; > + struct ida_bitmap *bitmap = radix_tree_lookup(root, index); > + > + bit %= IDA_BITMAP_BITS; > + > + if (!bitmap) > + return 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); > +} > + Missing EXPORT_SYMBOL? Perhaps all this code s...

...ed long bit) > +{ > + unsigned long index = bit / IDA_BITMAP_BITS; > + const struct radix_tree_root *root = &xb->xbrt; > + struct ida_bitmap *bitmap = radix_tree_lookup(root, index); > + > + bit %= IDA_BITMAP_BITS; > + > + if (!bitmap) > + return 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); > +} > + Missing EXPORT_SYMBOL? Perhaps all this code s...

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

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

...+ 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, &node, &slot); + 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); + + if (ebit >= BITS_PER_LONG) + continue; + bitmap_clear(&tmp, ebit, nbits); + if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY) + __radix...

...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...