cgroup/rstat: Optimize cgroup_rstat_updated_list()
authorWaiman Long <longman@redhat.com>
Thu, 30 Nov 2023 20:43:26 +0000 (15:43 -0500)
committerTejun Heo <tj@kernel.org>
Fri, 1 Dec 2023 17:40:04 +0000 (07:40 -1000)
commitd499fd418fa15949d86d28bb5442ab88203fc513
treea4f6e93180f287dbed56286e6b73037fad66745b
parent7b91eb6000104c450ebd7af5771ac305691b6fee
cgroup/rstat: Optimize cgroup_rstat_updated_list()

The current design of cgroup_rstat_cpu_pop_updated() is to traverse
the updated tree in a way to pop out the leaf nodes first before
their parents. This can cause traversal of multiple nodes before a
leaf node can be found and popped out. IOW, a given node in the tree
can be visited multiple times before the whole operation is done. So
it is not very efficient and the code can be hard to read.

With the introduction of cgroup_rstat_updated_list() to build a list
of cgroups to be flushed first before any flushing operation is being
done, we can optimize the way the updated tree nodes are being popped
by pushing the parents first to the tail end of the list before their
children. In this way, most updated tree nodes will be visited only
once with the exception of the subtree root as we still need to go
back to its parent and popped it out of its updated_children list.
This also makes the code easier to read.

Signed-off-by: Waiman Long <longman@redhat.com>
Signed-off-by: Tejun Heo <tj@kernel.org>
kernel/cgroup/rstat.c