linux-kernel - Re: [PATCH-cgroup v5 1/2] cgroup/rstat: Optimize cgroup_rstat_updated

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Fri, 1 Dec 2023 07:37:49 -1000
From:   Tejun Heo <tj@...nel.org>
To:     Waiman Long <longman@...hat.com>
Cc:     Zefan Li <lizefan.x@...edance.com>,
        Johannes Weiner <hannes@...xchg.org>, cgroups@...r.kernel.org,
        linux-kernel@...r.kernel.org, Joe Mario <jmario@...hat.com>,
        Sebastian Jug <sejug@...hat.com>,
        Yosry Ahmed <yosryahmed@...gle.com>
Subject: Re: [PATCH-cgroup v5 1/2] cgroup/rstat: Optimize
 cgroup_rstat_updated_list()

On Thu, Nov 30, 2023 at 03:43:26PM -0500, Waiman Long wrote:
> 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@...hat.com>

Applied to cgroup/for-6.8 with a small comment edit.

...
> + * Iteratively traverse down the cgroup_rstat_cpu updated tree level by
> + * level and push all the parents first before their next level children
> + * into a singly linked list built from the tail backward like "pushing"
> + * cgroups into a stack. The parent is by the caller.

I found the last sentence a bit difficult to understand and changed it to
"The root is pushed by the caller." That's what you meant, right?

Thanks.

-- 
tejun