[PATCH] vmalloc: Convert to XArray

[PATCH] vmalloc: Convert to XArray

[Matthew Wilcox]

From: "Matthew Wilcox (Oracle)" <willy@infradead.org>

The radix tree of vmap blocks is simpler to express as an XArray.
Reduces both the text and data sizes of the object file and eliminates
a user of the radix tree preload API.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
 mm/vmalloc.c | 40 +++++++++++-----------------------------
 1 file changed, 11 insertions(+), 29 deletions(-)

diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index 1e94497b7388..375bbb410a94 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -25,7 +25,7 @@
 #include <linux/list.h>
 #include <linux/notifier.h>
 #include <linux/rbtree.h>
-#include <linux/radix-tree.h>
+#include <linux/xarray.h>
 #include <linux/rcupdate.h>
 #include <linux/pfn.h>
 #include <linux/kmemleak.h>
@@ -1513,12 +1513,11 @@ struct vmap_block {
 static DEFINE_PER_CPU(struct vmap_block_queue, vmap_block_queue);
 
 /*
- * Radix tree of vmap blocks, indexed by address, to quickly find a vmap block
+ * XArray of vmap blocks, indexed by address, to quickly find a vmap block
  * in the free path. Could get rid of this if we change the API to return a
  * "cookie" from alloc, to be passed to free. But no big deal yet.
  */
-static DEFINE_SPINLOCK(vmap_block_tree_lock);
-static RADIX_TREE(vmap_block_tree, GFP_ATOMIC);
+static DEFINE_XARRAY(vmap_blocks);
 
 /*
  * We should probably have a fallback mechanism to allocate virtual memory
@@ -1575,13 +1574,6 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
 		return ERR_CAST(va);
 	}
 
-	err = radix_tree_preload(gfp_mask);
-	if (unlikely(err)) {
-		kfree(vb);
-		free_vmap_area(va);
-		return ERR_PTR(err);
-	}
-
 	vaddr = vmap_block_vaddr(va->va_start, 0);
 	spin_lock_init(&vb->lock);
 	vb->va = va;
@@ -1594,11 +1586,12 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
 	INIT_LIST_HEAD(&vb->free_list);
 
 	vb_idx = addr_to_vb_idx(va->va_start);
-	spin_lock(&vmap_block_tree_lock);
-	err = radix_tree_insert(&vmap_block_tree, vb_idx, vb);
-	spin_unlock(&vmap_block_tree_lock);
-	BUG_ON(err);
-	radix_tree_preload_end();
+	err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
+	if (err) {
+		kfree(vb);
+		free_vmap_area(va);
+		return ERR_PTR(err);
+	}
 
 	vbq = &get_cpu_var(vmap_block_queue);
 	spin_lock(&vbq->lock);
@@ -1612,12 +1605,8 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
 static void free_vmap_block(struct vmap_block *vb)
 {
 	struct vmap_block *tmp;
-	unsigned long vb_idx;
 
-	vb_idx = addr_to_vb_idx(vb->va->va_start);
-	spin_lock(&vmap_block_tree_lock);
-	tmp = radix_tree_delete(&vmap_block_tree, vb_idx);
-	spin_unlock(&vmap_block_tree_lock);
+	tmp = xa_erase(&vmap_blocks, addr_to_vb_idx(vb->va->va_start));
 	BUG_ON(tmp != vb);
 
 	free_vmap_area_noflush(vb->va);
@@ -1723,7 +1712,6 @@ static void *vb_alloc(unsigned long size, gfp_t gfp_mask)
 static void vb_free(unsigned long addr, unsigned long size)
 {
 	unsigned long offset;
-	unsigned long vb_idx;
 	unsigned int order;
 	struct vmap_block *vb;
 
@@ -1733,14 +1721,8 @@ static void vb_free(unsigned long addr, unsigned long size)
 	flush_cache_vunmap(addr, addr + size);
 
 	order = get_order(size);
-
 	offset = (addr & (VMAP_BLOCK_SIZE - 1)) >> PAGE_SHIFT;
-
-	vb_idx = addr_to_vb_idx(addr);
-	rcu_read_lock();
-	vb = radix_tree_lookup(&vmap_block_tree, vb_idx);
-	rcu_read_unlock();
-	BUG_ON(!vb);
+	vb = xa_load(&vmap_blocks, addr_to_vb_idx(addr));
 
 	unmap_kernel_range_noflush(addr, size);
 
-- 
2.26.2

Re: [PATCH] vmalloc: Convert to XArray

[William Kucharski]

> On Jun 3, 2020, at 11:14 AM, Matthew Wilcox <willy@infradead.org> wrote:
> 

[ ... snip ... ]

> -	err = radix_tree_preload(gfp_mask);
> -	if (unlikely(err)) {
> -		kfree(vb);
> -		free_vmap_area(va);
> -		return ERR_PTR(err);
> -	}
> -
> 	vaddr = vmap_block_vaddr(va->va_start, 0);
> 	spin_lock_init(&vb->lock);
> 	vb->va = va;
> @@ -1594,11 +1586,12 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
> 	INIT_LIST_HEAD(&vb->free_list);
> 
> 	vb_idx = addr_to_vb_idx(va->va_start);
> -	spin_lock(&vmap_block_tree_lock);
> -	err = radix_tree_insert(&vmap_block_tree, vb_idx, vb);
> -	spin_unlock(&vmap_block_tree_lock);
> -	BUG_ON(err);
> -	radix_tree_preload_end();
> +	err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
> +	if (err) {
> +		kfree(vb);
> +		free_vmap_area(va);
> +		return ERR_PTR(err);
> +	}
> 

Should the "(err)" here be "unlikely(err)" as the radix tree version was?

Nice change and simplifies the code quite a bit.

Reviewed-by: William Kucharski <william.kucharski@oracle.com>

Re: [PATCH] vmalloc: Convert to XArray

[Matthew Wilcox]

On Wed, Jun 03, 2020 at 11:35:24AM -0600, William Kucharski wrote:
> > -	err = radix_tree_preload(gfp_mask);
> > -	if (unlikely(err)) {
> > +	err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
> > +	if (err) {
> 
> Should the "(err)" here be "unlikely(err)" as the radix tree version was?

That's a good question.  In previous years, GCC used to be stupider and
we had to help it out by annotating which paths were more or less likely
to be taken.  Now it generally makes the right decision (eg understanding
that an "early exit" which unwinds state from a function is likely to
be an error case and thus the slow path), so we no longer need to mark
nearly as much code with unlikely() as we used to.  Similar things are
true for prefetch() calls.

I took a look at the disassembly of this code with and without the
unlikely() and I also compared if (err) with if (err < 0).  In the end,
it makes no difference to the control flow (all variants jump to the end
of the function) although it changes the register allocation decisions
a little (!)

What did make a difference was moving all the error handling to the
end of the function; reduced the size of the function by 48 bytes.
This is with gcc-9.3.  I can submit this patch as a follow-up since it's
basically unrelated to the other change.

diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index 375bbb410a94..3d5b5c32c840 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -1569,10 +1569,8 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
 	va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE,
 					VMALLOC_START, VMALLOC_END,
 					node, gfp_mask);
-	if (IS_ERR(va)) {
-		kfree(vb);
-		return ERR_CAST(va);
-	}
+	if (IS_ERR(va))
+		goto free_vb;
 
 	vaddr = vmap_block_vaddr(va->va_start, 0);
 	spin_lock_init(&vb->lock);
@@ -1587,11 +1585,8 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
 
 	vb_idx = addr_to_vb_idx(va->va_start);
 	err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
-	if (err) {
-		kfree(vb);
-		free_vmap_area(va);
-		return ERR_PTR(err);
-	}
+	if (err < 0)
+		goto free_va;
 
 	vbq = &get_cpu_var(vmap_block_queue);
 	spin_lock(&vbq->lock);
@@ -1600,6 +1595,13 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
 	put_cpu_var(vmap_block_queue);
 
 	return vaddr;
+
+free_va:
+	free_vmap_area(va);
+	va = ERR_PTR(err);
+free_vb:
+	kfree(vb);
+	return ERR_CAST(va);
 }
 
 static void free_vmap_block(struct vmap_block *vb)

> Nice change and simplifies the code quite a bit.
> 
> Reviewed-by: William Kucharski <william.kucharski@oracle.com>

Re: [PATCH] vmalloc: Convert to XArray

[William Kucharski]

Again, nice - for the followup:

Reviewed-by: William Kucharski <william.kucharski@oracle.com>

> On Jun 3, 2020, at 9:33 PM, Matthew Wilcox <willy@infradead.org> wrote:
> 
> On Wed, Jun 03, 2020 at 11:35:24AM -0600, William Kucharski wrote:
>>> -	err = radix_tree_preload(gfp_mask);
>>> -	if (unlikely(err)) {
>>> +	err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
>>> +	if (err) {
>> 
>> Should the "(err)" here be "unlikely(err)" as the radix tree version was?
> 
> That's a good question.  In previous years, GCC used to be stupider and
> we had to help it out by annotating which paths were more or less likely
> to be taken.  Now it generally makes the right decision (eg understanding
> that an "early exit" which unwinds state from a function is likely to
> be an error case and thus the slow path), so we no longer need to mark
> nearly as much code with unlikely() as we used to.  Similar things are
> true for prefetch() calls.
> 
> I took a look at the disassembly of this code with and without the
> unlikely() and I also compared if (err) with if (err < 0).  In the end,
> it makes no difference to the control flow (all variants jump to the end
> of the function) although it changes the register allocation decisions
> a little (!)
> 
> What did make a difference was moving all the error handling to the
> end of the function; reduced the size of the function by 48 bytes.
> This is with gcc-9.3.  I can submit this patch as a follow-up since it's
> basically unrelated to the other change.
> 
> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index 375bbb410a94..3d5b5c32c840 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -1569,10 +1569,8 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
> 	va = alloc_vmap_area(VMAP_BLOCK_SIZE, VMAP_BLOCK_SIZE,
> 					VMALLOC_START, VMALLOC_END,
> 					node, gfp_mask);
> -	if (IS_ERR(va)) {
> -		kfree(vb);
> -		return ERR_CAST(va);
> -	}
> +	if (IS_ERR(va))
> +		goto free_vb;
> 
> 	vaddr = vmap_block_vaddr(va->va_start, 0);
> 	spin_lock_init(&vb->lock);
> @@ -1587,11 +1585,8 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
> 
> 	vb_idx = addr_to_vb_idx(va->va_start);
> 	err = xa_insert(&vmap_blocks, vb_idx, vb, gfp_mask);
> -	if (err) {
> -		kfree(vb);
> -		free_vmap_area(va);
> -		return ERR_PTR(err);
> -	}
> +	if (err < 0)
> +		goto free_va;
> 
> 	vbq = &get_cpu_var(vmap_block_queue);
> 	spin_lock(&vbq->lock);
> @@ -1600,6 +1595,13 @@ static void *new_vmap_block(unsigned int order, gfp_t gfp_mask)
> 	put_cpu_var(vmap_block_queue);
> 
> 	return vaddr;
> +
> +free_va:
> +	free_vmap_area(va);
> +	va = ERR_PTR(err);
> +free_vb:
> +	kfree(vb);
> +	return ERR_CAST(va);
> }
> 
> static void free_vmap_block(struct vmap_block *vb)
> 
>> Nice change and simplifies the code quite a bit.
>> 
>> Reviewed-by: William Kucharski <william.kucharski@oracle.com>
>