I talked to puppet on IRC for a while and we figured out the following about his OS:

* He has utime() and utimes(), but no utimensat().
* utimes() can write with *microsecond* resolution.
* stat() reads the time with *nanosecond* resolution.  (He has HAVE_STAT_TV_NSEC defined.)
* utimes(path, NULL) sets the file to the current time with *second* resolution.  Which means if it happens within the same second as the previous update, it will set mtime to an earlier value.

Just to confirm, he ran this script:
--
import os
b = '/tmp/test2'
open(b,'a').close()
before = os.stat(b)
os.utime(b, None)
after = os.stat(b)
os.unlink(b)
print("before:", before.st_mtime_ns)
print(" after:", after.st_mtime_ns)
print("before <= after", before.st_mtime_ns <= after.st_mtime_ns)
--

and it consistently prints "before <= after False".

*facepalm*

Since utimes supports microsecond resolution, we could in theory work around this problem by explicitly specifying the current time when using utimes().  If we did that, we might want to also see if this behavior affects futimes() and lutimes().

Functions in posixmodule are expected to be atomic, and this would mean two system calls instead of one--so maybe we should only use this workaround on platforms with the bug?