[PATCH] cgroup: rstat: optimize flush through speculative test

[PATCH] cgroup: rstat: optimize flush through speculative test

[Shakeel Butt]

Currently cgroup_rstat_updated() has a speculative already-on-list test
to check if the given cgroup is already part of the rstat update tree.
This helps in reducing the contention on the rstat cpu lock. This patch
adds the similar speculative not-on-list test on the rstat flush
codepath.

Recently the commit aa48e47e3906 ("memcg: infrastructure to flush memcg
stats") added periodic rstat flush. On a large system which is not much
busy, most of the per-cpu rstat tree would be empty. So, the speculative
not-on-list test helps in eliminating unnecessary work and potentially
reducing contention on the rstat cpu lock. Please note this might
introduce temporary inaccuracy but with the frequent and periodic flush
this would not be an issue.

To evaluate the impact of this patch, an 8 GiB tmpfs file is created on
a system with swap-on-zram and the file was pushed to swap through
memory.force_empty interface. On reading the whole file, the memcg stat
flush in the refault code path is triggered. With this patch, we
observed 38% reduction in the read time of 8 GiB file.

Signed-off-by: Shakeel Butt <shakeelb@google.com>
---
 kernel/cgroup/rstat.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/kernel/cgroup/rstat.c b/kernel/cgroup/rstat.c
index b264ab5652ba..748494fbc786 100644
--- a/kernel/cgroup/rstat.c
+++ b/kernel/cgroup/rstat.c
@@ -35,7 +35,7 @@ void cgroup_rstat_updated(struct cgroup *cgrp, int cpu)
 	 * instead of NULL, we can tell whether @cgrp is on the list by
 	 * testing the next pointer for NULL.
 	 */
-	if (cgroup_rstat_cpu(cgrp, cpu)->updated_next)
+	if (data_race(cgroup_rstat_cpu(cgrp, cpu)->updated_next))
 		return;
 
 	raw_spin_lock_irqsave(cpu_lock, flags);
@@ -157,6 +157,13 @@ static void cgroup_rstat_flush_locked(struct cgroup *cgrp, bool may_sleep)
 						       cpu);
 		struct cgroup *pos = NULL;
 
+		/*
+		 * Speculative not-on-list test. This may lead to temporary
+		 * inaccuracies which is fine.
+		 */
+		if (!data_race(cgroup_rstat_cpu(cgrp, cpu)->updated_next))
+			goto next;
+
 		raw_spin_lock(cpu_lock);
 		while ((pos = cgroup_rstat_cpu_pop_updated(pos, cgrp, cpu))) {
 			struct cgroup_subsys_state *css;
@@ -170,7 +177,7 @@ static void cgroup_rstat_flush_locked(struct cgroup *cgrp, bool may_sleep)
 			rcu_read_unlock();
 		}
 		raw_spin_unlock(cpu_lock);
