[PATCH] mm/page: refine the calculation of highest possible node id

[PATCH] mm/page: refine the calculation of highest possible node id

[Wei Yang]

nr_node_ids records the highest possible node id, which is calculated by
scanning the bitmap node_states[N_POSSIBLE]. Current implementation scan
the bitmap from the beginning, which will scan the whole bitmap.

This patch reverse the order by scanning from the end. By doing so, this
will save some time whose worst case is the best case of current
implementation.

Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
---
 include/linux/nodemask.h |   16 ++++++++++++++++
 mm/page_alloc.c          |    3 +--
 2 files changed, 17 insertions(+), 2 deletions(-)

diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
index 6e85889..dfca95f 100644
--- a/include/linux/nodemask.h
+++ b/include/linux/nodemask.h
@@ -253,6 +253,12 @@ static inline int __first_node(const nodemask_t *srcp)
 	return min_t(int, MAX_NUMNODES, find_first_bit(srcp->bits, MAX_NUMNODES));
 }
 
+#define last_node(src) __last_node(&(src))
+static inline int __last_node(const nodemask_t *srcp)
+{
+	return min_t(int, MAX_NUMNODES, find_last_bit(srcp->bits, MAX_NUMNODES));
+}
+
 #define next_node(n, src) __next_node((n), &(src))
 static inline int __next_node(int n, const nodemask_t *srcp)
 {
@@ -360,10 +366,20 @@ static inline void __nodes_fold(nodemask_t *dstp, const nodemask_t *origp,
 	for ((node) = first_node(mask);			\
 		(node) < MAX_NUMNODES;			\
 		(node) = next_node((node), (mask)))
+
+static inline int highest_node_id(const nodemask_t possible)
+{
+	return last_node(possible);
+}
 #else /* MAX_NUMNODES == 1 */
 #define for_each_node_mask(node, mask)			\
 	if (!nodes_empty(mask))				\
 		for ((node) = 0; (node) < 1; (node)++)
+
+static inline int highest_node_id(const nodemask_t possible)
+{
+	return 0;
+}
 #endif /* MAX_NUMNODES */
 
 /*
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 506eac8..b2f75ea 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -5453,8 +5453,7 @@ void __init setup_nr_node_ids(void)
 	unsigned int node;
 	unsigned int highest = 0;
 
-	for_each_node_mask(node, node_possible_map)
-		highest = node;
+	highest = highest_node_id(node_possible_map);
 	nr_node_ids = highest + 1;
 }
 #endif
-- 
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] mm/page: refine the calculation of highest possible node id

[Andrew Morton]

On Fri, 10 Jul 2015 14:26:21 +0800 Wei Yang <weiyang@linux.vnet.ibm.com> wrote:

> nr_node_ids records the highest possible node id, which is calculated by
> scanning the bitmap node_states[N_POSSIBLE]. Current implementation scan
> the bitmap from the beginning, which will scan the whole bitmap.
> 
> This patch reverse the order by scanning from the end. By doing so, this
> will save some time whose worst case is the best case of current
> implementation.

It hardly matters - setup_nr_node_ids() is called a single time, at boot.

> --- a/include/linux/nodemask.h
> +++ b/include/linux/nodemask.h
> @@ -253,6 +253,12 @@ static inline int __first_node(const nodemask_t *srcp)
>  	return min_t(int, MAX_NUMNODES, find_first_bit(srcp->bits, MAX_NUMNODES));
>  }
>  
> +#define last_node(src) __last_node(&(src))
> +static inline int __last_node(const nodemask_t *srcp)
> +{
> +	return min_t(int, MAX_NUMNODES, find_last_bit(srcp->bits, MAX_NUMNODES));
> +}

hm.  Why isn't this just

	return find_last_bit(srcp->bits, MAX_NUMNODES);

?

> @@ -360,10 +366,20 @@ static inline void __nodes_fold(nodemask_t *dstp, const nodemask_t *origp,
>  	for ((node) = first_node(mask);			\
>  		(node) < MAX_NUMNODES;			\
>  		(node) = next_node((node), (mask)))
> +
> +static inline int highest_node_id(const nodemask_t possible)
> +{
> +	return last_node(possible);
> +}

`possible' isn't a good identifier.  This function doesn't *know* that
its caller passed node_possible_map.  Another caller could pass some
other nodemask.

> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -5453,8 +5453,7 @@ void __init setup_nr_node_ids(void)
>  	unsigned int node;
>  	unsigned int highest = 0;

The "= 0" can now be removed.

> -	for_each_node_mask(node, node_possible_map)
> -		highest = node;
> +	highest = highest_node_id(node_possible_map);

I suspect we can just open-code a find_last_bit() here and all the
infrastructure isn't needed.

>  	nr_node_ids = highest + 1;
>  }


And I suspect the "#if MAX_NUMNODES > 1" around setup_nr_node_ids() can
be removed.  Because if MAX_NUMNODES is ever <= 1 when
CONFIG_HAVE_MEMBLOCK_NODE_MAP=y, the kernel won't compile.

--
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] mm/page: refine the calculation of highest possible node id

[Wei Yang]

On Fri, Jul 10, 2015 at 12:35:55AM -0700, Andrew Morton wrote:
>On Fri, 10 Jul 2015 14:26:21 +0800 Wei Yang <weiyang@linux.vnet.ibm.com> wrote:
>
>> nr_node_ids records the highest possible node id, which is calculated by
>> scanning the bitmap node_states[N_POSSIBLE]. Current implementation scan
>> the bitmap from the beginning, which will scan the whole bitmap.
>> 
>> This patch reverse the order by scanning from the end. By doing so, this
>> will save some time whose worst case is the best case of current
>> implementation.
>
>It hardly matters - setup_nr_node_ids() is called a single time, at boot.

Hi, Andrew,

Glad to receive your comment :-)

Yes, the hardly matters on the performance side, while scanning from the end is
a better way to me. Hope you like it.

>
>> --- a/include/linux/nodemask.h
>> +++ b/include/linux/nodemask.h
>> @@ -253,6 +253,12 @@ static inline int __first_node(const nodemask_t *srcp)
>>  	return min_t(int, MAX_NUMNODES, find_first_bit(srcp->bits, MAX_NUMNODES));
>>  }
>>  
>> +#define last_node(src) __last_node(&(src))
>> +static inline int __last_node(const nodemask_t *srcp)
>> +{
>> +	return min_t(int, MAX_NUMNODES, find_last_bit(srcp->bits, MAX_NUMNODES));
>> +}
>
>hm.  Why isn't this just
>
>	return find_last_bit(srcp->bits, MAX_NUMNODES);
>
>?

I found this comment in the code:

/* FIXME: better would be to fix all architectures to never return
          > MAX_NUMNODES, then the silly min_ts could be dropped. */

While I didn't find the original commit for this change, so not dear to change
the related code format.

>
>> @@ -360,10 +366,20 @@ static inline void __nodes_fold(nodemask_t *dstp, const nodemask_t *origp,
>>  	for ((node) = first_node(mask);			\
>>  		(node) < MAX_NUMNODES;			\
>>  		(node) = next_node((node), (mask)))
>> +
>> +static inline int highest_node_id(const nodemask_t possible)
>> +{
>> +	return last_node(possible);
>> +}
>
>`possible' isn't a good identifier.  This function doesn't *know* that
>its caller passed node_possible_map.  Another caller could pass some
>other nodemask.
>

Agree. I would change it.

>> --- a/mm/page_alloc.c
>> +++ b/mm/page_alloc.c
>> @@ -5453,8 +5453,7 @@ void __init setup_nr_node_ids(void)
>>  	unsigned int node;
>>  	unsigned int highest = 0;
>
>The "= 0" can now be removed.
>
>> -	for_each_node_mask(node, node_possible_map)
>> -		highest = node;
>> +	highest = highest_node_id(node_possible_map);
>
>I suspect we can just open-code a find_last_bit() here and all the
>infrastructure isn't needed.
>

This is reasonable. If so, the code would be more clear.

>>  	nr_node_ids = highest + 1;
>>  }
>
>
>And I suspect the "#if MAX_NUMNODES > 1" around setup_nr_node_ids() can
>be removed.  Because if MAX_NUMNODES is ever <= 1 when
>CONFIG_HAVE_MEMBLOCK_NODE_MAP=y, the kernel won't compile.

Hmm... for this one, I am not sure.

#define MAX_NUMNODES    (1 << NODES_SHIFT)
#define NODES_SHIFT     CONFIG_NODES_SHIFT

CONFIG_NODES_SHIFT depends on CONFIG_NEED_MULTIPLE_NODES, which depends on
CONFIG_DISCONTIGMEM or CONFIG_NUMA.

And I grep the kernel tree, not see other configuration would depend on
HAVE_MEMBLOCK_NODE_MAP.

So I am don't get a clear clue for this suspection.

-- 
Richard Yang
Help you, Help me

--
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>

[PATCH V2] mm/page: refine the calculation of highest possible node id

[Wei Yang]

nr_node_ids records the highest possible node id, which is calculated by
scanning the bitmap node_states[N_POSSIBLE]. Current implementation scan
the bitmap from the beginning, which will scan the whole bitmap.

This patch reverse the order by scanning from the end with find_last_bit().

Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Tejun Heo <tj@kernel.org>

---
v2:
   Just call find_last_bit() on node_possible_map.
---
 mm/page_alloc.c |    5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 59248f4..f8d0a98 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -5450,10 +5450,9 @@ void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
 void __init setup_nr_node_ids(void)
 {
 	unsigned int node;
-	unsigned int highest = 0;
+	unsigned int highest;
 
-	for_each_node_mask(node, node_possible_map)
-		highest = node;
+	highest = find_last_bit(node_possible_map.bits, MAX_NUMNODES);
 	nr_node_ids = highest + 1;
 }
 #endif
-- 
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>

[PATCH V3] mm/page: refine the calculation of highest possible node id

[Wei Yang]

nr_node_ids records the highest possible node id, which is calculated by
scanning the bitmap node_states[N_POSSIBLE]. Current implementation scan
the bitmap from the beginning, which will scan the whole bitmap.

This patch reverse the order by scanning from the end with find_last_bit().

Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
CC: Andrew Morton <akpm@linux-foundation.org>
CC: Tejun Heo <tj@kernel.org>

---
v3:
   remove the unused variable node.
v2:
   Just call find_last_bit() on node_possible_map.
---
 mm/page_alloc.c |    6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 59248f4..c635e80 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -5449,11 +5449,9 @@ void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
  */
 void __init setup_nr_node_ids(void)
 {
-	unsigned int node;
-	unsigned int highest = 0;
+	unsigned int highest;
 
-	for_each_node_mask(node, node_possible_map)
-		highest = node;
+	highest = find_last_bit(node_possible_map.bits, MAX_NUMNODES);
 	nr_node_ids = highest + 1;
 }
 #endif
-- 
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 V3] mm/page: refine the calculation of highest possible node id

[David Rientjes]

On Sat, 11 Jul 2015, Wei Yang wrote:

> nr_node_ids records the highest possible node id, which is calculated by
> scanning the bitmap node_states[N_POSSIBLE]. Current implementation scan
> the bitmap from the beginning, which will scan the whole bitmap.
> 
> This patch reverse the order by scanning from the end with find_last_bit().
> 
> Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
> CC: Andrew Morton <akpm@linux-foundation.org>
> CC: Tejun Heo <tj@kernel.org>

Acked-by: David Rientjes <rientjes@google.com>

--
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>