Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

On 2016/10/14 8:33, Tejun Heo wrote:
> Hello,
> 
> On Fri, Oct 14, 2016 at 07:49:44AM +0800, zijun_hu wrote:
>> the main intent of this change is making the CPU grouping algorithm more
>> easily to understand, especially, for newcomer for memory managements
>> take me as a example, i really take me a longer timer to understand it
> 
> If the new code is easier to understand, it's only so marginally.  It
> just isn't worth the effort or risk.
> 
> Thanks.
> 
okay i agree with your opinion.
but i am sure this changes don't have any risk after tests and theoretic analyse

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

On 2016/10/14 8:33, Tejun Heo wrote:
> Hello,
> 
> On Fri, Oct 14, 2016 at 07:49:44AM +0800, zijun_hu wrote:
>> the main intent of this change is making the CPU grouping algorithm more
>> easily to understand, especially, for newcomer for memory managements
>> take me as a example, i really take me a longer timer to understand it
> 
> If the new code is easier to understand, it's only so marginally.  It
> just isn't worth the effort or risk.
> 
> Thanks.
> 
okay i agree with your opinion.
but i am sure this changes don't have any risk after tests and theoretic analyse

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[Tejun Heo]

Hello,

On Fri, Oct 14, 2016 at 07:49:44AM +0800, zijun_hu wrote:
> the main intent of this change is making the CPU grouping algorithm more
> easily to understand, especially, for newcomer for memory managements
> take me as a example, i really take me a longer timer to understand it

If the new code is easier to understand, it's only so marginally.  It
just isn't worth the effort or risk.

Thanks.

-- 
tejun

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[Tejun Heo]

Hello,

On Fri, Oct 14, 2016 at 07:49:44AM +0800, zijun_hu wrote:
> the main intent of this change is making the CPU grouping algorithm more
> easily to understand, especially, for newcomer for memory managements
> take me as a example, i really take me a longer timer to understand it

If the new code is easier to understand, it's only so marginally.  It
just isn't worth the effort or risk.

Thanks.

-- 
tejun

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

On 2016/10/14 7:37, Tejun Heo wrote:
> Hello, Zijun.
> 
> On Tue, Oct 11, 2016 at 08:48:45PM +0800, zijun_hu wrote:
>> compared with the original algorithm theoretically and practically, the
>> new one educes the same grouping results, besides, it is more effective,
>> simpler and easier to understand.
> 
> If the original code wasn't broken and the new code produces the same
> output, I'd really not mess with this code.  There simply is no upside
> to messing with this code.  It's run once during boot and never a
> noticeable contributor of boot overhead.  Maybe the new code is a bit
> simpler and more efficient but the actual benefit is so small that any
> risk would outweigh it.
> 
> Thanks.
>
the main intent of this change is making the CPU grouping algorithm more
easily to understand, especially, for newcomer for memory managements
take me as a example, i really take me a longer timer to understand it
 

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

On 2016/10/14 7:37, Tejun Heo wrote:
> Hello, Zijun.
> 
> On Tue, Oct 11, 2016 at 08:48:45PM +0800, zijun_hu wrote:
>> compared with the original algorithm theoretically and practically, the
>> new one educes the same grouping results, besides, it is more effective,
>> simpler and easier to understand.
> 
> If the original code wasn't broken and the new code produces the same
> output, I'd really not mess with this code.  There simply is no upside
> to messing with this code.  It's run once during boot and never a
> noticeable contributor of boot overhead.  Maybe the new code is a bit
> simpler and more efficient but the actual benefit is so small that any
> risk would outweigh it.
> 
> Thanks.
>
the main intent of this change is making the CPU grouping algorithm more
easily to understand, especially, for newcomer for memory managements
take me as a example, i really take me a longer timer to understand it
 

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[Tejun Heo]

Hello, Zijun.

On Tue, Oct 11, 2016 at 08:48:45PM +0800, zijun_hu wrote:
> compared with the original algorithm theoretically and practically, the
> new one educes the same grouping results, besides, it is more effective,
> simpler and easier to understand.

If the original code wasn't broken and the new code produces the same
output, I'd really not mess with this code.  There simply is no upside
to messing with this code.  It's run once during boot and never a
noticeable contributor of boot overhead.  Maybe the new code is a bit
simpler and more efficient but the actual benefit is so small that any
risk would outweigh it.

