bftw: Recover from ENAMETOOLONG

It is always possible to force a breadth-first traversal to encounter
ENAMETOOLONG, regardless of the dircache eviction policy.  As a concrete
example, consider this directory structure:

./1/{NAME_MAX}/{NAME_MAX}/{NAME_MAX}/... (longer than {PATH_MAX})
./2/{NAME_MAX}/{NAME_MAX}/{NAME_MAX}/...
./3/{NAME_MAX}/{NAME_MAX}/{NAME_MAX}/...
...
(more than RLIMIT_NOFILE directories under .)

Eventually, the next file to be processed will not have any parents in
the cache, as the cache can only hold RLIMIT_NOFILE entries.  Then the
whole path must be traversed from ., which will exceed {PATH_MAX} bytes.

Work around this by performing a component-by-component traversal
manually when we see ENAMETOOLONG.  This is required by POSIX:

> The find utility shall be able to descend to arbitrary depths in a file
> hierarchy and shall not fail due to path length limitations (unless a
> path operand specified by the application exceeds {PATH_MAX}
> requirements).

1 files changed, 30 insertions, 0 deletions

diff --git a/tests.sh b/tests.sh
index 2fce23b..872f485 100755
--- a/tests.sh
+++ b/tests.sh
@@ -104,6 +104,30 @@ function make_weirdnames() {
 }
 make_weirdnames "$TMP/weirdnames"
 
+# Creates a very deep directory structure for testing PATH_MAX handling
+function make_deep() {
+    mkdir -p "$1"
+
+    # $name will be 255 characters, aka _XOPEN_NAME_MAX
+    local name="0123456789ABCDEF"
+    name="${name}${name}${name}${name}"
+    name="${name}${name}${name}${name}"
+    name="${name:0:255}"
+
+    for i in {1..8}; do
+        (
+            mkdir "$1/$i"
+            cd "$1/$i"
+
+            for j in {1..16}; do
+                mkdir "$name"
+                cd "$name"
+            done
+        )
+    done
+}
+make_deep "$TMP/deep"
+
 # Creates a scratch directory that tests can modify
 function make_scratch() {
     mkdir -p "$1"
@@ -171,6 +195,7 @@ posix_tests=(
     test_implicit_and
     test_a
     test_o
+    test_deep
 )
 
 bsd_tests=(
@@ -1122,6 +1147,11 @@ function test_colors() {
     LS_COLORS= bfs_diff links -color
 }
 
+function test_deep() {
+    ulimit -n 8
+    bfs_diff deep -mindepth 17
+}
+
 passed=0
 failed=0