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