Thanks.

-- 
tejun

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[Tejun Heo]

Hello, Zijun.

On Tue, Oct 11, 2016 at 08:48:45PM +0800, zijun_hu wrote:
> compared with the original algorithm theoretically and practically, the
> new one educes the same grouping results, besides, it is more effective,
> simpler and easier to understand.

If the original code wasn't broken and the new code produces the same
output, I'd really not mess with this code.  There simply is no upside
to messing with this code.  It's run once during boot and never a
noticeable contributor of boot overhead.  Maybe the new code is a bit
simpler and more efficient but the actual benefit is so small that any
risk would outweigh it.

Thanks.

-- 
tejun

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

On 2016/10/11 20:48, zijun_hu wrote:
> From: zijun_hu 

> in order to verify the new algorithm, we enumerate many pairs of type
> @pcpu_fc_cpu_distance_fn_t function and the relevant CPU IDs array such
> below sample, then apply both algorithms to the same pair and print the
> grouping results separately, the new algorithm is okay after checking
> whether the result printed from the new one is same with the original.
> a sample pair of function and array format is shown as follows:
> /* group CPUs by even/odd number */
> static int cpu_distance_fn0(int from, int to)
> {
>   if (from % 2 ^ to % 2)
>   return REMOTE_DISTANCE;
>   else
>   return LOCAL_DISTANCE;
> }
> /* end with -1 */
> int cpu_ids_0[] = {0, 1, 2, 3, 7, 8, 9, 11, 14, 17, 19, 20, 22, 24, -1};
> 
> Signed-off-by: zijun_hu 
> Tested-by: zijun_hu 
> ---
how to test the new grouping CPU algorithm ?
1) copy the test source code to a file named percpu_group_test.c
2) compile the test program with below command line
   gcc -Wall -o percpu_group_test percpu_group_test.c
3) get usage info about the percpu_group_test
   ./percpu_group_test -h
4) produce the grouping result by the new algorithm
   ./percpu_group_test new > percpu.new
5) produce the grouping result by the original algorithm
   ./percpu_group_test orig > percpu.orig
6) examine the test result; okay if same result; otherwise, failed
   diff -u percpu.new percpu.orig

test program sources is shown as follows:

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define LOCAL_DISTANCE  10
#define REMOTE_DISTANCE 20

#define NR_CPUS 96
static int nr_groups;
static int group_map[NR_CPUS];
static int group_cnt[NR_CPUS];

static int *cpu_ids_ptr;
static int (*cpu_distance_fn) (int from, int to);

static int cpu_distance_fn0(int from, int to);
extern int cpu_ids_0[];

static int cpu_distance_fn1(int from, int to);
extern int cpu_ids_1[];

static int cpu_distance_fn2(int from, int to);
extern int cpu_ids_2[];

int (*cpu_distance_funcx[]) (int, int) = {
cpu_distance_fn0, cpu_distance_fn1, cpu_distance_fn2, NULL};
int *cpu_ids_x[] = { cpu_ids_0, cpu_ids_1, cpu_ids_2, NULL };

static void percpu_test_prepare(int test_type)
{
nr_groups = 0;
memset(group_map, 0xff, sizeof(group_map));
memset(group_cnt, 0xff, sizeof(group_cnt));

cpu_ids_ptr = cpu_ids_x[test_type];
cpu_distance_fn = cpu_distance_funcx[test_type];
}

static int next_cpu(int cpu)
{
int i = 0;
while (cpu_ids_ptr[i] != cpu)
i++;
return cpu_ids_ptr[i + 1];
}

#define for_each_possible_cpu(cpu)  \
for ((cpu) = cpu_ids_ptr[0];\
(cpu) != -1;\
(cpu) = next_cpu((cpu)))

#define max(v0, v1) ((v0) > (v1) ? (v0) : (v1))

static void percpu_result_printf(void)
{
int g;
int c;

printf("nr_groups = %d\n", nr_groups);
#if 0
for_each_possible_cpu(c)
if (group_map[c] != -1)
printf("group_map[%d] = %d\n", c, group_map[c]);
for (g = 0; g < nr_groups; g++)
printf("group_cnt[%d] = %d\n", g, group_cnt[g]);
#else
for (g = 0; g < nr_groups; g++) {
printf("group id %d : ", g);
for_each_possible_cpu(c)
if (group_map[c] == g)
printf("%d ", c);
printf("\n");
}
printf("\n");
#endif
}

