I hope you don't mind a bit more code inspection of fts.c by someone who doesn't fully grok the code yet.
I see that openat for directories is used in two places. One place uses O_NOFOLLOW if FTS_PHYSICAL is set; the other always follows symlinks. Is that intended? That is, wouldn't something like the following untested patch make sense, to avoid a race condition where a symlink replaces a directory? --- old/fts.c 2010-09-12 23:32:51.672822000 -0700 +++ new/fts.c 2010-09-13 00:35:03.330035000 -0700 @@ -290,10 +290,11 @@ fts_set_stat_required (FTSENT *p, bool r /* FIXME: if others need this function, move it into lib/openat.c */ static inline DIR * internal_function -opendirat (int fd, char const *dir) +opendirat (int fd, char const *dir, int extra_flags) { int new_fd = openat (fd, dir, - O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK); + (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK + | extra_flags)); DIR *dirp; if (new_fd < 0) @@ -1237,7 +1238,8 @@ fts_build (register FTS *sp, int type) #else # define __opendir2(file, flag) \ ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \ - ? opendirat(sp->fts_cwd_fd, file) \ + ? opendirat(sp->fts_cwd_fd, file, \ + ISSET(FTS_PHYSICAL) ? O_NOFOLLOW : 0) \ : opendir(file)) #endif if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {