How to correct segmentation fault in my C program

Question

I am having hard-time in debugging the following program written for knapSack

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


#define    MAX(x,y)   ((x)>(y) ? (x) : (y))
#define    table(i,j)    table[(i)*(C+1)+(j)]

int main(int argc, char **argv) {

   FILE   *fp;
   long    N, C, opt;                   // # of objects, capacity 
   int    *weights, *profits, *table, *solution;     // weights and profits
   int    verbose;

  // Temp variables
   long    i, j, count, size, size1, ii, jj;

   // Time
   double time;

   // Read input file:
   //  first line:  # of objects, knapsack capacity, 
   //  next lines:   weight and profit  of next object (1 object per line)
   if ( argc > 1 ) {
      fp = fopen(argv[1], "r"); 
      if ( fp == NULL) {


        printf("[ERROR] : Failed to read file named '%s'.\n", argv[1]);
         exit(1);
      }
   } else {
      printf("USAGE : %s [filename].\n", argv[0]);
      exit(1);
   }

   if (argc > 2) verbose = 1; else verbose = 0;

   fscanf(fp, "%ld %ld", &N, &C);
   printf("The number of objects is %ld, and the capacity is %ld.\n", N, C);

   size    = N * sizeof(int);
   size1   = C * sizeof(int);
   weights = (int *)malloc(size);
   profits = (int *)malloc(size);
   table   = (int *)malloc(size*size1);
   solution= (int *)malloc(size);

   if ( weights == NULL || profits == NULL ) {
      printf("[ERROR] : Failed to allocate memory for weights/profits.\n");
      exit(1);
   }

  for ( i=0 ; i < N ; i++ ) {
      count = fscanf(fp, "%d %d", &(weights[i]), &(profits[i]));
      if ( count != 2 ) {
         printf("[ERROR] : Input file is not well formatted.\n");
         exit(1);
      }
   }

   fclose(fp);



   initialize_timer ();
   start_timer();
   // Solve for the optimal profit (create the table)
    for(j=0; j<=C; j++) {
        table(0,j)=0;
    }

    for(ii=1;ii<=N;ii++) {
        for(jj=0; jj<=C; jj++) {    
            if(weights[ii-1]>jj) {
                table(ii,jj)=table(ii-1,jj);
            }
            else {
                table(ii,jj)=MAX(table(ii-1,jj),(profits[ii-1]+table(ii-1,jj-weights[ii-1])));
            }
            }
        }
opt=table(N,C);
   // We only time the creation of the table

  stop_timer();
   time = elapsed_time ();

   printf("The optimal profit is %ld Time taken : %lf.\n",opt,time);


 // End of "Solve for the optimal profit"


// Find the solution (choice vector) by backtracking through the table


      printf("Solution vector is: \n");
j=C;
      for(i=N;i>0;i--) {
    if(table(i,j)==table(i-1,j)) {
        //printf("Object %d not picked", i);
        solution[i-1]=0;
    }   
    else {
        //printf("Object %d picked", i);
        j=j-weights[i-1];
        solution[i-1]=1;
    }
      }
    for(i=0; i<N; i++) {
        printf("%d ",solution[i]);
    }
      if (verbose) {

    // print the solution vector 
      }

   return 0;
}

For small inputs the code runs fine. But for N=1200 and C= 38400000 or any other large input of C , the code shows segmentation error. Following is output from Valgrind :

The number of objects is 1200, and the capacity is 38400000.
==2297== Invalid write of size 4
==2297==    at 0x400A4E: main (knap1.c:73)
==2297==  Address 0x8 is not stack'd, malloc'd or (recently) free'd
==2297== 
==2297== 
==2297== Process terminating with default action of signal 11 (SIGSEGV)
==2297==  Access not within mapped region at address 0x8
==2297==    at 0x400A4E: main (knap1.c:73)
==2297==  If you believe this happened as a result of a stack
==2297==  overflow in your program's main thread (unlikely but
==2297==  possible), you can try to increase the size of the
==2297==  main thread stack using the --main-stacksize= flag.
==2297==  The main thread stack size used in this run was 8388608.
==2297== 
==2297== HEAP SUMMARY:
==2297==     in use at exit: 14,400 bytes in 3 blocks
==2297==   total heap usage: 4 allocs, 1 frees, 14,968 bytes allocated
==2297== 
==2297== LEAK SUMMARY:
==2297==    definitely lost: 0 bytes in 0 blocks
==2297==    indirectly lost: 0 bytes in 0 blocks
==2297==      possibly lost: 0 bytes in 0 blocks
==2297==    still reachable: 14,400 bytes in 3 blocks
==2297==         suppressed: 0 bytes in 0 blocks
==2297== Rerun with --leak-check=full to see details of leaked memory
==2297== 
==2297== For counts of detected and suppressed errors, rerun with: -v
==2297== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)
Segmentation fault