/*
 * group cpus by even or odd ids
 */
static int cpu_distance_fn0(int from, int to)
{
if (from % 2 ^ to % 2)
return REMOTE_DISTANCE;
else
return LOCAL_DISTANCE;
}

/* end with -1 */
int cpu_ids_0[] = { 0, 1, 2, 3, 7, 8, 9, 11, 14, 17, 19, 20, 22, 24, 31, -1 };

/*
 * group cpus by 3x of cpu ids
 */
int cpu_distance_fn1(int from, int to)
{
if (from % 3 == 0 && to % 3 == 0)
return LOCAL_DISTANCE;
else if (from % 3 && to % 3)
return LOCAL_DISTANCE;
else
return REMOTE_DISTANCE;
}
int cpu_ids_1[] = { 0, 3, 5, 6, 8, 9, 10, 11, 12, 14, 17, 18, 21, 24, 25, -1 };

/*
 * group cpus by range, [..., 10), [10, 20), [20, ...)
 */
int cpu_distance_fn2(int from, int to)
{
if (from < 10 && to < 10)
return LOCAL_DISTANCE;
else if (from >= 20 && to >= 20)
return LOCAL_DISTANCE;
else if ((from >= 10 && from < 20) && (to >= 10 && to < 20))
return LOCAL_DISTANCE;
else
return REMOTE_DISTANCE;

}
int cpu_ids_2[] =
{ 0, 1, 2, 4, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 22, 25, 27, -1 };

void orig_group_cpus(int test_type)
{
int group;
int cpu, tcpu;
percpu_test_prepare(test_type);

/* group cpus according to their proximity */
for_each_possible_cpu(cpu) {
  

Re: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

On 2016/10/11 20:48, zijun_hu wrote:
> From: zijun_hu 

> in order to verify the new algorithm, we enumerate many pairs of type
> @pcpu_fc_cpu_distance_fn_t function and the relevant CPU IDs array such
> below sample, then apply both algorithms to the same pair and print the
> grouping results separately, the new algorithm is okay after checking
> whether the result printed from the new one is same with the original.
> a sample pair of function and array format is shown as follows:
> /* group CPUs by even/odd number */
> static int cpu_distance_fn0(int from, int to)
> {
>   if (from % 2 ^ to % 2)
>   return REMOTE_DISTANCE;
>   else
>   return LOCAL_DISTANCE;
> }
> /* end with -1 */
> int cpu_ids_0[] = {0, 1, 2, 3, 7, 8, 9, 11, 14, 17, 19, 20, 22, 24, -1};
> 
> Signed-off-by: zijun_hu 
> Tested-by: zijun_hu 
> ---
how to test the new grouping CPU algorithm ?
1) copy the test source code to a file named percpu_group_test.c
2) compile the test program with below command line
   gcc -Wall -o percpu_group_test percpu_group_test.c
3) get usage info about the percpu_group_test
   ./percpu_group_test -h
4) produce the grouping result by the new algorithm
   ./percpu_group_test new > percpu.new
5) produce the grouping result by the original algorithm
   ./percpu_group_test orig > percpu.orig
6) examine the test result; okay if same result; otherwise, failed
   diff -u percpu.new percpu.orig

test program sources is shown as follows:

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define LOCAL_DISTANCE  10
#define REMOTE_DISTANCE 20

#define NR_CPUS 96
static int nr_groups;
static int group_map[NR_CPUS];
static int group_cnt[NR_CPUS];

static int *cpu_ids_ptr;
static int (*cpu_distance_fn) (int from, int to);

static int cpu_distance_fn0(int from, int to);
extern int cpu_ids_0[];

static int cpu_distance_fn1(int from, int to);
extern int cpu_ids_1[];

static int cpu_distance_fn2(int from, int to);
extern int cpu_ids_2[];

int (*cpu_distance_funcx[]) (int, int) = {
cpu_distance_fn0, cpu_distance_fn1, cpu_distance_fn2, NULL};
int *cpu_ids_x[] = { cpu_ids_0, cpu_ids_1, cpu_ids_2, NULL };

static void percpu_test_prepare(int test_type)
{
nr_groups = 0;
memset(group_map, 0xff, sizeof(group_map));
memset(group_cnt, 0xff, sizeof(group_cnt));

cpu_ids_ptr = cpu_ids_x[test_type];
cpu_distance_fn = cpu_distance_funcx[test_type];
}

