Re: struct_size() using sizeof() vs offsetof()

Re: struct_size() using sizeof() vs offsetof()

[Kees Cook]

On Thu, Aug 17, 2023 at 02:23:21AM +0200, Alejandro Colomar wrote:
> Hi Kees, Gustavo,

Hi!

> I've been discussing with a friend about the appropriateness of sizeof()
> vs offsetof() for calculating the size of a structure with a flexible
> array member (FAM).
> 
> After reading Jens Gustedt's blog post about it[1], we tried some tests,
> and we got some interesting results that discouraged me from using sizeof().
> See below.

When struct_size() was originally implemented this topic came up, and we
opted for potential over-estimation rather than using offsetof() which
could result in under-allocation, and using max() of two different
calculations just seemed like overkill. Additionally, almost all cases of
struct_size() was replacing a literal open-coded version of

	sizeof(*ptr) + sizeof(*ptr->array) * count

So avoiding a difference in calculation was nice too.

> But then, said friend pointed to me that the kernel uses sizeof() in
> struct_size(), and we wondered why you would have chosen it.  It's safe
> as long as you _know_ that there's no padding, or that the alignment of
> the FAM is as large as the padding (which you probably know in the kernel),
> but it seems safer to use
> 
> 	MAX(sizeof(s), offsetof(s, fam) + sizeof_member(s, fam) * count)

Ironically, this has been under careful examination recently by GCC[1]
too. Though that has mainly been looking at it from the perspective
of how __builtin_object_size() should behave in the face of the new
__counted_by attribute.

> The thing is, if there's any trailing padding in the struct, the FAM may
> overlap the padding, and the calculation with sizeof() will waste a few
> bytes, and if misused to get the location of the FAM, the problem will be
> bigger, as you'll get a wrong location.

Luckily, the _location_ of the FAM is well-defined by the compiler, so
that won't be a problem. However, yes, we can risk wasting some bytes.

> So, I just wanted to pry what and especially why the kernel chose to prefer
> a simple sizeof().

We opted for simple over complex, with the understanding that
over-allocation will be a relatively rare issue that will only waste
limited space (as opposed to potential under-allocation and risking
writing beyond the end of the region).

Here's some example I worked through:

https://godbolt.org/z/9aGjqon9v

But, yes, at the end of the day, struct_size() could be defined as
max(sizeof, offsetof-based struct-size).

Note that struct_size() has been designed to have two additional
behaviors:
 - be usable as a constant expression
 - saturate at SIZE_MAX

So as long as the max() could do the same (which it should be able to),
it'd likely be fine. I'm open to patches as long as we can validate any
binary differences found in allmodconfig builds. :)

-Kees

[1] https://gcc.gnu.org/pipermail/gcc-patches/2023-August/626672.html

-- 
Kees Cook

Re: struct_size() using sizeof() vs offsetof()

[Alejandro Colomar]

[-- Attachment #1.1: Type: text/plain, Size: 5937 bytes --]

Hi!

On 2023-08-17 05:05, Kees Cook wrote:
> On Thu, Aug 17, 2023 at 02:23:21AM +0200, Alejandro Colomar wrote:
[...]

> 
> When struct_size() was originally implemented this topic came up, and we
> opted for potential over-estimation rather than using offsetof() which
> could result in under-allocation, and using max() of two different
> calculations just seemed like overkill. Additionally, almost all cases of
> struct_size() was replacing a literal open-coded version of
> 
> 	sizeof(*ptr) + sizeof(*ptr->array) * count
> 
> So avoiding a difference in calculation was nice too.

Yup.

[...]

>>
>> 	MAX(sizeof(s), offsetof(s, fam) + sizeof_member(s, fam) * count)
> 
> Ironically, this has been under careful examination recently by GCC[1]
> too. Though that has mainly been looking at it from the perspective
> of how __builtin_object_size() should behave in the face of the new
> __counted_by attribute.

Heh, I've found that there are actually a lot of discussions about flex
arrays going on this summer.  Glibc also has something.

[...]

> 
> We opted for simple over complex, with the understanding that
> over-allocation will be a relatively rare issue that will only waste
> limited space (as opposed to potential under-allocation and risking
> writing beyond the end of the region).

Thanks.

[...]

> But, yes, at the end of the day, struct_size() could be defined as
> max(sizeof, offsetof-based struct-size).
> 
> Note that struct_size() has been designed to have two additional
> behaviors:
>  - be usable as a constant expression
>  - saturate at SIZE_MAX
> 
> So as long as the max() could do the same (which it should be able to),
> it'd likely be fine.

Yep.  It should be able to do that.

> I'm open to patches as long as we can validate any
> binary differences found in allmodconfig builds. :)

