[PATCH] mm/slub: skip node in case there is no slab to acquire

[PATCH] mm/slub: skip node in case there is no slab to acquire

[Wei Yang]

for_each_zone_zonelist() iterates the zonelist one by one, which means
it will iterate on zones on the same node. While get_partial_node()
checks available slab on node base instead of zone.

This patch skip a node in case get_partial_node() fails to acquire slab
on that node.

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

diff --git a/mm/slub.c b/mm/slub.c
index e3629cd7aff1..97a480b5dfb9 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1873,7 +1873,7 @@ static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
  * Get a page from somewhere. Search in increasing NUMA distances.
  */
 static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
-		struct kmem_cache_cpu *c)
+		struct kmem_cache_cpu *c, int except)
 {
 #ifdef CONFIG_NUMA
 	struct zonelist *zonelist;
@@ -1882,6 +1882,9 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 	enum zone_type high_zoneidx = gfp_zone(flags);
 	void *object;
 	unsigned int cpuset_mems_cookie;
+	nodemask_t nmask = node_states[N_MEMORY];
+
+	node_clear(except, nmask);
 
 	/*
 	 * The defrag ratio allows a configuration of the tradeoffs between
@@ -1908,7 +1911,8 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 	do {
 		cpuset_mems_cookie = read_mems_allowed_begin();
 		zonelist = node_zonelist(mempolicy_slab_node(), flags);
-		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
+		for_each_zone_zonelist_nodemask(zone, z, zonelist,
+						high_zoneidx, &nmask) {
 			struct kmem_cache_node *n;
 
 			n = get_node(s, zone_to_nid(zone));
@@ -1926,6 +1930,7 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 					 */
 					return object;
 				}
+				node_clear(zone_to_nid(zone), nmask);
 			}
 		}
 	} while (read_mems_allowed_retry(cpuset_mems_cookie));
@@ -1951,7 +1956,7 @@ static void *get_partial(struct kmem_cache *s, gfp_t flags, int node,
 	if (object || node != NUMA_NO_NODE)
 		return object;
 
-	return get_any_partial(s, flags, c);
+	return get_any_partial(s, flags, c, searchnode);
 }
 
 #ifdef CONFIG_PREEMPT
-- 
2.15.1

Re: [PATCH] mm/slub: skip node in case there is no slab to acquire

[Andrew Morton]

On Thu,  8 Nov 2018 09:12:04 +0800 Wei Yang <richard.weiyang@gmail.com> wrote:

> for_each_zone_zonelist() iterates the zonelist one by one, which means
> it will iterate on zones on the same node. While get_partial_node()
> checks available slab on node base instead of zone.
> 
> This patch skip a node in case get_partial_node() fails to acquire slab
> on that node.

This is rather hard to follow.

I *think* the patch is a performance optimization: prevent
get_any_partial() from checking a node which get_partial_node() has
already looked at?

Could we please have a more complete changelog?

> --- a/mm/slub.c
> +++ b/mm/slub.c
> @@ -1873,7 +1873,7 @@ static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
>   * Get a page from somewhere. Search in increasing NUMA distances.
>   */
>  static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
> -		struct kmem_cache_cpu *c)
> +		struct kmem_cache_cpu *c, int except)
>  {
>  #ifdef CONFIG_NUMA
>  	struct zonelist *zonelist;
> @@ -1882,6 +1882,9 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
>  	enum zone_type high_zoneidx = gfp_zone(flags);
>  	void *object;
>  	unsigned int cpuset_mems_cookie;
> +	nodemask_t nmask = node_states[N_MEMORY];
> +
> +	node_clear(except, nmask);

And please add a comment describing what's happening here and why it is
done.  Adding a sentence to the block comment over get_any_partial()
would be suitable.

Re: [PATCH] mm/slub: skip node in case there is no slab to acquire

[Wei Yang]

On Fri, Nov 09, 2018 at 12:48:06PM -0800, Andrew Morton wrote:
>On Thu,  8 Nov 2018 09:12:04 +0800 Wei Yang <richard.weiyang@gmail.com> wrote:
>
>> for_each_zone_zonelist() iterates the zonelist one by one, which means
>> it will iterate on zones on the same node. While get_partial_node()
>> checks available slab on node base instead of zone.
>> 
>> This patch skip a node in case get_partial_node() fails to acquire slab
>> on that node.
>
>This is rather hard to follow.
>
>I *think* the patch is a performance optimization: prevent
>get_any_partial() from checking a node which get_partial_node() has
>already looked at?

You are right :-)

>
>Could we please have a more complete changelog?

Hmm... I would like to.

But I am not sure which part makes you hard to follow. If you would like
to tell me the pain point, I am glad to think about how to make it more
obvious.

>
>> --- a/mm/slub.c
>> +++ b/mm/slub.c
>> @@ -1873,7 +1873,7 @@ static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
>>   * Get a page from somewhere. Search in increasing NUMA distances.
>>   */
>>  static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
>> -		struct kmem_cache_cpu *c)
>> +		struct kmem_cache_cpu *c, int except)
>>  {
>>  #ifdef CONFIG_NUMA
>>  	struct zonelist *zonelist;
>> @@ -1882,6 +1882,9 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
>>  	enum zone_type high_zoneidx = gfp_zone(flags);
>>  	void *object;
>>  	unsigned int cpuset_mems_cookie;
>> +	nodemask_t nmask = node_states[N_MEMORY];
>> +
>> +	node_clear(except, nmask);
>
>And please add a comment describing what's happening here and why it is
>done.  Adding a sentence to the block comment over get_any_partial()
>would be suitable.
>

Sure, I would address this in next spin.

-- 
Wei Yang
Help you, Help me

[PATCH v2] mm/slub: skip node in case there is no slab to acquire

[Wei Yang]

Current slub has three layers:

  * cpu_slab
  * percpu_partial
  * per node partial list

Slub allocator tries to get an object from top to bottom. When it can't
get an object from the upper two layers, it will search the per node
partial list. The is done in get_partial().

The abstraction of get_partial() may looks like this:

    get_partial()
        get_partial_node()
        get_any_partial()
            for_each_zone_zonelist()

The idea behind this is: it first try a local node, then try other nodes
if caller doesn't specify a node.

When we look one step deeper in get_any_partial(), it tries to get a
proper node by for_each_zone_zonelist(), which iterates on the
node_zonelists.

This behavior would introduce some redundant check on the same node.
Because:

  * the local node is already checked in get_partial_node()
  * one node may have several zones on node_zonelists

We could reduce these redundant check by providing a nodemask during
node_zonelists iteration.

  * clear the local node which is already checked in get_partial_node()
  * clear a node if we can't get an object from it.

This patch replaces for_each_zone_zonelist() with
for_each_zone_zonelist_nodemask() to skip the node which fails to acquire
an object.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
v2: rewrite the changelog and add a comment based on Andrew's comment
---
 mm/slub.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index e3629cd7aff1..e3db5cd52507 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1873,7 +1873,7 @@ static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
  * Get a page from somewhere. Search in increasing NUMA distances.
  */
 static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
-		struct kmem_cache_cpu *c)
+		struct kmem_cache_cpu *c, int except)
 {
 #ifdef CONFIG_NUMA
 	struct zonelist *zonelist;
@@ -1882,6 +1882,9 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 	enum zone_type high_zoneidx = gfp_zone(flags);
 	void *object;
 	unsigned int cpuset_mems_cookie;
+	nodemask_t nmask = node_states[N_MEMORY];
+
+	node_clear(except, nmask);
 
 	/*
 	 * The defrag ratio allows a configuration of the tradeoffs between
@@ -1908,7 +1911,8 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 	do {
 		cpuset_mems_cookie = read_mems_allowed_begin();
 		zonelist = node_zonelist(mempolicy_slab_node(), flags);
-		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
+		for_each_zone_zonelist_nodemask(zone, z, zonelist,
+						high_zoneidx, &nmask) {
 			struct kmem_cache_node *n;
 
 			n = get_node(s, zone_to_nid(zone));
@@ -1926,6 +1930,11 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 					 */
 					return object;
 				}
