• Salman's avatar
    pids: fix a race in pid generation that causes pids to be reused immediately · 5fdee8c4
    Salman authored
    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.
    Signed-off-by: default avatarSalman Qazi <sqazi@google.com>
    Cc: Ingo Molnar <mingo@elte.hu>
    Cc: Theodore Ts'o <tytso@mit.edu>
    Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
    Cc: Sukadev Bhattiprolu <sukadev@us.ibm.com>
    Cc: "Eric W. Biederman" <ebiederm@xmission.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    5fdee8c4
pid.c 13.8 KB