Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
On Sat, Oct 08, 2022 at 10:08:03PM +, David Laight wrote: > From: Jason A. Donenfeld > > Sent: 07 October 2022 19:01 > > > > Rather than incurring a division or requesting too many random bytes for > > the given range, use the prandom_u32_max() function, which only takes > > the minimum required bytes from the RNG and avoids divisions. > > > ... > > --- a/lib/cmdline_kunit.c > > +++ b/lib/cmdline_kunit.c > > @@ -76,7 +76,7 @@ static void cmdline_test_lead_int(struct kunit *test) > > int rc = cmdline_test_values[i]; > > int offset; > > > > - sprintf(in, "%u%s", prandom_u32_max(256), str); > > + sprintf(in, "%u%s", get_random_int() % 256, str); > > /* Only first '-' after the number will advance the pointer */ > > offset = strlen(in) - strlen(str) + !!(rc == 2); > > cmdline_do_one_test(test, in, rc, offset); > > @@ -94,7 +94,7 @@ static void cmdline_test_tail_int(struct kunit *test) > > int rc = strcmp(str, "") ? (strcmp(str, "-") ? 0 : 1) : 1; > > int offset; > > > > - sprintf(in, "%s%u", str, prandom_u32_max(256)); > > + sprintf(in, "%s%u", str, get_random_int() % 256); > > /* > > * Only first and leading '-' not followed by integer > > * will advance the pointer. > > Something has gone backwards here > And get_random_u8() looks a better fit. Wrong patch version. > > David > > - > Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 > 1PT, UK > Registration No: 1397386 (Wales)
RE: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
From: Jason A. Donenfeld > Sent: 07 October 2022 19:01 > > Rather than incurring a division or requesting too many random bytes for > the given range, use the prandom_u32_max() function, which only takes > the minimum required bytes from the RNG and avoids divisions. > ... > --- a/lib/cmdline_kunit.c > +++ b/lib/cmdline_kunit.c > @@ -76,7 +76,7 @@ static void cmdline_test_lead_int(struct kunit *test) > int rc = cmdline_test_values[i]; > int offset; > > - sprintf(in, "%u%s", prandom_u32_max(256), str); > + sprintf(in, "%u%s", get_random_int() % 256, str); > /* Only first '-' after the number will advance the pointer */ > offset = strlen(in) - strlen(str) + !!(rc == 2); > cmdline_do_one_test(test, in, rc, offset); > @@ -94,7 +94,7 @@ static void cmdline_test_tail_int(struct kunit *test) > int rc = strcmp(str, "") ? (strcmp(str, "-") ? 0 : 1) : 1; > int offset; > > - sprintf(in, "%s%u", str, prandom_u32_max(256)); > + sprintf(in, "%s%u", str, get_random_int() % 256); > /* >* Only first and leading '-' not followed by integer >* will advance the pointer. Something has gone backwards here And get_random_u8() looks a better fit. David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
On Fri, Oct 07, 2022 at 08:50:43PM -0700, Kees Cook wrote:
> On October 7, 2022 7:21:28 PM PDT, "Jason A. Donenfeld"
> wrote:
> >On Fri, Oct 07, 2022 at 03:47:44PM -0700, Kees Cook wrote:
> >> On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote:
...
> >> These are more fun, but Coccinelle can still do them with a little
> >> Pythonic help:
> >>
> >> // Find a potential literal
> >> @literal_mask@
> >> expression LITERAL;
> >> identifier randfunc =~ "get_random_int|prandom_u32|get_random_u32";
> >> position p;
> >> @@
> >>
> >> (randfunc()@p & (LITERAL))
> >>
> >> // Add one to the literal.
> >> @script:python add_one@
> >> literal << literal_mask.LITERAL;
> >> RESULT;
> >> @@
> >>
> >> if literal.startswith('0x'):
> >> value = int(literal, 16) + 1
> >> coccinelle.RESULT = cocci.make_expr("0x%x" % (value))
> >> elif literal[0] in '123456789':
> >> value = int(literal, 10) + 1
> >> coccinelle.RESULT = cocci.make_expr("%d" % (value))
> >> else:
> >> print("I don't know how to handle: %s" % (literal))
Wouldn't Python take care about (known) prefixes itself?
try:
x = int(literal)
except ValueError as ex:
print(..., ex.error)
> >> // Replace the literal mask with the calculated result.
> >> @plus_one@
> >> expression literal_mask.LITERAL;
> >> position literal_mask.p;
> >> expression add_one.RESULT;
> >> identifier FUNC;
> >> @@
> >>
> >> - (FUNC()@p & (LITERAL))
> >> + prandom_u32_max(RESULT)
> >
> >Oh that's pretty cool. I can do the saturation check in python, since
> >`value` holds the parsed result. Neat.
>
> It is (at least how I have it here) just the string, so YMMV.
...
> >Thanks a bunch for the guidance.
>
> Sure thing! I was pleased to figure out how to do the python bit.
I believe it can be optimized
--
With Best Regards,
Andy Shevchenko
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
> >> @minus_one@ > >> expression FULL; > >> @@ > >> > >> - (get_random_int() & ((FULL) - 1) > >> + prandom_u32_max(FULL) > > > >Ahh, well, okay, this is the example I mentioned above. Only works if > >FULL is saturated. Any clever way to get coccinelle to prove that? Can > >it look at the value of constants? > > I'm not sure if Cocci will do that without a lot of work. The literals trick > I used below would need a lot of fanciness. :) If FULL is an arbitrary expression, it would not be easy to automate. If it is a constant then you can use python/ocaml to analyze its value. But if it's a #define constant then you would need a previous rule to match the #define and find that value. For LITERAL, I think you could just do constant int LITERAL; for the metavariable declaration. julia
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
[resending because I failed to CC]
On October 7, 2022 7:21:28 PM PDT, "Jason A. Donenfeld" wrote:
>On Fri, Oct 07, 2022 at 03:47:44PM -0700, Kees Cook wrote:
>> On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote:
>> > Rather than incurring a division or requesting too many random bytes for
>> > the given range, use the prandom_u32_max() function, which only takes
>> > the minimum required bytes from the RNG and avoids divisions.
>>
>> I actually meant splitting the by-hand stuff by subsystem, but nearly
>> all of these can be done mechanically too, so it shouldn't be bad. Notes
>> below...
>
>Oh, cool, more coccinelle. You're basically giving me a class on these
>recipes. Much appreciated.
You're welcome! This was a fun exercise. :)
>
>> > [...]
>> > diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
>> > index 92bcc1768f0b..87203429f802 100644
>> > --- a/arch/arm64/kernel/process.c
>> > +++ b/arch/arm64/kernel/process.c
>> > @@ -595,7 +595,7 @@ unsigned long __get_wchan(struct task_struct *p)
>> > unsigned long arch_align_stack(unsigned long sp)
>> > {
>> >if (!(current->personality & ADDR_NO_RANDOMIZE) && randomize_va_space)
>> > - sp -= get_random_int() & ~PAGE_MASK;
>> > + sp -= prandom_u32_max(PAGE_SIZE);
>> >return sp & ~0xf;
>> > }
>> >
>>
>> @mask@
>> expression MASK;
>> @@
>>
>> - (get_random_int() & ~(MASK))
>> + prandom_u32_max(MASK)
>
>Not quite! PAGE_MASK != PAGE_SIZE. In this case, things get a litle
>more complicated where you can do:
>
>get_random_int() & MASK == prandom_u32_max(MASK + 1)
>*only if all the top bits of MASK are set* That is, if MASK one less
Oh whoops! Yes, right, I totally misread SIZE as MASK.
>than a power of two. Or if MASK & (MASK + 1) == 0.
>
>(If those top bits aren't set, you can technically do
>prandom_u32_max(MASK >> n + 1) << n. That'd be a nice thing to work out.
>But yeesh, maybe a bit much for the time being and probably a bit beyond
>coccinelle.)
>
>This case here, though, is a bit more special, where we can just rely on
>an obvious given kernel identity. Namely, PAGE_MASK == ~(PAGE_SIZE - 1).
>So ~PAGE_MASK == PAGE_SIZE - 1.
>So get_random_int() & ~PAGE_MASK == prandom_u32_max(PAGE_SIZE - 1 + 1).
>So get_random_int() & ~PAGE_MASK == prandom_u32_max(PAGE_SIZE).
>
>And most importantly, this makes the code more readable, since everybody
>knows what bounding by PAGE_SIZE means, where as what on earth is
>happening with the &~PAGE_MASK thing. So it's a good change. I'll try to
>teach coccinelle about that special case.
Yeah, it should be possible to just check for the literal.
>
>
>
>> > diff --git a/arch/loongarch/kernel/vdso.c b/arch/loongarch/kernel/vdso.c
>> > index f32c38abd791..8c9826062652 100644
>> > --- a/arch/loongarch/kernel/vdso.c
>> > +++ b/arch/loongarch/kernel/vdso.c
>> > @@ -78,7 +78,7 @@ static unsigned long vdso_base(void)
>> >unsigned long base = STACK_TOP;
>> >
>> >if (current->flags & PF_RANDOMIZE) {
>> > - base += get_random_int() & (VDSO_RANDOMIZE_SIZE - 1);
>> > + base += prandom_u32_max(VDSO_RANDOMIZE_SIZE);
>> >base = PAGE_ALIGN(base);
>> >}
>> >
>>
>> @minus_one@
>> expression FULL;
>> @@
>>
>> - (get_random_int() & ((FULL) - 1)
>> + prandom_u32_max(FULL)
>
>Ahh, well, okay, this is the example I mentioned above. Only works if
>FULL is saturated. Any clever way to get coccinelle to prove that? Can
>it look at the value of constants?
I'm not sure if Cocci will do that without a lot of work. The literals trick I
used below would need a lot of fanciness. :)
>
>>
>> > diff --git a/arch/parisc/kernel/vdso.c b/arch/parisc/kernel/vdso.c
>> > index 63dc44c4c246..47e5960a2f96 100644
>> > --- a/arch/parisc/kernel/vdso.c
>> > +++ b/arch/parisc/kernel/vdso.c
>> > @@ -75,7 +75,7 @@ int arch_setup_additional_pages(struct linux_binprm
>> > *bprm,
>> >
>> >map_base = mm->mmap_base;
>> >if (current->flags & PF_RANDOMIZE)
>> > - map_base -= (get_random_int() & 0x1f) * PAGE_SIZE;
>> > + map_base -= prandom_u32_max(0x20) * PAGE_SIZE;
>> >
>> >vdso_text_start = get_unmapped_area(NULL, map_base, vdso_text_len, 0,
>> > 0);
>> >
>>
>> These are more fun, but Coccinelle can still do them with a little
>> Pythonic help:
>>
>> // Find a potential literal
>> @literal_mask@
>> expression LITERAL;
>> identifier randfunc =~ "get_random_int|prandom_u32|get_random_u32";
>> position p;
>> @@
>>
>> (randfunc()@p & (LITERAL))
>>
>> // Add one to the literal.
>> @script:python add_one@
>> literal << literal_mask.LITERAL;
>> RESULT;
>> @@
>>
>> if literal.startswith('0x'):
>> value = int(literal, 16) + 1
>> coccinelle.RESULT = cocci.make_expr("0x%x" % (value))
>> elif literal[0] in '123456789':
>> value = int(literal, 10) + 1
>> coccinelle.RESULT = cocci.make_expr("%d" % (value))
>> else:
>> print("I don't know how to handle: %s" % (literal))
>>
>> //
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
On Fri, Oct 07, 2022 at 03:47:44PM -0700, Kees Cook wrote:
> > diff --git a/lib/test_vmalloc.c b/lib/test_vmalloc.c
> > index 4f2f2d1bac56..56ffaa8dd3f6 100644
> > --- a/lib/test_vmalloc.c
> > +++ b/lib/test_vmalloc.c
> > @@ -151,9 +151,7 @@ static int random_size_alloc_test(void)
> > int i;
> >
> > for (i = 0; i < test_loop_count; i++) {
> > - n = prandom_u32();
> > - n = (n % 100) + 1;
> > -
> > + n = prandom_u32_max(n % 100) + 1;
> > p = vmalloc(n * PAGE_SIZE);
> >
> > if (!p)
>
> This looks wrong. Cocci says:
>
> - n = prandom_u32();
> - n = (n % 100) + 1;
> + n = prandom_u32_max(100) + 1;
I agree that's wrong, but what rule did you use to make Cocci generate
that?
Jason
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
On Fri, Oct 07, 2022 at 03:47:44PM -0700, Kees Cook wrote:
> On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote:
> > Rather than incurring a division or requesting too many random bytes for
> > the given range, use the prandom_u32_max() function, which only takes
> > the minimum required bytes from the RNG and avoids divisions.
>
> I actually meant splitting the by-hand stuff by subsystem, but nearly
> all of these can be done mechanically too, so it shouldn't be bad. Notes
> below...
Oh, cool, more coccinelle. You're basically giving me a class on these
recipes. Much appreciated.
> > [...]
> > diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
> > index 92bcc1768f0b..87203429f802 100644
> > --- a/arch/arm64/kernel/process.c
> > +++ b/arch/arm64/kernel/process.c
> > @@ -595,7 +595,7 @@ unsigned long __get_wchan(struct task_struct *p)
> > unsigned long arch_align_stack(unsigned long sp)
> > {
> > if (!(current->personality & ADDR_NO_RANDOMIZE) && randomize_va_space)
> > - sp -= get_random_int() & ~PAGE_MASK;
> > + sp -= prandom_u32_max(PAGE_SIZE);
> > return sp & ~0xf;
> > }
> >
>
> @mask@
> expression MASK;
> @@
>
> - (get_random_int() & ~(MASK))
> + prandom_u32_max(MASK)
Not quite! PAGE_MASK != PAGE_SIZE. In this case, things get a litle
more complicated where you can do:
get_random_int() & MASK == prandom_u32_max(MASK + 1)
*only if all the top bits of MASK are set* That is, if MASK one less
than a power of two. Or if MASK & (MASK + 1) == 0.
(If those top bits aren't set, you can technically do
prandom_u32_max(MASK >> n + 1) << n. That'd be a nice thing to work out.
But yeesh, maybe a bit much for the time being and probably a bit beyond
coccinelle.)
This case here, though, is a bit more special, where we can just rely on
an obvious given kernel identity. Namely, PAGE_MASK == ~(PAGE_SIZE - 1).
So ~PAGE_MASK == PAGE_SIZE - 1.
So get_random_int() & ~PAGE_MASK == prandom_u32_max(PAGE_SIZE - 1 + 1).
So get_random_int() & ~PAGE_MASK == prandom_u32_max(PAGE_SIZE).
And most importantly, this makes the code more readable, since everybody
knows what bounding by PAGE_SIZE means, where as what on earth is
happening with the &~PAGE_MASK thing. So it's a good change. I'll try to
teach coccinelle about that special case.
> > diff --git a/arch/loongarch/kernel/vdso.c b/arch/loongarch/kernel/vdso.c
> > index f32c38abd791..8c9826062652 100644
> > --- a/arch/loongarch/kernel/vdso.c
> > +++ b/arch/loongarch/kernel/vdso.c
> > @@ -78,7 +78,7 @@ static unsigned long vdso_base(void)
> > unsigned long base = STACK_TOP;
> >
> > if (current->flags & PF_RANDOMIZE) {
> > - base += get_random_int() & (VDSO_RANDOMIZE_SIZE - 1);
> > + base += prandom_u32_max(VDSO_RANDOMIZE_SIZE);
> > base = PAGE_ALIGN(base);
> > }
> >
>
> @minus_one@
> expression FULL;
> @@
>
> - (get_random_int() & ((FULL) - 1)
> + prandom_u32_max(FULL)
Ahh, well, okay, this is the example I mentioned above. Only works if
FULL is saturated. Any clever way to get coccinelle to prove that? Can
it look at the value of constants?
>
> > diff --git a/arch/parisc/kernel/vdso.c b/arch/parisc/kernel/vdso.c
> > index 63dc44c4c246..47e5960a2f96 100644
> > --- a/arch/parisc/kernel/vdso.c
> > +++ b/arch/parisc/kernel/vdso.c
> > @@ -75,7 +75,7 @@ int arch_setup_additional_pages(struct linux_binprm *bprm,
> >
> > map_base = mm->mmap_base;
> > if (current->flags & PF_RANDOMIZE)
> > - map_base -= (get_random_int() & 0x1f) * PAGE_SIZE;
> > + map_base -= prandom_u32_max(0x20) * PAGE_SIZE;
> >
> > vdso_text_start = get_unmapped_area(NULL, map_base, vdso_text_len, 0,
> > 0);
> >
>
> These are more fun, but Coccinelle can still do them with a little
> Pythonic help:
>
> // Find a potential literal
> @literal_mask@
> expression LITERAL;
> identifier randfunc =~ "get_random_int|prandom_u32|get_random_u32";
> position p;
> @@
>
> (randfunc()@p & (LITERAL))
>
> // Add one to the literal.
> @script:python add_one@
> literal << literal_mask.LITERAL;
> RESULT;
> @@
>
> if literal.startswith('0x'):
> value = int(literal, 16) + 1
> coccinelle.RESULT = cocci.make_expr("0x%x" % (value))
> elif literal[0] in '123456789':
> value = int(literal, 10) + 1
> coccinelle.RESULT = cocci.make_expr("%d" % (value))
> else:
> print("I don't know how to handle: %s" % (literal))
>
> // Replace the literal mask with the calculated result.
> @plus_one@
> expression literal_mask.LITERAL;
> position literal_mask.p;
> expression add_one.RESULT;
> identifier FUNC;
> @@
>
> - (FUNC()@p & (LITERAL))
> + prandom_u32_max(RESULT)
Oh that's pretty cool. I can do the saturation check in python, since
`value` holds the parsed result. Neat.
> > diff --git a/fs/ext2/ialloc.c b/fs/ext2/ialloc.c
> > index 998dd2ac8008..f4944c4dee60 100644
> > --- a/fs/ext2/ialloc.c
> > +++
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
On Fri, Oct 07, 2022 at 02:17:22PM -0700, Darrick J. Wong wrote:
> On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote:
> > Rather than incurring a division or requesting too many random bytes for
> > the given range, use the prandom_u32_max() function, which only takes
> > the minimum required bytes from the RNG and avoids divisions.
> >
> > Reviewed-by: Kees Cook
> > Reviewed-by: KP Singh
> > Reviewed-by: Christoph Böhmwalder # for
> > drbd
> > Reviewed-by: Jan Kara # for ext2, ext4, and sbitmap
> > Signed-off-by: Jason A. Donenfeld
> > ---
>
>
>
> > diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
> > index e2bdf089c0a3..6261599bb389 100644
> > --- a/fs/xfs/libxfs/xfs_alloc.c
> > +++ b/fs/xfs/libxfs/xfs_alloc.c
> > @@ -1520,7 +1520,7 @@ xfs_alloc_ag_vextent_lastblock(
> >
> > #ifdef DEBUG
> > /* Randomly don't execute the first algorithm. */
> > - if (prandom_u32() & 1)
> > + if (prandom_u32_max(2))
>
> I wonder if these usecases (picking 0 or 1 randomly) ought to have a
> trivial wrapper to make it more obvious that we want boolean semantics:
>
> static inline bool prandom_bool(void)
> {
> return prandom_u32_max(2);
> }
>
> if (prandom_bool())
> use_crazy_algorithm(...);
>
Yea, I've had a lot of similar ideas there. Part of doing this (initial)
patchset is to get an intuitive sense of what's actually used and how
often. On my list for investigation are a get_random_u32_max() to return
uniform numbers by rejection sampling (prandom_u32_max() doesn't do
that uniformly) and adding a function for booleans or bits < 8. Possible
ideas for the latter include:
bool get_random_bool(void);
bool get_random_bool(unsigned int probability);
bool get_random_bits(u8 bits_less_than_eight);
With the core of all of those involving the same batching as the current
get_random_u{8,16,32,64}() functions, but also buffering the latest byte
and managing how many bits are left in it that haven't been shifted out
yet.
So API-wise, there are a few ways to go, so hopefully this series will
start to give a good picture of what's needed.
One thing I've noticed is that most of the prandom_u32_max(2)
invocations are in debug or test code, so that doesn't need to be
optimized. But kfence does that too in its hot path, so a
get_random_bool() function there would in theory lead to an 8x speed-up.
But I guess I just have to try some things and see.
Anyway, that is a long way to say, I share you curiosity on the matter
and I'm looking into it.
Jason
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote:
> Rather than incurring a division or requesting too many random bytes for
> the given range, use the prandom_u32_max() function, which only takes
> the minimum required bytes from the RNG and avoids divisions.
I actually meant splitting the by-hand stuff by subsystem, but nearly
all of these can be done mechanically too, so it shouldn't be bad. Notes
below...
>
> [...]
> diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
> index 92bcc1768f0b..87203429f802 100644
> --- a/arch/arm64/kernel/process.c
> +++ b/arch/arm64/kernel/process.c
> @@ -595,7 +595,7 @@ unsigned long __get_wchan(struct task_struct *p)
> unsigned long arch_align_stack(unsigned long sp)
> {
> if (!(current->personality & ADDR_NO_RANDOMIZE) && randomize_va_space)
> - sp -= get_random_int() & ~PAGE_MASK;
> + sp -= prandom_u32_max(PAGE_SIZE);
> return sp & ~0xf;
> }
>
@mask@
expression MASK;
@@
- (get_random_int() & ~(MASK))
+ prandom_u32_max(MASK)
> diff --git a/arch/loongarch/kernel/vdso.c b/arch/loongarch/kernel/vdso.c
> index f32c38abd791..8c9826062652 100644
> --- a/arch/loongarch/kernel/vdso.c
> +++ b/arch/loongarch/kernel/vdso.c
> @@ -78,7 +78,7 @@ static unsigned long vdso_base(void)
> unsigned long base = STACK_TOP;
>
> if (current->flags & PF_RANDOMIZE) {
> - base += get_random_int() & (VDSO_RANDOMIZE_SIZE - 1);
> + base += prandom_u32_max(VDSO_RANDOMIZE_SIZE);
> base = PAGE_ALIGN(base);
> }
>
@minus_one@
expression FULL;
@@
- (get_random_int() & ((FULL) - 1)
+ prandom_u32_max(FULL)
> diff --git a/arch/parisc/kernel/vdso.c b/arch/parisc/kernel/vdso.c
> index 63dc44c4c246..47e5960a2f96 100644
> --- a/arch/parisc/kernel/vdso.c
> +++ b/arch/parisc/kernel/vdso.c
> @@ -75,7 +75,7 @@ int arch_setup_additional_pages(struct linux_binprm *bprm,
>
> map_base = mm->mmap_base;
> if (current->flags & PF_RANDOMIZE)
> - map_base -= (get_random_int() & 0x1f) * PAGE_SIZE;
> + map_base -= prandom_u32_max(0x20) * PAGE_SIZE;
>
> vdso_text_start = get_unmapped_area(NULL, map_base, vdso_text_len, 0,
> 0);
>
These are more fun, but Coccinelle can still do them with a little
Pythonic help:
// Find a potential literal
@literal_mask@
expression LITERAL;
identifier randfunc =~ "get_random_int|prandom_u32|get_random_u32";
position p;
@@
(randfunc()@p & (LITERAL))
// Add one to the literal.
@script:python add_one@
literal << literal_mask.LITERAL;
RESULT;
@@
if literal.startswith('0x'):
value = int(literal, 16) + 1
coccinelle.RESULT = cocci.make_expr("0x%x" % (value))
elif literal[0] in '123456789':
value = int(literal, 10) + 1
coccinelle.RESULT = cocci.make_expr("%d" % (value))
else:
print("I don't know how to handle: %s" % (literal))
// Replace the literal mask with the calculated result.
@plus_one@
expression literal_mask.LITERAL;
position literal_mask.p;
expression add_one.RESULT;
identifier FUNC;
@@
- (FUNC()@p & (LITERAL))
+ prandom_u32_max(RESULT)
> diff --git a/drivers/mtd/tests/stresstest.c b/drivers/mtd/tests/stresstest.c
> index cb29c8c1b370..d2faaca7f19d 100644
> --- a/drivers/mtd/tests/stresstest.c
> +++ b/drivers/mtd/tests/stresstest.c
> @@ -45,9 +45,8 @@ static int rand_eb(void)
> unsigned int eb;
>
> again:
> - eb = prandom_u32();
> /* Read or write up 2 eraseblocks at a time - hence 'ebcnt - 1' */
> - eb %= (ebcnt - 1);
> + eb = prandom_u32_max(ebcnt - 1);
> if (bbt[eb])
> goto again;
> return eb;
This can also be done mechanically:
@multi_line@
identifier randfunc =~ "get_random_int|prandom_u32|get_random_u32";
identifier RAND;
expression E;
@@
- RAND = randfunc();
... when != RAND
- RAND %= (E);
+ RAND = prandom_u32_max(E);
@collapse_ret@
type TYPE;
identifier VAR;
expression E;
@@
{
- TYPE VAR;
- VAR = (E);
- return VAR;
+ return E;
}
@drop_var@
type TYPE;
identifier VAR;
@@
{
- TYPE VAR;
... when != VAR
}
> diff --git a/fs/ext2/ialloc.c b/fs/ext2/ialloc.c
> index 998dd2ac8008..f4944c4dee60 100644
> --- a/fs/ext2/ialloc.c
> +++ b/fs/ext2/ialloc.c
> @@ -277,8 +277,7 @@ static int find_group_orlov(struct super_block *sb,
> struct inode *parent)
> int best_ndir = inodes_per_group;
> int best_group = -1;
>
> - group = prandom_u32();
> - parent_group = (unsigned)group % ngroups;
> + parent_group = prandom_u32_max(ngroups);
> for (i = 0; i < ngroups; i++) {
> group = (parent_group + i) % ngroups;
> desc = ext2_get_group_desc (sb, group, NULL);
Okay, that one is too much for me -- checking that group is never used
after the assignment removal is likely possible, but beyond my cocci
Re: [PATCH v4 2/6] treewide: use prandom_u32_max() when possible
On Fri, Oct 07, 2022 at 12:01:03PM -0600, Jason A. Donenfeld wrote:
> Rather than incurring a division or requesting too many random bytes for
> the given range, use the prandom_u32_max() function, which only takes
> the minimum required bytes from the RNG and avoids divisions.
>
> Reviewed-by: Kees Cook
> Reviewed-by: KP Singh
> Reviewed-by: Christoph Böhmwalder # for
> drbd
> Reviewed-by: Jan Kara # for ext2, ext4, and sbitmap
> Signed-off-by: Jason A. Donenfeld
> ---
> diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
> index e2bdf089c0a3..6261599bb389 100644
> --- a/fs/xfs/libxfs/xfs_alloc.c
> +++ b/fs/xfs/libxfs/xfs_alloc.c
> @@ -1520,7 +1520,7 @@ xfs_alloc_ag_vextent_lastblock(
>
> #ifdef DEBUG
> /* Randomly don't execute the first algorithm. */
> - if (prandom_u32() & 1)
> + if (prandom_u32_max(2))
I wonder if these usecases (picking 0 or 1 randomly) ought to have a
trivial wrapper to make it more obvious that we want boolean semantics:
static inline bool prandom_bool(void)
{
return prandom_u32_max(2);
}
if (prandom_bool())
use_crazy_algorithm(...);
But this translation change looks correct to me, so for the XFS parts:
Acked-by: Darrick J. Wong
--D
> return 0;
> #endif
>
> diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
> index 6cdfd64bc56b..7838b31126e2 100644
> --- a/fs/xfs/libxfs/xfs_ialloc.c
> +++ b/fs/xfs/libxfs/xfs_ialloc.c
> @@ -636,7 +636,7 @@ xfs_ialloc_ag_alloc(
> /* randomly do sparse inode allocations */
> if (xfs_has_sparseinodes(tp->t_mountp) &&
> igeo->ialloc_min_blks < igeo->ialloc_blks)
> - do_sparse = prandom_u32() & 1;
> + do_sparse = prandom_u32_max(2);
> #endif
>
> /*
> diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
> index 4b71a96190a8..66ee9b4b7925 100644
> --- a/include/linux/nodemask.h
> +++ b/include/linux/nodemask.h
> @@ -509,7 +509,7 @@ static inline int node_random(const nodemask_t *maskp)
> w = nodes_weight(*maskp);
> if (w)
> bit = bitmap_ord_to_pos(maskp->bits,
> - get_random_int() % w, MAX_NUMNODES);
> + prandom_u32_max(w), MAX_NUMNODES);
> return bit;
> #else
> return 0;
> diff --git a/lib/cmdline_kunit.c b/lib/cmdline_kunit.c
> index e6a31c927b06..a72a2c16066e 100644
> --- a/lib/cmdline_kunit.c
> +++ b/lib/cmdline_kunit.c
> @@ -76,7 +76,7 @@ static void cmdline_test_lead_int(struct kunit *test)
> int rc = cmdline_test_values[i];
> int offset;
>
> - sprintf(in, "%u%s", prandom_u32_max(256), str);
> + sprintf(in, "%u%s", get_random_int() % 256, str);
> /* Only first '-' after the number will advance the pointer */
> offset = strlen(in) - strlen(str) + !!(rc == 2);
> cmdline_do_one_test(test, in, rc, offset);
> @@ -94,7 +94,7 @@ static void cmdline_test_tail_int(struct kunit *test)
> int rc = strcmp(str, "") ? (strcmp(str, "-") ? 0 : 1) : 1;
> int offset;
>
> - sprintf(in, "%s%u", str, prandom_u32_max(256));
> + sprintf(in, "%s%u", str, get_random_int() % 256);
> /*
>* Only first and leading '-' not followed by integer
>* will advance the pointer.
> diff --git a/lib/kobject.c b/lib/kobject.c
> index 5f0e71ab292c..a0b2dbfcfa23 100644
> --- a/lib/kobject.c
> +++ b/lib/kobject.c
> @@ -694,7 +694,7 @@ static void kobject_release(struct kref *kref)
> {
> struct kobject *kobj = container_of(kref, struct kobject, kref);
> #ifdef CONFIG_DEBUG_KOBJECT_RELEASE
> - unsigned long delay = HZ + HZ * (get_random_int() & 0x3);
> + unsigned long delay = HZ + HZ * prandom_u32_max(4);
> pr_info("kobject: '%s' (%p): %s, parent %p (delayed %ld)\n",
>kobject_name(kobj), kobj, __func__, kobj->parent, delay);
> INIT_DELAYED_WORK(>release, kobject_delayed_cleanup);
> diff --git a/lib/reed_solomon/test_rslib.c b/lib/reed_solomon/test_rslib.c
> index 6faf9c9a6215..4d241bdc88aa 100644
> --- a/lib/reed_solomon/test_rslib.c
> +++ b/lib/reed_solomon/test_rslib.c
> @@ -199,7 +199,7 @@ static int get_rcw_we(struct rs_control *rs, struct
> wspace *ws,
>
> derrlocs[i] = errloc;
>
> - if (ewsc && (prandom_u32() & 1)) {
> + if (ewsc && prandom_u32_max(2)) {
> /* Erasure with the symbol intact */
> errlocs[errloc] = 2;
> } else {
> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index c4f04edf3ee9..ef0661504561 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -21,7 +21,7 @@ static int init_alloc_hint(struct sbitmap *sb, gfp_t flags)
> int i;
>
> for_each_possible_cpu(i)
> - *per_cpu_ptr(sb->alloc_hint, i) = prandom_u32() % depth;
> +
