Round up allocations with kmalloc_size_roundup() so that the verifier's
use of ksize() is always accurate and no special handling of the memory
is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size
information back up to callers so they can use the space immediately,
so array resizing to happen less frequently as well.
Cc: Alexei Starovoitov <[email protected]>
Cc: Daniel Borkmann <[email protected]>
Cc: John Fastabend <[email protected]>
Cc: Andrii Nakryiko <[email protected]>
Cc: Martin KaFai Lau <[email protected]>
Cc: Song Liu <[email protected]>
Cc: Yonghong Song <[email protected]>
Cc: KP Singh <[email protected]>
Cc: Stanislav Fomichev <[email protected]>
Cc: Hao Luo <[email protected]>
Cc: Jiri Olsa <[email protected]>
Cc: [email protected]
Signed-off-by: Kees Cook <[email protected]>
---
kernel/bpf/verifier.c | 12 ++++++++----
1 file changed, 8 insertions(+), 4 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index eb8c34db74c7..1c040d27b8f6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1008,9 +1008,9 @@ static void *copy_array(void *dst, const void *src, size_t n, size_t size, gfp_t
if (unlikely(check_mul_overflow(n, size, &bytes)))
return NULL;
- if (ksize(dst) < bytes) {
+ if (ksize(dst) < ksize(src)) {
kfree(dst);
- dst = kmalloc_track_caller(bytes, flags);
+ dst = kmalloc_track_caller(kmalloc_size_roundup(bytes), flags);
if (!dst)
return NULL;
}
@@ -1027,12 +1027,14 @@ static void *copy_array(void *dst, const void *src, size_t n, size_t size, gfp_t
*/
static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
{
+ size_t alloc_size;
void *new_arr;
if (!new_n || old_n == new_n)
goto out;
- new_arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
+ alloc_size = kmalloc_size_roundup(size_mul(new_n, size));
+ new_arr = krealloc(arr, alloc_size, GFP_KERNEL);
if (!new_arr) {
kfree(arr);
return NULL;
@@ -2504,9 +2506,11 @@ static int push_jmp_history(struct bpf_verifier_env *env,
{
u32 cnt = cur->jmp_history_cnt;
struct bpf_idx_pair *p;
+ size_t alloc_size;
cnt++;
- p = krealloc(cur->jmp_history, cnt * sizeof(*p), GFP_USER);
+ alloc_size = kmalloc_size_roundup(size_mul(cnt, sizeof(*p)));
+ p = krealloc(cur->jmp_history, alloc_size, GFP_USER);
if (!p)
return -ENOMEM;
p[cnt - 1].idx = env->insn_idx;
--
2.34.1
On 10/29/22 4:54 AM, Kees Cook wrote:
> Round up allocations with kmalloc_size_roundup() so that the verifier's
> use of ksize() is always accurate and no special handling of the memory
> is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size
> information back up to callers so they can use the space immediately,
> so array resizing to happen less frequently as well.
>
[...]
The commit message is a bit cryptic here without further context. Is this
a bug fix or improvement? I read the latter, but it would be good to have
more context here for reviewers (maybe Link tag pointing to some discussion
or the like). Also, why is the kmalloc_size_roundup() not hidden for kmalloc
callers, isn't this a tree-wide issue?
Thanks,
Daniel
> kernel/bpf/verifier.c | 12 ++++++++----
> 1 file changed, 8 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index eb8c34db74c7..1c040d27b8f6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1008,9 +1008,9 @@ static void *copy_array(void *dst, const void *src, size_t n, size_t size, gfp_t
> if (unlikely(check_mul_overflow(n, size, &bytes)))
> return NULL;
>
> - if (ksize(dst) < bytes) {
> + if (ksize(dst) < ksize(src)) {
> kfree(dst);
> - dst = kmalloc_track_caller(bytes, flags);
> + dst = kmalloc_track_caller(kmalloc_size_roundup(bytes), flags);
> if (!dst)
> return NULL;
> }
> @@ -1027,12 +1027,14 @@ static void *copy_array(void *dst, const void *src, size_t n, size_t size, gfp_t
> */
> static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
> {
> + size_t alloc_size;
> void *new_arr;
>
> if (!new_n || old_n == new_n)
> goto out;
>
> - new_arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
> + alloc_size = kmalloc_size_roundup(size_mul(new_n, size));
> + new_arr = krealloc(arr, alloc_size, GFP_KERNEL);
> if (!new_arr) {
> kfree(arr);
> return NULL;
> @@ -2504,9 +2506,11 @@ static int push_jmp_history(struct bpf_verifier_env *env,
> {
> u32 cnt = cur->jmp_history_cnt;
> struct bpf_idx_pair *p;
> + size_t alloc_size;
>
> cnt++;
> - p = krealloc(cur->jmp_history, cnt * sizeof(*p), GFP_USER);
> + alloc_size = kmalloc_size_roundup(size_mul(cnt, sizeof(*p)));
> + p = krealloc(cur->jmp_history, alloc_size, GFP_USER);
> if (!p)
> return -ENOMEM;
> p[cnt - 1].idx = env->insn_idx;
>
On Tue, Nov 01, 2022 at 02:52:16PM +0100, Daniel Borkmann wrote:
> On 10/29/22 4:54 AM, Kees Cook wrote:
> > Round up allocations with kmalloc_size_roundup() so that the verifier's
> > use of ksize() is always accurate and no special handling of the memory
> > is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size
> > information back up to callers so they can use the space immediately,
> > so array resizing to happen less frequently as well.
> >
> [...]
>
> The commit message is a bit cryptic here without further context. Is this
> a bug fix or improvement? I read the latter, but it would be good to have
It's an improvement -- e.g. it depends on the recently added
kmalloc_size_roundup() helper.
> more context here for reviewers (maybe Link tag pointing to some discussion
> or the like). Also, why is the kmalloc_size_roundup() not hidden for kmalloc
> callers, isn't this a tree-wide issue?
The main issue is that _most_ allocation callers want an explicitly sized
allocation (and not "more"), and that dynamic runtime analysis tools
(e.g. KASAN, UBSAN_BOUNDS, FORTIFY_SOURCE, etc) are looking for precise
bounds checking (i.e. not something that is rounded up). A tiny handful
of allocations were doing an implicit alloc/realloc loop that actually
depended on ksize(), and didn't actually always call realloc. This has
created a long series of bugs and problems over many years related to the
runtime bounds checking, so these callers are finally being adjusted to
_not_ depend on the ksize() side-effect, by doing one of several things:
- tracking the allocation size precisely and just never calling ksize()
at all[1].
- always calling realloc and not using ksize() at all. (This solution
ends up actually be a subset of the next solution.)
- using kmalloc_size_roundup() to explicitly round up the desired
allocation size immediately[2].
The bpf/verifier case is this another of this latter case.
Because some of the dynamic bounds checking depends on the size being an
_argument_ to an allocator function (i.e. see the __alloc_size attribute),
the ksize() users are rare, and it could waste local variables, it
was been deemed better to explicitly separate the rounding up from the
allocation itself[3].
Hopefully that helps clarify! :)
-Kees
[1] e.g.:
https://git.kernel.org/linus/712f210a457d
https://git.kernel.org/linus/72c08d9f4c72
[2] e.g.:
https://git.kernel.org/netdev/net-next/c/12d6c1d3a2ad
https://git.kernel.org/netdev/net-next/c/ab3f7828c979
https://git.kernel.org/netdev/net-next/c/d6dd508080a3
[3] https://lore.kernel.org/lkml/[email protected]/
--
Kees Cook