diff mbox series

overflow: optimize struct_size() calculation

Message ID 20240909115221.1298010-1-mailhol.vincent@wanadoo.fr (mailing list archive)
State Superseded
Headers show
Series overflow: optimize struct_size() calculation | expand

Commit Message

Vincent Mailhol Sept. 9, 2024, 11:52 a.m. UTC
If the offsetof() of a given flexible array member (fam) is smaller
than the sizeof() of the containing struct, then the struct_size()
macro reports a size which is too big.

This occurs when the two conditions below are met:

  - there are padding bytes after the penultimate member (the member
    preceding the fam)
  - the alignment of the fam is less than the penultimate member's
    alignment

In that case, the fam overlaps with the padding bytes of the
penultimate member. This behaviour is not captured in the current
struct_size() macro, potentially resulting in an overestimated size.

Below example illustrates the issue:

  struct s {
  	u64 foo;
  	u32 count;
  	u8 fam[] __counted_by(count);
  };

Assuming a 64 bits architecture:

  - there are 4 bytes of padding after s.count (the penultimate
    member)
  - sizeof(struct s) is 16 bytes
  - the offset of s.fam is 12 bytes
  - the alignment of s.fam is 1 byte

The sizes are as below:

   s.count	current struct_size()	actual size
  -----------------------------------------------------------------------
   0		16			16
   1		17			16
   2		18			16
   3		19			16
   4		20			16
   5		21			17
   .		.			.
   .		.			.
   .		.			.
   n		sizeof(struct s) + n	max(sizeof(struct s),
					    offsetof(struct s, fam) + n)

Change struct_size() from this pseudo code logic:

  sizeof(struct s) + sizeof(*s.fam) * s.count

to that pseudo code logic:

  max(sizeof(struct s), offsetof(struct s, fam) + sizeof(*s.fam) * s.count)

Here, the lowercase max*() macros can cause struct_size() to return a
non constant integer expression which would break the DEFINE_FLEX()
macro by making it declare a variable length array. Because of that,
use the unsafe MAX() macro only if the expression is constant and use
the safer max_t() otherwise.

Reference: ISO/IEC 9899:2018 §6.7.2.1 "Structure and union specifiers" ¶18

Signed-off-by: Vincent Mailhol <mailhol.vincent@wanadoo.fr>
---

I also tried to think of whether the current struct_size() macro could
be a security issue.

The only example I can think of is if someone manually allocates the
exact size but then use the current struct_size() macro.

For example (reusing the struct s from above):

  u32 count = 5;
  struct s *s = kalloc(offsetof(typeof(*s), fam) + count);
  s->count = count;
  memset(s, 0, struct_size(s, fam, count)); /* 4 bytes buffer overflow */

If we have concerns that above pattern may actually exist, then this
patch should also go to stable. I personally think that the above is a
bit convoluted and, as such, I only suggest this patch to go to next.
---
 include/linux/overflow.h | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

Comments

David Laight Sept. 9, 2024, 4:19 p.m. UTC | #1
From: Vincent Mailhol
> Sent: 09 September 2024 12:52
> 
> If the offsetof() of a given flexible array member (fam) is smaller
> than the sizeof() of the containing struct, then the struct_size()
> macro reports a size which is too big.
> 
> This occurs when the two conditions below are met:
> 
>   - there are padding bytes after the penultimate member (the member
>     preceding the fam)
>   - the alignment of the fam is less than the penultimate member's
>     alignment
> 
> In that case, the fam overlaps with the padding bytes of the
> penultimate member. This behaviour is not captured in the current
> struct_size() macro, potentially resulting in an overestimated size.
> 
> Below example illustrates the issue:
> 
>   struct s {
>   	u64 foo;
>   	u32 count;
>   	u8 fam[] __counted_by(count);
>   };
> 
> Assuming a 64 bits architecture:
> 
>   - there are 4 bytes of padding after s.count (the penultimate
>     member)
>   - sizeof(struct s) is 16 bytes
>   - the offset of s.fam is 12 bytes
>   - the alignment of s.fam is 1 byte
> 
> The sizes are as below:
> 
>    s.count	current struct_size()	actual size
>   -----------------------------------------------------------------------
>    0		16			16
>    1		17			16
>    2		18			16
>    3		19			16
>    4		20			16
>    5		21			17
>    .		.			.
>    .		.			.
>    .		.			.
>    n		sizeof(struct s) + n	max(sizeof(struct s),
> 					    offsetof(struct s, fam) + n)

I actually suspect that it matters so infrequently it isn't worth the effort.
Not only do you need a structure with 'tail padding' but you also need
the size to go from one kmalloc() bucket to another.

