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: 19226 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp1397686wru; Sat, 12 Nov 2022 11:17:21 -0800 (PST) X-Google-Smtp-Source: AA0mqf60T6cp1DClFNSMagudDI04aQKKpuY4L1DqknY2ijOJ0MsQKRT/ipFNmIj4H8xOLgnLybVN X-Received: by 2002:aa7:cb92:0:b0:459:f897:7940 with SMTP id r18-20020aa7cb92000000b00459f8977940mr5935045edt.168.1668280641157; Sat, 12 Nov 2022 11:17:21 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668280641; cv=none; d=google.com; s=arc-20160816; b=AoSWKdiP6MqypDLhdRvFVB8hZsQYWkgs9M90ZEdlQ+eQT8BGF2/y7+2xVE3PJ9L7Eh Q2bnGTGe1TlQpgZzc/yOqAiI08rV4pzz+IPf88Nbloqu1RzvxNOjOzVelPfCSjvVB2VF eyyJi/W0GMBgD6gi9v9NnXOTlHwQXf9QLgrjEFbKKkBEbgZ6jYBRruVzun8KN50OaW8l DPtZXMmp8wPdhotHsMGClkT/N21peL/VWadRhx/fXAWDGWZgAPy/HedjUSBKxBkikrQC +Vb/+wqdA/FberO6MCrGTiLmerJ/TVih+NvZalU1vBTrGhDFx9bP0Ph+XrxSC3GEetSc j57A== 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=MPqmuncXUCU3pW/zVD2ThZ+OJwOyZGXsie5WSsI5Oh8=; b=QKN13fLt+OH0d00kFwGyFK+FEz+/aYqq55r0auskWTp+DkadkKraA5xHy6LhkPMHRd BWzm3afse/lJnRcveNAmK7BEQXTtCEOTfSuZc0Ws1p1S3v6OKxh/dvNLc39GbCx+pU6V QYChz43HN04DmvLA0yrAGcqibjV06xOEds1OvnFFik/qDcnok3KvtYGJCjqcCrGqLhSc ZCqCHTC64XiRPpXhsmB1dbPyr9egt1VXNGOSjeWgIoiPtkIp8lWH3YdpNvnl7SuN6AMk PTHAx/dVdzL22UNR2iqmpLjik2vKNy/b14QU2W9AHCE/lrGSrB3oTdpvQ5U5YFEONgyq lKxw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=jqi0y5qk; 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 bv9-20020a170906b1c900b0076f0940cb28si4159321ejb.175.2022.11.12.11.16.45; Sat, 12 Nov 2022 11:17:21 -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=jqi0y5qk; 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 S235108AbiKLTKA (ORCPT + 99 others); Sat, 12 Nov 2022 14:10:00 -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-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 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?1749319041547169349?= X-GMAIL-MSGID: =?utf-8?q?1749319041547169349?= 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: 19229 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp1398892wru; Sat, 12 Nov 2022 11:21:37 -0800 (PST) X-Google-Smtp-Source: AA0mqf6YLrk5PnkUZExG6hAKWiM3aWdjkqX0xuqPN+UAxjH21EHONN94ThDaf3RKUiHkqKGZjmxP X-Received: by 2002:a17:907:f94:b0:78d:b11f:da01 with SMTP id kb20-20020a1709070f9400b0078db11fda01mr5893552ejc.615.1668280897084; Sat, 12 Nov 2022 11:21:37 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668280897; cv=none; d=google.com; s=arc-20160816; b=JQZFamOPbbOqQufxjX6ql+KRbVE6JQG/szcs5VXcCI6cMpEM+wXVHKGvo/+Z70B5FZ 2geDL9j/uOQbEGQs2blE8Axhw7jXx1oJ4gLS8YcGdUSEMduwOM3uHNJef1HLDNgENyrz UAHlxsM6NoKGJ9hHEBwUjPqpWEVkLsnBjoEDTvll9acCiX0uZo5XrhdPrGBHK64bntYL jPW26BPcWmrS0C1jMH0kBQRB6oiRAhEjAm+qvxve1hXmZrunexw8rCFT78CJgSbEowB8 7o/HcL7nEn9COpFefZVk3Yfw47qqcYu5YdzTvIiJQGxWENLjHzlVFSJ96MfuNGcF264n upDA== 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=C0ZwMR2gCmjCo8DSne7eN5n31OgpWeA+QwMIe/AT+TA=; b=tj5UmtkGXOYj1bV31GR4wlTAXt0xQu/ks1x4d0JuVQjNZdzoK31U3aMUvKZ/OJAsW/ GX6fN90dA4ZpjDiq5ZYHwvlvbe76D3IWET9UKnPgKeMcmDG/vBQ6EerbbQhCLto0YklK tFLb9AgRNI7S7gwc4+RR5NOEm3rbWHWm4tcnDs1DqElXOEwHmzUA3CF3oLdQx4heil/H A3POskX6enJ8lOlWYzVxajlHZSFPWgrLQzMh8J12R5igEpE4C+dEW5FiyeQjQtncb40V xCSs1Io6ZWvInJ1qBvb0hybGM8fClLbggXa2QXDrVByqKvJMMNJ3KGuPuYfRfSWlEtKs gIyA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=EWbVcRK6; 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 qk42-20020a1709077faa00b0077cfec3a52fsi5614692ejc.839.2022.11.12.11.21.13; Sat, 12 Nov 2022 11:21:37 -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=EWbVcRK6; 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 S235101AbiKLTKF (ORCPT + 99 others); Sat, 12 Nov 2022 14:10:05 -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-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 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?1749319310275829716?= X-GMAIL-MSGID: =?utf-8?q?1749319310275829716?= 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: 19227 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp1398744wru; Sat, 12 Nov 2022 11:21:07 -0800 (PST) X-Google-Smtp-Source: AA0mqf4CphhwDkkd+6Sn7/FkKDc+jPcElqnFQYtlXHC16jdd1aeQlw0c3GF9x7ESbFIt9nVUYLJd X-Received: by 2002:aa7:dc16:0:b0:467:7026:515e with SMTP id b22-20020aa7dc16000000b004677026515emr4879460edu.26.1668280866975; Sat, 12 Nov 2022 11:21:06 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668280866; cv=none; d=google.com; s=arc-20160816; b=GB5tl4EX57hEPat20NerJBhaUytvBE8VybeHoqT4X5h2SEYQCnUjtQcCrIw1Ub7S+f rUxvWr8/o7tctM6nkf+JqI5lJAC+ehKGauQTgIwZycKpff4ntsCQtSBIxuOMiwTtioW4 of8xsa0RjUhn4YHHhyhNVUDFZgvBdbW1qNJK+yKDYg6ciROojIh9MaQadTkNKWxf+sXr yt4iN1SFby5YeSGGL5m9kI9HGzS3j6gOGnvFAcoxNn79DNaK/W4ywC5OTnoL8tJA36Gb LvInlRXVkpZYfLAPkJIoabpkItlkACdgqFCycBOFzq3gINGOl7pSRmCgqDwj3/vnJzpI 8Jwg== 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=tqEEjsLXHTNbUPsRH66Vwh3/Ffbwf/TAdluZMVix8HU=; b=TGfZ9mJqZXuYUEL3iRv3pYat5Qx8BYmS4lV2NQaLLPtqonNzrUEMa7261EH8OGaQKf lNIdl6Z7GDlzgno59bPnnxKq1J9JzsSwyFes6E6+3xfAngmC4CowlnxnaEPr3jnLaBZi CMOVCC9Cf65AWNbEP4fkbd9l7NjZNPlLVwM0GSZxXDTIp9/4Rk9lRRGPVg4VITfGKpJk J8z9Y15Pm828SZZeCFsUGI0jaLW6G1cBY3D/ILc22L8l27+yFvzwpKl0L3kNPePIZNnj XX0ZY1z/N4pkFZ29q0tDfTSSHI1FNhX0nQ98+5OGX8hNRfxfScFSG5H2i6ST2ijlJM5K wytw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=OrIPZw6d; 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 xj4-20020a170906db0400b00782f3e3bb71si5653124ejb.912.2022.11.12.11.20.42; Sat, 12 Nov 2022 11:21:06 -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=OrIPZw6d; 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 S234007AbiKLTKJ (ORCPT + 99 others); Sat, 12 Nov 2022 14:10:09 -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-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 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?1749319278289731570?= X-GMAIL-MSGID: =?utf-8?q?1749319278289731570?= 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: 19228 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp1398875wru; Sat, 12 Nov 2022 11:21:32 -0800 (PST) X-Google-Smtp-Source: AA0mqf4ABmWvjz2g2+bRQpWOFm9eltefZZ5EvBB7G8wm3Gr7o3+OywngmaT45MfT9ygQN7bJOVKO X-Received: by 2002:a17:906:1c85:b0:7ae:ca2f:171d with SMTP id g5-20020a1709061c8500b007aeca2f171dmr5351646ejh.353.1668280892377; Sat, 12 Nov 2022 11:21:32 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668280892; cv=none; d=google.com; s=arc-20160816; b=O98RB9Wo32xxu0FFWTakUf/1Njr9D5wdwNfy/epwsHsGg4hI+5ZDVtTI12zFT/YrL/ Qp7nEQdbe7CibF1G3I3Kvl7DGHhwPTMroUX6jIr2V4kyYZDpkboJt/8jZnsmHhvoCaIT p56eg7ZXa4tqoqvKuFHgzrU2ZIiuFN1JytREqve6Zu6IMGu4H9/UhXcCFsAcqW2F3ZlM oNTk3nDc5wlDjZqHdyK5XjH6ANQ03aZLp10tBWmxLW7Z4NcMEpiGEd7l7Vfn5Jgh/BVq TX7r0tf+A3uL6Scn0gtQrf43IGtAHWkIPbjoXD5nQwL01exdX0QK6L7r4slpqus1s1F0 kHdQ== 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=d0/IgShbjb7qZAYWczuxoDmDyDdccuNPQ9P2AVi15HY=; b=dHZ120S+yzcBAIWG/ZaDLC5fGoifLlqtusCn98h4pCD0G/0DPcOKuUnuJzvdnCljgJ F8jjeMTxnp9xnk1T2nvyiX30vOOM4yxPEQKwl93yGMLhyCvwOcgj3BpU0cvrv3cADajw mCktq23CUNrnW8uPhtM23UVg9rkX3fqErtBzcwNzOW2oE7dWc/aAfag9e+RYYnOQIu+Y La2b++5n3rwcwcxnGG9iLdrM55xH3oY4HMC1fZF4kaioIOPIH+0fPl98URq1XYfBUTOI m9XBZwuMFIWRVFmINhihuOuEapmRAmeBZ6z8rdGb2GXHTbwVn5hE3e/UQCPIOlEXtjA8 TsCA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=J0b0MU4l; 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 a42-20020a509ead000000b0045cd50b7c65si4875673edf.266.2022.11.12.11.21.09; Sat, 12 Nov 2022 11:21:32 -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=J0b0MU4l; 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 S235138AbiKLTKP (ORCPT + 99 others); Sat, 12 Nov 2022 14:10:15 -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-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 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?1749318790339965777?= X-GMAIL-MSGID: =?utf-8?q?1749319304895938221?= 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; }