From patchwork Thu Dec 8 18:30:57 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13068652 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 048CCC10F1D for ; Thu, 8 Dec 2022 18:31:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229830AbiLHSbK (ORCPT ); Thu, 8 Dec 2022 13:31:10 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46578 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229738AbiLHSbH (ORCPT ); Thu, 8 Dec 2022 13:31:07 -0500 Received: from mail-oa1-x33.google.com (mail-oa1-x33.google.com [IPv6:2001:4860:4864:20::33]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CD2B985D22; Thu, 8 Dec 2022 10:31:06 -0800 (PST) Received: by mail-oa1-x33.google.com with SMTP id 586e51a60fabf-144bd860fdbso2851441fac.0; Thu, 08 Dec 2022 10:31:06 -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=7GKu6nYSg2QuKfSdnsbd4k37yUZL8bwLA3bRTzpoaPY=; b=Y15HafJbJTrLTuYdUm3i7HUjS0WiIKG+VAqL+nHDWm1wgXNnqc3nd5zCGz2jAnyQeM XFIktIRnVOzIO3UCKzZW6YSDDH6n51hFOzeH1I5n4a36lrPgccDOhu5s/tT0Ok4GNlyH r7+C4+igqjHDeDuej17Sqsivvjg+a7aexu/boogD3G4gUJmoYPcSx0xJXffDy0Qe8g4o LDjBHzHGX7WhtP3If+O4WjybNGkXsZpkEYbW0IkwL+Y1kQMztK3S0EnbX+a0Z5qpeDXK LPzmLfDhg2KRJUe12KECmbL4j4wrgIEfvgBGiWsR5h6DzOKzrTISjEqGsmJGXXc3Nh3d bRmA== 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=7GKu6nYSg2QuKfSdnsbd4k37yUZL8bwLA3bRTzpoaPY=; b=UUqMbC3zwlvg9o/o/IMRqwyMuZGNplB8CHZE05oB7mdtqr/zD6eYqtC4lGLkYVexHH SaUX4E5Itw21olMdC10jZYTj8r7+TenBLT/FGaW5y6+Tp6paw+WjJefioqlFv1znB62x +zzVFpzDw62gOy6Db/hRiKN0G4AvTIEeXx6Q9E5S0EdBjT1wog5uKcwK2D6xX4u31C+W rMpVN0V1HUmKjM4pAIasOkZKzO2nA+Rg3Al/i55edSQv4sTPQ4GFjeiwfowSm2prwcf/ CKmVfxayb77uUBaVSCeYkf1VilGbmTPuBJD3ZpehuOT2udJsSuzKTD0IWBS7WYNmhjh0 3QcA== X-Gm-Message-State: ANoB5pkwJqSKQ2olZ2Mx1fCHHlMNj+VtI9dcPewgNyLwsxe2343poh4O ZmWARuhTNgYOPI0jHkrjuXhIcLpP8iU= X-Google-Smtp-Source: AA0mqf4cS0omche0WusJuRsm1M++bRMWf4geAAW8C6lPPHTypaUr2hXdeM8VNGIGdX1In1C2oFr4RQ== X-Received: by 2002:a05:6870:6088:b0:13b:85e:2a3a with SMTP id t8-20020a056870608800b0013b085e2a3amr1605938oae.12.1670524266217; Thu, 08 Dec 2022 10:31:06 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id d67-20020aca3646000000b0035a921f2093sm10834215oia.20.2022.12.08.10.31.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 08 Dec 2022 10:31:05 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , haniel Bristot de Oliveira , Dietmar Eggemann , Gal Pressman , Greg Kroah-Hartman , Heiko Carstens , Ingo Molnar , Jakub Kicinski , Jason Gunthorpe , Jesse Brandeburg , Jonathan Cameron , Juri Lelli , Leon Romanovsky , Mel Gorman , 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 v3 1/5] lib/find: introduce find_nth_and_andnot_bit Date: Thu, 8 Dec 2022 10:30:57 -0800 Message-Id: <20221208183101.1162006-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221208183101.1162006-1-yury.norov@gmail.com> References: <20221208183101.1162006-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org The function is used to implement in-place bitmaps traversing without storing intermediate result in temporary bitmaps, in the following patches. Signed-off-by: Yury Norov --- include/linux/find.h | 33 +++++++++++++++++++++++++++++++++ lib/find_bit.c | 9 +++++++++ 2 files changed, 42 insertions(+) diff --git a/include/linux/find.h b/include/linux/find.h index 3f59c2fbe438..b594207a0010 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -23,6 +23,9 @@ unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long unsigned long size, unsigned long n); unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long n); +unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, + const unsigned long *addr3, unsigned long size, + unsigned long n); extern unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size); extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); @@ -244,6 +247,36 @@ unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned lon return __find_nth_andnot_bit(addr1, addr2, size, n); } +/** + * find_nth_and_andnot_bit - find N'th set bit in 2 memory regions, + * excluding those set in 3rd region + * @addr1: The 1st address to start the search at + * @addr2: The 2nd address to start the search at + * @addr3: The 3rd address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed, counting from 0 + * + * Returns the bit number of the N'th set bit. + * If no such, returns @size. + */ +static __always_inline +unsigned long find_nth_and_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + const unsigned long *addr3, + unsigned long size, unsigned long n) +{ + if (n >= size) + return size; + + if (small_const_nbits(size)) { + unsigned long val = *addr1 & *addr2 & (~*addr3) & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return __find_nth_and_andnot_bit(addr1, addr2, addr3, size, n); +} + #ifndef find_first_and_bit /** * find_first_and_bit - find the first set bit in both memory regions diff --git a/lib/find_bit.c b/lib/find_bit.c index 18bc0a7ac8ee..c10920e66788 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -155,6 +155,15 @@ unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned l } EXPORT_SYMBOL(__find_nth_andnot_bit); +unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + const unsigned long *addr3, + unsigned long size, unsigned long n) +{ + return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n); +} +EXPORT_SYMBOL(__find_nth_and_andnot_bit); + #ifndef find_next_and_bit unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long nbits, unsigned long start) From patchwork Thu Dec 8 18:30:58 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13068653 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 29701C001B2 for ; Thu, 8 Dec 2022 18:31:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229870AbiLHSbN (ORCPT ); Thu, 8 Dec 2022 13:31:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46624 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229835AbiLHSbK (ORCPT ); Thu, 8 Dec 2022 13:31:10 -0500 Received: from mail-ot1-x329.google.com (mail-ot1-x329.google.com [IPv6:2607:f8b0:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8BFCD9B2A7; Thu, 8 Dec 2022 10:31:09 -0800 (PST) Received: by mail-ot1-x329.google.com with SMTP id s30-20020a056830439e00b0067052c70922so1362809otv.11; Thu, 08 Dec 2022 10:31:09 -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=LbKgne40p2rihRA02W+HijcyMxRa1yUI8+yJKRvf/NQ=; b=Bo31gsyp0J+TM4su3QjnRadwNIVXJy/+Lrdq6df32Kz4GdD2b0xgWMgT7N5K/DDwWU jfqLjlaQ8YRbgzCn1ch/yeC8xrsJP1640IroCB9FHD16GRqM/Ta8ROXek+v9w7MaRM75 0DzIOVFzssMmPt50XPvrT+5BmlptjQscuSrI/lQ9xH+E5B1C5HJpwGBfktPgPoj2yWWG m8woPWvOB0Zh38DJsq1tEjPsZ3FIN14HgQJJifleKRi22Bne5WnvlqgqBlJNVC2cUoPV b/e4nq92OOcGXb7Yh5WF0V2sEAs+iWV1lXLQspuNK61QhRyKYDPqgkgrKfVVwTwaqIjK 69Dg== 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=LbKgne40p2rihRA02W+HijcyMxRa1yUI8+yJKRvf/NQ=; b=4b5g97O3OvTiF/2LL93J/fINjP2H1Nr9UZzMFEw2CnPpf9OttxXQ2v/bnLHp3kJywT bX4kmhwL8lLl+wD5ktwvke6/rrF07/OeYKDnUrFRXbjQUicaSHCkWykEWTwi1d8U+bxA 99gy13kyuHR0xUNZ7mjKS/HPNAYSd8qio6RAqeovbxRhtmZx77MZppl4xucMTEln45HT AaDTjhIBj9uyrW7twgXQwmX5mcXqj7V0QbsxefnIyry8X/QI2Aqzuw6jbkUFutUgbRZr HGKDkFxPg+GKIbSEwlW3UAF6jD3cK6j+Nfmj4LtuyvMU74kQQl8yV/jLy/szTEyBFwK7 jY5g== X-Gm-Message-State: ANoB5pkDYXOR51k57zIepRCaExOfe8T8HagEfl8YsH/FoYgZS5HaJxX0 ZNZkNfikXMbq1X+3HxTnJvYx0dnjalc= X-Google-Smtp-Source: AA0mqf5S/KEvDVb/hsApCxLtfK1h78S1yk8iDwtF6DYH8dBGFneQlN/N/5/NO1fxSDgDkb8tg21Ovw== X-Received: by 2002:a05:6830:d8c:b0:66a:ea19:28ea with SMTP id bv12-20020a0568300d8c00b0066aea1928eamr2139337otb.38.1670524268597; Thu, 08 Dec 2022 10:31:08 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id i21-20020a9d68d5000000b00662228a27d3sm11783552oto.57.2022.12.08.10.31.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 08 Dec 2022 10:31:08 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , haniel Bristot de Oliveira , Dietmar Eggemann , Gal Pressman , Greg Kroah-Hartman , Heiko Carstens , Ingo Molnar , Jakub Kicinski , Jason Gunthorpe , Jesse Brandeburg , Jonathan Cameron , Juri Lelli , Leon Romanovsky , Mel Gorman , 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 v3 2/5] cpumask: introduce cpumask_nth_and_andnot Date: Thu, 8 Dec 2022 10:30:58 -0800 Message-Id: <20221208183101.1162006-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221208183101.1162006-1-yury.norov@gmail.com> References: <20221208183101.1162006-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Introduce cpumask_nth_and_andnot() based on find_nth_and_andnot_bit(). It's used in the following patch to traverse cpumasks without storing intermediate result in temporary cpumask. Signed-off-by: Yury Norov --- include/linux/cpumask.h | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h index 9543b22d6dc2..5c4905108d1b 100644 --- a/include/linux/cpumask.h +++ b/include/linux/cpumask.h @@ -391,6 +391,26 @@ unsigned int cpumask_nth_andnot(unsigned int cpu, const struct cpumask *srcp1, nr_cpumask_bits, cpumask_check(cpu)); } +/** + * cpumask_nth_and_andnot - get the Nth cpu set in 1st and 2nd cpumask, and clear in 3rd. + * @srcp1: the cpumask pointer + * @srcp2: the cpumask pointer + * @srcp3: the cpumask pointer + * @cpu: the N'th cpu to find, starting from 0 + * + * Returns >= nr_cpu_ids if such cpu doesn't exist. + */ +static __always_inline +unsigned int cpumask_nth_and_andnot(unsigned int cpu, const struct cpumask *srcp1, + const struct cpumask *srcp2, + const struct cpumask *srcp3) +{ + return find_nth_and_andnot_bit(cpumask_bits(srcp1), + cpumask_bits(srcp2), + cpumask_bits(srcp3), + nr_cpumask_bits, cpumask_check(cpu)); +} + #define CPU_BITS_NONE \ { \ [0 ... BITS_TO_LONGS(NR_CPUS)-1] = 0UL \ From patchwork Thu Dec 8 18:30:59 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13068654 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A13A1C001B2 for ; Thu, 8 Dec 2022 18:31:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229900AbiLHSbV (ORCPT ); Thu, 8 Dec 2022 13:31:21 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46690 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229861AbiLHSbN (ORCPT ); Thu, 8 Dec 2022 13:31:13 -0500 Received: from mail-oi1-x234.google.com (mail-oi1-x234.google.com [IPv6:2607:f8b0:4864:20::234]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3F547AD335; Thu, 8 Dec 2022 10:31:11 -0800 (PST) Received: by mail-oi1-x234.google.com with SMTP id h132so2259334oif.2; Thu, 08 Dec 2022 10:31:11 -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=+ecp1Y9KPy+kDAop1/WRITl7b0nkz2WoIf90DV196rk=; b=ePknV9D64SAqnSxRHkE514YZtiu5q9r6ovssx1zBnZsDJxmLaWxa9+pvv0qw+Al2tE 7icHc5bwiDk3Nh278NW1BN6NTObpkWNBsuw4SLzy33uI3jNOTkX3GJcPWXjyICJxc52V BrN7yFJ2Xsa7MwRxwsYa8OpinY4jgjm+mae9y2dMIfKcxxZ/wIB7+JK4M5R+9x01V/c8 R0b+vDqI9s08oTBaXlYnkgxbr1B5BIGwtwNwOXTybh3WFb1LO2cr//CYmmjb1C96h8ys LQ9EHbwRMcaZKB0SudjJO2N46odtJxuKV5xEPWLrXB2uOjL6Ah9qYL7H48NmIQt9b2XN fo6A== 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=+ecp1Y9KPy+kDAop1/WRITl7b0nkz2WoIf90DV196rk=; b=8F2Rwkwx9Nvc1yzxquflWxn/Yz2UB11MShW85tals2GxqSWTWxCPmjUHIJ0oojR0WV FuQAo+tbHS0moClLDca1PYIA14Fwf0ERFnzaakoCUXyqZZ8W5+aF7F9WTOcq+NRaCcby DNpPwVo2BaJ1wA8H+lrjhVtFImpNhTSCQ6zdBawFcTQgRV9vGzbc0AJ2vQTUz2Wue0LV h5K04/5+bHqsFGUWq0gQ/0GuLG2RByaZMQN9ARWZjV/zWBo1+Fgg0VwoUwWcFP0eiWxi v+ugtNKHf4MJ9H/YNvivvLEPfxxZVzGtLqrkAcjuU5U9STfu4FGJivdSrIp20w27O9vK p3uA== X-Gm-Message-State: ANoB5pmJR6mnvmaV6RGFycsqYbLQC8oKYBo8ZlLpZRhuIu+cku7dTklM qveTsmohvXnLqz8dJPJgdWOKObxJKFg= X-Google-Smtp-Source: AA0mqf6CFCCaWhBMhnZIhSSBXCFYdLJlvNU+Ql+n5K14MgA3Lj/YlgpT7Bt6I5rmS1doJMxUiQ7kKQ== X-Received: by 2002:a05:6808:1804:b0:35e:22a4:883b with SMTP id bh4-20020a056808180400b0035e22a4883bmr1770775oib.38.1670524270213; Thu, 08 Dec 2022 10:31:10 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id m11-20020aca3f0b000000b0035a81480ffcsm10766076oia.38.2022.12.08.10.31.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 08 Dec 2022 10:31:09 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , haniel Bristot de Oliveira , Dietmar Eggemann , Gal Pressman , Greg Kroah-Hartman , Heiko Carstens , Ingo Molnar , Jakub Kicinski , Jason Gunthorpe , Jesse Brandeburg , Jonathan Cameron , Juri Lelli , Leon Romanovsky , Mel Gorman , 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 v3 3/5] sched: add sched_numa_find_nth_cpu() Date: Thu, 8 Dec 2022 10:30:59 -0800 Message-Id: <20221208183101.1162006-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221208183101.1162006-1-yury.norov@gmail.com> References: <20221208183101.1162006-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org 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 --- 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..e515dcf44816 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -1764,6 +1764,8 @@ bool find_numa_distance(int distance) * there is an intermediary node C, which is < N hops away from both * nodes A and B, the system is a glueless mesh. */ +#include + static void init_numa_topology_type(int offline_node) { int a, b, c, n; @@ -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 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]), 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) From patchwork Thu Dec 8 18:31:00 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13068655 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4114EC001B2 for ; Thu, 8 Dec 2022 18:31:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229918AbiLHSba (ORCPT ); Thu, 8 Dec 2022 13:31:30 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46764 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229840AbiLHSbO (ORCPT ); Thu, 8 Dec 2022 13:31:14 -0500 Received: from mail-oa1-x2d.google.com (mail-oa1-x2d.google.com [IPv6:2001:4860:4864:20::2d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EE2D6AE4CA; Thu, 8 Dec 2022 10:31:12 -0800 (PST) Received: by mail-oa1-x2d.google.com with SMTP id 586e51a60fabf-14455716674so2807284fac.7; Thu, 08 Dec 2022 10:31:12 -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=d0/IgShbjb7qZAYWczuxoDmDyDdccuNPQ9P2AVi15HY=; b=lOxPMsbFDjwHG7HHR/orp+Pa1RS39Ze8na4rbdhPw189WP/MM4eBBehW1SZExmZPxq tiJirumWDNQOl3hPWfZpEdC3kT/L0/8Iw3MPpHUq36+mlsJIJ3NErF0CyEoEk24teAvb jv8iIoRKaccmPycGlitSJg/uRywRLWiunQxdbZNNXpBEWYpcieBXXwn8Sc/mwlKRGSzx 8wZo5ds/TIytpQjbzsy5F2LPl0IQFPVHI73htiuJVtdt5VQT1ZP2shA9/xBeLI67XWSt 19tRLmVoMARQt7scuWD50mPic1sJvH3poXZ9vPehyb0eRK+UXa0cZyII2ssgPYKNiwVG nNKA== 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=d0/IgShbjb7qZAYWczuxoDmDyDdccuNPQ9P2AVi15HY=; b=KvNdyOpxI2fnsWBIpd2tUzLilvh8efd9M47MLT0A0YBdFcGPKHVTzyaNkGCxtB6j73 NB2P/WR350FJI002dV3+uGPLBaLF2zwq5xKYrt7VdtzJ9EyzGyx8whdXFMbyjvnmAPa9 ZLmAhHZLwv8XfxO40cJ/HlPGD4H7Ggdo1gnyGP6Gb05dAjSfipW19AOxiTHg26NIauQU MEHqvFAHUiJkobCC7H9MTYE3V92czGhfP4/RKRKM7/sqREh05tXSe5OuiXObS7E9YW+y tJVXIQJMWMBODC4X2erNQlKhP6V8SJyUmN2Y8NC1ILvaxluErgk0HSKtOwBTpozBYKv2 ZCow== X-Gm-Message-State: ANoB5pnAG1L2fFX5vJVkjxfPmwYIPPPtF8bxhE+neFJWSFnFazezmOUz L3CtvSg7Sgy0h3A/cbdra+KfalIcY+s= X-Google-Smtp-Source: AA0mqf5isVkvLJVjOx5VBCgzSb+tYVQchORCS9bPkl13W6aETbe07HI49CIJpRycmeydxnnPPM4t5g== X-Received: by 2002:a05:6871:4683:b0:137:3ada:7249 with SMTP id ni3-20020a056871468300b001373ada7249mr1586685oab.54.1670524271939; Thu, 08 Dec 2022 10:31:11 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id m24-20020a056870a11800b001447d74a58esm8451783oae.8.2022.12.08.10.31.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 08 Dec 2022 10:31:11 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , haniel Bristot de Oliveira , Dietmar Eggemann , Gal Pressman , Greg Kroah-Hartman , Heiko Carstens , Ingo Molnar , Jakub Kicinski , Jason Gunthorpe , Jesse Brandeburg , Jonathan Cameron , Juri Lelli , Leon Romanovsky , Mel Gorman , 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 v3 4/5] cpumask: improve on cpumask_local_spread() locality Date: Thu, 8 Dec 2022 10:31:00 -0800 Message-Id: <20221208183101.1162006-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221208183101.1162006-1-yury.norov@gmail.com> References: <20221208183101.1162006-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Switch cpumask_local_spread() to use newly added sched_numa_find_nth_cpu(), which takes into account distances to each node in the system. For the following NUMA configuration: root@debian:~# numactl -H available: 4 nodes (0-3) node 0 cpus: 0 1 2 3 node 0 size: 3869 MB node 0 free: 3740 MB node 1 cpus: 4 5 node 1 size: 1969 MB node 1 free: 1937 MB node 2 cpus: 6 7 node 2 size: 1967 MB node 2 free: 1873 MB node 3 cpus: 8 9 10 11 12 13 14 15 node 3 size: 7842 MB node 3 free: 7723 MB node distances: node 0 1 2 3 0: 10 50 30 70 1: 50 10 70 30 2: 30 70 10 50 3: 70 30 50 10 The new cpumask_local_spread() traverses cpus for each node like this: node 0: 0 1 2 3 6 7 4 5 8 9 10 11 12 13 14 15 node 1: 4 5 8 9 10 11 12 13 14 15 0 1 2 3 6 7 node 2: 6 7 0 1 2 3 8 9 10 11 12 13 14 15 4 5 node 3: 8 9 10 11 12 13 14 15 4 5 6 7 0 1 2 3 Signed-off-by: Yury Norov --- lib/cpumask.c | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) diff --git a/lib/cpumask.c b/lib/cpumask.c index c7c392514fd3..255974cd6734 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -110,7 +110,7 @@ void __init free_bootmem_cpumask_var(cpumask_var_t mask) #endif /** - * cpumask_local_spread - select the i'th cpu with local numa cpu's first + * cpumask_local_spread - select the i'th cpu based on NUMA distances * @i: index number * @node: local numa_node * @@ -132,15 +132,7 @@ unsigned int cpumask_local_spread(unsigned int i, int node) if (cpu < nr_cpu_ids) return cpu; } else { - /* NUMA first. */ - cpu = cpumask_nth_and(i, cpu_online_mask, cpumask_of_node(node)); - if (cpu < nr_cpu_ids) - return cpu; - - i -= cpumask_weight_and(cpu_online_mask, cpumask_of_node(node)); - - /* Skip NUMA nodes, done above. */ - cpu = cpumask_nth_andnot(i, cpu_online_mask, cpumask_of_node(node)); + cpu = sched_numa_find_nth_cpu(cpu_online_mask, i, node); if (cpu < nr_cpu_ids) return cpu; } From patchwork Thu Dec 8 18:31:01 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13068656 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id CCE01C10F1B for ; Thu, 8 Dec 2022 18:32:01 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230023AbiLHScA (ORCPT ); Thu, 8 Dec 2022 13:32:00 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46932 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229894AbiLHSbS (ORCPT ); Thu, 8 Dec 2022 13:31:18 -0500 Received: from mail-ot1-x329.google.com (mail-ot1-x329.google.com [IPv6:2607:f8b0:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E0279AE4FD; Thu, 8 Dec 2022 10:31:14 -0800 (PST) Received: by mail-ot1-x329.google.com with SMTP id l8-20020a056830054800b006705fd35eceso1362463otb.12; Thu, 08 Dec 2022 10:31:14 -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=k44aAa8w+g09OTVc3BtKD/GeVUZOQmCH52b2zgD7vNE=; b=kJnn8W88eYCSTCdaionDWs5lanPHeksZRwOquRqQpTBf+8LE/3uQ6Kb7qIiD+I2JFB NXC1hNgGIMNa4RtjALbAPIj6NPXaAplZSYXFpEgFkCE4Kuvr62KzE9Db6q3E1uaCKomN EIMjj/zqnYLqPfVe+aWersTJ5haEMRKBNYkkM/2+XbFQAQ4YHH1RxjnPmpxvHaUnjvU2 ZRhNYhUEHZFxgLz1LFrWWFbSfevTzqa0HvdTj1q3AuGflLvTvBTsVo/X2HEusft2UGsW Q7Ih9kt50RqgUeUUITRHBrHUwXI7bvDSkpH02dZ/dQN5XFutYGi6lP5X4TUXs6MCZIRn fFTQ== 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=k44aAa8w+g09OTVc3BtKD/GeVUZOQmCH52b2zgD7vNE=; b=AS8kMgIt5wpLTCjPlxvwekueIeibvqTLzAiC78348nVkbvNKMVPaVf/BuvXISj8gIL n52qWIaJqzpSMTeW7w/ekN7bmfTuuknKFGHKcY5hGxl2cYv8aQaVL3zqLr1YSzFy4WWt pjhBiYSSfRhBjMx4YLDsPZMU3Kbx3dOp/GaVkHrBNE20uieS3bsalN8Ihuzh7V/z5cEO D5m7xqaXG5EyZeyMGbU5H3R6SXdipq4xRcN5gz/Ee+4EPXotrSuWq6wNhR7BsABCJpUa lbwg6zTWwLlwp3f8VYtCidQHUrxf+vxhO2rVKJQKbJdTyxTNHKYoD/q7wbRiDwYL/FdL 0iLA== X-Gm-Message-State: ANoB5pm12qik4BhbF3BA73eNYRQcFcAWtjIWX7mKVdMPpojd2Mm+/pke TLxhxkJN2FeiA9ZAGNMy4cg9xmPzPG8= X-Google-Smtp-Source: AA0mqf5qkVMTNLwYrHEwSHnT1jBNeG/TVLvAyXhtP9eQdTstA6d6OIfcNnz3oSL3kXGPlxhIOl1IdQ== X-Received: by 2002:a9d:5f02:0:b0:66d:a5fa:5c54 with SMTP id f2-20020a9d5f02000000b0066da5fa5c54mr1449103oti.1.1670524273395; Thu, 08 Dec 2022 10:31:13 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id x26-20020a9d629a000000b006705e35c4e2sm3077138otk.35.2022.12.08.10.31.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 08 Dec 2022 10:31:13 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , haniel Bristot de Oliveira , Dietmar Eggemann , Gal Pressman , Greg Kroah-Hartman , Heiko Carstens , Ingo Molnar , Jakub Kicinski , Jason Gunthorpe , Jesse Brandeburg , Jonathan Cameron , Juri Lelli , Leon Romanovsky , Mel Gorman , 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 v3 5/5] lib/cpumask: reorganize cpumask_local_spread() logic Date: Thu, 8 Dec 2022 10:31:01 -0800 Message-Id: <20221208183101.1162006-6-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221208183101.1162006-1-yury.norov@gmail.com> References: <20221208183101.1162006-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Now after moving all NUMA logic into sched_numa_find_nth_cpu(), else-branch of cpumask_local_spread() is just a function call, and we can simplify logic by using ternary operator. While here, replace BUG() with WARN(). Signed-off-by: Yury Norov Reviewed-by: Peter Lafreniere --- lib/cpumask.c | 16 ++++++---------- 1 file changed, 6 insertions(+), 10 deletions(-) diff --git a/lib/cpumask.c b/lib/cpumask.c index 255974cd6734..c7029fb3c372 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -127,16 +127,12 @@ unsigned int cpumask_local_spread(unsigned int i, int node) /* Wrap: we always want a cpu. */ i %= num_online_cpus(); - if (node == NUMA_NO_NODE) { - cpu = cpumask_nth(i, cpu_online_mask); - if (cpu < nr_cpu_ids) - return cpu; - } else { - cpu = sched_numa_find_nth_cpu(cpu_online_mask, i, node); - if (cpu < nr_cpu_ids) - return cpu; - } - BUG(); + cpu = node == NUMA_NO_NODE ? + cpumask_nth(i, cpu_online_mask) : + sched_numa_find_nth_cpu(cpu_online_mask, i, node); + + WARN_ON(cpu >= nr_cpu_ids); + return cpu; } EXPORT_SYMBOL(cpumask_local_spread);