From patchwork Sat Nov 12 19:09:43 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13041334 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 B226EC4332F for ; Sat, 12 Nov 2022 19:09:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235083AbiKLTJ4 (ORCPT ); Sat, 12 Nov 2022 14:09:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52878 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234867AbiKLTJw (ORCPT ); Sat, 12 Nov 2022 14:09:52 -0500 Received: from mail-qk1-x733.google.com (mail-qk1-x733.google.com [IPv6:2607:f8b0:4864:20::733]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C13E518343; Sat, 12 Nov 2022 11:09:51 -0800 (PST) Received: by mail-qk1-x733.google.com with SMTP id g10so5208830qkl.6; Sat, 12 Nov 2022 11:09:51 -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=jqi0y5qkypc9adsfTZBBaaEM1uXQiP6cacGrIvjX+Yn7th7DyMhhn6WjwvLBDwm3UH Dr3CKiYhAZBYhPbC7UpI5jWEoxjIIIFg/JWGl1Eye/3a0CynIRpXFVg9TD1q6uopzRoJ Vsq33cZkSBCr4vnHE4HXBe573KZExdKOHUX7cXN/kCZki2p3TND1pkf9FlGpHDVADIik TxaaupPcIX25wyhXpg6M+zztPNyIPtJyui3q+T1Ka/CsVtxO75IDdujNAkUkZaakTnE1 j+S2Pzj2Hdwy7k1OTOCRXL4hrBV1p/6ja7af6cva4pmW/8hY9EmnC/eSsXcWsPe9IVKA Y3aA== 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=fbIIvag132HibuKlZ2EF5Z3A2bZuzqq9DnLkjK315yXx7m/8AxlmyeUEmKcGvZu5+w 6oc23b42CpgdUro4iU8K2RM5eNjLS17uvPF/dIBFjAMgnRhoVNXY5VpndHpfIwRydYH0 kVEZJ8RYUgv8yY01GinPRV3RxgLi3pM0CQbdZXIw5wbdFGrRV5AxjnbLp9yAE+dUMIkJ E22L9bBq4LYZtJztJz80mUI0VEtodKJ8YPEZOPYpR/OQAURnRLvYYEj9Vi0Ae1L0v3Vc Rm+1g3+80i/SwIrQKdWprpGJ4C3TrHCtWZDB12qUin2Y9LVr3mVkQk4+mjSu/Tww5TiW cbBg== X-Gm-Message-State: ANoB5plkapyAN2cvPnOjgmYIqsiSsqXCK+KfLhA6VTU0p+KzmD2Ow8Ks xkcv80nKGNdNwc1kaVt5RXiv+zAN8CA= X-Google-Smtp-Source: AA0mqf52dCCruD9AxaYmeiO4/LpirAsSd1f8y58a4DQKi1AgaAaoh3ZaiVGFak7D7QWwdSzq6HIXQg== X-Received: by 2002:a37:95c2:0:b0:6fa:4749:cb87 with SMTP id x185-20020a3795c2000000b006fa4749cb87mr5742709qkd.619.1668280190642; Sat, 12 Nov 2022 11:09:50 -0800 (PST) Received: from localhost (user-24-236-74-177.knology.net. [24.236.74.177]) by smtp.gmail.com with ESMTPSA id bk40-20020a05620a1a2800b006fa4b111c76sm3551789qkb.36.2022.11.12.11.09.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 12 Nov 2022 11:09:50 -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 v2 1/4] lib/find: introduce find_nth_and_andnot_bit Date: Sat, 12 Nov 2022 11:09:43 -0800 Message-Id: <20221112190946.728270-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221112190946.728270-1-yury.norov@gmail.com> References: <20221112190946.728270-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 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 Sat Nov 12 19:09:44 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13041335 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 48FE8C41535 for ; Sat, 12 Nov 2022 19:10:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235094AbiKLTJ6 (ORCPT ); Sat, 12 Nov 2022 14:09:58 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52884 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234967AbiKLTJx (ORCPT ); Sat, 12 Nov 2022 14:09:53 -0500 Received: from mail-qv1-xf32.google.com (mail-qv1-xf32.google.com [IPv6:2607:f8b0:4864:20::f32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B1D2917E30; Sat, 12 Nov 2022 11:09:52 -0800 (PST) Received: by mail-qv1-xf32.google.com with SMTP id mi9so5532318qvb.8; Sat, 12 Nov 2022 11:09:52 -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=EWbVcRK6VQQtBX4Tw7NbZb11qrqsmGD9Jz7Ot3MeTptcgDZLc39mF82hrl6ywjrbGO 5DByMs2+I/BKQAcmYr+M1oulbaFFR6fvvCL1VeoXyITEu+c7LOlxKBZr/B1yiagKsHz/ N9iZiiGa0dvk/iIMA1qC+r9oxhwONnN+biuByTPkrUqgI2iIW2l87LwX6tgI3lNXwjqt +vNTOOL2/FmFLVwQhoQjYogKD5yIQK2zy4+QlvaJ0iAP/an3r6WmvEDR1+gE3BWwQEL0 vsSsbuoMlUmnsQq+bNA0hKDexmx9FLzjsxm5BZN2hfp+NiTZzGbAP19s3mtS0XTYkAXn Dq3A== 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=wCpC/n214E3DtoMznShvqVU71CbY5BQJYafdvsrL/XEfI9JOq4kUJyAHndkuK3W8hR 800r5o3c3lePFKoH0ZNPBf9ZoS0kqa8GBlR+AfVmKrwDf7x6+aBmGuERJPLBNsK5CPo8 H9UUHNijGPIUh/5v5cLCvpCAYI8DcYOWpOTsxUBXBDvCi9T+2FAguGrdgcRrVSqHEV67 iV6+fxPXF8JmiXISGBOuLu/idSoFYpPfCO+n5UIHMwtsIZ23e/XpdcX3DiTWBidSS+xv ZJBwxFOZd5FdYT/iPB0Ja09RL65GBgW47Uz1pqhxFjzEMW+XoI1hUk06t2BsKmpNcAAC dJEg== X-Gm-Message-State: ANoB5plekUzv6XiBZHMB7rg9uCESn9Z2VEeXU88Rr+8aFZmziJLYisDC wKIFYyyjA2NPSZtRvVT1v/IqX4opA+M= X-Google-Smtp-Source: AA0mqf7QvfhjET/seOjh75TRhk2tq5bA2F/OeMmuwwt/hZZHlDiRotzdRhTdoZGFvZRyZDq5pElPhA== X-Received: by 2002:a05:6214:428f:b0:4bb:d68d:2744 with SMTP id og15-20020a056214428f00b004bbd68d2744mr6920529qvb.5.1668280191620; Sat, 12 Nov 2022 11:09:51 -0800 (PST) Received: from localhost (user-24-236-74-177.knology.net. [24.236.74.177]) by smtp.gmail.com with ESMTPSA id f2-20020ac87f02000000b003a4c3c4d2d4sm3192944qtk.49.2022.11.12.11.09.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 12 Nov 2022 11:09:51 -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 v2 2/4] cpumask: introduce cpumask_nth_and_andnot Date: Sat, 12 Nov 2022 11:09:44 -0800 Message-Id: <20221112190946.728270-3-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221112190946.728270-1-yury.norov@gmail.com> References: <20221112190946.728270-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 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 Sat Nov 12 19:09:45 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13041336 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 6C9B4C433FE for ; Sat, 12 Nov 2022 19:10:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235102AbiKLTJ7 (ORCPT ); Sat, 12 Nov 2022 14:09:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52890 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235010AbiKLTJy (ORCPT ); Sat, 12 Nov 2022 14:09:54 -0500 Received: from mail-qv1-xf36.google.com (mail-qv1-xf36.google.com [IPv6:2607:f8b0:4864:20::f36]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D3D4918343; Sat, 12 Nov 2022 11:09:53 -0800 (PST) Received: by mail-qv1-xf36.google.com with SMTP id x13so5551917qvn.6; Sat, 12 Nov 2022 11:09:53 -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=tqEEjsLXHTNbUPsRH66Vwh3/Ffbwf/TAdluZMVix8HU=; b=OrIPZw6dnMFquB03z7bujIZ4SI0QmPWeWr/QWFL6/agYtrCvFvJrqwUBpjJDm0chv8 8fXqSEPeJifaigMJU8OzNcsqScMfwHgsJFmHfvH/WG/gpiopZqbQcWLVtjGGZe1kVfJD b9yOfiEWqX7WT/nsRQyydtfK7PBBELrmtMEMy2dP+nNjocxIOi05IR0FovguKKVaSwYj +dvVLcb2Vl93FH4WmyqtOC6sEOw1r1/NLDxY7qvylXUvyzy22CDtP9Ip345YFnFdxo8a 7oEc0R4ujegaVJNhUILMXAKkRjoFYPMFxZJ2lv0nORAvLixe1yR+coZ5UQE7HgI4cCFF HV9g== 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=tqEEjsLXHTNbUPsRH66Vwh3/Ffbwf/TAdluZMVix8HU=; b=WaoBRAkNmQE4jYeU19hgsYduj+RqUv3BL9XL5kfIXbf7nRB1JyqkVYE8FzI0Cx6Wdx OXMIRVXTv/6lRhTH5/Tr37GTDOICh+rM4EpfGTc8j1/ZSRMW6wXn1gT76uDrNeChK72g 2a8M1rbGdXUP91u5509iyn7NJ9at3cNfcceMG2VOLcyd7NT0gdN6yt/gLb1kFkpKmMFb ZrwsMa3H4bBw1qwFTEyWFc9YS1UZ4s6WNcAkhVSpVMsgGpO9JUMGkqEgsn4XSREYM29N gSB0Ir3cA4QH49ufeg60IRQSNsionHR7zK4NDYphg70IcSo1JLshwmv45Nb0X+RbcNAM 711w== X-Gm-Message-State: ANoB5pmhQzGhVDCRVAUFf5lo9F9RTG08aSmt5jN+L7d1F8UZb/hy7CTb MgQCEeZWmeEnQEhMGHnxm2k45NRY6C0= X-Google-Smtp-Source: AA0mqf5zShoEJOpwckW97mUU2Be2DzkQdB2sB1bJ8yi9Wk/kCY15bhTOdN9nciVVVaKwzW6uWRIrjQ== X-Received: by 2002:a05:6214:932:b0:4bb:cb21:df19 with SMTP id dk18-20020a056214093200b004bbcb21df19mr6772654qvb.85.1668280192703; Sat, 12 Nov 2022 11:09:52 -0800 (PST) Received: from localhost (user-24-236-74-177.knology.net. [24.236.74.177]) by smtp.gmail.com with ESMTPSA id r1-20020a05620a298100b006ecf030ef15sm3570207qkp.65.2022.11.12.11.09.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 12 Nov 2022 11:09:52 -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 v2 3/4] sched: add sched_numa_find_nth_cpu() Date: Sat, 12 Nov 2022 11:09:45 -0800 Message-Id: <20221112190946.728270-4-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221112190946.728270-1-yury.norov@gmail.com> References: <20221112190946.728270-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 | 55 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 63 insertions(+) diff --git a/include/linux/topology.h b/include/linux/topology.h index 4564faafd0e1..b2e87728caea 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 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..024f1da0e941 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,59 @@ 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, NULL, node, cpu, 0 }; + int hop, ret = nr_cpu_ids; + + rcu_read_lock(); + k.masks = rcu_dereference(sched_domains_numa_masks); + if (!k.masks) + goto unlock; + + hop = (struct cpumask ***) + bsearch(&k, k.masks, sched_domains_numa_levels, sizeof(k.masks[0]), cmp) - 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 - k.w, 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 Sat Nov 12 19:09:46 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 13041337 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 8F0D6C4321E for ; Sat, 12 Nov 2022 19:10:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235098AbiKLTKB (ORCPT ); Sat, 12 Nov 2022 14:10:01 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52902 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235082AbiKLTJz (ORCPT ); Sat, 12 Nov 2022 14:09:55 -0500 Received: from mail-qv1-xf29.google.com (mail-qv1-xf29.google.com [IPv6:2607:f8b0:4864:20::f29]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 17E8D17E30; Sat, 12 Nov 2022 11:09:55 -0800 (PST) Received: by mail-qv1-xf29.google.com with SMTP id j6so5516358qvn.12; Sat, 12 Nov 2022 11:09:55 -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=J0b0MU4lkGEXnXmOdosQFkNAakaHFGH3KxRmUtgL1P2al7Bklhj93oiCUKf2JCUCj5 oRbpR/1t7PQLl6/UvRLUOTIuyUdncAL5/yE5RvRusGwe3OTAV4bzbqzSIycPc3wgrc7Z xXohwCCcy8x686DW6W1DdRdUjMuplkiqSIfgzSohbZUIWCFAFgdMzg2Fu0bwH19bQLQC v0Y0RjN2jWDdGlL4XMldpgVLcZnYRtgFTimcVd7fM/3BXXK4SBHfy0G57g8tj+lFZQsy WcihYikQiL7hFjGwoCCFyqEVdzC9ha12z8CvTrg44hsq3cE0bPW0IWtS1VHzafkdHlKW zv1w== 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=0PDBiMK61JszYBdPZ3HBlmY+KWXSmsD4xDk3/H1eEFossjr4yLBlSqxVnOCyx+esON Srj/EiCkSBjzW9nNHcac3g9sy4SVvVxfG+VhIIZQKJ1EwMFv1xU/jU3v/eFbOenifbVn eDaf5So4XJUfT2NxKjj7Rkep2AI27De7oR8fy/FPk+9Dwv5NMrJdfZ9jRAIQN63MCr/q +dMSSO2964kGoB+Iq1CYb+l3hRispKhCvU3w+9YAvIaA7ttr0OqVfaBt88MmwZF7Lajd EVYsii7xXfOm2dhtjoeym/gwjbpu+9C3XjYlhXLGb7OyKdN6UWW4aQTUWkyElgt+F9s7 jbwQ== X-Gm-Message-State: ANoB5pkQIsesAllBoUddeUCbMk1Pz9HjsH6OQqp8VF8lcIKEME2THs82 b5R4rVrDGbZ1uruWYxny0IgsmYbdt80= X-Google-Smtp-Source: AA0mqf6105pixBNLmobZKxKFU+O3f3FIJRVWP8gdRjg3LLp/ywJgV6u55Uu/uUndEkpCeXzVhu4ktQ== X-Received: by 2002:a05:6214:102a:b0:4bb:8ef1:b544 with SMTP id k10-20020a056214102a00b004bb8ef1b544mr6871877qvr.99.1668280193936; Sat, 12 Nov 2022 11:09:53 -0800 (PST) Received: from localhost (user-24-236-74-177.knology.net. [24.236.74.177]) by smtp.gmail.com with ESMTPSA id bp44-20020a05620a45ac00b006f956766f76sm3577980qkb.1.2022.11.12.11.09.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 12 Nov 2022 11:09:53 -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 v2 4/4] cpumask: improve on cpumask_local_spread() locality Date: Sat, 12 Nov 2022 11:09:46 -0800 Message-Id: <20221112190946.728270-5-yury.norov@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221112190946.728270-1-yury.norov@gmail.com> References: <20221112190946.728270-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; }