[PATCH] vmalloc: Remove alloc_map from vmap_block.

[PATCH] vmalloc: Remove alloc_map from vmap_block.

[Chanho Min]

There is no reason to maintain alloc_map in the vmap_block.
The use of alloc_map may require heavy bitmap operation sometimes.
In the worst-case, We need 1024 for-loops to find 1 free bit and
thus cause overhead. vmap_block is fragmented unnecessarily by
2 order alignment as well.

Instead we can map by using vb->free in order. When It is freed,
Its corresponding bit will be set in the dirty_map and all
free/purge operations are carried out in the dirty_map.
vmap_block is not fragmented sporadically anymore and thus
purge_fragmented_blocks_thiscpu in the vb_alloc can be removed.

Signed-off-by: Chanho Min <chanho.min@lge.com>
Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/vmalloc.c |   23 +----------------------
 1 file changed, 1 insertion(+), 22 deletions(-)

diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index 5123a16..4fd3555 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -744,7 +744,6 @@ struct vmap_block {
 	struct vmap_area *va;
 	struct vmap_block_queue *vbq;
 	unsigned long free, dirty;
-	DECLARE_BITMAP(alloc_map, VMAP_BBMAP_BITS);
 	DECLARE_BITMAP(dirty_map, VMAP_BBMAP_BITS);
 	struct list_head free_list;
 	struct rcu_head rcu_head;
@@ -810,7 +809,6 @@ static struct vmap_block *new_vmap_block(gfp_t gfp_mask)
 	vb->va = va;
 	vb->free = VMAP_BBMAP_BITS;
 	vb->dirty = 0;
-	bitmap_zero(vb->alloc_map, VMAP_BBMAP_BITS);
 	bitmap_zero(vb->dirty_map, VMAP_BBMAP_BITS);
 	INIT_LIST_HEAD(&vb->free_list);

@@ -863,7 +861,6 @@ static void purge_fragmented_blocks(int cpu)
 		if (vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty !=
VMAP_BBMAP_BITS) {
 			vb->free = 0; /* prevent further allocs after releasing lock */
 			vb->dirty = VMAP_BBMAP_BITS; /* prevent purging it again */
-			bitmap_fill(vb->alloc_map, VMAP_BBMAP_BITS);
 			bitmap_fill(vb->dirty_map, VMAP_BBMAP_BITS);
 			spin_lock(&vbq->lock);
 			list_del_rcu(&vb->free_list);
@@ -881,11 +878,6 @@ static void purge_fragmented_blocks(int cpu)
 	}
 }

-static void purge_fragmented_blocks_thiscpu(void)
-{
-	purge_fragmented_blocks(smp_processor_id());
-}
-
 static void purge_fragmented_blocks_allcpus(void)
 {
 	int cpu;
@@ -900,7 +892,6 @@ static void *vb_alloc(unsigned long size, gfp_t gfp_mask)
 	struct vmap_block *vb;
 	unsigned long addr = 0;
 	unsigned int order;
-	int purge = 0;

 	BUG_ON(size & ~PAGE_MASK);
 	BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
@@ -924,17 +915,8 @@ again:
 		if (vb->free < 1UL << order)
 			goto next;

-		i = bitmap_find_free_region(vb->alloc_map,
-						VMAP_BBMAP_BITS, order);
+		i = VMAP_BBMAP_BITS - vb->free;

-		if (i < 0) {
-			if (vb->free + vb->dirty == VMAP_BBMAP_BITS) {
-				/* fragmented and no outstanding allocations */
-				BUG_ON(vb->dirty != VMAP_BBMAP_BITS);
-				purge = 1;
-			}
-			goto next;
-		}
 		addr = vb->va->va_start + (i << PAGE_SHIFT);
 		BUG_ON(addr_to_vb_idx(addr) !=
 				addr_to_vb_idx(vb->va->va_start));
@@ -950,9 +932,6 @@ next:
 		spin_unlock(&vb->lock);
 	}

-	if (purge)
-		purge_fragmented_blocks_thiscpu();
-
 	put_cpu_var(vmap_block_queue);
 	rcu_read_unlock();

-- 
1.7.9.5

[PATCH] vmalloc: Remove alloc_map from vmap_block.

