title: Recommended way to track down array out-of-bound access/write in C program
body: <p>Consider writing implementation for some not-so-obvious algorithm in C. For example let it be recursive quicksort, that I have found in K. N. King's "C Programming: A Modern Approach, 2nd Edition" book, that it's available from <a href="http://knking.com/books/c2/programs/qsort.c">here</a>. The most interesting part consist of two following definitions:</p>
  
  <pre><code>void quicksort(int a[], int low, int high)
  {
      int middle;
  
      if (low &gt;= high)
          return;
  
      middle = split(a, low, high);
      quicksort(a, low, middle - 1);
      quicksort(a, middle + 1, high);
  }
  
  int split(int a[], int low, int high)
  {
      int part_element = a[low];
  
      for (;;) {
         while (low &lt; high &amp;&amp; part_element &lt;= a[high])
             high--;
         if (low &gt;= high)
             break;
         a[low++] = a[high];
  
         while (low &lt; high &amp;&amp; a[low] &lt;= part_element)
             low++;
         if (low &gt;= high)
             break;
         a[high--] = a[low];
      }
  
      a[high] = part_element;
      return high;
  }
  </code></pre>
  
  <p>Both <code>while</code> loops can be optimized by removing <code>low &lt; high</code> tests:</p>
  
  <pre><code>for (;;) {
      while (part_element &lt; a[high])
          high--;
      if (low &gt;= high)
          break;
      a[low++] = a[high];
      a[high] = part_element;
  
      while (a[low] &lt;= part_element)
          low++;
      if (low &gt;= high)
          break;
      a[high--] = a[low];
      a[low] = part_element;
  }
  </code></pre>
  
  <p>What is the recommended way to make sure that every access or write to array (allocated on <strong>stack</strong>) is actually valid (i.e. not provoking undefined behaviour) ? What I already tried is to:</p>
  
  <ul>
  <li>manually debug with <code>gdb</code> on some actual data</li>
  <li>pass source code to static analysis tools like <code>split</code> or <code>cppcheck</code></li>
  <li><code>valgrind</code> with <code>--tool=exp-sgcheck</code> switch</li>
  </ul>
  
  <p>For example having five elements array <code>{8, 1, 2, 3, 4}</code>:</p>
  
  <pre><code>#define N 5
  
  int main(void)
  {
      int a[N] = {8, 1, 2, 3, 4}, i;
  
      quicksort(a, 0, N - 1);
  
      printf("After sort:");
      for (i = 0; i &lt; N; i++)
          printf(" %d", a[i]);
      putchar('\n');
  
      return 0;
  }
  </code></pre>
  
  <p>Result is (most certainly it's implemention dependent):</p>
  
  <pre><code>After sort: 1 1 2 4 8
  </code></pre>
  
  <h2>1. GDB</h2>
  
  <pre><code>(gdb) p low
  $1 = 3
  (gdb) p high
  $2 = 4
  (gdb) p a[low]
  $3 = 1
  (gdb) p part_element
  $4 = 8
  (gdb) s
  47              low++;
  (gdb) s
  46          while (a[low] &lt;= part_element)
  (gdb) s
  47              low++;
  (gdb) s
  46          while (a[low] &lt;= part_element)
  (gdb) p low
  $5 = 5
  (gdb) p high
  $6 = 4
  (gdb) bt full
  #0  split (a=0x7fffffffe140, low=5, high=4) at qsort.c:46
          part_element = 8
  #1  0x00000000004005df in quicksort (a=0x7fffffffe140, low=0, high=4) at qsort.c:30
          middle = &lt;value optimized out&gt;
  #2  0x0000000000400656 in main () at qsort.c:14
          a = {4, 1, 2, 1, 8}
          i = &lt;value optimized out&gt;
  </code></pre>
  
  <p>As you see <code>low</code> variable went outside boundary:</p>
  
  <pre><code>(gdb) p low
  $5 = 5
  </code></pre>
  
  <h2>2. Static analysis tools</h2>
  
  <pre><code>$ splint -retvalint -exportlocal qsort.c 
  Splint 3.1.2 --- 07 Feb 2011
  
  Finished checking --- no warnings
  
  $ cppcheck qsort.c 
  Checking qsort.c...
  </code></pre>
  
  <h2>3. Valgrind with <code>--tool=exp-sgcheck</code></h2>
  
  <pre><code>$ valgrind --tool=exp-sgcheck ./a.out 
  ==5480== exp-sgcheck, a stack and global array overrun detector
  ==5480== NOTE: This is an Experimental-Class Valgrind Tool
  ==5480== Copyright (C) 2003-2012, and GNU GPL'd, by OpenWorks Ltd et al.
  ==5480== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
  ==5480== Command: ./a.out
  ==5480== 
  ==5480== Invalid read of size 4
  ==5480==    at 0x4005A0: split (qsort.c:46)
  ==5480==    by 0x4005DE: quicksort (qsort.c:30)
  ==5480==    by 0x400655: main (qsort.c:14)
  ==5480==  Address 0x7ff000114 expected vs actual:
  ==5480==  Expected: stack array "a" of size 20 in frame 2 back from here
  ==5480==  Actual:   unknown
  ==5480==  Actual:   is 0 after Expected
  ==5480== 
  After sort: 1 1 2 4 8
  ==5480== 
  ==5480== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
  </code></pre>
  
  <p>The location <code>at 0x4005A0: split (qsort.c:46)</code> is matching to the same place as I found by <code>gdb</code> manually.</p>