[PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

Syzbot found a Use After Free bug in compute_effective_progs().
The reproducer creates a number of BPF links, and causes a fault
injected alloc to fail, while calling bpf_link_detach on them.
Link detach triggers the link to be freed by bpf_link_free(),
which calls __cgroup_bpf_detach() and update_effective_progs().
If the memory allocation in this function fails, the function restores
the pointer to the bpf_cgroup_link on the cgroup list, but the memory
gets freed just after it returns. After this, every subsequent call to
update_effective_progs() causes this already deallocated pointer to be
dereferenced in prog_list_length(), and triggers KASAN UAF error.
To fix this don't preserve the pointer to the link on the cgroup list
in __cgroup_bpf_detach(), but proceed with the cleanup and retry calling
update_effective_progs() again afterwards.


Cc: "Alexei Starovoitov" <ast@kernel.org>
Cc: "Daniel Borkmann" <daniel@iogearbox.net>
Cc: "Andrii Nakryiko" <andrii@kernel.org>
Cc: "Martin KaFai Lau" <kafai@fb.com>
Cc: "Song Liu" <songliubraving@fb.com>
Cc: "Yonghong Song" <yhs@fb.com>
Cc: "John Fastabend" <john.fastabend@gmail.com>
Cc: "KP Singh" <kpsingh@kernel.org>
Cc: <netdev@vger.kernel.org>
Cc: <bpf@vger.kernel.org>
Cc: <stable@vger.kernel.org>
Cc: <linux-kernel@vger.kernel.org>

Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
---
 kernel/bpf/cgroup.c | 25 ++++++++++++++-----------
 1 file changed, 14 insertions(+), 11 deletions(-)

diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
index 128028efda64..b6307337a3c7 100644
--- a/kernel/bpf/cgroup.c
+++ b/kernel/bpf/cgroup.c
@@ -723,10 +723,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 	pl->link = NULL;
 
 	err = update_effective_progs(cgrp, atype);
-	if (err)
-		goto cleanup;
-
-	/* now can actually delete it from this cgroup list */
+	/*
+	 * Proceed regardless of error. The link and/or prog will be freed
+	 * just after this function returns so just delete it from this
+	 * cgroup list and retry calling update_effective_progs again later.
+	 */
 	list_del(&pl->node);
 	kfree(pl);
 	if (list_empty(progs))
@@ -735,12 +736,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 	if (old_prog)
 		bpf_prog_put(old_prog);
 	static_branch_dec(&cgroup_bpf_enabled_key[atype]);
-	return 0;
 
-cleanup:
-	/* restore back prog or link */
-	pl->prog = old_prog;
-	pl->link = link;
+	/* In case of error call update_effective_progs again */
+	if (err)
+		err = update_effective_progs(cgrp, atype);
+
 	return err;
 }
 
@@ -881,6 +881,7 @@ static void bpf_cgroup_link_release(struct bpf_link *link)
 	struct bpf_cgroup_link *cg_link =
 		container_of(link, struct bpf_cgroup_link, link);
 	struct cgroup *cg;
+	int err;
 
 	/* link might have been auto-detached by dying cgroup already,
 	 * in that case our work is done here
@@ -896,8 +897,10 @@ static void bpf_cgroup_link_release(struct bpf_link *link)
 		return;
 	}
 
-	WARN_ON(__cgroup_bpf_detach(cg_link->cgroup, NULL, cg_link,
-				    cg_link->type));
+	err = __cgroup_bpf_detach(cg_link->cgroup, NULL, cg_link,
+				  cg_link->type);
+	if (err)
+		pr_warn("cgroup_bpf_detach() failed, err %d\n", err);
 
 	cg = cg_link->cgroup;
 	cg_link->cgroup = NULL;
-- 
2.35.1

Re: [PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

On 4/5/22 10:03, Tadeusz Struk wrote:
> Syzbot found a Use After Free bug in compute_effective_progs().
> The reproducer creates a number of BPF links, and causes a fault
> injected alloc to fail, while calling bpf_link_detach on them.
> Link detach triggers the link to be freed by bpf_link_free(),
> which calls __cgroup_bpf_detach() and update_effective_progs().
> If the memory allocation in this function fails, the function restores
> the pointer to the bpf_cgroup_link on the cgroup list, but the memory
> gets freed just after it returns. After this, every subsequent call to
> update_effective_progs() causes this already deallocated pointer to be
> dereferenced in prog_list_length(), and triggers KASAN UAF error.
> To fix this don't preserve the pointer to the link on the cgroup list
> in __cgroup_bpf_detach(), but proceed with the cleanup and retry calling
> update_effective_progs() again afterwards.
> 
> 
> Cc: "Alexei Starovoitov" <ast@kernel.org>
> Cc: "Daniel Borkmann" <daniel@iogearbox.net>
> Cc: "Andrii Nakryiko" <andrii@kernel.org>
> Cc: "Martin KaFai Lau" <kafai@fb.com>
> Cc: "Song Liu" <songliubraving@fb.com>
> Cc: "Yonghong Song" <yhs@fb.com>
> Cc: "John Fastabend" <john.fastabend@gmail.com>
> Cc: "KP Singh" <kpsingh@kernel.org>
> Cc: <netdev@vger.kernel.org>
> Cc: <bpf@vger.kernel.org>
> Cc: <stable@vger.kernel.org>
> Cc: <linux-kernel@vger.kernel.org>
> 
> Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
> Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
> Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
> ---
>   kernel/bpf/cgroup.c | 25 ++++++++++++++-----------
>   1 file changed, 14 insertions(+), 11 deletions(-)
> 
> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> index 128028efda64..b6307337a3c7 100644
> --- a/kernel/bpf/cgroup.c
> +++ b/kernel/bpf/cgroup.c
> @@ -723,10 +723,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>   	pl->link = NULL;
>   
>   	err = update_effective_progs(cgrp, atype);
> -	if (err)
> -		goto cleanup;
> -
> -	/* now can actually delete it from this cgroup list */
> +	/*
> +	 * Proceed regardless of error. The link and/or prog will be freed
> +	 * just after this function returns so just delete it from this
> +	 * cgroup list and retry calling update_effective_progs again later.
> +	 */
>   	list_del(&pl->node);
>   	kfree(pl);
>   	if (list_empty(progs))
> @@ -735,12 +736,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>   	if (old_prog)
>   		bpf_prog_put(old_prog);
>   	static_branch_dec(&cgroup_bpf_enabled_key[atype]);
> -	return 0;
>   
> -cleanup:
> -	/* restore back prog or link */
> -	pl->prog = old_prog;
> -	pl->link = link;
> +	/* In case of error call update_effective_progs again */
> +	if (err)
> +		err = update_effective_progs(cgrp, atype);
> +
>   	return err;
>   }
>   
> @@ -881,6 +881,7 @@ static void bpf_cgroup_link_release(struct bpf_link *link)
>   	struct bpf_cgroup_link *cg_link =
>   		container_of(link, struct bpf_cgroup_link, link);
>   	struct cgroup *cg;
> +	int err;
>   
>   	/* link might have been auto-detached by dying cgroup already,
>   	 * in that case our work is done here
> @@ -896,8 +897,10 @@ static void bpf_cgroup_link_release(struct bpf_link *link)
>   		return;
>   	}
>   
> -	WARN_ON(__cgroup_bpf_detach(cg_link->cgroup, NULL, cg_link,
> -				    cg_link->type));
> +	err = __cgroup_bpf_detach(cg_link->cgroup, NULL, cg_link,
> +				  cg_link->type);
> +	if (err)
> +		pr_warn("cgroup_bpf_detach() failed, err %d\n", err);
>   
>   	cg = cg_link->cgroup;
>   	cg_link->cgroup = NULL;

Hi,
Any feedback/comments on this one?

-- 
Thanks,
Tadeusz

Re: [PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Tue, Apr 5, 2022 at 10:04 AM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> Syzbot found a Use After Free bug in compute_effective_progs().
> The reproducer creates a number of BPF links, and causes a fault
> injected alloc to fail, while calling bpf_link_detach on them.
> Link detach triggers the link to be freed by bpf_link_free(),
> which calls __cgroup_bpf_detach() and update_effective_progs().
> If the memory allocation in this function fails, the function restores
> the pointer to the bpf_cgroup_link on the cgroup list, but the memory
> gets freed just after it returns. After this, every subsequent call to
> update_effective_progs() causes this already deallocated pointer to be
> dereferenced in prog_list_length(), and triggers KASAN UAF error.
> To fix this don't preserve the pointer to the link on the cgroup list
> in __cgroup_bpf_detach(), but proceed with the cleanup and retry calling
> update_effective_progs() again afterwards.

I think it's still problematic. BPF link might have been the last one
that holds bpf_prog's refcnt, so when link is put, its prog can stay
there in effective_progs array(s) and will cause use-after-free
anyways.

It would be best to make sure that detach never fails. On detach
effective prog array can only shrink, so even if
update_effective_progs() fails to allocate memory, we should be able
to iterate and just replace that prog with NULL, as a fallback
strategy.

>
>
> Cc: "Alexei Starovoitov" <ast@kernel.org>
> Cc: "Daniel Borkmann" <daniel@iogearbox.net>
> Cc: "Andrii Nakryiko" <andrii@kernel.org>
> Cc: "Martin KaFai Lau" <kafai@fb.com>
> Cc: "Song Liu" <songliubraving@fb.com>
> Cc: "Yonghong Song" <yhs@fb.com>
> Cc: "John Fastabend" <john.fastabend@gmail.com>
> Cc: "KP Singh" <kpsingh@kernel.org>
> Cc: <netdev@vger.kernel.org>
> Cc: <bpf@vger.kernel.org>
> Cc: <stable@vger.kernel.org>
> Cc: <linux-kernel@vger.kernel.org>
>
> Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
> Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
> Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
> ---
>  kernel/bpf/cgroup.c | 25 ++++++++++++++-----------
>  1 file changed, 14 insertions(+), 11 deletions(-)
>
> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> index 128028efda64..b6307337a3c7 100644
> --- a/kernel/bpf/cgroup.c
> +++ b/kernel/bpf/cgroup.c
> @@ -723,10 +723,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>         pl->link = NULL;
>
>         err = update_effective_progs(cgrp, atype);
> -       if (err)
> -               goto cleanup;
> -
> -       /* now can actually delete it from this cgroup list */
> +       /*
> +        * Proceed regardless of error. The link and/or prog will be freed
> +        * just after this function returns so just delete it from this
> +        * cgroup list and retry calling update_effective_progs again later.
> +        */
>         list_del(&pl->node);
>         kfree(pl);
>         if (list_empty(progs))
> @@ -735,12 +736,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>         if (old_prog)
>                 bpf_prog_put(old_prog);
>         static_branch_dec(&cgroup_bpf_enabled_key[atype]);
> -       return 0;
>
> -cleanup:
> -       /* restore back prog or link */
> -       pl->prog = old_prog;
> -       pl->link = link;
> +       /* In case of error call update_effective_progs again */
> +       if (err)
> +               err = update_effective_progs(cgrp, atype);

