I wrote a script to determine what all the stat() calls are looking at, and it turns out my guess was wrong.  There are a lot of files that find doesn't find, and I doubt it's because they're not in the filesystem.  E.g., all of /etc is missing.

There are the expectable differences in /proc.  But other than that, the first run ends at:

newfstatat(/sys/kernel/debug/tracing/events/task/task_newtask)
newfstatat(/sys/kernel/debug/tracing/events/task/task_rename)
newfstatat(/sys/kernel/debug/tracing/events/raw_syscalls)
newfstatat(/sys/kernel/debug/tracing/events/raw_syscalls/sys_enter)
newfstatat(/sys/kernel/debug/tracing/events/raw_syscalls/sys_exit)

but the second run continues with:

newfstatat(/sys/kernel/debug/tracing/options)
newfstatat(/sys/kernel/debug/tracing/instances)
newfstatat(/sys/kernel/debug/tracing/per_cpu)
newfstatat(/sys/kernel/debug/tracing/per_cpu/cpu0)
newfstatat(/sys/kernel/debug/tracing/trace_stat)
newfstatat(/sys/kernel/debug/usb)

and goes on to walk through /usr and /etc.

Looking at the end of the first run shows no obvious reason why find would terminate prematurely.

The script I used is:

#! /bin/perl

use strict;

my($debug) = 0;
my($cwd) = '';
my(@file);

while (<>) {
    chomp;
    print "\$_ = '$_' \n" if $debug;
    if (m/^open\("(.*)", O_[^)]+\) += (\d+)$/) {
my($name) = $1;
my($fd) = $2;
$file[$fd] = &append($cwd, $name);
print "\$file[$fd] = '$file[$fd]'\n" if $debug;
    } elsif (m/^openat\([^,]+, "(.*)", O_[^)]+\) += (\d+)$/) {
my($name) = $1;
my($fd) = $2;
$file[$fd] = &append($cwd, $name);
print "\$file[$fd] = '$file[$fd]'\n" if $debug;
    } elsif (m/^fchdir\((\d+)\)/) {
my($fd) = $1;
$cwd = $file[$fd];
print "\$cwd = '$cwd'\n" if $debug;
    } elsif (m/^newfstatat\([^,]+, "(.*)", {/) {
my($name) = $1;
$name = &append($cwd, $name);
$name = '/' if $name eq '';
print "newfstatat(", $name, ")\n";
    }
}

sub append {
    my($cwd, $name) = @_;

    if ($name eq '.') {
$name = $cwd;
    } elsif ($name eq '..') {
$name = $cwd;
$name =~ s%/[^/]*$%%;
    } elsif ($name !~ m%^/%) {
$name = $cwd . '/' . $name;
    } elsif ($name eq '/') {
$name = '';
    }
   
    return $name;
}

Could it be a case of automounting kicking in? If your file is hidden behind a mount point, maybe the first run triggers the mount to automount but doesn't descend, and the second one is able to descend into the (now-mounted) location?

It's also interesting to see the contents of the struct stat instances we get for the stat calls.   Could you use "strace -v" rather than plan strace please?

This is very interesting, and of course surprising.

Thanks for the comprehensive diagnositics.   First of all, please try to reproduce the problem with the current stable release of find.  You should be able to download version 4.6.0 from ftp.gnu.org/pub/gnu/findutils (you would need to build it yourself, I trust that this would not be a problem).

Given the nature of the problem, I'm still interested in tracking down the problem with version 4.4.2 even if it's not reproducible in 4.6.0.

Also, building 4.4.2 from source should generate two binaries.  One is called find and is the one you will have used for your video etc.  The other is called "oldfind".  With version 4.4.2 some distributions include oldfind and some do not.  I'd be interested in whether the problem is reproducible with oldfind (the two should be compatible and produce the same results but the internals are very different).

You can also get additional information about what find is doing with the -D option.  Try for example:

oldfind  -D search,stat,tree,opt / -iname 'firefox_binary.py'
find  -D search,stat,tree,opt / -iname 'firefox_binary.py'

You can get additional information about the debug options like this:

find -D help

Another thing to check is whether something is getting fooled by an incorrect st_nlink count on a directory.  Try passing the option -noleaf.