Thanks!  I'm preparing a patch.  It's being more complex than I thought
it would be.  There's some thing that's not compiling for me.


net/sched/cls_u32.c: In function ‘u32_init’:
net/sched/cls_u32.c:369:17: error: cannot apply ‘offsetof’ to a non constant address
  369 |                 tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);
      |                 ^~~~
In file included from ./include/linux/kernel.h:27,
                 from ./arch/x86/include/asm/percpu.h:27,
                 from ./arch/x86/include/asm/nospec-branch.h:14,
                 from ./arch/x86/include/asm/paravirt_types.h:27,
                 from ./arch/x86/include/asm/ptrace.h:97,
                 from ./arch/x86/include/asm/math_emu.h:5,
                 from ./arch/x86/include/asm/processor.h:13,
                 from ./arch/x86/include/asm/timex.h:5,
                 from ./include/linux/timex.h:67,
                 from ./include/linux/time32.h:13,
                 from ./include/linux/time.h:60,
                 from ./include/linux/stat.h:19,
                 from ./include/linux/module.h:13,
                 from net/sched/cls_u32.c:26:


Here's the entire function:

$ grepc u32_init
./net/sched/cls_u32.c:352:
static int u32_init(struct tcf_proto *tp)
{
	struct tc_u_hnode *root_ht;
	void *key = tc_u_common_ptr(tp);
	struct tc_u_common *tp_c = tc_u_common_find(key);

	root_ht = kzalloc(struct_size(root_ht, ht, 1), GFP_KERNEL);
	if (root_ht == NULL)
		return -ENOBUFS;

	root_ht->refcnt++;
	root_ht->handle = tp_c ? gen_new_htid(tp_c, root_ht) : 0x80000000;
	root_ht->prio = tp->prio;
	root_ht->is_root = true;
	idr_init(&root_ht->handle_idr);

	if (tp_c == NULL) {
		tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);
		if (tp_c == NULL) {
			kfree(root_ht);
			return -ENOBUFS;
		}
		tp_c->ptr = key;
		INIT_HLIST_NODE(&tp_c->hnode);
		idr_init(&tp_c->handle_idr);

		hlist_add_head(&tp_c->hnode, tc_u_hash(key));
	}

	tp_c->refcnt++;
	RCU_INIT_POINTER(root_ht->next, tp_c->hlist);
	rcu_assign_pointer(tp_c->hlist, root_ht);

	root_ht->refcnt++;
	rcu_assign_pointer(tp->root, root_ht);
	tp->data = tp_c;
	return 0;
}


Let's see the structure type:


$ grepc -tt tc_u_common
./net/sched/cls_u32.c:86:
struct tc_u_common {
	struct tc_u_hnode __rcu	*hlist;
	void			*ptr;
	int			refcnt;
	struct idr		handle_idr;
	struct hlist_node	hnode;
	long			knodes;
};


Huh, hlist is the first field and is a pointer.  I'm not at all
sure of what was being done here.  Here's the type of the
pointee:


$ grepc -tt tc_u_hnode
./net/sched/cls_u32.c:70:
struct tc_u_hnode {
	struct tc_u_hnode __rcu	*next;
	u32			handle;
	u32			prio;
	int			refcnt;
	unsigned int		divisor;
	struct idr		handle_idr;
	bool			is_root;
	struct rcu_head		rcu;
	u32			flags;
	/* The 'ht' field MUST be the last field in structure to allow for
	 * more entries allocated at end of structure.
	 */
	struct tc_u_knode __rcu	*ht[];
};


So, that struct_size() was, at best, doing black magic.  At worst, a
bug.  I would need to investigate that code a little bit more, but a
first guess tells me that struct_size() was returning the size of the
outer structure plus the size of the flex array in the inner structure,
but not including the size of the inner structure; i.e.:

	sizeof(outer) + flex_array_size(inner-flex)

which seems a weird calcualtion.

That line of code was written by Gustavo, in d61491a51f7e ("net/sched:
cls_u32: Replace one-element array with flexible-array member"), so
can you please confirm that code, and maybe explain why it's that way,
Gustavo?

-               tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
+               tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);


Cheers,
Alex


> 
> -Kees
> 
> [1] https://gcc.gnu.org/pipermail/gcc-patches/2023-August/626672.html
> 

-- 
<http://www.alejandro-colomar.es/>
GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: struct_size() using sizeof() vs offsetof()

[Gustavo A. R. Silva]

> -               tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
> +               tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);

I just sent a fix[1].

Thanks for reporting this! :)
--
Gustavo

[1] https://lore.kernel.org/linux-hardening/ZN5DvRyq6JNz20l1@work/

Re: struct_size() using sizeof() vs offsetof()

[Alejandro Colomar]

[-- Attachment #1.1: Type: text/plain, Size: 618 bytes --]

Hi Gustavo,

On 2023-08-17 18:05, Gustavo A. R. Silva wrote:
> 
>> -               tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
>> +               tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);
> 
> I just sent a fix[1].
> 
> Thanks for reporting this! :)

:-)

> --
> Gustavo
> 
> [1] https://lore.kernel.org/linux-hardening/ZN5DvRyq6JNz20l1@work/

Please CC me in that thread.  I want to know when the patch is installed, to
prepare my own against that tree.

Cheers,
Alex

-- 
<http://www.alejandro-colomar.es/>
GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

RE: struct_size() using sizeof() vs offsetof()

[David Laight]

From: Alejandro Colomar <alx@kernel.org>
> Sent: Thursday, August 17, 2023 7:38 PM
> 
> Hi Gustavo,
> 
> On 2023-08-17 18:05, Gustavo A. R. Silva wrote:
> >
> >> -               tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
> >> +               tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);
> >
> > I just sent a fix[1].
> >
> > Thanks for reporting this! :)

Perhaps struct_size() should include an assertion that:
	(offsetof(type, field[8]) > sizeof (type))
That will ensure that field is an array member and reasonably
near the end of the structure.

A more complex calculation (using _Alignof(type) and the offset/size
of field) could be used.
But I don't think you can actually detect it is field[] (or even the
last member).

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: struct_size() using sizeof() vs offsetof()

[Alejandro Colomar]

On 2023-08-21 10:38, David Laight wrote:
> From: Alejandro Colomar <alx@kernel.org>
>> Sent: Thursday, August 17, 2023 7:38 PM
>>
>> Hi Gustavo,
>>
>> On 2023-08-17 18:05, Gustavo A. R. Silva wrote:
>>>
>>>> -               tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
>>>> +               tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);
>>>
>>> I just sent a fix[1].
>>>
>>> Thanks for reporting this! :)
> 
> Perhaps struct_size() should include an assertion that:
> 	(offsetof(type, field[8]) > sizeof (type))
> That will ensure that field is an array member

There's already an assertion that the field in struct_size() is an
array:

$ grepc struct_size include/
include/linux/overflow.h:291:
#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)))
$ grepc flex_array_size include/
include/linux/overflow.h:275:
#define flex_array_size(p, member, count)				\
	__builtin_choose_expr(__is_constexpr(count),			\
		(count) * sizeof(*(p)->member) + __must_be_array((p)->member),	\
		size_mul(count, sizeof(*(p)->member) + __must_be_array((p)->member)))


Notice the must_be_array() there.


> and reasonably
> near the end of the structure.

I did add a must_be_zero_sizeof() assertion to my implementation of
sizeof_fam0(), so I think that's a reasonable assertion that it's
really a FAM.  You can still add a zero-length array in the middle
of a struct and pass those two assertions, but it's unlikely.

> 
> A more complex calculation (using _Alignof(type) and the offset/size
> of field) could be used.
> But I don't think you can actually detect it is field[] (or even the
> last member).

I'm thinking now that you can plug an assertion that offsetof_fam()
is >= sizeof(struct) - alignof(struct).  That should make it even
harder to pass all the assertions without really having the field at
the end.  A [0] at the end of a structure would still pass all those
assertions, but linters probably catch those.  So I think it's a
pretty robust assertion.

Cheers,
Alex

> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)

-- 
<http://www.alejandro-colomar.es/>
GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5