[Chanho Min]

There is no reason to maintain alloc_map in the vmap_block.
The use of alloc_map may require heavy bitmap operation sometimes.
In the worst-case, We need 1024 for-loops to find 1 free bit and
thus cause overhead. vmap_block is fragmented unnecessarily by
2 order alignment as well.

Instead we can map by using vb->free in order. When It is freed,
Its corresponding bit will be set in the dirty_map and all
free/purge operations are carried out in the dirty_map.
vmap_block is not fragmented sporadically anymore and thus
purge_fragmented_blocks_thiscpu in the vb_alloc can be removed.

Signed-off-by: Chanho Min <chanho.min@lge.com>
Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/vmalloc.c |   23 +----------------------
 1 file changed, 1 insertion(+), 22 deletions(-)

diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index 5123a16..4fd3555 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -744,7 +744,6 @@ struct vmap_block {
 	struct vmap_area *va;
 	struct vmap_block_queue *vbq;
 	unsigned long free, dirty;
-	DECLARE_BITMAP(alloc_map, VMAP_BBMAP_BITS);
 	DECLARE_BITMAP(dirty_map, VMAP_BBMAP_BITS);
 	struct list_head free_list;
 	struct rcu_head rcu_head;
@@ -810,7 +809,6 @@ static struct vmap_block *new_vmap_block(gfp_t gfp_mask)
 	vb->va = va;
 	vb->free = VMAP_BBMAP_BITS;
 	vb->dirty = 0;
-	bitmap_zero(vb->alloc_map, VMAP_BBMAP_BITS);
 	bitmap_zero(vb->dirty_map, VMAP_BBMAP_BITS);
 	INIT_LIST_HEAD(&vb->free_list);

@@ -863,7 +861,6 @@ static void purge_fragmented_blocks(int cpu)
 		if (vb->free + vb->dirty == VMAP_BBMAP_BITS && vb->dirty !=
VMAP_BBMAP_BITS) {
 			vb->free = 0; /* prevent further allocs after releasing lock */
 			vb->dirty = VMAP_BBMAP_BITS; /* prevent purging it again */
-			bitmap_fill(vb->alloc_map, VMAP_BBMAP_BITS);
 			bitmap_fill(vb->dirty_map, VMAP_BBMAP_BITS);
 			spin_lock(&vbq->lock);
 			list_del_rcu(&vb->free_list);
@@ -881,11 +878,6 @@ static void purge_fragmented_blocks(int cpu)
 	}
 }

-static void purge_fragmented_blocks_thiscpu(void)
-{
-	purge_fragmented_blocks(smp_processor_id());
-}
-
 static void purge_fragmented_blocks_allcpus(void)
 {
 	int cpu;
@@ -900,7 +892,6 @@ static void *vb_alloc(unsigned long size, gfp_t gfp_mask)
 	struct vmap_block *vb;
 	unsigned long addr = 0;
 	unsigned int order;
-	int purge = 0;

 	BUG_ON(size & ~PAGE_MASK);
 	BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
@@ -924,17 +915,8 @@ again:
 		if (vb->free < 1UL << order)
 			goto next;

-		i = bitmap_find_free_region(vb->alloc_map,
-						VMAP_BBMAP_BITS, order);
+		i = VMAP_BBMAP_BITS - vb->free;

-		if (i < 0) {
-			if (vb->free + vb->dirty == VMAP_BBMAP_BITS) {
-				/* fragmented and no outstanding allocations */
-				BUG_ON(vb->dirty != VMAP_BBMAP_BITS);
-				purge = 1;
-			}
-			goto next;
-		}
 		addr = vb->va->va_start + (i << PAGE_SHIFT);
 		BUG_ON(addr_to_vb_idx(addr) !=
 				addr_to_vb_idx(vb->va->va_start));
@@ -950,9 +932,6 @@ next:
 		spin_unlock(&vb->lock);
 	}

-	if (purge)
-		purge_fragmented_blocks_thiscpu();
-
 	put_cpu_var(vmap_block_queue);
 	rcu_read_unlock();

-- 
1.7.9.5

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] vmalloc: Remove alloc_map from vmap_block.

[Johannes Weiner]

Hi Chanho,

