From nobody Fri Nov 22 18:34:10 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1716581053; cv=none; d=zohomail.com; s=zohoarc; b=jpYayBWi9KF6lw5SN/nR7BJoav3/GC2tG0cuPqzmeuUtN73a9UPhMtv54pcrNbbJcq7TGnBxNF/As1B//E5i5rJfjgg7+BsP4ThIORi96nbuBl8re3O0PoDTl67YMahFstkcbMmX6bCcZEBr1cMPsaZT+2NCdxfnOavqhtXh6kg= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1716581053; h=Content-Type:Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=kIl6ox/sphrOz6UFI6xM1xqU962sO2kBKKT4aLgRbJg=; b=FyjH7A6RTZwYRBBFT64GxeEO4BQ/EVj49G0gS8XmSawXdgj2hfBhW/k0q/g37BAsRp7sO8Z4Zk9IWW+GzZC8PFUb8ZI7I1tEOrVBTkNLvz9AfV0A58udyiDt6N9Q1x9Fkasngr4ETBUi8xg0RBeqnUzKUkJt+HBneYaPMXdHceI= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1716581053664781.6644615538532; Fri, 24 May 2024 13:04:13 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.729751.1135059 (Exim 4.92) (envelope-from ) id 1sAb8r-0000Ot-HW; Fri, 24 May 2024 20:03:53 +0000 Received: by outflank-mailman (output) from mailman id 729751.1135059; Fri, 24 May 2024 20:03: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 1sAb8r-0000Nd-Ce; Fri, 24 May 2024 20:03:53 +0000 Received: by outflank-mailman (input) for mailman id 729751; Fri, 24 May 2024 20:03:52 +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 1sAb8q-000773-2L for xen-devel@lists.xenproject.org; Fri, 24 May 2024 20:03:52 +0000 Received: from mail-ed1-x52f.google.com (mail-ed1-x52f.google.com [2a00:1450:4864:20::52f]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id bcd8def2-1a08-11ef-b4bb-af5377834399; Fri, 24 May 2024 22:03:50 +0200 (CEST) Received: by mail-ed1-x52f.google.com with SMTP id 4fb4d7f45d1cf-578517c7ae9so1585194a12.3 for ; Fri, 24 May 2024 13:03:50 -0700 (PDT) Received: from andrewcoop.citrite.net ([160.101.139.1]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a626c9377d8sm173553066b.55.2024.05.24.13.03.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 13:03:48 -0700 (PDT) X-Outflank-Mailman: Message body and most headers restored to incoming version 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: bcd8def2-1a08-11ef-b4bb-af5377834399 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1716581029; x=1717185829; 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=kIl6ox/sphrOz6UFI6xM1xqU962sO2kBKKT4aLgRbJg=; b=hZfnLyQsdBdRA5tWILs1WM3bIsDtlcwqINDLfI4JpCMKKtsBWOAFSiOlMgaRUZSDQH FzrqPEa8yMfRKCm1Nbjc96gv11s4VpsjugV0pM3l6QC8wLYo/aUL1VzHxN/qmpm2BZjB anmgeeG0KCXFRZReYOZ+PAdHzExgfNo4lQzI4= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716581029; x=1717185829; 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=kIl6ox/sphrOz6UFI6xM1xqU962sO2kBKKT4aLgRbJg=; b=n62X7eyHznajFpCF94oATfA9z43bUfDvB2VV1IfFo3sbnQNaGNco1KqYVuWHfHrWpJ 9/nHvBKjZ61NHD29ZHCuGFdODQCgE6hrmnsMIkGK5zBtEk26jhbFpntgmnYDEXOIGELP izZglrg3acJxtNVtjhEWQ5BnYwcOA71cQeGAbC+KrjB/ertbJuEexfFohvnWbat+ot2p ih/hVL0BH5jdPvnkjrXpC4wvF6jNXnKd9+ShKXdSNQoOFIs+mtOUlMiA3RCw0lqTJtRW 674VyyIdG5M7LQXyuLXS1xlbkQcSMMjwaSDeDOdU9QKoTjmIykixMmHnXo+hwQ5ssfXL C5Pg== X-Gm-Message-State: AOJu0Yz/fOwOt5blhYpg9wQjoEsODu8o6AdC9wS8ybYoqHXfK2VphgAq U/YknOlKy69ymLRiC2qUdxZojAKyP6ONyW0q1fffwm30fTzjv0eO2DOH2POdSa2aq41Z3Js6Wp2 X3VA= X-Google-Smtp-Source: AGHT+IEUVNV4EpZfmOgPpyYnZ5/OwkBVDwrdSNszXAXbvrntU8FqgakDCrtsvjr4fA673YXJNwZzFw== X-Received: by 2002:a17:907:7844:b0:a5e:612e:fd58 with SMTP id a640c23a62f3a-a6264f126demr219304566b.51.1716581029010; Fri, 24 May 2024 13:03:49 -0700 (PDT) From: Andrew Cooper To: Xen-devel Cc: Andrew Cooper , Jan Beulich , =?UTF-8?q?Roger=20Pau=20Monn=C3=A9?= , Wei Liu , Stefano Stabellini , Julien Grall , Volodymyr Babchuk , Bertrand Marquis , Michal Orzel , Oleksii Kurochko , Shawn Anastasio , "consulting @ bugseng . com" , Simone Ballarin , Federico Serafini , Nicola Vetrini Subject: [PATCH v2 06/13] xen/bitops: Implement ffs() in common logic Date: Fri, 24 May 2024 21:03:31 +0100 Message-Id: <20240524200338.1232391-7-andrew.cooper3@citrix.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20240524200338.1232391-1-andrew.cooper3@citrix.com> References: <20240524200338.1232391-1-andrew.cooper3@citrix.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1716581056642100004 Perform constant-folding unconditionally, rather than having it implemented inconsistency between architectures. Confirm the expected behaviour with compile time and boot time tests. For non-constant inputs, use arch_ffs() if provided but fall back to generic_ffsl() if not. In particular, RISC-V doesn't have a builtin that works in all configurations. For x86, rename ffs() to arch_ffs() and adjust the prototype. For PPC, __builtin_ctz() is 1/3 of the size of size of the transform to generic_fls(). Drop the definition entirely. ARM too benefits in the gene= ral case by using __builtin_ctz(), but less dramatically because it using optimised asm(). Signed-off-by: Andrew Cooper Reviewed-by: Jan Beulich Reviewed-by: Stefano Stabellini --- CC: Jan Beulich CC: Roger Pau Monn=C3=A9 CC: Wei Liu CC: Stefano Stabellini CC: Julien Grall CC: Volodymyr Babchuk CC: Bertrand Marquis CC: Michal Orzel CC: Oleksii Kurochko CC: Shawn Anastasio CC: consulting@bugseng.com CC: Simone Ballarin CC: Federico Serafini CC: Nicola Vetrini v2: * Fall back to generic, not builtin. * Extend the testing with multi-bit values. * Use always_inline for x86 * Defer x86 optimisation to a later change --- xen/arch/arm/include/asm/bitops.h | 2 +- xen/arch/ppc/include/asm/bitops.h | 2 +- xen/arch/x86/include/asm/bitops.h | 3 ++- xen/common/Makefile | 1 + xen/common/bitops.c | 19 +++++++++++++++++++ xen/include/xen/bitops.h | 17 +++++++++++++++++ 6 files changed, 41 insertions(+), 3 deletions(-) create mode 100644 xen/common/bitops.c diff --git a/xen/arch/arm/include/asm/bitops.h b/xen/arch/arm/include/asm/b= itops.h index ec1cf7b9b323..a88ec2612e16 100644 --- a/xen/arch/arm/include/asm/bitops.h +++ b/xen/arch/arm/include/asm/bitops.h @@ -157,7 +157,7 @@ static inline int fls(unsigned int x) } =20 =20 -#define ffs(x) ({ unsigned int __t =3D (x); fls(ISOLATE_LSB(__t)); }) +#define arch_ffs(x) ((x) ? 1 + __builtin_ctz(x) : 0) #define ffsl(x) ({ unsigned long __t =3D (x); flsl(ISOLATE_LSB(__t)); }) =20 /** diff --git a/xen/arch/ppc/include/asm/bitops.h b/xen/arch/ppc/include/asm/b= itops.h index ab692d01717b..5c36a6cc0ce3 100644 --- a/xen/arch/ppc/include/asm/bitops.h +++ b/xen/arch/ppc/include/asm/bitops.h @@ -173,7 +173,7 @@ static inline int __test_and_clear_bit(int nr, volatile= void *addr) =20 #define flsl(x) generic_flsl(x) #define fls(x) generic_flsl(x) -#define ffs(x) ({ unsigned int t_ =3D (x); fls(t_ & -t_); }) +#define arch_ffs(x) ((x) ? 1 + __builtin_ctz(x) : 0) #define ffsl(x) ({ unsigned long t_ =3D (x); flsl(t_ & -t_); }) =20 /** diff --git a/xen/arch/x86/include/asm/bitops.h b/xen/arch/x86/include/asm/b= itops.h index 5a71afbc89d5..122767fc0d10 100644 --- a/xen/arch/x86/include/asm/bitops.h +++ b/xen/arch/x86/include/asm/bitops.h @@ -430,7 +430,7 @@ static inline int ffsl(unsigned long x) return (int)r+1; } =20 -static inline int ffs(unsigned int x) +static always_inline unsigned int arch_ffs(unsigned int x) { int r; =20 @@ -440,6 +440,7 @@ static inline int ffs(unsigned int x) "1:" : "=3Dr" (r) : "rm" (x)); return r + 1; } +#define arch_ffs arch_ffs =20 /** * fls - find last bit set diff --git a/xen/common/Makefile b/xen/common/Makefile index d512cad5243f..21a4fb4c7166 100644 --- a/xen/common/Makefile +++ b/xen/common/Makefile @@ -1,5 +1,6 @@ obj-$(CONFIG_ARGO) +=3D argo.o obj-y +=3D bitmap.o +obj-bin-$(CONFIG_DEBUG) +=3D bitops.init.o obj-$(CONFIG_GENERIC_BUG_FRAME) +=3D bug.o obj-$(CONFIG_HYPFS_CONFIG) +=3D config_data.o obj-$(CONFIG_CORE_PARKING) +=3D core_parking.o diff --git a/xen/common/bitops.c b/xen/common/bitops.c new file mode 100644 index 000000000000..8c161b8ea7fa --- /dev/null +++ b/xen/common/bitops.c @@ -0,0 +1,19 @@ +#include +#include +#include + +static void __init test_ffs(void) +{ + /* unsigned int ffs(unsigned int) */ + CHECK(ffs, 0, 0); + CHECK(ffs, 1, 1); + CHECK(ffs, 3, 1); + CHECK(ffs, 7, 1); + CHECK(ffs, 6, 2); + CHECK(ffs, 0x80000000U, 32); +} + +static void __init __constructor test_bitops(void) +{ + test_ffs(); +} diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h index cd405df96180..f7e90a2893a5 100644 --- a/xen/include/xen/bitops.h +++ b/xen/include/xen/bitops.h @@ -31,6 +31,23 @@ unsigned int __pure generic_flsl(unsigned long x); =20 #include =20 +/* + * Find First/Last Set bit (all forms). + * + * Bits are labelled from 1. Returns 0 if given 0. + */ +static always_inline __pure unsigned int ffs(unsigned int x) +{ + if ( __builtin_constant_p(x) ) + return __builtin_ffs(x); + +#ifdef arch_ffs + return arch_ffs(x); +#else + return generic_ffsl(x); +#endif +} + /* --------------------- Please tidy below here --------------------- */ =20 #ifndef find_next_bit --=20 2.30.2