From patchwork Sat Jan 21 04:24:30 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 46769 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:eb09:0:0:0:0:0 with SMTP id s9csp567096wrn; Fri, 20 Jan 2023 20:26:42 -0800 (PST) X-Google-Smtp-Source: AMrXdXtgLOtaCqkaD7t5DHYQYkw5ieO1J8d/B3zU4X3NGnfnupZYqU7LrPmUTwz33IoH5O+mKjf+ X-Received: by 2002:a05:6402:2419:b0:49d:2a42:b8c8 with SMTP id t25-20020a056402241900b0049d2a42b8c8mr19940149eda.26.1674275201946; Fri, 20 Jan 2023 20:26:41 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1674275201; cv=none; d=google.com; s=arc-20160816; b=OKibWcvnLq6A6V7gkvYOAidQrhGCtzFxEgDUq3hcz0dh2MmBJClUO8URuVCEub5KdS CJKr6fCPdx0vWFGifXKIHqVutW+y/x+v6tXIAzDWhIa7zaQ9grO124vZUdj4rQVjoEGI IgUlj9OJQqM+wYQms6HxpWEn7dpWeCd8IDBWieS/+RqHJoxvLLHVoH0/0nFaGlfEz31i bfBlcAxNZGCWlXSyY2Kyj11XGcXM4sdgc6w+iUzSETEuE0FzJHi4XYI1pt0Nctt2xcNt pz7il4cNQZjlNFryfUu7/8WlytiTptj1yvf2wsEuD8pdx73nlfe3DRXR/g1Ol6A9IzWU y90Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=DUfnaBP5lJbCL0GNiMEf+7JU9t1M5MfdDFKLQwINrqk=; b=uLDLa1zofcbmlLGcC0WUi2igmXyJJ0nqgCAGqlx8Mkk7ix7YW2V33HhsNojIk6ahgW hy7u2WAcQXdvp7vR48WUpD1Kec3ASwgr4kZ2PJa87sQXg4GmwrPYin0Dc69rylFOdcgg IvEAYjYY6So736gxrCbznZ0XYMBShno3pJq/B+0QNUxigGkS5QgorMzg6oonAYI8B26K Fy0//TTGqo/R5umtP7D6c9d59TwqXp31hZiVWqAOWm5qoThStR6nKNn5T7q7Hf2gk6+g a1ev0qN6evwxUvoUK2czMcT7IiKIdoDXouOywAJBvy3fOXMLA53wOJ5pquLYtnRuaWN3 izZA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=JI2Z5SzD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id a5-20020aa7d905000000b0049e6a68b509si6590219edr.631.2023.01.20.20.26.18; Fri, 20 Jan 2023 20:26:41 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=JI2Z5SzD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229604AbjAUEZQ (ORCPT + 99 others); Fri, 20 Jan 2023 23:25:16 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35736 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229823AbjAUEYq (ORCPT ); Fri, 20 Jan 2023 23:24:46 -0500 Received: from mail-qt1-x831.google.com (mail-qt1-x831.google.com [IPv6:2607:f8b0:4864:20::831]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1669150843; Fri, 20 Jan 2023 20:24:45 -0800 (PST) Received: by mail-qt1-x831.google.com with SMTP id g16so3765698qtu.2; Fri, 20 Jan 2023 20:24:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=DUfnaBP5lJbCL0GNiMEf+7JU9t1M5MfdDFKLQwINrqk=; b=JI2Z5SzD2aaTHlQx9e0J54AC8wdh7+DH+cR5sUi/bLrniSWMzxwFF7NL5awZ/lhqaF W5jiQGZPn58mj5hutiwKOHq+LBNCi3NWVqvfhK+3rTeu5C5/1Sebepnnbx7jhWShj2L8 zzY9N1e4mskl2NwiPSoUBlqA7gfWm/TlWIwTfsJtizaEtNyHPHhkm8A81dYUiOsGmTVA aJnEodZO/UHF55Aaa8Ya6ORBgPtXdVloQUbalUekikBiJJMmpUtLNPrT2zxW5KqTuEjD fue8rw06THQRNzmYOYEOO8Z0xtSgNrkxC98hJC5KZKNjpcsI8iJw8FdndTEjx9FiRTit G/oQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=DUfnaBP5lJbCL0GNiMEf+7JU9t1M5MfdDFKLQwINrqk=; b=jCrYIenIYx430tbWCM7t/J9vZUl2+XZkLayYMZkDv9y5nejMWwrFgSxTtJ/i8nOwDG Y6TsjIelcVo7jKEx4jT3uI6eDrNbJ0tyrEfOwvrnsUQYHAiB/KVyYAl9dcluiaBblDve efD9pQYiW5TgumNKsUFkbKI+bGGLfUMyBo2oVFNc/SBUmehuGD7gaich50+KUtZYL8EW M4fczhOf+QriQ6EzZp30Jse26+txG5MzcbVodGzWZj9b6ItN4hhjvTvdUvoXBcB3d88S 0oP194nKQlza9aydUk41N9BxwNFeMF1uL16Jg0MDHmGPB1sp0jBd7jy7gFIDvZ2m4a+7 j3Ow== X-Gm-Message-State: AFqh2kpzi8dRu5pjz0p8aJpps/rnVzepcviFAUGPhDXA8k/esbLbxpky ZsOnAp6zVCVJXSLW2Bu+k6zexCu+lck= X-Received: by 2002:ac8:6bd2:0:b0:3b2:2195:e2a2 with SMTP id b18-20020ac86bd2000000b003b22195e2a2mr23673991qtt.45.1674275083683; Fri, 20 Jan 2023 20:24:43 -0800 (PST) Received: from localhost (50-242-44-45-static.hfc.comcastbusiness.net. [50.242.44.45]) by smtp.gmail.com with ESMTPSA id fe13-20020a05622a4d4d00b003a580cd979asm21689174qtb.58.2023.01.20.20.24.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Jan 2023 20:24:43 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , Dietmar Eggemann , Gal Pressman , Greg Kroah-Hartman , Haniel Bristot de Oliveira , Heiko Carstens , Ingo Molnar , Jacob Keller , Jakub Kicinski , Jason Gunthorpe , Jesse Brandeburg , Jonathan Cameron , Juri Lelli , Leon Romanovsky , Linus Torvalds , Mel Gorman , Peter Lafreniere , Peter Zijlstra , Rasmus Villemoes , Saeed Mahameed , Steven Rostedt , Tariq Toukan , Tariq Toukan , Tony Luck , Valentin Schneider , Vincent Guittot Cc: Yury Norov , linux-crypto@vger.kernel.org, netdev@vger.kernel.org, linux-rdma@vger.kernel.org Subject: [PATCH 3/9] sched: add sched_numa_find_nth_cpu() Date: Fri, 20 Jan 2023 20:24:30 -0800 Message-Id: <20230121042436.2661843-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230121042436.2661843-1-yury.norov@gmail.com> References: <20230121042436.2661843-1-yury.norov@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM, RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1755604794190910539?= X-GMAIL-MSGID: =?utf-8?q?1755604794190910539?= The function finds Nth set CPU in a given cpumask starting from a given node. Leveraging the fact that each hop in sched_domains_numa_masks includes the same or greater number of CPUs than the previous one, we can use binary search on hops instead of linear walk, which makes the overall complexity of O(log n) in terms of number of cpumask_weight() calls. Signed-off-by: Yury Norov Acked-by: Tariq Toukan Reviewed-by: Jacob Keller Reviewed-by: Peter Lafreniere Reported-by: Bruno Goncalves Signed-off-by: Yury Norov --- include/linux/topology.h | 8 ++++++ kernel/sched/topology.c | 57 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 65 insertions(+) diff --git a/include/linux/topology.h b/include/linux/topology.h index 4564faafd0e1..72f264575698 100644 --- a/include/linux/topology.h +++ b/include/linux/topology.h @@ -245,5 +245,13 @@ static inline const struct cpumask *cpu_cpu_mask(int cpu) return cpumask_of_node(cpu_to_node(cpu)); } +#ifdef CONFIG_NUMA +int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node); +#else +static __always_inline int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node) +{ + return cpumask_nth(cpu, cpus); +} +#endif /* CONFIG_NUMA */ #endif /* _LINUX_TOPOLOGY_H */ diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c index 8739c2a5a54e..2bf89186a10f 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -3,6 +3,8 @@ * Scheduler topology setup/handling methods */ +#include + DEFINE_MUTEX(sched_domains_mutex); /* Protected by sched_domains_mutex: */ @@ -2067,6 +2069,61 @@ int sched_numa_find_closest(const struct cpumask *cpus, int cpu) return found; } +struct __cmp_key { + const struct cpumask *cpus; + struct cpumask ***masks; + int node; + int cpu; + int w; +}; + +static int hop_cmp(const void *a, const void *b) +{ + struct cpumask **prev_hop = *((struct cpumask ***)b - 1); + struct cpumask **cur_hop = *(struct cpumask ***)b; + struct __cmp_key *k = (struct __cmp_key *)a; + + if (cpumask_weight_and(k->cpus, cur_hop[k->node]) <= k->cpu) + return 1; + + k->w = (b == k->masks) ? 0 : cpumask_weight_and(k->cpus, prev_hop[k->node]); + if (k->w <= k->cpu) + return 0; + + return -1; +} + +/* + * sched_numa_find_nth_cpu() - given the NUMA topology, find the Nth next cpu + * closest to @cpu from @cpumask. + * cpumask: cpumask to find a cpu from + * cpu: Nth cpu to find + * + * returns: cpu, or nr_cpu_ids when nothing found. + */ +int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node) +{ + struct __cmp_key k = { .cpus = cpus, .node = node, .cpu = cpu }; + struct cpumask ***hop_masks; + int hop, ret = nr_cpu_ids; + + rcu_read_lock(); + + k.masks = rcu_dereference(sched_domains_numa_masks); + if (!k.masks) + goto unlock; + + hop_masks = bsearch(&k, k.masks, sched_domains_numa_levels, sizeof(k.masks[0]), hop_cmp); + hop = hop_masks - k.masks; + + ret = hop ? + cpumask_nth_and_andnot(cpu - k.w, cpus, k.masks[hop][node], k.masks[hop-1][node]) : + cpumask_nth_and(cpu, cpus, k.masks[0][node]); +unlock: + rcu_read_unlock(); + return ret; +} +EXPORT_SYMBOL_GPL(sched_numa_find_nth_cpu); #endif /* CONFIG_NUMA */ static int __sdt_alloc(const struct cpumask *cpu_map)