2021-01-18 20:29:19

by Jason Gunthorpe

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On Mon, Jan 18, 2021 at 03:08:51PM -0500, Douglas Gilbert wrote:
> On 2021-01-18 1:28 p.m., Jason Gunthorpe wrote:
> > On Mon, Jan 18, 2021 at 11:30:03AM -0500, Douglas Gilbert wrote:
> >
> > > After several flawed attempts to detect overflow, take the fastest
> > > route by stating as a pre-condition that the 'order' function argument
> > > cannot exceed 16 (2^16 * 4k = 256 MiB).
> >
> > That doesn't help, the point of the overflow check is similar to
> > overflow checks in kcalloc: to prevent the routine from allocating
> > less memory than the caller might assume.
> >
> > For instance ipr_store_update_fw() uses request_firmware() (which is
> > controlled by userspace) to drive the length argument to
> > sgl_alloc_order(). If userpace gives too large a value this will
> > corrupt kernel memory.
> >
> > So this math:
> >
> > nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
>
> But that check itself overflows if order is too large (e.g. 65).

I don't reall care about order. It is always controlled by the kernel
and it is fine to just require it be low enough to not
overflow. length is the data under userspace control so math on it
must be checked for overflow.

> Also note there is another pre-condition statement in that function's
> definition, namely that length cannot be 0.

I don't see callers checking for that either, if it is true length 0
can't be allowed it should be blocked in the function

Jason


2021-01-18 21:28:21

by Bodo Stroesser

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On 18.01.21 21:24, Jason Gunthorpe wrote:
> On Mon, Jan 18, 2021 at 03:08:51PM -0500, Douglas Gilbert wrote:
>> On 2021-01-18 1:28 p.m., Jason Gunthorpe wrote:
>>> On Mon, Jan 18, 2021 at 11:30:03AM -0500, Douglas Gilbert wrote:
>>>
>>>> After several flawed attempts to detect overflow, take the fastest
>>>> route by stating as a pre-condition that the 'order' function argument
>>>> cannot exceed 16 (2^16 * 4k = 256 MiB).
>>>
>>> That doesn't help, the point of the overflow check is similar to
>>> overflow checks in kcalloc: to prevent the routine from allocating
>>> less memory than the caller might assume.
>>>
>>> For instance ipr_store_update_fw() uses request_firmware() (which is
>>> controlled by userspace) to drive the length argument to
>>> sgl_alloc_order(). If userpace gives too large a value this will
>>> corrupt kernel memory.
>>>
>>> So this math:
>>>
>>> nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
>>
>> But that check itself overflows if order is too large (e.g. 65).
>
> I don't reall care about order. It is always controlled by the kernel
> and it is fine to just require it be low enough to not
> overflow. length is the data under userspace control so math on it
> must be checked for overflow.
>
>> Also note there is another pre-condition statement in that function's
>> definition, namely that length cannot be 0.
>
> I don't see callers checking for that either, if it is true length 0
> can't be allowed it should be blocked in the function
>
> Jason
>

A already said, I also think there should be a check for length or
rather nent overflow.

I like the easy to understand check in your proposed code:

if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
return NULL;


But I don't understand, why you open-coded the nent calculation:

nent = length >> (PAGE_SHIFT + order);
if (length & ((1ULL << (PAGE_SHIFT + order)) - 1))
nent++;

Wouldn't it be better to keep the original line instead:

nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);

Or maybe even better:

nent = DIV_ROUND_UP(length, PAGE_SIZE << order);


I think, combining the above lines results in short and easily readable code:


u32 elem_len;

if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
return NULL;
nent = DIV_ROUND_UP(length, PAGE_SIZE << order);

if (chainable) {
if (check_add_overflow(nent, 1, &nalloc))
return NULL;
}
else
nalloc = nent;


Thank you,
Bodo



2021-01-19 05:34:32

