[PATCH] randomize_range: use random long instead of int

[william....@intel.com]

From: William Roberts <william....@intel.com>

Use a long when generating the random range rather than
an int. This will produce better random distributions as
well as matching all the types at hand.

Signed-off-by: William Roberts <william....@intel.com>
---
drivers/char/random.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0158d3b..bbf11b5 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1837,7 +1837,8 @@ randomize_range(unsigned long start, unsigned long end, unsigned long len)

if (end <= start + len)
return 0;
- return PAGE_ALIGN(get_random_int() % range + start);
+
+ return PAGE_ALIGN(get_random_long() % range + start);
}

/* Interface for in-kernel drivers of true hardware RNGs.
--
1.9.1

[Kees Cook]

On Mon, Jul 25, 2016 at 11:25 AM, <william....@intel.com> wrote:
> From: William Roberts <william....@intel.com>
>
> Use a long when generating the random range rather than
> an int. This will produce better random distributions as
> well as matching all the types at hand.
>
> Signed-off-by: William Roberts <william....@intel.com>

I agree, this is what I pointed out back in Feb:
https://lkml.org/lkml/2016/2/4/854

Acked-by: Kees Cook <kees...@chromium.org>

Andrew, can you pick this up for 4.8?

-Kees

> ---
> drivers/char/random.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index 0158d3b..bbf11b5 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -1837,7 +1837,8 @@ randomize_range(unsigned long start, unsigned long end, unsigned long len)
>
> if (end <= start + len)
> return 0;
> - return PAGE_ALIGN(get_random_int() % range + start);
> +
> + return PAGE_ALIGN(get_random_long() % range + start);
> }
>
> /* Interface for in-kernel drivers of true hardware RNGs.
> --
> 1.9.1
>

--
Kees Cook
Chrome OS & Brillo Security

[Jason Cooper]

Hi William, Kees,

On Mon, Jul 25, 2016 at 11:25:41AM -0700, william....@intel.com wrote:
> From: William Roberts <william....@intel.com>
>
> Use a long when generating the random range rather than
> an int. This will produce better random distributions as
> well as matching all the types at hand.
>
> Signed-off-by: William Roberts <william....@intel.com>
> ---
> drivers/char/random.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)

Upon further review, I think we should dig into this a little bit
deeper. Standby, I'll post an RFC series shortly.

thx,

Jason.

[Jason Cooper]

Currently, all callers to randomize_range() set the length to 0 and
calculate end by adding a constant to the start address. We can
simplify the API to remove a bunch of needless checks and variables.

Use the new randomize_addr(start, range) call to set the requested
address.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---
arch/arm64/kernel/process.c | 8 ++------
1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/kernel/process.c b/arch/arm64/kernel/process.c
index 6cd2612236dc..11bf454baf86 100644
--- a/arch/arm64/kernel/process.c
+++ b/arch/arm64/kernel/process.c
@@ -374,12 +374,8 @@ unsigned long arch_align_stack(unsigned long sp)

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
- unsigned long range_end = mm->brk;
-
if (is_compat_task())
- range_end += 0x02000000;
+ return randomize_addr(mm->brk, 0x02000000);
else
- range_end += 0x40000000;
-
- return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
+ return randomize_addr(mm->brk, 0x40000000);
}
--
2.9.2

[Jason Cooper]

Currently, all callers to randomize_range() set the length to 0 and
calculate end by adding a constant to the start address. We can
simplify the API to remove a bunch of needless checks and variables.

Use the new randomize_addr(start, range) call to set the requested
address.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

arch/unicore32/kernel/process.c | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/arch/unicore32/kernel/process.c b/arch/unicore32/kernel/process.c
index 00299c927852..b856178cf167 100644
--- a/arch/unicore32/kernel/process.c
+++ b/arch/unicore32/kernel/process.c
@@ -295,8 +295,7 @@ unsigned long get_wchan(struct task_struct *p)

unsigned long arch_randomize_brk(struct mm_struct *mm)
{

- unsigned long range_end = mm->brk + 0x02000000;

- return randomize_range(mm->brk, range_end, 0) ? : mm->brk;

+ return randomize_addr(mm->brk, 0x02000000);
}

/*
--
2.9.2

[Jason Cooper]

Currently, all callers to randomize_range() set the length to 0 and
calculate end by adding a constant to the start address. We can
simplify the API to remove a bunch of needless checks and variables.

Use the new randomize_addr(start, range) call to set the requested
address.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

arch/arm/kernel/process.c | 3 +--

1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/arch/arm/kernel/process.c b/arch/arm/kernel/process.c
index 4a803c5a1ff7..02dee671cded 100644
--- a/arch/arm/kernel/process.c
+++ b/arch/arm/kernel/process.c
@@ -314,8 +314,7 @@ unsigned long get_wchan(struct task_struct *p)

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
- unsigned long range_end = mm->brk + 0x02000000;
- return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
+ return randomize_addr(mm->brk, 0x02000000);
}

#ifdef CONFIG_MMU
--
2.9.2

[Jason Cooper]

Currently, all callers to randomize_range() set the length to 0 and
calculate end by adding a constant to the start address. We can
simplify the API to remove a bunch of needless checks and variables.

Use the new randomize_addr(start, range) call to set the requested
address.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

arch/x86/kernel/process.c | 3 +--
arch/x86/kernel/sys_x86_64.c | 5 +----
2 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/arch/x86/kernel/process.c b/arch/x86/kernel/process.c
index 96becbbb52e0..a083a2c0744e 100644
--- a/arch/x86/kernel/process.c
+++ b/arch/x86/kernel/process.c
@@ -507,8 +507,7 @@ unsigned long arch_align_stack(unsigned long sp)

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
- unsigned long range_end = mm->brk + 0x02000000;
- return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
+ return randomize_addr(mm->brk, 0x02000000);
}

/*
diff --git a/arch/x86/kernel/sys_x86_64.c b/arch/x86/kernel/sys_x86_64.c
index 10e0272d789a..f9cad22808fc 100644
--- a/arch/x86/kernel/sys_x86_64.c
+++ b/arch/x86/kernel/sys_x86_64.c
@@ -101,7 +101,6 @@ static void find_start_end(unsigned long flags, unsigned long *begin,
unsigned long *end)
{
if (!test_thread_flag(TIF_ADDR32) && (flags & MAP_32BIT)) {
- unsigned long new_begin;
/* This is usually used needed to map code in small
model, so it needs to be in the first 31bit. Limit
it to that. This means we need to move the
@@ -112,9 +111,7 @@ static void find_start_end(unsigned long flags, unsigned long *begin,
*begin = 0x40000000;
*end = 0x80000000;
if (current->flags & PF_RANDOMIZE) {
- new_begin = randomize_range(*begin, *begin + 0x02000000, 0);
- if (new_begin)
- *begin = new_begin;
+ *begin = randomize_addr(*begin, 0x02000000);
}
} else {
*begin = current->mm->mmap_legacy_base;
--
2.9.2

[Jason Cooper]

Currently, all callers to randomize_range() set the length to 0 and
calculate end by adding a constant to the start address. We can
simplify the API to remove a bunch of needless checks and variables.

Use the new randomize_addr(start, range) call to set the requested
address.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

arch/tile/mm/mmap.c | 3 +--

1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/arch/tile/mm/mmap.c b/arch/tile/mm/mmap.c
index 851a94e6ae58..50f6a693a2b6 100644
--- a/arch/tile/mm/mmap.c
+++ b/arch/tile/mm/mmap.c
@@ -88,6 +88,5 @@ void arch_pick_mmap_layout(struct mm_struct *mm)

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
- unsigned long range_end = mm->brk + 0x02000000;
- return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
+ return randomize_addr(mm->brk, 0x02000000);
}

--
2.9.2

[Jason Cooper]

To date, all callers of randomize_range() have set the length to 0, and
check for a zero return value. For the current callers, the only way
to get zero returned is if end <= start. Since they are all adding a
constant to the start address, this is unnecessary.

We can remove a bunch of needless checks by simplifying the API to do
just what everyone wants, return an address between [start, start +
range].

While we're here, s/get_random_int/get_random_long/. No current call
site is adversely affected by get_random_int(), since all current range
requests are < MAX_UINT. However, we should match caller expectations
to avoid coming up short (ha!) in the future.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

drivers/char/random.c | 17 ++++-------------
include/linux/random.h | 2 +-
2 files changed, 5 insertions(+), 14 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0158d3bff7e5..1251cb2cbab2 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1822,22 +1822,13 @@ unsigned long get_random_long(void)
EXPORT_SYMBOL(get_random_long);

/*
- * randomize_range() returns a start address such that
- *
- * [...... <range> .....]
- * start end
- *
- * a <range> with size "len" starting at the return value is inside in the
- * area defined by [start, end], but is otherwise randomized.
+ * randomize_addr() returns a page aligned address within [start, start +
+ * range]
*/
unsigned long
-randomize_range(unsigned long start, unsigned long end, unsigned long len)
+randomize_addr(unsigned long start, unsigned long range)
{
- unsigned long range = end - len - start;
-
- if (end <= start + len)
- return 0;

- return PAGE_ALIGN(get_random_int() % range + start);
+ return PAGE_ALIGN(get_random_long() % range + start);
}

