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: 18439 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp526183wru; Thu, 10 Nov 2022 20:02:18 -0800 (PST) X-Google-Smtp-Source: AA0mqf6Az0aq18tT/TQubZIusJIsiaIep5lqN1gVQrfoDPBCoRKMEeLV98FJoZdIoy7hZQqzStiK X-Received: by 2002:a17:902:ea85:b0:186:8bca:1d50 with SMTP id x5-20020a170902ea8500b001868bca1d50mr680587plb.158.1668139337755; Thu, 10 Nov 2022 20:02:17 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668139337; cv=none; d=google.com; s=arc-20160816; b=sxRmTSPlRLCCnZ+MLbj2GmVFJzjEOMWqJZJQDZmkWEeCEOziLGqVj37sAQ0JW01eqW sEL6srcMAjHo6SO2XoydFnh//umn4tPLFAWcb9DEtbKmYWvUCohZOSN+7kXqG8fuPzdt O9SW7pIWF/ZDxO9W2xsfmQlYoz8Dto3jgwofU1O/09WjLHxMAi9Ke+2nCWJfgpQJ+2v4 FJ+VVxsJ9paiaZniC2idrX1IPLzCB0PF1Oh7VD78hxHcaBNsH9sLbnQ42/xfEGJI108o Yquv1BqZICJBjyKNav0JQXkrpLLlNMJhUGywSUyyBRJvEYwj0XdmIiOsVWBwzYA3qOb4 YV8w== 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=EHrG9zePShHoi0NYyDc82DLi/G5gE2/hAaN5Zl4qyv3ORcYTxo/3/vlFbCNZq0zNMX YVwGe12KmMLbVzv2DrTyxUDpgr11pAppN7T7me9uxD5mK7UcwTIEEyDXVmEbwAA65nQf c+aL+nIqFCozm1gA70YXu+M6ETGtaOHy+BiNuFPl9SQ/oSQc+QFUA/1cdoO53BV6kV81 NDa4iHrXUokPmDoJcLdx41I8TLc49Ak4C9lcRKeA2gRnOjG0LeFg8EZx7LP6PqhEOyYQ d7zC341T5nGVYT+Q8TyPAUcfMwP9ENCu9TAZiC/JS8NuskLAy043X+tjgq2DURNymV4F 3AvQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=d7kNbAR+; 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 d2-20020a17090ac24200b0020d3a22af84si1362703pjx.186.2022.11.10.20.02.03; Thu, 10 Nov 2022 20:02:17 -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=d7kNbAR+; 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 S232032AbiKKEAp (ORCPT + 99 others); Thu, 10 Nov 2022 23:00:45 -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-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 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?1749170874260212902?= X-GMAIL-MSGID: =?utf-8?q?1749170874260212902?= 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: 18440 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp526207wru; Thu, 10 Nov 2022 20:02:22 -0800 (PST) X-Google-Smtp-Source: AMsMyM7MD9KnCUwDuXcDqULkdueZv69+IiLAzhEVQwoVlWnlgu+rAyRiGM78kX6z9AZz8XJJU9bP X-Received: by 2002:a17:90a:4fa5:b0:214:6fc:31cf with SMTP id q34-20020a17090a4fa500b0021406fc31cfmr3317970pjh.21.1668139341658; Thu, 10 Nov 2022 20:02:21 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668139341; cv=none; d=google.com; s=arc-20160816; b=D+jfhQwLqYHHeOASG4Cxh11Kp/Br5S8WZiD3jnrOJVC3MMKljDhKvz20IdfCaGtCuQ W7PKTiUH8hXy5nc7Um7qpkv0uodD9S0Xok9amqp/sGLAP1/C/Nv77B+g69m8852VjkB3 c9DpDJv3dO5x71D84gN7lf/8jAHjTlHuZ2ISZILF9M3/32QDpYQepyTS8tZvDnayeQ5Q GcXV8RlxZXnAl2bIYbAf3c+AVUwhm+atrwEK7vZrmlGTtpRJpkG7WGHCBNmeWxn/O9Ex uMjbR/ipvd7xG8mfLIvOllYFEgTKPN074jAM8OgMCYnow9whvDs2i0dGM6N+vWs/c7QG 9L4g== 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=OFk79zX9LT9afZAQrYfidTDjcKxDTomWhEf+pI+M63lmyz+5f8FrlvT2NuCaN3nmAY qcfUQOnWH+PyPcYy4c9Iw6KDYWLjjuDQN2RqgcrGRDseJDKC5+XONCVcezkeBL/56cs6 NoXX370WG1gbHBeFBlwuxozHvlN0Z7AYe4eVIkx2EKp6Z5IGk2t44FQKGV3I4hpg5Ixy JDL5uB+AKO/QReSuaD88LfwBdHvar7w3DnWNTDsrnILJ8G35VYAfbt2L9E7Uc8BDHTPo 4W5oyWZ6FB/s7EXOlNSIM+OVw/EO5aWNYl+9chPqkK7bkoluYl/L55vXlGl1HYRk8j5G YWaA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=njrnJ9vy; 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 z198-20020a6333cf000000b0046ef5b3572fsi1121798pgz.562.2022.11.10.20.02.07; Thu, 10 Nov 2022 20:02: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=njrnJ9vy; 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 S231710AbiKKEAx (ORCPT + 99 others); Thu, 10 Nov 2022 23:00:53 -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-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 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?1749170878030082192?= X-GMAIL-MSGID: =?utf-8?q?1749170878030082192?= 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: 18441 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp526853wru; Thu, 10 Nov 2022 20:03:58 -0800 (PST) X-Google-Smtp-Source: AMsMyM7Tk00sxnPbUH68cvc3iZjaioi0vVVpdboo3M5i6nni73e9xCH2tT/7I62knVWwNXqxUDA7 X-Received: by 2002:a05:6402:31ee:b0:461:9e1f:222b with SMTP id dy14-20020a05640231ee00b004619e1f222bmr4228417edb.312.1668139438070; Thu, 10 Nov 2022 20:03:58 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668139438; cv=none; d=google.com; s=arc-20160816; b=ep319yKJsD/n+PbS9plDxw1DeDPsf/FcFzRXcg7YjWFGKIbSyoRCxpO5PQ1q7JjurG q/wei5CmJtp91hV3yGCD/wuz53uDIVbuNWKotp9TNlAkFn9L+ENTgWuJtCyIS99bH89r BFa9H1lDDJe4ykl7UE8lRKoQgGuCNdI0HtHM50P0re+Dze8ceyBvQle8irEAj5orA4ex ToH08F0bHzYGEWFIGh55E1b6q82WoWmnsV51c+Q1rvtNeUSI1wl/eaaMU2NuXcs5p2gf WZOluny6jqsSHxS3rgbzmkorBnr5ezyF7w/55SuuIPqVTko5aaYjDsoa/YvX0lt9Oh57 1T9A== 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=tzRDKkKs+46lV+ntk985L0+P6jvYS0wrm3ecpZliFYs=; b=l1NpDw5bGorvaCP0c2Q1emiRPMgk8fO8EXiaHNTyqJi8Dv+OzsCFpsyFT2k/MkT4MW 0HWWDKmtBWsbAMVS3gKP6Yp7NPtYFUFw5TFvSAQWa4v6FCIPFOe2sOaztgh1xC+2cEAZ n8Rk+Usw8ve3OoXlVdnFVvUEKvuCnwSuILNIvWKwgijNM3uUpCzXrPDUTWewwSYzCIZN 3zVOOp18ojjzBpUOxr/QmOo4XaQK7SDpmT4BN3b7Gimt7k8TyH3B+iJFWcLmN9v41P5i Bita2pA622F5VnDCDrUUtNNbxQ11m3kAJZp3nQ+w/Mefc+vJWAFSPDohAG1ZbLlhtwhc HQrQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=EXI9KlBN; 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 r19-20020a05640251d300b00461c852af19si1631663edd.633.2022.11.10.20.03.35; Thu, 10 Nov 2022 20:03:58 -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=EXI9KlBN; 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 S232609AbiKKEA7 (ORCPT + 99 others); Thu, 10 Nov 2022 23:00:59 -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-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 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?1749170979157033392?= X-GMAIL-MSGID: =?utf-8?q?1749170979157033392?= 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: 18442 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp527135wru; Thu, 10 Nov 2022 20:04:39 -0800 (PST) X-Google-Smtp-Source: AMsMyM7/HjYBlY/67e+WlJUj2UJAMvMNA5k1knq1I7JWgBmvi2JL9rQKGOql4aMD7yjL8/OjR7qT X-Received: by 2002:a05:6402:b57:b0:461:53b0:2ac0 with SMTP id bx23-20020a0564020b5700b0046153b02ac0mr4227921edb.153.1668139478998; Thu, 10 Nov 2022 20:04:38 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668139478; cv=none; d=google.com; s=arc-20160816; b=ZSkHuPR+LC98jpVqi3YKYfujvGuMBtPWseRDHjxBMBgG4xFz/CoPs+nQ1+yKfZQDB0 jq6+V9f0E1OCu+jZ8VU6QunZNAY4KDECYRpF7YjnG2KE6FrNCWkmSAz8Z5DtkipnPPjD 59UVwhbVqHJRETHm9bcyRjIt/K1fg2W8am94YGpUgNgT/oDQNxngKl1c4MIlx8LOYw53 NNcYvwaONil/3LILkdEB/1MmQZkeSw+cC+swnXH7LDC7gMNBG6o5Ou1oBuyJUaq/605d +t4lpT4Vp9djreV0e3AhruvO1C8SyJPMCEUjmtg7IPBHCrNq3pq/kQI+eGnoqQMTRZV5 zzxQ== 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=rAYwtSDCtMl3bQjs+7iu2M5ENCXGl/6+Ww9pC2GxEs0=; b=X5h1aaftq6FsT+17y8G9LHm5nASa9p6JTvQGSb4FYhd8ERVHlaWVK70vt5MgCsHc7d lwBOityC2YYuCHrLYCbKqzAckEJVn2TIkbViLnWvCbhWANJolNETiRAzY740+4ZWZmpz JJbbQmnbk3wGBN8YyZSY0uyvIhgJN9I+5cdSkYXhf7To+nqFkXroDfAy2M4EImUXZdmJ BeXlh8zc9+XguZWbT4jhoGAbetLeB77CHW/HwreZ7dLtQAgjUB+ImkjKpTLGVM5cp1uN tWaGCJjRJdGuB9NsxvEnt0UfnOos1vXvQ2wdXfX38usiQn0mJ+98a+BAWCEuXuP4j0Vl 2n6g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20210112 header.b=KR4r6Izz; 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 hd39-20020a17090796a700b007317274bb0dsi1081011ejc.979.2022.11.10.20.04.15; Thu, 10 Nov 2022 20:04:38 -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=KR4r6Izz; 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 S232620AbiKKEBD (ORCPT + 99 others); Thu, 10 Nov 2022 23:01:03 -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-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 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?1749170888079777217?= X-GMAIL-MSGID: =?utf-8?q?1749171022089054768?= 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; }