[PATCH] mm/vmalloc: reduce half comparison during pcpu_get_vm_areas()

[PATCH] mm/vmalloc: reduce half comparison during pcpu_get_vm_areas()

[Wei Yang]

In pcpu_get_vm_areas(), it checks each range is not overlapped. To make
sure it is, only (N^2)/2 comparison is necessary, while current code does
N^2 times. By starting from the next range, it achieves the goal and the
continue could be removed.

At the mean time, other two work in this patch:
*  the overlap check of two ranges could be done with one clause
*  one typo in comment is fixed.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 mm/vmalloc.c | 10 +++-------
 1 file changed, 3 insertions(+), 7 deletions(-)

diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index 8087451cb332..f33c8350fd83 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -2457,7 +2457,7 @@ static unsigned long pvm_determine_end(struct vmap_area **pnext,
  * matching slot.  While scanning, if any of the areas overlaps with
  * existing vmap_area, the base address is pulled down to fit the
  * area.  Scanning is repeated till all the areas fit and then all
- * necessary data structres are inserted and the result is returned.
+ * necessary data structures are inserted and the result is returned.
  */
 struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
 				     const size_t *sizes, int nr_vms,
@@ -2485,15 +2485,11 @@ struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
 		if (start > offsets[last_area])
 			last_area = area;
 
-		for (area2 = 0; area2 < nr_vms; area2++) {
+		for (area2 = area + 1; area2 < nr_vms; area2++) {
 			unsigned long start2 = offsets[area2];
 			unsigned long end2 = start2 + sizes[area2];
 
-			if (area2 == area)
-				continue;
-
-			BUG_ON(start2 >= start && start2 < end);
-			BUG_ON(end2 <= end && end2 > start);
+			BUG_ON(start2 < end && start < end2);
 		}
 	}
 	last_end = offsets[last_area] + sizes[last_area];
-- 
2.11.0

Re: [PATCH] mm/vmalloc: reduce half comparison during pcpu_get_vm_areas()

[Michal Hocko]

[CC Tejun]

On Thu 03-08-17 14:38:22, Wei Yang wrote:
> In pcpu_get_vm_areas(), it checks each range is not overlapped. To make
> sure it is, only (N^2)/2 comparison is necessary, while current code does
> N^2 times. By starting from the next range, it achieves the goal and the
> continue could be removed.
> 
> At the mean time, other two work in this patch:
> *  the overlap check of two ranges could be done with one clause
> *  one typo in comment is fixed.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> ---
>  mm/vmalloc.c | 10 +++-------
>  1 file changed, 3 insertions(+), 7 deletions(-)
> 
> diff --git a/mm/vmalloc.c b/mm/vmalloc.c
> index 8087451cb332..f33c8350fd83 100644
> --- a/mm/vmalloc.c
> +++ b/mm/vmalloc.c
> @@ -2457,7 +2457,7 @@ static unsigned long pvm_determine_end(struct vmap_area **pnext,
>   * matching slot.  While scanning, if any of the areas overlaps with
>   * existing vmap_area, the base address is pulled down to fit the
>   * area.  Scanning is repeated till all the areas fit and then all
> - * necessary data structres are inserted and the result is returned.
> + * necessary data structures are inserted and the result is returned.
>   */
>  struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
>  				     const size_t *sizes, int nr_vms,
> @@ -2485,15 +2485,11 @@ struct vm_struct **pcpu_get_vm_areas(const unsigned long *offsets,
>  		if (start > offsets[last_area])
>  			last_area = area;
>  
> -		for (area2 = 0; area2 < nr_vms; area2++) {
> +		for (area2 = area + 1; area2 < nr_vms; area2++) {
>  			unsigned long start2 = offsets[area2];
>  			unsigned long end2 = start2 + sizes[area2];
>  
> -			if (area2 == area)
> -				continue;
> -
> -			BUG_ON(start2 >= start && start2 < end);
> -			BUG_ON(end2 <= end && end2 > start);
> +			BUG_ON(start2 < end && start < end2);
>  		}
>  	}
>  	last_end = offsets[last_area] + sizes[last_area];
> -- 
> 2.11.0
> 

-- 
Michal Hocko
SUSE Labs

Re: [PATCH] mm/vmalloc: reduce half comparison during pcpu_get_vm_areas()

[Tejun Heo]

On Thu, Aug 03, 2017 at 02:38:22PM +0800, Wei Yang wrote:
> In pcpu_get_vm_areas(), it checks each range is not overlapped. To make
> sure it is, only (N^2)/2 comparison is necessary, while current code does
> N^2 times. By starting from the next range, it achieves the goal and the
> continue could be removed.
> 
> At the mean time, other two work in this patch:
> *  the overlap check of two ranges could be done with one clause
> *  one typo in comment is fixed.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>

Acked-by: Tejun Heo <tj@kernel.org>

Thanks.

-- 
tejun