/* Interface for in-kernel drivers of true hardware RNGs.

diff --git a/include/linux/random.h b/include/linux/random.h
index e47e533742b5..1ad877a98186 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -34,7 +34,7 @@ extern const struct file_operations random_fops, urandom_fops;

unsigned int get_random_int(void);
unsigned long get_random_long(void);
-unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
+unsigned long randomize_addr(unsigned long start, unsigned long range);

u32 prandom_u32(void);
void prandom_bytes(void *buf, size_t nbytes);
--
2.9.2

[Jason Cooper]

All,

bah! old patch file. This should have been:

if (range == 0)
return start;
else

return PAGE_ALIGN(get_random_long() % range + start);

sorry,

Jason.

[Kees Cook]

Also, this series isn't bisectable since randomize_range gets removed
here before the callers are updated. Perhaps add a macro that calls
randomize_addr with a BUG_ON for len != 0? (And then remove it in the
last patch?)

-Kees

> {
> - unsigned long range = end - len - start;
> -
> - if (end <= start + len)
> - return 0;
> - return PAGE_ALIGN(get_random_int() % range + start);
> + return PAGE_ALIGN(get_random_long() % range + start);
> }
>
> /* Interface for in-kernel drivers of true hardware RNGs.
> diff --git a/include/linux/random.h b/include/linux/random.h
> index e47e533742b5..1ad877a98186 100644
> --- a/include/linux/random.h
> +++ b/include/linux/random.h
> @@ -34,7 +34,7 @@ extern const struct file_operations random_fops, urandom_fops;
>
> unsigned int get_random_int(void);
> unsigned long get_random_long(void);
> -unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
> +unsigned long randomize_addr(unsigned long start, unsigned long range);
>
> u32 prandom_u32(void);
> void prandom_bytes(void *buf, size_t nbytes);
> --
> 2.9.2
>

[Kees Cook]

I think range should be limited to start + range < UINTMAX, and it
should be very clear if the range is inclusive or exclusive. start =
0, range = 4096. does this mean 1 page, or 2 pages possible?

-Kees

>
> sorry,
>
> Jason.
>
>>
>> /* Interface for in-kernel drivers of true hardware RNGs.
>> diff --git a/include/linux/random.h b/include/linux/random.h
>> index e47e533742b5..1ad877a98186 100644
>> --- a/include/linux/random.h
>> +++ b/include/linux/random.h
>> @@ -34,7 +34,7 @@ extern const struct file_operations random_fops, urandom_fops;
>>
>> unsigned int get_random_int(void);
>> unsigned long get_random_long(void);
>> -unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
>> +unsigned long randomize_addr(unsigned long start, unsigned long range);
>>
>> u32 prandom_u32(void);
>> void prandom_bytes(void *buf, size_t nbytes);
>> --
>> 2.9.2
>>

[Jason Cooper]

No, I was thinking just add randomize_addr() in the first patch, convert
all the callers, then the last patch would remove randomize_range().

That way the last patch can be a cleanup in a later merge window if
needed.

thx,

Jason.

[Kees Cook]

That works too! :)

-Kees

[Jason Cooper]

Hi Kees,

On Mon, Jul 25, 2016 at 09:39:58PM -0700, Kees Cook wrote:
> On Mon, Jul 25, 2016 at 8:30 PM, Jason Cooper <ja...@lakedaemon.net> wrote:
> > On Tue, Jul 26, 2016 at 03:01:55AM +0000, Jason Cooper wrote:
> >> To date, all callers of randomize_range() have set the length to 0, and
> >> check for a zero return value. For the current callers, the only way
> >> to get zero returned is if end <= start. Since they are all adding a
> >> constant to the start address, this is unnecessary.
> >>
> >> We can remove a bunch of needless checks by simplifying the API to do
> >> just what everyone wants, return an address between [start, start +
> >> range].
> >>
> >> While we're here, s/get_random_int/get_random_long/. No current call
> >> site is adversely affected by get_random_int(), since all current range
> >> requests are < MAX_UINT. However, we should match caller expectations

merf. UINT_MAX.

ULONG_MAX? I agree.

if (range == 0 || ULONG_MAX - range < start)

return start;
else
return PAGE_ALIGN(get_random_long() % range + start);

?

> and it should be very clear if the range is inclusive or exclusive.

Sorry, I was reading the original comment, '[start, end]' with square
brackets denoting inclusive.

Regardless, the math in randomize_range() was just undoing the math at
each of the call sites. This proposed change to randomize_addr()
doesn't alter the current state of affairs wrt inclusive, exclusive.

> start = 0, range = 4096. does this mean 1 page, or 2 pages possible?

ooh, good spot. What we have right now is [start, start + range), which
is matching previous behavior. But does not match the old comment,
[start, end]. It should have been [start, end).

So, you're correct, I need to clarify this in the comments.

thx,

Jason.

[Kees Cook]

Heh, I am plagued by misspelling these constants, and yes, sorry, ULONG_MAX. :)

> if (range == 0 || ULONG_MAX - range < start)
> return start;

Should it "abort" like this? I was thinking just cap the range, something like:

if (range > ULONG_MAX - start)
range = ULONG_MAX - start

> else
> return PAGE_ALIGN(get_random_long() % range + start);
>
> ?
>
>> and it should be very clear if the range is inclusive or exclusive.
>
> Sorry, I was reading the original comment, '[start, end]' with square
> brackets denoting inclusive.
>
> Regardless, the math in randomize_range() was just undoing the math at
> each of the call sites. This proposed change to randomize_addr()
> doesn't alter the current state of affairs wrt inclusive, exclusive.
>
>> start = 0, range = 4096. does this mean 1 page, or 2 pages possible?
>
> ooh, good spot. What we have right now is [start, start + range), which
> is matching previous behavior. But does not match the old comment,
> [start, end]. It should have been [start, end).
>
> So, you're correct, I need to clarify this in the comments.

Okay, cool. Thanks! I'm glad to have this clean-up. :)

-Kees

>
> thx,
>
> Jason.

[Roberts, William C]

> -----Original Message-----
> From: Jason Cooper [mailto:ja...@lakedaemon.net]
> Sent: Monday, July 25, 2016 8:31 PM
> To: Roberts, William C <william....@intel.com>; linux-
> m...@vger.kernel.org; linux-...@vger.kernel.org; kernel-
> hard...@lists.openwall.com
> Cc: li...@arm.linux.org.uk; ak...@linux-foundation.org;
> kees...@chromium.org; ty...@mit.edu; ar...@arndb.de;
> gre...@linuxfoundation.org; catalin...@arm.com; will....@arm.com;
> ra...@linux-mips.org; be...@kernel.crashing.org; pau...@samba.org;
> m...@ellerman.id.au; da...@davemloft.net; tg...@linutronix.de;
> mi...@redhat.com; h...@zytor.com; x...@kernel.org; vi...@zeniv.linux.org.uk;
> n...@google.com; je...@google.com; aly...@android.com;
> dcas...@android.com
> Subject: Re: [RFC patch 1/6] random: Simplify API for random address requests

> > + start +

> > + * range]
> > */
> > unsigned long
> > -randomize_range(unsigned long start, unsigned long end, unsigned long
> > len)
> > +randomize_addr(unsigned long start, unsigned long range)
> > {
> > - unsigned long range = end - len - start;
> > -
> > - if (end <= start + len)
> > - return 0;
> > - return PAGE_ALIGN(get_random_int() % range + start);
> > + return PAGE_ALIGN(get_random_long() % range + start);
> > }
>
> bah! old patch file. This should have been:
>
> if (range == 0)
> return start;
> else
> return PAGE_ALIGN(get_random_long() % range + start);
>
> sorry,

