I'd like to add up numbers using fork and divide-and-conquer. The idea is that i fill an array, and i'm checking it's length, using the 'left' and 'right' variables.
If the length is 1, it just returns the number, if it's 2 , it adds up that two numbers and returns their sum. If the length is more than 2, i set a 'middle' variable and cut the array into two pieces, those have two sums, and i add those together and return the final sum.
The two parts of the array are being processed by different processes, which i create with fork. The parent processes always wait for the child processes to finish, and the parent process gets the child's sum via a pipe, so they shouldn't collide, but if the number of integers to add is more than 6, it's not working. Here's the code :
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int DivEtImp(int left, int right, int v[]) {
switch (right-left) {
case 0 : return v[left]; break;
case 1 : return v[left]+v[right]; break;
default : {
int pfd[2];
if (pipe (pfd) < 0)
perror("Pipe error !");
int middle;
middle=(left+right)/2;
pid_t pid;
pid = fork();
if ( pid < 0 )
perror("Fork error !\n");
else {
if ( pid == 0 ) { // Child process.
close(pfd[0]);
int s;
s = DivEtImp(left,middle,v);
write(pfd[1],&s,sizeof(int));
exit(0);
}
else {
wait(NULL); // Parent process.
close(pfd[1]);
int s2,s3;
s2 = DivEtImp(middle+1,right,v);
read(pfd[0],&s3,sizeof(int));
return s2+s3;
}
}
}
}
}
int main() {
int n,i,sum,a;
int* v;
FILE *f = fopen("input.dat","r");
v = (int*)malloc(sizeof(int));
fscanf(f,"%d",&n);
for (i=0;i<n;i++) {
fscanf(f,"%d",&a);
v[i]=a;
}
fclose(f);
sum = DivEtImp(0,n-1,v);
f=fopen("output.dat","w");
fprintf(f,"sum : %d\n",sum);
fclose(f);
free(v);
return 0;
}
If the input.dat looks like this :
6
1 2 3 4 5 6
I get the result :
sum : 21
But with an input with more numbers :
7
1 2 3 4 5 6 7
I get this :
*** Error in `./p': munmap_chunk(): invalid pointer: 0x0000000001c73260 ***
======= Backtrace: =========
/lib64/libc.so.6(+0x7925b)[0x7f0a46c9225b]
/lib64/libc.so.6(cfree+0x1f8)[0x7f0a46c9f4c8]
/lib64/libc.so.6(_IO_setb+0x4b)[0x7f0a46c969ab]
/lib64/libc.so.6(_IO_file_close_it+0xae)[0x7f0a46c94a6e]
/lib64/libc.so.6(fclose+0x1bf)[0x7f0a46c8777f]
./p[0x400bc1]
/lib64/libc.so.6(__libc_start_main+0xf1)[0x7f0a46c39401]
./p[0x4008ca]
======= Memory map: ========
00400000-00401000 r-xp 00000000 fd:00 432360 /home/CaTNiP/Documents/fork/p
00601000-00602000 r--p 00001000 fd:00 432360 /home/CaTNiP/Documents/fork/p
00602000-00603000 rw-p 00002000 fd:00 432360 /home/CaTNiP/Documents/fork/p
01c73000-01c94000 rw-p 00000000 00:00 0 [heap]
7f0a46a02000-7f0a46a18000 r-xp 00000000 fd:00 269994 /usr/lib64/libgcc_s-6.2.1-20160916.so.1
7f0a46a18000-7f0a46c17000 ---p 00016000 fd:00 269994 /usr/lib64/libgcc_s-6.2.1-20160916.so.1
7f0a46c17000-7f0a46c18000 r--p 00015000 fd:00 269994 /usr/lib64/libgcc_s-6.2.1-20160916.so.1
7f0a46c18000-7f0a46c19000 rw-p 00016000 fd:00 269994 /usr/lib64/libgcc_s-6.2.1-20160916.so.1
7f0a46c19000-7f0a46dd6000 r-xp 00000000 fd:00 269812 /usr/lib64/libc-2.24.so
7f0a46dd6000-7f0a46fd5000 ---p 001bd000 fd:00 269812 /usr/lib64/libc-2.24.so
7f0a46fd5000-7f0a46fd9000 r--p 001bc000 fd:00 269812 /usr/lib64/libc-2.24.so
7f0a46fd9000-7f0a46fdb000 rw-p 001c0000 fd:00 269812 /usr/lib64/libc-2.24.so
7f0a46fdb000-7f0a46fdf000 rw-p 00000000 00:00 0
7f0a46fdf000-7f0a47004000 r-xp 00000000 fd:00 269637 /usr/lib64/ld-2.24.so
7f0a471eb000-7f0a471ed000 rw-p 00000000 00:00 0
7f0a47201000-7f0a47204000 rw-p 00000000 00:00 0
7f0a47204000-7f0a47205000 r--p 00025000 fd:00 269637 /usr/lib64/ld-2.24.so
7f0a47205000-7f0a47206000 rw-p 00026000 fd:00 269637 /usr/lib64/ld-2.24.so
7f0a47206000-7f0a47207000 rw-p 00000000 00:00 0
7ffce2cc4000-7ffce2ce5000 rw-p 00000000 00:00 0 [stack]
7ffce2d75000-7ffce2d77000 r--p 00000000 00:00 0 [vvar]
7ffce2d77000-7ffce2d79000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Aborted (core dumped)
Clearly, the code does multiple fork and pipe if the array has at least 7 elements, but i don't know which one causes the error, and how to fix it. Thanks in advance.
Each (forked) process has its own virtual address space (and don't share memory by default with others).
And your
v = (int*)malloc(sizeof(int)); // wrong
is very wrong. You should allocate a large enough v. Your current code has some buffer overflow (an instance of undefined behavior). Learn to use valgrind.
You should replace
// bad code
v = (int*)malloc(sizeof(int));
fscanf(f,"%d",&n);
with
n=0;
if (fscanf(f, "%d", &n)<1 || ((n<0) && (errno=EINVAL)) {
perror("fscanf n"); exit(EXIT_FAILURE);
}
v = calloc(n, sizeof(int));
if (v==NULL) {
perror("calloc v"); exit(EXIT_FAILURE);
}
(I am explicitly setting errno to EINVAL when n<0 so that perror outputs a sensible error)
FYI, see also shm_overview(7) and sem_overview(7), but in your case they are not needed. Notice that calloc is probably using mmap(2) (or sbrk).