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

[Andrei Vagin]

On Fri, Aug 03, 2018 at 04:59:14PM +0300, Kirill Tkhai wrote:
> 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>

Applied, thanks!

> 
> > ---
> >  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__ */
> > 
> _______________________________________________
> CRIU mailing list
> CRIU at openvz.org
> https://lists.openvz.org/mailman/listinfo/criu