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

[Kirill Tkhai]

On 03.08.2018 14:34, Radoslaw Burny wrote:
> If the same pid appears in the list multiple times, it makes most sense to
> put the
> new entry at the end of the  equal range, rather than needlessly scan
> through it
> to put it at the beginning (which would again be O(n^2) in terms of the
> range size).
> 
> I could achieve the same semantics by rewriting:
>  if (pid_rst_prio_eq(le->pid, new_le->pid))
> to
>  if (!pid_rst_prio(new_le->pid, le->pid))
> but I thought it's less readable.

Then I'm OK with new function. Though, the name is not intuitive for me,
but this is up to Andrey.

> On Fri, Aug 3, 2018 at 1:03 PM Kirill Tkhai <ktkhai at virtuozzo.com> wrote:
> 
>> 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
>>>>
>>>
>>
>