+				/*
+				 * Fail to get object from this node,
+				 * clear this to skip this node
+				 */
+				node_clear(zone_to_nid(zone), nmask);
 			}
 		}
 	} while (read_mems_allowed_retry(cpuset_mems_cookie));
@@ -1951,7 +1960,7 @@ static void *get_partial(struct kmem_cache *s, gfp_t flags, int node,
 	if (object || node != NUMA_NO_NODE)
 		return object;
 
-	return get_any_partial(s, flags, c);
+	return get_any_partial(s, flags, c, searchnode);
 }
 
 #ifdef CONFIG_PREEMPT
-- 
2.15.1

Re: [PATCH] mm/slub: skip node in case there is no slab to acquire

[Michal Hocko]

On Thu 08-11-18 09:12:04, Wei Yang wrote:
> for_each_zone_zonelist() iterates the zonelist one by one, which means
> it will iterate on zones on the same node. While get_partial_node()
> checks available slab on node base instead of zone.
> 
> This patch skip a node in case get_partial_node() fails to acquire slab
> on that node.

If this is an optimization then it should be accompanied by some
numbers.

> @@ -1882,6 +1882,9 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
>  	enum zone_type high_zoneidx = gfp_zone(flags);
>  	void *object;
>  	unsigned int cpuset_mems_cookie;
> +	nodemask_t nmask = node_states[N_MEMORY];

This will allocate a large bitmask on the stack and that is no-go for
something that might be called from a potentially deep call stack
already. Also are you sure that the micro-optimization offsets the
copying overhead?

-- 
Michal Hocko
SUSE Labs

Re: [PATCH] mm/slub: skip node in case there is no slab to acquire

[Wei Yang]

On Tue, Nov 13, 2018 at 02:17:51PM +0100, Michal Hocko wrote:
>On Thu 08-11-18 09:12:04, Wei Yang wrote:
>> for_each_zone_zonelist() iterates the zonelist one by one, which means
>> it will iterate on zones on the same node. While get_partial_node()
>> checks available slab on node base instead of zone.
>> 
>> This patch skip a node in case get_partial_node() fails to acquire slab
>> on that node.
>
>If this is an optimization then it should be accompanied by some
>numbers.

Let me try to get some test result.

Do you have some suggestion on the test suite? Is kernel build a proper
test?

>
>> @@ -1882,6 +1882,9 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
>>  	enum zone_type high_zoneidx = gfp_zone(flags);
>>  	void *object;
>>  	unsigned int cpuset_mems_cookie;
>> +	nodemask_t nmask = node_states[N_MEMORY];
>
>This will allocate a large bitmask on the stack and that is no-go for
>something that might be called from a potentially deep call stack
>already. Also are you sure that the micro-optimization offsets the
>copying overhead?
>

You are right. I didn't pay attention to this.

I got one other idea to achieve this effect, like the one in
get_page_from_freelist().

In get_page_from_freelist(), we use last_pgdat_dirty_limit to track the
last node out of dirty limit. I am willing to borrow this idea in
get_any_partial() to skip a node.

Well, let me do some tests to see whether this is visible.

>-- 
>Michal Hocko
>SUSE Labs

-- 
Wei Yang
Help you, Help me

Re: [PATCH] mm/slub: skip node in case there is no slab to acquire

[Michal Hocko]

On Tue 13-11-18 13:26:24, Wei Yang wrote:
> On Tue, Nov 13, 2018 at 02:17:51PM +0100, Michal Hocko wrote:
> >On Thu 08-11-18 09:12:04, Wei Yang wrote:
> >> for_each_zone_zonelist() iterates the zonelist one by one, which means
> >> it will iterate on zones on the same node. While get_partial_node()
> >> checks available slab on node base instead of zone.
> >> 
> >> This patch skip a node in case get_partial_node() fails to acquire slab
> >> on that node.
> >
> >If this is an optimization then it should be accompanied by some
> >numbers.
> 
> Let me try to get some test result.
> 
> Do you have some suggestion on the test suite? Is kernel build a proper
> test?

Make sure that the workload is hitting hard on this particular code path
that it matters. I am not aware of any such workload but others might
know better.

In any case, if you are up to optimize something then you should
evaluate what kind of workload might benefit from it. If there is no
workload then it is likely not worth bothering. Some changes might look
like obvious improvements but then they might add a maintenance burden
or they might be even wrong for other reasons. Recent patches you have
posted show both issues.

I would encourage you to look at a practical issues instead. Throwing
random patches by reading the code without having a larger picture is
usually not the best way to go.

[...]

> In get_page_from_freelist(), we use last_pgdat_dirty_limit to track the
> last node out of dirty limit. I am willing to borrow this idea in
> get_any_partial() to skip a node.
> 
> Well, let me do some tests to see whether this is visible.

See the above. Each and every change has its cost and patches make sense
only when both the future maintenance cost and the review cost are payed
off.
-- 
Michal Hocko
SUSE Labs

[PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Wei Yang]

1. Background

  Current slub has three layers:

    * cpu_slab
    * percpu_partial
    * per node partial list

  Slub allocator tries to get an object from top to bottom. When it can't
  get an object from the upper two layers, it will search the per node
  partial list. The is done in get_partial().

  The abstraction of get_partial() may looks like this:

      get_partial()
          get_partial_node()
          get_any_partial()
              for_each_zone_zonelist()

  The idea behind this is: it first try a local node, then try other nodes
  if caller doesn't specify a node.

2. Room for Improvement

  When we look one step deeper in get_any_partial(), it tries to get a
  proper node by for_each_zone_zonelist(), which iterates on the
  node_zonelists.

  This behavior would introduce some redundant check on the same node.
  Because:

    * the local node is already checked in get_partial_node()
    * one node may have several zones on node_zonelists

3. Solution Proposed in Patch

  We could reduce these redundant check by record the last unsuccessful
  node and then skip it.

4. Tests & Result

  After some tests, the result shows this may improve the system a little,
  especially on a machine with only one node.

