The Impossible Happened! What does this mean?

Question

I have experienced an interesting runtime error. I assume it is some sort of memory leak. I wrote the following program:

C Code:

#include <gmp.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#define  PRECISION 4096
#define  DECIMAL_POINT 1
#define  NULL_TERMINATOR 1

void     gatherSquares(const uint32_t limit, uint32_t ** const arr, uint32_t * const count);
uint32_t inList(const uint32_t n, const uint32_t * const arr, const uint32_t count);
void     print_help(const char * const str);

int main(int argc, char* argv[]) {
  uint32_t limit  = 100; /* default */
  uint32_t digits = 100; /* default */
  uint32_t i,j,sum,bufLen,charCount,sqCount=10;
  uint32_t *squares;
  char     *buffer;
  mpf_t    irrational;

  if(argc > 1 && !strcmp(argv[1],"--help"))
    return print_help(argv[0]), EXIT_SUCCESS;
  if(argc > 1)    sscanf(argv[1],"%u",&limit );
  if(argc > 2)    sscanf(argv[2],"%u",&digits);

  mpf_set_default_prec(PRECISION);
  mpf_init(irrational);

  charCount = digits + DECIMAL_POINT;
  bufLen    = charCount + NULL_TERMINATOR;

  gatherSquares(limit,&squares,&sqCount);
  buffer  = malloc(bufLen * sizeof *buffer);

  for(i=sum=0; i<=limit; ++i) {
    if(inList(i,squares,sqCount))
      continue;
    mpf_sqrt_ui(irrational,i);
    gmp_snprintf(buffer,bufLen,"%.*Ff",charCount,irrational);
    for(j=0; j<digits+DECIMAL_POINT; ++j)
      if(buffer[j]!='.')
        sum += buffer[j]-'0';
  }
  printf("%u\n",sum);
  return EXIT_SUCCESS;
}

void gatherSquares(const uint32_t limit, uint32_t ** const arr, uint32_t * const count) {
  uint32_t i,sq,size;
  size=10;
  *arr   = malloc(size * sizeof **arr);
  for(i=0; (sq=i*i)<=limit; ++i) {
    if(*count > size)
      *arr = realloc(*arr, (size*=2) * sizeof **arr);
    (*arr)[i] = sq;
  }
  *arr = realloc(*arr, i * sizeof **arr);
  *count = i;
}

uint32_t inList(const uint32_t n, const uint32_t * const arr, const uint32_t count) {
  uint32_t hi,mid,low;
  hi  = count; /* exclusive upper bound */
  low = 0;     /* inclusive lower bound */
  while(low < hi) {
    mid = low/2 + hi/2;
    if(arr[mid]==n)
      return 1;
    if(arr[mid] >n)
      hi  = mid;
    else
      low = mid + 1;
  }
  return 0;
}

void print_help(const char * const str) {
  printf("  Usage: %s <limit> <digits>\n",str);
  printf("  Calculates the digital sum of the first <digits> digits \n");
  printf("  of each irrational square root <= <limit>\n");
  printf("  * limit    : a decimal number\n");
  printf("             : default = 100\n");
  printf("  * digits   : a decimal number\n");
  printf("             : default = 100\n");
}

I ran the program with the default settings ./a.out and everything ran correctly. I then decided to try running the program with a higher search space ./a.out 1000. This produced the following output:

user@comp:~/Current/Working/Directory ./a.out 1000 
a.out: malloc.c:2369: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *)
&((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk,fd)))) &&
old_size == 0) || ((unsigned long) (old_size) >= 
(unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+
((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && 
((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
Aborted (core dumped)

I assumed there must be some memory leak so I fired up valgrind to help locate the issue. I was dumbstruck by the output:

user@comp:~/Current/Working/Directory valgrind ./a.out 1000 
==4032== Memcheck, a memory error detector
==4032== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==4032== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==4032== Command: ./ans-0080 1000
==4032== 
==4032== Invalid write of size 4
==4032==    at 0x8048920: gatherSquares (prog.c:59)
==4032==    by 0x80486C4: main (prog.c:36)
==4032==  Address 0x427b288 is 0 bytes after a block of size 40 alloc'd
==4032==    at 0x402C418: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==4032==    by 0x804890F: gatherSquares (prog.c:55)
==4032==    by 0x80486C4: main (prog.c:36)
==4032== 
--4032-- VALGRIND INTERNAL ERROR: Valgrind received a signal 11 (SIGSEGV) - exiting
--4032-- si_code=1;  Faulting address: 0x66656220;  sp: 0x625b8a80

valgrind: the 'impossible' happened:
   Killed by fatal signal
==4032==    at 0x380DA208: ??? (in /usr/lib/valgrind/memcheck-x86-linux)
==4032==    by 0x380DAAB1: ??? (in /usr/lib/valgrind/memcheck-x86-linux)
==4032==    by 0x38054133: ??? (in /usr/lib/valgrind/memcheck-x86-linux)
==4032==    by 0x38054206: ??? (in /usr/lib/valgrind/memcheck-x86-linux)
==4032==    by 0x38052115: ??? (in /usr/lib/valgrind/memcheck-x86-linux)
==4032==    by 0x20657360: ???

sched status:
  running_tid=1

Thread 1: status = VgTs_Runnable
==4032==    at 0x402C63E: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==4032==    by 0x8048979: gatherSquares (prog.c:61)
==4032==    by 0x80486C4: main (prog.c:36)

Note the line valgrind: the 'impossible' happened:! What impossible thing happened? What does this mean?

---

PS:
If you know what the program was written for, don't post references to that for search engines to index!

Answer 1

I suspect this isn't a memory leak, but that you're writing before the beginning or after the end of your allocated buffers and thus overwriting the data that malloc uses to maintain it's data structures, thus a failure in malloc.

I can't compile your code to test, but on a quick visual inspection, this looks suspicious (in gatherSquares()):

if(*count > size)
  *arr = realloc(*arr, (size*=2) * sizeof **arr);

You need to realloc based on i, not *count points to.

Answer 2

This line has a problem in my gdb

*arr = realloc(*arr, i * sizeof **arr);

gdb reports

* glibc detected /run/shm/a.out: realloc(): invalid next size: 0x0000000000603230 **