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

[Kirill Tkhai]

On 03.08.2018 13:13, Radoslaw Burny wrote:
> 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>

Looks good for me. Thanks.

Acked-by: Kirill Tkhai <ktkhai at virtuozzo.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__ */
>