linux-kernel - [PATCH] avoid negative (and full-width) shifts in radix-tree.c, take 4

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-Id: <1188411176.7216.137.camel@localhost.localdomain>
Date:	Wed, 29 Aug 2007 20:12:56 +0200
From:	Peter Lund <firefly@...64.dk>
To:	Christoph Lameter <clameter@....com>
Cc:	Christoph Hellwig <hch@...radead.org>, trivial@...nel.org,
	linux-kernel@...r.kernel.org, Momchil Velikov <velco@...ata.bg>,
	"Maciej W. Rozycki" <macro@...ux-mips.org>
Subject: [PATCH] avoid negative (and full-width) shifts in radix-tree.c,
	take 4

From: Peter Lund <firefly@...64.dk>

Negative shifts are not allowed in C (the result is undefined).
Same thing with full-width shifts.

It works on most platforms but not on the VAX with gcc 4.0.1 (it results in an
"operand reserved" fault).

Applies to Linux 2.6.22.

Signed-off-by: Peter Lund <firefly@...64.dk>
---
Take 4 uses BITS_PER_LONG instead of 8 * sizeof(unsigned long)
Take 3 checks for shifts >= the width of the left value (after promotion)
Take 2 removes index, a variable I'd forgotten to remove
Take 1 avoided negative shifts, which cause a problem on the VAX

Shifting by more than the width of the value on the left is also not allowed.
I think the extra '>> 1' tacked on at the end in the original code was an attempt
to work around that.  Getting rid of that is an extra feature of this patch.

Here's the chapter and verse, taken from the final draft of the C99 standard
("6.5.7 Bitwise shift operators", paragraph 3):

  "The integer promotions are performed on each of the operands. The
  type of the result is that of the promoted left operand. If the
  value of the right operand is negative or is greater than or equal
  to the width of the promoted left operand, the behavior is
  undefined."

Thank you to Jan-Benedict Glaw, Christoph Hellwig, Maciej Rozycki,
Pekka Enberg, Andreas Schwab, and Christoph Lameter for review.  Special
thanks to Andreas for spotting that my fix only removed half the undefined
behaviour.

--- linux-2.6.22/lib/radix-tree.c.orig	2007-08-29 20:00:16.000000000 +0200
+++ linux-2.6.22/lib/radix-tree.c	2007-08-29 20:05:01.000000000 +0200
@@ -980,12 +980,14 @@

 static __init unsigned long __maxindex(unsigned int height)
 {
-	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
-	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+	unsigned int width = height * RADIX_TREE_MAP_SHIFT;
+	int shift = RADIX_TREE_INDEX_BITS - width;

-	if (tmp >= RADIX_TREE_INDEX_BITS)
-		index = ~0UL;
-	return index;
+	if (shift < 0)
+		return ~0UL;
+	if (shift >= BITS_PER_LONG)
+		return 0UL;
+	return ~0UL >> shift;
 }

 static __init void radix_tree_init_maxindex(void)

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/