fusefrontend: implement recursive diriv caching

The new contrib/maxlen.bash showed that we have exponential
runtime with respect to directory depth.

The new recursive diriv caching is a lot smarter as it caches
intermediate lookups. maxlen.bash now completes in a few seconds.

xfstests results same as
https://github.com/rfjakob/fuse-xfstests/blob/2d158e4c82be85c15269af77498e353f928f4fab/screenlog.0 :

  Failures: generic/035 generic/062 generic/080 generic/093 generic/099 generic/215 generic/285 generic/319 generic/426 generic/444 generic/467 generic/477 generic/523
  Failed 13 of 580 tests

benchmark.bash results are identical:

  $ ./benchmark.bash
  Testing gocryptfs at /tmp/benchmark.bash.BdQ: gocryptfs v2.0.1-17-g6b09bc0; go-fuse v2.1.1-0.20210611132105-24a1dfe6b4f8; 2021-06-25 go1.16.5 linux/amd64
  /tmp/benchmark.bash.BdQ.mnt is a mountpoint
  WRITE: 262144000 bytes (262 MB, 250 MiB) copied, 0,4821 s, 544 MB/s
  READ:  262144000 bytes (262 MB, 250 MiB) copied, 0,266061 s, 985 MB/s
  UNTAR: 8,280
  MD5:   4,564
  LS:    1,745
  RM:    2,244

9 files changed, 144 insertions, 110 deletions

diff --git a/internal/fusefrontend/dircache.go b/internal/fusefrontend/dircache.go
index 6732de1..8c285fa 100644
--- a/internal/fusefrontend/dircache.go
+++ b/internal/fusefrontend/dircache.go
@@ -7,7 +7,6 @@ import (
 	"syscall"
 	"time"
 
-	"github.com/rfjakob/gocryptfs/internal/nametransform"
 	"github.com/rfjakob/gocryptfs/internal/tlog"
 )
 