On Thu, Feb 07, 2013 at 11:27:54AM +0900, Chanho Min wrote:
> There is no reason to maintain alloc_map in the vmap_block.
> The use of alloc_map may require heavy bitmap operation sometimes.
> In the worst-case, We need 1024 for-loops to find 1 free bit and
> thus cause overhead. vmap_block is fragmented unnecessarily by
> 2 order alignment as well.
> 
> Instead we can map by using vb->free in order. When It is freed,
> Its corresponding bit will be set in the dirty_map and all
> free/purge operations are carried out in the dirty_map.
> vmap_block is not fragmented sporadically anymore and thus
> purge_fragmented_blocks_thiscpu in the vb_alloc can be removed.

I submitted a similar patch some time ago, but at the time Mel
suggested instead to figure out if this bitmap was not supposed to be
doing something useful and depending on that implement recycling of
partially used vmap blocks.

Here is the thread:

https://lkml.org/lkml/2011/4/14/619

I started looking for workloads to profile but then lost interest.
The current code can theoretically end up walking through a lot of
partially used blocks if a string of allocations never fit any of
them.  The number of these blocks depends on previous allocations that
leave them unusable for future allocations and whether any other
vmalloc/vmap user recently flushed them all.  So it's painful to think
about it and hard to impossible to pin down should this ever actually
result in a performance problem.

Either way, short of an actual fix I suspect this patch will pop up
again as it removes currently dead code.

Re: [PATCH] vmalloc: Remove alloc_map from vmap_block.

[Johannes Weiner]

Hi Chanho,

On Thu, Feb 07, 2013 at 11:27:54AM +0900, Chanho Min wrote:
> There is no reason to maintain alloc_map in the vmap_block.
> The use of alloc_map may require heavy bitmap operation sometimes.
> In the worst-case, We need 1024 for-loops to find 1 free bit and
> thus cause overhead. vmap_block is fragmented unnecessarily by
> 2 order alignment as well.
> 
> Instead we can map by using vb->free in order. When It is freed,
> Its corresponding bit will be set in the dirty_map and all
> free/purge operations are carried out in the dirty_map.
> vmap_block is not fragmented sporadically anymore and thus
> purge_fragmented_blocks_thiscpu in the vb_alloc can be removed.

I submitted a similar patch some time ago, but at the time Mel
suggested instead to figure out if this bitmap was not supposed to be
doing something useful and depending on that implement recycling of
partially used vmap blocks.

Here is the thread:

https://lkml.org/lkml/2011/4/14/619

I started looking for workloads to profile but then lost interest.
The current code can theoretically end up walking through a lot of
partially used blocks if a string of allocations never fit any of
them.  The number of these blocks depends on previous allocations that
leave them unusable for future allocations and whether any other
vmalloc/vmap user recently flushed them all.  So it's painful to think
about it and hard to impossible to pin down should this ever actually
result in a performance problem.

Either way, short of an actual fix I suspect this patch will pop up
again as it removes currently dead code.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] vmalloc: Remove alloc_map from vmap_block.

[Chanho Min]

>I started looking for workloads to profile but then lost interest.
>The current code can theoretically end up walking through a lot of
>partially used blocks if a string of allocations never fit any of
>them.  The number of these blocks depends on previous allocations that
>leave them unusable for future allocations and whether any other
>vmalloc/vmap user recently flushed them all.  So it's painful to think
>about it and hard to impossible to pin down should this ever actually
>result in a performance problem.

vm_map_ram() is allowed to be called by external kernel module.
I profiled some kernel module as bellow perf log. Its mapping behavior
was most of the workload. yes, we can improve its inefficient mapping.
But, This shows the allocation bitmap has the potential to cause significant
overhead.

# Overhead          Command        Shared Object
                  Symbol