static int next_cpu(int cpu)
{
int i = 0;
while (cpu_ids_ptr[i] != cpu)
i++;
return cpu_ids_ptr[i + 1];
}

#define for_each_possible_cpu(cpu)  \
for ((cpu) = cpu_ids_ptr[0];\
(cpu) != -1;\
(cpu) = next_cpu((cpu)))

#define max(v0, v1) ((v0) > (v1) ? (v0) : (v1))

static void percpu_result_printf(void)
{
int g;
int c;

printf("nr_groups = %d\n", nr_groups);
#if 0
for_each_possible_cpu(c)
if (group_map[c] != -1)
printf("group_map[%d] = %d\n", c, group_map[c]);
for (g = 0; g < nr_groups; g++)
printf("group_cnt[%d] = %d\n", g, group_cnt[g]);
#else
for (g = 0; g < nr_groups; g++) {
printf("group id %d : ", g);
for_each_possible_cpu(c)
if (group_map[c] == g)
printf("%d ", c);
printf("\n");
}
printf("\n");
#endif
}

/*
 * group cpus by even or odd ids
 */
static int cpu_distance_fn0(int from, int to)
{
if (from % 2 ^ to % 2)
return REMOTE_DISTANCE;
else
return LOCAL_DISTANCE;
}

/* end with -1 */
int cpu_ids_0[] = { 0, 1, 2, 3, 7, 8, 9, 11, 14, 17, 19, 20, 22, 24, 31, -1 };

/*
 * group cpus by 3x of cpu ids
 */
int cpu_distance_fn1(int from, int to)
{
if (from % 3 == 0 && to % 3 == 0)
return LOCAL_DISTANCE;
else if (from % 3 && to % 3)
return LOCAL_DISTANCE;
else
return REMOTE_DISTANCE;
}
int cpu_ids_1[] = { 0, 3, 5, 6, 8, 9, 10, 11, 12, 14, 17, 18, 21, 24, 25, -1 };

/*
 * group cpus by range, [..., 10), [10, 20), [20, ...)
 */
int cpu_distance_fn2(int from, int to)
{
if (from < 10 && to < 10)
return LOCAL_DISTANCE;
else if (from >= 20 && to >= 20)
return LOCAL_DISTANCE;
else if ((from >= 10 && from < 20) && (to >= 10 && to < 20))
return LOCAL_DISTANCE;
else
return REMOTE_DISTANCE;

}
int cpu_ids_2[] =
{ 0, 1, 2, 4, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 22, 25, 27, -1 };

