Displaying 20 results from an estimated 34 matches for "radix_tree_except".
2017 Nov 03
1
[PATCH v17 1/6] lib/xbitmap: Introduce xbitmap
...**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)
Ple...
2017 Nov 03
1
[PATCH v17 1/6] lib/xbitmap: Introduce xbitmap
...**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)
Ple...
2017 Nov 03
0
[PATCH v17 2/6] radix tree test suite: add tests for xbitmap
...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(*...
2017 Nov 03
0
[PATCH v17 1/6] lib/xbitmap: Introduce xbitmap
...);
}
-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,...
2017 Aug 03
0
[PATCH v13 1/5] Introduce xbitmap
...);
}
-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), gf...
2017 Sep 11
1
[PATCH v15 1/5] lib/xbitmap: Introduce xbitmap
...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;...
2017 Sep 11
1
[PATCH v15 1/5] lib/xbitmap: Introduce xbitmap
...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;...
2017 Dec 13
0
[PATCH v19 3/7] xbitmap: add more operations
...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;" w...
2017 Dec 14
0
[PATCH v19 3/7] xbitmap: add more operations
...(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)
>>...
2017 Sep 11
1
[PATCH v15 2/5] lib/xbitmap: add xb_find_next_bit() and xb_zero()
...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 ...;...
2017 Sep 11
1
[PATCH v15 2/5] lib/xbitmap: add xb_find_next_bit() and xb_zero()
...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 ...;...
2017 Dec 12
0
[PATCH v19 1/7] xbitmap: Introduce xbitmap
...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(*...
2017 Aug 09
1
[PATCH v13 1/5] Introduce xbitmap
...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 cod...
2017 Aug 09
1
[PATCH v13 1/5] Introduce xbitmap
...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 cod...
2017 Nov 03
12
[PATCH v17 0/6] Virtio-balloon Enhancement
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
2017 Nov 03
12
[PATCH v17 0/6] Virtio-balloon Enhancement
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
2017 Dec 12
21
[PATCH v19 0/7] Virtio-balloon Enhancement
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
2017 Dec 12
21
[PATCH v19 0/7] Virtio-balloon Enhancement
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
2017 Dec 12
0
[PATCH v19 3/7] xbitmap: add more operations
...+ 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)
+ __ra...
2017 Nov 30
0
[PATCH v18 05/10] xbitmap: add more operations
...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 t...