# ........  ...............  ...................
.............................................
#
    42.74%  XXXXXXTextureSc  [kernel.kallsyms]    [k] __reg_op
            |
            --- __reg_op
               |
               |--5.39%-- 0xaf57de00
               |          |
               |           --100.00%-- malloc
               |
               |--2.35%-- 0xaf57da00
               |          |
               |           --100.00%-- malloc
               |
               |--2.10%-- 0xaf57ce00
               |          |
               |           --100.00%-- malloc
               |
               |--1.46%-- 0xaf57c800
               |          |
               |           --100.00%-- malloc
               |
               |--1.43%-- 0xaf57dc00
               |          |
               |           --100.00%-- malloc
               |
               |--1.36%-- 0xaf57c200
               |          |
               |           --100.00%-- malloc
               |
               |--1.34%-- 0xaf57c000
               |          |
               |           --100.00%-- malloc
               |
               |--1.26%-- 0xae915400
               |          |
               |           --100.00%-- malloc
               |
               |--0.80%-- 0xae914200
               |          |
               |           --100.00%-- malloc
               |
               |--0.79%-- 0xaf57ca00
               |          |
               |           --100.00%-- malloc
               |
               |--0.67%-- 0xaf57d000
               |          |
               |           --100.00%-- malloc
               |
               |--0.52%-- 0xaf57cc00
               |          |
               |           --100.00%-- malloc
                --80.54%-- [...]
    17.39%  XXXXXXTextureSc  [kernel.kallsyms]    [k]
bitmap_find_free_region
            |
            --- bitmap_find_free_region
               |
               |--99.93%-- vm_map_ram
               |          0x7f00097c
               |          0x7f00985c
               |          |
               |          |--99.79%-- 0x7f009948
               |          |          |
               |          |          |--50.24%-- 0x7f00ab90
               |          |          |          0x7f006c50
               |          |          |          0x7f00e948
               |          |          |          0x7f019630
               |          |          |          0x7f00f0ac
               |          |          |          0x7f002384
               |          |          |          vfs_ioctl
               |          |          |          do_vfs_ioctl
               |          |          |          sys_ioctl
               |          |          |          ret_fast_syscall
               |          |          |
               |          |          |--49.60%-- 0x7f00acfc
               |          |          |          0x7f006bfc
               |          |          |          0x7f018fac
               |          |          |          0x7f00f0ac
               |          |          |          0x7f002384
               |          |          |          vfs_ioctl
               |          |          |          do_vfs_ioctl
               |          |          |          sys_ioctl
               |          |          |          ret_fast_syscall
               |          |          |          malloc
               |          |           --0.16%-- [...]
...

Thanks
Chanho Min

Re: [PATCH] vmalloc: Remove alloc_map from vmap_block.

[Chanho Min]

>I started looking for workloads to profile but then lost interest.
>The current code can theoretically end up walking through a lot of
>partially used blocks if a string of allocations never fit any of
>them.  The number of these blocks depends on previous allocations that
>leave them unusable for future allocations and whether any other
>vmalloc/vmap user recently flushed them all.  So it's painful to think
>about it and hard to impossible to pin down should this ever actually
>result in a performance problem.

vm_map_ram() is allowed to be called by external kernel module.
I profiled some kernel module as bellow perf log. Its mapping behavior
was most of the workload. yes, we can improve its inefficient mapping.
But, This shows the allocation bitmap has the potential to cause significant
overhead.

# Overhead          Command        Shared Object
                  Symbol
# ........  ...............  ...................
.............................................
#
    42.74%  XXXXXXTextureSc  [kernel.kallsyms]    [k] __reg_op
            |
            --- __reg_op
               |
               |--5.39%-- 0xaf57de00
               |          |
               |           --100.00%-- malloc
               |
               |--2.35%-- 0xaf57da00
               |          |
               |           --100.00%-- malloc
               |
               |--2.10%-- 0xaf57ce00
               |          |
               |           --100.00%-- malloc
               |
               |--1.46%-- 0xaf57c800
               |          |
               |           --100.00%-- malloc
               |
               |--1.43%-- 0xaf57dc00
               |          |
               |           --100.00%-- malloc
               |
               |--1.36%-- 0xaf57c200
               |          |
               |           --100.00%-- malloc
               |
               |--1.34%-- 0xaf57c000
               |          |
               |           --100.00%-- malloc
               |
               |--1.26%-- 0xae915400
               |          |
               |           --100.00%-- malloc
               |
               |--0.80%-- 0xae914200
               |          |
               |           --100.00%-- malloc
               |
               |--0.79%-- 0xaf57ca00
               |          |
               |           --100.00%-- malloc
               |
               |--0.67%-- 0xaf57d000
               |          |
               |           --100.00%-- malloc
               |
               |--0.52%-- 0xaf57cc00
               |          |
               |           --100.00%-- malloc
                --80.54%-- [...]
    17.39%  XXXXXXTextureSc  [kernel.kallsyms]    [k]