Yeah that looks better. I had a similar intended set of changes locally, because of the issues Jason pointed out.
I ended up in the old case where if end - start == len it returns 0 instead of start. Jason's change is better though :-P

>
> Jason.
>
> >
> > /* Interface for in-kernel drivers of true hardware RNGs.
> > diff --git a/include/linux/random.h b/include/linux/random.h index
> > e47e533742b5..1ad877a98186 100644
> > --- a/include/linux/random.h
> > +++ b/include/linux/random.h
> > @@ -34,7 +34,7 @@ extern const struct file_operations random_fops,
> > urandom_fops;
> >
> > unsigned int get_random_int(void);
> > unsigned long get_random_long(void);
> > -unsigned long randomize_range(unsigned long start, unsigned long end,
> > unsigned long len);
> > +unsigned long randomize_addr(unsigned long start, unsigned long

> > +range);

[Yann Droneaud]

Hi,

Le mardi 26 juillet 2016 à 03:01 +0000, Jason Cooper a écrit :
> To date, all callers of randomize_range() have set the length to 0,
> and check for a zero return value.  For the current callers, the only
> way to get zero returned is if end <= start.  Since they are all
> adding a constant to the start address, this is unnecessary.
>

I agree.

> We can remove a bunch of needless checks by simplifying the API to do
> just what everyone wants, return an address between [start, start +
> range].
>

I agree.

For the record:

http://lkml.kernel.org/r/cover.139077060...@opteya.com

[Jason Cooper]

On Tue, Jul 26, 2016 at 10:07:22AM -0700, Kees Cook wrote:
> On Tue, Jul 26, 2016 at 10:00 AM, Jason Cooper <ja...@lakedaemon.net> wrote:

...

> > if (range == 0 || ULONG_MAX - range < start)
> > return start;
>
> Should it "abort" like this? I was thinking just cap the range, something like:
>
> if (range > ULONG_MAX - start)
> range = ULONG_MAX - start

yes, will do.

thx,

Jason.

[Jason Cooper]

Currently, all callers to randomize_range() set the length to 0 and
calculate end by adding a constant to the start address. We can
simplify the API to remove a bunch of needless checks and variables.

Use the new randomize_addr(start, range) call to set the requested
address.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

arch/x86/kernel/process.c | 3 +--
arch/x86/kernel/sys_x86_64.c | 5 +----
2 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/arch/x86/kernel/process.c b/arch/x86/kernel/process.c
index 96becbbb52e0..a083a2c0744e 100644
--- a/arch/x86/kernel/process.c
+++ b/arch/x86/kernel/process.c
@@ -507,8 +507,7 @@ unsigned long arch_align_stack(unsigned long sp)

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
- unsigned long range_end = mm->brk + 0x02000000;
- return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
+ return randomize_addr(mm->brk, 0x02000000);
}

[Jason Cooper]

Currently, all callers to randomize_range() set the length to 0 and
calculate end by adding a constant to the start address. We can
simplify the API to remove a bunch of needless checks and variables.

Use the new randomize_addr(start, range) call to set the requested
address.

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

arch/tile/mm/mmap.c | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/arch/tile/mm/mmap.c b/arch/tile/mm/mmap.c
index 851a94e6ae58..50f6a693a2b6 100644
--- a/arch/tile/mm/mmap.c
+++ b/arch/tile/mm/mmap.c
@@ -88,6 +88,5 @@ void arch_pick_mmap_layout(struct mm_struct *mm)

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
- unsigned long range_end = mm->brk + 0x02000000;
- return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
+ return randomize_addr(mm->brk, 0x02000000);
}

--
2.9.2

[Jason Cooper]

To date, all callers of randomize_range() have set the length to 0, and
check for a zero return value. For the current callers, the only way

to get zero returned is if end <= start. Since they are all adding a
constant to the start address, this is unnecessary.

We can remove a bunch of needless checks by simplifying the API to do
just what everyone wants, return an address between [start, start +

range).

While we're here, s/get_random_int/get_random_long/. No current call
site is adversely affected by get_random_int(), since all current range

requests are < UINT_MAX. However, we should match caller expectations

to avoid coming up short (ha!) in the future.

Address generation within [start, start + range) behavior is preserved.

All current callers to randomize_range() chose to use the start address
if randomize_range() failed. Therefore, we simplify things by just
returning the start address on error.

randomize_range() will be removed once all callers have been converted
over to randomize_addr().

Signed-off-by: Jason Cooper <ja...@lakedaemon.net>
---

drivers/char/random.c | 26 ++++++++++++++++++++++++++
include/linux/random.h | 1 +
2 files changed, 27 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0158d3bff7e5..3610774bcc53 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1840,6 +1840,32 @@ randomize_range(unsigned long start, unsigned long end, unsigned long len)

return PAGE_ALIGN(get_random_int() % range + start);
}

+/**
+ * randomize_addr - Generate a random, page aligned address
+ * @start: The smallest acceptable address the caller will take.
+ * @range: The size of the area, starting at @start, within which the
+ * random address must fall.
+ *
+ * Before page alignment, the random address generated can be any value from
+ * @start, to @start + @range - 1 inclusive.
+ *
+ * If @start + @range would overflow, @range is capped.
+ *
+ * Return: A page aligned address within [start, start + range). On error,
+ * @start is returned.
+ */
+unsigned long