4.1 Test Description

  There are two cases for two system configurations.

  Test Cases:

    1. counter comparison
    2. kernel build test

  System Configuration:

    1. One node machine with 4G
    2. Four node machine with 8G

4.2 Result for Test 1

  Test 1: counter comparison

  This is a test with hacked kernel to record times function
  get_any_partial() is invoked and times the inner loop iterates. By
  comparing the ratio of two counters, we get to know how many inner
  loops we skipped.

  Here is a snip of the test patch.

  ---
  static void *get_any_partial() {

	get_partial_count++;

        do {
		for_each_zone_zonelist() {
			get_partial_try_count++;
		}
	} while();

	return NULL;
  }
  ---

  The result of (get_partial_count / get_partial_try_count):

   +----------+----------------+------------+-------------+
   |          |       Base     |    Patched |  Improvement|
   +----------+----------------+------------+-------------+
   |One Node  |       1:3      |    1:0     |      - 100% |
   +----------+----------------+------------+-------------+
   |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
   +----------+----------------+------------+-------------+

4.3 Result for Test 2

  Test 2: kernel build

   Command used:

   > time make -j8 bzImage

   Each version/system configuration combination has four round kernel
   build tests. Take the average result of real to compare.

   +----------+----------------+------------+-------------+
   |          |       Base     |   Patched  |  Improvement|
   +----------+----------------+------------+-------------+
   |One Node  |      4m41s     |   4m32s    |     - 4.47% |
   +----------+----------------+------------+-------------+
   |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
   +----------+----------------+------------+-------------+

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>

---
v3:
  * replace nmask with except to reduce potential stack overflow and copy
    overhead
  * test this in two cases and two system configurations and list the result

v2:
  * rewrite the changelog and add a comment based on Andrew's comment

---
 mm/slub.c | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index e3629cd7aff1..3d93a07d86d9 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1873,7 +1873,7 @@ static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
  * Get a page from somewhere. Search in increasing NUMA distances.
  */
 static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
-		struct kmem_cache_cpu *c)
+		struct kmem_cache_cpu *c, int except)
 {
 #ifdef CONFIG_NUMA
 	struct zonelist *zonelist;
@@ -1911,6 +1911,9 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
 			struct kmem_cache_node *n;
 
+			if (except == zone_to_nid(zone))
+				continue;
+
 			n = get_node(s, zone_to_nid(zone));
 
 			if (n && cpuset_zone_allowed(zone, flags) &&
@@ -1927,6 +1930,13 @@ static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
 					return object;
 				}
 			}
+			/*
+			 * Fail to get object from this node, either because
+			 *   1. Fails in if check
+			 *   2. NULl object returns from get_partial_node()
+			 * Skip it next time.
+			 */
+			except = zone_to_nid(zone);
 		}
 	} while (read_mems_allowed_retry(cpuset_mems_cookie));
 #endif
@@ -1951,7 +1961,7 @@ static void *get_partial(struct kmem_cache *s, gfp_t flags, int node,
 	if (object || node != NUMA_NO_NODE)
 		return object;
 
-	return get_any_partial(s, flags, c);
+	return get_any_partial(s, flags, c, searchnode);
 }
 
 #ifdef CONFIG_PREEMPT
-- 
2.15.1

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Andrew Morton]

On Tue, 20 Nov 2018 11:31:19 +0800 Wei Yang <richard.weiyang@gmail.com> wrote:

> 1. Background
> 
>   Current slub has three layers:
> 
>     * cpu_slab
>     * percpu_partial
>     * per node partial list
> 
>   Slub allocator tries to get an object from top to bottom. When it can't
>   get an object from the upper two layers, it will search the per node
>   partial list. The is done in get_partial().
> 
>   The abstraction of get_partial() may looks like this:
> 
>       get_partial()
>           get_partial_node()
>           get_any_partial()
>               for_each_zone_zonelist()
> 
>   The idea behind this is: it first try a local node, then try other nodes
>   if caller doesn't specify a node.
> 
> 2. Room for Improvement
> 
>   When we look one step deeper in get_any_partial(), it tries to get a
>   proper node by for_each_zone_zonelist(), which iterates on the
>   node_zonelists.
> 
>   This behavior would introduce some redundant check on the same node.
>   Because:
> 
>     * the local node is already checked in get_partial_node()
>     * one node may have several zones on node_zonelists
> 
> 3. Solution Proposed in Patch
> 
>   We could reduce these redundant check by record the last unsuccessful
>   node and then skip it.
> 
> 4. Tests & Result
> 
>   After some tests, the result shows this may improve the system a little,
>   especially on a machine with only one node.
> 
> 4.1 Test Description
> 
>   There are two cases for two system configurations.
> 
>   Test Cases:
> 
>     1. counter comparison
>     2. kernel build test
> 
>   System Configuration:
> 
>     1. One node machine with 4G
>     2. Four node machine with 8G
> 
> 4.2 Result for Test 1
> 
>   Test 1: counter comparison
> 
>   This is a test with hacked kernel to record times function
>   get_any_partial() is invoked and times the inner loop iterates. By
>   comparing the ratio of two counters, we get to know how many inner
>   loops we skipped.
> 
>   Here is a snip of the test patch.
> 
>   ---
>   static void *get_any_partial() {
> 
> 	get_partial_count++;
> 
>         do {
> 		for_each_zone_zonelist() {
> 			get_partial_try_count++;
> 		}
> 	} while();
> 
> 	return NULL;
>   }
>   ---
> 
>   The result of (get_partial_count / get_partial_try_count):
> 
>    +----------+----------------+------------+-------------+
>    |          |       Base     |    Patched |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |       1:3      |    1:0     |      - 100% |
>    +----------+----------------+------------+-------------+
>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>    +----------+----------------+------------+-------------+
> 
> 4.3 Result for Test 2
> 
>   Test 2: kernel build
> 
>    Command used:
> 
>    > time make -j8 bzImage
> 
>    Each version/system configuration combination has four round kernel
>    build tests. Take the average result of real to compare.
> 
>    +----------+----------------+------------+-------------+
>    |          |       Base     |   Patched  |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>    +----------+----------------+------------+-------------+
>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>    +----------+----------------+------------+-------------+
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> 

Looks good to me, but I'll await input from the slab maintainers before
proceeding any further.

I didn't like the variable name much, and the comment could be
improved.  Please review:


--- a/mm/slub.c~mm-slub-improve-performance-by-skipping-checked-node-in-get_any_partial-fix
+++ a/mm/slub.c
@@ -1873,7 +1873,7 @@ static void *get_partial_node(struct kme
  * Get a page from somewhere. Search in increasing NUMA distances.
  */
 static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
-		struct kmem_cache_cpu *c, int except)
+		struct kmem_cache_cpu *c, int exclude_nid)
 {
 #ifdef CONFIG_NUMA
 	struct zonelist *zonelist;
@@ -1911,7 +1911,7 @@ static void *get_any_partial(struct kmem
 		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
 			struct kmem_cache_node *n;
 
-			if (except == zone_to_nid(zone))
+			if (exclude_nid == zone_to_nid(zone))
 				continue;
 
 			n = get_node(s, zone_to_nid(zone));
@@ -1931,12 +1931,13 @@ static void *get_any_partial(struct kmem
 				}
 			}
 			/*
-			 * Fail to get object from this node, either because
-			 *   1. Fails in if check
-			 *   2. NULl object returns from get_partial_node()
-			 * Skip it next time.
+			 * Failed to get an object from this node, either 
+			 * because
+			 *   1. Failure in the above if check
+			 *   2. NULL return from get_partial_node()
+			 * So skip this node next time.
 			 */
-			except = zone_to_nid(zone);
+			exclude_nid = zone_to_nid(zone);
 		}
 	} while (read_mems_allowed_retry(cpuset_mems_cookie));
 #endif
_

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Wei Yang]

On Wed, Nov 21, 2018 at 07:05:55PM -0800, Andrew Morton wrote:
>On Tue, 20 Nov 2018 11:31:19 +0800 Wei Yang <richard.weiyang@gmail.com> wrote:
>
>> 1. Background
>> 
>>   Current slub has three layers:
>> 
>>     * cpu_slab
>>     * percpu_partial
>>     * per node partial list
>> 
>>   Slub allocator tries to get an object from top to bottom. When it can't
>>   get an object from the upper two layers, it will search the per node
>>   partial list. The is done in get_partial().
>> 
>>   The abstraction of get_partial() may looks like this:
>> 
>>       get_partial()
>>           get_partial_node()
>>           get_any_partial()
>>               for_each_zone_zonelist()
>> 
>>   The idea behind this is: it first try a local node, then try other nodes
>>   if caller doesn't specify a node.
>> 
>> 2. Room for Improvement
>> 
>>   When we look one step deeper in get_any_partial(), it tries to get a
>>   proper node by for_each_zone_zonelist(), which iterates on the
>>   node_zonelists.
>> 
>>   This behavior would introduce some redundant check on the same node.
>>   Because:
>> 
>>     * the local node is already checked in get_partial_node()
>>     * one node may have several zones on node_zonelists
>> 
>> 3. Solution Proposed in Patch
>> 
>>   We could reduce these redundant check by record the last unsuccessful
>>   node and then skip it.
>> 
>> 4. Tests & Result
>> 
>>   After some tests, the result shows this may improve the system a little,
>>   especially on a machine with only one node.
>> 
>> 4.1 Test Description
>> 
>>   There are two cases for two system configurations.
>> 
>>   Test Cases:
>> 
>>     1. counter comparison
>>     2. kernel build test
>> 
>>   System Configuration:
>> 
>>     1. One node machine with 4G
>>     2. Four node machine with 8G
>> 
>> 4.2 Result for Test 1
>> 
>>   Test 1: counter comparison
>> 
>>   This is a test with hacked kernel to record times function
>>   get_any_partial() is invoked and times the inner loop iterates. By
>>   comparing the ratio of two counters, we get to know how many inner
>>   loops we skipped.
>> 
>>   Here is a snip of the test patch.
>> 
>>   ---
>>   static void *get_any_partial() {
>> 
>> 	get_partial_count++;
>> 
>>         do {
>> 		for_each_zone_zonelist() {
>> 			get_partial_try_count++;
>> 		}
>> 	} while();
>> 
>> 	return NULL;
>>   }
>>   ---
>> 
>>   The result of (get_partial_count / get_partial_try_count):
>> 
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |    Patched |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |       1:3      |    1:0     |      - 100% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>>    +----------+----------------+------------+-------------+
>> 
>> 4.3 Result for Test 2
>> 
>>   Test 2: kernel build
>> 
>>    Command used:
>> 
>>    > time make -j8 bzImage
>> 
>>    Each version/system configuration combination has four round kernel
>>    build tests. Take the average result of real to compare.
>> 
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |   Patched  |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>>    +----------+----------------+------------+-------------+
>> 
>> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> 
>
>Looks good to me, but I'll await input from the slab maintainers before
>proceeding any further.
>
>I didn't like the variable name much, and the comment could be
>improved.  Please review:
>

Looks much better, thanks :-)

>
>--- a/mm/slub.c~mm-slub-improve-performance-by-skipping-checked-node-in-get_any_partial-fix
>+++ a/mm/slub.c
>@@ -1873,7 +1873,7 @@ static void *get_partial_node(struct kme
>  * Get a page from somewhere. Search in increasing NUMA distances.
>  */
> static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
>-		struct kmem_cache_cpu *c, int except)
>+		struct kmem_cache_cpu *c, int exclude_nid)
> {
> #ifdef CONFIG_NUMA
> 	struct zonelist *zonelist;
>@@ -1911,7 +1911,7 @@ static void *get_any_partial(struct kmem
> 		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
> 			struct kmem_cache_node *n;
> 
>-			if (except == zone_to_nid(zone))
>+			if (exclude_nid == zone_to_nid(zone))
> 				continue;
> 
> 			n = get_node(s, zone_to_nid(zone));
>@@ -1931,12 +1931,13 @@ static void *get_any_partial(struct kmem
> 				}
> 			}
> 			/*
>-			 * Fail to get object from this node, either because
>-			 *   1. Fails in if check
>-			 *   2. NULl object returns from get_partial_node()
>-			 * Skip it next time.
>+			 * Failed to get an object from this node, either 
>+			 * because
>+			 *   1. Failure in the above if check
>+			 *   2. NULL return from get_partial_node()
>+			 * So skip this node next time.
> 			 */
>-			except = zone_to_nid(zone);
>+			exclude_nid = zone_to_nid(zone);
> 		}
> 	} while (read_mems_allowed_retry(cpuset_mems_cookie));
> #endif
>_

-- 
Wei Yang
Help you, Help me

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Wei Yang]