bitmap_find_free_region
            |
            --- bitmap_find_free_region
               |
               |--99.93%-- vm_map_ram
               |          0x7f00097c
               |          0x7f00985c
               |          |
               |          |--99.79%-- 0x7f009948
               |          |          |
               |          |          |--50.24%-- 0x7f00ab90
               |          |          |          0x7f006c50
               |          |          |          0x7f00e948
               |          |          |          0x7f019630
               |          |          |          0x7f00f0ac
               |          |          |          0x7f002384
               |          |          |          vfs_ioctl
               |          |          |          do_vfs_ioctl
               |          |          |          sys_ioctl
               |          |          |          ret_fast_syscall
               |          |          |
               |          |          |--49.60%-- 0x7f00acfc
               |          |          |          0x7f006bfc
               |          |          |          0x7f018fac
               |          |          |          0x7f00f0ac
               |          |          |          0x7f002384
               |          |          |          vfs_ioctl
               |          |          |          do_vfs_ioctl
               |          |          |          sys_ioctl
               |          |          |          ret_fast_syscall
               |          |          |          malloc
               |          |           --0.16%-- [...]
...

Thanks
Chanho Min

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] vmalloc: Remove alloc_map from vmap_block.

[Johannes Weiner]

On Fri, Feb 08, 2013 at 12:37:13PM +0900, Chanho Min wrote:
> >I started looking for workloads to profile but then lost interest.
> >The current code can theoretically end up walking through a lot of
> >partially used blocks if a string of allocations never fit any of
> >them.  The number of these blocks depends on previous allocations that
> >leave them unusable for future allocations and whether any other
> >vmalloc/vmap user recently flushed them all.  So it's painful to think
> >about it and hard to impossible to pin down should this ever actually
> >result in a performance problem.
> 
> vm_map_ram() is allowed to be called by external kernel module.
> I profiled some kernel module as bellow perf log. Its mapping behavior
> was most of the workload. yes, we can improve its inefficient mapping.
> But, This shows the allocation bitmap has the potential to cause significant
> overhead.

No question that you can find a scenario where this bitmap becomes
expensive.  And I don't think we should leave the code as is, because
it really is a waste of time for cpus and readers of the code.

The question is whether we put the bitmap to good use and implement
partial block recycling, or keep with the current allocation model but
make it a little less expensive.

Nobody actually seems interested in implementing partial block
recycling and we do have multiple patches to ditch the bitmap.  I
think we should probably merge the patch that we have and save some
wasted cycles, that doesn't prevent anyone from improving the
algorithm later on.

Re: [PATCH] vmalloc: Remove alloc_map from vmap_block.

[Johannes Weiner]

On Fri, Feb 08, 2013 at 12:37:13PM +0900, Chanho Min wrote:
> >I started looking for workloads to profile but then lost interest.
> >The current code can theoretically end up walking through a lot of
> >partially used blocks if a string of allocations never fit any of
> >them.  The number of these blocks depends on previous allocations that
> >leave them unusable for future allocations and whether any other
> >vmalloc/vmap user recently flushed them all.  So it's painful to think
> >about it and hard to impossible to pin down should this ever actually
> >result in a performance problem.
> 
> vm_map_ram() is allowed to be called by external kernel module.
> I profiled some kernel module as bellow perf log. Its mapping behavior
> was most of the workload. yes, we can improve its inefficient mapping.
> But, This shows the allocation bitmap has the potential to cause significant
> overhead.

No question that you can find a scenario where this bitmap becomes
expensive.  And I don't think we should leave the code as is, because
it really is a waste of time for cpus and readers of the code.

The question is whether we put the bitmap to good use and implement
partial block recycling, or keep with the current allocation model but
make it a little less expensive.

Nobody actually seems interested in implementing partial block
recycling and we do have multiple patches to ditch the bitmap.  I
think we should probably merge the patch that we have and save some
wasted cycles, that doesn't prevent anyone from improving the
algorithm later on.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>