there is no guarantee that this will now succeed, right? so it's more
like "let's try just in case we are lucky this time"?

> +
>         return err;
>  }
>
> @@ -881,6 +881,7 @@ static void bpf_cgroup_link_release(struct bpf_link *link)
>         struct bpf_cgroup_link *cg_link =
>                 container_of(link, struct bpf_cgroup_link, link);
>         struct cgroup *cg;
> +       int err;
>
>         /* link might have been auto-detached by dying cgroup already,
>          * in that case our work is done here
> @@ -896,8 +897,10 @@ static void bpf_cgroup_link_release(struct bpf_link *link)
>                 return;
>         }
>
> -       WARN_ON(__cgroup_bpf_detach(cg_link->cgroup, NULL, cg_link,
> -                                   cg_link->type));
> +       err = __cgroup_bpf_detach(cg_link->cgroup, NULL, cg_link,
> +                                 cg_link->type);
> +       if (err)
> +               pr_warn("cgroup_bpf_detach() failed, err %d\n", err);
>
>         cg = cg_link->cgroup;
>         cg_link->cgroup = NULL;
> --
> 2.35.1

Re: [PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

Hi Andrii,
On 4/12/22 21:34, Andrii Nakryiko wrote:
> On Tue, Apr 5, 2022 at 10:04 AM Tadeusz Struk<tadeusz.struk@linaro.org>  wrote:
>> Syzbot found a Use After Free bug in compute_effective_progs().
>> The reproducer creates a number of BPF links, and causes a fault
>> injected alloc to fail, while calling bpf_link_detach on them.
>> Link detach triggers the link to be freed by bpf_link_free(),
>> which calls __cgroup_bpf_detach() and update_effective_progs().
>> If the memory allocation in this function fails, the function restores
>> the pointer to the bpf_cgroup_link on the cgroup list, but the memory
>> gets freed just after it returns. After this, every subsequent call to
>> update_effective_progs() causes this already deallocated pointer to be
>> dereferenced in prog_list_length(), and triggers KASAN UAF error.
>> To fix this don't preserve the pointer to the link on the cgroup list
>> in __cgroup_bpf_detach(), but proceed with the cleanup and retry calling
>> update_effective_progs() again afterwards.
> I think it's still problematic. BPF link might have been the last one
> that holds bpf_prog's refcnt, so when link is put, its prog can stay
> there in effective_progs array(s) and will cause use-after-free
> anyways.
> 
> It would be best to make sure that detach never fails. On detach
> effective prog array can only shrink, so even if
> update_effective_progs() fails to allocate memory, we should be able
> to iterate and just replace that prog with NULL, as a fallback
> strategy.

it would be ideal if detach would never fail, but it would require some kind of 
prealloc, on attach maybe? Another option would be to minimize the probability
of failing by sending it gfp_t flags (GFP_NOIO | GFP_NOFS | __GFP_NOFAIL)?
Detach can really only fail if the kzalloc in compute_effective_progs() fails
so maybe doing something like bellow would help:

diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
index 128028efda64..5a47740c317b 100644
--- a/kernel/bpf/cgroup.c
+++ b/kernel/bpf/cgroup.c
@@ -226,7 +226,8 @@ static bool hierarchy_allows_attach(struct cgroup *cgrp,
   */
  static int compute_effective_progs(struct cgroup *cgrp,
  				   enum cgroup_bpf_attach_type atype,
-				   struct bpf_prog_array **array)
+				   struct bpf_prog_array **array,
+				   gfp_t flags)
  {
  	struct bpf_prog_array_item *item;
  	struct bpf_prog_array *progs;
@@ -241,7 +242,7 @@ static int compute_effective_progs(struct cgroup *cgrp,
  		p = cgroup_parent(p);
  	} while (p);

-	progs = bpf_prog_array_alloc(cnt, GFP_KERNEL);
+	progs = bpf_prog_array_alloc(cnt, flags);
  	if (!progs)
  		return -ENOMEM;

@@ -308,7 +309,7 @@ int cgroup_bpf_inherit(struct cgroup *cgrp)
  	INIT_LIST_HEAD(&cgrp->bpf.storages);

  	for (i = 0; i < NR; i++)
-		if (compute_effective_progs(cgrp, i, &arrays[i]))
+		if (compute_effective_progs(cgrp, i, &arrays[i], GFP_KERNEL))
  			goto cleanup;

  	for (i = 0; i < NR; i++)
@@ -328,7 +329,8 @@ int cgroup_bpf_inherit(struct cgroup *cgrp)
  }

  static int update_effective_progs(struct cgroup *cgrp,
-				  enum cgroup_bpf_attach_type atype)
+				  enum cgroup_bpf_attach_type atype,
+				  gfp_t flags)
  {
  	struct cgroup_subsys_state *css;
  	int err;
@@ -340,7 +342,8 @@ static int update_effective_progs(struct cgroup *cgrp,
  		if (percpu_ref_is_zero(&desc->bpf.refcnt))
  			continue;

-		err = compute_effective_progs(desc, atype, &desc->bpf.inactive);
+		err = compute_effective_progs(desc, atype, &desc->bpf.inactive,
+					      flags);
  		if (err)
  			goto cleanup;
  	}
@@ -499,7 +502,7 @@ static int __cgroup_bpf_attach(struct cgroup *cgrp,
  	bpf_cgroup_storages_assign(pl->storage, storage);
  	cgrp->bpf.flags[atype] = saved_flags;

-	err = update_effective_progs(cgrp, atype);
+	err = update_effective_progs(cgrp, atype, GFP_KERNEL);
  	if (err)
  		goto cleanup;

@@ -722,7 +725,7 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct 
bpf_prog *prog,
  	pl->prog = NULL;
  	pl->link = NULL;

-	err = update_effective_progs(cgrp, atype);
+	err = update_effective_progs(cgrp, atype, GFP_NOIO | GFP_NOFS | __GFP_NOFAIL);
  	if (err)
  		goto cleanup;

>> -cleanup:
>> -       /* restore back prog or link */
>> -       pl->prog = old_prog;
>> -       pl->link = link;
>> +       /* In case of error call update_effective_progs again */
>> +       if (err)
>> +               err = update_effective_progs(cgrp, atype);
> there is no guarantee that this will now succeed, right? so it's more
> like "let's try just in case we are lucky this time"?

Yes, there is no guarantee, but my thinking was that since we have freed some
memory (see kfree(pl) above) let's retry and see if it works this time.
If that is combined with the above gfp flags it is a good chance that it will
work. What do you think?

-- 
Thanks,
Tadeusz

Re: [PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Wed, Apr 13, 2022 at 10:28 AM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> Hi Andrii,
> On 4/12/22 21:34, Andrii Nakryiko wrote:
> > On Tue, Apr 5, 2022 at 10:04 AM Tadeusz Struk<tadeusz.struk@linaro.org>  wrote:
> >> Syzbot found a Use After Free bug in compute_effective_progs().
> >> The reproducer creates a number of BPF links, and causes a fault
> >> injected alloc to fail, while calling bpf_link_detach on them.
> >> Link detach triggers the link to be freed by bpf_link_free(),
> >> which calls __cgroup_bpf_detach() and update_effective_progs().
> >> If the memory allocation in this function fails, the function restores
> >> the pointer to the bpf_cgroup_link on the cgroup list, but the memory
> >> gets freed just after it returns. After this, every subsequent call to
> >> update_effective_progs() causes this already deallocated pointer to be
> >> dereferenced in prog_list_length(), and triggers KASAN UAF error.
> >> To fix this don't preserve the pointer to the link on the cgroup list
> >> in __cgroup_bpf_detach(), but proceed with the cleanup and retry calling
> >> update_effective_progs() again afterwards.
> > I think it's still problematic. BPF link might have been the last one
> > that holds bpf_prog's refcnt, so when link is put, its prog can stay
> > there in effective_progs array(s) and will cause use-after-free
> > anyways.
> >
> > It would be best to make sure that detach never fails. On detach
> > effective prog array can only shrink, so even if
> > update_effective_progs() fails to allocate memory, we should be able
> > to iterate and just replace that prog with NULL, as a fallback
> > strategy.
>
> it would be ideal if detach would never fail, but it would require some kind of
> prealloc, on attach maybe? Another option would be to minimize the probability

We allocate new arrays in update_effective_progs() under assumption
that we might need to grow the array because we use
update_effective_progs() for attachment. But for detachment we know
that we definitely don't need to increase the size, we need to remove
existing element only, thus shrinking the size.

Normally we'd reallocate the array to shrink it (and that's why we use
update_effective_progs() and allocate memory), but we can also have a
fallback path for detachment only to reuse existing effective arrays
and just shift all the elements to the right from the element that's
being removed. We'll leave NULL at the end, but that's much better
than error out. Subsequent attachment or detachment will attempt to
properly size and reallocate everything.

So I think that should be the fix, if you'd be willing to work on it.


> of failing by sending it gfp_t flags (GFP_NOIO | GFP_NOFS | __GFP_NOFAIL)?
> Detach can really only fail if the kzalloc in compute_effective_progs() fails
> so maybe doing something like bellow would help:
>
> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> index 128028efda64..5a47740c317b 100644
> --- a/kernel/bpf/cgroup.c
> +++ b/kernel/bpf/cgroup.c
> @@ -226,7 +226,8 @@ static bool hierarchy_allows_attach(struct cgroup *cgrp,
>    */
>   static int compute_effective_progs(struct cgroup *cgrp,
>                                    enum cgroup_bpf_attach_type atype,
> -                                  struct bpf_prog_array **array)
> +                                  struct bpf_prog_array **array,
> +                                  gfp_t flags)
>   {
>         struct bpf_prog_array_item *item;
>         struct bpf_prog_array *progs;
> @@ -241,7 +242,7 @@ static int compute_effective_progs(struct cgroup *cgrp,
>                 p = cgroup_parent(p);
>         } while (p);
>
> -       progs = bpf_prog_array_alloc(cnt, GFP_KERNEL);
> +       progs = bpf_prog_array_alloc(cnt, flags);
>         if (!progs)
>                 return -ENOMEM;
>
> @@ -308,7 +309,7 @@ int cgroup_bpf_inherit(struct cgroup *cgrp)
>         INIT_LIST_HEAD(&cgrp->bpf.storages);
>
>         for (i = 0; i < NR; i++)
> -               if (compute_effective_progs(cgrp, i, &arrays[i]))
> +               if (compute_effective_progs(cgrp, i, &arrays[i], GFP_KERNEL))
>                         goto cleanup;
>
>         for (i = 0; i < NR; i++)
> @@ -328,7 +329,8 @@ int cgroup_bpf_inherit(struct cgroup *cgrp)
>   }
>
>   static int update_effective_progs(struct cgroup *cgrp,
> -                                 enum cgroup_bpf_attach_type atype)
> +                                 enum cgroup_bpf_attach_type atype,
> +                                 gfp_t flags)
>   {
>         struct cgroup_subsys_state *css;
>         int err;
> @@ -340,7 +342,8 @@ static int update_effective_progs(struct cgroup *cgrp,
>                 if (percpu_ref_is_zero(&desc->bpf.refcnt))
>                         continue;
>
> -               err = compute_effective_progs(desc, atype, &desc->bpf.inactive);
> +               err = compute_effective_progs(desc, atype, &desc->bpf.inactive,
> +                                             flags);
>                 if (err)
>                         goto cleanup;
>         }
> @@ -499,7 +502,7 @@ static int __cgroup_bpf_attach(struct cgroup *cgrp,
>         bpf_cgroup_storages_assign(pl->storage, storage);
>         cgrp->bpf.flags[atype] = saved_flags;
>
> -       err = update_effective_progs(cgrp, atype);
> +       err = update_effective_progs(cgrp, atype, GFP_KERNEL);
>         if (err)
>                 goto cleanup;
>
> @@ -722,7 +725,7 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct
> bpf_prog *prog,
>         pl->prog = NULL;
>         pl->link = NULL;
>
> -       err = update_effective_progs(cgrp, atype);
> +       err = update_effective_progs(cgrp, atype, GFP_NOIO | GFP_NOFS | __GFP_NOFAIL);
>         if (err)
>                 goto cleanup;
>
> >> -cleanup:
> >> -       /* restore back prog or link */
> >> -       pl->prog = old_prog;
> >> -       pl->link = link;
> >> +       /* In case of error call update_effective_progs again */
> >> +       if (err)
> >> +               err = update_effective_progs(cgrp, atype);
> > there is no guarantee that this will now succeed, right? so it's more
> > like "let's try just in case we are lucky this time"?
>
> Yes, there is no guarantee, but my thinking was that since we have freed some
> memory (see kfree(pl) above) let's retry and see if it works this time.
> If that is combined with the above gfp flags it is a good chance that it will
> work. What do you think?
>

See above, instead of compensating for the update_effective_progs()
failure, we should make sure it never fails for detachment.


> --
> Thanks,
> Tadeusz

Re: [PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

On 4/13/22 12:07, Andrii Nakryiko wrote:
>> it would be ideal if detach would never fail, but it would require some kind of
>> prealloc, on attach maybe? Another option would be to minimize the probability
> We allocate new arrays in update_effective_progs() under assumption
> that we might need to grow the array because we use
> update_effective_progs() for attachment. But for detachment we know
> that we definitely don't need to increase the size, we need to remove
> existing element only, thus shrinking the size.
> 
> Normally we'd reallocate the array to shrink it (and that's why we use
> update_effective_progs() and allocate memory), but we can also have a
> fallback path for detachment only to reuse existing effective arrays
> and just shift all the elements to the right from the element that's
> being removed. We'll leave NULL at the end, but that's much better
> than error out. Subsequent attachment or detachment will attempt to
> properly size and reallocate everything.
> 
> So I think that should be the fix, if you'd be willing to work on it.

That makes it much easier then. I will change it so that there is no
alloc needed on the detach path. Thanks for the clarification.

-- 
Thanks,
Tadeusz

Re: [PATCH] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Wed, Apr 13, 2022 at 12:27 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> On 4/13/22 12:07, Andrii Nakryiko wrote:
> >> it would be ideal if detach would never fail, but it would require some kind of
> >> prealloc, on attach maybe? Another option would be to minimize the probability
> > We allocate new arrays in update_effective_progs() under assumption
> > that we might need to grow the array because we use
> > update_effective_progs() for attachment. But for detachment we know
> > that we definitely don't need to increase the size, we need to remove
> > existing element only, thus shrinking the size.
> >
> > Normally we'd reallocate the array to shrink it (and that's why we use
> > update_effective_progs() and allocate memory), but we can also have a
> > fallback path for detachment only to reuse existing effective arrays
> > and just shift all the elements to the right from the element that's
> > being removed. We'll leave NULL at the end, but that's much better
> > than error out. Subsequent attachment or detachment will attempt to
> > properly size and reallocate everything.
> >
> > So I think that should be the fix, if you'd be willing to work on it.
>
> That makes it much easier then. I will change it so that there is no
> alloc needed on the detach path. Thanks for the clarification.

Keep in mind that we probably want to do normal alloc-based detach
first anyways, if it works. It will keep effective arrays minimally
sized. This additional detach specific logic should be a fall back
path if the normal way doesn't work.

>
> --
> Thanks,
> Tadeusz

[PATCH v2] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

Syzbot found a Use After Free bug in compute_effective_progs().
The reproducer creates a number of BPF links, and causes a fault
injected alloc to fail, while calling bpf_link_detach on them.
Link detach triggers the link to be freed by bpf_link_free(),
which calls __cgroup_bpf_detach() and update_effective_progs().
If the memory allocation in this function fails, the function restores
the pointer to the bpf_cgroup_link on the cgroup list, but the memory
gets freed just after it returns. After this, every subsequent call to
update_effective_progs() causes this already deallocated pointer to be
dereferenced in prog_list_length(), and triggers KASAN UAF error.

To fix this issue don't preserve the pointer to the prog or link in the
list, but remove it and rearrange the effective table without
shrinking it. The subsequent call to __cgroup_bpf_detach() or
__cgroup_bpf_detach() will correct it.

Cc: "Alexei Starovoitov" <ast@kernel.org>
Cc: "Daniel Borkmann" <daniel@iogearbox.net>
Cc: "Andrii Nakryiko" <andrii@kernel.org>
Cc: "Martin KaFai Lau" <kafai@fb.com>
Cc: "Song Liu" <songliubraving@fb.com>
Cc: "Yonghong Song" <yhs@fb.com>
Cc: "John Fastabend" <john.fastabend@gmail.com>
Cc: "KP Singh" <kpsingh@kernel.org>
Cc: <netdev@vger.kernel.org>
Cc: <bpf@vger.kernel.org>
Cc: <stable@vger.kernel.org>
Cc: <linux-kernel@vger.kernel.org>

Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
---
v2: Add a fall back path that removes a prog from the effective progs
    table in case detach fails to allocate memory in compute_effective_progs().
---
 kernel/bpf/cgroup.c | 55 +++++++++++++++++++++++++++++++++++++++------
 1 file changed, 48 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
index 128028efda64..5a64cece09f3 100644
--- a/kernel/bpf/cgroup.c
+++ b/kernel/bpf/cgroup.c
@@ -723,10 +723,8 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 	pl->link = NULL;
 
 	err = update_effective_progs(cgrp, atype);
-	if (err)
-		goto cleanup;
 
-	/* now can actually delete it from this cgroup list */
+	/* now can delete it from this cgroup list */
 	list_del(&pl->node);
 	kfree(pl);
 	if (list_empty(progs))
@@ -735,12 +733,55 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 	if (old_prog)
 		bpf_prog_put(old_prog);
 	static_branch_dec(&cgroup_bpf_enabled_key[atype]);
-	return 0;
+
+	if (!err)
+		return 0;
 
 cleanup:
-	/* restore back prog or link */
-	pl->prog = old_prog;
-	pl->link = link;
+	/*
+	 * If compute_effective_progs failed with -ENOMEM, i.e. alloc for
+	 * cgrp->bpf.inactive table failed, we can recover by removing
+	 * the detached prog from effective table and rearranging it.
+	 */
+	if (err == -ENOMEM) {
+		struct bpf_prog_array_item *item;
+		struct bpf_prog *prog_tmp, *prog_detach, *prog_last;
+		struct bpf_prog_array *array;
+		int index = 0, index_detach = -1;
+
+		array = cgrp->bpf.effective[atype];
+		item = &array->items[0];
+
+		if (prog)
+			prog_detach = prog;
+		else
+			prog_detach = link->link.prog;
+
+		if (!prog_detach)
+			return -EINVAL;
+
+		while ((prog_tmp = READ_ONCE(item->prog))) {
+			if (prog_tmp == prog_detach)
+				index_detach = index;
+			item++;
+			index++;
+			prog_last = prog_tmp;
+		}
+
+		/* Check if we found what's needed for removing the prog */
+		if (index_detach == -1 || index_detach == index-1)
+			return -EINVAL;
+
+		/* Remove the last program in the array */
+		if (bpf_prog_array_delete_safe_at(array, index-1))
+			return -EINVAL;
+
+		/* and update the detached with the last just removed */
+		if (bpf_prog_array_update_at(array, index_detach, prog_last))
+			return -EINVAL;
+
+		err = 0;
+	}
 	return err;
 }
 
-- 
2.35.1

Re: [PATCH v2] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Fri, Apr 15, 2022 at 7:14 AM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> Syzbot found a Use After Free bug in compute_effective_progs().
> The reproducer creates a number of BPF links, and causes a fault
> injected alloc to fail, while calling bpf_link_detach on them.
> Link detach triggers the link to be freed by bpf_link_free(),
> which calls __cgroup_bpf_detach() and update_effective_progs().
> If the memory allocation in this function fails, the function restores
> the pointer to the bpf_cgroup_link on the cgroup list, but the memory
> gets freed just after it returns. After this, every subsequent call to
> update_effective_progs() causes this already deallocated pointer to be
> dereferenced in prog_list_length(), and triggers KASAN UAF error.
>
> To fix this issue don't preserve the pointer to the prog or link in the
> list, but remove it and rearrange the effective table without
> shrinking it. The subsequent call to __cgroup_bpf_detach() or
> __cgroup_bpf_detach() will correct it.
>
> Cc: "Alexei Starovoitov" <ast@kernel.org>
> Cc: "Daniel Borkmann" <daniel@iogearbox.net>
> Cc: "Andrii Nakryiko" <andrii@kernel.org>
> Cc: "Martin KaFai Lau" <kafai@fb.com>
> Cc: "Song Liu" <songliubraving@fb.com>
> Cc: "Yonghong Song" <yhs@fb.com>
> Cc: "John Fastabend" <john.fastabend@gmail.com>
> Cc: "KP Singh" <kpsingh@kernel.org>
> Cc: <netdev@vger.kernel.org>
> Cc: <bpf@vger.kernel.org>
> Cc: <stable@vger.kernel.org>
> Cc: <linux-kernel@vger.kernel.org>
>
> Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
> Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
> Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
> ---
> v2: Add a fall back path that removes a prog from the effective progs
>     table in case detach fails to allocate memory in compute_effective_progs().
> ---
>  kernel/bpf/cgroup.c | 55 +++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 48 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> index 128028efda64..5a64cece09f3 100644
> --- a/kernel/bpf/cgroup.c
> +++ b/kernel/bpf/cgroup.c
> @@ -723,10 +723,8 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>         pl->link = NULL;
>
>         err = update_effective_progs(cgrp, atype);
> -       if (err)
> -               goto cleanup;
>
> -       /* now can actually delete it from this cgroup list */
> +       /* now can delete it from this cgroup list */
>         list_del(&pl->node);
>         kfree(pl);
>         if (list_empty(progs))
> @@ -735,12 +733,55 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>         if (old_prog)
>                 bpf_prog_put(old_prog);
>         static_branch_dec(&cgroup_bpf_enabled_key[atype]);
> -       return 0;
> +
> +       if (!err)
> +               return 0;
>
>  cleanup:
> -       /* restore back prog or link */
> -       pl->prog = old_prog;
> -       pl->link = link;
> +       /*
> +        * If compute_effective_progs failed with -ENOMEM, i.e. alloc for
> +        * cgrp->bpf.inactive table failed, we can recover by removing
> +        * the detached prog from effective table and rearranging it.
> +        */
> +       if (err == -ENOMEM) {
> +               struct bpf_prog_array_item *item;
> +               struct bpf_prog *prog_tmp, *prog_detach, *prog_last;
> +               struct bpf_prog_array *array;
> +               int index = 0, index_detach = -1;
> +
> +               array = cgrp->bpf.effective[atype];
> +               item = &array->items[0];
> +
> +               if (prog)
> +                       prog_detach = prog;
> +               else
> +                       prog_detach = link->link.prog;
> +
> +               if (!prog_detach)
> +                       return -EINVAL;
> +
> +               while ((prog_tmp = READ_ONCE(item->prog))) {
> +                       if (prog_tmp == prog_detach)
> +                               index_detach = index;
> +                       item++;
> +                       index++;
> +                       prog_last = prog_tmp;
> +               }
> +
> +               /* Check if we found what's needed for removing the prog */
> +               if (index_detach == -1 || index_detach == index-1)
> +                       return -EINVAL;
> +
> +               /* Remove the last program in the array */
> +               if (bpf_prog_array_delete_safe_at(array, index-1))
> +                       return -EINVAL;
> +
> +               /* and update the detached with the last just removed */
> +               if (bpf_prog_array_update_at(array, index_detach, prog_last))
> +                       return -EINVAL;
> +
> +               err = 0;
> +       }

There are a bunch of problems with this implementation.

1. We should do this fallback right after update_effective_progs()
returns error, before we get to list_del(&pl->node) and subsequent
code that does some additional things (like clearing flags and stuff).
This additional code needs to run even if update_effective_progs()
fails. So I suggest to extract the logic of removing program from
effective prog arrays into a helper function and doing

err = update_effective_progs(...);
if (err)
    purge_effective_progs();

where purge_effective_progs() will be the logic you are adding. And it
will be void function because it can't fail.

2. We have to update not just cgrp->bpf.effective array, but all the
descendants' lists as well. See what update_effective_progs() is
doing, it has css_for_each_descendant_pre() iteration. You need to do
it here as well. But instead of doing compute_effective_progs() which
allocates a new copy of an array we'll need to update existing array
in place.

3. Not clear why you need to do both bpf_prog_array_delete_safe_at()
and bpf_prog_array_update_at(), isn't delete_safe_at() enought?


>         return err;
>  }
>
> --
> 2.35.1
>