by Jason Gunthorpe

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On Mon, Jan 18, 2021 at 10:22:56PM +0100, Bodo Stroesser wrote:
> On 18.01.21 21:24, Jason Gunthorpe wrote:
> > On Mon, Jan 18, 2021 at 03:08:51PM -0500, Douglas Gilbert wrote:
> >> On 2021-01-18 1:28 p.m., Jason Gunthorpe wrote:
> >>> On Mon, Jan 18, 2021 at 11:30:03AM -0500, Douglas Gilbert wrote:
> >>>
> >>>> After several flawed attempts to detect overflow, take the fastest
> >>>> route by stating as a pre-condition that the 'order' function argument
> >>>> cannot exceed 16 (2^16 * 4k = 256 MiB).
> >>>
> >>> That doesn't help, the point of the overflow check is similar to
> >>> overflow checks in kcalloc: to prevent the routine from allocating
> >>> less memory than the caller might assume.
> >>>
> >>> For instance ipr_store_update_fw() uses request_firmware() (which is
> >>> controlled by userspace) to drive the length argument to
> >>> sgl_alloc_order(). If userpace gives too large a value this will
> >>> corrupt kernel memory.
> >>>
> >>> So this math:
> >>>
> >>> nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
> >>
> >> But that check itself overflows if order is too large (e.g. 65).
> >
> > I don't reall care about order. It is always controlled by the kernel
> > and it is fine to just require it be low enough to not
> > overflow. length is the data under userspace control so math on it
> > must be checked for overflow.
> >
> >> Also note there is another pre-condition statement in that function's
> >> definition, namely that length cannot be 0.
> >
> > I don't see callers checking for that either, if it is true length 0
> > can't be allowed it should be blocked in the function
> >
> > Jason
> >
>
> A already said, I also think there should be a check for length or
> rather nent overflow.
>
> I like the easy to understand check in your proposed code:
>
> if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
> return NULL;
>
>
> But I don't understand, why you open-coded the nent calculation:
>
> nent = length >> (PAGE_SHIFT + order);
> if (length & ((1ULL << (PAGE_SHIFT + order)) - 1))
> nent++;

It is necessary to properly check for overflow, because the easy to
understand check doesn't prove that round_up will work, only that >>
results in something that fits in an int and that +1 won't overflow
the int.

> Wouldn't it be better to keep the original line instead:
>
> nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);

This can overflow inside the round_up

Jason

2021-01-19 05:39:40

by Douglas Gilbert

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On 2021-01-18 6:48 p.m., Jason Gunthorpe wrote:
> On Mon, Jan 18, 2021 at 10:22:56PM +0100, Bodo Stroesser wrote:
>> On 18.01.21 21:24, Jason Gunthorpe wrote:
>>> On Mon, Jan 18, 2021 at 03:08:51PM -0500, Douglas Gilbert wrote:
>>>> On 2021-01-18 1:28 p.m., Jason Gunthorpe wrote:
>>>>> On Mon, Jan 18, 2021 at 11:30:03AM -0500, Douglas Gilbert wrote:
>>>>>
>>>>>> After several flawed attempts to detect overflow, take the fastest
>>>>>> route by stating as a pre-condition that the 'order' function argument
>>>>>> cannot exceed 16 (2^16 * 4k = 256 MiB).
>>>>>
>>>>> That doesn't help, the point of the overflow check is similar to
>>>>> overflow checks in kcalloc: to prevent the routine from allocating
>>>>> less memory than the caller might assume.
>>>>>
>>>>> For instance ipr_store_update_fw() uses request_firmware() (which is
>>>>> controlled by userspace) to drive the length argument to
>>>>> sgl_alloc_order(). If userpace gives too large a value this will
>>>>> corrupt kernel memory.
>>>>>
>>>>> So this math:
>>>>>
>>>>> nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
>>>>
>>>> But that check itself overflows if order is too large (e.g. 65).
>>>
>>> I don't reall care about order. It is always controlled by the kernel
>>> and it is fine to just require it be low enough to not
>>> overflow. length is the data under userspace control so math on it
>>> must be checked for overflow.
>>>
>>>> Also note there is another pre-condition statement in that function's
>>>> definition, namely that length cannot be 0.
>>>
>>> I don't see callers checking for that either, if it is true length 0
>>> can't be allowed it should be blocked in the function
>>>
>>> Jason
>>>
>>
>> A already said, I also think there should be a check for length or
>> rather nent overflow.
>>
>> I like the easy to understand check in your proposed code:
>>
>> if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
>> return NULL;
>>
>>
>> But I don't understand, why you open-coded the nent calculation:
>>
>> nent = length >> (PAGE_SHIFT + order);
>> if (length & ((1ULL << (PAGE_SHIFT + order)) - 1))
>> nent++;
>
> It is necessary to properly check for overflow, because the easy to
> understand check doesn't prove that round_up will work, only that >>
> results in something that fits in an int and that +1 won't overflow
> the int.
>
>> Wouldn't it be better to keep the original line instead:
>>
>> nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
>
> This can overflow inside the round_up

To protect against the "unsigned long long" length being too big why
not pick a large power of two and if someone can justify a larger
value, they can send a patch.

if (length > 64ULL * 1024 * 1024 * 1024)
return NULL;

So 64 GiB or a similar calculation involving PAGE_SIZE. Compiler does
the multiplication and at run time there is only a 64 bit comparison.


I tested 6 one GiB ramdisks on an 8 GiB machine, worked fine until
firefox was started. Then came the OOM killer ...

Doug Gilbert

2021-01-19 13:16:51

