Re: Fwd: [Lse-tech] get_pid() performance fix

[Hubertus Franke <frankeh@watson.ibm.com>]

On Tuesday 05 March 2002 03:10 pm, OGAWA Hirofumi wrote:
> Hubertus Franke <frankeh@watson.ibm.com> writes:
> > > I said:
> > > 	task { pid = 300, pgrp = 301, };
> > > 	301 is free;
> > >
> > > 	get_pid() returns 301.
> > >
> > > "task 301" can't call setsid(). pid 301 is available?
> >
> > The original code is/was:
> >
> >                         if(p->pid == last_pid   ||
> >                            p->pgrp == last_pid  ||
> >                            p->tgid == last_pid  ||
> >                            p->session == last_pid) {
> >                                 if(++last_pid >= next_safe) {
> >                                         if(last_pid & 0xffff8000)
> >                                                 last_pid = 300;
> >                                         next_safe = PID_MAX;
> >                                 }
> >                                 goto repeat;
> >                         }
> >
> > if any process holds the pgrp=301 as in your case, 301 won't be eligible
> > due to (p->pgrp == last_pid) check.
>
> I know.
>
> > @@ -153,13 +155,18 @@
> >                               if(last_pid & 0xffff8000)
> >                                     last_pid = 300;
> >                               next_safe = PID_MAX;
> > +                             goto repeat;
> >                         }
> > -                       goto repeat;
> > +                       if(unlikely(last_pid == beginpid))
> > +                             goto nomorepids;
> > +                       continue;
>
> You changed it. No?

Yes, we changed but only the logic that once a pid is busy we start searching 
for every task again. This is exactly the O(n**2) problem.
Run the program and you'll see.

-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)