| Message ID | 20210118163006.61659-2-dgilbert@interlog.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | scatterlist: add new capabilities | expand |
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); Needs to be checked, add a precondition to order does not help. I already proposed a straightforward algorithm you can use. Jason
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). A pre-condition says that the caller must know or check a value is sane, and if the user space can have a hand in the value passed the caller _must_ check pre-conditions IMO. A pre-condition also implies that the function's implementation will not have code to check the pre-condition. My "log of both sides" proposal at least got around the overflowing left shift problem. And one reviewer, Bodo Stroesser, liked it. > Needs to be checked, add a precondition to order does not help. I > already proposed a straightforward algorithm you can use. It does help, it stops your proposed check from being flawed :-) Giving a false sense of security seems more dangerous than a pre-condition statement IMO. Bart's original overflow check (in the mainline) limits length to 4GB (due to wrapping inside a 32 bit unsigned). Also note there is another pre-condition statement in that function's definition, namely that length cannot be 0. So perhaps you, Bart Van Assche and Bodo Stroesser, should compare notes and come up with a solution that you are _all_ happy with. The pre-condition works for me and is the fastest. The 'length' argument might be large, say > 1 GB [I use 1 GB in testing but did try 4GB and found the bug I'm trying to fix] but having individual elements greater than say 32 MB each does not seem very practical (and fails on the systems that I test with). In my testing the largest element size is 4 MB. Doug Gilbert
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
On 18.01.21 21:08, 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). > A pre-condition says that the caller must know or check a value > is sane, and if the user space can have a hand in the value passed > the caller _must_ check pre-conditions IMO. A pre-condition also > implies that the function's implementation will not have code to > check the pre-condition. > > My "log of both sides" proposal at least got around the overflowing > left shift problem. And one reviewer, Bodo Stroesser, liked it. I added my Reviewed-by after you added a working check of nent overflow. I did not oppose to the usage of ilog() there. But now I think Jason is right that indeed ilog usage is a bit 'indirect'. Anyway I still think, there should be a check for nent overflow. > >> Needs to be checked, add a precondition to order does not help. I >> already proposed a straightforward algorithm you can use. > > It does help, it stops your proposed check from being flawed :-) > > Giving a false sense of security seems more dangerous than a > pre-condition statement IMO. Bart's original overflow check (in > the mainline) limits length to 4GB (due to wrapping inside a 32 > bit unsigned). > > Also note there is another pre-condition statement in that function's > definition, namely that length cannot be 0. > > So perhaps you, Bart Van Assche and Bodo Stroesser, should compare > notes and come up with a solution that you are _all_ happy with. > The pre-condition works for me and is the fastest. The 'length' > argument might be large, say > 1 GB [I use 1 GB in testing but > did try 4GB and found the bug I'm trying to fix] but having > individual elements greater than say 32 MB each does not > seem very practical (and fails on the systems that I test with). > In my testing the largest element size is 4 MB. > > > Doug Gilbert >
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
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
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
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
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
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
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 >
On Tue, Jan 19, 2021 at 07:08:32PM +0100, Bodo Stroesser wrote: > 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. Why not? It still makes nents 0 and still causes a bad bug Jason
On 19.01.21 19:17, Jason Gunthorpe wrote: > On Tue, Jan 19, 2021 at 07:08:32PM +0100, Bodo Stroesser wrote: >> 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. > > Why not? It still makes nents 0 and still causes a bad bug > Generally spoken, you of course are right. OTOH, if someone tries to allocate such big sgls, then we will run into trouble during memory allocation even without overrun. Anyway, if we first calculate nent and nalloc and then check with if ((unsigned long long)nalloc << (PAGE_SHIFT + order) < length) return NULL; I think we would have checked against all kind of overrun in a single step. Or am I missing something? Bodo
diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h index 6f70572b2938..8adff41f7cfa 100644 --- a/include/linux/scatterlist.h +++ b/include/linux/scatterlist.h @@ -302,6 +302,7 @@ struct scatterlist *sgl_alloc(unsigned long long length, gfp_t gfp, unsigned int *nent_p); void sgl_free_n_order(struct scatterlist *sgl, int nents, int order); void sgl_free_order(struct scatterlist *sgl, int order); +/* Only use sgl_free() when order is 0 */ void sgl_free(struct scatterlist *sgl); #endif /* CONFIG_SGL_ALLOC */ diff --git a/lib/scatterlist.c b/lib/scatterlist.c index a59778946404..24ea2d31a405 100644 --- a/lib/scatterlist.c +++ b/lib/scatterlist.c @@ -554,13 +554,16 @@ EXPORT_SYMBOL(sg_alloc_table_from_pages); #ifdef CONFIG_SGL_ALLOC /** - * sgl_alloc_order - allocate a scatterlist and its pages + * sgl_alloc_order - allocate a scatterlist with equally sized elements each + * of which has 2^@order continuous pages * @length: Length in bytes of the scatterlist. Must be at least one - * @order: Second argument for alloc_pages() + * @order: Second argument for alloc_pages(). Each sgl element size will + * be (PAGE_SIZE*2^@order) bytes. @order must not exceed 16. * @chainable: Whether or not to allocate an extra element in the scatterlist - * for scatterlist chaining purposes + * for scatterlist chaining purposes * @gfp: Memory allocation flags - * @nent_p: [out] Number of entries in the scatterlist that have pages + * @nent_p: [out] Number of entries in the scatterlist that have pages. + * Ignored if NULL is given. * * Returns: A pointer to an initialized scatterlist or %NULL upon failure. */ @@ -574,15 +577,11 @@ struct scatterlist *sgl_alloc_order(unsigned long long length, u32 elem_len; nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order); - /* Check for integer overflow */ - if (length > (nent << (PAGE_SHIFT + order))) - return NULL; - nalloc = nent; if (chainable) { - /* Check for integer overflow */ - if (nalloc + 1 < nalloc) + if (check_add_overflow(nent, 1U, &nalloc)) return NULL; - nalloc++; + } else { + nalloc = nent; } sgl = kmalloc_array(nalloc, sizeof(struct scatterlist), gfp & ~GFP_DMA);
This patch fixes a check done by sgl_alloc_order() before it starts any allocations. The comment in the original said: "Check for integer overflow" but the check itself contained an integer overflow! The right hand side (rhs) of the expression in the condition is resolved as u32 so it could not exceed UINT32_MAX (4 GiB) which means 'length' could not exceed that value. If that was the intention then the comment above it could be dropped and the condition rewritten more clearly as: if (length > UINT32_MAX) <<failure path >>; 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). This function may be used to replace vmalloc(unsigned long) for a large allocation (e.g. a ramdisk). vmalloc has no limit at 4 GiB so it seems unreasonable that: sgl_alloc_order(unsigned long long length, ....) does. sgl_s made with sgl_alloc_order() have equally sized segments placed in a scatter gather array. That allows O(1) navigation around a big sgl using some simple integer arithmetic. Revise some of this function's description to more accurately reflect what this function is doing. An earlier patch fixed a memory leak in sg_alloc_order() due to the misuse of sgl_free(). Take the opportunity to put a one line comment above sgl_free()'s declaration warning that it is not suitable when order > 0 . Reviewed-by: Bodo Stroesser <bostroesser@gmail.com> Signed-off-by: Douglas Gilbert <dgilbert@interlog.com> --- include/linux/scatterlist.h | 1 + lib/scatterlist.c | 21 ++++++++++----------- 2 files changed, 11 insertions(+), 11 deletions(-)