Here is info about value of locals (got from gdb) when run with different input files (k10.txt to k1200.txt) :

  for files with which I got correct output until it exceeded that fix. no. of byte value 
  fp = 0x0 N = 4131212846 C = 140737488347792 opt = 4294967295 weights =

  0x0 profits = 0x36dd221168 table = 0x7ffff7ffc6b8 solution =
  0x36dd8101c0 verbose = 0 i = 0 j = 140737488348128 count = 2 size =
  4198301 size1 = 1 ii = 4196160 jj = 4198224 time =
  2.0728237613194911e-317

  for k1200.txt 
  k1200.txt fp = 0x177b010 N = 1200 C = 38400000 opt = 4294967295
  weights = 0x177b250 profits = 0x177c520 table = 0x8 solution =
  0x7f3cd40008c0 verbose = 0 i = 1200 j = 0 count = 2 size = 4800 size1
  = 153600000 ii = 4196160 jj = 4198224 time = 2.0728237613194911e-317

Any inputs about what is wrong with my code ? and how can I correct the program so that it will never show segmentation fault?

Answer 1

At N=1200 and C=38400000, N*C is 46,080,000,000. Are you using a 32 bit or 64 bit OS? On 32 bit your longs are probably overflowing. Additionally, you probably don't have enough memory for this computation.

Looking at your algorithm, it occurs to me that you may not need to allocate table as N*C, but only 2*C.

The for loop updates the row ii only using row ii-1. So once you've computed, ii, you don't need ii-1 any more. This means you could re-use the memory from the ii-1th row to store ii+1, etc. Thus you really only need two rows.

Something more like this:

table = malloc(2*size1);

...

for(ii=1;ii<=N;ii++) {
    iiOut = ii%2;
    iiIn = (ii-1)%2;
    for(jj=0; jj<=C; jj++) {    
        if(weights[ii-1]>jj) {
            table(iiOut,jj)=table(iiIn,jj);
        }
        else {
            table(iiOut,jj)=MAX(table(iiIn,jj),(profits[ii-1]+table(iiIn,jj-weights[ii-1])));
        }
    }
}
opt=table(iiOut,C);

Answer 2

OK, a few things in addition to dohashi's issues.

You should added checks to see if the following memory allocations failed:

if ( table == NULL ) {
    printf("[ERROR] : Failed to allocate memory for calculation table.\n");
    exit(1);
}
if ( solution == NULL) {
    printf("[ERROR] : Failed to allocate memory for solution.\n");
    exit(1);
}

If you don't have enough memory to allocate these, now you will know.

Next, I note that your macro for indexing into the 2d table mysteriously adds an extra column that is not allocated:

#define    table(i,j)    table[(i)*(C+1)+(j)]

See that "(C+1)" there? It says the table is actually of size N * (C+1). Next, you later index through table from 1 to N and 1 to C

for(ii=1;ii<=N;ii++) {
    for(jj=0; jj<=C; jj++) {    
        if(weights[ii-1]>jj) {
            table(ii,jj)=table(ii-1,jj);
        }
        else {
            table(ii,jj)=MAX(table(ii-1,jj),(profits[ii-1]+table(ii-1,jj-weights[ii-1])));
        }
    }
}
opt=table(N,C);

Size the macro treats table as being of size N * (C+1), this actually requires the table to be of size (N+1)*(C+2).

I think at least one problem here is that somebody translated this code from FORTRAN without accounting for the fact that arrays in C are zero-based not one-based. See here for example.

Answer 3

You are asking for way too much memory here:

table   = (int *)malloc(size*size1);

exactly 1200 * 38400000 * sizeof (int) * sizeof (int) which is around 74GB of memory (assuming sizeof (int) == 4). Your computer cannot reastically handle such a large block, so the allocation fails, and when it fails, a NULL pointer is returned. You should have checked this condition:

if (table == NULL) {
    fprintf(stderr, "Memory allocation failed :(");
    exit(1);
}

You didn't and used a NULL pointer, yielding the segmentation fault.

Unfortunately, there is not easy fix here. You should rethink the algorithm and see if you really need such a large chunk at once, or you can reuse a smaller block.

A minor issue is that you are asking for 4x the memory you need (still assuming sizeof (int) == 4). In fact, when you malloc size * size1 bytes, you are taking sizeof (int) into account twice, once as size = N * sizeof (int) and once as size1 = D * sizeof (int), while it was clear that you wanted a N * C * sizeof(int) matrix.

74GB / 4 means 18.5GB which is still too much: your OS might be able to handle it in virtual memory, but it will get painfully slow when swap kicks in. Unless you have 18+GB of RAM installed, of course.

Anyway, I suppose you are using table as a true/false boolean matrix. Each element is likely a 32-bit int, of which you are using only 1bit. You could cut off the allocated size by 32x if you packed 32 cells into one integer using bitwise operations. It might have an impact on performance, but it will certainly reduce memory footprint to a size your computer can handle.

As suggested in the comments, you could also use char or bool instead of int, since they are usually smaller.