> 
> Change struct_size() from this pseudo code logic:
> 
>   sizeof(struct s) + sizeof(*s.fam) * s.count
> 
> to that pseudo code logic:
> 
>   max(sizeof(struct s), offsetof(struct s, fam) + sizeof(*s.fam) * s.count)
> 
> Here, the lowercase max*() macros can cause struct_size() to return a
> non constant integer expression which would break the DEFINE_FLEX()
> macro by making it declare a variable length array. Because of that,
> use the unsafe MAX() macro only if the expression is constant and use
> the safer max_t() otherwise.
> 
> Reference: ISO/IEC 9899:2018 §6.7.2.1 "Structure and union specifiers" ¶18
> 
> Signed-off-by: Vincent Mailhol <mailhol.vincent@wanadoo.fr>
> ---
> 
> I also tried to think of whether the current struct_size() macro could
> be a security issue.
> 
> The only example I can think of is if someone manually allocates the
> exact size but then use the current struct_size() macro.
> 
> For example (reusing the struct s from above):
> 
>   u32 count = 5;
>   struct s *s = kalloc(offsetof(typeof(*s), fam) + count);
>   s->count = count;
>   memset(s, 0, struct_size(s, fam, count)); /* 4 bytes buffer overflow */
> 
> If we have concerns that above pattern may actually exist, then this
> patch should also go to stable. I personally think that the above is a
> bit convoluted and, as such, I only suggest this patch to go to next.
> ---
>  include/linux/overflow.h | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/overflow.h b/include/linux/overflow.h
> index 0c7e3dcfe867..1384887f3684 100644
> --- a/include/linux/overflow.h
> +++ b/include/linux/overflow.h
> @@ -5,6 +5,7 @@
>  #include <linux/compiler.h>
>  #include <linux/limits.h>
>  #include <linux/const.h>
> +#include <linux/minmax.h>
> 
>  /*
>   * We need to compute the minimum and maximum values representable in a given
> @@ -369,8 +370,12 @@ static inline size_t __must_check size_sub(size_t minuend, size_t subtrahend)
>   */
>  #define struct_size(p, member, count)					\
>  	__builtin_choose_expr(__is_constexpr(count),			\
> -		sizeof(*(p)) + flex_array_size(p, member, count),	\
> -		size_add(sizeof(*(p)), flex_array_size(p, member, count)))
> +		MAX(sizeof(*(p)),					\
> +		    offsetof(typeof(*(p)), member) +			\
> +			flex_array_size(p, member, count)),		\
> +		max_t(size_t, sizeof(*(p)),				\
> +		      size_add(offsetof(typeof(*(p)), member),		\
> +			       flex_array_size(p, member, count))))

I don't think you need max_t() here, a plain max() should suffice.

	David