+randomize_addr(unsigned long start, unsigned long range)

+{
+ if (range == 0)
+ return start;
+
+ if (start > ULONG_MAX - range)
+ range = ULONG_MAX - start;
+

+ return PAGE_ALIGN(get_random_long() % range + start);

+}
+

/* Interface for in-kernel drivers of true hardware RNGs.

* Those devices may produce endless random bits and will be throttled
* when our pool is full.
diff --git a/include/linux/random.h b/include/linux/random.h
index e47e533742b5..f1ca2fa4c071 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -35,6 +35,7 @@ extern const struct file_operations random_fops, urandom_fops;

unsigned int get_random_int(void);
unsigned long get_random_long(void);

unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
+unsigned long randomize_addr(unsigned long start, unsigned long range);

u32 prandom_u32(void);
void prandom_bytes(void *buf, size_t nbytes);

--
2.9.2

[Yann Droneaud]

Hi,

PAGE_ALIGN(start + range - 1) can be greater than start + range ..

In the worst case, when start = 0, range = ULONG_MAX, the result would
be 0.

In order to stay in the bounds, the start address must be rounded up,
and the random offset must be rounded down.

Something I haven't found the time to send was looking like this:

  unsigned long base = PAGE_ALIGN(start);

  range -= (base - start);
  range >>= PAGE_SHIFT;

  return base + ((get_random_int() % range) << PAGE_SHIFT);

Regards.

--
Yann Droneaud
OPTEYA

[Jason Cooper]

Hi Yann,

First, thanks for the review!

Ok, so I need to reword my Return desription. :)

> In the worst case, when start = 0, range = ULONG_MAX, the result would
> be 0.
>
> In order to stay in the bounds, the start address must be rounded up,
> and the random offset must be rounded down.

Well, I'm trying to preserve existing behavior. Of which, it seems to
be presumed that start was page aligned. Since it was used unaltered in
all cases when randomize_range failed.

I'll add that to the kerneldoc.

> Something I haven't found the time to send was looking like this:
>
>   unsigned long base = PAGE_ALIGN(start);
>
>   range -= (base - start);

I think the above two lines are unnecessary due to my comment above.

>   range >>= PAGE_SHIFT;
>
>   return base + ((get_random_int() % range) << PAGE_SHIFT);

However, this is interesting. Instead of a random address, you're
picking a random page. If we combine this with the requirement that
start be page aligned, we can remove the PAGE_ALIGN(). Which neatly
handles your first listed concern.

> >   On error,
> > + * @start is returned.
> > + */
> > +unsigned long
> > +randomize_addr(unsigned long start, unsigned long range)
> > +{
> > + if (range == 0)
> > + return start;
> > +
> > + if (start > ULONG_MAX - range)
> > + range = ULONG_MAX - start;
> > +
> > + return PAGE_ALIGN(get_random_long() % range + start);

On digging in to this, I found the following scenario:

start=ULONG_MAX, range=ULONG_MAX
range=0 by our second test
UB by get_random_long() % 0

This should be mitigated by swapping the tests. So, we would have:

unsigned long
randomize_addr(unsigned long start, unsigned long range)

{

if (start > ULONG_MAX - range)

range = ULONG_MAX - start;

range >>= PAGE_SHIFT;

if (range == 0)
return start;

return start + ((get_random_long() % range) << PAGE_SHIFT);
}

Look better?

thx,

Jason.