[CRIU] [PATCH 1/1] Fix O(n^2) restore in terms of the number of fds.

[Radoslaw Burny]

Since the processes and fds are restored from images in the increasing
order, and they are stored in sorted lists, CRIU always needed (at least
in my experiments) to traverse the whole list before inserting them.
With this change, lists are traversed in reverse, so the fds should be
inserted immediately.

Signed-off-by: Radoslaw Burny <rburny at google.com>
---
 criu/files.c       | 18 +++++++++++-------
 criu/include/pid.h |  5 +++++
 2 files changed, 16 insertions(+), 7 deletions(-)

diff --git a/criu/files.c b/criu/files.c
index 4585395a..13f40fa3 100644
--- a/criu/files.c
+++ b/criu/files.c
@@ -139,13 +139,17 @@ static void collect_task_fd(struct fdinfo_list_entry *new_fle, struct rst_info *
 {
 	struct fdinfo_list_entry *fle;
 
-	/* fles in fds list are ordered by fd */
-	list_for_each_entry(fle, &ri->fds, ps_list) {
-		if (new_fle->fe->fd < fle->fe->fd)
+        /*
+         * fles in fds list are ordered by fd. Fds are restored from img files
+         * in ascending order, so it is faster to insert them from the end of
+         * the list.
+         */
+        list_for_each_entry_reverse(fle, &ri->fds, ps_list) {
+		if (fle->fe->fd < new_fle->fe->fd)
 			break;
 	}
 
-	list_add_tail(&new_fle->ps_list, &fle->ps_list);
+	list_add(&new_fle->ps_list, &fle->ps_list);
 }
 
 unsigned int find_unused_fd(struct pstree_item *task, int hint_fd)
@@ -778,10 +782,10 @@ static void __collect_desc_fle(struct fdinfo_list_entry *new_le, struct file_des
 {
 	struct fdinfo_list_entry *le;
 
-	list_for_each_entry(le, &fdesc->fd_info_head, desc_list)
-		if (pid_rst_prio(new_le->pid, le->pid))
+	list_for_each_entry_reverse(le, &fdesc->fd_info_head, desc_list)
+		if (pid_rst_prio_eq(le->pid, new_le->pid))
 			break;
-	list_add_tail(&new_le->desc_list, &le->desc_list);
+	list_add(&new_le->desc_list, &le->desc_list);
 }
 
 static void collect_desc_fle(struct fdinfo_list_entry *new_le,
diff --git a/criu/include/pid.h b/criu/include/pid.h
index 81786ec4..c749176f 100644
--- a/criu/include/pid.h
+++ b/criu/include/pid.h
@@ -54,4 +54,9 @@ static inline bool pid_rst_prio(unsigned pid_a, unsigned pid_b)
 	return pid_a < pid_b;
 }
 
+static inline bool pid_rst_prio_eq(unsigned pid_a, unsigned pid_b)
+{
+	return pid_a <= pid_b;
+}
+
 #endif /* __CR_PID_H__ */
-- 
2.18.0.597.ga71716f1ad-goog