On Wed, Nov 21, 2018 at 07:05:55PM -0800, Andrew Morton wrote:
>On Tue, 20 Nov 2018 11:31:19 +0800 Wei Yang <richard.weiyang@gmail.com> wrote:
>
>> 1. Background
>> 
>>   Current slub has three layers:
>> 
>>     * cpu_slab
>>     * percpu_partial
>>     * per node partial list
>> 
>>   Slub allocator tries to get an object from top to bottom. When it can't
>>   get an object from the upper two layers, it will search the per node
>>   partial list. The is done in get_partial().
>> 
>>   The abstraction of get_partial() may looks like this:
>> 
>>       get_partial()
>>           get_partial_node()
>>           get_any_partial()
>>               for_each_zone_zonelist()
>> 
>>   The idea behind this is: it first try a local node, then try other nodes
>>   if caller doesn't specify a node.
>> 
>> 2. Room for Improvement
>> 
>>   When we look one step deeper in get_any_partial(), it tries to get a
>>   proper node by for_each_zone_zonelist(), which iterates on the
>>   node_zonelists.
>> 
>>   This behavior would introduce some redundant check on the same node.
>>   Because:
>> 
>>     * the local node is already checked in get_partial_node()
>>     * one node may have several zones on node_zonelists
>> 
>> 3. Solution Proposed in Patch
>> 
>>   We could reduce these redundant check by record the last unsuccessful
>>   node and then skip it.
>> 
>> 4. Tests & Result
>> 
>>   After some tests, the result shows this may improve the system a little,
>>   especially on a machine with only one node.
>> 
>> 4.1 Test Description
>> 
>>   There are two cases for two system configurations.
>> 
>>   Test Cases:
>> 
>>     1. counter comparison
>>     2. kernel build test
>> 
>>   System Configuration:
>> 
>>     1. One node machine with 4G
>>     2. Four node machine with 8G
>> 
>> 4.2 Result for Test 1
>> 
>>   Test 1: counter comparison
>> 
>>   This is a test with hacked kernel to record times function
>>   get_any_partial() is invoked and times the inner loop iterates. By
>>   comparing the ratio of two counters, we get to know how many inner
>>   loops we skipped.
>> 
>>   Here is a snip of the test patch.
>> 
>>   ---
>>   static void *get_any_partial() {
>> 
>> 	get_partial_count++;
>> 
>>         do {
>> 		for_each_zone_zonelist() {
>> 			get_partial_try_count++;
>> 		}
>> 	} while();
>> 
>> 	return NULL;
>>   }
>>   ---
>> 
>>   The result of (get_partial_count / get_partial_try_count):
>> 
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |    Patched |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |       1:3      |    1:0     |      - 100% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>>    +----------+----------------+------------+-------------+
>> 
>> 4.3 Result for Test 2
>> 
>>   Test 2: kernel build
>> 
>>    Command used:
>> 
>>    > time make -j8 bzImage
>> 
>>    Each version/system configuration combination has four round kernel
>>    build tests. Take the average result of real to compare.
>> 
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |   Patched  |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>>    +----------+----------------+------------+-------------+
>> 
>> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> 
>
>Looks good to me, but I'll await input from the slab maintainers before
>proceeding any further.
>
>I didn't like the variable name much, and the comment could be
>improved.  Please review:
>

Can I add this?

Reviewed-by: Wei Yang <richard.weiyang@gmail.com>


-- 
Wei Yang
Help you, Help me

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Michal Hocko]

On Thu 22-11-18 23:41:59, Wei Yang wrote:
> On Wed, Nov 21, 2018 at 07:05:55PM -0800, Andrew Morton wrote:
[...]
> >> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> 
> Reviewed-by: Wei Yang <richard.weiyang@gmail.com>

Why would you want to add reviewed tag to your own patch? Isn't the
s-o-b a sufficient sign of you being and author of the patch and
therefore the one who has reviewed the change before asking for merging?

Btw. Documentation/SubmittingPatches might come handy to understand the
process some more. Feel free to ask if there is something unclear.
-- 
Michal Hocko
SUSE Labs

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Michal Hocko]

On Fri 23-11-18 14:39:02, Michal Hocko wrote:
> On Thu 22-11-18 23:41:59, Wei Yang wrote:
> > On Wed, Nov 21, 2018 at 07:05:55PM -0800, Andrew Morton wrote:
> [...]
> > >> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> > 
> > Reviewed-by: Wei Yang <richard.weiyang@gmail.com>
> 
> Why would you want to add reviewed tag to your own patch? Isn't the
> s-o-b a sufficient sign of you being and author of the patch and
> therefore the one who has reviewed the change before asking for merging?

OK, it seems I've misunderstood. Did you mean Reviewed-by to the follow
up fixes by Andrew? If yes then sorry about my response. I do not want
to speak for Andrew but he usually just wants a "looks good" and will
eventually fold his changes into the original patch.
-- 
Michal Hocko
SUSE Labs

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Wei Yang]

On Fri, Nov 23, 2018 at 02:49:24PM +0100, Michal Hocko wrote:
>On Fri 23-11-18 14:39:02, Michal Hocko wrote:
>> On Thu 22-11-18 23:41:59, Wei Yang wrote:
>> > On Wed, Nov 21, 2018 at 07:05:55PM -0800, Andrew Morton wrote:
>> [...]
>> > >> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> > 
>> > Reviewed-by: Wei Yang <richard.weiyang@gmail.com>
>> 
>> Why would you want to add reviewed tag to your own patch? Isn't the
>> s-o-b a sufficient sign of you being and author of the patch and
>> therefore the one who has reviewed the change before asking for merging?
>
>OK, it seems I've misunderstood. Did you mean Reviewed-by to the follow
>up fixes by Andrew? If yes then sorry about my response. I do not want
>to speak for Andrew but he usually just wants a "looks good" and will
>eventually fold his changes into the original patch.

Yes, Reviewed-by is for Andrew's fix.

>-- 
>Michal Hocko
>SUSE Labs

-- 
Wei Yang
Help you, Help me

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Andrew Morton]

Could someone please review this?

Thanks.

From: Wei Yang <richard.weiyang@gmail.com>
Subject: mm/slub.c: improve performance by skipping checked node in get_any_partial()

1. Background

  Current slub has three layers:

    * cpu_slab
    * percpu_partial
    * per node partial list

  Slub allocator tries to get an object from top to bottom.  When it
  can't get an object from the upper two layers, it will search the per
  node partial list.  The is done in get_partial().

  The abstraction of get_partial() look like this:

      get_partial()
          get_partial_node()
          get_any_partial()
              for_each_zone_zonelist()

  The idea behind this is: first try a local node, then try other nodes
  if caller doesn't specify a node.

2. Room for Improvement

  When we look one step deeper in get_any_partial(), it tries to get a
  proper node by for_each_zone_zonelist(), which iterates on the
  node_zonelists.

  This behavior would introduce some redundant check on the same node. 
  Because:

    * the local node is already checked in get_partial_node()
    * one node may have several zones on node_zonelists

3. Solution Proposed in Patch

  We could reduce these redundant check by record the last unsuccessful
  node and then skip it.

4. Tests & Result

  After some tests, the result shows this may improve the system a little,
  especially on a machine with only one node.

4.1 Test Description

  There are two cases for two system configurations.

  Test Cases:

    1. counter comparison
    2. kernel build test

  System Configuration:

    1. One node machine with 4G
    2. Four node machine with 8G

4.2 Result for Test 1

  Test 1: counter comparison

  This is a test with hacked kernel to record times function
  get_any_partial() is invoked and times the inner loop iterates. By
  comparing the ratio of two counters, we get to know how many inner
  loops we skipped.

  Here is a snip of the test patch.

  ---
  static void *get_any_partial() {

	get_partial_count++;

        do {
		for_each_zone_zonelist() {
			get_partial_try_count++;
		}
	} while();

	return NULL;
  }
  ---

  The result of (get_partial_count / get_partial_try_count):

   +----------+----------------+------------+-------------+
   |          |       Base     |    Patched |  Improvement|
   +----------+----------------+------------+-------------+
   |One Node  |       1:3      |    1:0     |      - 100% |
   +----------+----------------+------------+-------------+
   |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
   +----------+----------------+------------+-------------+

