Symlink loop detection incorrectly skips all symlinks for a given file location (except the first)

[chaorace]

Summary

Starting with commit 5b82b99, gopass began to incorrectly skip symlinks if more than one symlink in the store resolves to the same file.

Steps To Reproduce

1. Create a credential in the store root (test-real.gpg)
2. Create 2 symlinks to the credential, also in the store root (test-link1.gpg, test-link2.gpg)
3. Invoke gopass find test

Expected behavior

All resolvable symlinks should be considered when querying credentials and be included in the command output if appropriate

~ λ gopass find test
test-real
test-link1
test-link2

Environment

• OS: Manjaro Linux (Stable)
• OS version: Linux chao-desktop 5.15.74-3-MANJARO #1 SMP PREEMPT Sat Oct 15 13:39:11 UTC 2022 x86_64 GNU/Linux
• gopass Version: gopass 1.14.9 go1.19.1 linux amd64 <root> - gpg 2.2.39 - fs 0.0.0 Available Crypto Backends: age, gpgcli, plain Available Storage Backends: fossilfs, fs, gitfs
• Installation method: Arch package (community/gopass)

Additional context

Demonstration (sensitive names replaced):

~/.password-store λ find ./ | grep foo.bar@example.com
./A.example/foo.bar@example.com.gpg
./email/foo.bar@example.com.gpg
./B.example/foo.bar@example.com.gpg
./C.example/foo.bar@example.com.gpg
./D.example/foo.bar@example.com.gpg

~/.password-store λ find ./ | grep foo.bar@example.com | xargs readlink --canonicalize 
/home/chao/.password-store/C.example/foo.bar@example.com.gpg
/home/chao/.password-store/C.example/foo.bar@example.com.gpg
/home/chao/.password-store/C.example/foo.bar@example.com.gpg
/home/chao/.password-store/C.example/foo.bar@example.com.gpg
/home/chao/.password-store/C.example/foo.bar@example.com.gpg

~/.password-store λ gopass find foo.bar@example.com
D.example/foo.bar@example.com
C.example/foo.bar@example.com

As you can see, only the real file (C.example/foo.bar@example.com.gpg) and one symlink (D.example/foo.bar@example.com) were kept in the output for gopass find, even though all of the symlinks resolve without producing a loop. I use symlinks extensively in my password store and I see the same behavior in every situation where I have two or more symlinks to the same credential.

Log output (sensitive names replaced):

2022/11/01 17:37:52.089045 fs/store.go:153	fs.(*Store).List	Listing /home/chao/.password-store/
2022/11/01 17:37:52.089496 fs/store.go:163	fs.(*Store).List.func1	skipping dot dir (relPath: .gopass/, prefix: )
2022/11/01 17:37:52.089536 fs/store.go:163	fs.(*Store).List.func1	skipping dot dir (relPath: .public-keys/, prefix: )
2022/11/01 17:37:52.091926 fs/walk.go:39	fs.(*walker).walk.func1	Symlink loop detected at /home/chao/.password-store/C.example/foo.bar@example.com.gpg!
2022/11/01 17:37:52.092719 fs/walk.go:39	fs.(*walker).walk.func1	Symlink loop detected at /home/chao/.password-store/C.example/foo.bar@example.com.gpg!
2022/11/01 17:37:52.092975 fs/walk.go:39	fs.(*walker).walk.func1	Symlink loop detected at /home/chao/.password-store/C.example/foo.bar@example.com.gpg!
2022/11/01 17:37:52.096862 action/find.go:89	action.(*Action).find	D.example/foo.bar@example.com
2022/11/01 17:37:52.096882 action/find.go:89	action.(*Action).find	C.example/foo.bar@example.com
2022/11/01 17:37:52.096929 queue/background.go:91	queue.(*Queue).run	all tasks done

Note that there are 3 instances of the "Symlink loop detected" message, which corresponds to the number of missing symlinks from the expected output.

[dominikschulz]

Yes, I think the problem is that we should only record destPath as seen if it is pointing to a symlink it self: https://github.com/gopasspw/gopass/blob/master/internal/backend/storage/fs/walk.go#L38

[chaorace]

It seems to me that this is a relatively expensive case to try and detect algorithmically, so I took a peek at how GNU find detects such loops: apparently, it simply checks if the kernel syscall failed to resolve with a reported loop condition.

The documentation for the linux approach to symlink chain resolution is here. Basically, they count the symlink depth and give up once depth exceeds MAXSYMLINKS (40 by default). Anything deeper than that is considered a loop. The rationale behind this "dumb" implementation being that it's computationally cheap and prevents the case of DoS via extremely long, yet technically valid symlink chains:

Because it's a latency and DoS issue too. We need to react well to true loops, but also to "very deep" non-loops. It's not about memory use, it's about users triggering unreasonable CPU resources.

I think we should use the same approach at the application-level, with the extra wrinkle that we retain the current depth as the walk branches out:

1. Observe the MAXSYMLINKS environment variable for the depth maximum, with a default of 40
2. While walking, traverse symlink chains one level at a time via os.ReadLink
3. Count depth while following the chain, handling that particular "sub-walk" as a loop when the accumulated depth exceeds our limit
4. If the end of the chain is reached, walk the resulting path as usual. We'll need to copy over the symlink depth from the "super-walk" for any "sub-walks" that get spawned when traversing symlinks nested within.
5. Prior to function return, deduplicate the walk's collected results

[dominikschulz]

@chaorace thanks for doing some digging here. We should definitely do 1. through 3. But I'm not sure if I got 4. and 5., yet.

Any chance you could come up with a PR?