Re: [PATCH v2] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

Hi Andrii,
On 4/20/22 10:07, Andrii Nakryiko wrote:
>> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
>> index 128028efda64..5a64cece09f3 100644
>> --- a/kernel/bpf/cgroup.c
>> +++ b/kernel/bpf/cgroup.c
>> @@ -723,10 +723,8 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>>          pl->link = NULL;
>>
>>          err = update_effective_progs(cgrp, atype);
>> -       if (err)
>> -               goto cleanup;
>>
>> -       /* now can actually delete it from this cgroup list */
>> +       /* now can delete it from this cgroup list */
>>          list_del(&pl->node);
>>          kfree(pl);
>>          if (list_empty(progs))
>> @@ -735,12 +733,55 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>>          if (old_prog)
>>                  bpf_prog_put(old_prog);
>>          static_branch_dec(&cgroup_bpf_enabled_key[atype]);
>> -       return 0;
>> +
>> +       if (!err)
>> +               return 0;
>>
>>   cleanup:
>> -       /* restore back prog or link */
>> -       pl->prog = old_prog;
>> -       pl->link = link;
>> +       /*
>> +        * If compute_effective_progs failed with -ENOMEM, i.e. alloc for
>> +        * cgrp->bpf.inactive table failed, we can recover by removing
>> +        * the detached prog from effective table and rearranging it.
>> +        */
>> +       if (err == -ENOMEM) {
>> +               struct bpf_prog_array_item *item;
>> +               struct bpf_prog *prog_tmp, *prog_detach, *prog_last;
>> +               struct bpf_prog_array *array;
>> +               int index = 0, index_detach = -1;
>> +
>> +               array = cgrp->bpf.effective[atype];
>> +               item = &array->items[0];
>> +
>> +               if (prog)
>> +                       prog_detach = prog;
>> +               else
>> +                       prog_detach = link->link.prog;
>> +
>> +               if (!prog_detach)
>> +                       return -EINVAL;
>> +
>> +               while ((prog_tmp = READ_ONCE(item->prog))) {
>> +                       if (prog_tmp == prog_detach)
>> +                               index_detach = index;
>> +                       item++;
>> +                       index++;
>> +                       prog_last = prog_tmp;
>> +               }
>> +
>> +               /* Check if we found what's needed for removing the prog */
>> +               if (index_detach == -1 || index_detach == index-1)
>> +                       return -EINVAL;
>> +
>> +               /* Remove the last program in the array */
>> +               if (bpf_prog_array_delete_safe_at(array, index-1))
>> +                       return -EINVAL;
>> +
>> +               /* and update the detached with the last just removed */
>> +               if (bpf_prog_array_update_at(array, index_detach, prog_last))
>> +                       return -EINVAL;
>> +
>> +               err = 0;
>> +       }

