Serhiy Storchaka suggested (in private email, not on tracker or python-dev): why not make follow_symlinks and effective_ids failover where possible?

Let's take the example of effective_ids first, that's simpler.  Let's say the user calls
  os.access("x", os.F_OK, effective_ids=True)
But they doesn't have faccessat() for some reason.  IF euid==uid, and egid==gid, then it's harmless to ignore the effective_ids flag and just use normal access().

Supporting this is easy: if effective_ids=True, and !defined(HAVE_FACCESSAT), but we have all four of the get{e|}{u|g}id() functions, do the above comparison and if it is just call access().

It's a bit more complicated with follow_symlinks.  Let's say they call
  os.chmod("x", 0o644, follow_symlinks=False)
As it happens, they're on Linux so they don't have lchmod() and their fchmodat() doesn't support AT_SYMLINK_NOFOLLOW.  But!  "x" isn't a symbolic link!  In this case normal chmod would be fine fine.

How do we detect that the file is a symbolic link?  That's easy, call lstat().  On Windows, if they gave us a wide path, call win32_lstat_w().  If they passed in a non-default dir_fd, call fstatat() (if available).

The one place where we can't fail over gracefully: os.stat()  If we don't have the appropriate native stat function (lstat or fstatat), then obviously we can't stat nofollow the file to see if it's not a symbolic link and call normal stat().  Sad face.

The attached patch implements all of the above.  It passes the regression test suite on Linux 64-bit (with and without pydebug) and Windows 32-bit (Debug and Release).