From mboxrd@z Thu Jan 1 00:00:00 1970 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 D4FA8C4332F for ; Tue, 15 Nov 2022 17:26:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232152AbiKOR03 (ORCPT ); Tue, 15 Nov 2022 12:26:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56384 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231439AbiKOR0S (ORCPT ); Tue, 15 Nov 2022 12:26:18 -0500 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 05DA4264A8 for ; Tue, 15 Nov 2022 09:25:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1668533115; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=4AF5wlPWBdv2FqTXmRD8z1A6As043p69QbUfc2aOxsk=; b=OioFkvvdnJXvYsyaW12V6Wj05HgDo+1HAl1z5UZjN4/LxX3un6wXCiR1HQYjEgYR4a/ibL KnpIkjnDycpRp/4LupK0jOQUBACOuy56ZbpLz+deA+hqlBpswW9Y7MYWAnvIEFv6fCSqd1 1NR8Nfxfc4s25o2NBUHCruqZeh9Wyt8= Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-460-pK_75RJnMpapxPm022_zVQ-1; Tue, 15 Nov 2022 12:25:14 -0500 X-MC-Unique: pK_75RJnMpapxPm022_zVQ-1 Received: by mail-qt1-f200.google.com with SMTP id y8-20020ac87088000000b003a528a5b844so10737832qto.18 for ; Tue, 15 Nov 2022 09:25:14 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:message-id:date:references:in-reply-to:subject:cc:to :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=4AF5wlPWBdv2FqTXmRD8z1A6As043p69QbUfc2aOxsk=; b=vgZ8F4kyd/Ijd1JQMhydAI6GNdev+UxLSnIRLsfQbi2CWuMobotftIc7nY43X2V/Ut cP+sg2JAwqNeqEwjWMkjQL4F/rAyzpUAPZpr4tv8MGYF45hGkYDJbPJwL7lEWd+sgwvZ m7mO69oVNPe/SG/vHW+V73E4Q8CHq+BfjtznJAUFXaMcNOrQtnPgyaEh5YeOqg/CAmMA fj3mVV6Lm6D4o2I/gX+BvBiIsCwR76V6dscgKqa2DPx2C579gf7G2CSQfuWM9Ra8hu3E hrWriMxbGZyOdwvI4vEEADoF0e6uqlBsIwWEJeK0d6pkitChGdujVx497OxmRSme6ngu dMdg== X-Gm-Message-State: ANoB5pk0y4MJ/zxaZQouqrP9J8KwWIO1L+jfMQbdV8aavE21Zchjypm5 WENZ5XAcXY7rqqT8qkRVSiJX32ICv6oaw23t6mzO2t+5SVbpIX14x35dE5bUV9iUWhxElgKgrZB 2YC7qiN/vRv9sufEgnTOfpolm X-Received: by 2002:a05:622a:248c:b0:3a5:6005:7db6 with SMTP id cn12-20020a05622a248c00b003a560057db6mr17429561qtb.131.1668533114158; Tue, 15 Nov 2022 09:25:14 -0800 (PST) X-Google-Smtp-Source: AA0mqf7zZKeX/NTHK2U+NGI2HOpzkibwEC02BCDSKCXnFiWM2TzRBw3qp/HS9r1HUB4lPxzefKfbhw== X-Received: by 2002:a05:622a:248c:b0:3a5:6005:7db6 with SMTP id cn12-20020a05622a248c00b003a560057db6mr17429531qtb.131.1668533113947; Tue, 15 Nov 2022 09:25:13 -0800 (PST) Received: from vschneid.remote.csb ([154.57.232.159]) by smtp.gmail.com with ESMTPSA id g10-20020a05620a40ca00b006faf76e7c9asm8680773qko.115.2022.11.15.09.25.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 15 Nov 2022 09:25:13 -0800 (PST) From: Valentin Schneider To: Yury Norov , 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 , Vincent Guittot Cc: Yury Norov , linux-crypto@vger.kernel.org, netdev@vger.kernel.org, linux-rdma@vger.kernel.org Subject: Re: [PATCH v2 3/4] sched: add sched_numa_find_nth_cpu() In-Reply-To: <20221112190946.728270-4-yury.norov@gmail.com> References: <20221112190946.728270-1-yury.norov@gmail.com> <20221112190946.728270-4-yury.norov@gmail.com> Date: Tue, 15 Nov 2022 17:25:06 +0000 Message-ID: MIME-Version: 1.0 Content-Type: text/plain Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 12/11/22 11:09, Yury Norov wrote: > 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. > So one thing regarding the bsearch and NUMA levels; until not so long ago we couldn't even support 3 hops [1], and this only got detected when such machines started showing up. Your bsearch here operates on NUMA levels, which represent hops, and so far we know of systems that have up to 4 levels. I'd be surprised (and also appalled) if we even doubled that in the next decade, so with that in mind, a linear walk might not be so horrible. [1]: https://lore.kernel.org/all/20210224030944.15232-1-song.bao.hua@hisilicon.com/ > Signed-off-by: Yury Norov > --- > +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]); ^^^ wouldn't this always be 0 here? > +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) > -- > 2.34.1