Valgrind reports invalid read size of 8, but there are no memory leaks

Question

The following is Valgrind's report:

==31109== Invalid read of size 8
==31109==    at 0x400D95: Array_Shellsort (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==    by 0x4006CB: main (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==  Address 0x5207238 is 8 bytes before a block of size 240 alloc'd
==31109==    at 0x4C29F73: malloc (vg_replace_malloc.c:309)
==31109==    by 0x400A92: Generate_2p3q_Seq (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==    by 0x400CBE: Array_Shellsort (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==    by 0x4006CB: main (in /home/shay/a/ashanbha/368summer/pa2/pa2)
==31109==
31970.000000
==31109==
==31109== HEAP SUMMARY:
==31109==     in use at exit: 0 bytes in 0 blocks
==31109==   total heap usage: 4 allocs, 4 frees, 9,376 bytes allocated
==31109==
==31109== All heap blocks were freed -- no leaks are possible
==31109==
==31109== For lists of detected and suppressed errors, rerun with: -s
==31109== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

The following is the generate function:

  long *Generate_2p3q_Seq (int n, int *seq_size)
  {
    *seq_size = seqsize(n);
    long *sequence = malloc (sizeof(long) * *seq_size);
    printf("size: %d \n",*seq_size);
    sequence[0] = 1;
    int two = 0;
    int three = 0;
    for (int i = 1; i < *seq_size; i++)
    {
      if ((sequence[two] * 2) > (sequence[three] * 3))
      {
        sequence[i] = sequence[three] * 3;
        three++;
      }
      else if ((sequence[two] * 2) < (sequence[three] * 3) )
      {
        sequence[i] = sequence[two] * 2;
        two++;
      }
      else
      {
        sequence[i] = sequence[two] * 2;
        three++;
        two++;
      }
    }
    return sequence;                                                                                          
  }

And the following is my shellsort function:

 void Array_Shellsort (long *array, int size, double *n_comp)
  {
    int seqsize = 0;
    long * sequencearray = Generate_2p3q_Seq(size,&seqsize);
      long interval = sequencearray[seqsize - 1];
    int i = 1;
    int in,out;
    long temp;
    *n_comp = 0;
    while (interval > 0)
    {
      for (out = interval; out < size; out++)
      {
        temp = array[out];
        in = out;
 
        while (in > interval - 1 && array[in - interval] >= temp)
        {
          array[in] = array[in - interval];
          in -= interval;
          (*n_comp)++;
        }
        array[in] = temp;
        (*n_comp)++;
      }
      i += 1;
      interval = sequencearray[seqsize - i];
    }
    free(sequencearray);
  }

I free my actual array (not my sequence) in main. I am curious as to what is causing the invalid read size of 8 because valgrind says there are no leaks. I am also curious as to where the 4 allocs come from as I only allocate for the acutal array, and the array for the sequence.

Answer 1

I figured the answer to my question. These two lines cause the problem:

i += 1;
interval = sequencearray[seqsize - i];

This can be fixed with a simple if statement that breaks out if it is invalid (condition being that seqsize - i < 0, it is invalid, and you break.