4.3 Result for Test 2

  Test 2: kernel build

   Command used:

   > time make -j8 bzImage

   Each version/system configuration combination has four round kernel
   build tests. Take the average result of real to compare.

   +----------+----------------+------------+-------------+
   |          |       Base     |   Patched  |  Improvement|
   +----------+----------------+------------+-------------+
   |One Node  |      4m41s     |   4m32s    |     - 4.47% |
   +----------+----------------+------------+-------------+
   |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
   +----------+----------------+------------+-------------+

[akpm@linux-foundation.org: rename variable, tweak comment]
Link: http://lkml.kernel.org/r/20181120033119.30013-1-richard.weiyang@gmail.com
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Christoph Lameter <cl@linux.com>
Cc: Pekka Enberg <penberg@kernel.org>
Cc: David Rientjes <rientjes@google.com>
Cc: Joonsoo Kim <iamjoonsoo.kim@lge.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 mm/slub.c |   15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

--- a/mm/slub.c~mm-slub-improve-performance-by-skipping-checked-node-in-get_any_partial
+++ a/mm/slub.c
@@ -1877,7 +1877,7 @@ static void *get_partial_node(struct kme
  * Get a page from somewhere. Search in increasing NUMA distances.
  */
 static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
-		struct kmem_cache_cpu *c)
+		struct kmem_cache_cpu *c, int exclude_nid)
 {
 #ifdef CONFIG_NUMA
 	struct zonelist *zonelist;
@@ -1915,6 +1915,9 @@ static void *get_any_partial(struct kmem
 		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
 			struct kmem_cache_node *n;
 
+			if (exclude_nid == zone_to_nid(zone))
+				continue;
+
 			n = get_node(s, zone_to_nid(zone));
 
 			if (n && cpuset_zone_allowed(zone, flags) &&
@@ -1931,6 +1934,14 @@ static void *get_any_partial(struct kmem
 					return object;
 				}
 			}
+			/*
+			 * Failed to get an object from this node, either
+			 * because
+			 *   1. Failure in the above if check
+			 *   2. NULL return from get_partial_node()
+			 * So skip this node next time.
+			 */
+			exclude_nid = zone_to_nid(zone);
 		}
 	} while (read_mems_allowed_retry(cpuset_mems_cookie));
 #endif
@@ -1955,7 +1966,7 @@ static void *get_partial(struct kmem_cac
 	if (object || node != NUMA_NO_NODE)
 		return object;
 
-	return get_any_partial(s, flags, c);
+	return get_any_partial(s, flags, c, searchnode);
 }
 
 #ifdef CONFIG_PREEMPT
_

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Alexander Duyck]

On Thu, 2018-12-20 at 14:41 -0800, Andrew Morton wrote:
> Could someone please review this?
> 
> Thanks.
> 
> From: Wei Yang <richard.weiyang@gmail.com>
> Subject: mm/slub.c: improve performance by skipping checked node in get_any_partial()
> 
> 1. Background
> 
>   Current slub has three layers:
> 
>     * cpu_slab
>     * percpu_partial
>     * per node partial list
> 
>   Slub allocator tries to get an object from top to bottom.  When it
>   can't get an object from the upper two layers, it will search the per
>   node partial list.  The is done in get_partial().
> 
>   The abstraction of get_partial() look like this:
> 
>       get_partial()
>           get_partial_node()
>           get_any_partial()
>               for_each_zone_zonelist()
> 
>   The idea behind this is: first try a local node, then try other nodes
>   if caller doesn't specify a node.
> 
> 2. Room for Improvement
> 
>   When we look one step deeper in get_any_partial(), it tries to get a
>   proper node by for_each_zone_zonelist(), which iterates on the
>   node_zonelists.
> 
>   This behavior would introduce some redundant check on the same node. 
>   Because:
> 
>     * the local node is already checked in get_partial_node()
>     * one node may have several zones on node_zonelists
> 

So it seems like there can be a few different behaviors based on
mempolicy_slab_node() being used to construct the zonelist. Do you
happen to know what memory policy your test process was running under?
Also have you tried using any of the other policies to gather data?

> 3. Solution Proposed in Patch
> 
>   We could reduce these redundant check by record the last unsuccessful
>   node and then skip it.
> 
> 4. Tests & Result
> 
>   After some tests, the result shows this may improve the system a little,
>   especially on a machine with only one node.
> 
> 4.1 Test Description
> 
>   There are two cases for two system configurations.
> 
>   Test Cases:
> 
>     1. counter comparison
>     2. kernel build test
> 
>   System Configuration:
> 
>     1. One node machine with 4G
>     2. Four node machine with 8G
> 
> 4.2 Result for Test 1
> 
>   Test 1: counter comparison
> 
>   This is a test with hacked kernel to record times function
>   get_any_partial() is invoked and times the inner loop iterates. By
>   comparing the ratio of two counters, we get to know how many inner
>   loops we skipped.
> 
>   Here is a snip of the test patch.
> 
>   ---
>   static void *get_any_partial() {
> 
> 	get_partial_count++;
> 
>         do {
> 		for_each_zone_zonelist() {
> 			get_partial_try_count++;
> 		}
> 	} while();
> 
> 	return NULL;
>   }
>   ---
> 
>   The result of (get_partial_count / get_partial_try_count):
> 
>    +----------+----------------+------------+-------------+
>    |          |       Base     |    Patched |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |       1:3      |    1:0     |      - 100% |
>    +----------+----------------+------------+-------------+
>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>    +----------+----------------+------------+-------------+
> 
> 4.3 Result for Test 2
> 
>   Test 2: kernel build
> 
>    Command used:
> 
>    > time make -j8 bzImage
> 
>    Each version/system configuration combination has four round kernel
>    build tests. Take the average result of real to compare.
> 
>    +----------+----------------+------------+-------------+
>    |          |       Base     |   Patched  |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>    +----------+----------------+------------+-------------+
>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>    +----------+----------------+------------+-------------+
> 
> [akpm@linux-foundation.org: rename variable, tweak comment]
> Link: http://lkml.kernel.org/r/20181120033119.30013-1-richard.weiyang@gmail.com
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> Cc: Christoph Lameter <cl@linux.com>
> Cc: Pekka Enberg <penberg@kernel.org>
> Cc: David Rientjes <rientjes@google.com>
> Cc: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> ---
> 
>  mm/slub.c |   15 +++++++++++++--
>  1 file changed, 13 insertions(+), 2 deletions(-)
> 
> --- a/mm/slub.c~mm-slub-improve-performance-by-skipping-checked-node-in-get_any_partial
> +++ a/mm/slub.c
> @@ -1877,7 +1877,7 @@ static void *get_partial_node(struct kme
>   * Get a page from somewhere. Search in increasing NUMA distances.
>   */
>  static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
> -		struct kmem_cache_cpu *c)
> +		struct kmem_cache_cpu *c, int exclude_nid)
>  {
>  #ifdef CONFIG_NUMA
>  	struct zonelist *zonelist;
> @@ -1915,6 +1915,9 @@ static void *get_any_partial(struct kmem
>  		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
>  			struct kmem_cache_node *n;
>  
> +			if (exclude_nid == zone_to_nid(zone))
> +				continue;
> +
>  			n = get_node(s, zone_to_nid(zone));
>  
>  			if (n && cpuset_zone_allowed(zone, flags) &&
> @@ -1931,6 +1934,14 @@ static void *get_any_partial(struct kmem
>  					return object;
>  				}
>  			}
> +			/*
> +			 * Failed to get an object from this node, either
> +			 * because
> +			 *   1. Failure in the above if check
> +			 *   2. NULL return from get_partial_node()
> +			 * So skip this node next time.
> +			 */
> +			exclude_nid = zone_to_nid(zone);
>  		}
>  	} while (read_mems_allowed_retry(cpuset_mems_cookie));
>  #endif

