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 bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (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 B13F2C19F32 for ; Sun, 2 Mar 2025 08:20:24 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:References: Message-ID:Subject:Cc:To:From:Date:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=JbjQAIJIxwpRbjsh7GuhipenGW3zk9AUL1iag+9e6s4=; b=u3Ugz9ZYeVO0sg tRKAW0JOaOjkvd2e6w+SW7OWEkgwfll6WlsewMbFu9NECbMmqIfyAHpFNeygrsZFmGGd3k1B7IrGU yp4K25lEaskfaxnDjlSt1VWIBq6zIOmPuF2ZU2LN4At0Ug2gwJqB1rJ3ZN50U8UfL7B2qFA6++7Da 42P95rIL5me6/qPuuC5sMAYBkUiA5dzpUi1PwYZrFUN+blr+SN1MJpg8DQIStnfJxI6tNuMeHCUTz XM5nn4cP7sJB3D4Mhnt+p4a47RxxVeFtPWw7U14Xtr8ISvIsbvq8kfEzvP9PEUdoHEBAXyTKc+Jrg ZYBJTnc1jmwQACK9TWZA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.98 #2 (Red Hat Linux)) id 1toeYb-0000000Fe0H-3qGX; Sun, 02 Mar 2025 08:20:17 +0000 Received: from mail-pj1-x102e.google.com ([2607:f8b0:4864:20::102e]) by bombadil.infradead.org with esmtps (Exim 4.98 #2 (Red Hat Linux)) id 1toeYY-0000000Fdze-2Wvv for linux-mtd@lists.infradead.org; Sun, 02 Mar 2025 08:20:15 +0000 Received: by mail-pj1-x102e.google.com with SMTP id 98e67ed59e1d1-2fe848040b1so7273795a91.3 for ; Sun, 02 Mar 2025 00:20:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1740903613; x=1741508413; darn=lists.infradead.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=hvRvdsHloY5BTybtl092nj/Kn8Sd866ni5GmAJ3o96M=; b=mIsZbzK5i3CcttsqltxMxLvQAK/qbpeqsJE8sQcY15o29DuVDJZO3SQFVoXeR6C/VN 4uXYJojJBMllNXGkCcVC//NVqIgdmNxTp/Tjd5Gzd//xheQc+BFrvOYXCVshy3mCyeHP EH7tzdlqHJZpr18FIvPaxfir2wwGX62qxh5bGtoeX9wJ7NfaHWfLWhQHlo7MdZw3do6H fbSmhqnxgNu+fZzsRvupLdw20Vsslt8YCjiXG9sQHLK9FjE/wL2DlL926xF9rEBc59Xj QzayKBlCadN514z0Tjg/6JnUL5MxNGJ1lnKUvRuVlwj4BE7iv2BULW0sarNjRwf7IDXD SqeQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740903613; x=1741508413; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=hvRvdsHloY5BTybtl092nj/Kn8Sd866ni5GmAJ3o96M=; b=K3sf3F2szSfsDimRyKLLCIRCBCc5rEqbUe/tjucpY4DPTIU6gcUPeMDO4k1kWOvNop 1NXJJynLp/dqy8cjuE1O8984y9zqKfwqk4mAFxlWSPaYcySPgpdgvosj5OmlsEX0nyNv EPATfBcMtWirwev9ZjAJ+x6w60PBIXX6kx0bzxas/PfwifdrAK+BnruTD3VXsGec1OUe 4l9VvvSULg6a3RG0wkPkf25Dbm/VPNiU4i9cZ6m/jaP4vXofmhgYynoxmc76ZLqCIIC5 pU81VCQa/yqAZPZk5VYYaocQAz6zn8gxOuw4QS/d/SNfN41oebPelWDeSIYcd8XUK975 0QSg== X-Forwarded-Encrypted: i=1; AJvYcCWelzmxlcM3BqyEhZ05v+BfUg8wR0W4EdxElx2hSJmGY88/3EMkuoohBr26rc6+y75UObxHnm4aExY=@lists.infradead.org X-Gm-Message-State: AOJu0YzUHFul+wUMqyd20k1gWeBaQhF7k58OttUwIUJ5vhQhfPsdPOEA dFUEg7ZJIlidi8gcdg1S7pBjcCRJsvW6ORM9guQRWGGK7N6ksH/9 X-Gm-Gg: ASbGncs25K1LimiJQl/KgDLWeP7F71/CjqRdLBj8dYYm3VKvMCKb+sqO14+sk4VSYCX 2yW/YbCpDScf9K1asBlFgPNgTbCwHJI4bbfpDi+NI6pCpLOxyiKbmhZHSpmaqrAOJgHAwxF4Iwf ts86LhClb7CpNMkYsBaGv5N8puoZETrHzPuDtVbAhKOk12Ha7T07BUlg7jM0ONE2wK505kj93WB MhScCWvW+dGzpzJ062s+9Bvnl25DhscF+XJC8FqxMb+HpExrVc+l9ULp8s2sN8bGUTbIeIohygy FBedejess3YmdFTDvGFYJ5wSVi6Xi3uKfc+efnv7meN43PTTzegz+z32u8fz8z+u7uTOIh3h X-Google-Smtp-Source: AGHT+IEhxHA+kpP3f6IyyP7qeoU3p0FUjq/2+GkVz3d5MRAoSIvjaHiRGY0TomgRz3SF6T/LAIMe2Q== X-Received: by 2002:a17:90b:17d2:b0:2ee:aef4:2c5d with SMTP id 98e67ed59e1d1-2febabdede3mr12777219a91.26.1740903613420; Sun, 02 Mar 2025 00:20:13 -0800 (PST) Received: from visitorckw-System-Product-Name ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2235052a622sm58034965ad.231.2025.03.02.00.20.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 02 Mar 2025 00:20:12 -0800 (PST) Date: Sun, 2 Mar 2025 16:20:02 +0800 From: Kuan-Wei Chiu To: Yury Norov Cc: tglx@linutronix.de, mingo@redhat.com, bp@alien8.de, dave.hansen@linux.intel.com, x86@kernel.org, jk@ozlabs.org, joel@jms.id.au, eajames@linux.ibm.com, andrzej.hajda@intel.com, neil.armstrong@linaro.org, rfoss@kernel.org, maarten.lankhorst@linux.intel.com, mripard@kernel.org, tzimmermann@suse.de, airlied@gmail.com, simona@ffwll.ch, dmitry.torokhov@gmail.com, mchehab@kernel.org, awalls@md.metrocast.net, hverkuil@xs4all.nl, miquel.raynal@bootlin.com, richard@nod.at, vigneshr@ti.com, louis.peens@corigine.com, andrew+netdev@lunn.ch, davem@davemloft.net, edumazet@google.com, pabeni@redhat.com, parthiban.veerasooran@microchip.com, arend.vanspriel@broadcom.com, johannes@sipsolutions.net, gregkh@linuxfoundation.org, jirislaby@kernel.org, akpm@linux-foundation.org, hpa@zytor.com, alistair@popple.id.au, linux@rasmusvillemoes.dk, Laurent.pinchart@ideasonboard.com, jonas@kwiboo.se, jernej.skrabec@gmail.com, kuba@kernel.org, linux-kernel@vger.kernel.org, linux-fsi@lists.ozlabs.org, dri-devel@lists.freedesktop.org, linux-input@vger.kernel.org, linux-media@vger.kernel.org, linux-mtd@lists.infradead.org, oss-drivers@corigine.com, netdev@vger.kernel.org, linux-wireless@vger.kernel.org, brcm80211@lists.linux.dev, brcm80211-dev-list.pdl@broadcom.com, linux-serial@vger.kernel.org, bpf@vger.kernel.org, jserv@ccns.ncku.edu.tw, david.laight.linux@gmail.com, andrew.cooper3@citrix.com, Yu-Chun Lin Subject: Re: [PATCH v2 01/18] lib/parity: Add __builtin_parity() fallback implementations Message-ID: References: <20250301142409.2513835-1-visitorckw@gmail.com> <20250301142409.2513835-2-visitorckw@gmail.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20250302_002014_649632_7F980E18 X-CRM114-Status: GOOD ( 44.04 ) X-BeenThere: linux-mtd@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Linux MTD discussion mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-mtd" Errors-To: linux-mtd-bounces+linux-mtd=archiver.kernel.org@lists.infradead.org Hi Yury, On Sat, Mar 01, 2025 at 10:10:20PM -0500, Yury Norov wrote: > On Sat, Mar 01, 2025 at 10:23:52PM +0800, Kuan-Wei Chiu wrote: > > Add generic C implementations of __paritysi2(), __paritydi2(), and > > __parityti2() as fallback functions in lib/parity.c. These functions > > compute the parity of a given integer using a bitwise approach and are > > marked with __weak, allowing architecture-specific implementations to > > override them. > > > > This patch serves as preparation for using __builtin_parity() by > > ensuring a fallback mechanism is available when the compiler does not > > inline the __builtin_parity(). > > > > Co-developed-by: Yu-Chun Lin > > Signed-off-by: Yu-Chun Lin > > Signed-off-by: Kuan-Wei Chiu > > --- > > lib/Makefile | 2 +- > > lib/parity.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ > > 2 files changed, 49 insertions(+), 1 deletion(-) > > create mode 100644 lib/parity.c > > > > diff --git a/lib/Makefile b/lib/Makefile > > index 7bab71e59019..45affad85ee4 100644 > > --- a/lib/Makefile > > +++ b/lib/Makefile > > @@ -51,7 +51,7 @@ obj-y += bcd.o sort.o parser.o debug_locks.o random32.o \ > > bsearch.o find_bit.o llist.o lwq.o memweight.o kfifo.o \ > > percpu-refcount.o rhashtable.o base64.o \ > > once.o refcount.o rcuref.o usercopy.o errseq.o bucket_locks.o \ > > - generic-radix-tree.o bitmap-str.o > > + generic-radix-tree.o bitmap-str.o parity.o > > obj-y += string_helpers.o > > obj-y += hexdump.o > > obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o > > diff --git a/lib/parity.c b/lib/parity.c > > new file mode 100644 > > index 000000000000..a83ff8d96778 > > --- /dev/null > > +++ b/lib/parity.c > > @@ -0,0 +1,48 @@ > > +// SPDX-License-Identifier: GPL-2.0-only > > +/* > > + * lib/parity.c > > + * > > + * Copyright (C) 2025 Kuan-Wei Chiu > > + * Copyright (C) 2025 Yu-Chun Lin > > + * > > + * __parity[sdt]i2 can be overridden by linking arch-specific versions. > > + */ > > + > > +#include > > +#include > > + > > +/* > > + * One explanation of this algorithm: > > + * https://funloop.org/codex/problem/parity/README.html > > I already asked you not to spread this link. Is there any reason to > ignore it? > In v2, this algorithm was removed from bitops.h, so I moved the link here instead. I'm sorry if it seemed like I ignored your comment. > > + */ > > +int __weak __paritysi2(u32 val); > > +int __weak __paritysi2(u32 val) > > +{ > > + val ^= val >> 16; > > + val ^= val >> 8; > > + val ^= val >> 4; > > + return (0x6996 >> (val & 0xf)) & 1; > > +} > > +EXPORT_SYMBOL(__paritysi2); > > + > > +int __weak __paritydi2(u64 val); > > +int __weak __paritydi2(u64 val) > > +{ > > + val ^= val >> 32; > > + val ^= val >> 16; > > + val ^= val >> 8; > > + val ^= val >> 4; > > + return (0x6996 >> (val & 0xf)) & 1; > > +} > > +EXPORT_SYMBOL(__paritydi2); > > + > > +int __weak __parityti2(u64 val); > > +int __weak __parityti2(u64 val) > > +{ > > + val ^= val >> 32; > > + val ^= val >> 16; > > + val ^= val >> 8; > > + val ^= val >> 4; > > + return (0x6996 >> (val & 0xf)) & 1; > > +} > > +EXPORT_SYMBOL(__parityti2); > > OK, it seems I wasn't clear enough on the previous round, so I'll try > to be very straightforward now. > > To begin with, the difference between __parityti2 and __paritydi2 > doesn't exist. I'm seriously. I put them side by side, and there's > no difference at all. > > Next, this all is clearly an overengineering. You bake all those weak, > const and (ironically, missing) high-efficient arch implementations. > But you show no evidence that: > - it improves on code generation, > - the drivers care about parity()'s performance, and > - show no perf tests at all. > > So you end up with +185/-155 LOCs. > > Those +30 lines add no new functionality. You copy-paste the same > algorithm again and again in very core kernel files. This is a no-go > for a nice consolidation series. > > In the previous round reviewers gave you quite a few nice suggestions. > H. Peter Anvin suggested to switch the function to return a boolean, I > suggested to make it a macro and even sent you a patch, Jiri and David > also spent their time trying to help you, and became ignored. > > Nevertheless. NAK for the series. Whatever you end up, if it comes to > v3, please make it simple, avoid code duplication and run checkpatch. > In v1, I used the same approach as parity8() because I couldn't justify the performance impact in a specific driver or subsystem. However, multiple people commented on using __builtin_parity or an x86 assembly implementation. I'm not ignoring their feedback-I want to address these comments. Before submitting, I sent an email explaining my current approach: using David's suggested method along with __builtin_parity, but no one responded. So, I decided to submit v2 for discussion instead. To avoid mistakes in v3, I want to confirm the following changes before sending it: (a) Change the return type from int to bool. (b) Avoid __builtin_parity and use the same approach as parity8(). (c) Implement parity16/32/64() as single-line inline functions that call the next smaller variant after xor. (d) Add a parity() macro that selects the appropriate parityXX() based on type size. (e) Update users to use this parity() macro. However, (d) may require a patch affecting multiple subsystems at once since some places that already include bitops.h have functions named parity(), causing conflicts. Unless we decide not to add this macro in the end. As for checkpatch.pl warnings, they are mostly pre-existing coding style issues in this series. I've kept them as-is, but if preferred, I'm fine with fixing them. If anything is incorrect or if there are concerns, please let me know. Regards, Kuan-Wei diff --git a/include/linux/bitops.h b/include/linux/bitops.h index c1cb53cf2f0f..47b7eca8d3b7 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -260,6 +260,43 @@ static inline int parity8(u8 val) return (0x6996 >> (val & 0xf)) & 1; } +static inline bool parity16(u16 val) +{ + return parity8(val ^ (val >> 8)); +} + +static inline bool parity32(u32 val) +{ + return parity16(val ^ (val >> 16)); +} + +static inline bool parity64(u64 val) +{ + return parity32(val ^ (val >> 32)); +} + +#define parity(val) \ +({ \ + bool __ret; \ + switch (BITS_PER_TYPE(val)) { \ + case 64: \ + __ret = parity64(val); \ + break; \ + case 32: \ + __ret = parity32(val); \ + break; \ + case 16: \ + __ret = parity16(val); \ + break; \ + case 8: \ + __ret = parity8(val); \ + break; \ + default: \ + BUILD_BUG(); \ + } \ + __ret; \ +}) + /** * __ffs64 - find first set bit in a 64 bit word * @word: The 64 bit word ______________________________________________________ Linux MTD discussion mailing list http://lists.infradead.org/mailman/listinfo/linux-mtd/