@@ -37,7 +37,6 @@ struct unix_vertex {
unsigned long out_degree;
unsigned long index;
unsigned long lowlink;
- bool on_stack;
};
struct unix_edge {
@@ -112,16 +112,20 @@ static struct unix_vertex *unix_edge_successor(struct unix_edge *edge)
static LIST_HEAD(unix_unvisited_vertices);
enum unix_vertex_index {
- UNIX_VERTEX_INDEX_UNVISITED,
+ UNIX_VERTEX_INDEX_MARK1,
+ UNIX_VERTEX_INDEX_MARK2,
UNIX_VERTEX_INDEX_START,
};
+static unsigned long unix_vertex_unvisited_index = UNIX_VERTEX_INDEX_MARK1;
+
static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
{
struct unix_vertex *vertex = edge->predecessor->vertex;
if (!vertex) {
vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry);
+ vertex->index = unix_vertex_unvisited_index;
vertex->out_degree = 0;
INIT_LIST_HEAD(&vertex->edges);
@@ -266,6 +270,7 @@ void unix_destroy_fpl(struct scm_fp_list *fpl)
}
static LIST_HEAD(unix_visited_vertices);
+static unsigned long unix_vertex_grouped_index = UNIX_VERTEX_INDEX_MARK2;
static void __unix_walk_scc(struct unix_vertex *vertex)
{
@@ -279,7 +284,6 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
vertex->lowlink = index;
index++;
- vertex->on_stack = true;
list_add(&vertex->scc_entry, &vertex_stack);
list_for_each_entry(edge, &vertex->edges, vertex_entry) {
@@ -288,7 +292,7 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
if (!next_vertex)
continue;
- if (next_vertex->index == UNIX_VERTEX_INDEX_UNVISITED) {
+ if (next_vertex->index == unix_vertex_unvisited_index) {
list_add(&edge->stack_entry, &edge_stack);
vertex = next_vertex;
@@ -302,7 +306,7 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
vertex = edge->predecessor->vertex;
vertex->lowlink = min(vertex->lowlink, next_vertex->lowlink);
- } else if (edge->successor->vertex->on_stack) {
+ } else if (next_vertex->index != unix_vertex_grouped_index) {
vertex->lowlink = min(vertex->lowlink, next_vertex->index);
}
}
@@ -315,7 +319,7 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
list_for_each_entry_reverse(vertex, &scc, scc_entry) {
list_move_tail(&vertex->entry, &unix_visited_vertices);
- vertex->on_stack = false;
+ vertex->index = unix_vertex_grouped_index;
}
list_del(&scc);
@@ -327,17 +331,15 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
static void unix_walk_scc(void)
{
- struct unix_vertex *vertex;
-
- list_for_each_entry(vertex, &unix_unvisited_vertices, entry)
- vertex->index = UNIX_VERTEX_INDEX_UNVISITED;
-
while (!list_empty(&unix_unvisited_vertices)) {
+ struct unix_vertex *vertex;
+
vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
__unix_walk_scc(vertex);
}
list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
+ swap(unix_vertex_unvisited_index, unix_vertex_grouped_index);
}
static LIST_HEAD(gc_candidates);
Before starting Tarjan's algorithm, we need to mark all vertices as unvisited. We can save this O(n) setup by reserving two special indices (0, 1) and using two variables. The first time we link a vertex to unix_unvisited_vertices, we set unix_vertex_unvisited_index to index. During DFS, we can see that the index of unvisited vertices is the same as unix_vertex_unvisited_index. When we finalise SCC later, we set unix_vertex_grouped_index to each vertex's index. Then, we can know (i) that the vertex is on the stack if the index of a visited vertex is >= 2 and (ii) that it is not on the stack and belongs to a different SCC if the index is unix_vertex_grouped_index. After the whole algorithm, all indices of vertices are set as unix_vertex_grouped_index. Next time we start DFS, we know that all unvisited vertices have unix_vertex_grouped_index, and we can use unix_vertex_unvisited_index as the not-on-stack marker. To use the same variable in __unix_walk_scc(), we can swap unix_vertex_(grouped|unvisited)_index at the end of Tarjan's algorithm. Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com> --- include/net/af_unix.h | 1 - net/unix/garbage.c | 22 ++++++++++++---------- 2 files changed, 12 insertions(+), 11 deletions(-)