[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20240226190741.66233-1-kuniyu@amazon.com>
Date: Mon, 26 Feb 2024 11:07:41 -0800
From: Kuniyuki Iwashima <kuniyu@...zon.com>
To: <kuba@...nel.org>
CC: <davem@...emloft.net>, <edumazet@...gle.com>, <kuni1840@...il.com>,
<kuniyu@...zon.com>, <netdev@...r.kernel.org>, <pabeni@...hat.com>
Subject: Re: [PATCH v3 net-next 05/14] af_unix: Detect Strongly Connected Components.
From: Jakub Kicinski <kuba@...nel.org>
Date: Sat, 24 Feb 2024 16:34:30 -0800
> On Fri, 23 Feb 2024 13:39:54 -0800 Kuniyuki Iwashima wrote:
> > + list_for_each_entry(edge, &vertex->edges, vertex_entry) {
> > + struct unix_vertex *next_vertex = edge->successor->vertex;
> > +
> > + if (!next_vertex)
> > + continue;
> > +
> > + if (next_vertex->index == UNIX_VERTEX_INDEX_UNVISITED) {
> > + list_add(&edge->stack_entry, &edge_stack);
> > +
> > + vertex = next_vertex;
> > + goto next_vertex;
> > +prev_vertex:
> > + next_vertex = vertex;
> > +
> > + edge = list_first_entry(&edge_stack, typeof(*edge), stack_entry);
> > + list_del_init(&edge->stack_entry);
> > +
> > + vertex = edge->predecessor->vertex;
> > +
> > + vertex->lowlink = min(vertex->lowlink, next_vertex->lowlink);
> > + } else if (edge->successor->vertex->on_stack) {
> > + vertex->lowlink = min(vertex->lowlink, next_vertex->index);
> > + }
> > + }
> > +
> > + if (vertex->index == vertex->lowlink) {
> > + struct list_head scc;
> > +
> > + __list_cut_position(&scc, &vertex_stack, &vertex->scc_entry);
> > +
> > + list_for_each_entry_reverse(vertex, &scc, scc_entry) {
> > + list_move_tail(&vertex->entry, &unix_visited_vertices);
> > +
> > + vertex->on_stack = false;
> > + }
> > +
> > + list_del(&scc);
> > + }
> > +
> > + if (!list_empty(&edge_stack))
> > + goto prev_vertex;
>
> coccicheck says:
>
> net/unix/garbage.c:406:17-23: ERROR: invalid reference to the index variable of the iterator on line 425
>
> this code looks way to complicated to untangle on a quick weekend scan,
> so please LMK if this is a false positive, I'll hide the patches from
> patchwork for now ;)
Yeah, I think it's false positive :)
The code above implements recursion withtout nesting call stack
and instead uses goto jump and restores the previous in-loop
variables there.
__unix_walk_scc(struct unix_vertex *vertex)
{
...
list_for_each_entry(edge, &vertex->edges, vertex_entry) {
if (next_vertex->index == UNIX_VERTEX_INDEX_UNVISITED) {
__unix_walk_scc(next_vertex);
^-- This is rewritten with goto next_vertex & prev_vertex.
vertex->lowlink = min(vertex->lowlink, next_vertex->lowlink);
} else {
vertex->lowlink = min(vertex->lowlink, next_vertex->index);
}
}
...
Here's the original recursive pseudocode.
https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
Powered by blists - more mailing lists