[CRIU] [PATCH 2/2] dump: optimize dead_pid_conflict by searching in rbtree

[Andrey Vagin]

From: Andrew Vagin <avagin at virtuozzo.com>

All task are collected in rbtree what allows us to search
any task by a virtual pid for O(n log(n)).

Signed-off-by: Andrew Vagin <avagin at virtuozzo.com>
---
 criu/files-reg.c      | 44 +++++++++++++++++++++-----------------------
 criu/include/pstree.h |  1 +
 criu/pstree.c         |  2 +-
 3 files changed, 23 insertions(+), 24 deletions(-)

diff --git a/criu/files-reg.c b/criu/files-reg.c
index 0fc2598..fd36ae9 100644
--- a/criu/files-reg.c
+++ b/criu/files-reg.c
@@ -806,36 +806,34 @@ static int dump_linked_remap(char *path, int len, const struct stat *ost,
 static pid_t *dead_pids;
 static int n_dead_pids;
 
-static int dead_pid_check_threads(struct pstree_item *item, pid_t pid)
+int dead_pid_conflict(void)
 {
 	int i;
 
-	for (i = 0; i < item->nr_threads; i++) {
-		/*
-		 * If the dead PID was given to a main thread of another
-		 * process, this is handled during restore.
-		 */
-		if (item->pid.real == item->threads[i].real ||
-		    item->threads[i].virt != pid)
-			continue;
+	for (i = 0; i < n_dead_pids; i++) {
+		struct pid *node;
+		pid_t pid = dead_pids[i];
 
-		pr_err("Conflict with a dead task with the same PID as of this thread (virt %d, real %d).\n",
-			item->threads[i].virt, item->threads[i].real);
-		return 1;
-	}
+		node = pstree_pid_by_virt(pid);
+		if (!node)
+			continue;
 
-	return 0;
-}
+		if (node->state != TASK_THREAD) {
+			struct pstree_item *item;
 
-int dead_pid_conflict(void)
-{
-	struct pstree_item *item;
-	int i;
+			/*
+			 * If the dead PID was given to a main thread of another
+			 * process, this is handled during restore.
+			 */
+			item = container_of(node, struct pstree_item, pid);
+			if (item->pid.real == item->threads[i].real ||
+			    item->threads[i].virt != pid)
+				continue;
+		}
 
-	for (i = 0; i < n_dead_pids; i++) {
-		for_each_pstree_item(item)
-			if (dead_pid_check_threads(item, dead_pids[i]))
-				return 1;
+		pr_err("Conflict with a dead task with the same PID as of this thread (virt %d, real %d).\n",
+			node->virt, node->real);
+		return -1;
 	}
 
 	return 0;
diff --git a/criu/include/pstree.h b/criu/include/pstree.h
index afefd67..b51714b 100644
--- a/criu/include/pstree.h
+++ b/criu/include/pstree.h
@@ -68,6 +68,7 @@ extern void init_pstree_helper(struct pstree_item *ret);
 
 extern struct pstree_item *lookup_create_item(pid_t pid);
 extern void pstree_insert_pid(pid_t pid, struct pid *pid_node);
+extern struct pid *pstree_pid_by_virt(pid_t pid);
 
 extern struct pstree_item *root_item;
 extern struct pstree_item *pstree_item_next(struct pstree_item *item);
diff --git a/criu/pstree.c b/criu/pstree.c
index 7a30ab8..49142f2 100644
--- a/criu/pstree.c
+++ b/criu/pstree.c
@@ -433,7 +433,7 @@ struct pstree_item *lookup_create_item(pid_t pid)
 	return container_of(node, struct pstree_item, pid);
 }
 
-static struct pid *pstree_pid_by_virt(pid_t pid)
+struct pid *pstree_pid_by_virt(pid_t pid)
 {
 	struct rb_node *node = pid_root_rb.rb_node;
 
-- 
2.7.4