> 
>  /**
>   * struct_size_t() - Calculate size of structure with trailing flexible array
> --
> 2.25.1
> 

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
Vincent Mailhol Sept. 10, 2024, 1:48 a.m. UTC | #2
On Tue. 10 Sept. 2024 at 01:19, David Laight <David.Laight@aculab.com> wrote:
> From: Vincent Mailhol
> > Sent: 09 September 2024 12:52
> >
> > If the offsetof() of a given flexible array member (fam) is smaller
> > than the sizeof() of the containing struct, then the struct_size()
> > macro reports a size which is too big.
> >
> > This occurs when the two conditions below are met:
> >
> >   - there are padding bytes after the penultimate member (the member
> >     preceding the fam)
> >   - the alignment of the fam is less than the penultimate member's
> >     alignment
> >
> > In that case, the fam overlaps with the padding bytes of the
> > penultimate member. This behaviour is not captured in the current
> > struct_size() macro, potentially resulting in an overestimated size.
> >
> > Below example illustrates the issue:
> >
> >   struct s {
> >       u64 foo;
> >       u32 count;
> >       u8 fam[] __counted_by(count);
> >   };
> >
> > Assuming a 64 bits architecture:
> >
> >   - there are 4 bytes of padding after s.count (the penultimate
> >     member)
> >   - sizeof(struct s) is 16 bytes
> >   - the offset of s.fam is 12 bytes
> >   - the alignment of s.fam is 1 byte
> >
> > The sizes are as below:
> >
> >    s.count    current struct_size()   actual size
> >   -----------------------------------------------------------------------
> >    0          16                      16
> >    1          17                      16
> >    2          18                      16
> >    3          19                      16
> >    4          20                      16
> >    5          21                      17
> >    .          .                       .
> >    .          .                       .
> >    .          .                       .
> >    n          sizeof(struct s) + n    max(sizeof(struct s),
> >                                           offsetof(struct s, fam) + n)
>
> I actually suspect that it matters so infrequently it isn't worth the effort.
> Not only do you need a structure with 'tail padding'

There are a significant number of these. For example, this:

  $ git grep -E "(u8|char).*\[\] __counted_by.*;"

lists a couple dozen cases (a few of which are false positives, but
you get the idea). And that simple grep did not catch the full list
for sure.

Yes, it is not thousands, but in my view this isn't something I will
qualify as infrequent either.

> but you also need
> the size to go from one kmalloc() bucket to another.

I think that kmalloc() is only one example. Here, we can also
consider, for example, the memset() or the memcpy() operations.

This patch is not meant to revolutionise things for sure. It is more
of a "save the bytes" thing. Is it worth the effort? I would still say
yes (else I wouldn't have sent the patch), and now that this effort is
done, it is up to you guys.

> >
> > Change struct_size() from this pseudo code logic:
> >
> >   sizeof(struct s) + sizeof(*s.fam) * s.count
> >
> > to that pseudo code logic:
> >
> >   max(sizeof(struct s), offsetof(struct s, fam) + sizeof(*s.fam) * s.count)
> >
> > Here, the lowercase max*() macros can cause struct_size() to return a
> > non constant integer expression which would break the DEFINE_FLEX()
> > macro by making it declare a variable length array. Because of that,
> > use the unsafe MAX() macro only if the expression is constant and use
> > the safer max_t() otherwise.
> >
> > Reference: ISO/IEC 9899:2018 §6.7.2.1 "Structure and union specifiers" ¶18
> >
> > Signed-off-by: Vincent Mailhol <mailhol.vincent@wanadoo.fr>
> > ---
> >
> > I also tried to think of whether the current struct_size() macro could
> > be a security issue.
> >
> > The only example I can think of is if someone manually allocates the
> > exact size but then use the current struct_size() macro.
> >
> > For example (reusing the struct s from above):
> >
> >   u32 count = 5;
> >   struct s *s = kalloc(offsetof(typeof(*s), fam) + count);
> >   s->count = count;
> >   memset(s, 0, struct_size(s, fam, count)); /* 4 bytes buffer overflow */
> >
> > If we have concerns that above pattern may actually exist, then this
> > patch should also go to stable. I personally think that the above is a
> > bit convoluted and, as such, I only suggest this patch to go to next.
> > ---
> >  include/linux/overflow.h | 9 +++++++--
> >  1 file changed, 7 insertions(+), 2 deletions(-)
> >
> > diff --git a/include/linux/overflow.h b/include/linux/overflow.h
> > index 0c7e3dcfe867..1384887f3684 100644
> > --- a/include/linux/overflow.h
> > +++ b/include/linux/overflow.h
> > @@ -5,6 +5,7 @@
> >  #include <linux/compiler.h>
> >  #include <linux/limits.h>
> >  #include <linux/const.h>
> > +#include <linux/minmax.h>
> >
> >  /*
> >   * We need to compute the minimum and maximum values representable in a given
> > @@ -369,8 +370,12 @@ static inline size_t __must_check size_sub(size_t minuend, size_t subtrahend)
> >   */
> >  #define struct_size(p, member, count)                                        \
> >       __builtin_choose_expr(__is_constexpr(count),                    \
> > -             sizeof(*(p)) + flex_array_size(p, member, count),       \
> > -             size_add(sizeof(*(p)), flex_array_size(p, member, count)))
> > +             MAX(sizeof(*(p)),                                       \
> > +                 offsetof(typeof(*(p)), member) +                    \
> > +                     flex_array_size(p, member, count)),             \
> > +             max_t(size_t, sizeof(*(p)),                             \
> > +                   size_add(offsetof(typeof(*(p)), member),          \
> > +                            flex_array_size(p, member, count))))
>
> I don't think you need max_t() here, a plain max() should suffice.

Ack. I will send a v2 with max() instead of max_t().


Yours sincerely,
Vincent Mailhol
diff mbox series

Patch

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 0c7e3dcfe867..1384887f3684 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -5,6 +5,7 @@ 
 #include <linux/compiler.h>
 #include <linux/limits.h>
 #include <linux/const.h>
+#include <linux/minmax.h>
 
 /*
  * We need to compute the minimum and maximum values representable in a given
@@ -369,8 +370,12 @@  static inline size_t __must_check size_sub(size_t minuend, size_t subtrahend)
  */
 #define struct_size(p, member, count)					\
 	__builtin_choose_expr(__is_constexpr(count),			\
-		sizeof(*(p)) + flex_array_size(p, member, count),	\
-		size_add(sizeof(*(p)), flex_array_size(p, member, count)))
+		MAX(sizeof(*(p)),					\
+		    offsetof(typeof(*(p)), member) +			\
+			flex_array_size(p, member, count)),		\
+		max_t(size_t, sizeof(*(p)),				\
+		      size_add(offsetof(typeof(*(p)), member),		\
+			       flex_array_size(p, member, count))))
 
 /**
  * struct_size_t() - Calculate size of structure with trailing flexible array