From patchwork Thu Aug 22 23:06:27 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774333 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 6B53EC3DA4A for ; Thu, 22 Aug 2024 23:06:55 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782003.1191479 (Exim 4.92) (envelope-from ) id 1shGtA-0005HP-Q5; Thu, 22 Aug 2024 23:06:44 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782003.1191479; Thu, 22 Aug 2024 23:06:44 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtA-0005HI-NT; Thu, 22 Aug 2024 23:06:44 +0000 Received: by outflank-mailman (input) for mailman id 782003; Thu, 22 Aug 2024 23:06:43 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGt9-00052v-BY for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:43 +0000 Received: from mail-lf1-x133.google.com (mail-lf1-x133.google.com [2a00:1450:4864:20::133]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 31641ac1-60db-11ef-8776-851b0ebba9a2; Fri, 23 Aug 2024 01:06:41 +0200 (CEST) Received: by mail-lf1-x133.google.com with SMTP id 2adb3069b0e04-5334a8a1b07so1860646e87.1 for ; Thu, 22 Aug 2024 16:06:41 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:39 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 31641ac1-60db-11ef-8776-851b0ebba9a2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368000; x=1724972800; darn=lists.xenproject.org; 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=vi0HNaxsoocOO70fDh+VCPKJb25Qc7z5AiDZW/3dXd4=; b=q1U1G8I5sUJYS3ilmi2J7exQaeisMT+5GRvN46ZFTt2eOMAcMvpMy8BRsYUe4RMh+X OAsuIsBOyVQhlpDXXg95c/7kCFKHCcdPKcSLqSLc0CtbTO8tVPpgF/wcER6J2sNAzuS+ oZb6v1xzps4lfHg8l9N7mN9Ook8/8QKtsmD3o= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368000; x=1724972800; 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=vi0HNaxsoocOO70fDh+VCPKJb25Qc7z5AiDZW/3dXd4=; b=I8kl4461gTHqdAXFQpqlSvHfX9YjtJQ9bjy6rbicy/uuR3o9faxcxjxpJMcaUUUYAB VssQg50CBmmXXax99Mf7Jn+b8MHKY2KSILXoL+8Sc+cGWx5bB5GBXk92nwOUnt9D5pZC IPGIR4j3C4IIvVInGbhYCyyEJ8wGf3R/g0fBzJ/aQN4cfffqlact6C9KCPkMmwyr2KnO lQPSlEEgWeMeTvpHGtEjiAiiqWsRS15vQc9o8SHQP4CGVVuRm6nt1vjsg5GYBvc+/J+K y6OV1CjL9ySH6Jfa0XsRA1zSS+jVMsoSOXAfTjU8Fe4SWiFFheOHWu8/xuGSSMLjYs3G EiNw== X-Gm-Message-State: AOJu0YxLBIv//FkCVefrKGhiPiRjt2lKd0x8Wn/JAazsAsvHMPGuvowl jx4Sda6hmQcyt+hSOobDkUVyBEypfTgKPCAwzWESkAfHWQlIXtT8ECbdGulq6DSmC5csr+gVVe+ F X-Google-Smtp-Source: AGHT+IG08atBLSrHkN0q7MwPV4pRgbVAGpFeqlS9ZEga/uXi2+39o90RumbhPvbxno7nfcsm9Ll9eA== X-Received: by 2002:a05:6512:3a8a:b0:52c:e4cf:4f31 with SMTP id 2adb3069b0e04-5343886beeemr195477e87.49.1724368000028; Thu, 22 Aug 2024 16:06:40 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 1/9] xen/bitops: Reinstate the please tidy message Date: Fri, 23 Aug 2024 00:06:27 +0100 Message-Id: <20240822230635.954557-2-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 Recent additions have undone prior tidying at the top of the file. Signed-off-by: Andrew Cooper --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio --- xen/include/xen/bitops.h | 2 ++ 1 file changed, 2 insertions(+) diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index 3d88d2f3f1d6..b8bb2ffcd337 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -204,6 +204,8 @@ static always_inline bool test_bit(int nr, const volatile void *addr) test_bit(nr, addr); \ }) +/* --------------------- Please tidy above here --------------------- */ + static always_inline __pure unsigned int ffs(unsigned int x) { if ( __builtin_constant_p(x) ) From patchwork Thu Aug 22 23:06:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774339 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id C4D4AC5321D for ; Thu, 22 Aug 2024 23:06:56 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782004.1191490 (Exim 4.92) (envelope-from ) id 1shGtC-0005Vo-2R; Thu, 22 Aug 2024 23:06:46 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782004.1191490; Thu, 22 Aug 2024 23:06:46 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtB-0005Vh-Ug; Thu, 22 Aug 2024 23:06:45 +0000 Received: by outflank-mailman (input) for mailman id 782004; Thu, 22 Aug 2024 23:06:44 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtA-00052v-Bs for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:44 +0000 Received: from mail-ej1-x62c.google.com (mail-ej1-x62c.google.com [2a00:1450:4864:20::62c]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 31c0e354-60db-11ef-8776-851b0ebba9a2; Fri, 23 Aug 2024 01:06:42 +0200 (CEST) Received: by mail-ej1-x62c.google.com with SMTP id a640c23a62f3a-a869332c2c2so182236666b.0 for ; Thu, 22 Aug 2024 16:06:42 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:40 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 31c0e354-60db-11ef-8776-851b0ebba9a2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368001; x=1724972801; darn=lists.xenproject.org; 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=2Z50rUek42kgTiveeKTgR2WMlKuKbEecpCox+h79eBY=; b=C56+IeeF4PwlqSsDWuIb0/VOP1/ZnziWSbJZ+MsuNGG43R9MIK8ApuP2r+QjDVFF+J yEpNVHKbzxfUsXsDnrr1rKR6aNYhVw3miIpSGASSY0bu+9fm9heYemp9QLoZQHQUKqYa ZgZIa/zZyb5tVI6oc9DlvVev3exFldFvpznvc= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368001; x=1724972801; 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=2Z50rUek42kgTiveeKTgR2WMlKuKbEecpCox+h79eBY=; b=S1xQQyKCtESOjdUr2uCfbVilRAaadyh0i3rhkceNL2iRleH0uZE4w9abLK3WyOhvix 2Sdu3ySPRzJey50RrMTXM0EZo2I0LXuvLoXrV9wJjC8SgyvhdGdLupRMdCFDR2l5/6Za X0kAd/FDiMWgIq8+JHrpPNN5sAeu+BtyDDU3hd3T6EzPa0ud3FxNlAq5eJywLKRg3HiN X2C/Qg+E3a8g/z7z7Dxo1zKXGo5YLyWiPAl56yHwu+xP6SBK2NSdAGUsbabSwAbd74VH BP+sMqTQpo38dn53P+IcAE/FNkCQL5RL6zfBFponETDMON5cUBA9C5ZPl0otduVIjjTT qtfw== X-Gm-Message-State: AOJu0YxLVzlllHpTME8vo9jGk6nvHCp+3hlynO2r3RBKMv8fbjTxolj2 0i0up79JZX/1pwQJVpQPPACusv4Vv6Vhh5wjtNe5xOpxfuNe6FLipYjowD9ukfiHwwKWzqVpLA9 O X-Google-Smtp-Source: AGHT+IGsUggwR5NOud8P1JQNlp5q7xeSM5LIrPIsYEgMon9pttFSlivUmD8Is2ZkHkpnZwkWVAyHgg== X-Received: by 2002:a17:907:3d8a:b0:a72:5967:b34 with SMTP id a640c23a62f3a-a86a309ac9bmr48081766b.22.1724368000957; Thu, 22 Aug 2024 16:06:40 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 2/9] xen/bitops: Introduce a multiple_bits_set() helper Date: Fri, 23 Aug 2024 00:06:28 +0100 Message-Id: <20240822230635.954557-3-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 This will be used to simplify real logic in the following patch. Add compile and boot time testing as with other bitops. Because the expression is so simple, implement it as a function-like macro which is generic on the type of it's argument, rather than having multiple variants. Testing function-like macros needs a minor adjustments to the infrastructure in xen/self-tests.h to avoid bracketing the fn parameter. The utility of this outweighs the associated risks. Signed-off-by: Andrew Cooper Reviewed-by: Jan Beulich --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio Name inevitably subject to nitpicking. I'd prefer it to be shorter but I can't think of anything suitable. --- xen/common/bitops.c | 24 ++++++++++++++++++++++++ xen/include/xen/bitops.h | 10 ++++++++++ xen/include/xen/self-tests.h | 10 ++++++++-- 3 files changed, 42 insertions(+), 2 deletions(-) diff --git a/xen/common/bitops.c b/xen/common/bitops.c index 94a8983af99c..4545682aa8e0 100644 --- a/xen/common/bitops.c +++ b/xen/common/bitops.c @@ -84,8 +84,32 @@ static void __init test_fls(void) CHECK(fls64, 0x8000000000000001ULL, 64); } +static void __init test_multiple_bits_set(void) +{ + /* + * multiple_bits_set() is generic on the type of it's parameter, as the + * internal expression is so simple. + */ + + CHECK(multiple_bits_set, 0, false); + CHECK(multiple_bits_set, 1, false); + CHECK(multiple_bits_set, 2, false); + CHECK(multiple_bits_set, 3, true); + + CHECK(multiple_bits_set, 1 | (1UL << (BITS_PER_LONG - 1)), true); +#if BITS_PER_LONG > 32 + CHECK(multiple_bits_set, 1 | (1UL << 32), true); + CHECK(multiple_bits_set, 1 | (1UL << 63), true); +#endif + + CHECK(multiple_bits_set, 0x8000000000000001ULL, true); + CHECK(multiple_bits_set, 0xc000000000000000ULL, true); +} + static void __init __constructor test_bitops(void) { test_ffs(); test_fls(); + + test_multiple_bits_set(); } diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index b8bb2ffcd337..74c0d04e6647 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -274,6 +274,16 @@ static always_inline __pure unsigned int fls64(uint64_t x) } } +/* + * Calculate if a value has two or more bits set. Always use this in + * preference to an expression of the form 'hweight(x) > 1'. + */ +#define multiple_bits_set(x) \ + ({ \ + typeof(x) _v = (x); \ + (_v & (_v - 1)) != 0; \ + }) + /* --------------------- Please tidy below here --------------------- */ #ifndef find_next_bit diff --git a/xen/include/xen/self-tests.h b/xen/include/xen/self-tests.h index 58484fe5a8ae..e5a6ba748aba 100644 --- a/xen/include/xen/self-tests.h +++ b/xen/include/xen/self-tests.h @@ -15,11 +15,14 @@ * * Clang < 8 can't fold constants through static inlines, causing this to * fail. Simply skip it for incredibly old compilers. + * + * N.B. fn is intentionally not bracketed to allow us to test function-like + * macros too. */ #if !defined(CONFIG_CC_IS_CLANG) || CONFIG_CLANG_VERSION >= 80000 #define COMPILE_CHECK(fn, val, res) \ do { \ - typeof((fn)(val)) real = (fn)(val); \ + typeof(fn(val)) real = fn(val); \ \ if ( !__builtin_constant_p(real) ) \ asm ( ".error \"'" STR(fn(val)) "' not compile-time constant\"" ); \ @@ -34,10 +37,13 @@ * Check that Xen's runtime logic for fn(val) gives the expected answer. This * requires using HIDE() to prevent the optimiser from collapsing the logic * into a constant. + * + * N.B. fn is intentionally not bracketed to allow us to test function-like + * macros too. */ #define RUNTIME_CHECK(fn, val, res) \ do { \ - typeof((fn)(val)) real = (fn)(HIDE(val)); \ + typeof(fn(val)) real = fn(HIDE(val)); \ \ if ( real != (res) ) \ panic("%s: %s(%s) expected %u, got %u\n", \ From patchwork Thu Aug 22 23:06:29 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774334 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id B641EC5320E for ; Thu, 22 Aug 2024 23:06:55 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782005.1191499 (Exim 4.92) (envelope-from ) id 1shGtD-0005lI-Ci; Thu, 22 Aug 2024 23:06:47 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782005.1191499; Thu, 22 Aug 2024 23:06:47 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtD-0005lB-9L; Thu, 22 Aug 2024 23:06:47 +0000 Received: by outflank-mailman (input) for mailman id 782005; Thu, 22 Aug 2024 23:06:45 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtB-00052v-Ke for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:45 +0000 Received: from mail-ej1-x633.google.com (mail-ej1-x633.google.com [2a00:1450:4864:20::633]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 32d8ce17-60db-11ef-8776-851b0ebba9a2; Fri, 23 Aug 2024 01:06:44 +0200 (CEST) Received: by mail-ej1-x633.google.com with SMTP id a640c23a62f3a-a86859e2fc0so173830866b.3 for ; Thu, 22 Aug 2024 16:06:44 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:41 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 32d8ce17-60db-11ef-8776-851b0ebba9a2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368003; x=1724972803; darn=lists.xenproject.org; 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=YpnZe/6Rj0UVvPnf3275lXIauGqfUzo8Cf5z0ZU/Amw=; b=UwyaKJRH3kF5sHar/blpSxBxoVNxI/Rkn2BFwDCychf+aFhnx/gn93XE6H1koH6MWN jjro5GCzGAHmhMLdQkDhP9aY0Uz+XL4JFLI35vU6SfzA24va9rwNAHkZoEck2kwXmjEF QYnbiL0MKWwUdtd1ZprAdKt7ss9dT5HKiRA5o= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368003; x=1724972803; 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=YpnZe/6Rj0UVvPnf3275lXIauGqfUzo8Cf5z0ZU/Amw=; b=gLe6sPkY66BagCVL4SSZlewQ1KSoBUauQwZCkeN0/gwFSTAFYKYPhZi5MkWozhWmDJ nh7CLAxoY0n8TxJ+gE/D1jl6QuaOkrJJDXaUGHHVhUQANSzLiMyRXLPj2amcupMWMK++ qgxlZM5qegMVWAzY0Chn0cJtJPqytEty9pGzWgpVQ7cOEUA6UI5kLODvXjHoJDQmBAQl t5N2V151X79kgePoDhP9Dtyznd4QgJxc+c3Y+hWnxDwiukn06cg0fGFMFOnYm+hbSB12 KXJi3hrVhHy5PPKmmGakrFDHwTGgHFzY9oo88rLgt6qCLAfT5meq2QR0dDS6f3JiWWRx e7iQ== X-Gm-Message-State: AOJu0Yx3Tl7BIKq6xZnaieqHH8tlTGUlHrUfBep4xkFWDYaT+21SZrAs T27pMQaE+VEppPe13neT7/ee+dBBx14d4cVpIxtWKTUAipFce4iDn5rtJsVqwqgnnpO3aohrJl5 9 X-Google-Smtp-Source: AGHT+IH6ftjYtMlhJLqOnuqIi9pKaUpCeM5Mae1UDb83A9+Z2/FTPNORDiie+hP4NqFf7A9vDzPXAg== X-Received: by 2002:a17:907:940a:b0:a86:9f56:21e6 with SMTP id a640c23a62f3a-a86a53005e7mr14271566b.33.1724368002530; Thu, 22 Aug 2024 16:06:42 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 3/9] xen/bitops: Convert 'hweight(x) > 1' to new multiple_bits_set() Date: Fri, 23 Aug 2024 00:06:29 +0100 Message-Id: <20240822230635.954557-4-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 Using hweight() is an especially expensive way of determining simply if multiple bits are set in a value. Worse, 4 of the 10 hweight() calls in Xen are of this form. Switch to the new multiple_bits_set() helper. This is far more efficient than the longhand hweight() algorithm and, owing to its simplicity, likely more efficient than even a dedicated instruction on a superscalar processor. No functional change. Signed-off-by: Andrew Cooper Reviewed-by: Jan Beulich --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio On x86, the code reduction speaks for itself: add/remove: 0/0 grow/shrink: 0/3 up/down: 0/-240 (-240) Function old new delta vlapic_ipi 722 650 -72 numa_emulation 577 497 -80 do_xenpmu_op 1665 1577 -88 That's an aweful lot of wasted calculation for the same answer. I can't find a way of enabling CONFIG_NUMA on ARM (yet?) so right now there's no change in any other architecture. However, a synthetic helper shows the following on ARM32: add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-128 (-128) Function old new delta test_mbs 176 48 -128 and on ARM64: add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-44 (-44) Function old new delta test_mbs 60 16 -44 PPC64 has POPCNTD in a default build of Xen and by chance both algorithms compile to the same number of instructions. RISC-V doesn't have hweight() wired up yet at all. --- xen/arch/x86/cpu/vpmu.c | 2 +- xen/arch/x86/hvm/vlapic.c | 10 ++++++---- xen/common/numa.c | 2 +- 3 files changed, 8 insertions(+), 6 deletions(-) diff --git a/xen/arch/x86/cpu/vpmu.c b/xen/arch/x86/cpu/vpmu.c index b2ba9994129b..a5bb1689c7d5 100644 --- a/xen/arch/x86/cpu/vpmu.c +++ b/xen/arch/x86/cpu/vpmu.c @@ -673,7 +673,7 @@ long do_xenpmu_op( { if ( (pmu_params.val & ~(XENPMU_MODE_SELF | XENPMU_MODE_HV | XENPMU_MODE_ALL)) || - (hweight64(pmu_params.val) > 1) ) + multiple_bits_set(pmu_params.val) ) return -EINVAL; /* 32-bit dom0 can only sample itself. */ diff --git a/xen/arch/x86/hvm/vlapic.c b/xen/arch/x86/hvm/vlapic.c index 2ec95942713e..4a3e21a65f9d 100644 --- a/xen/arch/x86/hvm/vlapic.c +++ b/xen/arch/x86/hvm/vlapic.c @@ -467,12 +467,14 @@ static bool is_multicast_dest(struct vlapic *vlapic, unsigned int short_hand, return short_hand != APIC_DEST_SELF; if ( vlapic_x2apic_mode(vlapic) ) - return dest_mode ? hweight16(dest) > 1 : dest == 0xffffffffU; + return dest_mode ? multiple_bits_set((uint16_t)dest) + : dest == 0xffffffffU; if ( dest_mode ) - return hweight8(dest & - GET_xAPIC_DEST_FIELD(vlapic_get_reg(vlapic, - APIC_DFR))) > 1; + { + dest &= GET_xAPIC_DEST_FIELD(vlapic_get_reg(vlapic, APIC_DFR)); + return multiple_bits_set((uint8_t)dest); + } return dest == 0xff; } diff --git a/xen/common/numa.c b/xen/common/numa.c index 28a09766fabc..ce3991929ce5 100644 --- a/xen/common/numa.c +++ b/xen/common/numa.c @@ -546,7 +546,7 @@ static int __init numa_emulation(unsigned long start_pfn, uint64_t sz = pfn_to_paddr(end_pfn - start_pfn) / numa_fake; /* Kludge needed for the hash function */ - if ( hweight64(sz) > 1 ) + if ( multiple_bits_set(sz) ) { uint64_t x = 1; From patchwork Thu Aug 22 23:06:30 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774336 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id BB7AFC5321E for ; Thu, 22 Aug 2024 23:06:55 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782006.1191505 (Exim 4.92) (envelope-from ) id 1shGtD-0005nt-QT; Thu, 22 Aug 2024 23:06:47 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782006.1191505; Thu, 22 Aug 2024 23:06:47 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtD-0005n7-IJ; Thu, 22 Aug 2024 23:06:47 +0000 Received: by outflank-mailman (input) for mailman id 782006; Thu, 22 Aug 2024 23:06:46 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtC-00052v-K0 for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:46 +0000 Received: from mail-ej1-x62b.google.com (mail-ej1-x62b.google.com [2a00:1450:4864:20::62b]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 3371b277-60db-11ef-8776-851b0ebba9a2; Fri, 23 Aug 2024 01:06:45 +0200 (CEST) Received: by mail-ej1-x62b.google.com with SMTP id a640c23a62f3a-a86984e035aso130619766b.2 for ; Thu, 22 Aug 2024 16:06:45 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:42 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 3371b277-60db-11ef-8776-851b0ebba9a2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368004; x=1724972804; darn=lists.xenproject.org; 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=Z32VSiikSGXLFKmdcP1zMNdlkMYVkQVHFcaYHWzqH0I=; b=bTj2R2eBRNsDxvMlENtJm2nUIzV/d/FdqWcoOYH7NugUyK0aB5LCmZ3zsnoOAM0Gvp RsZkdMi5tHeey/yC9js/aR/IE4npPB4hqLBjSRb4utOEvJtxPrlLEXEm6aambgif6wwc l5hT3usa4qyncQS0iI4Cet2HXdeLgN6cCmaaA= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368004; x=1724972804; 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=Z32VSiikSGXLFKmdcP1zMNdlkMYVkQVHFcaYHWzqH0I=; b=EmCzYAsHYR3mEuaNXcKvo8sC6owAEsXlte/84TdJQ9NqAASZj/vZsT7neGtduoGVdi UFrwigWwAI/koPomeLNVx7EnUBJjX7QrDCoYOJQ31sTNZ0SGtE5ZG3IUlEHjVaurMSkP NCpaF16ken/CECD0vwg5Dy4FdB8jn3zaheYnTbErCnGFywVB1OagoyZvDP9OIf+A/hr8 jUyBsQmIhrBAnA9wJR2Y+3bLMzzAl2g8VDkyTUOBGcjDx2ex9C9zXyWnPNkjii8R6Jgv AY89O22NbTLymQFfde5UJ0QxbWjrGbVQ1RzsTh6BpGCTWkHBHmkfc6YkD3+4QvCYBjQM KNEQ== X-Gm-Message-State: AOJu0YztvEZLOCKCN49xC8yHwFZgXizDgrFO6YmxW4ShYtFsywON/2fa PRWSw2Kb1vZhjTSAVOMNhXOm00ZzyS4+EyiJ8EQDLGn2rbBHos72SqDG8Su3lLxrWaYKqqrIhWo I X-Google-Smtp-Source: AGHT+IFRDX/W4UY1H3WUEVSmOJeaLU8RAXCjyi52CvapXkXlmfnP6gHsMAgaeNOhzlOkCzNZeD3hMw== X-Received: by 2002:a17:906:9c82:b0:a86:96b3:86be with SMTP id a640c23a62f3a-a86a54b70d3mr14312866b.63.1724368003385; Thu, 22 Aug 2024 16:06:43 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 4/9] xen/bitops: Drop the remnants of hweight{8,16}() Date: Fri, 23 Aug 2024 00:06:30 +0100 Message-Id: <20240822230635.954557-5-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 They are no more, and won't be returning in this form. No functional change. Signed-off-by: Andrew Cooper Acked-by: Jan Beulich --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio --- xen/arch/arm/include/asm/bitops.h | 2 -- xen/arch/ppc/include/asm/bitops.h | 2 -- xen/arch/x86/include/asm/bitops.h | 2 -- xen/include/xen/bitops.h | 17 ----------------- 4 files changed, 23 deletions(-) diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h index 3c023103f734..91cd167b6bbb 100644 --- a/xen/arch/arm/include/asm/bitops.h +++ b/xen/arch/arm/include/asm/bitops.h @@ -86,8 +86,6 @@ bool clear_mask16_timeout(uint16_t mask, volatile void *p, */ #define hweight64(x) generic_hweight64(x) #define hweight32(x) generic_hweight32(x) -#define hweight16(x) generic_hweight16(x) -#define hweight8(x) generic_hweight8(x) #endif /* _ARM_BITOPS_H */ /* diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h index eb3355812ea3..a62c4f99c3bb 100644 --- a/xen/arch/ppc/include/asm/bitops.h +++ b/xen/arch/ppc/include/asm/bitops.h @@ -132,7 +132,5 @@ static inline int test_and_set_bit(unsigned int nr, volatile void *addr) */ #define hweight64(x) __builtin_popcountll(x) #define hweight32(x) __builtin_popcount(x) -#define hweight16(x) __builtin_popcount((uint16_t)(x)) -#define hweight8(x) __builtin_popcount((uint8_t)(x)) #endif /* _ASM_PPC_BITOPS_H */ diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h index 8c0403405aa2..4c5b21907a64 100644 --- a/xen/arch/x86/include/asm/bitops.h +++ b/xen/arch/x86/include/asm/bitops.h @@ -483,7 +483,5 @@ static always_inline unsigned int arch_flsl(unsigned long x) */ #define hweight64(x) generic_hweight64(x) #define hweight32(x) generic_hweight32(x) -#define hweight16(x) generic_hweight16(x) -#define hweight8(x) generic_hweight8(x) #endif /* _X86_BITOPS_H */ diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index 74c0d04e6647..64d70a7a1cb5 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -371,23 +371,6 @@ static inline unsigned int generic_hweight32(unsigned int w) return (w + (w >> 16)) & 0xff; } -static inline unsigned int generic_hweight16(unsigned int w) -{ - w -= ((w >> 1) & 0x5555); - w = (w & 0x3333) + ((w >> 2) & 0x3333); - w = (w + (w >> 4)) & 0x0f0f; - - return (w + (w >> 8)) & 0xff; -} - -static inline unsigned int generic_hweight8(unsigned int w) -{ - w -= ((w >> 1) & 0x55); - w = (w & 0x33) + ((w >> 2) & 0x33); - - return (w + (w >> 4)) & 0x0f; -} - static inline unsigned int generic_hweight64(uint64_t w) { if ( BITS_PER_LONG < 64 ) From patchwork Thu Aug 22 23:06:31 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774338 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 8A6C6C54722 for ; Thu, 22 Aug 2024 23:06:56 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782007.1191520 (Exim 4.92) (envelope-from ) id 1shGtG-0006IP-1w; Thu, 22 Aug 2024 23:06:50 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782007.1191520; Thu, 22 Aug 2024 23:06:49 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtF-0006IE-Sq; Thu, 22 Aug 2024 23:06:49 +0000 Received: by outflank-mailman (input) for mailman id 782007; Thu, 22 Aug 2024 23:06:48 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtE-0005x0-BD for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:48 +0000 Received: from mail-lf1-x133.google.com (mail-lf1-x133.google.com [2a00:1450:4864:20::133]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 34e28d5b-60db-11ef-a50a-bb4a2ccca743; Fri, 23 Aug 2024 01:06:47 +0200 (CEST) Received: by mail-lf1-x133.google.com with SMTP id 2adb3069b0e04-533463f6b16so1643376e87.1 for ; Thu, 22 Aug 2024 16:06:47 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:43 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 34e28d5b-60db-11ef-a50a-bb4a2ccca743 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368006; x=1724972806; darn=lists.xenproject.org; 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=AFP1jZxVxjDc6UuHRCIC5TORBnTsTsKkcvJ4HC7gOwo=; b=sJr3ax5WDcIYW9IT9jsb+X7jCjKugh7iocNh8PcZDIAHwUXrn4s3DDwYDUIwxCFcMM kdOHY5Vl3SDaHmXCksuRgZ4cBmTocbXxD0mPBtDnLlhAGJM/GtA+ZE4aNN/f/MkN/1uw gWnfoCp8lx3kyNpbZED3j4V7IrD5jWPppPCNQ= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368006; x=1724972806; 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=AFP1jZxVxjDc6UuHRCIC5TORBnTsTsKkcvJ4HC7gOwo=; b=uhMYUjlLOnQcPYYR5gaFO7OZ1Dp4cFUh+8MLn0Qw3DF18bpmpJq+pWZcRhDonjfk2n RC3z+mJ3fvjJk+HrZZcfKmWqzjjjA8lhg8KmrT6leeXWik7usmA2CXXAAPuBxz5NHSL0 ZG99Q8TRLKiz1ZDU8TNrfsUxVDZ2XwAlb7xhj2KHyHvCh/WELfcKr4feeE61d041iLvg W5NKABiMz6/4syRWwKDbi2xkip2LNtKVXEB8qC8OQ18Mz76yyYYeRACOvUnc2soE/lZy vuXVlVR8foFO0SHGo8SuVWsQBIgqZT7N+DS2/WQRBRD+OueulioLamdoxokAcU9Ghkah E3ZQ== X-Gm-Message-State: AOJu0Yyd4DKdX3F9koSntbK1serhHYv+lalOos2IrIOMjjQITbSh7sq0 Dts+LTn1vdoAlgz3AQqhyw8qJ3vRWnHA2E5Z9uYuabAKqLeRfysDggHSuQf9N7dtfafWARe0wto v X-Google-Smtp-Source: AGHT+IH4elKNA9PI3Ye/Rk6RqPEOVDFJKs/8JLNAzXLdemfeMbGWP7YuXjdSF8ZeK/iVyrA7vwZ9Hw== X-Received: by 2002:a05:6512:33ce:b0:52e:8b15:7c55 with SMTP id 2adb3069b0e04-534387853e7mr203955e87.27.1724368004524; Thu, 22 Aug 2024 16:06:44 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 5/9] xen/bitops: Introduce generic_hweightl() and hweightl() Date: Fri, 23 Aug 2024 00:06:31 +0100 Message-Id: <20240822230635.954557-6-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 There are 6 remaining callers in Xen: * The two hweight32() calls, _domain_struct_bits() and efi_find_gop_mode(), are __init only. * The two hweight_long() calls are both in bitmap_weight(). * The two hweight64() calls are hv_vpset_nr_banks() and x86_emulate(). Only bitmap_weight() and possibly hv_vpset_nr_banks() can be considered fast(ish) paths, and they're all of GPR-width form. Furthermore, the differences between a generic int and generic long form is only an ADD and SHIFT, and only in !CONFIG_HAS_FAST_MULTIPLY builds. Therefore, it is definitely not worth having both generic implemenations. Implement generic_hweightl() based on the current generic_hweight64(), adjusted to be compatible with ARM32, along with standard SELF_TESTS. Implement hweightl() with usual constant-folding and arch opt-in support. PPC is the only architecture that devates from generic, and it simply uses the builtin. No functional change. Signed-off-by: Andrew Cooper --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio --- xen/arch/ppc/include/asm/bitops.h | 2 ++ xen/common/bitops.c | 14 ++++++++++ xen/include/xen/bitops.h | 18 ++++++++++++ xen/lib/Makefile | 1 + xen/lib/generic-hweightl.c | 46 +++++++++++++++++++++++++++++++ 5 files changed, 81 insertions(+) create mode 100644 xen/lib/generic-hweightl.c diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h index a62c4f99c3bb..64512e949530 100644 --- a/xen/arch/ppc/include/asm/bitops.h +++ b/xen/arch/ppc/include/asm/bitops.h @@ -124,6 +124,8 @@ static inline int test_and_set_bit(unsigned int nr, volatile void *addr) #define arch_fls(x) ((x) ? 32 - __builtin_clz(x) : 0) #define arch_flsl(x) ((x) ? BITS_PER_LONG - __builtin_clzl(x) : 0) +#define arch_hweightl(x) __builtin_popcountl(x) + /** * hweightN - returns the hamming weight of a N-bit word * @x: the word to weigh diff --git a/xen/common/bitops.c b/xen/common/bitops.c index 4545682aa8e0..d0c268b4994a 100644 --- a/xen/common/bitops.c +++ b/xen/common/bitops.c @@ -106,10 +106,24 @@ static void __init test_multiple_bits_set(void) CHECK(multiple_bits_set, 0xc000000000000000ULL, true); } +static void __init test_hweight(void) +{ + /* unsigned int hweightl(unsigned long) */ + CHECK(hweightl, 0, 0); + CHECK(hweightl, 1, 1); + CHECK(hweightl, 3, 2); + CHECK(hweightl, 7, 3); + CHECK(hweightl, 0xff, 8); + + CHECK(hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2); + CHECK(hweightl, -1UL, BITS_PER_LONG); +} + static void __init __constructor test_bitops(void) { test_ffs(); test_fls(); test_multiple_bits_set(); + test_hweight(); } diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index 64d70a7a1cb5..3aac10b7f532 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -35,6 +35,12 @@ extern void __bitop_bad_size(void); unsigned int __pure generic_ffsl(unsigned long x); unsigned int __pure generic_flsl(unsigned long x); +/* + * Hamming Weight, also called Population Count. Returns the number of set + * bits in @x. + */ +unsigned int __pure generic_hweightl(unsigned long x); + /** * generic__test_and_set_bit - Set a bit and return its old value * @nr: Bit to set @@ -284,6 +290,18 @@ static always_inline __pure unsigned int fls64(uint64_t x) (_v & (_v - 1)) != 0; \ }) +static always_inline __pure unsigned int hweightl(unsigned long x) +{ + if ( __builtin_constant_p(x) ) + return __builtin_popcountl(x); + +#ifdef arch_hweightl + return arch_hweightl(x); +#else + return generic_hweightl(x); +#endif +} + /* --------------------- Please tidy below here --------------------- */ #ifndef find_next_bit diff --git a/xen/lib/Makefile b/xen/lib/Makefile index a48541596470..b6558e108bd9 100644 --- a/xen/lib/Makefile +++ b/xen/lib/Makefile @@ -6,6 +6,7 @@ lib-y += ctype.o lib-y += find-next-bit.o lib-y += generic-ffsl.o lib-y += generic-flsl.o +lib-y += generic-hweightl.o lib-y += list-sort.o lib-y += memchr.o lib-y += memchr_inv.o diff --git a/xen/lib/generic-hweightl.c b/xen/lib/generic-hweightl.c new file mode 100644 index 000000000000..fa4bbec273ab --- /dev/null +++ b/xen/lib/generic-hweightl.c @@ -0,0 +1,46 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ + +#include +#include +#include + +/* Mask value @b broadcast to every byte in a long */ +#if BITS_PER_LONG == 32 +# define MASK(b) ((b) * 0x01010101UL) +#elif BITS_PER_LONG == 64 +# define MASK(b) ((b) * 0x0101010101010101UL) +#else +# error Extend me please +#endif + +unsigned int generic_hweightl(unsigned long x) +{ + x -= (x >> 1) & MASK(0x55); + x = (x & MASK(0x33)) + ((x >> 2) & MASK(0x33)); + x = (x + (x >> 4)) & MASK(0x0f); + + if ( IS_ENABLED(CONFIG_HAS_FAST_MULTIPLY) ) + return (x * MASK(0x01)) >> (BITS_PER_LONG - 8); + + x += x >> 8; + x += x >> 16; +#if BITS_PER_LONG > 32 + x += x >> 32; +#endif + + return x & 0xff; +} + +#ifdef CONFIG_SELF_TESTS +static void __init __constructor test_generic_hweightl(void) +{ + RUNTIME_CHECK(generic_hweightl, 0, 0); + RUNTIME_CHECK(generic_hweightl, 1, 1); + RUNTIME_CHECK(generic_hweightl, 3, 2); + RUNTIME_CHECK(generic_hweightl, 7, 3); + RUNTIME_CHECK(generic_hweightl, 0xff, 8); + + RUNTIME_CHECK(generic_hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2); + RUNTIME_CHECK(generic_hweightl, -1UL, BITS_PER_LONG); +} +#endif /* CONFIG_SELF_TESTS */ From patchwork Thu Aug 22 23:06:32 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774337 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 50908C5472D for ; Thu, 22 Aug 2024 23:06:58 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782008.1191526 (Exim 4.92) (envelope-from ) id 1shGtG-0006Lx-H7; Thu, 22 Aug 2024 23:06:50 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782008.1191526; Thu, 22 Aug 2024 23:06:50 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtG-0006Kd-7A; Thu, 22 Aug 2024 23:06:50 +0000 Received: by outflank-mailman (input) for mailman id 782008; Thu, 22 Aug 2024 23:06:48 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtE-00052v-EA for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:48 +0000 Received: from mail-ej1-x62e.google.com (mail-ej1-x62e.google.com [2a00:1450:4864:20::62e]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 3498bd16-60db-11ef-8776-851b0ebba9a2; Fri, 23 Aug 2024 01:06:46 +0200 (CEST) Received: by mail-ej1-x62e.google.com with SMTP id a640c23a62f3a-a86933829dcso159480266b.3 for ; Thu, 22 Aug 2024 16:06:46 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:45 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 3498bd16-60db-11ef-8776-851b0ebba9a2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368006; x=1724972806; darn=lists.xenproject.org; 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=AK82ekbFPxm5HGoW+WcJpZodZZU1A3OHLLprY4hQ81c=; b=untMoLfEqpW0n12rPuTw0k3tnYpmgvhdwRwxr4VSC23E2RZCduxzik8Uxm7EGiECOk RwSDu9Ej5tSkK1bFvK+esp8JDwAhMb39TgcsBjqfVfYgi4bGXala5XsniTPe3J/KtZuH Z7mEtn9gDEr6DYlFKE2UjIYOVKZ+hC+J/dM4w= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368006; x=1724972806; 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=AK82ekbFPxm5HGoW+WcJpZodZZU1A3OHLLprY4hQ81c=; b=XcISQFZfK0iPcI0u+AwyoP01G/nFbDTdS/vn3hx4qcD8lGULR7W5Q+oqSfuFgyA0i2 RuDwDywqbV7X7jr2EJ5Qp9+wYR/aXbR8Rd/qK0st4d7RkHwg9Ja3lkmG9l42hhYWiBfk SwtRo/c9NBE8xTu708VS4aHnGghH0x/gco9CxBEw+YxsvRI8Y6fcL7thi6tKD0ub9tQI 86fMpG+yoj4iMs43Ml/DR15Wd+jYeL375RkmGRIvbfr6gRCTSZ62xtDZOlwN/7AnJUCW x8jM1zDTuJrbKaC2hE1VfNht9I3uXJumqPfEB2exjodykjR3w3zHTNv/YeMwYeM31brM +9MQ== X-Gm-Message-State: AOJu0Yy+6LMOP4xI/H6PhR4OWG3cwKweBG4BFdM+G4SgB6pJezuJxrcT OhIyuOjqJ2o3fEmxbvldsSJOb4GOjn6k0zbN5fKVeRf0XZZ/cuoff+lgwX/CZhP2Oqb09odcuXb O X-Google-Smtp-Source: AGHT+IEYvr3ptXUw2rp6Zjt30wMYdUycUCnNCfxJnJTOh3X6pfOU4e0TztA8+zwhTK/Ff8lMCviONw== X-Received: by 2002:a17:907:3f14:b0:a80:f6a0:9c3c with SMTP id a640c23a62f3a-a86a4eb3659mr22293866b.0.1724368005517; Thu, 22 Aug 2024 16:06:45 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 6/9] xen/bitops: Drop hweight_long() and use hweightl() Date: Fri, 23 Aug 2024 00:06:32 +0100 Message-Id: <20240822230635.954557-7-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 No functional change. Signed-off-by: Andrew Cooper Reviewed-by: Jan Beulich --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio --- xen/common/bitmap.c | 4 ++-- xen/include/xen/bitops.h | 5 ----- 2 files changed, 2 insertions(+), 7 deletions(-) diff --git a/xen/common/bitmap.c b/xen/common/bitmap.c index 9d9ff09f3dde..3da63a32a680 100644 --- a/xen/common/bitmap.c +++ b/xen/common/bitmap.c @@ -191,10 +191,10 @@ unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) unsigned int k, w = 0, lim = bits / BITS_PER_LONG; for (k = 0; k < lim; k++) - w += hweight_long(bitmap[k]); + w += hweightl(bitmap[k]); if (bits % BITS_PER_LONG) - w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); + w += hweightl(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); return w; } diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index 3aac10b7f532..11a1c9130722 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -407,11 +407,6 @@ static inline unsigned int generic_hweight64(uint64_t w) return (w + (w >> 32)) & 0xFF; } -static inline unsigned int hweight_long(unsigned long w) -{ - return sizeof(w) == 4 ? generic_hweight32(w) : generic_hweight64(w); -} - /* * rol32 - rotate a 32-bit value left * From patchwork Thu Aug 22 23:06:33 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774340 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id F0B38C5320E for ; Thu, 22 Aug 2024 23:06:58 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782009.1191532 (Exim 4.92) (envelope-from ) id 1shGtG-0006WV-UQ; Thu, 22 Aug 2024 23:06:50 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782009.1191532; Thu, 22 Aug 2024 23:06:50 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtG-0006Ub-PB; Thu, 22 Aug 2024 23:06:50 +0000 Received: by outflank-mailman (input) for mailman id 782009; Thu, 22 Aug 2024 23:06:49 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtF-00052v-LA for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:49 +0000 Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [2a00:1450:4864:20::32f]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 35360f7f-60db-11ef-8776-851b0ebba9a2; Fri, 23 Aug 2024 01:06:48 +0200 (CEST) Received: by mail-wm1-x32f.google.com with SMTP id 5b1f17b1804b1-429da8b5feaso13144605e9.2 for ; Thu, 22 Aug 2024 16:06:48 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:45 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 35360f7f-60db-11ef-8776-851b0ebba9a2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368007; x=1724972807; darn=lists.xenproject.org; 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=04R2tozSLk4UY2KQvXd1YOljv9lem5MX3oYM5xelDrU=; b=Go3pnA3IJPCAUr4/jE0eBz6wuNTqt4OHgIztAquFdtTn8NnK4d3W3V+00dd0SUWiDD b07kBFp7z0yRiK/QgGKUuD/VhOOMWJzcswN2ShpXZrgZcFoLtXK8sZDFeWcWnDJVjPwL bpkpCazN5fOwKccvjnsQmzHsJWSvpnpEH2Pk4= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368007; x=1724972807; 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=04R2tozSLk4UY2KQvXd1YOljv9lem5MX3oYM5xelDrU=; b=gAvru6LJGDkACBVHcbEPO2JAVZ4CQfJwwPT6V7rOqxMEBsdXugGO9fYc1eGI07GMB6 yBO2YwVhYGHXN7k1jwnC1oMtmGdj+8nlXIfYL0JLI7ZgjG2HAqM2VuPfOYqKGjMiQhyA JnNn0QHzW7+nLQY4oEP7P3gW8K4qS51oEruLl8nxd+OH4nXV0BuKFan8TuMjIcgEglZY eTAiPrI71dbvSKhe7Q4wNipQKgwrnC3j5e25azEzXi0u3ZXrfN5IOjZeY4R2vVJM0X2h HxaZIm7i0J/rgFPrvR97lIu9gvTcjvVwYXblfLCkpZo5UTiXLfGvE/s6Z8FYL4a/sBYQ ybEA== X-Gm-Message-State: AOJu0YxIel9F4X9QdQgREEmUqPIOOCm2RsHT01wWV9VSTM4SsVxDvvGG 6M1mEVPYrQL3NFPqVzYjUKivWRxJauhMctk95lVv3hWslqKmllRpq8VA48hk0IIg5av/uBOmkOZ 4 X-Google-Smtp-Source: AGHT+IHio/DKBV8jaKHOLljzZuYgJ+o3P9U5Tg3vcUpxjvZ+92Kcr0GWV4YmOYv7acgAE63q6nqrIQ== X-Received: by 2002:a5d:404e:0:b0:368:6f64:307c with SMTP id ffacd0b85a97d-37311855fbdmr188983f8f.15.1724368006329; Thu, 22 Aug 2024 16:06:46 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 7/9] xen/bitops: Implement hweight64() in terms of hweightl() Date: Fri, 23 Aug 2024 00:06:33 +0100 Message-Id: <20240822230635.954557-8-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 ... and drop generic_hweight64(). This is identical on all architectures except ARM32. Add one extra SELF_TEST to check that hweight64() works when the input is split in half. No functional change. Signed-off-by: Andrew Cooper Reviewed-by: Jan Beulich --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio --- xen/arch/arm/include/asm/bitops.h | 1 - xen/arch/ppc/include/asm/bitops.h | 1 - xen/arch/x86/include/asm/bitops.h | 1 - xen/common/bitops.c | 3 +++ xen/include/xen/bitops.h | 26 ++++++++------------------ 5 files changed, 11 insertions(+), 21 deletions(-) diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h index 91cd167b6bbb..bed6b3b98e08 100644 --- a/xen/arch/arm/include/asm/bitops.h +++ b/xen/arch/arm/include/asm/bitops.h @@ -84,7 +84,6 @@ bool clear_mask16_timeout(uint16_t mask, volatile void *p, * * The Hamming Weight of a number is the total number of bits set in it. */ -#define hweight64(x) generic_hweight64(x) #define hweight32(x) generic_hweight32(x) #endif /* _ARM_BITOPS_H */ diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h index 64512e949530..24dc35ef644d 100644 --- a/xen/arch/ppc/include/asm/bitops.h +++ b/xen/arch/ppc/include/asm/bitops.h @@ -132,7 +132,6 @@ static inline int test_and_set_bit(unsigned int nr, volatile void *addr) * * The Hamming Weight of a number is the total number of bits set in it. */ -#define hweight64(x) __builtin_popcountll(x) #define hweight32(x) __builtin_popcount(x) #endif /* _ASM_PPC_BITOPS_H */ diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h index 4c5b21907a64..9d3a2448036e 100644 --- a/xen/arch/x86/include/asm/bitops.h +++ b/xen/arch/x86/include/asm/bitops.h @@ -481,7 +481,6 @@ static always_inline unsigned int arch_flsl(unsigned long x) * * The Hamming Weight of a number is the total number of bits set in it. */ -#define hweight64(x) generic_hweight64(x) #define hweight32(x) generic_hweight32(x) #endif /* _X86_BITOPS_H */ diff --git a/xen/common/bitops.c b/xen/common/bitops.c index d0c268b4994a..f6a3eb5c9daf 100644 --- a/xen/common/bitops.c +++ b/xen/common/bitops.c @@ -117,6 +117,9 @@ static void __init test_hweight(void) CHECK(hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2); CHECK(hweightl, -1UL, BITS_PER_LONG); + + /* unsigned int hweight64(uint64_t) */ + CHECK(hweight64, -1ULL, 64); } static void __init __constructor test_bitops(void) diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index 11a1c9130722..e97516552a2e 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -302,6 +302,14 @@ static always_inline __pure unsigned int hweightl(unsigned long x) #endif } +static always_inline __pure unsigned int hweight64(uint64_t x) +{ + if ( BITS_PER_LONG == 64 ) + return hweightl(x); + else + return hweightl(x >> 32) + hweightl(x); +} + /* --------------------- Please tidy below here --------------------- */ #ifndef find_next_bit @@ -389,24 +397,6 @@ static inline unsigned int generic_hweight32(unsigned int w) return (w + (w >> 16)) & 0xff; } -static inline unsigned int generic_hweight64(uint64_t w) -{ - if ( BITS_PER_LONG < 64 ) - return generic_hweight32(w >> 32) + generic_hweight32(w); - - w -= (w >> 1) & 0x5555555555555555UL; - w = (w & 0x3333333333333333UL) + ((w >> 2) & 0x3333333333333333UL); - w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0fUL; - - if ( IS_ENABLED(CONFIG_HAS_FAST_MULTIPLY) ) - return (w * 0x0101010101010101UL) >> 56; - - w += w >> 8; - w += w >> 16; - - return (w + (w >> 32)) & 0xFF; -} - /* * rol32 - rotate a 32-bit value left * From patchwork Thu Aug 22 23:06:34 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774342 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 08BFAC5321E for ; Thu, 22 Aug 2024 23:07:02 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782011.1191553 (Exim 4.92) (envelope-from ) id 1shGtJ-0007Bq-JP; Thu, 22 Aug 2024 23:06:53 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782011.1191553; Thu, 22 Aug 2024 23:06:53 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtJ-0007B6-Fd; Thu, 22 Aug 2024 23:06:53 +0000 Received: by outflank-mailman (input) for mailman id 782011; Thu, 22 Aug 2024 23:06:51 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtH-00052v-SP for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:51 +0000 Received: from mail-lf1-x12e.google.com (mail-lf1-x12e.google.com [2a00:1450:4864:20::12e]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 3699e577-60db-11ef-8776-851b0ebba9a2; Fri, 23 Aug 2024 01:06:50 +0200 (CEST) Received: by mail-lf1-x12e.google.com with SMTP id 2adb3069b0e04-533462b9428so2424368e87.3 for ; Thu, 22 Aug 2024 16:06:50 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:46 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 3699e577-60db-11ef-8776-851b0ebba9a2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368009; x=1724972809; darn=lists.xenproject.org; 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=Hv9HlPwXrRYZdKJJ+1+hjJMFB9PxOUm7mKL1fwt8sqc=; b=LkHq+bj66eQWwX2bfzMPnXlvAKAFUu3jUVVFazOW9yIp53btyNksaiUTQ+FCBUNB+8 Bu0CBDtqz0qY/inO45Pd4c+F8f0Jn0RiQ76XAEF7dIzRj8C16tDCM6zeu1FwO7OG9O/Z i5mXyA13Kkehef4hC0S5xKA6LNiCj98HfrMwQ= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368009; x=1724972809; 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=Hv9HlPwXrRYZdKJJ+1+hjJMFB9PxOUm7mKL1fwt8sqc=; b=hyb6h/6ctauQtAulfnXTrRmePhuZx6e5NcWTnMQUs4hGzqrV7gRNfeigU1mzT8riV7 53eSVp2I6Zt2Q8mu0EgBtm6lbYt7j0rmubLKYPO7pIhgLmh3g0sr11ThO49MY+gOpXY2 mHJZYftURAVO5AmPqIlGL7uH4wreYfAoE9CaCK+TdUpGUBLNu7D3jZgiSi3cPK217t3H 3hQMPdpGfltpRpm6gBfw1GHLO2L6jUXOSO3sEoCARzCYZaT90xqfHxcg+g/Gg8uwGC4r nPdZbnFu8B51xk5Kt07w2QX3FId01hWUImaQleclgDHYmfckzR67uhAE3CXiRqBdVbZd +upQ== X-Gm-Message-State: AOJu0YzxZwpF8TaIFxyTxGtsCzcWQwfwrRzLLYbf0xxr51WWqUxinlWv SXEYGwbeUrirXtZcBCOg4ut3vQAZYBEyH3mqX6PJ06kSnoFWLfiD/bH9NtPRLRXukodIkNwrqpZ 9 X-Google-Smtp-Source: AGHT+IE7t0IfrG/EKoPzKoWKQ7aMXt59Dnlv0A5uSbNgbXpz8Nz7/5pY6zVU/KKdUSpN6o8Cct/2wA== X-Received: by 2002:a05:6512:114b:b0:52e:9808:3f48 with SMTP id 2adb3069b0e04-5343884701cmr433413e87.21.1724368008957; Thu, 22 Aug 2024 16:06:48 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio Subject: [PATCH 8/9] xen/bitops: Implement hweight32() in terms of hweightl() Date: Fri, 23 Aug 2024 00:06:34 +0100 Message-Id: <20240822230635.954557-9-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 ... and drop generic_hweight32(). As noted previously, the only two users of hweight32() and they're both singleton callers in __init paths, so it's not interesting to have a sub-GPR optimised generic. No functional change. Signed-off-by: Andrew Cooper Acked-by: Jan Beulich --- CC: Jan Beulich CC: Roger Pau Monné CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio --- xen/arch/arm/include/asm/bitops.h | 8 -------- xen/arch/ppc/include/asm/bitops.h | 8 -------- xen/arch/x86/include/asm/bitops.h | 8 -------- xen/include/xen/bitops.h | 24 +++++------------------- 4 files changed, 5 insertions(+), 43 deletions(-) diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/bitops.h index bed6b3b98e08..f163d9bb4578 100644 --- a/xen/arch/arm/include/asm/bitops.h +++ b/xen/arch/arm/include/asm/bitops.h @@ -78,14 +78,6 @@ bool clear_mask16_timeout(uint16_t mask, volatile void *p, #define arch_fls(x) ((x) ? 32 - __builtin_clz(x) : 0) #define arch_flsl(x) ((x) ? BITS_PER_LONG - __builtin_clzl(x) : 0) -/** - * hweightN - returns the hamming weight of a N-bit word - * @x: the word to weigh - * - * The Hamming Weight of a number is the total number of bits set in it. - */ -#define hweight32(x) generic_hweight32(x) - #endif /* _ARM_BITOPS_H */ /* * Local variables: diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/bitops.h index 24dc35ef644d..c942e9432e20 100644 --- a/xen/arch/ppc/include/asm/bitops.h +++ b/xen/arch/ppc/include/asm/bitops.h @@ -126,12 +126,4 @@ static inline int test_and_set_bit(unsigned int nr, volatile void *addr) #define arch_hweightl(x) __builtin_popcountl(x) -/** - * hweightN - returns the hamming weight of a N-bit word - * @x: the word to weigh - * - * The Hamming Weight of a number is the total number of bits set in it. - */ -#define hweight32(x) __builtin_popcount(x) - #endif /* _ASM_PPC_BITOPS_H */ diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h index 9d3a2448036e..642d8e58b288 100644 --- a/xen/arch/x86/include/asm/bitops.h +++ b/xen/arch/x86/include/asm/bitops.h @@ -475,12 +475,4 @@ static always_inline unsigned int arch_flsl(unsigned long x) } #define arch_flsl arch_flsl -/** - * hweightN - returns the hamming weight of a N-bit word - * @x: the word to weigh - * - * The Hamming Weight of a number is the total number of bits set in it. - */ -#define hweight32(x) generic_hweight32(x) - #endif /* _X86_BITOPS_H */ diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index e97516552a2e..bad2601b0fe6 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -302,6 +302,11 @@ static always_inline __pure unsigned int hweightl(unsigned long x) #endif } +static always_inline __pure unsigned int hweight32(uint32_t x) +{ + return hweightl(x); +} + static always_inline __pure unsigned int hweight64(uint64_t x) { if ( BITS_PER_LONG == 64 ) @@ -378,25 +383,6 @@ static inline int get_count_order(unsigned int count) return order; } -/* - * hweightN: returns the hamming weight (i.e. the number - * of bits set) of a N-bit word - */ - -static inline unsigned int generic_hweight32(unsigned int w) -{ - w -= (w >> 1) & 0x55555555; - w = (w & 0x33333333) + ((w >> 2) & 0x33333333); - w = (w + (w >> 4)) & 0x0f0f0f0f; - - if ( IS_ENABLED(CONFIG_HAS_FAST_MULTIPLY) ) - return (w * 0x01010101) >> 24; - - w += w >> 8; - - return (w + (w >> 16)) & 0xff; -} - /* * rol32 - rotate a 32-bit value left * From patchwork Thu Aug 22 23:06:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew Cooper X-Patchwork-Id: 13774341 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 lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 2630AC3DA4A for ; Thu, 22 Aug 2024 23:07:01 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.782010.1191550 (Exim 4.92) (envelope-from ) id 1shGtJ-00077n-A3; Thu, 22 Aug 2024 23:06:53 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 782010.1191550; Thu, 22 Aug 2024 23:06:53 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtJ-00077T-4u; Thu, 22 Aug 2024 23:06:53 +0000 Received: by outflank-mailman (input) for mailman id 782010; Thu, 22 Aug 2024 23:06:51 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1shGtH-0005x0-Pg for xen-devel@lists.xenproject.org; Thu, 22 Aug 2024 23:06:51 +0000 Received: from mail-ed1-x52f.google.com (mail-ed1-x52f.google.com [2a00:1450:4864:20::52f]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 371f1151-60db-11ef-a50a-bb4a2ccca743; Fri, 23 Aug 2024 01:06:51 +0200 (CEST) Received: by mail-ed1-x52f.google.com with SMTP id 4fb4d7f45d1cf-5beb6ea9ed6so1825947a12.1 for ; Thu, 22 Aug 2024 16:06:51 -0700 (PDT) Received: from andrewcoop.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a868f21ff19sm174676866b.39.2024.08.22.16.06.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Aug 2024 16:06:49 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 371f1151-60db-11ef-a50a-bb4a2ccca743 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1724368010; x=1724972810; darn=lists.xenproject.org; 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=ZhC0dDRFULppQVdbhtuL/Lf0g47WWxeU1SaqkI74Lp0=; b=XtvJAfOfBDSJuh0Kg5UoQx152wKatFwvNXiKWmjHWiWbatr+6rNuPIAHQlh9OmWy+S Pqyq/ClHwb8/DLQNWJCd+h79cUNOdLHhHTQBDgLUf9NYTpi5ew2UGjvQo5uahPDaCRtu RvRE46zQd6XkDi+zGVeOhCoAK5nSDiFXbMgGk= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724368010; x=1724972810; 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=ZhC0dDRFULppQVdbhtuL/Lf0g47WWxeU1SaqkI74Lp0=; b=QuT1nJvQgPIHP7u+tmFAiTCgefxIsQpYsN6t2zKMZn59wmisQ90eKc4fM86WaRXF6d gsDgOFh212bTkdH6+MN1/yEGzU78HLnu6iHrlYim5joGojZRJZNgqB0bNnrS3dfozhmn r3+6pCZlSnB+NdOrJRZKP1DXrHVzd4L1nqMb6YzLUUnuD+dNZssWnQc4yGn5y9CNHitQ C6Tc/WT5XA38JNmpHJIMKIq2HzVXjselzm5M+okNwgfPfp/inSmEXhkDSqGbdKaWY5Mv g1iT1ozXA3XQ5iEtG9oiJzKTb3ZY49XvE6I09yHUqnjzekrW/7jis69XeXUUW6B9GUbH ALKA== X-Gm-Message-State: AOJu0YzL1122s+cnDldBiI+ThnUinfGk7uOQ90Ta8PR5GET+SbH6xtCS 1nETXfkOwO0hJvf+4J7oUjdsiCP2j4em4p1FsfNtm2AUfhDi83977JLKCq16kNOxjdSzgPdEQud C X-Google-Smtp-Source: AGHT+IHNUm/EcdxtV5dBXZ8zfI7oCAB0QZqAzhTQlqiAQ9Y/DTgEq1db+kf1Yi4Q4Xa0ZVfQM72mnA== X-Received: by 2002:a17:907:6092:b0:a86:83c3:d5d0 with SMTP id a640c23a62f3a-a86a54b6ff9mr20615766b.59.1724368009670; Thu, 22 Aug 2024 16:06:49 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?utf-8?q?Roger_Pau_Monn=C3=A9?= Subject: [PATCH 9/9] x86/bitops: Use the POPCNT instruction when available Date: Fri, 23 Aug 2024 00:06:35 +0100 Message-Id: <20240822230635.954557-10-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240822230635.954557-1-andrew.cooper3@citrix.com> References: <20240822230635.954557-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 It has existed in x86 CPUs since 2008, so we're only 16 years late adding support. With all the other scafolding in place, implement arch_hweightl() for x86. The only complication is that the call to arch_generic_hweightl() is behind the compilers back. Address this by writing it in ASM and ensure that it preserves all registers. Copy the code generation from generic_hweightl(). It's not a complicated algorithm, and is easy to regenerate if needs be, but cover it with the same unit tests as test_generic_hweightl() just for piece of mind. Signed-off-by: Andrew Cooper --- CC: Jan Beulich CC: Roger Pau Monné A few RFC points. * I throught we had an x86 general lib-y but I can't find one, hence why it's still in xen/lib/ for now. * When we up the minimum toolchain to GCC 7 / Clang 5, we can use a __attribute__((no_caller_saved_registers)) and can forgo writing this in asm. GCC seems to need extra help, and wants -mgeneral-regs-only too. It has a habit of complaining about incompatible instructions even when it's not emitting them. --- xen/arch/x86/include/asm/bitops.h | 21 ++++++++++++++ xen/lib/Makefile | 1 + xen/lib/arch-generic-hweightl.S | 46 +++++++++++++++++++++++++++++++ xen/lib/generic-hweightl.c | 15 ++++++++++ 4 files changed, 83 insertions(+) create mode 100644 xen/lib/arch-generic-hweightl.S diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/bitops.h index 642d8e58b288..0db698ed3f4c 100644 --- a/xen/arch/x86/include/asm/bitops.h +++ b/xen/arch/x86/include/asm/bitops.h @@ -6,6 +6,7 @@ */ #include +#include #include /* @@ -475,4 +476,24 @@ static always_inline unsigned int arch_flsl(unsigned long x) } #define arch_flsl arch_flsl +static always_inline unsigned int arch_hweightl(unsigned long x) +{ + unsigned int r; + + /* + * arch_generic_hweightl() is written in ASM in order to preserve all + * registers, as the compiler can't see the call. + * + * This limits the POPCNT instruction to using the same ABI as a function + * call (input in %rdi, output in %eax) but that's fine. + */ + alternative_io("call arch_generic_hweightl", + "popcnt %[val], %q[res]", X86_FEATURE_POPCNT, + ASM_OUTPUT2([res] "=a" (r) ASM_CALL_CONSTRAINT), + [val] "D" (x)); + + return r; +} +#define arch_hweightl arch_hweightl + #endif /* _X86_BITOPS_H */ diff --git a/xen/lib/Makefile b/xen/lib/Makefile index b6558e108bd9..84d731dc0ac8 100644 --- a/xen/lib/Makefile +++ b/xen/lib/Makefile @@ -1,5 +1,6 @@ obj-$(CONFIG_X86) += x86/ +lib-$(CONFIG_X86) += arch-generic-hweightl.o lib-y += bsearch.o lib-y += ctors.o lib-y += ctype.o diff --git a/xen/lib/arch-generic-hweightl.S b/xen/lib/arch-generic-hweightl.S new file mode 100644 index 000000000000..15c6e3394845 --- /dev/null +++ b/xen/lib/arch-generic-hweightl.S @@ -0,0 +1,46 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + + .file __FILE__ + +#include + +/* + * An implementation of generic_hweightl() used on hardware without the POPCNT + * instruction. + * + * This function is called from within an ALTERNATIVE in arch_hweightl(). + * i.e. behind the back of the compiler. Therefore all registers are callee + * preserved. + * + * The ASM is what GCC-12 emits for generic_hweightl() in a release build of + * Xen, with spilling of %rdi/%rdx to preserve the callers registers. + */ +FUNC(arch_generic_hweightl) + push %rdi + push %rdx + + movabs $0x5555555555555555, %rdx + mov %rdi, %rax + shr $1, %rax + and %rdx, %rax + sub %rax, %rdi + movabs $0x3333333333333333, %rax + mov %rdi, %rdx + shr $0x2, %rdi + and %rax, %rdx + and %rax, %rdi + add %rdi, %rdx + mov %rdx, %rax + shr $0x4, %rax + add %rdx, %rax + movabs $0xf0f0f0f0f0f0f0f, %rdx + and %rdx, %rax + movabs $0x101010101010101, %rdx + imul %rdx, %rax + shr $0x38, %rax + + pop %rdx + pop %rdi + + ret +END(arch_generic_hweightl) diff --git a/xen/lib/generic-hweightl.c b/xen/lib/generic-hweightl.c index fa4bbec273ab..4b39dd84de5e 100644 --- a/xen/lib/generic-hweightl.c +++ b/xen/lib/generic-hweightl.c @@ -43,4 +43,19 @@ static void __init __constructor test_generic_hweightl(void) RUNTIME_CHECK(generic_hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2); RUNTIME_CHECK(generic_hweightl, -1UL, BITS_PER_LONG); } + +#ifdef CONFIG_X86 +unsigned int arch_generic_hweightl(unsigned long); +static void __init __constructor test_arch_generic_hweightl(void) +{ + RUNTIME_CHECK(arch_generic_hweightl, 0, 0); + RUNTIME_CHECK(arch_generic_hweightl, 1, 1); + RUNTIME_CHECK(arch_generic_hweightl, 3, 2); + RUNTIME_CHECK(arch_generic_hweightl, 7, 3); + RUNTIME_CHECK(arch_generic_hweightl, 0xff, 8); + + RUNTIME_CHECK(arch_generic_hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2); + RUNTIME_CHECK(arch_generic_hweightl, -1UL, BITS_PER_LONG); +} +#endif /* CONFIG_X86 */ #endif /* CONFIG_SELF_TESTS */