Relocation error

Question

#include <stdio.h>

#define MAX 1000000

int dp[MAX];
int P[MAX], C[MAX], K[MAX], child[MAX][1000], index[MAX];
int mod = 1000000007;

void dfs(int i) {
    int j = 1;
    while (j <= index[i]) {
        dfs(child[i][j]);
        if ((C[child[i][j]] == C[i]) && (K[i] - K[child[i][j]] == 1))
            dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod;
        ++j;
    }
}

int main() {
    int T, N, X, i, j;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &X);

        for (i = 0; i < N; ++i)
            index[i] = 0;

        for (i = 1; i < N; ++i) {
             scanf("%d", &P[i]);
             child[P[i]][++index[P[i]]] = i;
        }
        for (i = 0; i < N; ++i)
            scanf("%d", &C[i]);
        for (i = 0; i < N; ++i) {
            scanf("%d", &K[i]);
            if (K[i])
                dp[i] = 0;
            else
                dp[i] = 1;
        }
        dfs(0);
        for (i = 0; i < N; ++i)
            printf("%d\n", dp[i]);
    }
    return 0;
}

When I compiled the above code, I got the following error:

In function `dfs':
(.text+0xa): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x3b): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x4f): relocation truncated to fit: R_X86_64_32S against symbol `C' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x56): relocation truncated to fit: R_X86_64_32S against symbol `C' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x60): relocation truncated to fit: R_X86_64_32S against symbol `K' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x67): relocation truncated to fit: R_X86_64_32S against symbol `K' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x74): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x84): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x97): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o
In function `main':
(.text.startup+0x6e): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o
(.text.startup+0xba): additional relocation overflows omitted from the output
error: ld returned 1 exit status

I know what this error is;how does it occur. I have searched for it in stackoverflow, but I can't understand how to correct it. Can someone please tell me how to correct my code?

Answer 1

The array child has 10^9 elements and each element is 4 Byte, so its size is almost 4GB. However, GCC has a limit on the data segment size and the default threshold is 2GB.

You have two ways to address this problem:

1. Reduce the size of the array child
2. Compile your program with the GCC option -mcmodel=medium.

References:

http://www.network-theory.co.uk/docs/gccintro/gccintro_65.html https://gcc.gnu.org/onlinedocs/gcc-4.2.0/gcc/i386-and-x86_002d64-Options.html

Answer 2

You may to have hit a limit on the size of global variables defined in your program: the 2D array child alone has a size of 4000000000 bytes (4 billion bytes).

Either reduce the size of some of these global variables, or allocate them from the heap at start time with calloc().

Try this version, where child is allocated from the heap:

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

#define MAX 1000000

int dp[MAX], P[MAX], C[MAX], K[MAX], index[MAX];
int (*child)[1000];
int mod = 1000000007;

void dfs(int i) {
    int j = 1;
    while (j <= index[i]) {
        dfs(child[i][j]);
        if ((C[child[i][j]] == C[i]) && (K[i] - K[child[i][j]] == 1))
            dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod;
        ++j;
    }
}

int main(void) {
    int T, N, X, i;

    child = calloc(MAX, sizeof(*child));
    if (child == NULL) {
        fprintf(stderr, "cannot allocate child array (%llu bytes)\n",
                (unsigned long long)MAX * sizeof(*child));
        return 1;
    }

    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &X);

        for (i = 0; i < N; ++i)
            index[i] = 0;

        for (i = 1; i < N; ++i) {
            scanf("%d", &P[i]);
            child[P[i]][++index[P[i]]] = i;
        }
        for (i = 0; i < N; ++i)
            scanf("%d", &C[i]);
        for (i = 0; i < N; ++i) {
            scanf("%d", &K[i]);
            if (K[i])
                dp[i] = 0;
            else
                dp[i] = 1;
        }
        dfs(0);
        for (i = 0; i < N; ++i)
            printf("%d\n", dp[i]);
    }
    free(child);
    return 0;
}

Notes:

• You should also check if the values read from standard input are compatible with the allocated sizes (N <= MAX and P[i] < 1000).

• You can reduce MAX or 1000 if the allocation fails.

• dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod; could be simplified as dp[i] = (dp[i] + dp[child[i][j]]) % mod;