Thanks for feedback, and sorry for delay. I got pulled into something else.

> There are a bunch of problems with this implementation.
> 
> 1. We should do this fallback right after update_effective_progs()
> returns error, before we get to list_del(&pl->node) and subsequent
> code that does some additional things (like clearing flags and stuff).
> This additional code needs to run even if update_effective_progs()
> fails. So I suggest to extract the logic of removing program from
> effective prog arrays into a helper function and doing
> 
> err = update_effective_progs(...);
> if (err)
>      purge_effective_progs();
> 
> where purge_effective_progs() will be the logic you are adding. And it
> will be void function because it can't fail.

I have implemented that in v3, will send that out soon.

> 
> 2. We have to update not just cgrp->bpf.effective array, but all the
> descendants' lists as well. See what update_effective_progs() is
> doing, it has css_for_each_descendant_pre() iteration. You need to do
> it here as well. But instead of doing compute_effective_progs() which
> allocates a new copy of an array we'll need to update existing array
> in place.
> 
> 3. Not clear why you need to do both bpf_prog_array_delete_safe_at()
> and bpf_prog_array_update_at(), isn't delete_safe_at() enought?

I thought that we need to reshuffle the table and move the progs around,
but your are right, delete_safe_at() is enough.

-- 
Thanks,
Tadeusz

[PATCH v3] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