@@ -50,6 +49,9 @@ func (e *dirCacheEntry) Clear() {
 
 type dirCache struct {
 	sync.Mutex
+	// Expected length of the stored IVs. Only used for sanity checks.
+	// Usually set to 16, but 0 in plaintextnames mode.
+	ivLen int
 	// Cache entries
 	entries [dirCacheSize]dirCacheEntry
 	// Where to store the next entry (index into entries)
@@ -77,7 +79,7 @@ func (d *dirCache) Clear() {
 func (d *dirCache) Store(node *Node, fd int, iv []byte) {
 	// Note: package ensurefds012, imported from main, guarantees that dirCache
 	// can never get fds 0,1,2.
-	if fd <= 0 || len(iv) != nametransform.DirIVLen {
+	if fd <= 0 || len(iv) != d.ivLen {
 		log.Panicf("Store sanity check failed: fd=%d len=%d", fd, len(iv))
 	}
 	d.Lock()
@@ -139,7 +141,7 @@ func (d *dirCache) Lookup(node *Node) (fd int, iv []byte) {
 	if enableStats {
 		d.hits++
 	}
-	if fd <= 0 || len(iv) != nametransform.DirIVLen {
+	if fd <= 0 || len(iv) != d.ivLen {
 		log.Panicf("Lookup sanity check failed: fd=%d len=%d", fd, len(iv))
 	}
 	d.dbg("dirCache.Lookup %p hit fd=%d dup=%d iv=%x\n", node, e.fd, fd, iv)
diff --git a/internal/fusefrontend/node.go b/internal/fusefrontend/node.go
index 8370a22..dd446a3 100644
--- a/internal/fusefrontend/node.go
+++ b/internal/fusefrontend/node.go
@@ -52,7 +52,7 @@ func (n *Node) Getattr(ctx context.Context, f fs.FileHandle, out *fuse.AttrOut)
 		return f.(fs.FileGetattrer).Getattr(ctx, out)
 	}
 
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -106,7 +106,7 @@ func (n *Node) Unlink(ctx context.Context, name string) (errno syscall.Errno) {
 //
 // Symlink-safe through openBackingDir() + Readlinkat().
 func (n *Node) Readlink(ctx context.Context) (out []byte, errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -123,7 +123,7 @@ func (n *Node) Setattr(ctx context.Context, f fs.FileHandle, in *fuse.SetAttrIn,
 		return f2.Setattr(ctx, in, out)
 	}
 
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -271,7 +271,7 @@ func (n *Node) Link(ctx context.Context, target fs.InodeEmbedder, name string, o
 	defer syscall.Close(dirfd)
 
 	n2 := toNode(target)
-	dirfd2, cName2, errno := n2.prepareAtSyscall("")
+	dirfd2, cName2, errno := n2.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
diff --git a/internal/fusefrontend/node_dir_ops.go b/internal/fusefrontend/node_dir_ops.go
index 001c23a..0f48876 100644
--- a/internal/fusefrontend/node_dir_ops.go
+++ b/internal/fusefrontend/node_dir_ops.go
@@ -154,7 +154,7 @@ func (n *Node) Mkdir(ctx context.Context, name string, mode uint32, out *fuse.En
 // This function is symlink-safe through use of openBackingDir() and
 // ReadDirIVAt().
 func (n *Node) Readdir(ctx context.Context) (fs.DirStream, syscall.Errno) {
-	parentDirFd, cDirName, errno := n.prepareAtSyscall("")
+	parentDirFd, cDirName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return nil, errno
 	}
@@ -360,7 +360,7 @@ retry:
 
 // Opendir is a FUSE call to check if the directory can be opened.
 func (n *Node) Opendir(ctx context.Context) (errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
diff --git a/internal/fusefrontend/node_helpers.go b/internal/fusefrontend/node_helpers.go
index f2d1e5e..ce2e8a9 100644
--- a/internal/fusefrontend/node_helpers.go
+++ b/internal/fusefrontend/node_helpers.go
@@ -2,16 +2,12 @@ package fusefrontend
 
 import (
 	"context"
-	"log"
-	"path/filepath"
-	"sync/atomic"
 	"syscall"
 
 	"github.com/hanwen/go-fuse/v2/fs"
 
 	"github.com/hanwen/go-fuse/v2/fuse"
 
-	"github.com/rfjakob/gocryptfs/internal/nametransform"
 	"github.com/rfjakob/gocryptfs/internal/syscallcompat"
 	"github.com/rfjakob/gocryptfs/internal/tlog"
 )
@@ -80,91 +76,6 @@ func (n *Node) rootNode() *RootNode {
 	return n.Root().Operations().(*RootNode)
 }
 
-// prepareAtSyscall returns a (dirfd, cName) pair that can be used
-// with the "___at" family of system calls (openat, fstatat, unlinkat...) to
-// access the backing encrypted directory.
-//
-// If you pass a `child` file name, the (dirfd, cName) pair will refer to
-// a child of this node.
-// If `child` is empty, the (dirfd, cName) pair refers to this node itself. For
-// the root node, that means (dirfd, ".").
-func (n *Node) prepareAtSyscall(child string) (dirfd int, cName string, errno syscall.Errno) {
-	rn := n.rootNode()
-	// all filesystem operations go through prepareAtSyscall(), so this is a
-	// good place to reset the idle marker.
-	atomic.StoreUint32(&rn.IsIdle, 0)
-
-	// root node itself is special
-	if child == "" && n.IsRoot() {
-		var err error
-		dirfd, cName, err = rn.openBackingDir("")
-		if err != nil {
-			errno = fs.ToErrno(err)
-		}
-		return
-	}
-
-	// normal node itself can be converted to child of parent node
-	if child == "" {
-		name, p1 := n.Parent()
-		if p1 == nil || name == "" {
-			return -1, "", syscall.ENOENT
-		}
-		p2 := toNode(p1.Operations())
-		return p2.prepareAtSyscall(name)
-	}
-
-	// Cache lookup
-	// TODO make it work for plaintextnames as well?
-	cacheable := (!rn.args.PlaintextNames)
-	if cacheable {
-		var iv []byte
-		dirfd, iv = rn.dirCache.Lookup(n)
-		if dirfd > 0 {
-			var cName string
-			var err error
-			if rn.nameTransform.HaveBadnamePatterns() {
-				//BadName allowed, try to determine filenames
-				cName, err = rn.nameTransform.EncryptAndHashBadName(child, iv, dirfd)
-			} else {
-				cName, err = rn.nameTransform.EncryptAndHashName(child, iv)
-			}
-
-			if err != nil {
-				return -1, "", fs.ToErrno(err)
-			}
-			return dirfd, cName, 0
-		}
-	}
-
-	// Slowpath
-	if child == "" {
-		log.Panicf("BUG: child name is empty - this cannot happen")
-	}
-	p := filepath.Join(n.Path(), child)
-	if rn.isFiltered(p) {
-		errno = syscall.EPERM
-		return
-	}
-	dirfd, cName, err := rn.openBackingDir(p)
-	if err != nil {
-		errno = fs.ToErrno(err)
-		return
-	}
-
-	// Cache store
-	if cacheable {
-		// TODO: openBackingDir already calls ReadDirIVAt(). Avoid duplicate work?
-		iv, err := nametransform.ReadDirIVAt(dirfd)
-		if err != nil {
-			syscall.Close(dirfd)
-			return -1, "", fs.ToErrno(err)
-		}
-		rn.dirCache.Store(n, dirfd, iv)
-	}
-	return
-}
-
 // newChild attaches a new child inode to n.
 // The passed-in `st` will be modified to get a unique inode number
 // (or, in `-sharedstorage` mode, the inode number will be set to zero).
diff --git a/internal/fusefrontend/node_open_create.go b/internal/fusefrontend/node_open_create.go
index 8b31932..6385bc1 100644
--- a/internal/fusefrontend/node_open_create.go
+++ b/internal/fusefrontend/node_open_create.go
@@ -16,7 +16,7 @@ import (
 //
 // Symlink-safe through Openat().
 func (n *Node) Open(ctx context.Context, flags uint32) (fh fs.FileHandle, fuseFlags uint32, errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
diff --git a/internal/fusefrontend/node_prepare_syscall.go b/internal/fusefrontend/node_prepare_syscall.go
new file mode 100644
index 0000000..fa558e8
--- /dev/null
+++ b/internal/fusefrontend/node_prepare_syscall.go
@@ -0,0 +1,116 @@
+package fusefrontend
+
+import (
+	"sync/atomic"
+	"syscall"
+
+	"github.com/rfjakob/gocryptfs/internal/tlog"
+
+	"github.com/hanwen/go-fuse/v2/fs"
+
+	"github.com/rfjakob/gocryptfs/internal/nametransform"
+	"github.com/rfjakob/gocryptfs/internal/syscallcompat"
+)
+
+// prepareAtSyscall returns a (dirfd, cName) pair that can be used
+// with the "___at" family of system calls (openat, fstatat, unlinkat...) to
+// access the backing encrypted child file.
+func (n *Node) prepareAtSyscall(child string) (dirfd int, cName string, errno syscall.Errno) {
+	if child == "" {
+		tlog.Warn.Printf("BUG: prepareAtSyscall: child=%q, should have called prepareAtSyscallMyself", child)
+		return n.prepareAtSyscallMyself()
+	}
+
+	rn := n.rootNode()
+
+	// All filesystem operations go through here, so this is a good place
+	// to reset the idle marker.
+	atomic.StoreUint32(&rn.IsIdle, 0)
+
+	if n.IsRoot() && rn.isFiltered(child) {
+		return -1, "", syscall.EPERM
+	}
+
+	var encryptName func(int, string, []byte) (string, error)
+	if !rn.args.PlaintextNames {
+		encryptName = func(dirfd int, child string, iv []byte) (cName string, err error) {
+			// Badname allowed, try to determine filenames
+			if rn.nameTransform.HaveBadnamePatterns() {
+				return rn.nameTransform.EncryptAndHashBadName(child, iv, dirfd)
+			}
+			return rn.nameTransform.EncryptAndHashName(child, iv)
+		}
+	}
+
+	// Cache lookup
+	var iv []byte
+	dirfd, iv = rn.dirCache.Lookup(n)
+	if dirfd > 0 {
+		if rn.args.PlaintextNames {
+			return dirfd, child, 0
+		}
+		var err error
+		cName, err = encryptName(dirfd, child, iv)
+		if err != nil {
+			syscall.Close(dirfd)
+			return -1, "", fs.ToErrno(err)
+		}
+		return
+	}
+
+	// Slowpath: Open ourselves & read diriv
+	parentDirfd, myCName, errno := n.prepareAtSyscallMyself()
+	if errno != 0 {
+		return
+	}
+	defer syscall.Close(parentDirfd)
+
+	dirfd, err := syscallcompat.Openat(parentDirfd, myCName, syscall.O_NOFOLLOW|syscall.O_DIRECTORY|syscallcompat.O_PATH, 0)
+
+	// Cache store
+	if !rn.args.PlaintextNames {
+		var err error
+		iv, err = nametransform.ReadDirIVAt(dirfd)
+		if err != nil {
+			syscall.Close(dirfd)
+			return -1, "", fs.ToErrno(err)
+		}
+	}
+	rn.dirCache.Store(n, dirfd, iv)
+
+	if rn.args.PlaintextNames {
+		return dirfd, child, 0
+	}
+
+	cName, err = encryptName(dirfd, child, iv)
+	if err != nil {
+		syscall.Close(dirfd)
+		return -1, "", fs.ToErrno(err)
+	}
+
+	return
+}
+
+func (n *Node) prepareAtSyscallMyself() (dirfd int, cName string, errno syscall.Errno) {
+	dirfd = -1
+
+	// Handle root node
+	if n.IsRoot() {
+		var err error
+		rn := n.rootNode()
+		dirfd, cName, err = rn.openBackingDir("")
+		if err != nil {
+			errno = fs.ToErrno(err)
+		}
+		return
+	}
+
+	// Otherwise convert to prepareAtSyscall of parent node
+	myName, p1 := n.Parent()
+	if p1 == nil || myName == "" {
+		errno = syscall.ENOENT
+		return
+	}
+	parent := toNode(p1.Operations())
+	return parent.prepareAtSyscall(myName)
+}
diff --git a/internal/fusefrontend/node_xattr_darwin.go b/internal/fusefrontend/node_xattr_darwin.go
index 0f61a5d..31ba653 100644
--- a/internal/fusefrontend/node_xattr_darwin.go
+++ b/internal/fusefrontend/node_xattr_darwin.go
@@ -20,7 +20,7 @@ func filterXattrSetFlags(flags int) int {
 }
 
 func (n *Node) getXAttr(cAttr string) (out []byte, errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -42,7 +42,7 @@ func (n *Node) getXAttr(cAttr string) (out []byte, errno syscall.Errno) {
 }
 
 func (n *Node) setXAttr(context *fuse.Context, cAttr string, cData []byte, flags uint32) (errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -64,7 +64,7 @@ func (n *Node) setXAttr(context *fuse.Context, cAttr string, cData []byte, flags
 }
 
 func (n *Node) removeXAttr(cAttr string) (errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -86,7 +86,7 @@ func (n *Node) removeXAttr(cAttr string) (errno syscall.Errno) {
 }
 
 func (n *Node) listXAttr() (out []string, errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
diff --git a/internal/fusefrontend/node_xattr_linux.go b/internal/fusefrontend/node_xattr_linux.go
index 9698282..212d4e1 100644
--- a/internal/fusefrontend/node_xattr_linux.go
+++ b/internal/fusefrontend/node_xattr_linux.go
@@ -17,7 +17,7 @@ func filterXattrSetFlags(flags int) int {
 }
 
 func (n *Node) getXAttr(cAttr string) (out []byte, errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -32,7 +32,7 @@ func (n *Node) getXAttr(cAttr string) (out []byte, errno syscall.Errno) {
 }
 
 func (n *Node) setXAttr(context *fuse.Context, cAttr string, cData []byte, flags uint32) (errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -44,7 +44,7 @@ func (n *Node) setXAttr(context *fuse.Context, cAttr string, cData []byte, flags
 }
 
 func (n *Node) removeXAttr(cAttr string) (errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
@@ -55,7 +55,7 @@ func (n *Node) removeXAttr(cAttr string) (errno syscall.Errno) {
 }
 
 func (n *Node) listXAttr() (out []string, errno syscall.Errno) {
-	dirfd, cName, errno := n.prepareAtSyscall("")
+	dirfd, cName, errno := n.prepareAtSyscallMyself()
 	if errno != 0 {
 		return
 	}
diff --git a/internal/fusefrontend/root_node.go b/internal/fusefrontend/root_node.go
index af4407e..ab0cdcd 100644
--- a/internal/fusefrontend/root_node.go
+++ b/internal/fusefrontend/root_node.go
@@ -61,11 +61,16 @@ func NewRootNode(args Args, c *contentenc.ContentEnc, n *nametransform.NameTrans
 	if len(args.Exclude) > 0 {
 		tlog.Warn.Printf("Forward mode does not support -exclude")
 	}
+	ivLen := nametransform.DirIVLen
+	if args.PlaintextNames {
+		ivLen = 0
+	}
 	rn := &RootNode{
 		args:          args,
 		nameTransform: n,
 		contentEnc:    c,
 		inoMap:        inomap.New(),
+		dirCache:      dirCache{ivLen: ivLen},
 	}
 	// In `-sharedstorage` mode we always set the inode number to zero.
 	// This makes go-fuse generate a new inode number for each lookup.
@@ -122,15 +127,15 @@ func (rn *RootNode) reportMitigatedCorruption(item string) {
 	}
 }
 
-// isFiltered - check if plaintext "path" should be forbidden
+// isFiltered - check if plaintext file "child" should be forbidden
 //
 // Prevents name clashes with internal files when file names are not encrypted
-func (rn *RootNode) isFiltered(path string) bool {
+func (rn *RootNode) isFiltered(child string) bool {
 	if !rn.args.PlaintextNames {
 		return false
 	}
 	// gocryptfs.conf in the root directory is forbidden
-	if path == configfile.ConfDefaultName {
+	if child == configfile.ConfDefaultName {
 		tlog.Info.Printf("The name /%s is reserved when -plaintextnames is used\n",
 			configfile.ConfDefaultName)
 		return true