by Jason Gunthorpe

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On Mon, Jan 18, 2021 at 08:27:09PM -0500, Douglas Gilbert wrote:

> To protect against the "unsigned long long" length being too big why
> not pick a large power of two and if someone can justify a larger
> value, they can send a patch.
>
> if (length > 64ULL * 1024 * 1024 * 1024)
> return NULL;

That is not how we protect against arithemetic overflows in the kernel

Jason

2021-01-19 17:27:43

by Bodo Stroesser

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On 19.01.21 00:48, Jason Gunthorpe wrote:
> On Mon, Jan 18, 2021 at 10:22:56PM +0100, Bodo Stroesser wrote:
>> On 18.01.21 21:24, Jason Gunthorpe wrote:
>>> On Mon, Jan 18, 2021 at 03:08:51PM -0500, Douglas Gilbert wrote:
>>>> On 2021-01-18 1:28 p.m., Jason Gunthorpe wrote:
>>>>> On Mon, Jan 18, 2021 at 11:30:03AM -0500, Douglas Gilbert wrote:
>>>>>
>>>>>> After several flawed attempts to detect overflow, take the fastest
>>>>>> route by stating as a pre-condition that the 'order' function argument
>>>>>> cannot exceed 16 (2^16 * 4k = 256 MiB).
>>>>>
>>>>> That doesn't help, the point of the overflow check is similar to
>>>>> overflow checks in kcalloc: to prevent the routine from allocating
>>>>> less memory than the caller might assume.
>>>>>
>>>>> For instance ipr_store_update_fw() uses request_firmware() (which is
>>>>> controlled by userspace) to drive the length argument to
>>>>> sgl_alloc_order(). If userpace gives too large a value this will
>>>>> corrupt kernel memory.
>>>>>
>>>>> So this math:
>>>>>
>>>>> nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
>>>>
>>>> But that check itself overflows if order is too large (e.g. 65).
>>>
>>> I don't reall care about order. It is always controlled by the kernel
>>> and it is fine to just require it be low enough to not
>>> overflow. length is the data under userspace control so math on it
>>> must be checked for overflow.
>>>
>>>> Also note there is another pre-condition statement in that function's
>>>> definition, namely that length cannot be 0.
>>>
>>> I don't see callers checking for that either, if it is true length 0
>>> can't be allowed it should be blocked in the function
>>>
>>> Jason
>>>
>>
>> A already said, I also think there should be a check for length or
>> rather nent overflow.
>>
>> I like the easy to understand check in your proposed code:
>>
>> if (length >> (PAGE_SHIFT + order) >= UINT_MAX)
>> return NULL;
>>
>>
>> But I don't understand, why you open-coded the nent calculation:
>>
>> nent = length >> (PAGE_SHIFT + order);
>> if (length & ((1ULL << (PAGE_SHIFT + order)) - 1))
>> nent++;
>
> It is necessary to properly check for overflow, because the easy to
> understand check doesn't prove that round_up will work, only that >>
> results in something that fits in an int and that +1 won't overflow
> the int.
>
>> Wouldn't it be better to keep the original line instead:
>>
>> nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
>
> This can overflow inside the round_up

I had a second look into math.h, but I don't find any reason why
round_up could overflow. Can you give a hint please?

Regarding the overflow checks: would it be a good idea to not check
length >> (PAGE_SHIFT + order) in the beginning, but check nalloc
immediately before the kmalloc_array() as the only overrun check:

if ((unsigned long long)nalloc << (PAGE_SHIFT + order) < length)
return NULL;

-Bodo

2021-01-19 18:13:40

by Jason Gunthorpe

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On Tue, Jan 19, 2021 at 06:24:49PM +0100, Bodo Stroesser wrote:
>
> I had a second look into math.h, but I don't find any reason why round_up
> could overflow. Can you give a hint please?

#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
^^^^^

That +1 can overflow

It looks like it would not be so bad to implement some
check_round_up_overflow() if people prefer

Jason

2021-01-19 18:59:17

by Bodo Stroesser

[permalink] [raw]
Subject: Re: [PATCH v6 1/4] sgl_alloc_order: remove 4 GiB limit, sgl_free() warning

On 19.01.21 19:03, Jason Gunthorpe wrote:
> On Tue, Jan 19, 2021 at 06:24:49PM +0100, Bodo Stroesser wrote:
>>
>> I had a second look into math.h, but I don't find any reason why round_up
>> could overflow. Can you give a hint please?
>
> #define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
> ^^^^^
>
> That +1 can overflow

But that would be a unsigned long long overflow. I considered this to
not be relevant.

>
> It looks like it would not be so bad to implement some
> check_round_up_overflow() if people prefer
>
> Jason
>