Displaying 20 results from an estimated 65 matches for "ida_bitmap".
2017 Nov 03
1
[PATCH v17 1/6] lib/xbitmap: Introduce xbitmap
...ck annotation, for __radix_tree_preload() is marked
with __must_check annotation. By error failing to check result of
xb_preload() will lead to preemption kept disabled unexpectedly.
> +int xb_set_bit(struct xb *xb, unsigned long bit)
> +{
> + int err;
> + 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;
> +
> + bit %= IDA_BITMAP_BITS;
> + ebit = bit + 2;
> +
> + err = __radix_tree_create(root, index, 0, &a...
2017 Nov 03
1
[PATCH v17 1/6] lib/xbitmap: Introduce xbitmap
...ck annotation, for __radix_tree_preload() is marked
with __must_check annotation. By error failing to check result of
xb_preload() will lead to preemption kept disabled unexpectedly.
> +int xb_set_bit(struct xb *xb, unsigned long bit)
> +{
> + int err;
> + 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;
> +
> + bit %= IDA_BITMAP_BITS;
> + ebit = bit + 2;
> +
> + err = __radix_tree_create(root, index, 0, &a...
2017 Aug 03
0
[PATCH v13 1/5] Introduce xbitmap
...* Number of nodes in fully populated tree of given height */
@@ -78,6 +79,14 @@ static struct kmem_cache *radix_tree_node_cachep;
#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
/*
+ * The XB can go up to unsigned long, but also uses a bitmap.
+ */
+#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
+#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
+#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
+
+/*
* Per-cpu pool of preloaded nodes
*/
struct radix_tree_preload {
@@ -840,6 +849,8 @@ int __radix_tree_create(struct radix_tree_root *root, unsign...
2017 Aug 09
1
[PATCH v13 1/5] Introduce xbitmap
...6 +79,14 @@ static struct kmem_cache *radix_tree_node_cachep;
> #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
>
> /*
> + * The XB can go up to unsigned long, but also uses a bitmap.
This comment is hard to understand.
> + */
> +#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
> +#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
> + RADIX_TREE_MAP_SHIFT))
> +#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
> +
>
> ...
>
> +void xb_preload(gfp_t gfp)
> +{
> + __radix_tree_preload(gfp, XB_PRELOAD_SIZE);
> + if (!this_cpu_...
2017 Aug 09
1
[PATCH v13 1/5] Introduce xbitmap
...6 +79,14 @@ static struct kmem_cache *radix_tree_node_cachep;
> #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
>
> /*
> + * The XB can go up to unsigned long, but also uses a bitmap.
This comment is hard to understand.
> + */
> +#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
> +#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
> + RADIX_TREE_MAP_SHIFT))
> +#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
> +
>
> ...
>
> +void xb_preload(gfp_t gfp)
> +{
> + __radix_tree_preload(gfp, XB_PRELOAD_SIZE);
> + if (!this_cpu_...
2017 Oct 11
0
[PATCH v16 3/5] virtio-balloon: VIRTIO_BALLOON_F_SG
...xb_set_page() calls xb_preload(GFP_KERNEL) which might sleep with
>>> preemption disabled.
>> Yes, I think that should not be expected, thanks.
>>
>> I plan to change it like this:
>>
>> bool xb_preload(gfp_t gfp)
>> {
>> if (!this_cpu_read(ida_bitmap)) {
>> struct ida_bitmap *bitmap = kmalloc(sizeof(*bitmap), gfp);
>>
>> if (!bitmap)
>> return false;
>> bitmap = this_cpu_cmpxchg(ida_bitmap, NULL, bitmap);
>> kfree(bitmap);...
2017 Dec 17
2
[PATCH v19 3/7] xbitmap: add more operations
On Sun, Dec 17, 2017 at 01:47:21PM +0000, Wang, Wei W wrote:
> On Saturday, December 16, 2017 3:22 AM, Matthew Wilcox wrote:
> > On Fri, Dec 15, 2017 at 10:49:15AM -0800, Matthew Wilcox wrote:
> > > Here's the API I'm looking at right now. The user need take no lock;
> > > the locking (spinlock) is handled internally to the implementation.
>
> Another
2017 Dec 17
2
[PATCH v19 3/7] xbitmap: add more operations
On Sun, Dec 17, 2017 at 01:47:21PM +0000, Wang, Wei W wrote:
> On Saturday, December 16, 2017 3:22 AM, Matthew Wilcox wrote:
> > On Fri, Dec 15, 2017 at 10:49:15AM -0800, Matthew Wilcox wrote:
> > > Here's the API I'm looking at right now. The user need take no lock;
> > > the locking (spinlock) is handled internally to the implementation.
>
> Another
2017 Nov 03
0
[PATCH v17 1/6] lib/xbitmap: Introduce xbitmap
...tmap implementation supports up to ULONG_MAX bits, and it is
+ * implemented based on ida bitmaps. So, given an unsigned long index,
+ * the high order XB_INDEX_BITS bits of the index is used to find the
+ * corresponding item (i.e. ida bitmap) from the radix tree, and the low
+ * order (i.e. ilog2(IDA_BITMAP_BITS)) bits of the index are indexed into
+ * the ida bitmap to find the bit.
+ */
+#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
+#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
+#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
+
+/*
* Per-c...
2017 Dec 12
0
[PATCH v19 2/7] xbitmap: potential improvement
...x-tree.c
+++ b/lib/radix-tree.c
@@ -77,9 +77,6 @@ static struct kmem_cache *radix_tree_node_cachep;
RADIX_TREE_MAP_SHIFT))
#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
-/*
- * The XB can go up to unsigned long, but also uses a bitmap.
- */
#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
RADIX_TREE_MAP_SHIFT))
@@ -2145,17 +2142,35 @@ int ida_pre_get(struct ida *ida, gfp_t gfp)
}
EXPORT_SYMBOL(ida_pre_get);
-void xb_preload(gfp_t gfp)
+/**
+ * xb_preload - preload for xb_set_bit()
+ * @gfp_mask: allocation mask...
2017 Dec 12
0
[PATCH v19 1/7] xbitmap: Introduce xbitmap
...7000ad6 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -78,6 +78,14 @@ static struct kmem_cache *radix_tree_node_cachep;
#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
/*
+ * The XB can go up to unsigned long, but also uses a bitmap.
+ */
+#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
+#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
+#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
+
+/*
* Per-cpu pool of preloaded nodes
*/
struct radix_tree_preload {
@@ -839,6 +847,8 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned lo...
2017 Oct 09
4
[PATCH v16 3/5] virtio-balloon: VIRTIO_BALLOON_F_SG
On Sat, Sep 30, 2017 at 12:05:52PM +0800, Wei Wang wrote:
> +static inline void xb_set_page(struct virtio_balloon *vb,
> + struct page *page,
> + unsigned long *pfn_min,
> + unsigned long *pfn_max)
> +{
> + unsigned long pfn = page_to_pfn(page);
> +
> + *pfn_min = min(pfn, *pfn_min);
> + *pfn_max = max(pfn, *pfn_max);
> +
2017 Oct 09
4
[PATCH v16 3/5] virtio-balloon: VIRTIO_BALLOON_F_SG
On Sat, Sep 30, 2017 at 12:05:52PM +0800, Wei Wang wrote:
> +static inline void xb_set_page(struct virtio_balloon *vb,
> + struct page *page,
> + unsigned long *pfn_min,
> + unsigned long *pfn_max)
> +{
> + unsigned long pfn = page_to_pfn(page);
> +
> + *pfn_min = min(pfn, *pfn_min);
> + *pfn_max = max(pfn, *pfn_max);
> +
2017 Dec 19
0
[PATCH v20 1/7] xbitmap: Introduce xbitmap
...ee of given height */
static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly;
@@ -77,6 +77,11 @@ static struct kmem_cache *radix_tree_node_cachep;
RADIX_TREE_MAP_SHIFT))
#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
+#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
+#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
+#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
+
/*
* Per-cpu pool of preloaded nodes
*/
@@ -839,6 +844,8 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
offset, 0,...
2017 Dec 15
2
[PATCH v19 1/7] xbitmap: Introduce xbitmap
...6 /**
7 * xb_set_bit - set a bit in the xbitmap
8 * @xb: the xbitmap tree used to record the bit
9 * @bit: index of the bit to set
10 *
11 * This function is used to set a bit in the xbitmap. If the bitmap that @bit
12 * resides in is not there, the per-cpu ida_bitmap will be taken.
13 *
14 * Returns: 0 on success. %-EAGAIN indicates that @bit was not set.
15 */
16 int xb_set_bit(struct xb *xb, unsigned long bit)
17 {
18 int err;
19 unsigned long index = bit / IDA_BITMAP_BITS;
20 struct radix_tree_root *root = &xb->xb...
2017 Dec 15
2
[PATCH v19 1/7] xbitmap: Introduce xbitmap
...6 /**
7 * xb_set_bit - set a bit in the xbitmap
8 * @xb: the xbitmap tree used to record the bit
9 * @bit: index of the bit to set
10 *
11 * This function is used to set a bit in the xbitmap. If the bitmap that @bit
12 * resides in is not there, the per-cpu ida_bitmap will be taken.
13 *
14 * Returns: 0 on success. %-EAGAIN indicates that @bit was not set.
15 */
16 int xb_set_bit(struct xb *xb, unsigned long bit)
17 {
18 int err;
19 unsigned long index = bit / IDA_BITMAP_BITS;
20 struct radix_tree_root *root = &xb->xb...
2017 Dec 21
7
[PATCH v20 3/7 RESEND] xbitmap: add more operations
...e of bits in the xbitmap. If all the
+ * bits in the bitmap are 0, the bitmap will be freed.
+ */
+void xb_clear_bit_range(struct xb *xb, unsigned long start,
+ unsigned long nbits)
+{
+ struct radix_tree_root *root = &xb->xbrt;
+ struct radix_tree_node *node;
+ void __rcu **slot;
+ struct ida_bitmap *bitmap;
+ unsigned long index = start / IDA_BITMAP_BITS;
+ unsigned long bit = start % IDA_BITMAP_BITS;
+
+ if (nbits > ULONG_MAX - start)
+ nbits = ULONG_MAX - start;
+
+ while (nbits) {
+ unsigned int __nbits = min(nbits,
+ (unsigned long)IDA_BITMAP_BITS - bit);
+
+ bitmap = __radix_tr...
2017 Dec 21
7
[PATCH v20 3/7 RESEND] xbitmap: add more operations
...e of bits in the xbitmap. If all the
+ * bits in the bitmap are 0, the bitmap will be freed.
+ */
+void xb_clear_bit_range(struct xb *xb, unsigned long start,
+ unsigned long nbits)
+{
+ struct radix_tree_root *root = &xb->xbrt;
+ struct radix_tree_node *node;
+ void __rcu **slot;
+ struct ida_bitmap *bitmap;
+ unsigned long index = start / IDA_BITMAP_BITS;
+ unsigned long bit = start % IDA_BITMAP_BITS;
+
+ if (nbits > ULONG_MAX - start)
+ nbits = ULONG_MAX - start;
+
+ while (nbits) {
+ unsigned int __nbits = min(nbits,
+ (unsigned long)IDA_BITMAP_BITS - bit);
+
+ bitmap = __radix_tr...
2017 Dec 21
0
[PATCH v20 3/7 RESEND] xbitmap: add more operations
...ee of given height */
static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly;
@@ -77,6 +77,11 @@ static struct kmem_cache *radix_tree_node_cachep;
RADIX_TREE_MAP_SHIFT))
#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
+#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
+#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
+#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
+
/*
* Per-cpu pool of preloaded nodes
*/
@@ -1781,7 +1786,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
child = rcu_deref...
2018 Jan 09
0
[PATCH v21 1/5] xbitmap: Introduce xbitmap
...ee of given height */
static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly;
@@ -77,6 +77,11 @@ static struct kmem_cache *radix_tree_node_cachep;
RADIX_TREE_MAP_SHIFT))
#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
+#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS))
+#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
+#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1)
+
/*
* Per-cpu pool of preloaded nodes
*/
@@ -1781,7 +1786,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
child = rcu_deref...