Syzbot found a Use After Free bug in compute_effective_progs().
The reproducer creates a number of BPF links, and causes a fault
injected alloc to fail, while calling bpf_link_detach on them.
Link detach triggers the link to be freed by bpf_link_free(),
which calls __cgroup_bpf_detach() and update_effective_progs().
If the memory allocation in this function fails, the function restores
the pointer to the bpf_cgroup_link on the cgroup list, but the memory
gets freed just after it returns. After this, every subsequent call to
update_effective_progs() causes this already deallocated pointer to be
dereferenced in prog_list_length(), and triggers KASAN UAF error.

To fix this issue don't preserve the pointer to the prog or link in the
list, but remove it and replace it with a dummy prog without shrinking
the table. The subsequent call to __cgroup_bpf_detach() or
__cgroup_bpf_detach() will correct it.

Cc: "Alexei Starovoitov" <ast@kernel.org>
Cc: "Daniel Borkmann" <daniel@iogearbox.net>
Cc: "Andrii Nakryiko" <andrii@kernel.org>
Cc: "Martin KaFai Lau" <kafai@fb.com>
Cc: "Song Liu" <songliubraving@fb.com>
Cc: "Yonghong Song" <yhs@fb.com>
Cc: "John Fastabend" <john.fastabend@gmail.com>
Cc: "KP Singh" <kpsingh@kernel.org>
Cc: <netdev@vger.kernel.org>
Cc: <bpf@vger.kernel.org>
Cc: <stable@vger.kernel.org>
Cc: <linux-kernel@vger.kernel.org>

Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
---
v2: Add a fall back path that removes a prog from the effective progs
    table in case detach fails to allocate memory in compute_effective_progs().

v3: Implement the fallback in a separate function purge_effective_progs
---
 kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------
 1 file changed, 56 insertions(+), 8 deletions(-)

diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
index 128028efda64..9d3af4d6c055 100644
--- a/kernel/bpf/cgroup.c
+++ b/kernel/bpf/cgroup.c
@@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs,
 	return ERR_PTR(-ENOENT);
 }
 
+/**
+ * purge_effective_progs() - After compute_effective_progs fails to alloc new
+ *                           cgrp->bpf.inactive table we can recover by
+ *                           recomputing the array in place.
+ *
+ * @cgrp: The cgroup which descendants to traverse
+ * @link: A link to detach
+ * @atype: Type of detach operation
+ */
+static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog,
+				  enum cgroup_bpf_attach_type atype)
+{
+	struct cgroup_subsys_state *css;
+	struct bpf_prog_array_item *item;
+	struct bpf_prog *tmp;
+	struct bpf_prog_array *array;
+	int index = 0, index_purge = -1;
+
+	if (!prog)
+		return;
+
+	/* recompute effective prog array in place */
+	css_for_each_descendant_pre(css, &cgrp->self) {
+		struct cgroup *desc = container_of(css, struct cgroup, self);
+
+		array = desc->bpf.effective[atype];
+		item = &array->items[0];
+
+		/* Find the index of the prog to purge */
+		while ((tmp = READ_ONCE(item->prog))) {
+			if (tmp == prog) {
+				index_purge = index;
+				break;
+			}
+			item++;
+			index++;
+		}
+
+		/* Check if we found what's needed for removing the prog */
+		if (index_purge == -1 || index_purge == index - 1)
+			continue;
+
+		/* Remove the program from the array */
+		WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge),
+			  "Failed to purge a prog from array at index %d", index_purge);
+
+		index = 0;
+		index_purge = -1;
+	}
+}
+
 /**
  * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and
  *                         propagate the change to descendants
@@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 	pl->link = NULL;
 
 	err = update_effective_progs(cgrp, atype);
-	if (err)
-		goto cleanup;
+	if (err) {
+		struct bpf_prog *prog_purge = prog ? prog : link->link.prog;
+
+		purge_effective_progs(cgrp, prog_purge, atype);
+	}
 
 	/* now can actually delete it from this cgroup list */
 	list_del(&pl->node);
@@ -736,12 +790,6 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 		bpf_prog_put(old_prog);
 	static_branch_dec(&cgroup_bpf_enabled_key[atype]);
 	return 0;
-
-cleanup:
-	/* restore back prog or link */
-	pl->prog = old_prog;
-	pl->link = link;
-	return err;
 }
 
 static int cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
-- 
2.36.1

Re: [PATCH v3] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Fri, May 13, 2022 at 12:08 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> Syzbot found a Use After Free bug in compute_effective_progs().
> The reproducer creates a number of BPF links, and causes a fault
> injected alloc to fail, while calling bpf_link_detach on them.
> Link detach triggers the link to be freed by bpf_link_free(),
> which calls __cgroup_bpf_detach() and update_effective_progs().
> If the memory allocation in this function fails, the function restores
> the pointer to the bpf_cgroup_link on the cgroup list, but the memory
> gets freed just after it returns. After this, every subsequent call to
> update_effective_progs() causes this already deallocated pointer to be
> dereferenced in prog_list_length(), and triggers KASAN UAF error.
>
> To fix this issue don't preserve the pointer to the prog or link in the
> list, but remove it and replace it with a dummy prog without shrinking
> the table. The subsequent call to __cgroup_bpf_detach() or
> __cgroup_bpf_detach() will correct it.
>
> Cc: "Alexei Starovoitov" <ast@kernel.org>
> Cc: "Daniel Borkmann" <daniel@iogearbox.net>
> Cc: "Andrii Nakryiko" <andrii@kernel.org>
> Cc: "Martin KaFai Lau" <kafai@fb.com>
> Cc: "Song Liu" <songliubraving@fb.com>
> Cc: "Yonghong Song" <yhs@fb.com>
> Cc: "John Fastabend" <john.fastabend@gmail.com>
> Cc: "KP Singh" <kpsingh@kernel.org>
> Cc: <netdev@vger.kernel.org>
> Cc: <bpf@vger.kernel.org>
> Cc: <stable@vger.kernel.org>
> Cc: <linux-kernel@vger.kernel.org>
>
> Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
> Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
> Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
> ---
> v2: Add a fall back path that removes a prog from the effective progs
>     table in case detach fails to allocate memory in compute_effective_progs().
>
> v3: Implement the fallback in a separate function purge_effective_progs
> ---
>  kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 56 insertions(+), 8 deletions(-)
>
> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> index 128028efda64..9d3af4d6c055 100644
> --- a/kernel/bpf/cgroup.c
> +++ b/kernel/bpf/cgroup.c
> @@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs,
>         return ERR_PTR(-ENOENT);
>  }
>
> +/**
> + * purge_effective_progs() - After compute_effective_progs fails to alloc new
> + *                           cgrp->bpf.inactive table we can recover by
> + *                           recomputing the array in place.
> + *
> + * @cgrp: The cgroup which descendants to traverse
> + * @link: A link to detach
> + * @atype: Type of detach operation
> + */
> +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog,
> +                                 enum cgroup_bpf_attach_type atype)
> +{
> +       struct cgroup_subsys_state *css;
> +       struct bpf_prog_array_item *item;
> +       struct bpf_prog *tmp;
> +       struct bpf_prog_array *array;
> +       int index = 0, index_purge = -1;
> +
> +       if (!prog)
> +               return;
> +
> +       /* recompute effective prog array in place */
> +       css_for_each_descendant_pre(css, &cgrp->self) {
> +               struct cgroup *desc = container_of(css, struct cgroup, self);
> +
> +               array = desc->bpf.effective[atype];

../kernel/bpf/cgroup.c:748:23: warning: incorrect type in assignment
(different address spaces)
../kernel/bpf/cgroup.c:748:23:    expected struct bpf_prog_array *array
../kernel/bpf/cgroup.c:748:23:    got struct bpf_prog_array [noderef] __rcu *


you need rcu_dereference here? but also see suggestions below to avoid
iterating effective directly (it's ambiguous to search by prog only)

> +               item = &array->items[0];
> +
> +               /* Find the index of the prog to purge */
> +               while ((tmp = READ_ONCE(item->prog))) {
> +                       if (tmp == prog) {

I think comparing just prog isn't always correct, as the same program
can be in effective array multiple times if attached through bpf_link.

Looking at replace_effective_prog() I think we can do a very similar
(and tested) approach:

1. restore original pl state in __cgroup_bpf_detach (so we can find it
by comparing pl->prog == prog && pl->link == link)
2. use replace_effective_prog's approach to find position of pl in
effective array (using this nested for loop over cgroup parents and
list_for_each_entry inside)
3. then instead of replacing one prog with another do
bpf_prog_array_delete_safe_at ?

I'd feel more comfortable using the same tested overall approach of
replace_effective_prog.

> +                               index_purge = index;
> +                               break;
> +                       }
> +                       item++;
> +                       index++;
> +               }
> +
> +               /* Check if we found what's needed for removing the prog */
> +               if (index_purge == -1 || index_purge == index - 1)
> +                       continue;

the search shouldn't fail, should it?

> +
> +               /* Remove the program from the array */
> +               WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge),
> +                         "Failed to purge a prog from array at index %d", index_purge);
> +
> +               index = 0;
> +               index_purge = -1;
> +       }
> +}
> +
>  /**
>   * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and
>   *                         propagate the change to descendants
> @@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>         pl->link = NULL;
>
>         err = update_effective_progs(cgrp, atype);
> -       if (err)
> -               goto cleanup;
> +       if (err) {
> +               struct bpf_prog *prog_purge = prog ? prog : link->link.prog;
> +

so here we shouldn't forget link, instead pass both link and prog (one
of them will have to be NULL) into purge_effective_progs

> +               purge_effective_progs(cgrp, prog_purge, atype);
> +       }
>
>         /* now can actually delete it from this cgroup list */
>         list_del(&pl->node);
> @@ -736,12 +790,6 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>                 bpf_prog_put(old_prog);
>         static_branch_dec(&cgroup_bpf_enabled_key[atype]);
>         return 0;
> -
> -cleanup:
> -       /* restore back prog or link */
> -       pl->prog = old_prog;
> -       pl->link = link;
> -       return err;
>  }
>
>  static int cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
> --
> 2.36.1
>

