lkml.org 
[lkml]   [2016]   [Oct]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm
    From
    Date
    On 2016/10/11 20:48, zijun_hu wrote:
    > From: zijun_hu <zijun_hu@htc.com>

    > 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 <zijun_hu@htc.com>
    > Tested-by: zijun_hu <zijun_hu@htc.com>
    > ---
    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 <stdarg.h>
    #include <stdbool.h>
    #include <stdint.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <string.h>

    #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:
    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)) {
    group++;
    nr_groups = max(nr_groups, group + 1);
    goto next_group;
    }
    }
    group_map[cpu] = group;
    group_cnt[group]++;
    }

    percpu_result_printf();
    }

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

    /* group cpus according to their proximity */
    group = 0;
    for_each_possible_cpu(cpu)
    for_each_possible_cpu(tcpu) {
    if (tcpu == cpu) {
    group_map[cpu] = group;
    group_cnt[group] = 1;
    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;
    }
    }
    nr_groups = group;

    percpu_result_printf();
    }

    int main(int argc, char *argv[])
    {
    int ret = -1;
    int is_new;
    int test_type;

    if (argc < 2)
    goto help_out;

    if (strcmp(argv[1], "-h") == 0 || strcmp(argv[1], "--help") == 0) {
    ret = 0;
    goto help_out;
    }

    if (strcmp(argv[1], "new") == 0)
    is_new = 1;
    else if (strcmp(argv[1], "orig") == 0)
    is_new = 0;
    else
    goto help_out;

    printf("is_new = %d\n", is_new);
    for (test_type = 0; cpu_ids_x[test_type] != NULL; test_type++)
    if (is_new)
    fix_group_cpus(test_type);
    else
    orig_group_cpus(test_type);
    ret = 0;
    return ret;

    help_out:
    printf("Usage : %s -h|--help|new|orig\n", argv[0]);
    printf("\t-h|--help : ouput this help message\n");
    printf("\tnew : get the results of grouping cpu by new \
    algorithm\n");
    printf("\torig : get the results of grouping cpu by \
    original algorithm\n");
    printf("new algorithm can be verified by run this test \
    program with parameter\n");
    printf("new and orig respectively, then check whether the \
    output message are same\n");
    return ret;
    }


    \
     
     \ /
      Last update: 2016-10-11 14:54    [W:4.726 / U:1.168 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site