nametransform: extend diriv cache to 100 entries

* extend the diriv cache to 100 entries
* add special handling for the immutable root diriv

The better cache allows to shed some complexity from the path
encryption logic (parent-of-parent check).

Mitigates https://github.com/rfjakob/gocryptfs/issues/127

1 files changed, 51 insertions, 26 deletions

diff --git a/internal/nametransform/dirivcache/dirivcache.go b/internal/nametransform/dirivcache/dirivcache.go
index 890ebac..2708d89 100644
--- a/internal/nametransform/dirivcache/dirivcache.go
+++ b/internal/nametransform/dirivcache/dirivcache.go
@@ -5,59 +5,84 @@ import (
 	"time"
 )
 
-// Single-entry DirIV cache. Stores the directory IV and the encrypted
-// path.
+const (
+	maxEntries = 100
+	expireTime = 1 * time.Second
+)
+
+type cacheEntry struct {
+	// DirIV of the directory.
+	iv []byte
+	// Relative ciphertext path of the directory.
+	cDir string
+}
+
+// DirIVCache stores up to "maxEntries" directory IVs.
 type DirIVCache struct {
-	// Directory the DirIV belongs to
-	dir string
-	// Time the entry expires.
+	// data in the cache, indexed by relative plaintext path
+	// of the directory.
+	data map[string]cacheEntry
+
+	// The DirIV of the root directory gets special treatment because it
+	// cannot change (the root directory cannot be renamed or deleted).
+	// It is unaffected by the expiry timer and cache clears.
+	rootDirIV []byte
+
+	// expiry is the time when the whole cache expires.
 	// The cached entry my become out-of-date if the ciphertext directory is
 	// modifed behind the back of gocryptfs. Having an expiry time limits the
 	// inconstency to one second, like attr_timeout does for the kernel
 	// getattr cache.
 	expiry time.Time
 
-	// The DirIV
-	iv []byte
-	// Ecrypted version of "dir"
-	cDir string
-
-	// Invalidated?
-	cleared bool
 	sync.RWMutex
 }
 
-// lookup - fetch entry for "dir" from the cache
+// Lookup - fetch entry for "dir" from the cache
 func (c *DirIVCache) Lookup(dir string) ([]byte, string) {
 	c.RLock()
 	defer c.RUnlock()
-	if c.cleared || c.dir != dir {
+	if dir == "" {
+		return c.rootDirIV, ""
+	}
+	if c.data == nil {
 		return nil, ""
 	}
 	if time.Since(c.expiry) > 0 {
-		c.cleared = true
+		c.data = nil
 		return nil, ""
 	}
-	return c.iv, c.cDir
+	v := c.data[dir]
+	return v.iv, v.cDir
 }
 
-// store - write entry for "dir" into the cache
+// Store - write entry for "dir" into the cache
 func (c *DirIVCache) Store(dir string, iv []byte, cDir string) {
 	c.Lock()
 	defer c.Unlock()
-	c.cleared = false
-	c.iv = iv
-	c.dir = dir
-	c.cDir = cDir
-	// Set expiry time one second into the future
-	c.expiry = time.Now().Add(1 * time.Second)
+	if dir == "" {
+		c.rootDirIV = iv
+	}
+	if c.data == nil {
+		c.data = make(map[string]cacheEntry, maxEntries)
+		// Set expiry time one second into the future
+		c.expiry = time.Now().Add(expireTime)
+	}
+	// Delete a random entry from the map if reached maxEntries
+	if len(c.data) >= maxEntries {
+		for k := range c.data {
+			delete(c.data, k)
+			break
+		}
+	}
+	c.data[dir] = cacheEntry{iv, cDir}
 }
 
 // Clear ... clear the cache.
-// Exported because it is called from fusefrontend when directories are
-// renamed or deleted.
+// Called from fusefrontend when directories are renamed or deleted.
 func (c *DirIVCache) Clear() {
 	c.Lock()
 	defer c.Unlock()
-	c.cleared = true
+	// Will be re-initialized in the next Store()
+	c.data = nil
 }