<div dir="ltr">If the same pid appears in the list multiple times, it makes most sense to put the<div>new entry at the end of the equal range, rather than needlessly scan through it</div><div>to put it at the beginning (which would again be O(n^2) in terms of the range size).</div><div><br></div><div>I could achieve the same semantics by rewriting:</div><div><font face="monospace, monospace"> if (pid_rst_prio_eq(le->pid, new_le->pid))</font><br></div><div>to</div><div><font face="monospace, monospace"> if (!pid_rst_prio(new_le->pid, le->pid))<br></font></div><div>but I thought it's less readable.</div></div><br><div class="gmail_quote"><div dir="ltr">On Fri, Aug 3, 2018 at 1:03 PM Kirill Tkhai <<a href="mailto:ktkhai@virtuozzo.com">ktkhai@virtuozzo.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 03.08.2018 13:25, Radoslaw Burny wrote:<br>
> On Fri, Aug 3, 2018 at 10:11 AM Kirill Tkhai <<a href="mailto:ktkhai@virtuozzo.com" target="_blank">ktkhai@virtuozzo.com</a>> wrote:<br>
> <br>
>> Hi, Radoslaw,<br>
>><br>
>> On 02.08.2018 13:58, Radoslaw Burny wrote:<br>
>>> Since the processes and fds are restored from images in the increasing<br>
>>> order, and they are stored in sorted lists, CRIU always needed (at least<br>
>>> in my experiments) to traverse the whole list before inserting them.<br>
>>> With this change, lists are traversed in reverse, so the fds should be<br>
>>> inserted immediately.<br>
>>><br>
>>> Signed-off-by: Radoslaw Burny <<a href="mailto:rburny@google.com" target="_blank">rburny@google.com</a>><br>
>>> ---<br>
>>> criu/files.c | 12 ++++++------<br>
>>> criu/include/pid.h | 5 +++++<br>
>>> 2 files changed, 11 insertions(+), 6 deletions(-)<br>
>>><br>
>>> diff --git a/criu/files.c b/criu/files.c<br>
>>> index 4ed84305..ea41f59e 100644<br>
>>> --- a/criu/files.c<br>
>>> +++ b/criu/files.c<br>
>>> @@ -140,12 +140,12 @@ static void collect_task_fd(struct<br>
>> fdinfo_list_entry *new_fle, struct rst_info *<br>
>>> struct fdinfo_list_entry *fle;<br>
>>><br>
>>> /* fles in fds list are ordered by fd */<br>
>>> - list_for_each_entry(fle, &ri->fds, ps_list) {<br>
>>> - if (new_fle->fe->fd < fle->fe->fd)<br>
>>> + list_for_each_entry_reverse(fle, &ri->fds, ps_list) {<br>
>>> + if (fle->fe->fd < new_fle->fe->fd)<br>
>>> break;<br>
>>> }<br>
>>><br>
>>> - list_add_tail(&new_fle->ps_list, &fle->ps_list);<br>
>>> + list_add(&new_fle->ps_list, &fle->ps_list);<br>
>><br>
>> Looks OK. Could you add a small comment, that reverse traverse is faster<br>
>> since we keep fles ordered im images?<br>
>><br>
>><br>
> Sure, done. I'll send a new version of the patch in a minute.<br>
> <br>
> <br>
>>> }<br>
>>><br>
>>> unsigned int find_unused_fd(struct pstree_item *task, int hint_fd)<br>
>>> @@ -785,10 +785,10 @@ static void __collect_desc_fle(struct<br>
>> fdinfo_list_entry *new_le, struct file_des<br>
>>> {<br>
>>> struct fdinfo_list_entry *le;<br>
>>><br>
>>> - list_for_each_entry(le, &fdesc->fd_info_head, desc_list)<br>
>>> - if (pid_rst_prio(new_le->pid, le->pid))<br>
>>> + list_for_each_entry_reverse(le, &fdesc->fd_info_head, desc_list)<br>
>>> + if (pid_rst_prio_eq(le->pid, new_le->pid))<br>
>><br>
>> Two fle with equal pids are bug in this place, aren't they?<br>
>> I'd added direct BUG() for that.<br>
>><br>
>><br>
> Actually, I have seen the same (fd, pid) pair appear twice when the process<br>
> had<br>
> stdin & stdout redirected to /dev/null, and /dev/null was injected through<br>
> --inherit-fd.<br>
> (I'm not sure if --inherit-fd is necessary to trigger this scenario)<br>
<br>
Yeah, sure, thanks for explanation. It's possible on simply dup()'ed fds.<br>
<br>
Let me ask you one more question. What is the reason we should care about<br>
"equal" case and to introduce pid_rst_prio_eq()? Can't we use pid_rst_prio()<br>
like we have?<br>
<br>
> <br>
> <br>
>>> break;<br>
>>> - list_add_tail(&new_le->desc_list, &le->desc_list);<br>
>>> + list_add(&new_le->desc_list, &le->desc_list);<br>
>>> }<br>
>>><br>
>>> static void collect_desc_fle(struct fdinfo_list_entry *new_le,<br>
>>> diff --git a/criu/include/pid.h b/criu/include/pid.h<br>
>>> index 81786ec4..c749176f 100644<br>
>>> --- a/criu/include/pid.h<br>
>>> +++ b/criu/include/pid.h<br>
>>> @@ -54,4 +54,9 @@ static inline bool pid_rst_prio(unsigned pid_a,<br>
>> unsigned pid_b)<br>
>>> return pid_a < pid_b;<br>
>>> }<br>
>>><br>
>>> +static inline bool pid_rst_prio_eq(unsigned pid_a, unsigned pid_b)<br>
>>> +{<br>
>>> + return pid_a <= pid_b;<br>
>>> +}<br>
>>> +<br>
>>> #endif /* __CR_PID_H__ */<br>
>><br>
>> Thanks,<br>
>> Kirill<br>
>><br>
> <br>
</blockquote></div>