Read() call returns -1 in prime sieve program

Question

I am trying to implement a concurrent prime sieve program. Each pipe will eliminate the multiples of the current number. For example, the first pipe will eliminate all the multiples of 2 and send the non-multiples to the next pipe, the next pipe will eliminate all multiples of 3 and so on. Here is a more detailed description, but it is pretty simple: Detailed. My code is the following:

void receiveAndSend(int wr[35][2], int pipeNr) {
    int p;
    if (close(wr[pipeNr][1]) < 0) {
        perror("close 1");
    }
    if (read(wr[pipeNr][0], &p, 4) < 0) {
        perror("Read1");
    }
    
    printf("prime %d, from file descriptor %d\n", p, wr[pipeNr][0]);
    int j;
    pipeNr++;
    pipe(wr[pipeNr]);
    int cont = 0; 
    
    // enclose all of this in new fork
    int sec = fork();
    if (sec == 0) {
        //close(wr[pipeNr][0]);
        while (read(wr[pipeNr - 1][0], &j, 4) > 0) {
            if (j % p != 0) {
                // printf("%d is not divisible by %d\n", j, p);
                cont = 1;
                if (write(wr[pipeNr][1], &j, 4) < 0) {
                    perror("Write x");
                }
                // perror("test");
            }   
        }       
                    
        if (close(wr[pipeNr - 1][0]) < 0) {
            perror("close x");
        }
        // perror("test2");
        
        if (cont) {
            // printf("arrived\n");
            receiveAndSend(wr, pipeNr);
        }
        exit(0);
    }   
    if (wait(0) < 0) {
        perror("Wait Outter");
    }       
}

I am having a problem with the read call on line 6. When calling the function the first time, it works and read returns 4, but after the first recursive call, I am getting -1.

The first file descriptor, (wr[0]) is filled up with numbers 2...35. I have 35 file descriptors available, but I won't need all of them since there aren't 35 prime numbers.

The writing to the next pipe/fd happens in line 23 and works (returns 4 in each iteration).

I'm assuming there is some kind of problem with the child processes or with the closing calls, but I am not sure. I've tried all sorts of combinations already.

Update:

After debugging the problem on my own linux machine (and printing errno) as @pts suggested, I was able to make some progress. I am getting past the second iteration now with the following output:

prime 2, from file descriptor 3                                                                                                                                                                           
prime 3, from file descriptor 4

However, right after, it hangs with errno being "Success." The writing and while loop works, but right after the while loops, it hangs for some reason even though errno doesn't complain.

Answer 1

There are multiple problems in your implementation:

• when reading p, you only test for failure, not for end of file, hence you may continue with an invalid value of p. You should just use:

  if (read(wr[pipeNr][0], &p, 4) < 4)
      return;
  

• testing for failure of the close() system call is useless, it does not matter for the purpose of the algorithm and obfuscates the code.

• conversely, you should test for failure of the fork() and pipe() system calls, indicating that you are running out of system resources.

• you should check that pipeNr is less than 35 to avoid a buffer overflow, which will occur if the main process writes too many numbers to the initial pipe (> 149). Passing the array length would make the function more generic.

• the purpose of the wait(0) (or more readably wait(NULL)) system call is to avoid exiting the intial process until all prime numbers have been printed. Removing this call lets the program output all primes but some or all of them may be printed after the initial process has already exited to the shell.

• the receiveAndSend function only does something in the child process. The current process just waits for the child process to exit. This is incorrect. The only reason why the program seems to work with the wait() calls removed is the child process writes to the pipe buffer, then recurses and lets its child process read from the pipe. This approach is limited by the pipe buffer size: with a longer stream, the pipe buffer would fill up and write would wait for the pipe reader to read from the pipe, which will not happen because the next process has not been created yet.

  To fix this problem, you should just recurse in the child process and perform the filtering in the parent process.

• after this fix, the wait() call will still hang because the child process is waiting for the next number from the pipe. The parent process must close the wr[pipeNr][1] handle for the child process to get an end of file on its wr[pipeNr - 1][0] handle and exit.

Here is a modified version with a main function that takes a maximum value:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void receiveAndSend(int wr[][2], int pipeNr, int pipeSize) {
    int p;

    close(wr[pipeNr][1]);
    if (read(wr[pipeNr][0], &p, 4) < 4)
        return;

    printf("prime %d, from file descriptor %d\n", p, wr[pipeNr][0]);

    pipeNr++;
    if (pipeNr >= pipeSize) {
        fprintf(stderr, "too many primes\n");
        return;
    }
    if (pipe(wr[pipeNr])) {
        perror("pipe");
        return;
    }

    // enclose all of this in new fork
    int sec = fork();
    if (sec < 0) {
        perror("fork");
        return;
    }
    if (sec == 0) {
        receiveAndSend(wr, pipeNr, pipeSize);
    } else {
        close(wr[pipeNr][0]);
        int j;
        while (read(wr[pipeNr - 1][0], &j, 4) > 0) {
            if (j % p != 0) {
                if (write(wr[pipeNr][1], &j, 4) < 0) {
                    perror("Write x");
                }
            }
        }
        close(wr[pipeNr - 1][0]);
        close(wr[pipeNr][1]);
        wait(NULL);
    }
}

