Skip to contentSkip to conversation

Fix a race in pid generation that causes pids to be reused immediately.

PATCH In review Salman 3 participants 9 messages Jun 9, 2010 – Jun 10, 2010 1 message not in the archive

lore
Share & tools
lore

Salman

author
#0 lore raw

PATCH 1/1 Fix a race in pid generation that causes pids to be reused immediately.

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.

Race Description:

A B

// pid == offset == n // pid == offset == n + 1
test_and_set_bit(offset, map->page)

                                     test_and_set_bit(offset, map->page);
                                     pid_ns->last_pid = pid;
pid_ns->last_pid = pid;
                                     // pid == n + 1 is freed (wait())

                                     // Next fork()...
                                     last = pid_ns->last_pid; // == n
                                     pid = last + 1;

Code to reproduce it (Running multiple instances is more effective):

#include <errno.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

// The distance mod 32768 between two pids, where the first pid is expected // to be smaller than the second.
int PidDistance(pid_t first, pid_t second) {
return (second + 32768 - first) % 32768;
}

int main(int argc, char* argv[]) {
int failed = 0;
pid_t last_pid = 0;
int i;
printf("%d\n", sizeof(pid_t));

  for (i = 0; i < 10000000; ++i) {
    if (i % 32786 == 0)
      printf("Iter: %d\n", i/32768);
    int child_exit_code = i % 256;
    pid_t pid = fork();
    if (pid == -1) {
      fprintf(stderr, "fork failed, iteration %d, errno=%d", i, errno);
      exit(1);
    }
    if (pid == 0) {
      // Child
      exit(child_exit_code);
    } else {
      // Parent
      if (i > 0) {
        int distance = PidDistance(last_pid, pid);
        if (distance == 0 || distance > 30000) {
          fprintf(stderr,
                  "Unexpected pid sequence: previous fork: pid=%d, "
                  "current fork: pid=%d for iteration=%d.\n",
                  last_pid, pid, i);
          failed = 1;
        }
      }
      last_pid = pid;
      int status;
      int reaped = wait(&status);
      if (reaped != pid) {
        fprintf(stderr,
                "Wait return value: expected pid=%d, "
                "got %d, iteration %d\n",
                pid, reaped, i);
        failed = 1;
      } else if (WEXITSTATUS(status) != child_exit_code) {
        fprintf(stderr,
                "Unexpected exit status %x, iteration %d\n",
                WEXITSTATUS(status), i);
        failed = 1;
      }
    }

}
exit(failed);
}

Thanks to Ted Tso for the key ideas of this implementation.

---
 kernel/pid.c |   39 ++++++++++++++++++++++++++++++++++++++-
 1 files changed, 38 insertions(+), 1 deletions(-)
kernel/pid.c +38 -1
index e9fd8c1..865a482 100644
@@ -122,6 +122,22 @@ static void free_pidmap(struct upid *upid)
 	atomic_inc(&map->nr_free);
 }
 
+/*
+ * 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;
+}
+
 static int alloc_pidmap(struct pid_namespace *pid_ns)
 {
 	int i, offset, max_scan, pid, last = pid_ns->last_pid;
@@ -153,8 +169,29 @@ static int alloc_pidmap(struct pid_namespace *pid_ns)
 		if (likely(atomic_read(&map->nr_free))) {
 			do {
 				if (!test_and_set_bit(offset, map->page)) {
+					int prev;
+					int last_write = last;
 					atomic_dec(&map->nr_free);
-					pid_ns->last_pid = pid;
+
+					/*
+					 * We might be racing with someone else trying
+					 * to set pid_ns->last_pid.  We want the
+					 * the winner to have the "later" value,
+					 * because if the "earlier" value prevails, then
+					 * a pid may get reused immediately.
+					 *
+					 * Since pids rollover, it is not sufficent
+					 * to just pick the bigger value.  We
+					 * have to consider where we started counting
+					 * from.
+					 */
+					do {
+						prev = last_write;
+						last_write = cmpxchg(&pid_ns->last_pid,
+							       prev, pid);
+					} while ((prev != last_write) &&
+						 (pid_before(last, last_write, pid)));
+
 					return pid;
 				}
 				offset = find_next_offset(map, offset);
#1 lore raw
Quoted 5 lines · Salman
kernel/pid.c +5 -0
+/*
+ * If we started walking pids at 'base', is 'a' seen before 'b'?
+ *
+ */
+static int pid_before(int base, int a, int b)

kernel/pid.c static void free_pidmap(struct upid *upid) · line 139

Quoted 10 lines
kernel/pid.c +10 -0
+{
+	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

#2 lore raw
Quoted 32 lines · Linus Torvalds
Quoted 5 lines · Salman
kernel/pid.c +5 -0
+/*
+ * If we started walking pids at 'base', is 'a' seen before 'b'?
+ *
+ */
+static int pid_before(int base, int a, int b)

kernel/pid.c static void free_pidmap(struct upid *upid) · line 139

Quoted 10 lines
kernel/pid.c +10 -0
+{
+	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?

Quoted 8 lines

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?

#3 lore raw
Quoted 2 lines · Peter Zijlstra

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

#4 lore raw
Quoted 3 lines · Linus Torvalds

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.

Linus

#5 lore raw
Quoted 11 lines · Linus Torvalds
Quoted 3 lines · Linus Torvalds

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?
.

Quoted 5 lines

                       Linus

#6 lore raw
Quoted 5 lines · Salman Qazi

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.

Quoted 2 lines

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.

Linus

A message that is not in the archive (sent off-list or not yet received): [email protected]

#8 lore raw
Quoted 18 lines · Michel Lespinasse
Quoted 8 lines · Linus Torvalds
Quoted 5 lines · Salman Qazi

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.

Quoted 7 lines

Right you are.

Quoted 2 lines

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.

Quoted 8 lines

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?

Quoted 5 lines

--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

#9 lore raw
Quoted 5 lines · Salman Qazi
Quoted 4 lines · Michel Lespinasse

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.

Quoted 6 lines
Quoted 6 lines

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.

Quoted 2 lines

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