So this piece gives me some concerns. You are updating the exclude_nid,
but as a result you are no longer excluding your original nid. So it
becomes possible that you are going to go back and search your original
exlcude_nid on the next pass if the zones are interleaved between nodes
aren't you?

Would it perhaps make more sense to instead replace
for_each_zone_zonelist with for_each_zone_zonelist_nodemask and then
just mask out any of the failing nodes?

> @@ -1955,7 +1966,7 @@ static void *get_partial(struct kmem_cac
>  	if (object || node != NUMA_NO_NODE)
>  		return object;
>  
> -	return get_any_partial(s, flags, c);
> +	return get_any_partial(s, flags, c, searchnode);
>  }
>  
>  #ifdef CONFIG_PREEMPT
> _
> 

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Wei Yang]

On Thu, Dec 20, 2018 at 04:25:55PM -0800, Alexander Duyck wrote:
>On Thu, 2018-12-20 at 14:41 -0800, Andrew Morton wrote:
>> Could someone please review this?
>> 
>> Thanks.
>> 
>> From: Wei Yang <richard.weiyang@gmail.com>
>> Subject: mm/slub.c: improve performance by skipping checked node in get_any_partial()
>> 
>> 1. Background
>> 
>>   Current slub has three layers:
>> 
>>     * cpu_slab
>>     * percpu_partial
>>     * per node partial list
>> 
>>   Slub allocator tries to get an object from top to bottom.  When it
>>   can't get an object from the upper two layers, it will search the per
>>   node partial list.  The is done in get_partial().
>> 
>>   The abstraction of get_partial() look like this:
>> 
>>       get_partial()
>>           get_partial_node()
>>           get_any_partial()
>>               for_each_zone_zonelist()
>> 
>>   The idea behind this is: first try a local node, then try other nodes
>>   if caller doesn't specify a node.
>> 
>> 2. Room for Improvement
>> 
>>   When we look one step deeper in get_any_partial(), it tries to get a
>>   proper node by for_each_zone_zonelist(), which iterates on the
>>   node_zonelists.
>> 
>>   This behavior would introduce some redundant check on the same node. 
>>   Because:
>> 
>>     * the local node is already checked in get_partial_node()
>>     * one node may have several zones on node_zonelists
>> 
>
>So it seems like there can be a few different behaviors based on
>mempolicy_slab_node() being used to construct the zonelist. Do you
>happen to know what memory policy your test process was running under?
>Also have you tried using any of the other policies to gather data?
>

I have little knowledge about the mempolicy so the test is based on a
"default" configuration.


>> 3. Solution Proposed in Patch
>> 
>>   We could reduce these redundant check by record the last unsuccessful
>>   node and then skip it.
>> 
>> 4. Tests & Result
>> 
>>   After some tests, the result shows this may improve the system a little,
>>   especially on a machine with only one node.
>> 
>> 4.1 Test Description
>> 
>>   There are two cases for two system configurations.
>> 
>>   Test Cases:
>> 
>>     1. counter comparison
>>     2. kernel build test
>> 
>>   System Configuration:
>> 
>>     1. One node machine with 4G
>>     2. Four node machine with 8G
>> 
>> 4.2 Result for Test 1
>> 
>>   Test 1: counter comparison
>> 
>>   This is a test with hacked kernel to record times function
>>   get_any_partial() is invoked and times the inner loop iterates. By
>>   comparing the ratio of two counters, we get to know how many inner
>>   loops we skipped.
>> 
>>   Here is a snip of the test patch.
>> 
>>   ---
>>   static void *get_any_partial() {
>> 
>> 	get_partial_count++;
>> 
>>         do {
>> 		for_each_zone_zonelist() {
>> 			get_partial_try_count++;
>> 		}
>> 	} while();
>> 
>> 	return NULL;
>>   }
>>   ---
>> 
>>   The result of (get_partial_count / get_partial_try_count):
>> 
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |    Patched |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |       1:3      |    1:0     |      - 100% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>>    +----------+----------------+------------+-------------+
>> 
>> 4.3 Result for Test 2
>> 
>>   Test 2: kernel build
>> 
>>    Command used:
>> 
>>    > time make -j8 bzImage
>> 
>>    Each version/system configuration combination has four round kernel
>>    build tests. Take the average result of real to compare.
>> 
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |   Patched  |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>>    +----------+----------------+------------+-------------+
>> 
>> [akpm@linux-foundation.org: rename variable, tweak comment]
>> Link: http://lkml.kernel.org/r/20181120033119.30013-1-richard.weiyang@gmail.com
>> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> Cc: Christoph Lameter <cl@linux.com>
>> Cc: Pekka Enberg <penberg@kernel.org>
>> Cc: David Rientjes <rientjes@google.com>
>> Cc: Joonsoo Kim <iamjoonsoo.kim@lge.com>
>> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
>> ---
>> 
>>  mm/slub.c |   15 +++++++++++++--
>>  1 file changed, 13 insertions(+), 2 deletions(-)
>> 
>> --- a/mm/slub.c~mm-slub-improve-performance-by-skipping-checked-node-in-get_any_partial
>> +++ a/mm/slub.c
>> @@ -1877,7 +1877,7 @@ static void *get_partial_node(struct kme
>>   * Get a page from somewhere. Search in increasing NUMA distances.
>>   */
>>  static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
>> -		struct kmem_cache_cpu *c)
>> +		struct kmem_cache_cpu *c, int exclude_nid)
>>  {
>>  #ifdef CONFIG_NUMA
>>  	struct zonelist *zonelist;
>> @@ -1915,6 +1915,9 @@ static void *get_any_partial(struct kmem
>>  		for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
>>  			struct kmem_cache_node *n;
>>  
>> +			if (exclude_nid == zone_to_nid(zone))
>> +				continue;
>> +
>>  			n = get_node(s, zone_to_nid(zone));
>>  
>>  			if (n && cpuset_zone_allowed(zone, flags) &&
>> @@ -1931,6 +1934,14 @@ static void *get_any_partial(struct kmem
>>  					return object;
>>  				}
>>  			}
>> +			/*
>> +			 * Failed to get an object from this node, either
>> +			 * because
>> +			 *   1. Failure in the above if check
>> +			 *   2. NULL return from get_partial_node()
>> +			 * So skip this node next time.
>> +			 */
>> +			exclude_nid = zone_to_nid(zone);
>>  		}
>>  	} while (read_mems_allowed_retry(cpuset_mems_cookie));
>>  #endif
>
>So this piece gives me some concerns. You are updating the exclude_nid,
>but as a result you are no longer excluding your original nid. So it
>becomes possible that you are going to go back and search your original
>exlcude_nid on the next pass if the zones are interleaved between nodes
>aren't you?

