Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data)

[Linus Torvalds <torvalds@linux-foundation.org>]

On Sat, 15 Dec 2007, Herbert Xu wrote:
> 
> There ought to be a warning about this sort of thing.

We could add it to sparse. The appended (untested) patch seems to say 
there's a lot of those signed divides-by-power-of-twos.

However, the problem with such warnings is that it encourages people to do 
the simple fix that may be *wrong*. For example, you fixed it with patches 
like

> -		int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
> +		int rsvd = r->limit ? 0 : random_read_wakeup_thresh / 4u;

which is really quite dangerous for several reasons:

 - it depends intimately on the type of the thing being divided (try it: 
   it will do nothing at all if the thing you divide is larger than 
   "unsigned int", since then the "4u" will be turned into a _signed_ 
   larger type by the C type expansion).

   So in general, the above doesn't even do what it's supposed to do on a 
   64-bit architecture if the thing to be divided is 64-bit!

 - it changes behaviour. If that thing really is signed and can be 
   negative, that "trivial" patch just changed the divide to be 
   fundamentally something totally different.

so I think this patch is horribly wrong.

The *correct* way to fix signed divisions is by doing one of two things:

 - really make the data we divide be unsigned. With all the thinking that 
   involves!

   This is the good change, but it does involve making sure that there are 
   no tests against zero and that the value really cannot go negative. 
   Usually the unsigned types are (a) faster and (b) more robust, but if 
   somebody is depending on signs, unsigned types are obviously not 
   appropriate.

 - change a divide-by-power-of-2 into a signed shift instead.

   Yes, this also changes the end result for negative values, but it 
   changes it in a sane and generally good way (ie it will still be a 
   "valid" divide, it will just be a divide that rounds differently, and 
   is more likely than turning it into an unsigned divide to generally 
   result in working code).

Hmm?

			Linus
---
 simplify.c |   30 ++++++++++++++++++++++++++++++
 1 files changed, 30 insertions(+), 0 deletions(-)

diff --git a/simplify.c b/simplify.c
index 94e14d2..91f1120 100644
--- a/simplify.c
+++ b/simplify.c
@@ -286,6 +286,36 @@ static int simplify_constant_rightside(struct instruction *insn)
 		if (!value)
 			return replace_with_pseudo(insn, insn->src2);
 		return 0;
+
+	case OP_DIVU: case OP_DIVS:
+		if (!value)
+			break;
+		if (value == 1)
+			return replace_with_pseudo(insn, insn->src1);
+		/* Power-of-two? */
+		if (!(value & (value-1))) {
+			int log2 = -1;
+			do {
+				log2++;
+				value >>= 1;
+			} while (value);
+
+			/* Turn unsigned divides into shifts */
+			if (insn->opcode == OP_DIVU) {
+				insn->src2->value = log2;
+				insn->opcode = OP_LSR;
+				return 1;
+			}
+
+			/*
+			 * This is incorrect, but we care more about
+			 * the warning than the code generation
+			 */
+			warning(insn->pos, "expensive signed divide");
+			insn->src2->value = log2;
+			insn->opcode = OP_ASR;
+			return 1;
+		}
 	}
 	return 0;
 }