linux-kernel - Re: [PATCH 5/7] lib/random32.c: Make prandom_u32

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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	8 Jun 2014 16:48:00 -0400
From:	"George Spelvin" <linux@...izon.com>
To:	davem@...emloft.net, dborkman@...hat.com,
	hannes@...essinduktion.org, linux@...izon.com, shemminger@...l.org,
	tytso@....edu
Cc:	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 5/7] lib/random32.c: Make prandom_u32_max efficient for powers of 2

Thank you for your comments!

> Have you checked assembler output if this helps anything at all? Constant
> propagation in the compiler should be able to figure that out all by
> itself. The only places I use __builtin_constant_p today are where I
> also make use of inline assembler.

Yes, I did.  (I'll expand the commit comment for v2; my bad.)

It seems that GCC isn't smart enough to reduce this to a single shift.
With the multiply and reduce, the code looks like:
        call    prandom_u32
        xorl    %edx, %edx
        shldl   $4, %eax, %edx
        movl    %edx, %eax

Instead of the hoped-for
        call    prandom_u32
	shrl	$28, %eax

Converting to a single mask is something the compiler can't do,
because it doesn't understand that using the lsbits instead of the
msbits is okay.

With the mask, it turns into the spectacularly simple:
        call    prandom_u32
        andl    $15, %eax

An interesting question is which is preferred in general.

The AND allows non-constant powers of 2 without requiring CLZ.  But I
don't recall seeing that actually happen anywhere.  And the shift allows
a smaller encoding (8-bit rather than 32-bit immediate constant) when
the power of 2 is known at compile time and is larger than 128 (for
example, PAGE_SIZE).

Me, I thought it was in the noise and not worth stressing about,
but I also understand the hackers's urge for maximum tweaking.

The other thing that I couldn't think of a clean wrapper for is the
"probability 1 in N" case that happens in several bits of code.
For example, in drivers/mtd/ubi/debug.h, I made the following change:

 static inline int ubi_dbg_is_bitflip(const struct ubi_device *ubi)
 {
-	if (ubi->dbg.emulate_bitflips)
-		return !(prandom_u32() % 200);
-	return 0;
+	return ubi->dbg.emulate_bitflips && prandom_u32() < -1u/200;
 }

GCC doesn't know how to optimize "prandom_u32_max(200) == 0", which
is basically the same.  It spits out:

        call    prandom_u32
        movl    %eax, %edx
        movl    $200, %eax
        mull    %edx
        testl   %edx, %edx

I couldn't think of a good enough function name for this, so I just left
it as inline code.  (Using "-1u/200" rather than the technically correct
"(u32)(((u64)1 << 32)/200)" is okay as long as 200 isn't a power of 2, and
even if it were, the error wouldn't matter since it's approximate anyway.)

> Btw, IIRC there is a function is_power_of_2 somewhere. ;)

In <linux/log2.h>; thanks for the pointer.
--
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/