After Michal's change, current zonelist just have node order.

This means once we have a exclude_nid, we will skip all zones on this
node.

>
>Would it perhaps make more sense to instead replace
>for_each_zone_zonelist with for_each_zone_zonelist_nodemask and then
>just mask out any of the failing nodes?

My first version is implemented in this way. While Michal mentioned it
would be heavy on stack and took much time to copy nodemask_t.

>
>> @@ -1955,7 +1966,7 @@ static void *get_partial(struct kmem_cac
>>  	if (object || node != NUMA_NO_NODE)
>>  		return object;
>>  
>> -	return get_any_partial(s, flags, c);
>> +	return get_any_partial(s, flags, c, searchnode);
>>  }
>>  
>>  #ifdef CONFIG_PREEMPT
>> _
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Christopher Lameter]

On Thu, 20 Dec 2018, Andrew Morton wrote:

>   The result of (get_partial_count / get_partial_try_count):
>
>    +----------+----------------+------------+-------------+
>    |          |       Base     |    Patched |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |       1:3      |    1:0     |      - 100% |

If you have one node then you already searched all your slabs. So we could
completely skip the get_any_partial() functionality in the non NUMA case
(if nr_node_ids == 1)


>    +----------+----------------+------------+-------------+
>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>    +----------+----------------+------------+-------------+

Hmm.... Ok but that is the extreme slowpath.

>    Each version/system configuration combination has four round kernel
>    build tests. Take the average result of real to compare.
>
>    +----------+----------------+------------+-------------+
>    |          |       Base     |   Patched  |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>    +----------+----------------+------------+-------------+
>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>    +----------+----------------+------------+-------------+

3% on the four node case? That means that the slowpath is taken
frequently. Wonder why?

Can we also see the variability? Since this is a NUMA system there is
bound to be some indeterminism in those numbers.

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Christopher Lameter]

On Thu, 20 Dec 2018, Andrew Morton wrote:

>   The result of (get_partial_count / get_partial_try_count):
>
>    +----------+----------------+------------+-------------+
>    |          |       Base     |    Patched |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |       1:3      |    1:0     |      - 100% |

If you have one node then you already searched all your slabs. So we could
completely skip the get_any_partial() functionality in the non NUMA case
(if nr_node_ids == 1)


>    +----------+----------------+------------+-------------+
>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>    +----------+----------------+------------+-------------+

Hmm.... Ok but that is the extreme slowpath.

>    Each version/system configuration combination has four round kernel
>    build tests. Take the average result of real to compare.
>
>    +----------+----------------+------------+-------------+
>    |          |       Base     |   Patched  |  Improvement|
>    +----------+----------------+------------+-------------+
>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>    +----------+----------------+------------+-------------+
>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>    +----------+----------------+------------+-------------+

3% on the four node case? That means that the slowpath is taken
frequently. Wonder why?

Can we also see the variability? Since this is a NUMA system there is
bound to be some indeterminism in those numbers.

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Wei Yang]

On Fri, Dec 21, 2018 at 01:37:38AM +0000, Christopher Lameter wrote:
>On Thu, 20 Dec 2018, Andrew Morton wrote:
>
>>   The result of (get_partial_count / get_partial_try_count):
>>
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |    Patched |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |       1:3      |    1:0     |      - 100% |
>
>If you have one node then you already searched all your slabs. So we could
>completely skip the get_any_partial() functionality in the non NUMA case
>(if nr_node_ids == 1)
>

Yes, agree.

>
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>>    +----------+----------------+------------+-------------+
>
>Hmm.... Ok but that is the extreme slowpath.
>
>>    Each version/system configuration combination has four round kernel
>>    build tests. Take the average result of real to compare.
>>
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |   Patched  |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>>    +----------+----------------+------------+-------------+
>
>3% on the four node case? That means that the slowpath is taken
>frequently. Wonder why?

Hmm... not sure.

>
>Can we also see the variability? Since this is a NUMA system there is
>bound to be some indeterminism in those numbers.

Oops, I have deleted those raw data. I need to retest this.

-- 
Wei Yang
Help you, Help me

Re: [PATCH v2] mm/slub: improve performance by skipping checked node in get_any_partial()

[Wei Yang]

On Fri, Dec 21, 2018 at 01:37:38AM +0000, Christopher Lameter wrote:
>On Thu, 20 Dec 2018, Andrew Morton wrote:
>
>>   The result of (get_partial_count / get_partial_try_count):
>>
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |    Patched |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |       1:3      |    1:0     |      - 100% |
>
>If you have one node then you already searched all your slabs. So we could
>completely skip the get_any_partial() functionality in the non NUMA case
>(if nr_node_ids == 1)
>
>
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|       1:5.8    |    1:2.5   |      -  56% |
>>    +----------+----------------+------------+-------------+
>
>Hmm.... Ok but that is the extreme slowpath.
>
>>    Each version/system configuration combination has four round kernel
>>    build tests. Take the average result of real to compare.
>>
>>    +----------+----------------+------------+-------------+
>>    |          |       Base     |   Patched  |  Improvement|
>>    +----------+----------------+------------+-------------+
>>    |One Node  |      4m41s     |   4m32s    |     - 4.47% |
>>    +----------+----------------+------------+-------------+
>>    |Four Nodes|      4m45s     |   4m39s    |     - 2.92% |
>>    +----------+----------------+------------+-------------+
>
>3% on the four node case? That means that the slowpath is taken
>frequently. Wonder why?
>
>Can we also see the variability? Since this is a NUMA system there is
>bound to be some indeterminism in those numbers.

Hmm... I rebuilt the kernel and try the experiment again, but found I
can't reproduce this statistics. The data show it is worse than base
line and shakes heavily...

Base                    Patched 
                        
real    5m49.652s       real    8m9.515s
user    19m0.581s       user    17m30.296s
sys     2m31.906s       sys     2m21.445s
                        
real    5m47.145s       real    6m47.437s
user    19m17.445s      user    18m33.461s
sys     2m41.931s       sys     2m43.249s
                        
real    7m2.043s        real    5m38.539s
user    18m11.723s      user    19m40.552s
sys     2m46.443s       sys     2m43.771s
                        
real    5m31.797s       real    12m59.936s
user    19m13.984s      user    15m47.602s
sys     2m34.727s       sys     2m20.385s



















-- 
Wei Yang
Help you, Help me