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

[Radoslaw Burny]

On Fri, Aug 3, 2018 at 10:11 AM Kirill Tkhai <ktkhai at virtuozzo.com> wrote:

> 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?
>
>
Sure, done. I'll send a new version of the patch in a minute.


> >  }
> >
> >  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.
>
>
Actually, I have seen the same (fd, pid) pair appear twice when the process
had
stdin & stdout redirected to /dev/null, and /dev/null was injected through
--inherit-fd.
(I'm not sure if --inherit-fd is necessary to trigger this scenario)



> >                       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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openvz.org/pipermail/criu/attachments/20180803/cf2399ba/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4843 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://lists.openvz.org/pipermail/criu/attachments/20180803/cf2399ba/attachment.p7s>