Re: [PATCH v3] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

On 5/16/22 16:16, Andrii Nakryiko wrote:
> On Fri, May 13, 2022 at 12:08 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>>   kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------
>>   1 file changed, 56 insertions(+), 8 deletions(-)
>>
>> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
>> index 128028efda64..9d3af4d6c055 100644
>> --- a/kernel/bpf/cgroup.c
>> +++ b/kernel/bpf/cgroup.c
>> @@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs,
>>          return ERR_PTR(-ENOENT);
>>   }
>>
>> +/**
>> + * purge_effective_progs() - After compute_effective_progs fails to alloc new
>> + *                           cgrp->bpf.inactive table we can recover by
>> + *                           recomputing the array in place.
>> + *
>> + * @cgrp: The cgroup which descendants to traverse
>> + * @link: A link to detach
>> + * @atype: Type of detach operation
>> + */
>> +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog,
>> +                                 enum cgroup_bpf_attach_type atype)
>> +{
>> +       struct cgroup_subsys_state *css;
>> +       struct bpf_prog_array_item *item;
>> +       struct bpf_prog *tmp;
>> +       struct bpf_prog_array *array;
>> +       int index = 0, index_purge = -1;
>> +
>> +       if (!prog)
>> +               return;
>> +
>> +       /* recompute effective prog array in place */
>> +       css_for_each_descendant_pre(css, &cgrp->self) {
>> +               struct cgroup *desc = container_of(css, struct cgroup, self);
>> +
>> +               array = desc->bpf.effective[atype];
> 
> ../kernel/bpf/cgroup.c:748:23: warning: incorrect type in assignment
> (different address spaces)
> ../kernel/bpf/cgroup.c:748:23:    expected struct bpf_prog_array *array
> ../kernel/bpf/cgroup.c:748:23:    got struct bpf_prog_array [noderef] __rcu *
> 
> 
> you need rcu_dereference here? but also see suggestions below to avoid
> iterating effective directly (it's ambiguous to search by prog only)

I didn't check it with sparse so I didn't see this warning.
Will fix in the next version.

> 
>> +               item = &array->items[0];
>> +
>> +               /* Find the index of the prog to purge */
>> +               while ((tmp = READ_ONCE(item->prog))) {
>> +                       if (tmp == prog) {
> 
> I think comparing just prog isn't always correct, as the same program
> can be in effective array multiple times if attached through bpf_link.
> 
> Looking at replace_effective_prog() I think we can do a very similar
> (and tested) approach:
> 
> 1. restore original pl state in __cgroup_bpf_detach (so we can find it
> by comparing pl->prog == prog && pl->link == link)
> 2. use replace_effective_prog's approach to find position of pl in
> effective array (using this nested for loop over cgroup parents and
> list_for_each_entry inside)
> 3. then instead of replacing one prog with another do
> bpf_prog_array_delete_safe_at ?
> 
> I'd feel more comfortable using the same tested overall approach of
> replace_effective_prog.

Ok, I can try that.

> 
>> +                               index_purge = index;
>> +                               break;
>> +                       }
>> +                       item++;
>> +                       index++;
>> +               }
>> +
>> +               /* Check if we found what's needed for removing the prog */
>> +               if (index_purge == -1 || index_purge == index - 1)
>> +                       continue;
> 
> the search shouldn't fail, should it?

I wasn't if the prog will be present in all parents so I decided to add this
check to make sure it is found.

> 
>> +
>> +               /* Remove the program from the array */
>> +               WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge),
>> +                         "Failed to purge a prog from array at index %d", index_purge);
>> +
>> +               index = 0;
>> +               index_purge = -1;
>> +       }
>> +}
>> +
>>   /**
>>    * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and
>>    *                         propagate the change to descendants
>> @@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>>          pl->link = NULL;
>>
>>          err = update_effective_progs(cgrp, atype);
>> -       if (err)
>> -               goto cleanup;
>> +       if (err) {
>> +               struct bpf_prog *prog_purge = prog ? prog : link->link.prog;
>> +
> 
> so here we shouldn't forget link, instead pass both link and prog (one
> of them will have to be NULL) into purge_effective_progs

ok, I will pass in both.

-- 
Thanks,
Tadeusz

Re: [PATCH v3] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Mon, May 16, 2022 at 4:35 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> On 5/16/22 16:16, Andrii Nakryiko wrote:
> > On Fri, May 13, 2022 at 12:08 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
> >>   kernel/bpf/cgroup.c | 64 +++++++++++++++++++++++++++++++++++++++------
> >>   1 file changed, 56 insertions(+), 8 deletions(-)
> >>
> >> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> >> index 128028efda64..9d3af4d6c055 100644
> >> --- a/kernel/bpf/cgroup.c
> >> +++ b/kernel/bpf/cgroup.c
> >> @@ -681,6 +681,57 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs,
> >>          return ERR_PTR(-ENOENT);
> >>   }
> >>
> >> +/**
> >> + * purge_effective_progs() - After compute_effective_progs fails to alloc new
> >> + *                           cgrp->bpf.inactive table we can recover by
> >> + *                           recomputing the array in place.
> >> + *
> >> + * @cgrp: The cgroup which descendants to traverse
> >> + * @link: A link to detach
> >> + * @atype: Type of detach operation
> >> + */
> >> +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog,
> >> +                                 enum cgroup_bpf_attach_type atype)
> >> +{
> >> +       struct cgroup_subsys_state *css;
> >> +       struct bpf_prog_array_item *item;
> >> +       struct bpf_prog *tmp;
> >> +       struct bpf_prog_array *array;
> >> +       int index = 0, index_purge = -1;
> >> +
> >> +       if (!prog)
> >> +               return;
> >> +
> >> +       /* recompute effective prog array in place */
> >> +       css_for_each_descendant_pre(css, &cgrp->self) {
> >> +               struct cgroup *desc = container_of(css, struct cgroup, self);
> >> +
> >> +               array = desc->bpf.effective[atype];
> >
> > ../kernel/bpf/cgroup.c:748:23: warning: incorrect type in assignment
> > (different address spaces)
> > ../kernel/bpf/cgroup.c:748:23:    expected struct bpf_prog_array *array
> > ../kernel/bpf/cgroup.c:748:23:    got struct bpf_prog_array [noderef] __rcu *
> >
> >
> > you need rcu_dereference here? but also see suggestions below to avoid
> > iterating effective directly (it's ambiguous to search by prog only)
>
> I didn't check it with sparse so I didn't see this warning.
> Will fix in the next version.
>
> >
> >> +               item = &array->items[0];
> >> +
> >> +               /* Find the index of the prog to purge */
> >> +               while ((tmp = READ_ONCE(item->prog))) {
> >> +                       if (tmp == prog) {
> >
> > I think comparing just prog isn't always correct, as the same program
> > can be in effective array multiple times if attached through bpf_link.
> >
> > Looking at replace_effective_prog() I think we can do a very similar
> > (and tested) approach:
> >
> > 1. restore original pl state in __cgroup_bpf_detach (so we can find it
> > by comparing pl->prog == prog && pl->link == link)
> > 2. use replace_effective_prog's approach to find position of pl in
> > effective array (using this nested for loop over cgroup parents and
> > list_for_each_entry inside)
> > 3. then instead of replacing one prog with another do
> > bpf_prog_array_delete_safe_at ?
> >
> > I'd feel more comfortable using the same tested overall approach of
> > replace_effective_prog.
>
> Ok, I can try that.
>
> >
> >> +                               index_purge = index;
> >> +                               break;
> >> +                       }
> >> +                       item++;
> >> +                       index++;
> >> +               }
> >> +
> >> +               /* Check if we found what's needed for removing the prog */
> >> +               if (index_purge == -1 || index_purge == index - 1)
> >> +                       continue;
> >
> > the search shouldn't fail, should it?
>
> I wasn't if the prog will be present in all parents so I decided to add this
> check to make sure it is found.

Looking at replace_effective_prog (it's been a while since I touched
this code) it has to be present, otherwise it's a bug

>
> >
> >> +
> >> +               /* Remove the program from the array */
> >> +               WARN_ONCE(bpf_prog_array_delete_safe_at(array, index_purge),
> >> +                         "Failed to purge a prog from array at index %d", index_purge);
> >> +
> >> +               index = 0;
> >> +               index_purge = -1;
> >> +       }
> >> +}
> >> +
> >>   /**
> >>    * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and
> >>    *                         propagate the change to descendants
> >> @@ -723,8 +774,11 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
> >>          pl->link = NULL;
> >>
> >>          err = update_effective_progs(cgrp, atype);
> >> -       if (err)
> >> -               goto cleanup;
> >> +       if (err) {
> >> +               struct bpf_prog *prog_purge = prog ? prog : link->link.prog;
> >> +
> >
> > so here we shouldn't forget link, instead pass both link and prog (one
> > of them will have to be NULL) into purge_effective_progs
>
> ok, I will pass in both.
>
> --
> Thanks,
> Tadeusz

[PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

Syzbot found a Use After Free bug in compute_effective_progs().
The reproducer creates a number of BPF links, and causes a fault
injected alloc to fail, while calling bpf_link_detach on them.
Link detach triggers the link to be freed by bpf_link_free(),
which calls __cgroup_bpf_detach() and update_effective_progs().
If the memory allocation in this function fails, the function restores
the pointer to the bpf_cgroup_link on the cgroup list, but the memory
gets freed just after it returns. After this, every subsequent call to
update_effective_progs() causes this already deallocated pointer to be
dereferenced in prog_list_length(), and triggers KASAN UAF error.

To fix this issue don't preserve the pointer to the prog or link in the
list, but remove it and replace it with a dummy prog without shrinking
the table. The subsequent call to __cgroup_bpf_detach() or
__cgroup_bpf_detach() will correct it.

Cc: "Alexei Starovoitov" <ast@kernel.org>
Cc: "Daniel Borkmann" <daniel@iogearbox.net>
Cc: "Andrii Nakryiko" <andrii@kernel.org>
Cc: "Martin KaFai Lau" <kafai@fb.com>
Cc: "Song Liu" <songliubraving@fb.com>
Cc: "Yonghong Song" <yhs@fb.com>
Cc: "John Fastabend" <john.fastabend@gmail.com>
Cc: "KP Singh" <kpsingh@kernel.org>
Cc: <netdev@vger.kernel.org>
Cc: <bpf@vger.kernel.org>
Cc: <stable@vger.kernel.org>
Cc: <linux-kernel@vger.kernel.org>

Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
---
v2: Add a fall back path that removes a prog from the effective progs
    table in case detach fails to allocate memory in compute_effective_progs().

v3: Implement the fallback in a separate function purge_effective_progs

v4: Changed purge_effective_progs() to manipulate the array in a similar way
    how replace_effective_prog() does it.
---
 kernel/bpf/cgroup.c | 68 +++++++++++++++++++++++++++++++++++++++------
 1 file changed, 60 insertions(+), 8 deletions(-)

diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
index 128028efda64..6f1a6160c99e 100644
--- a/kernel/bpf/cgroup.c
+++ b/kernel/bpf/cgroup.c
@@ -681,6 +681,60 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs,
 	return ERR_PTR(-ENOENT);
 }
 
+/**
+ * purge_effective_progs() - After compute_effective_progs fails to alloc new
+ *                           cgrp->bpf.inactive table we can recover by
+ *                           recomputing the array in place.
+ *
+ * @cgrp: The cgroup which descendants to travers
+ * @prog: A program to detach or NULL
+ * @link: A link to detach or NULL
+ * @atype: Type of detach operation
+ */
+static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog,
+				  struct bpf_cgroup_link *link,
+				  enum cgroup_bpf_attach_type atype)
+{
+	struct cgroup_subsys_state *css;
+	struct bpf_prog_array *progs;
+	struct bpf_prog_list *pl;
+	struct list_head *head;
+	struct cgroup *cg;
+	int pos;
+
+	/* recompute effective prog array in place */
+	css_for_each_descendant_pre(css, &cgrp->self) {
+		struct cgroup *desc = container_of(css, struct cgroup, self);
+
+		if (percpu_ref_is_zero(&desc->bpf.refcnt))
+			continue;
+
+		/* find position of link or prog in effective progs array */
+		for (pos = 0, cg = desc; cg; cg = cgroup_parent(cg)) {
+			if (pos && !(cg->bpf.flags[atype] & BPF_F_ALLOW_MULTI))
+				continue;
+
+			head = &cg->bpf.progs[atype];
+			list_for_each_entry(pl, head, node) {
+				if (!prog_list_prog(pl))
+					continue;
+				if (pl->prog == prog && pl->link == link)
+					goto found;
+				pos++;
+			}
+		}
+found:
+		BUG_ON(!cg);
+		progs = rcu_dereference_protected(
+				desc->bpf.effective[atype],
+				lockdep_is_held(&cgroup_mutex));
+
+		/* Remove the program from the array */
+		WARN_ONCE(bpf_prog_array_delete_safe_at(progs, pos),
+			  "Failed to purge a prog from array at index %d", pos);
+	}
+}
+
 /**
  * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and
  *                         propagate the change to descendants
@@ -723,8 +777,12 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 	pl->link = NULL;
 
 	err = update_effective_progs(cgrp, atype);
-	if (err)
-		goto cleanup;
+	if (err) {
+		/* If update affective array failed replace the prog with a dummy prog*/
+		pl->prog = old_prog;
+		pl->link = link;
+		purge_effective_progs(cgrp, old_prog, link, atype);
+	}
 
 	/* now can actually delete it from this cgroup list */
 	list_del(&pl->node);
