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

[Kirill Tkhai]

Hi, Radoslaw,

On 02.08.2018 13:58, 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>
> ---
>  criu/files.c       | 12 ++++++------
>  criu/include/pid.h |  5 +++++
>  2 files changed, 11 insertions(+), 6 deletions(-)
> 
> diff --git a/criu/files.c b/criu/files.c
> index 4ed84305..ea41f59e 100644
> --- a/criu/files.c
> +++ b/criu/files.c
> @@ -140,12 +140,12 @@ 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)
> +	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);

Looks OK. Could you add a small comment, that reverse traverse is faster
since we keep fles ordered im images?

>  }
>  
>  unsigned int find_unused_fd(struct pstree_item *task, int hint_fd)
> @@ -785,10 +785,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))

Two fle with equal pids are bug in this place, aren't they?
I'd added direct BUG() for that.

>  			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__ */

Thanks,
Kirill