-
+next:
 		/* if @may_sleep, play nice and yield if necessary */
 		if (may_sleep && (need_resched() ||
 				  spin_needbreak(&cgroup_rstat_lock))) {
-- 
2.33.0.685.g46640cef36-goog

Re: [PATCH] cgroup: rstat: optimize flush through speculative test

[Tejun Heo]

Hello, Shakeel.

On Wed, Sep 29, 2021 at 04:59:36PM -0700, Shakeel Butt wrote:
> Currently cgroup_rstat_updated() has a speculative already-on-list test
> to check if the given cgroup is already part of the rstat update tree.
> This helps in reducing the contention on the rstat cpu lock. This patch
> adds the similar speculative not-on-list test on the rstat flush
> codepath.
> 
> Recently the commit aa48e47e3906 ("memcg: infrastructure to flush memcg
> stats") added periodic rstat flush. On a large system which is not much
> busy, most of the per-cpu rstat tree would be empty. So, the speculative
> not-on-list test helps in eliminating unnecessary work and potentially
> reducing contention on the rstat cpu lock. Please note this might
> introduce temporary inaccuracy but with the frequent and periodic flush
> this would not be an issue.
> 
> To evaluate the impact of this patch, an 8 GiB tmpfs file is created on
> a system with swap-on-zram and the file was pushed to swap through
> memory.force_empty interface. On reading the whole file, the memcg stat
> flush in the refault code path is triggered. With this patch, we
> observed 38% reduction in the read time of 8 GiB file.

The patch looks fine to me but that's a lot of reduction in read time. Can
you elaborate a bit on why this makes such a huge difference? Who's hitting
on that lock so hard?

Thanks.

-- 
tejun

Re: [PATCH] cgroup: rstat: optimize flush through speculative test

[Shakeel Butt]

On Mon, Oct 4, 2021 at 10:00 AM Tejun Heo <tj@kernel.org> wrote:
>
> Hello, Shakeel.
>
> On Wed, Sep 29, 2021 at 04:59:36PM -0700, Shakeel Butt wrote:
> > Currently cgroup_rstat_updated() has a speculative already-on-list test
> > to check if the given cgroup is already part of the rstat update tree.
> > This helps in reducing the contention on the rstat cpu lock. This patch
> > adds the similar speculative not-on-list test on the rstat flush
> > codepath.
> >
> > Recently the commit aa48e47e3906 ("memcg: infrastructure to flush memcg
> > stats") added periodic rstat flush. On a large system which is not much
> > busy, most of the per-cpu rstat tree would be empty. So, the speculative
> > not-on-list test helps in eliminating unnecessary work and potentially
> > reducing contention on the rstat cpu lock. Please note this might
> > introduce temporary inaccuracy but with the frequent and periodic flush
> > this would not be an issue.
> >
> > To evaluate the impact of this patch, an 8 GiB tmpfs file is created on
> > a system with swap-on-zram and the file was pushed to swap through
> > memory.force_empty interface. On reading the whole file, the memcg stat
> > flush in the refault code path is triggered. With this patch, we
> > observed 38% reduction in the read time of 8 GiB file.
>
> The patch looks fine to me but that's a lot of reduction in read time. Can
> you elaborate a bit on why this makes such a huge difference? Who's hitting
> on that lock so hard?
>

It was actually due to machine size. I ran a single threaded workload
without any interference on a 112 cpus machine. So, most of the time
the flush was acquiring and releasing the per-cpu rstat lock for empty
trees.

Shakeel

Re: [PATCH] cgroup: rstat: optimize flush through speculative test

[Tejun Heo]

On Mon, Oct 04, 2021 at 10:25:12AM -0700, Shakeel Butt wrote:
> > > To evaluate the impact of this patch, an 8 GiB tmpfs file is created on
> > > a system with swap-on-zram and the file was pushed to swap through
> > > memory.force_empty interface. On reading the whole file, the memcg stat
> > > flush in the refault code path is triggered. With this patch, we
> > > observed 38% reduction in the read time of 8 GiB file.
> >
> > The patch looks fine to me but that's a lot of reduction in read time. Can
> > you elaborate a bit on why this makes such a huge difference? Who's hitting
> > on that lock so hard?
> 
> It was actually due to machine size. I ran a single threaded workload
> without any interference on a 112 cpus machine. So, most of the time
> the flush was acquiring and releasing the per-cpu rstat lock for empty
> trees.

Sorry for being so slow but can you point to the exact call path which gets
slowed down so significantly? I'm mostly wondering whether we need some sort
of time-batched flushes because even with lock avoidance the flush path
really isn't great when called frequently. We can mitigate it further if
necessary - e.g. by adding an "updated" bitmap so that the flusher doesn't
have to go around touching the cachelines for all the cpus.

Thanks.

-- 
tejun

Re: [PATCH] cgroup: rstat: optimize flush through speculative test

[Shakeel Butt]

On Mon, Oct 4, 2021 at 10:44 AM Tejun Heo <tj@kernel.org> wrote:
>
> On Mon, Oct 04, 2021 at 10:25:12AM -0700, Shakeel Butt wrote:
> > > > To evaluate the impact of this patch, an 8 GiB tmpfs file is created on
> > > > a system with swap-on-zram and the file was pushed to swap through
> > > > memory.force_empty interface. On reading the whole file, the memcg stat
> > > > flush in the refault code path is triggered. With this patch, we
> > > > observed 38% reduction in the read time of 8 GiB file.
> > >
> > > The patch looks fine to me but that's a lot of reduction in read time. Can
> > > you elaborate a bit on why this makes such a huge difference? Who's hitting
> > > on that lock so hard?
> >
> > It was actually due to machine size. I ran a single threaded workload
> > without any interference on a 112 cpus machine. So, most of the time
> > the flush was acquiring and releasing the per-cpu rstat lock for empty
> > trees.
>
> Sorry for being so slow but can you point to the exact call path which gets
> slowed down so significantly?

This is the mem_cgroup_flush_stats() inside workingset_refault() in
mm/workingset.c.

> I'm mostly wondering whether we need some sort
> of time-batched flushes because even with lock avoidance the flush path
> really isn't great when called frequently. We can mitigate it further if
> necessary - e.g. by adding an "updated" bitmap so that the flusher doesn't
> have to go around touching the cachelines for all the cpus.

For the memcg stats, I already proposed a batched flush at [1].

I actually did perform the same experiment with the proposed patch
along with [1] and it improves around just 1%. More specifically for
memcg stats [1] is good enough but that is memcg specific and this
patch has merits on its own.

[1] https://lkml.kernel.org/r/20210930044711.2892660-1-shakeelb@google.com

>
> Thanks.

>
> --
> tejun

Re: [PATCH] cgroup: rstat: optimize flush through speculative test

[Tejun Heo]

On Mon, Oct 04, 2021 at 11:07:45AM -0700, Shakeel Butt wrote:
> > Sorry for being so slow but can you point to the exact call path which gets
> > slowed down so significantly?
> 
> This is the mem_cgroup_flush_stats() inside workingset_refault() in
> mm/workingset.c.

I see. Was looking at a repo which was too old.

> > I'm mostly wondering whether we need some sort
> > of time-batched flushes because even with lock avoidance the flush path
> > really isn't great when called frequently. We can mitigate it further if
> > necessary - e.g. by adding an "updated" bitmap so that the flusher doesn't
> > have to go around touching the cachelines for all the cpus.
> 
> For the memcg stats, I already proposed a batched flush at [1].
> 
> I actually did perform the same experiment with the proposed patch
> along with [1] and it improves around just 1%. More specifically for
> memcg stats [1] is good enough but that is memcg specific and this
> patch has merits on its own.

So, the current rstat code doesn't pay a lot of attention to optimizing the
read path - the reasoning being that as long as we avoid O(nr_cgroups), the
flush operations aren't frequent enough to be problematic. The use in
refault path seems to change that balance and it likely is worthwhile to
update rstat accordingly. As I mentioned above, a next step could be adding
a cpumask which tracks cpus with populated updated list, which should add
pretty small cost to the writers while making frequent flushes significantly
cheaper.

What do you think about that approach? While the proposed patch looks fine,
it kinda bothers me that it's a very partial optimization - ie. if flush
frequency is high enough for this to matter, that for_each_possible_cpu()
scanning loop really isn't appropriate.

Thanks.

-- 
tejun

Re: [PATCH] cgroup: rstat: optimize flush through speculative test

[Shakeel Butt]

On Mon, Oct 4, 2021 at 11:21 AM Tejun Heo <tj@kernel.org> wrote:
>
>
[...]
> What do you think about that approach? While the proposed patch looks fine,
> it kinda bothers me that it's a very partial optimization - ie. if flush
> frequency is high enough for this to matter, that for_each_possible_cpu()
> scanning loop really isn't appropriate.
>

Makes sense. I will take a stab at that.