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).