void orig_group_cpus(int test_type)
{
int group;
int cpu, tcpu;
percpu_test_prepare(test_type);

/* group cpus according to their proximity */
for_each_possible_cpu(cpu) {
group = 0;
next_group:

[RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

From: zijun_hu 

pcpu_build_alloc_info() groups CPUs according to relevant proximity
together to allocate memory for each percpu unit based on group.
however, the grouping algorithm consists of three loops and a goto
statement actually, and is inefficient and difficult to understand

the original algorithm is simplified to only consists of two loops
without any goto statement. for the new one, in order to assign a group
number to a target CPU, we check whether it can share a group with any
lower index CPU; the shareable group number is reused if so; otherwise,
a new one is assigned to it.

compared with the original algorithm theoretically and practically, the
new one educes the same grouping results, besides, it is more effective,
simpler and easier to understand.

in order to verify the new algorithm, we enumerate many pairs of type
@pcpu_fc_cpu_distance_fn_t function and the relevant CPU IDs array such
below sample, then apply both algorithms to the same pair and print the
grouping results separately, the new algorithm is okay after checking
whether the result printed from the new one is same with the original.
a sample pair of function and array format is shown as follows:
/* group CPUs by even/odd number */
static int cpu_distance_fn0(int from, int to)
{
if (from % 2 ^ to % 2)
return REMOTE_DISTANCE;
else
return LOCAL_DISTANCE;
}
/* end with -1 */
int cpu_ids_0[] = {0, 1, 2, 3, 7, 8, 9, 11, 14, 17, 19, 20, 22, 24, -1};

Signed-off-by: zijun_hu 
Tested-by: zijun_hu 
---
 Changes in v2:
  - update commit messages

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

diff --git a/mm/percpu.c b/mm/percpu.c
index 255714302394..32e2d8d128c1 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -1824,23 +1824,25 @@ static struct pcpu_alloc_info * __init 
pcpu_build_alloc_info(
max_upa = upa;
 
/* group cpus according to their proximity */
-   for_each_possible_cpu(cpu) {
-   group = 0;
-   next_group:
+   group = 0;
+   for_each_possible_cpu(cpu)
for_each_possible_cpu(tcpu) {
-   if (cpu == tcpu)
-   break;
-   if (group_map[tcpu] == group && cpu_distance_fn &&
-   (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
-cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
+   if (tcpu == cpu) {
+   group_map[cpu] = group;
+   group_cnt[group] = 1;
group++;
-   nr_groups = max(nr_groups, group + 1);
-   goto next_group;
+   break;
+   }
+
+   if (!cpu_distance_fn ||
+   (cpu_distance_fn(cpu, tcpu) == LOCAL_DISTANCE &&
+cpu_distance_fn(tcpu, cpu) == LOCAL_DISTANCE)) {
+   group_map[cpu] = group_map[tcpu];
+   group_cnt[group_map[cpu]]++;
+   break;
}
}
-   group_map[cpu] = group;
-   group_cnt[group]++;
-   }
+   nr_groups = group;
 
/*
 * Expand unit size until address space usage goes over 75%
-- 
1.9.1

[RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm

[zijun_hu]

From: zijun_hu 

pcpu_build_alloc_info() groups CPUs according to relevant proximity
together to allocate memory for each percpu unit based on group.
however, the grouping algorithm consists of three loops and a goto
statement actually, and is inefficient and difficult to understand

the original algorithm is simplified to only consists of two loops
without any goto statement. for the new one, in order to assign a group
number to a target CPU, we check whether it can share a group with any
lower index CPU; the shareable group number is reused if so; otherwise,
a new one is assigned to it.

compared with the original algorithm theoretically and practically, the
new one educes the same grouping results, besides, it is more effective,
simpler and easier to understand.

in order to verify the new algorithm, we enumerate many pairs of type
@pcpu_fc_cpu_distance_fn_t function and the relevant CPU IDs array such
below sample, then apply both algorithms to the same pair and print the
grouping results separately, the new algorithm is okay after checking
whether the result printed from the new one is same with the original.
a sample pair of function and array format is shown as follows:
/* group CPUs by even/odd number */
static int cpu_distance_fn0(int from, int to)
{
if (from % 2 ^ to % 2)
return REMOTE_DISTANCE;
else
return LOCAL_DISTANCE;
}
/* end with -1 */
int cpu_ids_0[] = {0, 1, 2, 3, 7, 8, 9, 11, 14, 17, 19, 20, 22, 24, -1};

Signed-off-by: zijun_hu 
Tested-by: zijun_hu 
---
 Changes in v2:
  - update commit messages

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

diff --git a/mm/percpu.c b/mm/percpu.c
index 255714302394..32e2d8d128c1 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -1824,23 +1824,25 @@ static struct pcpu_alloc_info * __init 
pcpu_build_alloc_info(
max_upa = upa;
 
/* group cpus according to their proximity */
-   for_each_possible_cpu(cpu) {
-   group = 0;
-   next_group:
+   group = 0;
+   for_each_possible_cpu(cpu)
for_each_possible_cpu(tcpu) {
-   if (cpu == tcpu)
-   break;
-   if (group_map[tcpu] == group && cpu_distance_fn &&
-   (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
-cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
+   if (tcpu == cpu) {
+   group_map[cpu] = group;
+   group_cnt[group] = 1;
group++;
-   nr_groups = max(nr_groups, group + 1);
-   goto next_group;
+   break;
+   }
+
+   if (!cpu_distance_fn ||
+   (cpu_distance_fn(cpu, tcpu) == LOCAL_DISTANCE &&
+cpu_distance_fn(tcpu, cpu) == LOCAL_DISTANCE)) {
+   group_map[cpu] = group_map[tcpu];
+   group_cnt[group_map[cpu]]++;
+   break;
}
}
-   group_map[cpu] = group;
-   group_cnt[group]++;
-   }
+   nr_groups = group;
 
/*
 * Expand unit size until address space usage goes over 75%
-- 
1.9.1