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

[Kirill Tkhai]

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

Yeah, sure, thanks for explanation. It's possible on simply dup()'ed fds.

Let me ask you one more question. What is the reason we should care about
"equal" case and to introduce pid_rst_prio_eq()? Can't we use pid_rst_prio()
like we have?

> 
> 
>>>                       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
>>
>