My static checker is warning about integer overflows in kernel/relay.c
relay_create_buf()
170
171 buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This can only overflow on 32bit systems.
172 if (!buf->padding)
173 goto free_buf;
174
relay_open()
582 chan->version = RELAYFS_CHANNEL_VERSION;
583 chan->n_subbufs = n_subbufs;
584 chan->subbuf_size = subbuf_size;
585 chan->alloc_size = FIX_SIZE(subbuf_size * n_subbufs);
^^^^^^^^^^^^^^^^^^^^^^^
586 chan->parent = parent;
These come from the user in blk_trace_setup() and they aren't capped.
I'm not sure what the maximum size to use is.
regards,
dan carpenter
On 02/07/2012 03:11 PM, Dan Carpenter wrote:
> My static checker is warning about integer overflows in kernel/relay.c
>
> relay_create_buf()
> 170
> 171 buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> This can only overflow on 32bit systems.
Correct
> 172 if (!buf->padding)
> 173 goto free_buf;
> 174
>
> relay_open()
> 582 chan->version = RELAYFS_CHANNEL_VERSION;
> 583 chan->n_subbufs = n_subbufs;
> 584 chan->subbuf_size = subbuf_size;
> 585 chan->alloc_size = FIX_SIZE(subbuf_size * n_subbufs);
> ^^^^^^^^^^^^^^^^^^^^^^^
> 586 chan->parent = parent;
>
> These come from the user in blk_trace_setup() and they aren't capped.
> I'm not sure what the maximum size to use is.
They are both u32 types, so can overflow on 32-bit as well. By default,
blktrace is using 4 for n_subbufs and 512k for subbuf_size, but they are
configurable. As a fix, I would suggest just checking if the products
overflow, and if they do, return an error. That's better than imposing
some hard limits. In reality, only a malicious users would trigger
these.
--
Jens Axboe
On Wed, 08 Feb 2012 09:34:16 +0100
Jens Axboe <[email protected]> wrote:
> On 02/07/2012 03:11 PM, Dan Carpenter wrote:
> > My static checker is warning about integer overflows in kernel/relay.c
> >
> > relay_create_buf()
> > 170
> > 171 buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
> > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > This can only overflow on 32bit systems.
>
> Correct
This is a relatively common problem. Converting a kzalloc() call to
kcalloc() fixes it. But we do not have a non-zeroing version of
kcalloc().
Please, someone complete this patch and send it to me!
--- a/include/linux/slab.h~a
+++ a/include/linux/slab.h
@@ -240,11 +240,16 @@ size_t ksize(const void *);
* for general use, and so are not documented here. For a full list of
* potential flags, always refer to linux/gfp.h.
*/
-static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+static inline void *wtf_do_i_call_this(size_t n, size_t size, gfp_t flags)
{
if (size != 0 && n > ULONG_MAX / size)
return NULL;
- return __kmalloc(n * size, flags | __GFP_ZERO);
+ return __kmalloc(n * size, flags);
+}
+
+static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+{
+ return wtf_do_i_call_this(n, size, flags | __GFP_ZERO);
}
#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
_
"subbuf_size" and "n_subbufs" come from the user and they need to be
capped to prevent an integer overflow.
Signed-off-by: Dan Carpenter <[email protected]>
diff --git a/kernel/relay.c b/kernel/relay.c
index 4335e1d..ab56a17 100644
--- a/kernel/relay.c
+++ b/kernel/relay.c
@@ -164,10 +164,14 @@ depopulate:
*/
static struct rchan_buf *relay_create_buf(struct rchan *chan)
{
- struct rchan_buf *buf = kzalloc(sizeof(struct rchan_buf), GFP_KERNEL);
- if (!buf)
+ struct rchan_buf *buf;
+
+ if (chan->n_subbufs > UINT_MAX / sizeof(size_t *))
return NULL;
+ buf = kzalloc(sizeof(struct rchan_buf), GFP_KERNEL);
+ if (!buf)
+ return NULL;
buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
if (!buf->padding)
goto free_buf;
@@ -574,6 +578,8 @@ struct rchan *relay_open(const char *base_filename,
if (!(subbuf_size && n_subbufs))
return NULL;
+ if (subbuf_size > UINT_MAX / n_subbufs)
+ return NULL;
chan = kzalloc(sizeof(struct rchan), GFP_KERNEL);
if (!chan)
Am 09.02.2012 11:44, schrieb Dan Carpenter:
> "subbuf_size" and "n_subbufs" come from the user and they need to be
> capped to prevent an integer overflow.
>
> Signed-off-by: Dan Carpenter <[email protected]>
>
> diff --git a/kernel/relay.c b/kernel/relay.c
> index 4335e1d..ab56a17 100644
> --- a/kernel/relay.c
> +++ b/kernel/relay.c
> @@ -164,10 +164,14 @@ depopulate:
> */
> static struct rchan_buf *relay_create_buf(struct rchan *chan)
> {
> - struct rchan_buf *buf = kzalloc(sizeof(struct rchan_buf), GFP_KERNEL);
> - if (!buf)
> + struct rchan_buf *buf;
> +
> + if (chan->n_subbufs > UINT_MAX / sizeof(size_t *))
> return NULL;
>
> + buf = kzalloc(sizeof(struct rchan_buf), GFP_KERNEL);
> + if (!buf)
> + return NULL;
> buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
> if (!buf->padding)
> goto free_buf;
> @@ -574,6 +578,8 @@ struct rchan *relay_open(const char *base_filename,
>
> if (!(subbuf_size && n_subbufs))
> return NULL;
> + if (subbuf_size > UINT_MAX / n_subbufs)
> + return NULL;
>
> chan = kzalloc(sizeof(struct rchan), GFP_KERNEL);
> if (!chan)
> --
numerical this is ok, but ...
maybe it is better to cap the chan->n_subbufs at a useful number ?
The user can still allocate an insane number of bytes.
Restricting subbuf_size*n_subbufs seems more logical (otherwise is this a real problem ?)
re,
wh
On Thu, Feb 09, 2012 at 12:55:52PM +0100, walter harms wrote:
> numerical this is ok, but ...
> maybe it is better to cap the chan->n_subbufs at a useful number ?
We considered this question already earlier in the thread.
> The user can still allocate an insane number of bytes.
> Restricting subbuf_size*n_subbufs seems more logical (otherwise is this a real problem ?)
>
Yes. It is a real problem.
regards,
dan carpenter
This patch introduces knalloc/kxnalloc wrappers that perform integer
overflow checks without zeroing the memory.
knalloc(n, size, flags) is the non-zeroing version of kcalloc(),
which allocates n * size bytes.
kxnalloc(xsize, n, size, flags) allocates xsize + n * size bytes.
It is useful to allocate a structure ending with a zero-length array,
which is a commonly used pattern. For example, in posix_acl_alloc()
to allocate a posix_acl object one could call
kxnalloc(sizeof(struct posix_acl),
count, sizeof(struct posix_acl_entry), flags);
to avoid overflowing the allocation size.
Suggested-by: Andrew Morton <[email protected]>
Signed-off-by: Xi Wang <[email protected]>
---
I coined the name knalloc() for Andrew's wtf_do_i_call_this() in the
previous email. A better name is welcome.
I additionally added kxnalloc() since it's a common idiom.
---
include/linux/slab.h | 31 +++++++++++++++++++++++++++----
1 files changed, 27 insertions(+), 4 deletions(-)
diff --git a/include/linux/slab.h b/include/linux/slab.h
index 573c809..e3a1e81 100644
--- a/include/linux/slab.h
+++ b/include/linux/slab.h
@@ -190,7 +190,8 @@ size_t ksize(const void *);
#endif
/**
- * kcalloc - allocate memory for an array. The memory is set to zero.
+ * kxnalloc - allocate memory for an array with an extra header.
+ * @xsize: extra header size.
* @n: number of elements.
* @size: element size.
* @flags: the type of memory to allocate.
@@ -240,11 +241,33 @@ size_t ksize(const void *);
* for general use, and so are not documented here. For a full list of
* potential flags, always refer to linux/gfp.h.
*/
-static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+static inline void *kxnalloc(size_t xsize, size_t n, size_t size, gfp_t flags)
{
- if (size != 0 && n > ULONG_MAX / size)
+ if (size != 0 && n > (ULONG_MAX - xsize) / size)
return NULL;
- return __kmalloc(n * size, flags | __GFP_ZERO);
+ return __kmalloc(xsize + n * size, flags);
+}
+
+/**
+ * knalloc - allocate memory for an array.
+ * @n: number of elements.
+ * @size: element size.
+ * @flags: the type of memory to allocate (see kmalloc).
+ */
+static inline void *knalloc(size_t n, size_t size, gfp_t flags)
+{
+ return kxnalloc(0, n, size, flags);
+}
+
+/**
+ * kcalloc - allocate memory for an array. The memory is set to zero.
+ * @n: number of elements.
+ * @size: element size.
+ * @flags: the type of memory to allocate (see kmalloc).
+ */
+static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+{
+ return knalloc(n, size, flags | __GFP_ZERO);
}
#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
--
1.7.5.4
On 02/08/2012 11:25 PM, Andrew Morton wrote:
> On Wed, 08 Feb 2012 09:34:16 +0100
> Jens Axboe <[email protected]> wrote:
>
>> On 02/07/2012 03:11 PM, Dan Carpenter wrote:
>>> My static checker is warning about integer overflows in kernel/relay.c
>>>
>>> relay_create_buf()
>>> 170
>>> 171 buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
>>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>> This can only overflow on 32bit systems.
>>
>> Correct
>
> This is a relatively common problem. Converting a kzalloc() call to
> kcalloc() fixes it. But we do not have a non-zeroing version of
> kcalloc().
>
> Please, someone complete this patch and send it to me!
>
>
> --- a/include/linux/slab.h~a
> +++ a/include/linux/slab.h
> @@ -240,11 +240,16 @@ size_t ksize(const void *);
> * for general use, and so are not documented here. For a full list of
> * potential flags, always refer to linux/gfp.h.
> */
> -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> +static inline void *wtf_do_i_call_this(size_t n, size_t size, gfp_t flags)
kzcalloc()? Either that, or long_and_verbose().
--
Jens Axboe
On Thu, Feb 9, 2012 at 12:25 AM, Andrew Morton
<[email protected]> wrote:
> On Wed, 08 Feb 2012 09:34:16 +0100
> Jens Axboe <[email protected]> wrote:
>
>> On 02/07/2012 03:11 PM, Dan Carpenter wrote:
>> > My static checker is warning about integer overflows in kernel/relay.c
>> >
>> > relay_create_buf()
>> > ? ?170
>> > ? ?171 ? ? ? ? ?buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
>> > ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>> > This can only overflow on 32bit systems.
>>
>> Correct
>
> This is a relatively common problem. ?Converting a kzalloc() call to
> kcalloc() fixes it. ?But we do not have a non-zeroing version of
> kcalloc().
>
> Please, someone complete this patch and send it to me!
>
>
> --- a/include/linux/slab.h~a
> +++ a/include/linux/slab.h
> @@ -240,11 +240,16 @@ size_t ksize(const void *);
> ?* for general use, and so are not documented here. For a full list of
> ?* potential flags, always refer to linux/gfp.h.
> ?*/
> -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> +static inline void *wtf_do_i_call_this(size_t n, size_t size, gfp_t flags)
I'd call it kmalloc_array().
> ?{
> ? ? ? ?if (size != 0 && n > ULONG_MAX / size)
> ? ? ? ? ? ? ? ?return NULL;
> - ? ? ? return __kmalloc(n * size, flags | __GFP_ZERO);
> + ? ? ? return __kmalloc(n * size, flags);
> +}
On Thu, Feb 9, 2012 at 2:41 PM, Xi Wang <[email protected]> wrote:
> This patch introduces knalloc/kxnalloc wrappers that perform integer
> overflow checks without zeroing the memory.
>
> knalloc(n, size, flags) is the non-zeroing version of kcalloc(),
> which allocates n * size bytes.
>
> kxnalloc(xsize, n, size, flags) allocates xsize + n * size bytes.
> It is useful to allocate a structure ending with a zero-length array,
> which is a commonly used pattern. ?For example, in posix_acl_alloc()
> to allocate a posix_acl object one could call
>
> ? ?kxnalloc(sizeof(struct posix_acl),
> ? ? ? ? ? ? count, sizeof(struct posix_acl_entry), flags);
>
> to avoid overflowing the allocation size.
>
> Suggested-by: Andrew Morton <[email protected]>
> Signed-off-by: Xi Wang <[email protected]>
Are there really enough potential users to justify adding both?
> ---
> I coined the name knalloc() for Andrew's wtf_do_i_call_this() in the
> previous email. ?A better name is welcome.
>
> I additionally added kxnalloc() since it's a common idiom.
> ---
> ?include/linux/slab.h | ? 31 +++++++++++++++++++++++++++----
> ?1 files changed, 27 insertions(+), 4 deletions(-)
>
> diff --git a/include/linux/slab.h b/include/linux/slab.h
> index 573c809..e3a1e81 100644
> --- a/include/linux/slab.h
> +++ b/include/linux/slab.h
> @@ -190,7 +190,8 @@ size_t ksize(const void *);
> ?#endif
>
> ?/**
> - * kcalloc - allocate memory for an array. The memory is set to zero.
> + * kxnalloc - allocate memory for an array with an extra header.
> + * @xsize: extra header size.
> ?* @n: number of elements.
> ?* @size: element size.
> ?* @flags: the type of memory to allocate.
> @@ -240,11 +241,33 @@ size_t ksize(const void *);
> ?* for general use, and so are not documented here. For a full list of
> ?* potential flags, always refer to linux/gfp.h.
> ?*/
> -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> +static inline void *kxnalloc(size_t xsize, size_t n, size_t size, gfp_t flags)
> ?{
> - ? ? ? if (size != 0 && n > ULONG_MAX / size)
> + ? ? ? if (size != 0 && n > (ULONG_MAX - xsize) / size)
> ? ? ? ? ? ? ? ?return NULL;
> - ? ? ? return __kmalloc(n * size, flags | __GFP_ZERO);
> + ? ? ? return __kmalloc(xsize + n * size, flags);
> +}
> +
> +/**
> + * knalloc - allocate memory for an array.
> + * @n: number of elements.
> + * @size: element size.
> + * @flags: the type of memory to allocate (see kmalloc).
> + */
> +static inline void *knalloc(size_t n, size_t size, gfp_t flags)
> +{
> + ? ? ? return kxnalloc(0, n, size, flags);
> +}
> +/**
> + * kcalloc - allocate memory for an array. The memory is set to zero.
> + * @n: number of elements.
> + * @size: element size.
> + * @flags: the type of memory to allocate (see kmalloc).
> + */
> +static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> +{
> + ? ? ? return knalloc(n, size, flags | __GFP_ZERO);
> ?}
>
> ?#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
On 02/09/2012 02:05 PM, Pekka Enberg wrote:
> On Thu, Feb 9, 2012 at 2:41 PM, Xi Wang <[email protected]> wrote:
>> This patch introduces knalloc/kxnalloc wrappers that perform integer
>> overflow checks without zeroing the memory.
>>
>> knalloc(n, size, flags) is the non-zeroing version of kcalloc(),
>> which allocates n * size bytes.
>>
>> kxnalloc(xsize, n, size, flags) allocates xsize + n * size bytes.
>> It is useful to allocate a structure ending with a zero-length array,
>> which is a commonly used pattern. For example, in posix_acl_alloc()
>> to allocate a posix_acl object one could call
>>
>> kxnalloc(sizeof(struct posix_acl),
>> count, sizeof(struct posix_acl_entry), flags);
>>
>> to avoid overflowing the allocation size.
>>
>> Suggested-by: Andrew Morton <[email protected]>
>> Signed-off-by: Xi Wang <[email protected]>
>
> Are there really enough potential users to justify adding both?
Agree, lets not overdesign. kmalloc_array() sounds good to me, fwiw.
--
Jens Axboe
On Feb 9, 2012, at 8:19 AM, Jens Axboe wrote:
> Agree, lets not overdesign. kmalloc_array() sounds good to me, fwiw.
I like kmalloc_array. "knalloc" can be easily confused with kmalloc.
- xi
This patch introduces a kmalloc_array() wrapper that performs integer
overflow checking without zeroing the memory.
Suggested-by: Andrew Morton <[email protected]>
Suggested-by: Jens Axboe <[email protected]>
Signed-off-by: Xi Wang <[email protected]>
---
Let's take "kxnalloc" off for now and keep the patch simple.
---
include/linux/slab.h | 17 ++++++++++++++---
1 files changed, 14 insertions(+), 3 deletions(-)
diff --git a/include/linux/slab.h b/include/linux/slab.h
index 573c809..a595dce 100644
--- a/include/linux/slab.h
+++ b/include/linux/slab.h
@@ -190,7 +190,7 @@ size_t ksize(const void *);
#endif
/**
- * kcalloc - allocate memory for an array. The memory is set to zero.
+ * kmalloc_array - allocate memory for an array.
* @n: number of elements.
* @size: element size.
* @flags: the type of memory to allocate.
@@ -240,11 +240,22 @@ size_t ksize(const void *);
* for general use, and so are not documented here. For a full list of
* potential flags, always refer to linux/gfp.h.
*/
-static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
{
if (size != 0 && n > ULONG_MAX / size)
return NULL;
- return __kmalloc(n * size, flags | __GFP_ZERO);
+ return __kmalloc(n * size, flags);
+}
+
+/**
+ * kcalloc - allocate memory for an array. The memory is set to zero.
+ * @n: number of elements.
+ * @size: element size.
+ * @flags: the type of memory to allocate (see kmalloc).
+ */
+static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+{
+ return kmalloc_array(n, size, flags | __GFP_ZERO);
}
#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
--
1.7.5.4
On Thu, 09 Feb 2012 13:41:38 +0100 Jens Axboe <[email protected]> wrote:
> On 02/08/2012 11:25 PM, Andrew Morton wrote:
> > On Wed, 08 Feb 2012 09:34:16 +0100
> > Jens Axboe <[email protected]> wrote:
> >
> >> On 02/07/2012 03:11 PM, Dan Carpenter wrote:
> >>> My static checker is warning about integer overflows in kernel/relay.c
> >>>
> >>> relay_create_buf()
> >>> 170
> >>> 171 buf->padding = kmalloc(chan->n_subbufs * sizeof(size_t *), GFP_KERNEL);
> >>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> >>> This can only overflow on 32bit systems.
> >>
> >> Correct
> >
> > This is a relatively common problem. Converting a kzalloc() call to
> > kcalloc() fixes it. But we do not have a non-zeroing version of
> > kcalloc().
> >
> > Please, someone complete this patch and send it to me!
> >
> >
> > --- a/include/linux/slab.h~a
> > +++ a/include/linux/slab.h
> > @@ -240,11 +240,16 @@ size_t ksize(const void *);
> > * for general use, and so are not documented here. For a full list of
> > * potential flags, always refer to linux/gfp.h.
> > */
> > -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> > +static inline void *wtf_do_i_call_this(size_t n, size_t size, gfp_t flags)
>
> kzcalloc()? Either that, or long_and_verbose().
I would need to be k_not_z_calloc() because it's the non-zeroing version.
kcallocn()? knalloc()? kncalloc()?
On Thu, 9 Feb 2012, Xi Wang wrote:
> This patch introduces a kmalloc_array() wrapper that performs integer
> overflow checking without zeroing the memory.
>
> Suggested-by: Andrew Morton <[email protected]>
> Suggested-by: Jens Axboe <[email protected]>
> Signed-off-by: Xi Wang <[email protected]>
Acked-by: David Rientjes <[email protected]>
assuming there's at least one new user or one existing user that can be
modified to use the new interface and this won't just sit around not being
used.
On Thu, 9 Feb 2012, Xi Wang wrote:
> This patch introduces a kmalloc_array() wrapper that performs integer
> overflow checking without zeroing the memory.
>
> Suggested-by: Andrew Morton <[email protected]>
> Suggested-by: Jens Axboe <[email protected]>
> Signed-off-by: Xi Wang <[email protected]>
> ---
> Let's take "kxnalloc" off for now and keep the patch simple.
> ---
> include/linux/slab.h | 17 ++++++++++++++---
> 1 files changed, 14 insertions(+), 3 deletions(-)
>
> diff --git a/include/linux/slab.h b/include/linux/slab.h
> index 573c809..a595dce 100644
> --- a/include/linux/slab.h
> +++ b/include/linux/slab.h
> @@ -190,7 +190,7 @@ size_t ksize(const void *);
> #endif
>
> /**
> - * kcalloc - allocate memory for an array. The memory is set to zero.
> + * kmalloc_array - allocate memory for an array.
> * @n: number of elements.
> * @size: element size.
> * @flags: the type of memory to allocate.
> @@ -240,11 +240,22 @@ size_t ksize(const void *);
> * for general use, and so are not documented here. For a full list of
> * potential flags, always refer to linux/gfp.h.
> */
> -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> +static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
> {
> if (size != 0 && n > ULONG_MAX / size)
> return NULL;
> - return __kmalloc(n * size, flags | __GFP_ZERO);
> + return __kmalloc(n * size, flags);
> +}
> +
> +/**
> + * kcalloc - allocate memory for an array. The memory is set to zero.
> + * @n: number of elements.
> + * @size: element size.
> + * @flags: the type of memory to allocate (see kmalloc).
> + */
> +static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> +{
> + return kmalloc_array(n, size, flags | __GFP_ZERO);
> }
>
> #if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
>
Does this want adding to Documentation/CodingStyle "Chapter 14: Allocating
memory" ?
--
Jesper Juhl <[email protected]> http://www.chaosbits.net/
Don't top-post http://www.catb.org/jargon/html/T/top-post.html
Plain text mails only, please.
On Thu, 9 Feb 2012 23:47:42 +0100 (CET)
Jesper Juhl <[email protected]> wrote:
> > -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> > +static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
> > {
> > if (size != 0 && n > ULONG_MAX / size)
> > return NULL;
> > - return __kmalloc(n * size, flags | __GFP_ZERO);
> > + return __kmalloc(n * size, flags);
> > +}
> > +
> > +/**
> > + * kcalloc - allocate memory for an array. The memory is set to zero.
> > + * @n: number of elements.
> > + * @size: element size.
> > + * @flags: the type of memory to allocate (see kmalloc).
> > + */
> > +static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> > +{
> > + return kmalloc_array(n, size, flags | __GFP_ZERO);
> > }
> >
> > #if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
> >
>
> Does this want adding to Documentation/CodingStyle "Chapter 14: Allocating
> memory" ?
Spose so. We could possibly cook up a checkpatch rule too ;)
<gad, CodingStyle has 18 chapters and an appendix??>
On Thu, 9 Feb 2012 14:42:49 -0800 (PST)
David Rientjes <[email protected]> wrote:
> On Thu, 9 Feb 2012, Xi Wang wrote:
>
> > This patch introduces a kmalloc_array() wrapper that performs integer
> > overflow checking without zeroing the memory.
> >
> > Suggested-by: Andrew Morton <[email protected]>
> > Suggested-by: Jens Axboe <[email protected]>
> > Signed-off-by: Xi Wang <[email protected]>
>
> Acked-by: David Rientjes <[email protected]>
>
> assuming there's at least one new user or one existing user that can be
> modified to use the new interface and this won't just sit around not being
> used.
The need is there - I've whined about the absence of kmalloc_array()
maybe 3 times in the past year.
Often kcalloc() is suitable - quite a lot of arrays which are sized
based on a userspace-provided dimension are also zeroed out. For some
reason.
On Thu, 2012-02-09 at 15:06 -0800, Andrew Morton wrote:
> On Thu, 9 Feb 2012 23:47:42 +0100 (CET)
> Jesper Juhl <[email protected]> wrote:
> > > -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> > > +static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
> []
> > Does this want adding to Documentation/CodingStyle "Chapter 14: Allocating
> > memory" ?
>
> Spose so. We could possibly cook up a checkpatch rule too ;)
> <gad, CodingStyle has 18 chapters and an appendix??>
Symmetry please.
[kv]malloc_array
[kv]malloc_node_array
On Thu, Feb 9, 2012 at 4:48 PM, Xi Wang <[email protected]> wrote:
> -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
> +static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
> Â {
> Â Â Â Â if (size != 0 && n > ULONG_MAX / size)
> Â Â Â Â Â Â Â Â return NULL;
> - Â Â Â return __kmalloc(n * size, flags | __GFP_ZERO);
> + Â Â Â return __kmalloc(n * size, flags);
> +}
It should be named kaalloc(), I think.
Why it is ULONG_MAX, when size_t is used?
On Fri, Feb 10, 2012 at 4:09 PM, Alexey Dobriyan <[email protected]> wrote:
> On Thu, Feb 9, 2012 at 4:48 PM, Xi Wang <[email protected]> wrote:
>> -static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
>> +static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
>> Â {
>> Â Â Â Â if (size != 0 && n > ULONG_MAX / size)
>> Â Â Â Â Â Â Â Â return NULL;
>> - Â Â Â return __kmalloc(n * size, flags | __GFP_ZERO);
>> + Â Â Â return __kmalloc(n * size, flags);
>> +}
>
> It should be named kaalloc(), I think.
> Why it is ULONG_MAX, when size_t is used?
Also, it could be written more "robust" against people who will make
sizeof() the first argument with __builtin_constant_p().
On Feb 10, 2012, at 8:11 AM, Alexey Dobriyan wrote:
>> It should be named kaalloc(), I think.
I like this shorter name. Let's see what others think. ;-)
>> Why it is ULONG_MAX, when size_t is used?
Is there a SIZE_MAX or something similar?
> Also, it could be written more "robust" against people who will make
> sizeof() the first argument with __builtin_constant_p().
Do you mean something like this?
BUILD_BUG_ON(__builtin_constant_p(n));
or
BUILD_BUG_ON(__builtin_constant_p(n) && !__builtin_constant_p(size));
- xi
On Fri, Feb 10, 2012 at 4:55 PM, Xi Wang <[email protected]> wrote:
> On Feb 10, 2012, at 8:11 AM, Alexey Dobriyan wrote:
>> Also, it could be written more "robust" against people who will make
>> sizeof() the first argument with __builtin_constant_p().
No,
If one dimension is constant, limit should be divided by it, so
compiler would have less chance
to screw up compile time evaluation.
Also, gfp_t mask could be made first argument if we ever want to
expand it to >2 dimensional arrays
without adding kaalloc3().
> Do you mean something like this?
>
> Â BUILD_BUG_ON(__builtin_constant_p(n));
>
> or
>
> Â BUILD_BUG_ON(__builtin_constant_p(n) && !__builtin_constant_p(size));
>
> - xi
On Feb 10, 2012, at 8:58 AM, Alexey Dobriyan wrote:
> No,
>
> If one dimension is constant, limit should be divided by it, so
> compiler would have less chance
> to screw up compile time evaluation.
I think the BUILD_BUG_ON macro can prevent that misuse.
- xi
On Fri, Feb 10, 2012 at 09:09:09AM -0500, Xi Wang wrote:
> On Feb 10, 2012, at 8:58 AM, Alexey Dobriyan wrote:
> > No,
> >
> > If one dimension is constant, limit should be divided by it, so
> > compiler would have less chance
> > to screw up compile time evaluation.
>
> I think the BUILD_BUG_ON macro can prevent that misuse.
But there is no misuse.
Both kaalloc(non-const, const) and kaalloc(const, non-const) are OK.
It's just first case happens more often.
On Feb 11, 2012, at 7:19 AM, Alexey Dobriyan wrote:
> But there is no misuse.
>
> Both kaalloc(non-const, const) and kaalloc(const, non-const) are OK.
> It's just first case happens more often.
Any k*alloc(const, non-const) example? I feel like in most cases
it is the caller code that should get fixed, such as:
https://lkml.org/lkml/2012/2/10/135
- xi
Here goes a quick summary.
Proposed names
==============
kaalloc (Alexey Dobriyan)
kcallocn (Andrew Morton)
kmalloc_array (Pekka Enberg)
knalloc (Andrew Morton, Xi Wang)
kncalloc (Andrew Morton)
Other changes
=============
Documentation/CodingStyle "Chapter 14: Allocating memory"
* Mention the new array allocator whatever-it-is-called.
* Add some description:
"The preferred form for allocating an array is the following:
p = whatever-it-is-called(n, sizeof(...), ...);
To return zeroed items, the preferred form is the following:
p = kcalloc(n, sizeof(...), ...);
Both forms avoid overflowing the allocation size n * sizeof(...)."
* Add some checkpatch rule?
- xi
Well I think the best is just not do any of this. One can already do
k[zm]alloc(x * sizeof(struct whatever)). Do x*x for 2 dimensions etc etc.
No need to change the API.
If you add these variants then please think
about the necessity to add other variants (like the kmalloc_node() NUMA
call) etc in the future.
On Mon, Feb 13, 2012 at 10:01:42AM -0600, Christoph Lameter wrote:
> Well I think the best is just not do any of this. One can already do
> k[zm]alloc(x * sizeof(struct whatever)). Do x*x for 2 dimensions etc etc.
> No need to change the API.
>
The point was that there are a bunch of places where we have had
integer overflows caused by doing kmalloc(x * sizeof(struct whatever)).
For kzalloc(x * sizeof(struct whatever)), you just write it like
kcalloc(x, sizeof(struct whatever)) and avoid the overflow, but we
don't have a non-zeroing version of kcalloc() to do that.
Probably once we have the kmalloc_array() and people start using it,
we get a bunch of overflow checking automatically and it's a kernel
hardenning thing. As well we could remove the duplicative checking
so it's a cleanup.
> If you add these variants then please think
> about the necessity to add other variants (like the kmalloc_node() NUMA
> call) etc in the future.
>
We don't have a kcalloc_node(), so I don't think this is likely to
be a big issue.
regards,
dan carpenter
On Mon, 13 Feb 2012, Dan Carpenter wrote:
>
> The point was that there are a bunch of places where we have had
> integer overflows caused by doing kmalloc(x * sizeof(struct whatever)).
> For kzalloc(x * sizeof(struct whatever)), you just write it like
> kcalloc(x, sizeof(struct whatever)) and avoid the overflow, but we
> don't have a non-zeroing version of kcalloc() to do that.
>
> Probably once we have the kmalloc_array() and people start using it,
> we get a bunch of overflow checking automatically and it's a kernel
> hardenning thing. As well we could remove the duplicative checking
> so it's a cleanup.
Could you just do a macro that can be used in any location where the
size of an array needs to be calculation. For example:
SAFE_ARRAY_SIZE(<nr>,<struct>)
So you'd do
kmalloc_node(SAFE_ARRAY_SIZE(10, struct page), 2, GFP_KERNEL)
or if you want multiple dimensions
SAFE_ARRAY_SIZE_2(<nr1>,<nr2>,<struct>)
?
> > If you add these variants then please think
> > about the necessity to add other variants (like the kmalloc_node() NUMA
> > call) etc in the future.
> >
>
> We don't have a kcalloc_node(), so I don't think this is likely to
> be a big issue.
Yes and so if you need to allocate on a particular node then you need to
do the calculation manually and therefore may not check for overflows.
Get rid of kcalloc and replace it with
kzalloc(SAFE_ARRAY_SIZE(x, y), ....)
?
SAFE_ARRAY_SIZE() would return the size if there were no overflow
and -1 on errors? We can't return zero on errors because there are
a lot of places which do zero size allocations and it's valid. It
seems ugly.
I really think that's over thinking things. Let's just match
kcalloc() exactly except without zeroing. The BUILD_BUG_ON() thing
is an over complication as well. We haven't needed it for
kcalloc().
The only impossible bit is picking the right name.
regards,
dan carpenter
On Tue, 14 Feb 2012, Dan Carpenter wrote:
> SAFE_ARRAY_SIZE() would return the size if there were no overflow
> and -1 on errors? We can't return zero on errors because there are
> a lot of places which do zero size allocations and it's valid. It
> seems ugly.
>
> I really think that's over thinking things. Let's just match
> kcalloc() exactly except without zeroing. The BUILD_BUG_ON() thing
> is an over complication as well. We haven't needed it for
> kcalloc().
It is and we're not going to phase out a userspace-like kcalloc() API with
something as verbose as SAFE_ARRAY_SIZE().
Pekka
On Feb 14, 2012, at 2:20 AM, Dan Carpenter wrote:
> I really think that's over thinking things. Let's just match
> kcalloc() exactly except without zeroing. The BUILD_BUG_ON() thing
> is an over complication as well. We haven't needed it for
> kcalloc().
I don't think the BUILD_BUG_ON macro is useful here nor in kcalloc
(besides gcc won't give you much handy information).
Just matching the new non-zeroing array allocator with kcalloc seems
like the right thing to do. We had quite a few patches that could
be simpler with it. For now I don't feel like it's necessary to
change the API (e.g., making gfp_t as the first argument), do "smart"
optimizations (e.g., recognizing the first argument is a constant),
nor add more allocators (e.g., to match vmalloc, kmalloc_node).
- xi
On Tue, 14 Feb 2012, Dan Carpenter wrote:
> SAFE_ARRAY_SIZE() would return the size if there were no overflow
> and -1 on errors? We can't return zero on errors because there are
> a lot of places which do zero size allocations and it's valid. It
> seems ugly.
We could also catch these issues with BUG() or WARN_ON() and then return
zero.
> I really think that's over thinking things. Let's just match
> kcalloc() exactly except without zeroing. The BUILD_BUG_ON() thing
> is an over complication as well. We haven't needed it for
> kcalloc().
The best thing is to remove kcalloc and get it all cleaned up
with some mechanism to safely calculate the size of an array to be
allocated.
The other way will lead to naming issues and then to a multiplication of
variants of the allocator interface. It makes things difficult to
understand and handle.
Keep it simple by providing a function that determines the array size and
handles any possible error condition.
On Feb 14, 2012, at 10:02 AM, Christoph Lameter wrote:
> We could also catch these issues with BUG() or WARN_ON() and then return
> zero.
You cannot have SAFE_ARRAY_SIZE return 0 when an integer overflow
occurs.
1) kmalloc(0) has a different semantics.
2) Using kmalloc(0) allows DoS attacks because often after kmalloc()
there is some initialization code that writes to the allocated
memory, such as:
p = kmalloc(SAFE_ARRAY_SIZE(n, size), ...);
for (i = 0; i < n; ++i)
p[i] = ...;
Besides, BUG() still allows DoS attacks and WARN_ON() would flood
the log, especially if n is controlled from user space. Neither
seems appropriate here.
- xi
On Tue, 14 Feb 2012, Xi Wang wrote:
> On Feb 14, 2012, at 10:02 AM, Christoph Lameter wrote:
> > We could also catch these issues with BUG() or WARN_ON() and then return
> > zero.
>
> You cannot have SAFE_ARRAY_SIZE return 0 when an integer overflow
> occurs.
You can if you check the results later. A zero size return would be an
indication of an error. No need to pass it on to kmalloc.
> Besides, BUG() still allows DoS attacks and WARN_ON() would flood
> the log, especially if n is controlled from user space. Neither
> seems appropriate here.
We have means at various level to control the "flood."
On Feb 14, 2012, at 11:34 AM, Christoph Lameter wrote:
> You can if you check the results later. A zero size return would be an
> indication of an error. No need to pass it on to kmalloc.
Maybe I misunderstood something here. How do you not pass it to
kmalloc() with kmalloc(SAFE_ARRAY_SIZE(n, size), ...)?
- xi
On Tue, 14 Feb 2012, Xi Wang wrote:
> On Feb 14, 2012, at 11:34 AM, Christoph Lameter wrote:
> > You can if you check the results later. A zero size return would be an
> > indication of an error. No need to pass it on to kmalloc.
>
> Maybe I misunderstood something here. How do you not pass it to
> kmalloc() with kmalloc(SAFE_ARRAY_SIZE(n, size), ...)?
Ok two patches to address this. First one
Subject: Uninline kcalloc
kcalloc is not used in performance critical ways. So it does not need to
be inline. If we would add diagnostics to track the overflow occurrences
then such code would be replicated at all call sites in the kernel.
Signed-off-by: Christoph Lameter <[email protected]>
---
include/linux/slab.h | 7 +------
mm/util.c | 15 +++++++++++++++
2 files changed, 16 insertions(+), 6 deletions(-)
Index: linux-2.6/include/linux/slab.h
===================================================================
--- linux-2.6.orig/include/linux/slab.h 2012-02-14 09:56:08.000000000 -0600
+++ linux-2.6/include/linux/slab.h 2012-02-14 13:32:43.000000000 -0600
@@ -240,12 +240,7 @@ size_t ksize(const void *);
* for general use, and so are not documented here. For a full list of
* potential flags, always refer to linux/gfp.h.
*/
-static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
-{
- if (size != 0 && n > ULONG_MAX / size)
- return NULL;
- return __kmalloc(n * size, flags | __GFP_ZERO);
-}
+void *kcalloc(size_t n, size_t size, gfp_t flags);
#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
/**
Index: linux-2.6/mm/util.c
===================================================================
--- linux-2.6.orig/mm/util.c 2012-02-14 09:56:08.000000000 -0600
+++ linux-2.6/mm/util.c 2012-02-14 13:32:54.000000000 -0600
@@ -75,6 +75,21 @@ void *kmemdup(const void *src, size_t le
EXPORT_SYMBOL(kmemdup);
/**
+ * kcalloc - allocate memory for an array. The memory is set to zero.
+ *
+ * @n: number of elements.
+ * @size: element size.
+ * @flags: the type of memory to allocate.
+ */
+void *kcalloc(size_t n, size_t size, gfp_t flags)
+{
+ if (size != 0 && n > ULONG_MAX / size)
+ return NULL;
+ return __kmalloc(n * size, flags | __GFP_ZERO);
+}
+EXPORT_SYMBOL(kcalloc);
+
+/**
* memdup_user - duplicate memory region from user space
*
* @src: source address in user space
This patch still preserves kcalloc. But note that if kcalloc returns NULL
then multiple conditions may have caused it. One is that the array is
simply too large. The other may be that such an allocation is not possible
due to fragmentation.
Subject: Introduce calculate_array_size
calculate_array_size calculates the size of an array while
checking for errors. Returns 0 if the size is too large.
Signed-off-by: Christoph Lameter <[email protected]>
---
include/linux/slab.h | 15 +++++++++++++++
mm/util.c | 9 ++++++---
2 files changed, 21 insertions(+), 3 deletions(-)
Index: linux-2.6/include/linux/slab.h
===================================================================
--- linux-2.6.orig/include/linux/slab.h 2012-02-14 13:32:43.000000000 -0600
+++ linux-2.6/include/linux/slab.h 2012-02-14 13:34:41.000000000 -0600
@@ -242,6 +242,21 @@ size_t ksize(const void *);
*/
void *kcalloc(size_t n, size_t size, gfp_t flags);
+/*
+ * calculate_array_size - Calculate an array size given the size of a
+ * particular element with checking for overflow.
+ *
+ * Return 0 if there is an overflow.
+ */
+static inline long calculate_array_size(size_t n, size_t size)
+{
+ if (size != 0 && n > ULONG_MAX / size)
+
+ return 0;
+
+ return n * size;
+}
+
#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
/**
* kmalloc_node - allocate memory from a specific node
Index: linux-2.6/mm/util.c
===================================================================
--- linux-2.6.orig/mm/util.c 2012-02-14 13:32:54.000000000 -0600
+++ linux-2.6/mm/util.c 2012-02-14 13:34:10.000000000 -0600
@@ -83,9 +83,12 @@ EXPORT_SYMBOL(kmemdup);
*/
void *kcalloc(size_t n, size_t size, gfp_t flags)
{
- if (size != 0 && n > ULONG_MAX / size)
- return NULL;
- return __kmalloc(n * size, flags | __GFP_ZERO);
+ size_t s = calculate_array_size(n, size);
+
+ if (s)
+ return kzalloc(s, flags);
+
+ return NULL;
}
EXPORT_SYMBOL(kcalloc);
On Tue, 14 Feb 2012 13:33:40 -0600 (CST)
Christoph Lameter <[email protected]> wrote:
> Subject: Uninline kcalloc
>
> kcalloc is not used in performance critical ways. So it does not need to
> be inline. If we would add diagnostics to track the overflow occurrences
> then such code would be replicated at all call sites in the kernel.
Uninlining kcalloc() seems reasonable. But if we're going to uninline
kcalloc() then we also should uninline kmalloc_array().
And yes, it's still called kmalloc_array() in my tree. I've been
following this discussion for N days waiting for a reason for changing
the original patch and I ain't seen one yet.
From: Xi Wang <[email protected]>
Subject: slab: introduce kmalloc_array()
Introduce a kmalloc_array() wrapper that performs integer overflow
checking without zeroing the memory.
Suggested-by: Andrew Morton <[email protected]>
Suggested-by: Jens Axboe <[email protected]>
Signed-off-by: Xi Wang <[email protected]>
Cc: Pekka Enberg <[email protected]>
Cc: Dan Carpenter <[email protected]>
Signed-off-by: Andrew Morton <[email protected]>
---
include/linux/slab.h | 17 ++++++++++++++---
1 file changed, 14 insertions(+), 3 deletions(-)
diff -puN include/linux/slab.h~slab-introduce-kmalloc_array include/linux/slab.h
--- a/include/linux/slab.h~slab-introduce-kmalloc_array
+++ a/include/linux/slab.h
@@ -190,7 +190,7 @@ size_t ksize(const void *);
#endif
/**
- * kcalloc - allocate memory for an array. The memory is set to zero.
+ * kmalloc_array - allocate memory for an array.
* @n: number of elements.
* @size: element size.
* @flags: the type of memory to allocate.
@@ -240,11 +240,22 @@ size_t ksize(const void *);
* for general use, and so are not documented here. For a full list of
* potential flags, always refer to linux/gfp.h.
*/
-static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
{
if (size != 0 && n > ULONG_MAX / size)
return NULL;
- return __kmalloc(n * size, flags | __GFP_ZERO);
+ return __kmalloc(n * size, flags);
+}
+
+/**
+ * kcalloc - allocate memory for an array. The memory is set to zero.
+ * @n: number of elements.
+ * @size: element size.
+ * @flags: the type of memory to allocate (see kmalloc).
+ */
+static inline void *kcalloc(size_t n, size_t size, gfp_t flags)
+{
+ return kmalloc_array(n, size, flags | __GFP_ZERO);
}
#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
_
On Tue, 14 Feb 2012 13:37:44 -0600 (CST)
Christoph Lameter <[email protected]> wrote:
> This patch still preserves kcalloc. But note that if kcalloc returns NULL
> then multiple conditions may have caused it. One is that the array is
> simply too large. The other may be that such an allocation is not possible
> due to fragmentation.
>
>
> Subject: Introduce calculate_array_size
>
> calculate_array_size calculates the size of an array while
> checking for errors. Returns 0 if the size is too large.
>
> Signed-off-by: Christoph Lameter <[email protected]>
>
>
> ---
> include/linux/slab.h | 15 +++++++++++++++
> mm/util.c | 9 ++++++---
> 2 files changed, 21 insertions(+), 3 deletions(-)
>
> Index: linux-2.6/include/linux/slab.h
> ===================================================================
> --- linux-2.6.orig/include/linux/slab.h 2012-02-14 13:32:43.000000000 -0600
> +++ linux-2.6/include/linux/slab.h 2012-02-14 13:34:41.000000000 -0600
> @@ -242,6 +242,21 @@ size_t ksize(const void *);
> */
> void *kcalloc(size_t n, size_t size, gfp_t flags);
>
> +/*
> + * calculate_array_size - Calculate an array size given the size of a
> + * particular element with checking for overflow.
> + *
> + * Return 0 if there is an overflow.
> + */
> +static inline long calculate_array_size(size_t n, size_t size)
> +{
> + if (size != 0 && n > ULONG_MAX / size)
> +
> + return 0;
> +
> + return n * size;
> +}
> +
> #if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
> /**
> * kmalloc_node - allocate memory from a specific node
> Index: linux-2.6/mm/util.c
> ===================================================================
> --- linux-2.6.orig/mm/util.c 2012-02-14 13:32:54.000000000 -0600
> +++ linux-2.6/mm/util.c 2012-02-14 13:34:10.000000000 -0600
> @@ -83,9 +83,12 @@ EXPORT_SYMBOL(kmemdup);
> */
> void *kcalloc(size_t n, size_t size, gfp_t flags)
> {
> - if (size != 0 && n > ULONG_MAX / size)
> - return NULL;
> - return __kmalloc(n * size, flags | __GFP_ZERO);
> + size_t s = calculate_array_size(n, size);
> +
> + if (s)
> + return kzalloc(s, flags);
> +
> + return NULL;
> }
> EXPORT_SYMBOL(kcalloc);
The patch appears to be a no-op. Confused.
On 2012-02-14 13:37 -0600, Christoph Lameter wrote:
> This patch still preserves kcalloc. But note that if kcalloc returns NULL
> then multiple conditions may have caused it. One is that the array is
> simply too large. The other may be that such an allocation is not possible
> due to fragmentation.
[...]
> +static inline long calculate_array_size(size_t n, size_t size)
> +{
> + if (size != 0 && n > ULONG_MAX / size)
> +
> + return 0;
This isn't right. The above tests whether or not the result of the
multiplication will not be representable in an 'unsigned long'...
> +
> + return n * size;
but then the result is assigned to a (signed) long, which may overflow
if it's greater than LONG_MAX.
> +}
[...]
> void *kcalloc(size_t n, size_t size, gfp_t flags)
> {
> - if (size != 0 && n > ULONG_MAX / size)
> - return NULL;
> - return __kmalloc(n * size, flags | __GFP_ZERO);
> + size_t s = calculate_array_size(n, size);
> +
> + if (s)
> + return kzalloc(s, flags);
> +
> + return NULL;
> }
This hunk changes the behaviour of kcalloc if either of the two size parameters
is 0.
Cheers,
--
Nick Bowler, Elliptic Technologies (http://www.elliptictech.com/)
On Tue, Feb 14, 2012 at 10:45 PM, Andrew Morton
<[email protected]> wrote:
> On Tue, 14 Feb 2012 13:33:40 -0600 (CST)
> Christoph Lameter <[email protected]> wrote:
>
>> Subject: Uninline kcalloc
>>
>> kcalloc is not used in performance critical ways. So it does not need to
>> be inline. If we would add diagnostics to track the overflow occurrences
>> then such code would be replicated at all call sites in the kernel.
>
> Uninlining kcalloc() seems reasonable. ?But if we're going to uninline
> kcalloc() then we also should uninline kmalloc_array().
Well, kcalloc() used to be uninline and we made it inline on purpose
at some point. I don't have a git tree here so I can't check. IIRC it
had something to do with kernel text size reduction.
> And yes, it's still called kmalloc_array() in my tree. ?I've been
> following this discussion for N days waiting for a reason for changing
> the original patch and I ain't seen one yet.
Me neither. I don't think Christoph's SAFE_ARRAY_SIZE() suggestion
makes much sense, really. It's more verbose, less obvious API, and
doesn't really deal with the overflow case cleanly.
Pekka
On Tue, 14 Feb 2012, Pekka Enberg wrote:
> Me neither. I don't think Christoph's SAFE_ARRAY_SIZE() suggestion
> makes much sense, really. It's more verbose, less obvious API, and
> doesn't really deal with the overflow case cleanly.
IMHO Having a function to deal with the overflow of a multiplication and
then do an allocation based on the result is a conflation of two different
things that need to be separate. kcalloc only exists because there is
an ancient user space function that somehow got a second parameter instead
of just using the same as malloc().
On Tue, 14 Feb 2012, Nick Bowler wrote:
> On 2012-02-14 13:37 -0600, Christoph Lameter wrote:
> > This patch still preserves kcalloc. But note that if kcalloc returns NULL
> > then multiple conditions may have caused it. One is that the array is
> > simply too large. The other may be that such an allocation is not possible
> > due to fragmentation.
> [...]
> > +static inline long calculate_array_size(size_t n, size_t size)
> > +{
> > + if (size != 0 && n > ULONG_MAX / size)
> > +
> > + return 0;
>
> This isn't right. The above tests whether or not the result of the
> multiplication will not be representable in an 'unsigned long'...
Yes and so does the current kcalloc.
> > + return n * size;
>
> but then the result is assigned to a (signed) long, which may overflow
> if it's greater than LONG_MAX.
That can happen? But you are right its better to use the size_t as the
result of the argument. There is a gooh of long / size_t confusion
already. This useless function should not be in the kernel.
> > +}
> [...]
> > void *kcalloc(size_t n, size_t size, gfp_t flags)
> > {
> > - if (size != 0 && n > ULONG_MAX / size)
> > - return NULL;
> > - return __kmalloc(n * size, flags | __GFP_ZERO);
> > + size_t s = calculate_array_size(n, size);
> > +
> > + if (s)
> > + return kzalloc(s, flags);
> > +
> > + return NULL;
> > }
>
> This hunk changes the behaviour of kcalloc if either of the two size parameters
> is 0.
You want ZERO_PTR returns?
NULL is one permissible return value of calloc() if size == 0. So we are
now deviating from user space conventions.
Subject: Introduce calculate_array_size
calculate_array_size calculates the size of an array while
checking for errors. Returns 0 if the size is too large.
Signed-off-by: Christoph Lameter <[email protected]>
---
include/linux/slab.h | 15 +++++++++++++++
mm/util.c | 7 +++++--
2 files changed, 20 insertions(+), 2 deletions(-)
Index: linux-2.6/include/linux/slab.h
===================================================================
--- linux-2.6.orig/include/linux/slab.h 2012-02-14 15:16:53.000000000 -0600
+++ linux-2.6/include/linux/slab.h 2012-02-14 15:21:39.000000000 -0600
@@ -242,6 +242,21 @@ size_t ksize(const void *);
*/
void *kcalloc(size_t n, size_t size, gfp_t flags);
+/*
+ * calculate_array_size - Calculate an array size given the size of a
+ * particular element with checking for overflow.
+ *
+ * Return 0 if there is an overflow.
+ */
+static inline size_t calculate_array_size(size_t n, size_t size)
+{
+ if (n > ULONG_MAX / size)
+
+ return 0;
+
+ return n * size;
+}
+
#if !defined(CONFIG_NUMA) && !defined(CONFIG_SLOB)
/**
* kmalloc_node - allocate memory from a specific node
Index: linux-2.6/mm/util.c
===================================================================
--- linux-2.6.orig/mm/util.c 2012-02-14 15:16:53.000000000 -0600
+++ linux-2.6/mm/util.c 2012-02-14 15:21:05.000000000 -0600
@@ -83,9 +83,12 @@ EXPORT_SYMBOL(kmemdup);
*/
void *kcalloc(size_t n, size_t size, gfp_t flags)
{
- if (size != 0 && n > ULONG_MAX / size)
+ size_t s = calculate_array_size(n, size);
+
+ if (size && !s)
return NULL;
- return __kmalloc(n * size, flags | __GFP_ZERO);
+
+ return kzalloc(s, flags);
}
EXPORT_SYMBOL(kcalloc);
On Tue, 14 Feb 2012, Pekka Enberg wrote:
>> Me neither. I don't think Christoph's SAFE_ARRAY_SIZE() suggestion
>> makes much sense, really. It's more verbose, less obvious API, and
>> doesn't really deal with the overflow case cleanly.
On Tue, Feb 14, 2012 at 11:09 PM, Christoph Lameter <[email protected]> wrote:
> IMHO Having a function to deal with the overflow of a multiplication and
> then do an allocation based on the result is a conflation of two different
> things that need to be separate. kcalloc only exists because there is
> an ancient user space function that somehow got a second parameter instead
> of just using the same as malloc().
It's an ancient userspace function that everybody knows how to use.
There really isn't big enough gains from SAFE_ARRAY_SIZE() to justify
a new API. And it's not as if the macro is an elegant way to solve the
problem at hand either.
Pekka
On Tue, 14 Feb 2012, Pekka Enberg wrote:
> On Tue, 14 Feb 2012, Pekka Enberg wrote:
> >> Me neither. I don't think Christoph's SAFE_ARRAY_SIZE() suggestion
> >> makes much sense, really. It's more verbose, less obvious API, and
> >> doesn't really deal with the overflow case cleanly.
>
> On Tue, Feb 14, 2012 at 11:09 PM, Christoph Lameter <[email protected]> wrote:
> > IMHO Having a function to deal with the overflow of a multiplication and
> > then do an allocation based on the result is a conflation of two different
> > things that need to be separate. kcalloc only exists because there is
> > an ancient user space function that somehow got a second parameter instead
> > of just using the same as malloc().
>
> It's an ancient userspace function that everybody knows how to use.
> There really isn't big enough gains from SAFE_ARRAY_SIZE() to justify
> a new API. And it's not as if the macro is an elegant way to solve the
> problem at hand either.
Ok then keep the calloc style API but at least allow the refactoring with
an additional function. That way one is able to check if there is an
overflow in size calculation and can differentiate that condition from an
out of memory situation due to a large contiguous allocation attempt.
On Feb 14, 2012, at 4:09 PM, Christoph Lameter wrote:
> IMHO Having a function to deal with the overflow of a multiplication and
> then do an allocation based on the result is a conflation of two different
> things that need to be separate. kcalloc only exists because there is
> an ancient user space function that somehow got a second parameter instead
> of just using the same as malloc().
I don't understand why these kcalloc patches have anything to do
with kmalloc(SAFE_ARRAY_SIZE(...), ...) you proposed.
It also doesn't make much sense to force the caller to check the
result of SAFE_ARRAY_SIZE() or calculate_array_size() before passing
it to kmalloc(). This is too verbose.
- xi
On Tue, 14 Feb 2012, Xi Wang wrote:
> On Feb 14, 2012, at 4:09 PM, Christoph Lameter wrote:
> > IMHO Having a function to deal with the overflow of a multiplication and
> > then do an allocation based on the result is a conflation of two different
> > things that need to be separate. kcalloc only exists because there is
> > an ancient user space function that somehow got a second parameter instead
> > of just using the same as malloc().
>
> I don't understand why these kcalloc patches have anything to do
> with kmalloc(SAFE_ARRAY_SIZE(...), ...) you proposed.
Not sure why you are so hung up on SAFE_ARRAY_SIZE. It was an idea to
discuss. Certainly having an inline function seems to be better.
> It also doesn't make much sense to force the caller to check the
> result of SAFE_ARRAY_SIZE() or calculate_array_size() before passing
> it to kmalloc(). This is too verbose.
kcalloc is still there. Certainly useful for legacy purposes. But I'd feel
better if I had fine grained control over the size of my allocation rather
than rely on the slab allocators to check up on my multiplication.
With these patches both is possible. And if you want the check of an
allocation that is not zeroed then you can do so because you have a
function that will perform the size check for you without calling into the
slab allocator.
On Feb 14, 2012, at 5:08 PM, Christoph Lameter wrote:
> kcalloc is still there. Certainly useful for legacy purposes. But I'd feel
> better if I had fine grained control over the size of my allocation rather
> than rely on the slab allocators to check up on my multiplication.
>
> With these patches both is possible. And if you want the check of an
> allocation that is not zeroed then you can do so because you have a
> function that will perform the size check for you without calling into the
> slab allocator.
In the code you proposed, where calculate_array_size() returns 0
for overflow, one has to write:
size_t s = calculate_array_size(n, size);
if (s)
p = kmalloc(s, ...);
This "if" thing is just too verbose --- you need three lines to
allocate an array.
We could change calculate_array_size() to return ULONG_MAX or some
large number with which kmalloc() would fail. Then one would write:
p = kmalloc(calculate_array_size(n, size), ...);
This looks better to me. The advantage is that we don't need another
allocator (and avoid this name picking game). The disadvantage is
that the semantics of calculate_array_size(), returning ULONG_MAX
on overflow, sounds sort of strange.
- xi
On Wed, 15 Feb 2012, Xi Wang wrote:
> for overflow, one has to write:
>
> size_t s = calculate_array_size(n, size);
> if (s)
> p = kmalloc(s, ...);
>
> This "if" thing is just too verbose --- you need three lines to
> allocate an array.
>
> We could change calculate_array_size() to return ULONG_MAX or some
> large number with which kmalloc() would fail. Then one would write:
Any allocation larger than MAX_ORDER << PAGE_SHIFT will fail since the
page allocator cannot serve larger contigous pages.
On 2012-02-14 15:24 -0600, Christoph Lameter wrote:
> On Tue, 14 Feb 2012, Nick Bowler wrote:
>
> > On 2012-02-14 13:37 -0600, Christoph Lameter wrote:
> > > This patch still preserves kcalloc. But note that if kcalloc returns NULL
> > > then multiple conditions may have caused it. One is that the array is
> > > simply too large. The other may be that such an allocation is not possible
> > > due to fragmentation.
> > [...]
> > > +static inline long calculate_array_size(size_t n, size_t size)
> > > +{
> > > + if (size != 0 && n > ULONG_MAX / size)
> > > +
> > > + return 0;
> >
> > This isn't right. The above tests whether or not the result of the
> > multiplication will not be representable in an 'unsigned long'...
>
> Yes and so does the current kcalloc.
Well, the current kcalloc doesn't assign the result to a signed long.
However, it does assign the result to a size_t, which makes one wonder
why it's not testing against SIZE_MAX. If size_t has the same range as
unsigned long on all architectures, then this confusion doesn't matter,
but is that actually the case?
> > > + return n * size;
> >
> > but then the result is assigned to a (signed) long, which may overflow
> > if it's greater than LONG_MAX.
>
> That can happen?
Yes, because LONG_MAX (the maximum value of your return type) is
strictly less than ULONG_MAX (what you test against). It's not hard to
pick input numbers that multiply to something between LONG_MAX and
ULONG_MAX, which will cause your function to return a negative value
(standard C leaves the result of such a conversion implementation-
defined, but I'll assume for now that it works this way for everything
that compiles Linux).
Admittedly, your kcalloc change then assigns this negative value to a
size_t, which will result in the correct positive value assuming
SIZE_MAX == ULONG_MAX, but that's gratuitously roundabout.
[...]
> > [...]
> > > void *kcalloc(size_t n, size_t size, gfp_t flags)
> > > {
> > > - if (size != 0 && n > ULONG_MAX / size)
> > > - return NULL;
> > > - return __kmalloc(n * size, flags | __GFP_ZERO);
> > > + size_t s = calculate_array_size(n, size);
> > > +
> > > + if (s)
> > > + return kzalloc(s, flags);
> > > +
> > > + return NULL;
> > > }
> >
> > This hunk changes the behaviour of kcalloc if either of the two size parameters
> > is 0.
>
> You want ZERO_PTR returns?
>
> NULL is one permissible return value of calloc() if size == 0. So we are
> now deviating from user space conventions.
Sort of. While standard C leaves it implementation-defined whether
successful zero-sized allocations are possible, all sane implementations
let them succeed. Hence, portable C apps need to handle 0 as a special
case, because there are insane implementations out there. There's no
reason for the kernel to be one of them.
Regardless, this was still a (presumably unintentional) change from
the previous behaviour.
Cheers,
--
Nick Bowler, Elliptic Technologies (http://www.elliptictech.com/)
On 2012-02-15 15:17 -0500, Nick Bowler wrote:
> On 2012-02-14 15:24 -0600, Christoph Lameter wrote:
> > On Tue, 14 Feb 2012, Nick Bowler wrote:
> >
> > > On 2012-02-14 13:37 -0600, Christoph Lameter wrote:
> > > > This patch still preserves kcalloc. But note that if kcalloc returns NULL
> > > > then multiple conditions may have caused it. One is that the array is
> > > > simply too large. The other may be that such an allocation is not possible
> > > > due to fragmentation.
> > > [...]
> > > > +static inline long calculate_array_size(size_t n, size_t size)
> > > > +{
> > > > + if (size != 0 && n > ULONG_MAX / size)
> > > > +
> > > > + return 0;
> > >
> > > This isn't right. The above tests whether or not the result of the
> > > multiplication will not be representable in an 'unsigned long'...
> >
> > Yes and so does the current kcalloc.
>
> Well, the current kcalloc doesn't assign the result to a signed long.
> However, it does assign the result to a size_t, which makes one wonder
> why it's not testing against SIZE_MAX.
Of course, right after I send this I realize that we do not appear to
define SIZE_MAX in the kernel. So s/SIZE_MAX/((size_t)-1)/g.
> If size_t has the same range as unsigned long on all architectures,
> then this confusion doesn't matter, but is that actually the case?
>
> > > > + return n * size;
> > >
> > > but then the result is assigned to a (signed) long, which may overflow
> > > if it's greater than LONG_MAX.
> >
> > That can happen?
>
> Yes, because LONG_MAX (the maximum value of your return type) is
> strictly less than ULONG_MAX (what you test against). It's not hard to
> pick input numbers that multiply to something between LONG_MAX and
> ULONG_MAX, which will cause your function to return a negative value
> (standard C leaves the result of such a conversion implementation-
> defined, but I'll assume for now that it works this way for everything
> that compiles Linux).
>
> Admittedly, your kcalloc change then assigns this negative value to a
> size_t, which will result in the correct positive value assuming
> SIZE_MAX == ULONG_MAX, but that's gratuitously roundabout.
>
> [...]
> > > [...]
> > > > void *kcalloc(size_t n, size_t size, gfp_t flags)
> > > > {
> > > > - if (size != 0 && n > ULONG_MAX / size)
> > > > - return NULL;
> > > > - return __kmalloc(n * size, flags | __GFP_ZERO);
> > > > + size_t s = calculate_array_size(n, size);
> > > > +
> > > > + if (s)
> > > > + return kzalloc(s, flags);
> > > > +
> > > > + return NULL;
> > > > }
> > >
> > > This hunk changes the behaviour of kcalloc if either of the two size parameters
> > > is 0.
> >
> > You want ZERO_PTR returns?
> >
> > NULL is one permissible return value of calloc() if size == 0. So we are
> > now deviating from user space conventions.
>
> Sort of. While standard C leaves it implementation-defined whether
> successful zero-sized allocations are possible, all sane implementations
> let them succeed. Hence, portable C apps need to handle 0 as a special
> case, because there are insane implementations out there. There's no
> reason for the kernel to be one of them.
>
> Regardless, this was still a (presumably unintentional) change from
> the previous behaviour.
>
> Cheers,
--
Nick Bowler, Elliptic Technologies (http://www.elliptictech.com/)
On Feb 15, 2012, at 2:34 PM, Christoph Lameter wrote:
> Any allocation larger than MAX_ORDER << PAGE_SHIFT will fail since the
> page allocator cannot serve larger contigous pages.
Yes, any number larger than KMALLOC_MAX_SIZE would do the trick.
The question is whether people would like to adopt
kmalloc(ARRAY_BYTES(n, size), ...);
or
knalloc(n, size, ...);
Besides, I am worried that ARRAY_BYTES is error-prone because you
have to make sure that ARRAY_BYTES is used only in *alloc, not
elsewhere, not in forms like ARRAY_BYTES(n, size) + padding_size,
etc. If ARRAY_BYTES is mostly used with kmalloc(), and the only
safe form is kmalloc(ARRAY_BYTES(n, size), ...), then adding a new
allocator knalloc(n, size, ...) seems like a simpler choice.
BTW, here goes a partial list of places where the new allocator
could be used to simplify existing checks.
fs/cifs/cifsacl.c:912
if (num_aces > ULONG_MAX / sizeof(struct cifs_ace *))
return;
ppace = kmalloc(num_aces * sizeof(struct cifs_ace *),
GFP_KERNEL);
fs/cifs/asn1.c:428
if (size < 2 || size > UINT_MAX/sizeof(unsigned long))
return 0;
*oid = kmalloc(size * sizeof(unsigned long), GFP_ATOMIC);
fs/nfs/callback_xdr.c:308
if (n > ULONG_MAX / sizeof(*args->devs)) {
status = htonl(NFS4ERR_BADXDR);
goto out;
}
args->devs = kmalloc(n * sizeof(*args->devs), GFP_KERNEL);
net/ipv4/netfilter/nf_nat_snmp_basic.c:447
if (size < 2 || size > ULONG_MAX/sizeof(unsigned long))
return 0;
*oid = kmalloc(size * sizeof(unsigned long), GFP_ATOMIC);
drivers/staging/comedi/comedi_fops.c:673
insns =
kcalloc(insnlist.n_insns, sizeof(struct comedi_insn), GFP_KERNEL);
I believe there are more places without those checks, where the new
allocator can offer better security.
- xi
On Wed, 15 Feb 2012, Xi Wang wrote:
> On Feb 15, 2012, at 2:34 PM, Christoph Lameter wrote:
> > Any allocation larger than MAX_ORDER << PAGE_SHIFT will fail since the
> > page allocator cannot serve larger contigous pages.
>
> Yes, any number larger than KMALLOC_MAX_SIZE would do the trick.
> The question is whether people would like to adopt
>
> kmalloc(ARRAY_BYTES(n, size), ...);
Well it would be f.e.
kmalloc_node(calculate_array_size(sizeof(struct bla), n), GFP_KERNEL, my_numa_node)
or
vmalloc(calculate_array_size(sizeof(struct blu), n));
Then there is
vzalloc
kzalloc
vmalloc_32
alloc_bootmem (MAXORDER limit may not work)
alloc_remap
...
This would also work for special subsystem allocations like
usb_alloc_coherent
dm_vcalloc
devres_alloc
....
The use of a function or macro makes the overflow check much more
universal and allows these array allocations to occur with different
allocation functions throughout the kernel.
Please do not increase the number of allocation functions needlessly with
new variants.
On Feb 16, 2012, at 9:51 AM, Christoph Lameter wrote:
> Then there is
>
> vzalloc
> kzalloc
> vmalloc_32
> alloc_bootmem (MAXORDER limit may not work)
> alloc_remap
>
> ...
>
> This would also work for special subsystem allocations like
>
> usb_alloc_coherent
> dm_vcalloc
> devres_alloc
>
> ....
>
>
> The use of a function or macro makes the overflow check much more
> universal and allows these array allocations to occur with different
> allocation functions throughout the kernel.
No, it does NOT. It can be easily misued to introduce more bugs.
1) Should calculate_array_size() return 0 on overflow, as you
orginally proposed?
No, as Dan, Pekka, and some others already pointed out.
2) Should calculate_array_size() return something like
KMALLOC_MAX_SIZE + 1?
No, because you intended to use it with other allocators such as
vmalloc().
3) Should calculate_array_size() return ULONG_MAX/SIZE_MAX/-1?
No! Consider devres_alloc() you mentioned. Then you do
devres_alloc(..., calculate_array_size(n, size), ...).
It internally invokes kmalloc() with allocation size:
sizeof(struct devres) + calculate_array_size(n, size).
When n * size overflows, calculate_array_size() returns ULONG_MAX,
and the allocation size wraps around to a small integer!
I like the idea of "do not add an allocator unless necessary".
However, "universal" calculate_array_size() just doesn't work,
unless you can find the correct semantics or limit its use.
It can be easily misused and bring more trouble than it's worth.
- xi
On Thu, 16 Feb 2012, Xi Wang wrote:
> > The use of a function or macro makes the overflow check much more
> > universal and allows these array allocations to occur with different
> > allocation functions throughout the kernel.
>
> No, it does NOT. It can be easily misued to introduce more bugs.
>
> 1) Should calculate_array_size() return 0 on overflow, as you
> orginally proposed?
I thought you worked that out?
> No, as Dan, Pekka, and some others already pointed out.
>
> 2) Should calculate_array_size() return something like
> KMALLOC_MAX_SIZE + 1?
>
> No, because you intended to use it with other allocators such as
> vmalloc().
vmalloc will also fail if you pass a large number.
> 3) Should calculate_array_size() return ULONG_MAX/SIZE_MAX/-1?
>
> No! Consider devres_alloc() you mentioned. Then you do
>
> devres_alloc(..., calculate_array_size(n, size), ...).
>
> It internally invokes kmalloc() with allocation size:
>
> sizeof(struct devres) + calculate_array_size(n, size).
That is an addition which is less likely to overflow. Especially if you
return MAX_ORDER << PAGE_SIZE from the array size calculation.
It would be best to be universal if you want to introduce size overflow
checking rather than just dealing with one case and let the rest of the
kernel fend for themselves. I think we need something like
calculate_array_size() with proper error handling (and no I am not
particular set on having it done a particular way. Just that is it done).