From patchwork Fri Nov 11 04:00:24 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13039607 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 7BC85C43217 for ; Fri, 11 Nov 2022 04:00:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232446AbiKKEAf (ORCPT ); Thu, 10 Nov 2022 23:00:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50658 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232080AbiKKEAd (ORCPT ); Thu, 10 Nov 2022 23:00:33 -0500 Received: from mail-oa1-x36.google.com (mail-oa1-x36.google.com [IPv6:2001:4860:4864:20::36]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CA524663D0; Thu, 10 Nov 2022 20:00:32 -0800 (PST) Received: by mail-oa1-x36.google.com with SMTP id 586e51a60fabf-13b103a3e5dso4339761fac.2; Thu, 10 Nov 2022 20:00:32 -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=MPqmuncXUCU3pW/zVD2ThZ+OJwOyZGXsie5WSsI5Oh8=; b=d7kNbAR+XN+55Y78lTPX/AcgKjBIcFtiVfpbHNR6fGXUjfu0fc6N5DgXL0DPt0FOsG mImOMTGRKD058s5Opn/bS8AP/Ww/c2LPjMT2PYTrDGhjnHCSAp+roN4qibzTOjOjCEFx zXEm7Rs8i3yogDI2kcQcd3yTmA/g+QL12Zknka3omfARYd79Es/iCaqA0kfl84XXl+/m 3GnoRBJHtStYrnBhiN/D2SFQbxYhTNMKe/Bmnp0GHiX6G6zpmM8DHhrNg4vDGqkxfRpj Ld6pUw90Am+U6cuVRt4OMLMHWKe6hExyLLvuobAhWSQnOOKnFVLiMu/Zd8adV/WnXASP dHgQ== 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=MPqmuncXUCU3pW/zVD2ThZ+OJwOyZGXsie5WSsI5Oh8=; b=LXLjKKtYaoZ3X0vpEeYmHUPYrZihFSffQMpG40M6CioxC67Ogqm9LCpBFcA/r/gYA+ LP3wHxEGoL+4CJ0UcHQhxzhCunGADeMNUIAGu4eTExgmW/KDc1opU/9aL4p8xTDuaCnz H6w5hcNhsUJKRpYvpA0moVgLgABQt6oV8FpWEU4HwzrpiG/jEEa+Q5ZnfG9GF5zjYcWg BEMyIxWl3FmXkQNhK5q+B00YINIsgvDGj88o6/G6+vV7lV/9U6pxxkoGMe4KhBEZAz0i M3KS9D5OZX1Pw7MTrw0+7z1J+GLFVf8ZbvnGKXPB5jBCU9Prveg4nCod56+qTgdp+NJs 5vGQ== X-Gm-Message-State: ACrzQf2GYqg8VUfTSvYQr/Dge62q/67Ld86OCr9OtB6eJVHyiqeTOIj8 nk+VAsCuOt8mHAM01qIcaDcXUqUREac= X-Google-Smtp-Source: AMsMyM5Xsoo+HsbznS0m+wxPjY7H0NY3MsBKTiqPr4ytUF/Dly2hgMuLkd3Ju98TPQvPZZnrk5VooA== X-Received: by 2002:a05:6870:c98a:b0:13b:a8de:c248 with SMTP id hi10-20020a056870c98a00b0013ba8dec248mr2928387oab.99.1668139231805; Thu, 10 Nov 2022 20:00:31 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id c18-20020a4ac312000000b0049be423151asm435717ooq.34.2022.11.10.20.00.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 10 Nov 2022 20:00:31 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , Daniel 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 1/4] lib/find: introduce find_nth_and_andnot_bit Date: Thu, 10 Nov 2022 20:00:24 -0800 Message-Id: <20221111040027.621646-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221111040027.621646-1-yury.norov@gmail.com> References: <20221111040027.621646-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@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 ccaf61a0f5fd..7a97b492b447 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -22,6 +22,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); @@ -255,6 +258,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 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 & (~*addr2) & 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 Fri Nov 11 04:00:25 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13039608 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 3403BC43219 for ; Fri, 11 Nov 2022 04:00:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231234AbiKKEAi (ORCPT ); Thu, 10 Nov 2022 23:00:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50664 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232426AbiKKEAe (ORCPT ); Thu, 10 Nov 2022 23:00:34 -0500 Received: from mail-ot1-x32a.google.com (mail-ot1-x32a.google.com [IPv6:2607:f8b0:4864:20::32a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0F07F5D6B5; Thu, 10 Nov 2022 20:00:34 -0800 (PST) Received: by mail-ot1-x32a.google.com with SMTP id j25-20020a056830015900b0066ca2cd96daso2202114otp.10; Thu, 10 Nov 2022 20:00:33 -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=C0ZwMR2gCmjCo8DSne7eN5n31OgpWeA+QwMIe/AT+TA=; b=njrnJ9vyO0RH4SZFlia43XxDqyHL5yQxnEjslsS8ZZ3a5GZs+uHt38cWCH3yeLB2wP 3/XRVO24mTH44oADo2t5CL0gWPmfoI+1xX+nsXxEzOcZCWJapa3feyvL1zMBcn0bfjeS MIWz2sU5ap00WIDTAreMJcGd5UOzPPb+kxriJiYygVjEgUhWgAIU+71bscSS3PWSbZYr 3GfxqpbwHvbfHsN3ut6N4QyZa9WfrTgM5DWvoqgf1wggmuDGOkZhDKWSNU2SCMtQdzHX nBSQdVtvOkJbOdaY/zcvaIoD2BEs9xUJn/dukih3MTRNu7YHukem3oYf4vYzJR7Xaltg INzw== 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=C0ZwMR2gCmjCo8DSne7eN5n31OgpWeA+QwMIe/AT+TA=; b=zmoINtjTZ3s1dTQxW/LtxClLUl6Y9dmCPtoIERnV4VydfvqYPlAnew8+nVbxiGneMp VohVPTWdoEH2UlIfzR5vtEUZ8hptg1O3VfYIZNjKJncQFlIw+G+U96KvaLy35+s+DAqf hsEaGUeBXizlNzDxqS3WFLd4p/IjM4ZnIhZBZ19e4E9ad0Cc9grOk8uopBN0On3RfoJk bgI1WTN3SGQTSThZ6DxpTEI/y9XBY14pI7TpfDdfGFwkljmhkLJdjDc1rswV29egBYgY qrHr8rWMGoSq3ulsV1JjgzbE/JACqStjJy7XuomMJqWCGNfFmjii0UyTq8G2gb7C6O63 L//Q== X-Gm-Message-State: ANoB5pn8vffOcsH3w5D7HYal/t2OtJPnpVIsx9JnX8GhvG61s5p2xWCh 5aHmm0+ydWETnO8dK50ADII2QfXXuAY= X-Google-Smtp-Source: AA0mqf5hhOqnQ/9iobOUUSORsscwhDEjIDe4SzmcDj3oM9x9Nk6CTns4GtZKJUoomiMp0nstW9oSJQ== X-Received: by 2002:a05:6830:1212:b0:663:c55e:c5ac with SMTP id r18-20020a056830121200b00663c55ec5acmr374932otp.196.1668139233135; Thu, 10 Nov 2022 20:00:33 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id d74-20020a4a524d000000b0049052c66126sm471606oob.2.2022.11.10.20.00.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 10 Nov 2022 20:00:32 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , Daniel 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 2/4] cpumask: introduce cpumask_nth_and_andnot() Date: Thu, 10 Nov 2022 20:00:25 -0800 Message-Id: <20221111040027.621646-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221111040027.621646-1-yury.norov@gmail.com> References: <20221111040027.621646-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@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 c2aa0aa26b45..debfa2261569 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 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 Fri Nov 11 04:00:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13039609 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 44209C4332F for ; Fri, 11 Nov 2022 04:00:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232540AbiKKEAn (ORCPT ); Thu, 10 Nov 2022 23:00:43 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50670 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232471AbiKKEAg (ORCPT ); Thu, 10 Nov 2022 23:00:36 -0500 Received: from mail-oi1-x231.google.com (mail-oi1-x231.google.com [IPv6:2607:f8b0:4864:20::231]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6D34965862; Thu, 10 Nov 2022 20:00:35 -0800 (PST) Received: by mail-oi1-x231.google.com with SMTP id m204so3902408oib.6; Thu, 10 Nov 2022 20:00:35 -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=tzRDKkKs+46lV+ntk985L0+P6jvYS0wrm3ecpZliFYs=; b=EXI9KlBNRoNAC/HBM2t606C6k+BIKeV0yCiHoTnP+qKe2h/QdHKK058z8mFYDDYIlB ifkh+NI5b9E6h2EXFXvU85dmBLejYquO5VlXYt/3sRXdPsArf1afj7+1PSOQc5OJNxeR WpViD79eNh7CtAQmQ1AIZVuEQIYhkjGZUBl4ooje1+Dk006Ye6nXJ26TLl7vE19RoxLc NUCFe0PwYE2HPYsdwExhlg652eT5hm0Mv+hVE6/jc6eVjKam9IoGSJKONth26M0jCcbv 9fRQfEUyt1VKN206SefuI3XcTv+uPDvBFHZqYObM3nM0TicHayrNYGhqRaen7IjUlW9s HGUw== 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=tzRDKkKs+46lV+ntk985L0+P6jvYS0wrm3ecpZliFYs=; b=53x5w+Yq+gjxX1P/ZPTBR03t/lxVRyX174TSzf2rlnycEDbZxTe/aykhA9CdDWZBg2 tHnhQT4mWIFiBBMu9qOoiA6IG7qW392JjWOMT+7/mmvMa9qVw10B5JodpWEzAw7eQJax UnMGjY74OH3SLwsunf0I1FHPO/sGr2ZjAoF0EGKYM55NFVmJxgGUDk0exg65DNvXtIm/ QEr/BJbO5LyHTts4RO087Vz41dFibiLuHj9g6FfgJOi6mfdP48ir6Bga4yBTUOoq8GtT q7SY4rtMcgwZq0KPuRCttldh4NMLrPJ8EIWhjQpCM9pPBjc/6M/k/nRfORJ1qi/MlI/6 1iTQ== X-Gm-Message-State: ACrzQf1U0xF1UCaIz1xeznoInY09qVdOV2HAj+OnY0oS7xrab9VfS1V6 W/lmLbcryE2ic1S5TJq8nTgbbSKaPKQ= X-Google-Smtp-Source: AMsMyM5edoBCgwfjhFXNXfIH8nqgdrdgOPAuv0BCWrlhB7OpA0bg+Z74wF8buizABMtPnDl5vxADeQ== X-Received: by 2002:aca:dad4:0:b0:359:b842:e383 with SMTP id r203-20020acadad4000000b00359b842e383mr2859251oig.123.1668139234518; Thu, 10 Nov 2022 20:00:34 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id f8-20020a056830204800b0066101e9dccdsm591533otp.45.2022.11.10.20.00.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 10 Nov 2022 20:00:34 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , Daniel 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 3/4] sched: add sched_numa_find_nth_cpu() Date: Thu, 10 Nov 2022 20:00:26 -0800 Message-Id: <20221111040027.621646-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221111040027.621646-1-yury.norov@gmail.com> References: <20221111040027.621646-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@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 | 42 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+) diff --git a/include/linux/topology.h b/include/linux/topology.h index 4564faafd0e1..63048ac3207c 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 +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..c8f56287de46 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -2067,6 +2067,48 @@ int sched_numa_find_closest(const struct cpumask *cpus, int cpu) return found; } +/* + * 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) +{ + unsigned int first = 0, mid, last = sched_domains_numa_levels; + struct cpumask ***masks; + int w, ret = nr_cpu_ids; + + rcu_read_lock(); + masks = rcu_dereference(sched_domains_numa_masks); + if (!masks) + goto out; + + while (last >= first) { + mid = (last + first) / 2; + + if (cpumask_weight_and(cpus, masks[mid][node]) <= cpu) { + first = mid + 1; + continue; + } + + w = (mid == 0) ? 0 : cpumask_weight_and(cpus, masks[mid - 1][node]); + if (w <= cpu) + break; + + last = mid - 1; + } + + ret = (mid == 0) ? + cpumask_nth_and(cpu - w, cpus, masks[mid][node]) : + cpumask_nth_and_andnot(cpu - w, cpus, masks[mid][node], masks[mid - 1][node]); +out: + 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 Fri Nov 11 04:00:27 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13039610 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 CB44EC4332F for ; Fri, 11 Nov 2022 04:00:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232590AbiKKEAy (ORCPT ); Thu, 10 Nov 2022 23:00:54 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50676 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232483AbiKKEAh (ORCPT ); Thu, 10 Nov 2022 23:00:37 -0500 Received: from mail-oa1-x36.google.com (mail-oa1-x36.google.com [IPv6:2001:4860:4864:20::36]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E42455D6B5; Thu, 10 Nov 2022 20:00:36 -0800 (PST) Received: by mail-oa1-x36.google.com with SMTP id 586e51a60fabf-13ba86b5ac0so4346973fac.1; Thu, 10 Nov 2022 20:00:36 -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=rAYwtSDCtMl3bQjs+7iu2M5ENCXGl/6+Ww9pC2GxEs0=; b=KR4r6IzzTgskdFP8Rme0Hyk5hPZYO4XY3H0XE01oKcqWfSSxHwOgNQFildSqG7miMu yT3JwPbuvWTmFKTkqBKQ3pPoL8Qr1qekp0RBD3sCT5GSt5yT4GagQvb92eg1jLDMJNE9 mEZVf7PizTyM+S8UBZQU/ZzbNul6uDpvdFs7EgQoQUvTfZjbm0iEM+2jT5IsCcEPHgfZ t7eOAWf9iBX7Ta/BCpfo4G3yQNl/tNB7L7b3GrIQiTrSmXz5Y6ZvzjaVb132muydXYjO hlbs3i4lcl8LPuiN4zpEdO9/36k7BKO54FszguDYkNX3c5N0QauSjKVImNj9WgjS4YjD cp+w== 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=rAYwtSDCtMl3bQjs+7iu2M5ENCXGl/6+Ww9pC2GxEs0=; b=fF5296gH2wH1A/TEYr6UiAZ936uEmiHUL+pwzqFSJt3/WyGVPjVIr9VGMgie/hQorc 0JUTMZh34wYiLgFoKbGeH6O1rTjZ2joedQQdb3woGvnHilZ/zTg6tkpGVKW9uL7/DYgV TvNg0xSLv5GNzHry9LjivZZOkmLhK5F/T62qoZs/54PZ/NQhfrwSQkpnhiD23ys9/lD9 rKxpkbZjdBDNOSq+y0pHM+ZZSRZilGmf+wArtpkYrozmWt3Vchlih2DSPHwgVKQRCWw8 8U2Fw5jQMYsheFcBn1+xZbrJv6VqyazbZikax8OcCQQQVo5OGS2XbjXLT1BDdULqrV27 h92g== X-Gm-Message-State: ACrzQf3CKAUVaV/Osj92d35qIscTsaUvaryK+JjsHpU0QlzBpOV0KED4 ElBiHxoGKmGN/h2nN8r3pbaCvvsOcIA= X-Google-Smtp-Source: AMsMyM7w0T3Gc5xKhp78M0R9cxJeB1gkaRqv6qQOCQrqpAz1kyY3RoQfByDnA0VaqsZydQZuKSO/oA== X-Received: by 2002:a05:6870:d3ca:b0:13a:f0e3:cc1f with SMTP id l10-20020a056870d3ca00b0013af0e3cc1fmr2749422oag.164.1668139236062; Thu, 10 Nov 2022 20:00:36 -0800 (PST) Received: from localhost ([12.97.180.36]) by smtp.gmail.com with ESMTPSA id er10-20020a056870c88a00b0013b911d5960sm709668oab.49.2022.11.10.20.00.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 10 Nov 2022 20:00:35 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, "David S. Miller" , Andy Shevchenko , Barry Song , Ben Segall , Daniel 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 4/4] cpumask: improve on cpumask_local_spread() locality Date: Thu, 10 Nov 2022 20:00:27 -0800 Message-Id: <20221111040027.621646-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221111040027.621646-1-yury.norov@gmail.com> References: <20221111040027.621646-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org Switch cpumask_local_spread() to 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; }