@@ -736,12 +794,6 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
 		bpf_prog_put(old_prog);
 	static_branch_dec(&cgroup_bpf_enabled_key[atype]);
 	return 0;
-
-cleanup:
-	/* restore back prog or link */
-	pl->prog = old_prog;
-	pl->link = link;
-	return err;
 }
 
 static int cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
-- 
2.36.1

Re: [PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

On 5/17/22 11:04, Tadeusz Struk wrote:
> Syzbot found a Use After Free bug in compute_effective_progs().
> The reproducer creates a number of BPF links, and causes a fault
> injected alloc to fail, while calling bpf_link_detach on them.
> Link detach triggers the link to be freed by bpf_link_free(),
> which calls __cgroup_bpf_detach() and update_effective_progs().
> If the memory allocation in this function fails, the function restores
> the pointer to the bpf_cgroup_link on the cgroup list, but the memory
> gets freed just after it returns. After this, every subsequent call to
> update_effective_progs() causes this already deallocated pointer to be
> dereferenced in prog_list_length(), and triggers KASAN UAF error.
> 
> To fix this issue don't preserve the pointer to the prog or link in the
> list, but remove it and replace it with a dummy prog without shrinking
> the table. The subsequent call to __cgroup_bpf_detach() or
> __cgroup_bpf_detach() will correct it.
> 
> Cc: "Alexei Starovoitov" <ast@kernel.org>
> Cc: "Daniel Borkmann" <daniel@iogearbox.net>
> Cc: "Andrii Nakryiko" <andrii@kernel.org>
> Cc: "Martin KaFai Lau" <kafai@fb.com>
> Cc: "Song Liu" <songliubraving@fb.com>
> Cc: "Yonghong Song" <yhs@fb.com>
> Cc: "John Fastabend" <john.fastabend@gmail.com>
> Cc: "KP Singh" <kpsingh@kernel.org>
> Cc: <netdev@vger.kernel.org>
> Cc: <bpf@vger.kernel.org>
> Cc: <stable@vger.kernel.org>
> Cc: <linux-kernel@vger.kernel.org>
> 
> Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
> Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
> Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
> ---
> v2: Add a fall back path that removes a prog from the effective progs
>      table in case detach fails to allocate memory in compute_effective_progs().
> 
> v3: Implement the fallback in a separate function purge_effective_progs
> 
> v4: Changed purge_effective_progs() to manipulate the array in a similar way
>      how replace_effective_prog() does it.
> ---
>   kernel/bpf/cgroup.c | 68 +++++++++++++++++++++++++++++++++++++++------
>   1 file changed, 60 insertions(+), 8 deletions(-)
> 
> diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> index 128028efda64..6f1a6160c99e 100644
> --- a/kernel/bpf/cgroup.c
> +++ b/kernel/bpf/cgroup.c
> @@ -681,6 +681,60 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs,
>   	return ERR_PTR(-ENOENT);
>   }
>   
> +/**
> + * purge_effective_progs() - After compute_effective_progs fails to alloc new
> + *                           cgrp->bpf.inactive table we can recover by
> + *                           recomputing the array in place.
> + *
> + * @cgrp: The cgroup which descendants to travers
> + * @prog: A program to detach or NULL
> + * @link: A link to detach or NULL
> + * @atype: Type of detach operation
> + */
> +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog,
> +				  struct bpf_cgroup_link *link,
> +				  enum cgroup_bpf_attach_type atype)
> +{
> +	struct cgroup_subsys_state *css;
> +	struct bpf_prog_array *progs;
> +	struct bpf_prog_list *pl;
> +	struct list_head *head;
> +	struct cgroup *cg;
> +	int pos;
> +
> +	/* recompute effective prog array in place */
> +	css_for_each_descendant_pre(css, &cgrp->self) {
> +		struct cgroup *desc = container_of(css, struct cgroup, self);
> +
> +		if (percpu_ref_is_zero(&desc->bpf.refcnt))
> +			continue;
> +
> +		/* find position of link or prog in effective progs array */
> +		for (pos = 0, cg = desc; cg; cg = cgroup_parent(cg)) {
> +			if (pos && !(cg->bpf.flags[atype] & BPF_F_ALLOW_MULTI))
> +				continue;
> +
> +			head = &cg->bpf.progs[atype];
> +			list_for_each_entry(pl, head, node) {
> +				if (!prog_list_prog(pl))
> +					continue;
> +				if (pl->prog == prog && pl->link == link)
> +					goto found;
> +				pos++;
> +			}
> +		}
> +found:
> +		BUG_ON(!cg);
> +		progs = rcu_dereference_protected(
> +				desc->bpf.effective[atype],
> +				lockdep_is_held(&cgroup_mutex));
> +
> +		/* Remove the program from the array */
> +		WARN_ONCE(bpf_prog_array_delete_safe_at(progs, pos),
> +			  "Failed to purge a prog from array at index %d", pos);
> +	}
> +}
> +
>   /**
>    * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and
>    *                         propagate the change to descendants
> @@ -723,8 +777,12 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>   	pl->link = NULL;
>   
>   	err = update_effective_progs(cgrp, atype);
> -	if (err)
> -		goto cleanup;
> +	if (err) {
> +		/* If update affective array failed replace the prog with a dummy prog*/
> +		pl->prog = old_prog;
> +		pl->link = link;
> +		purge_effective_progs(cgrp, old_prog, link, atype);
> +	}
>   
>   	/* now can actually delete it from this cgroup list */
>   	list_del(&pl->node);
> @@ -736,12 +794,6 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>   		bpf_prog_put(old_prog);
>   	static_branch_dec(&cgroup_bpf_enabled_key[atype]);
>   	return 0;
> -
> -cleanup:
> -	/* restore back prog or link */
> -	pl->prog = old_prog;
> -	pl->link = link;
> -	return err;
>   }
>   
>   static int cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,

Hi Andrii,
Do you have any more feedback? Does it look better to you now?
-- 
Thanks,
Tadeusz

