Message ID | 41d93ca827a248698ec64bf57e0c05a5@AcuMS.aculab.com |
---|---|
State | New |
Headers |
Return-Path: <linux-kernel-owner@vger.kernel.org> Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:612c:172:b0:3f2:4152:657d with SMTP id h50csp2528373vqi; Mon, 18 Sep 2023 02:27:42 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHaz2Wz392/CzaJdqj7NaDPb8gzz7A9nCHZ+Sa0BAx0Qe8u6Gx42YLQGfxhfXhoGupBAqJb X-Received: by 2002:a17:903:22cd:b0:1c3:a814:a12b with SMTP id y13-20020a17090322cd00b001c3a814a12bmr11264122plg.16.1695029261841; Mon, 18 Sep 2023 02:27:41 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695029261; cv=none; d=google.com; s=arc-20160816; b=yy1az0d4DBZ9vCCKUoVCUeqqIpkr15djClCU1bM4laAeYyKVPjoF/Xe29445sCU+fl Gk2HvYaoz6L2kOssNsUmVG23jEC41EwG1JJyEZA4HY9A5x6Qun1grS2oMUb99Mr78mkh 2HRrdajo7+/O1Ay+uVdNddYY7cfszm7epxVTq76N7ANsBVzrAN3OhIUOGezdB6ks5tgt dbD+QokqWs9hvjKOUlk5Cl+AoyRXa0HwRKfxRIjPjKB8qKZNFQm+opLGHe/RHycD228H BmoKrXTNVYVIBsEneU0g7IbXvhPnXNWf8fafm2ZkBLgTB732l3nquVKgNROCqxfMFv/g 1hwQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:content-language :mime-version:accept-language:in-reply-to:references:message-id:date :thread-index:thread-topic:subject:cc:to:from; bh=0SLMQ1ToUw7Jhi3Im2T3zCFrIc6Ro5TWxpN8O+YwNgg=; fh=O7+mvh5MpI0TRpoWjlJXbuqRWYgEFgj8fdoOuxSUxxo=; b=hVQMxvzgTcW+/zYenWKL4IWsvx9ixbSSm4CtPs5p8vtvLJycnS5r6RjyRJKATg9j0C kLJfkZecyQrqDFVkKiPQTiAU/bPIzctGQbu4goAp8bJzKEU0Y7/E0RqVRQr1U64rwOIO vpMJ0M8TKU2qeCmDS82VVBLQyzt9rXpSRZZQVR5qhN9hVVB1dWUZ+MNZLhNQGYbsQrOa QkzVlFsQcLEEwunZjqRbXyNG5dqwK4w7/FQ9k5b92lXk0aZ1AQB4Xgm8Ib3Cpe40EYey Vbk4myJiNc7MgSEAYxOMY4b+GPXibaiaLH65bp9LjhAUFHB0+HYwCy6/yvhPOsYP6NgF scOw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=aculab.com Received: from howler.vger.email (howler.vger.email. [2620:137:e000::3:4]) by mx.google.com with ESMTPS id t4-20020a170902e84400b001c0993e4111si8071779plg.253.2023.09.18.02.27.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 18 Sep 2023 02:27:41 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) client-ip=2620:137:e000::3:4; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=aculab.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by howler.vger.email (Postfix) with ESMTP id B15FC82CBA67; Mon, 18 Sep 2023 01:20:18 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at howler.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S240829AbjIRITl convert rfc822-to-8bit (ORCPT <rfc822;kernel.ruili@gmail.com> + 27 others); Mon, 18 Sep 2023 04:19:41 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44858 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240996AbjIRITG (ORCPT <rfc822;linux-kernel@vger.kernel.org>); Mon, 18 Sep 2023 04:19:06 -0400 Received: from eu-smtp-delivery-151.mimecast.com (eu-smtp-delivery-151.mimecast.com [185.58.85.151]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C552412F for <linux-kernel@vger.kernel.org>; Mon, 18 Sep 2023 01:16:58 -0700 (PDT) Received: from AcuMS.aculab.com (156.67.243.121 [156.67.243.121]) by relay.mimecast.com with ESMTP with both STARTTLS and AUTH (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id uk-mta-66-K0WpNAvKPb2jQwtICPCfbQ-1; Mon, 18 Sep 2023 09:16:41 +0100 X-MC-Unique: K0WpNAvKPb2jQwtICPCfbQ-1 Received: from AcuMS.Aculab.com (10.202.163.4) by AcuMS.aculab.com (10.202.163.4) with Microsoft SMTP Server (TLS) id 15.0.1497.48; Mon, 18 Sep 2023 09:16:30 +0100 Received: from AcuMS.Aculab.com ([::1]) by AcuMS.aculab.com ([::1]) with mapi id 15.00.1497.048; Mon, 18 Sep 2023 09:16:30 +0100 From: David Laight <David.Laight@ACULAB.COM> To: "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org> CC: Linus Torvalds <torvalds@linux-foundation.org>, 'Andy Shevchenko' <andriy.shevchenko@linux.intel.com>, 'Andrew Morton' <akpm@linux-foundation.org>, "'Matthew Wilcox (Oracle)'" <willy@infradead.org>, 'Christoph Hellwig' <hch@infradead.org>, "'Jason A. Donenfeld'" <Jason@zx2c4.com> Subject: [PATCH next v4 1/5] minmax: Add umin(a, b) and umax(a, b) Thread-Topic: [PATCH next v4 1/5] minmax: Add umin(a, b) and umax(a, b) Thread-Index: AdnqCG3fyWBHnOXsRX2exERoRDa2+g== Date: Mon, 18 Sep 2023 08:16:30 +0000 Message-ID: <41d93ca827a248698ec64bf57e0c05a5@AcuMS.aculab.com> References: <b97faef60ad24922b530241c5d7c933c@AcuMS.aculab.com> In-Reply-To: <b97faef60ad24922b530241c5d7c933c@AcuMS.aculab.com> Accept-Language: en-GB, en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-exchange-transport-fromentityheader: Hosted x-originating-ip: [10.202.205.107] MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: aculab.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8BIT X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_BLOCKED,RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: <linux-kernel.vger.kernel.org> X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Mon, 18 Sep 2023 01:20:18 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1777367002962928448 X-GMAIL-MSGID: 1777367002962928448 |
Series |
minmax: Relax type checks in min() and max().
|
|
Commit Message
David Laight
Sept. 18, 2023, 8:16 a.m. UTC
These can be used when min()/max() errors a signed v unsigned
compare when the signed value is known to be non-negative.
Unlike min_t(some_unsigned_type, a, b) umin() will never
mask off high bits if an inappropriate type is selected.
The '+ 0u + 0ul + 0ull' may look strange.
The '+ 0u' is needed for 'signed int' on 64bit systems.
The '+ 0ul' is needed for 'signed long' on 32bit systems.
The '+ 0ull' is needed for 'signed long long'.
Signed-off-by: David Laight <david.laight@aculab.com>
--
v4: Rename (from min_unsigned) to shorten code lines.
Suggested by Linus.
v3: No change.
v2: Updated commit message.
---
include/linux/minmax.h | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
Comments
On Mon, Sep 18, 2023 at 08:16:30AM +0000, David Laight wrote: > +/** > + * umin - return minimum of two non-negative values > + * Signed types are zero extended to match a larger unsigned type. > + * @x: first value > + * @y: second value > + */ > +#define umin(x, y) \ > + __careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, <) Why do we match "a larger unsigned type" instead of ULL_MAX? Presumably it helps performance somehow... I agree that it's probably fine but I would be more comfortable if it skipped UINT_MAX and jumped directly to ULONG_MAX. These days 4 gigs is small potatoes. The vmalloc() function can allocate 4G so we've had integer overflow bugs with this before. regards, dan carpenter
From: Dan Carpenter > Sent: 12 January 2024 12:50 > > On Mon, Sep 18, 2023 at 08:16:30AM +0000, David Laight wrote: > > +/** > > + * umin - return minimum of two non-negative values > > + * Signed types are zero extended to match a larger unsigned type. > > + * @x: first value > > + * @y: second value > > + */ > > +#define umin(x, y) \ > > + __careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, <) > > Why do we match "a larger unsigned type" instead of ULL_MAX? Presumably > it helps performance somehow... I agree that it's probably fine but I > would be more comfortable if it skipped UINT_MAX and jumped directly to > ULONG_MAX. These days 4 gigs is small potatoes. The vmalloc() function > can allocate 4G so we've had integer overflow bugs with this before. The '+ 0ul*' carefully zero extend signed values without changing unsigned values. The compiler detects when it has zero-extended both sides and uses the smaller compare. In essence: x + 0u converts 'int' to 'unsigned int'. Avoids the sign extension adding 0ul on 64bit. x + 0ul converts a 'long' to 'unsigned long'. Avoids the sign extension adding 0ull on 32bit x + 0ull converts a 'long long' to 'unsigned long long'. You need all three to avoid sign extensions and get an unsigned compare. If the type is __int128 (signed or unsigned) then nothing happens. (which means you can still get a signed v unsigned error.) You could add in (__uint128)0 on 64bit systems that support it, but it is so uncommon it really isn't worth the hassle. Unlike any kind of cast the arithmetic cannot discard high bits. I've found a few min_t() with dubious types. One was a real bug found by someone else at much the same time. David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
On Fri, Jan 12, 2024 at 01:40:30PM +0000, David Laight wrote: > From: Dan Carpenter > > Sent: 12 January 2024 12:50 > > > > On Mon, Sep 18, 2023 at 08:16:30AM +0000, David Laight wrote: > > > +/** > > > + * umin - return minimum of two non-negative values > > > + * Signed types are zero extended to match a larger unsigned type. > > > + * @x: first value > > > + * @y: second value > > > + */ > > > +#define umin(x, y) \ > > > + __careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, <) > > > > Why do we match "a larger unsigned type" instead of ULL_MAX? Presumably > > it helps performance somehow... I agree that it's probably fine but I > > would be more comfortable if it skipped UINT_MAX and jumped directly to > > ULONG_MAX. These days 4 gigs is small potatoes. The vmalloc() function > > can allocate 4G so we've had integer overflow bugs with this before. > > The '+ 0ul*' carefully zero extend signed values without changing > unsigned values. > The compiler detects when it has zero-extended both sides and > uses the smaller compare. > In essence: > x + 0u converts 'int' to 'unsigned int'. > Avoids the sign extension adding 0ul on 64bit. > x + 0ul converts a 'long' to 'unsigned long'. > Avoids the sign extension adding 0ull on 32bit > x + 0ull converts a 'long long' to 'unsigned long long'. > You need all three to avoid sign extensions and get an unsigned > compare. So unsigned int compares are faster than unsigned long compares? It's just sort of weird how it works. min_t(unsigned long, -1, 10000000000)); => 10000000000 umin(umin(-1, 10000000000)); => UINT_MAX UINT_MAX is just kind of a random value. I would have prefered ULONG_MAX, it's equally random but it's more safe because nothing can allocate ULONG_MAX bytes. regards, dan carpenter > If the type is __int128 (signed or unsigned) then nothing happens. > (which means you can still get a signed v unsigned error.) > You could add in (__uint128)0 on 64bit systems that support it, > but it is so uncommon it really isn't worth the hassle. > > Unlike any kind of cast the arithmetic cannot discard high bits. > I've found a few min_t() with dubious types. > One was a real bug found by someone else at much the same time. > > David > > - > Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK > Registration No: 1397386 (Wales)
From: Dan Carpenter > Sent: 12 January 2024 14:03 > > On Fri, Jan 12, 2024 at 01:40:30PM +0000, David Laight wrote: > > From: Dan Carpenter > > > Sent: 12 January 2024 12:50 > > > > > > On Mon, Sep 18, 2023 at 08:16:30AM +0000, David Laight wrote: > > > > +/** > > > > + * umin - return minimum of two non-negative values > > > > + * Signed types are zero extended to match a larger unsigned type. > > > > + * @x: first value > > > > + * @y: second value > > > > + */ > > > > +#define umin(x, y) \ > > > > + __careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, <) > > > > > > Why do we match "a larger unsigned type" instead of ULL_MAX? Presumably > > > it helps performance somehow... I agree that it's probably fine but I > > > would be more comfortable if it skipped UINT_MAX and jumped directly to > > > ULONG_MAX. These days 4 gigs is small potatoes. The vmalloc() function > > > can allocate 4G so we've had integer overflow bugs with this before. > > > > The '+ 0ul*' carefully zero extend signed values without changing > > unsigned values. > > The compiler detects when it has zero-extended both sides and > > uses the smaller compare. > > In essence: > > x + 0u converts 'int' to 'unsigned int'. > > Avoids the sign extension adding 0ul on 64bit. > > x + 0ul converts a 'long' to 'unsigned long'. > > Avoids the sign extension adding 0ull on 32bit > > x + 0ull converts a 'long long' to 'unsigned long long'. > > You need all three to avoid sign extensions and get an unsigned > > compare. > > So unsigned int compares are faster than unsigned long compares? > > It's just sort of weird how it works. > > min_t(unsigned long, -1, 10000000000)); => 10000000000 > umin(umin(-1, 10000000000)); => UINT_MAX > > UINT_MAX is just kind of a random value. I would have prefered > ULONG_MAX, it's equally random but it's more safe because nothing can > allocate ULONG_MAX bytes. umin() is only defined for non-negative values. So that example is really outside the domain of the function. Consider: int x = some_positive_value; unsigned long long y; then: min_t(unsigned long long, x, y); Does (unsigned long long)x which is (unsigned long long)(long long)x and requires that x be sign extended to 64bits. On 32bit that is quite horrid. whereas: umin(x, y); Only has to zero extend x. So is compiled as: y:hi || y:lo > x ? x ; y If both values are 32bit the compiler generates a 32bit compare (even on 64bit). David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
On Fri, Jan 12, 2024 at 02:26:33PM +0000, David Laight wrote: > From: Dan Carpenter > > Sent: 12 January 2024 14:03 > > > > On Fri, Jan 12, 2024 at 01:40:30PM +0000, David Laight wrote: > > > From: Dan Carpenter > > > > Sent: 12 January 2024 12:50 > > > > > > > > On Mon, Sep 18, 2023 at 08:16:30AM +0000, David Laight wrote: > > > > > +/** > > > > > + * umin - return minimum of two non-negative values > > > > > + * Signed types are zero extended to match a larger unsigned type. > > > > > + * @x: first value > > > > > + * @y: second value > > > > > + */ > > > > > +#define umin(x, y) \ > > > > > + __careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, <) > > > > > > > > Why do we match "a larger unsigned type" instead of ULL_MAX? Presumably > > > > it helps performance somehow... I agree that it's probably fine but I > > > > would be more comfortable if it skipped UINT_MAX and jumped directly to > > > > ULONG_MAX. These days 4 gigs is small potatoes. The vmalloc() function > > > > can allocate 4G so we've had integer overflow bugs with this before. > > > > > > The '+ 0ul*' carefully zero extend signed values without changing > > > unsigned values. > > > The compiler detects when it has zero-extended both sides and > > > uses the smaller compare. > > > In essence: > > > x + 0u converts 'int' to 'unsigned int'. > > > Avoids the sign extension adding 0ul on 64bit. > > > x + 0ul converts a 'long' to 'unsigned long'. > > > Avoids the sign extension adding 0ull on 32bit > > > x + 0ull converts a 'long long' to 'unsigned long long'. > > > You need all three to avoid sign extensions and get an unsigned > > > compare. > > > > So unsigned int compares are faster than unsigned long compares? > > > > It's just sort of weird how it works. > > > > min_t(unsigned long, -1, 10000000000)); => 10000000000 > > umin(umin(-1, 10000000000)); => UINT_MAX > > > > UINT_MAX is just kind of a random value. I would have prefered > > ULONG_MAX, it's equally random but it's more safe because nothing can > > allocate ULONG_MAX bytes. > > umin() is only defined for non-negative values. I'm so confused by this. To me the big selling point of min_t() was that it clamps things to between zero and the max. > So that example is really outside the domain of the function. > > Consider: > int x = some_positive_value; > unsigned long long y; > then: > min_t(unsigned long long, x, y); > Does (unsigned long long)x which is (unsigned long long)(long long)x > and requires that x be sign extended to 64bits. > On 32bit that is quite horrid. I wasn't saying jump straight to ull. I was suggesting jump to ul then ull, but skip uint. On a 32bit system, you can't allocate ULONG_MAX bytes, so it still ends up being quite a safe number. regards, dan carpenter
diff --git a/include/linux/minmax.h b/include/linux/minmax.h index 83aebc244cba..0e89c78810f6 100644 --- a/include/linux/minmax.h +++ b/include/linux/minmax.h @@ -74,6 +74,23 @@ */ #define max(x, y) __careful_cmp(x, y, >) +/** + * umin - return minimum of two non-negative values + * Signed types are zero extended to match a larger unsigned type. + * @x: first value + * @y: second value + */ +#define umin(x, y) \ + __careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, <) + +/** + * umax - return maximum of two non-negative values + * @x: first value + * @y: second value + */ +#define umax(x, y) \ + __careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, >) + /** * min3 - return minimum of three values * @x: first value