int main(int argc, char *argv[]) {
    int wr[35][2];
    int maxp = 100;

    if (argc >= 2)
        maxp = atoi(argv[1]);

    if (pipe(wr[0])) {
        perror("pipe");
        return 1;
    }
    int sec = fork();
    if (sec < 0) {
        perror("fork");
        return 1;
    }
    if (sec == 0) {
        receiveAndSend(wr, 0, sizeof(wr) / sizeof(wr[0]));
    } else {
        close(wr[0][0]);
        for (int p = 2; p < maxp; p++) {
            write(wr[0][1], &p, 4);
        }
        close(wr[0][1]);
        wait(NULL);
    }
    return 0;
}

Sessions:

chqrlie ~/dev/stackoverflow > ./230311-prime 50
prime 2, from file descriptor 3
prime 3, from file descriptor 4
prime 5, from file descriptor 5
prime 7, from file descriptor 6
prime 11, from file descriptor 7
prime 13, from file descriptor 8
prime 17, from file descriptor 9
prime 19, from file descriptor 10
prime 23, from file descriptor 11
prime 29, from file descriptor 12
prime 31, from file descriptor 13
prime 37, from file descriptor 14
prime 41, from file descriptor 15
prime 43, from file descriptor 16
prime 47, from file descriptor 17

chqrlie ~/dev/stackoverflow > ./230311-prime 200
prime 2, from file descriptor 3
prime 3, from file descriptor 4
prime 5, from file descriptor 5
prime 7, from file descriptor 6
prime 11, from file descriptor 7
[...]
prime 127, from file descriptor 33
prime 131, from file descriptor 34
prime 137, from file descriptor 35
prime 139, from file descriptor 36
prime 149, from file descriptor 37
too many primes

Note these further remarks:

• the read and write system calls are not guaranteed to return 4 on success, they would return a smaller value for multiple reasons, eg: if the pipe buffer is almost full for write or almost empty for read. In practice, this does not happen because the pipe buffer length is a multiple of 4 and the pipe buffer never fills up because of the small number of iterations.

• there is no need for an array of handle pairs: the function receiveAndSend could just get the read handle as an argument and use a local array of 2 handles for the pipe call.

Here is a modified version without an array:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void receiveAndSend(int fd) {
    int p;

    if (read(fd, &p, 4) < 4)
        return;

    printf("prime %d, from file descriptor %d\n", p, fd);

    int wr[2];
    if (pipe(wr)) {
        perror("pipe");
        return;
    }

    // enclose all of this in new fork
    int sec = fork();
    if (sec < 0) {
        perror("fork");
        return;
    }
    if (sec == 0) {
        close(wr[1]);
        receiveAndSend(wr[0]);
    } else {
        close(wr[0]);
        int j;
        while (read(fd, &j, 4) > 0) {
            if (j % p != 0) {
                if (write(wr[1], &j, 4) < 0) {
                    perror("Write x");
                }
            }
        }
        close(fd);
        close(wr[1]);
        wait(NULL);
    }
}

int main(int argc, char *argv[]) {
    int maxp = 100;

    if (argc >= 2)
        maxp = atoi(argv[1]);

    int wr[2];
    if (pipe(wr)) {
        perror("pipe");
        return 1;
    }
    int sec = fork();
    if (sec < 0) {
        perror("fork");
        return 1;
    }
    if (sec == 0) {
        close(wr[1]);
        receiveAndSend(wr[0]);
    } else {
        close(wr[0]);
        for (int p = 2; p < maxp; p++) {
            write(wr[1], &p, 4);
        }
        close(wr[1]);
        wait(NULL);
    }
    return 0;
}

This version accepts larger limits but will run out of resources for relatively small numbers of primes:

chqrlie ~/dev/stackoverflow > ./230311-prime 2000
prime 2, from file descriptor 3
prime 3, from file descriptor 4
prime 5, from file descriptor 5
prime 7, from file descriptor 6
prime 11, from file descriptor 7
[...]
prime 1571, from file descriptor 250
prime 1579, from file descriptor 251
prime 1583, from file descriptor 252
prime 1597, from file descriptor 253
prime 1601, from file descriptor 254
pipe: Too many open files

Closing fd in the child process removes the limitation on file handles:

    if (sec == 0) {
        close(fd);
        close(wr[1]);
        receiveAndSend(wr[0]);
    } ...

But since all processes run concurrently, the limit will hit when fork fails:

chqrlie ~/dev/stackoverflow > ./230311-prime 100000
prime 2, from file descriptor 3
prime 3, from file descriptor 4
prime 5, from file descriptor 3
prime 7, from file descriptor 4
prime 11, from file descriptor 3
[...]
prime 33601, from file descriptor 3
prime 33613, from file descriptor 4
prime 33617, from file descriptor 3
prime 33619, from file descriptor 4
prime 33623, from file descriptor 3
fork: Resource temporarily unavailable