Re: [PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Mon, May 23, 2022 at 2:36 PM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> On 5/17/22 11:04, Tadeusz Struk wrote:
> > Syzbot found a Use After Free bug in compute_effective_progs().
> > The reproducer creates a number of BPF links, and causes a fault
> > injected alloc to fail, while calling bpf_link_detach on them.
> > Link detach triggers the link to be freed by bpf_link_free(),
> > which calls __cgroup_bpf_detach() and update_effective_progs().
> > If the memory allocation in this function fails, the function restores
> > the pointer to the bpf_cgroup_link on the cgroup list, but the memory
> > gets freed just after it returns. After this, every subsequent call to
> > update_effective_progs() causes this already deallocated pointer to be
> > dereferenced in prog_list_length(), and triggers KASAN UAF error.
> >
> > To fix this issue don't preserve the pointer to the prog or link in the
> > list, but remove it and replace it with a dummy prog without shrinking
> > the table. The subsequent call to __cgroup_bpf_detach() or
> > __cgroup_bpf_detach() will correct it.
> >
> > Cc: "Alexei Starovoitov" <ast@kernel.org>
> > Cc: "Daniel Borkmann" <daniel@iogearbox.net>
> > Cc: "Andrii Nakryiko" <andrii@kernel.org>
> > Cc: "Martin KaFai Lau" <kafai@fb.com>
> > Cc: "Song Liu" <songliubraving@fb.com>
> > Cc: "Yonghong Song" <yhs@fb.com>
> > Cc: "John Fastabend" <john.fastabend@gmail.com>
> > Cc: "KP Singh" <kpsingh@kernel.org>
> > Cc: <netdev@vger.kernel.org>
> > Cc: <bpf@vger.kernel.org>
> > Cc: <stable@vger.kernel.org>
> > Cc: <linux-kernel@vger.kernel.org>
> >
> > Link: https://syzkaller.appspot.com/bug?id=8ebf179a95c2a2670f7cf1ba62429ec044369db4
> > Fixes: af6eea57437a ("bpf: Implement bpf_link-based cgroup BPF program attachment")
> > Reported-by: <syzbot+f264bffdfbd5614f3bb2@syzkaller.appspotmail.com>
> > Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
> > ---
> > v2: Add a fall back path that removes a prog from the effective progs
> >      table in case detach fails to allocate memory in compute_effective_progs().
> >
> > v3: Implement the fallback in a separate function purge_effective_progs
> >
> > v4: Changed purge_effective_progs() to manipulate the array in a similar way
> >      how replace_effective_prog() does it.
> > ---
> >   kernel/bpf/cgroup.c | 68 +++++++++++++++++++++++++++++++++++++++------
> >   1 file changed, 60 insertions(+), 8 deletions(-)
> >
> > diff --git a/kernel/bpf/cgroup.c b/kernel/bpf/cgroup.c
> > index 128028efda64..6f1a6160c99e 100644
> > --- a/kernel/bpf/cgroup.c
> > +++ b/kernel/bpf/cgroup.c
> > @@ -681,6 +681,60 @@ static struct bpf_prog_list *find_detach_entry(struct list_head *progs,
> >       return ERR_PTR(-ENOENT);
> >   }
> >
> > +/**
> > + * purge_effective_progs() - After compute_effective_progs fails to alloc new
> > + *                           cgrp->bpf.inactive table we can recover by
> > + *                           recomputing the array in place.
> > + *
> > + * @cgrp: The cgroup which descendants to travers
> > + * @prog: A program to detach or NULL
> > + * @link: A link to detach or NULL
> > + * @atype: Type of detach operation
> > + */
> > +static void purge_effective_progs(struct cgroup *cgrp, struct bpf_prog *prog,
> > +                               struct bpf_cgroup_link *link,
> > +                               enum cgroup_bpf_attach_type atype)
> > +{
> > +     struct cgroup_subsys_state *css;
> > +     struct bpf_prog_array *progs;
> > +     struct bpf_prog_list *pl;
> > +     struct list_head *head;
> > +     struct cgroup *cg;
> > +     int pos;
> > +
> > +     /* recompute effective prog array in place */
> > +     css_for_each_descendant_pre(css, &cgrp->self) {
> > +             struct cgroup *desc = container_of(css, struct cgroup, self);
> > +
> > +             if (percpu_ref_is_zero(&desc->bpf.refcnt))
> > +                     continue;
> > +
> > +             /* find position of link or prog in effective progs array */
> > +             for (pos = 0, cg = desc; cg; cg = cgroup_parent(cg)) {
> > +                     if (pos && !(cg->bpf.flags[atype] & BPF_F_ALLOW_MULTI))
> > +                             continue;
> > +
> > +                     head = &cg->bpf.progs[atype];
> > +                     list_for_each_entry(pl, head, node) {
> > +                             if (!prog_list_prog(pl))
> > +                                     continue;
> > +                             if (pl->prog == prog && pl->link == link)
> > +                                     goto found;
> > +                             pos++;
> > +                     }
> > +             }
> > +found:
> > +             BUG_ON(!cg);
> > +             progs = rcu_dereference_protected(
> > +                             desc->bpf.effective[atype],
> > +                             lockdep_is_held(&cgroup_mutex));
> > +
> > +             /* Remove the program from the array */
> > +             WARN_ONCE(bpf_prog_array_delete_safe_at(progs, pos),
> > +                       "Failed to purge a prog from array at index %d", pos);
> > +     }
> > +}
> > +
> >   /**
> >    * __cgroup_bpf_detach() - Detach the program or link from a cgroup, and
> >    *                         propagate the change to descendants
> > @@ -723,8 +777,12 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
> >       pl->link = NULL;
> >
> >       err = update_effective_progs(cgrp, atype);
> > -     if (err)
> > -             goto cleanup;
> > +     if (err) {
> > +             /* If update affective array failed replace the prog with a dummy prog*/
> > +             pl->prog = old_prog;
> > +             pl->link = link;
> > +             purge_effective_progs(cgrp, old_prog, link, atype);
> > +     }
> >
> >       /* now can actually delete it from this cgroup list */
> >       list_del(&pl->node);
> > @@ -736,12 +794,6 @@ static int __cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
> >               bpf_prog_put(old_prog);
> >       static_branch_dec(&cgroup_bpf_enabled_key[atype]);
> >       return 0;
> > -
> > -cleanup:
> > -     /* restore back prog or link */
> > -     pl->prog = old_prog;
> > -     pl->link = link;
> > -     return err;
> >   }
> >
> >   static int cgroup_bpf_detach(struct cgroup *cgrp, struct bpf_prog *prog,
>
> Hi Andrii,
> Do you have any more feedback? Does it look better to you now?

Hi, this is on my TODO list, but I need a bit more focused time to
think all this through and I haven't managed to get it in last week.
I'm worried about the percpu_ref_is_zero(&desc->bpf.refcnt) portion
and whether it can cause some skew in the calculated array index, I
need to look at this a bit more in depth. Sorry for the delay.

> --
> Thanks,
> Tadeusz

Re: [PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

On 5/23/22 15:47, Andrii Nakryiko wrote:
>> Hi Andrii,
>> Do you have any more feedback? Does it look better to you now?
> Hi, this is on my TODO list, but I need a bit more focused time to
> think all this through and I haven't managed to get it in last week.
> I'm worried about the percpu_ref_is_zero(&desc->bpf.refcnt) portion
> and whether it can cause some skew in the calculated array index, I
> need to look at this a bit more in depth. Sorry for the delay.

That's fine. take your time and let me know if there is anything else
to change/improve. FWIW I tested it extensively with the syzbot repro
and the issue doesn't trigger anymore.

-- 
Thanks,
Tadeusz

Re: [PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

Hi Andrii,
On 5/23/22 15:47, Andrii Nakryiko wrote:
>> Hi Andrii,
>> Do you have any more feedback? Does it look better to you now?
> Hi, this is on my TODO list, but I need a bit more focused time to
> think all this through and I haven't managed to get it in last week.
> I'm worried about the percpu_ref_is_zero(&desc->bpf.refcnt) portion
> and whether it can cause some skew in the calculated array index, I
> need to look at this a bit more in depth. Sorry for the delay.

Did you get a chance to look at this yet?

-- 
Thanks,
Tadeusz

Re: [PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Andrii Nakryiko]

On Thu, Jun 2, 2022 at 7:37 AM Tadeusz Struk <tadeusz.struk@linaro.org> wrote:
>
> Hi Andrii,
> On 5/23/22 15:47, Andrii Nakryiko wrote:
> >> Hi Andrii,
> >> Do you have any more feedback? Does it look better to you now?
> > Hi, this is on my TODO list, but I need a bit more focused time to
> > think all this through and I haven't managed to get it in last week.
> > I'm worried about the percpu_ref_is_zero(&desc->bpf.refcnt) portion
> > and whether it can cause some skew in the calculated array index, I
> > need to look at this a bit more in depth. Sorry for the delay.
>
> Did you get a chance to look at this yet?
>

Hm.. I've applied it two days ago, but for some reason there was no
notification from the bot. It's now c89c79fda9b6 ("bpf: Fix KASAN
use-after-free Read in compute_effective_progs").

> --
> Thanks,
> Tadeusz

Re: [PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

On 6/2/22 09:11, Andrii Nakryiko wrote:
>> Did you get a chance to look at this yet?
>>
> Hm.. I've applied it two days ago, but for some reason there was no
> notification from the bot. It's now c89c79fda9b6 ("bpf: Fix KASAN
> use-after-free Read in compute_effective_progs").

Great! Thank you.

-- 
Thanks,
Tadeusz

Re: [PATCH v4] bpf: Fix KASAN use-after-free Read in compute_effective_progs

[Tadeusz Struk]

On 6/2/22 09:25, Tadeusz Struk wrote:
> On 6/2/22 09:11, Andrii Nakryiko wrote:
>>> Did you get a chance to look at this yet?
>>>
>> Hm.. I've applied it two days ago, but for some reason there was no
>> notification from the bot. It's now c89c79fda9b6 ("bpf: Fix KASAN
>> use-after-free Read in compute_effective_progs").

FYI. Just requested a test on bpf-next and it passed fine.
https://groups.google.com/g/syzkaller-android-bugs/c/nr6mD4vhRA4

-- 
Thanks,
Tadeusz