Fix a race in pid generation that causes pids to be reused immediately.
in [Kernel]
|
Prev: [PATCH] zorro: Fix reading of proc/bus/zorro/* in small chunks
Next: Ext2/3 Filesystem Analysis
From: Linus Torvalds on 9 Jun 2010 13:50 On Wed, 9 Jun 2010, tytso(a)mit.edu wrote: > > Well, I was thinking about something like this: No, this is wrong for the case where you end up having to allocate a new pidmap and/or overflow max_pid. It also doesn't set the bit at all. > There appears to be some interesting uses of the bitmap by > find_ge_pid() and next_pidmap() that I haven't completely grokked yet, We need that bitmap to handle the overflow max_pid case. We are _not_ returning just increasing pid numbers. 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: Linus Torvalds on 9 Jun 2010 17:30 On Wed, 9 Jun 2010, Salman wrote: > +/* > + * If we started walking pids at 'base', is 'a' seen before 'b'? > + * > + */ > +static int pid_before(int base, int a, int b) > +{ > + int a_lt_b = (a < b); > + int min_a_b = min(a, b); > + int max_a_b = max(a, b); > + > + if ((base <= min_a_b) || (base >= max_a_b)) > + return a_lt_b; > + > + return !a_lt_b; > +} Ok, so that's a very confusing expression. I'm sure it gets the right value, but it's not exactly straightforward, is it? Wouldn't it be nicer to write it out in a more straightforward way? Something like /* a and b in order? base must not be between them */ if (a <= b) return (base <= a || base >= b); /* b < a? We reach 'a' first iff base is between them */ return base >= b && base <= a; would seem to be equivalent and easier to explain, no? And when you write it that way, it looks like the compiler should be able to trivially CSE the five comparisons down to just three (notice how the "base <= a" and "base >= b" comparisons are repeated. Which I'm sure some super-optimizing compiler can do from your version too, but mine seems more straightforward. But maybe I did that thing wrong, and I just confused myself. I have _not_ checked the logic deeply, somebody else should definitely double-check me. 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: Peter Zijlstra on 9 Jun 2010 17:40 On Wed, 2010-06-09 at 14:21 -0700, Linus Torvalds wrote: > > On Wed, 9 Jun 2010, Salman wrote: > > +/* > > + * If we started walking pids at 'base', is 'a' seen before 'b'? > > + * > > + */ > > +static int pid_before(int base, int a, int b) > > +{ > > + int a_lt_b = (a < b); > > + int min_a_b = min(a, b); > > + int max_a_b = max(a, b); > > + > > + if ((base <= min_a_b) || (base >= max_a_b)) > > + return a_lt_b; > > + > > + return !a_lt_b; > > +} > > Ok, so that's a very confusing expression. I'm sure it gets the right > value, but it's not exactly straightforward, is it? > > Wouldn't it be nicer to write it out in a more straightforward way? > Something like > > /* a and b in order? base must not be between them */ > if (a <= b) > return (base <= a || base >= b); > /* b < a? We reach 'a' first iff base is between them */ > return base >= b && base <= a; > > would seem to be equivalent and easier to explain, no? > > And when you write it that way, it looks like the compiler should be able > to trivially CSE the five comparisons down to just three (notice how the > "base <= a" and "base >= b" comparisons are repeated. Which I'm sure some > super-optimizing compiler can do from your version too, but mine seems > more straightforward. > > But maybe I did that thing wrong, and I just confused myself. I have _not_ > checked the logic deeply, somebody else should definitely double-check me. Isn't: return a - base < b - base, the natural way to express this? -- 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 9 Jun 2010 18:30 On Wed, 9 Jun 2010, Peter Zijlstra wrote: > > Isn't: return a - base < b - base, the natural way to express this? 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. 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: tytso on 10 Jun 2010 16:40
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? 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? - 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/ |