struct_size() using sizeof() vs offsetof()
Hi Kees, Gustavo,
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.
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)
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.
So, I just wanted to pry what and especially why the kernel chose to prefer a simple sizeof().
Cheers,
Alex
---
$ cat off.c #include <err.h> #include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <string.h>
struct s {
int i;
char c;
char fam[];
};static inline void *xmalloc(size_t size);
int
main(void)
{
char *p;
struct s *s;
printf("sizeof: %zu\n", sizeof(struct s));
printf("offsetof: %zu\n", offsetof(struct s, fam));
puts("\nWith sizeof():");
s = xmalloc(sizeof(struct s) + sizeof("Hello, sizeof!"));
strcpy(s->fam, "Hello, sizeof!");
p = (char *) s + sizeof(struct s);
puts(p);
free(s);
puts("\nWith offsetof(3):");
s = xmalloc(offsetof(struct s, fam) + sizeof("Hello, offsetof!"));
strcpy(s->fam, "Hello, offsetof!");
p = (char *) s + offsetof(struct s, fam);
puts(p);
free(s);
exit(EXIT_SUCCESS);
}static inline void *xmalloc(size_t size)
{
void *p;
p = malloc(size);
if (p == NULL)
err(EXIT_FAILURE, "malloc");
return p;
}$ ./a.out sizeof: 8 offsetof: 5
With sizeof():
lo, sizeof!
With offsetof(3):
Hello, offsetof!
[1]: <https://gustedt.wordpress.com/2011/03/14/flexible-array-member/>
Signature · 2 lines
<http://www.alejandro-colomar.es/> GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5
Quoted 1 line · Alejandro Colomar
Hi Kees, Gustavo,
Hi!
Quoted 7 lines
I've been discussing with a friend about the appropriateness of
sizeof()vsoffsetof()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.
Quoted 7 lines
But then, said friend pointed to me that the kernel uses
sizeof()instruct_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.
Quoted 4 lines
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.
Quoted 2 lines
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
Signature · 1 line
Kees Cook
Hi!
Quoted 1 line · Kees Cook
On Thu, Aug 17, 2023 at 02:23:21AM +0200, Alejandro Colomar wrote:
[...]
Quoted 10 lines
When
struct_size()was originally implemented this topic came up, and we opted for potential over-estimation rather than usingoffsetof()which could result in under-allocation, and usingmax()of two different calculations just seemed like overkill. Additionally, almost all cases ofstruct_size()was replacing a literal open-coded version ofsizeof(*ptr) + sizeof(*ptr->array) * countSo avoiding a difference in calculation was nice too.
Yup.
[...]
Quoted 7 lines
Quoted 2 lines
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_byattribute.
Heh, I've found that there are actually a lot of discussions about flex arrays going on this summer. Glibc also has something.
[...]
Quoted 5 lines
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.
[...]
Quoted 10 lines
But, yes, at the end of the day,
struct_size()could be defined asmax(sizeof, offsetof-based struct-size).Note that
struct_size()has been designed to have two additional behaviors:
- be usable as a constant expression
- saturate atSIZE_MAXSo 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.
Quoted 2 lines
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
Quoted 5 lines
-Kees
[1] https://gcc.gnu.org/pipermail/gcc-patches/2023-August/626672.html
Signature · 2 lines
<http://www.alejandro-colomar.es/> GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5
Review
Quoted 3 lines
(quoted diff) +1
-1- 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/
Hi Gustavo,
Quoted 7 lines · Gustavo A. R. Silva
Review
Quoted 3 lines
(quoted diff) +1
-1- 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! :)
:-)
Quoted 4 lines
--
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
Signature · 2 lines
<http://www.alejandro-colomar.es/> GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5
From: Alejandro Colomar <[email protected]>
Quoted 12 lines
Sent: Thursday, August 17, 2023 7:38 PM
Hi Gustavo,
Quoted 7 lines · Gustavo A. R. Silva
Review
Quoted 3 lines
(quoted diff) +1
-1- 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)
Quoted 10 lines · David Laight
From: Alejandro Colomar <[email protected]>
Quoted 9 lines
Sent: Thursday, August 17, 2023 7:38 PM
Hi Gustavo,
Quoted 4 lines · Gustavo A. R. Silva
Quoted 3 lines
(quoted diff) +1
-1- tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL); + tp_c = kzalloc(struct_size(tp_c, hlist->ht, 1), GFP_KERNEL);
Quoted 7 lines
Quoted 3 lines
Quoted 3 lines
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.
Quoted 2 lines
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.
Quoted 5 lines
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
Quoted 6 lines
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Signature · 2 lines
<http://www.alejandro-colomar.es/> GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5
From: Alejandro Colomar
Quoted 32 lines
Sent: Thursday, August 17, 2023 1:23 AM
Hi Kees, Gustavo,
I've been discussing with a friend about the appropriateness of
sizeof()vsoffsetof()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.But then, said friend pointed to me that the kernel uses
sizeof()instruct_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)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.So, I just wanted to pry what and especially why the kernel chose to prefer a simple
sizeof().Cheers,
Alex---
.....
Quoted 3 lines
strcpy(s->fam, "Hello, sizeof!"); p = (char *) s + sizeof(struct s); puts(p);
Why on earth would you expect the above to do anything sensible?
It is a shame you can just use offsetof(type, member[count + 1]). That is fine for constants, but the C language requires offsetof() to be a compile-time constant - I can't help feeling the standards body didn't consider non-constant array offsets.
(The compiler for a well known OS won't compile that (or anything that looks like it) even for a constant array subscript!)
The actual problem with using offsetof() is that you might end up with something smaller than the structure size. (When the variable sized array is smaller than the padding.)
While max() will generate a constant for constant input, it will be a real compare for non-constant input.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Hi David,
Quoted 8 lines · David Laight
From: Alejandro Colomar
Quoted 5 lines
Sent: Thursday, August 17, 2023 1:23 AM
strcpy(s->fam, "Hello, sizeof!"); p = (char *) s + sizeof(struct s); puts(p);Why on earth would you expect the above to do anything sensible?
This trivial example may seem unreasonable, but I've seen code that does something like that (but more complex). Not in the kernel, but in an nginx subproject:
<https://github.com/nginx/unit/blob/47ff51009fa05d83bb67cd5db16829ab4c0081d7/src/wasm/nxt_wasm.c#L108>
<https://github.com/nginx/unit/blob/47ff51009fa05d83bb67cd5db16829ab4c0081d7/src/wasm/nxt_wasm.c#L160>
It uses pointer arithmetic with sizeof to get the offset of the FAM, instead of calling it by its name.
Quoted 5 lines
It is a shame you can just use
offsetof(type, member[count + 1]). That is fine for constants, but the C language requiresoffsetof()to be a compile-time constant - I can't help feeling the standards body didn't consider non-constant array offsets.
This helped catch a bug last week, so I think it's good that the standard disallows it.
You can always write a macro offsetof_fam(type, fam, n) which does that. In fact, I've written it, and will be part of the patch that I'll propose. It is much safer than if offsetof() would just accept that, as I can embed some static assertions within that macro.
Here's a look at the file I've been testing before submitting a patch. A lot of what you'll see here is similar to what I pretend to send in a patch.
$ cat alx_cdefs.h /* Copyright (C) 2023 Alejandro Colomar <[email protected]> */ /* SPDX-License-Identifier: GPL-3.0-or-later */
#ifndef ALX_CDEFS_H_INCLUDED_
#define ALX_CDEFS_H_INCLUDED_
#include <stddef.h>
#include <sys/param.h>
#define sizeof_array(a) (sizeof(a) + must_be_array(a))
#define nitems(a) (sizeof_array(a) / sizeof((a)[0]))
#define memberof(T, member) ((T){}.member)#define sizeof_incomplete(x) \
( \
sizeof( \
struct { \
max_align_t a; \
typeof(x) inc; \
} \
) \
- sizeof(max_align_t) \)
#define sizeof_fam0(T, fam) (sizeof(memberof(T, fam[0])) + must_be_fam(T, fam))
#define sizeof_fam(T, fam, n) (sizeof_fam0(T, fam) * (n)) #define offsetof_fam(T, fam, n) (offsetof(T, fam) + sizeof_fam(T, fam, n)) #define sizeof_struct(T, fam, n) MAX(sizeof(T), offsetof_fam(T, fam, n))
#define is_zero_sizeof(z) (sizeof_incomplete(z) == 0) #define is_same_type(a, b) __builtin_types_compatible_p(a, b) #define is_same_typeof(a, b) is_same_type(typeof(a), typeof(b)) #define is_array(a) (!is_same_typeof(a, &(a)[0]))
#define must_be(e) \
( \
0 * (int) sizeof( \
struct { \
_Static_assert(e, ""); \
int ISO_C_forbids_a_struct_with_no_members_; \
} \
) \)
#define must_be_array(a) must_be(is_array(a))
#define must_be_zero_sizeof(z) must_be(is_zero_sizeof(z))
#define must_be_fam(T, fam) \
(must_be_array(memberof(T, fam)) + must_be_zero_sizeof(memberof(T, fam)))
#endif /* ALX_CDEFS_H_INCLUDED_ */
Quoted 6 lines
(The compiler for a well known OS won't compile that (or anything that looks like it) even for a constant array subscript!)
The actual problem with using
offsetof()is that you might end up with something smaller than the structure size. (When the variable sized array is smaller than the padding.)
That's why MAX().
Quoted 3 lines
While
max()will generate a constant for constant input, it will be a real compare for non-constant input.
If the input was non-constant, then it would already have been non-constant with the current code. I don't think MAX() will make it worse.
Quoted 2 lines
David
Cheers,
Alex
Signature · 2 lines
<http://www.alejandro-colomar.es/> GPG key fingerprint: A9348594CE31283A826FBDD8D57633D441E25BB5