Fix a race in pid generation that causes pids to be reused immediately.
in [Kernel]
|
Prev: [patch] add quirk to fix volume wheel on Toshiba U300 laptops
Next: [tip:perf/core] x86: Unify save_stack_address() and save_stack_address_nosched()
From: Salman Qazi on 9 Jun 2010 14:20 On Wed, Jun 9, 2010 at 10:47 AM, <tytso(a)mit.edu> wrote: > On Wed, Jun 09, 2010 at 10:43:33AM -0700, Linus Torvalds wrote: >> >> We need that bitmap to handle the overflow max_pid case. We are _not_ >> returning just increasing pid numbers. > > Doh! �I knew I was forgetting something obvious. �I was hoping we > could get rid of the bitmap entirely, but I guess not.... > > (Unless users would stand for 64-bit pid numbers... no? �Dang. :-) > > � � � � � � � � � � � � � � � � � � �- Ted > (sorry about the previous message, to those who got it... my mail client silently switched to HTML mode) I am working on a new version of the change taking into account comments (both about substance and style) by Michel, Ted and Linus. I agree with Michel in that I am not sure that the rare case of same last_pid being set by two threads is worth fixing. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Salman Qazi on 9 Jun 2010 20:10 On Wed, Jun 9, 2010 at 3:27 PM, Linus Torvalds <torvalds(a)linux-foundation.org> wrote: > > > On Wed, 9 Jun 2010, Linus Torvalds wrote: >> >> Quite possibly. I'd worry about the overflow case a bit, but it's >> certainly going to get the right value when base << MAX_INT. > > Having given it a couple of seconds more thought, I don't think there is > an overflow case either. All of a/b/base are guaranteed to be non-negative > (or our pid code is in worse trouble anyway), so there is no overflow > possible. So yes. Just comparing a-base < b-base should always be safe I don't think this gives the right answer in the a < base < b case. Here a - base < 0 and b - base > 0. But we really want b to be before a, since a has rolled over further than b. I think the right solution is comparing (a - base + max_pid) % max_pid with (b - base + max_pid) % max_pid. Am I correct or deluded? .. > > � � � � � � � � � � � �Linus > > > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Salman Qazi on 10 Jun 2010 02:00 On Wed, Jun 9, 2010 at 10:17 PM, Michel Lespinasse <walken(a)google.com> wrote: > On Wed, Jun 9, 2010 at 5:20 PM, Linus Torvalds > <torvalds(a)linux-foundation.org> wrote: >> >> On Wed, 9 Jun 2010, Salman Qazi wrote: >> > >> > I don't think this gives the right answer in the a < base < b �case. >> > Here a - base < 0 and >> > b - base > 0. �But we really want b to be before a, since a has rolled >> > over further than b. >> >> Right you are. >> >> > I think the right solution is comparing (a - base + max_pid) % max_pid >> > with (b - base + max_pid) % max_pid. �Am I correct or deluded? . >> >> That would work, but it would be horrible. Just use the three compares >> version: doing a integer 'mod' operator is _way_ more expensive. > > As shown by the three compares version, the question here does not depend on > the max_pid value. So, we can replace max_pid with any integer >= max_pid > without changing the result. This is nice because, replacing max_pid with > 2^32, the expression simplifies to: > > (unsigned)(a - base) < (unsigned)(b - base) > > I think I like this form after all :) I don't mind doing this, if nobody disagrees. Should be fine with a comment on top explaining the intention? > > -- > Michel "Walken" Lespinasse > A program is never fully debugged until the last user dies. > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Linus Torvalds on 10 Jun 2010 12:40 On Wed, Jun 9, 2010 at 10:55 PM, Salman Qazi <sqazi(a)google.com> wrote: > On Wed, Jun 9, 2010 at 10:17 PM, Michel Lespinasse <walken(a)google.com> wrote: >> >> As shown by the three compares version, the question here does not depend on >> the max_pid value. So, we can replace max_pid with any integer >= max_pid >> without changing the result. I like the logical argument, and cannot fault it. >> This is nice because, replacing max_pid with >> 2^32, the expression simplifies to: >> >> (unsigned)(a - base) < (unsigned)(b - base) >> >> I think I like this form after all :) Sounds right to me. > I don't mind doing this, if nobody disagrees. �Should be fine with a > comment on top explaining the intention? Yes. And lots of testing (including, very much, the whole max_pid roll-over, of course). The logic of it all seems impeccable, but nothing beats testing. Thanks, Linus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Salman Qazi on 10 Jun 2010 17:10
On Thu, Jun 10, 2010 at 1:38 PM, <tytso(a)mit.edu> wrote: > On Thu, Jun 10, 2010 at 01:09:11PM -0700, Salman wrote: >> A program that repeatedly forks and waits is susceptible to having the >> same pid repeated, especially when it competes with another instance of the >> same program. �This is really bad for bash implementation. �Furthermore, many shell >> scripts assume that pid numbers will not be used for some length of time. > > This should probably get wrapped at column 74 or so.... > >> +static int pid_before(int base, int a, int b) >> +{ >> + � � /* >> + � � �* This is the same as saying >> + � � �* >> + � � �* (a - base + MAXUINT) % MAXUINT < (b - base + MAXUINT) % MAXUINT >> + � � �* and that mapping orders 'a' and 'b' with respect to 'base'. >> + � � �* >> + � � �*/ >> + � � return (unsigned)(a - base) < (unsigned)(b - base); >> +} > > Does this work though if /proc/sys/kernel/pid_max is not set to > MAXUINT? Yes it does. It should work for all values of pid_max. > > I like the optimization, but it looks like pid_max defaults to 4096 if > CONFIG_BASE_SMALL is set, and 32768 otherwise. > > Am I missing something? Yes. (a - base + pid_max) % pid_max < (b - base + max_pid) % pid_max iff (a - base + MAXUINT) % MAXUINT < (b - base + MAXUINT) % MAXUINT for all pid_max <= MAXUINT. The values of 'a' (or 'b') in the range [base, pid_max) gets mapped to [0, pid_max - base) and the range [0, base) gets mapped to [MAXUINT, MAXUINT - base). So, the order is essentially maintained by this mapping. > > � � � � � � � � � � � � � � � � � � � �- Ted > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |