Created attachment 206304 [details]
The original implementation of gcov_stats_reset() uses LIST_FOREACH to traverse the list.
However, because of the remove inside, it has to traverse from the beginning every time after removing node.
We can utilize LIST_FOREACH_SAFE to eliminate such redundant operations.
This change is not correct. Nodes are actually in a tree topology and remove_node() will release parent nodes as it goes, potentially invalidating the traverse (even with FOREACH_SAFE).
The code could be refactored to mark removed nodes as a first pass, and then remove them in a second pass (with plain TAILQ_FOREACH_SAFE). This alternative would avoid wasted work for nodes that are never removed (which is probably the goal of the proposed change), but not break the algorithm.
Created attachment 206319 [details]
gcov_fs patch v2
Use two passes to optimize the traverse.
In the first pass, add all nodes which need to be removed to a queue.
In the second pass, traverse the queue and remove the nodes.
This change isn't quite right either. The remove_node() traversal needs to happen on the first pass. It can mark the nodes for removal during that pass, but cannot remove them from the "all_head" list (nor free them, of course).
The question that comes to mind is, why does this function's performance matter at all? It can only be invoked manually from a sysctl. Does it take material time?
(In reply to Conrad Meyer from comment #3)
I just find this algorithm is a little strange and has redundant operations.
I am not very clear about how to revise it...
remove_node() will remove the node from "all_head" list and free the node, so how to call it in the first pass but just mark the nodes for removal and do not remove or free the nodes?
(In reply to Chuhong Yuan from comment #4)
> (In reply to Conrad Meyer from comment #3)
> I am not very clear about how to revise it...
> remove_node() will remove the node from "all_head" list and free the node,
> so how to call it in the first pass but just mark the nodes for removal and
> do not remove or free the nodes?
You would modify remove_node().
However, if you don't have clear motivation to improve this algorithm (performance does not matter), don't have a good grasp of what the algorithm does, why are you trying to change it?