Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753444AbcJKMt0 (ORCPT ); Tue, 11 Oct 2016 08:49:26 -0400 Received: from sender153-mail.zoho.com ([74.201.84.153]:25357 "EHLO sender153-mail.zoho.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752618AbcJKMtX (ORCPT ); Tue, 11 Oct 2016 08:49:23 -0400 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=zapps768; d=zoho.com; h=cc:from:subject:to:message-id:date:user-agent:mime-version:content-type; b=s1ojh6OJRky2sXdjv5y35EveDPMB9E0q5HXGtgfHegQrjyt09WAdiVGQJ/73OnKcLGXASRLbRlo0 FHA02kBG1zVW4I8JCqRpcYUjp0ErbR8C1xt7M1AJB9bREvJgE82d Cc: zijun_hu@htc.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, cl@linux.com From: zijun_hu Subject: [RFC v2 PATCH] mm/percpu.c: simplify grouping CPU algorithm To: tj@kernel.org, akpm@linux-foundation.org Message-ID: <701fa92a-026b-f30b-833c-a5e61eab6549@zoho.com> Date: Tue, 11 Oct 2016 20:48:45 +0800 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.3.0 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2877 Lines: 88 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