Thanks, the key problem is the fourth time the breakpoint is hit, where the output in your log looks like this:

Breakpoint 3, Fverify_visited_file_modtime (buf=27021317) at fileio.c:5338
5338      if (timespec_cmp (mtime, b->modtime) == 0
(gdb) p mtime
$7 = {
  tv_sec = 1422018451,
  tv_nsec = 132061000
}
(gdb) p b->modtime
$8 = {
  tv_sec = 1422018451,
  tv_nsec = 40059000
}

The two time stamps should be the same, but the nanoseconds component differ (the tv_sec components are the same, which is why we don't observe any bugs in the strace output).

I suspect a bug in the file system.  Can you please try running the attached program, with the current directory being that file system?  It should take about 2 seconds.  You might try running it twice (it may depend on whether the file already exists).