Recursive C mergesort hangs on read using pipe/forks

Question

I'm trying to create a mergesort an array of 800 ints using a system of recursive forks so that each of the bottom-most children (8 total) qsort 100 each, then pass the array back up to their respective parent processes to be merge sorted and passed up again.

For some reason the function hangs after the first set of bottom-most children finish writing to their parent process.

My recursive fork function that takes in the initial array of 800...

static void forkSort(int* parentNums, int size)
{
    printf("PPid:%ld Pid:%ld Size:%d\n", (long)getppid(), (long)getpid(), size);
    int childNums[size/2], fd[2], left, right;

    if(size <= 100) //Send sorted array to parent thru pipe
    {
        qsort(parentNums, size, sizeof(int), compare);
        write(fd[1], &parentNums, sizeof(parentNums));
        exit(0);
    }
    if (pipe(fd)==-1){perror("Failed");}

    size /= 2;
    if(!(left = tryFork()) || !(right = tryFork())) //Children
    {
        if(left)    copy(childNums, parentNums, size);
        else        copy(childNums, parentNums + size, size);

        forkSort(childNums, size);
    }
    //Parents
    int first[size], second[size], combined[size*2];
    read(fd[0], first, sizeof(first));
    read(fd[0], second, sizeof(second));

    mergeSort(first, second, combined, size);
    if(size*2 == SIZE) //Finished, write to out.dat
        printArray(combined, SIZE);
    else
        write(fd[0], combined, sizeof(combined));
}

Answer 1

There's a couple of things wrong with your code (I must add that this was fun to look at).

A) you should exit() and not just return in the client code. Otherwise you'll continue execution, especially when you do recursion.

B) You need to pass the write end of the pipe to your clients so they know where to write too. I added this as a parameter to forkSort().

C) When size is <= 100, you do a sizeof(parentNums) this turns into a sizeof(int*), the correct way is: sizeof(int)*size.

D) When you write back a merged set of ints you only write the first part and you write it to the read end of the pipe. The correct call would be: write(write_fd, combined, sizeof(combined));.

E) I removed the wait(NULL) call since I didn't see the point. Synchronization will be done by the read() and write() calls.

Here's my proposal:

static void forkSort(int* parentNums, int size, int write_fd)
{
  int fd[2];
  printf("PPid:%ld Pid:%ld Size:%d\n", (long)getppid(), (long)getpid(), size);
  int childNums[size/2], left, right;
  if(size <= 100) //Send sorted array to parent thru pipe
    {
      qsort(parentNums, size, sizeof(int), compare);
      write(write_fd, parentNums, size*sizeof(int));
      exit(0);
    }
  if (pipe(fd)==-1){perror("Failed");}

  printf("Creating child processes...\n");
  size /= 2;

  if(!(left = tryFork()) || !(right = tryFork())) //Children
  {
      if(left)    copy(childNums, parentNums, size);
      else        copy(childNums, parentNums + size, size);
      forkSort(childNums, size, fd[1]);
  }

  /* parent */
  int first[size], second[size], combined[size*2];
  read(fd[0], first, sizeof(first));
  read(fd[0], second, sizeof(second));
  printf("\n\nMerge sorting...  Size:%d\n", size*2);
  mergeSort(first, second, combined, size);
  if(size*2 == SIZE) { //Finished, write to out.dat
    printf("\nFinished!!! (%d)\n\n", size * 2);
    printArray(combined, SIZE);
  }
  else {
    write(write_fd, combined, sizeof(combined));
    exit(0);
  }
}