inomap: rework logic to efficiently support flags

Adding flags allows to use inomap in reverse mode,
replacing the clunky inoBaseDirIV/inoBaseNameFile
logic that causes problems with high underlying
inode numbers ( https://github.com/rfjakob/gocryptfs/issues/457 )

Microbenchmarks (values below) show that the "SingleDev"
case is now much slower due to an extra map lookup,
but this has no visible effects in ./test.bash results,
so there was no time spent optimizing the case further.

$ go test -bench=.
goos: linux
goarch: amd64
pkg: github.com/rfjakob/gocryptfs/internal/inomap
BenchmarkTranslateSingleDev-4   	18757510	        61.5 ns/op
BenchmarkTranslateManyDevs-4    	18061515	        64.5 ns/op
PASS
ok  	github.com/rfjakob/gocryptfs/internal/inomap	2.467s

4 files changed, 149 insertions, 63 deletions

diff --git a/internal/fusefrontend/fs.go b/internal/fusefrontend/fs.go
index cfd17e3..dbd8236 100644
--- a/internal/fusefrontend/fs.go
+++ b/internal/fusefrontend/fs.go
@@ -85,7 +85,7 @@ func NewFS(args Args, c *contentenc.ContentEnc, n nametransform.NameTransformer)
 		args:          args,
 		nameTransform: n,
 		contentEnc:    c,
-		inoMap:        inomap.New(uint64(st.Dev)), // cast is needed for Darwin
+		inoMap:        inomap.New(),
 	}
 }
 
diff --git a/internal/inomap/inomap.go b/internal/inomap/inomap.go
index f8909c7..1a92156 100644
--- a/internal/inomap/inomap.go
+++ b/internal/inomap/inomap.go
@@ -1,53 +1,91 @@
+// inomap translates (Dev, Flags, Ino) tuples to unique uint64
+// inode numbers.
+//
+// Format of the returned inode numbers:
+//
+//   [spill bit = 0][15 bit namespace id][48 bit passthru inode number]
+//   [spill bit = 1][63 bit spill inode number                        ]
+//
+// Each (Dev, Flags) tuple gets a namespace id assigned. The original inode
+// number is then passed through in the lower 48 bits.
+//
+// If namespace ids are exhaused, or the original id is larger than 48 bits,
+// the whole (Dev, Flags, Ino) tuple gets mapped in the spill map, and the
+// spill bit is set to 1.
 package inomap
 
 import (
+	"log"
 	"sync"
 	"syscall"
 )
 
-// UINT64_MAX           = 18446744073709551615
-const inumTranslateBase = 10000000000000000000
+const (
+	maxNamespaceId = 1<<15 - 1
+	maxPassthruIno = 1<<48 - 1
+	maxSpillIno    = 1<<63 - 1
+)
 
-// InoMap ... see New() for description.
+// InoMap stores the maps using for inode number translation.
+// See package comment for details.
 type InoMap struct {
 	sync.Mutex
-	baseDev       uint64
-	translate     map[QIno]uint64
-	translateNext uint64
+	// namespaces keeps the mapping of (Dev,Flags) tuples to
+	// uint16 identifiers
+	namespaceMap map[namespaceData]uint16
+	// spillNext is the next free namespace number in the namespaces map
+	namespaceNext uint16
+	// spill is used once the namespaces map is full
+	spillMap map[QIno]uint64
+	// spillNext is the next free inode number in the spill map
+	spillNext uint64
 }
 
 // New returns a new InoMap.
-//
-// InoMap translates (device uint64, inode uint64) pairs to unique uint64
-// inode numbers.
-// Inode numbers on the "baseDev" are passed through unchanged (as long as they
-// are not higher than inumTranslateBase).
-// Inode numbers on other devices are remapped to the number space above
-// 10000000000000000000. The mapping is stored in a simple Go map. Entries
-// can only be added and are never removed.
-func New(baseDev uint64) *InoMap {
+func New() *InoMap {
 	return &InoMap{
-		baseDev:       baseDev,
-		translate:     make(map[QIno]uint64),
-		translateNext: inumTranslateBase,
+		namespaceMap:  make(map[namespaceData]uint16),
+		namespaceNext: 0,
+		spillMap:      make(map[QIno]uint64),
+		spillNext:     0,
+	}
+}
+
+func (m *InoMap) spill(in QIno) (out uint64) {
+	out, found := m.spillMap[in]
+	if found {
+		return out
+	}
+	if m.spillNext >= maxSpillIno {
+		log.Panicf("spillMap overflow: spillNext = 0x%x", m.spillNext)
 	}
+	out = m.spillNext
+	m.spillNext++
+	m.spillMap[in] = out
+	return 1<<63 | out
 }
 
 // Translate maps the passed-in (device, inode) pair to a unique inode number.
 func (m *InoMap) Translate(in QIno) (out uint64) {
-	if in.Dev == m.baseDev && in.Ino < inumTranslateBase {
-		return in.Ino
-	}
 	m.Lock()
 	defer m.Unlock()
-	out = m.translate[in]
-	if out != 0 {
-		return out
+
+	if in.Ino > maxPassthruIno {
+		return m.spill(in)
+	}
+	ns, found := m.namespaceMap[in.namespaceData]
+	// Use existing namespace
+	if found {
+		return uint64(ns)<<48 | in.Ino
+	}
+	// No free namespace slots?
+	if m.namespaceNext >= maxNamespaceId {
+		return m.spill(in)
 	}
-	out = m.translateNext
-	m.translate[in] = m.translateNext
-	m.translateNext++
-	return out
+	ns = m.namespaceNext
+	m.namespaceNext++
+	m.namespaceMap[in.namespaceData] = ns
+	return uint64(ns)<<48 | in.Ino
 }
 
 // TranslateStat translates the inode number contained in "st" if neccessary.
@@ -56,8 +94,3 @@ func (m *InoMap) TranslateStat(st *syscall.Stat_t) {
 	in := QInoFromStat(st)
 	st.Ino = m.Translate(in)
 }
-
-// Count returns the number of entries in the translation table.
-func (m *InoMap) Count() int {
-	return len(m.translate)
-}
diff --git a/internal/inomap/inomap_test.go b/internal/inomap/inomap_test.go
index 0349fd6..8efc960 100644
--- a/internal/inomap/inomap_test.go
+++ b/internal/inomap/inomap_test.go
@@ -6,17 +6,15 @@ import (
 )
 
 func TestTranslate(t *testing.T) {
-	const baseDev = 12345
-	m := New(baseDev)
-
-	q := QIno{Dev: baseDev, Ino: 1}
+	m := New()
+	q := QIno{Ino: 1}
 	out := m.Translate(q)
 	if out != 1 {
 		t.Errorf("expected 1, got %d", out)
 	}
-	q.Ino = inumTranslateBase
+	q.Ino = maxPassthruIno
 	out = m.Translate(q)
-	if out < inumTranslateBase {
+	if out < maxPassthruIno {
 		t.Errorf("got %d", out)
 	}
 	out2 := m.Translate(q)
@@ -27,61 +25,106 @@ func TestTranslate(t *testing.T) {
 
 func TestTranslateStress(t *testing.T) {
 	const baseDev = 12345
-	m := New(baseDev)
+	m := New()
+
+	// Make sure baseDev gets namespace id zero
+	var q QIno
+	q.Dev = baseDev
+	m.Translate(q)
+
 	var wg sync.WaitGroup
 	wg.Add(4)
 	go func() {
-		q := QIno{Dev: baseDev}
+		// Some normal inode numbers on baseDev
+		var q QIno
+		q.Dev = baseDev
 		for i := uint64(1); i <= 10000; i++ {
 			q.Ino = i
 			out := m.Translate(q)
 			if out != i {
-				t.Fail()
+				t.Errorf("i=%d out=%d", i, out)
+				break
 			}
 		}
 		wg.Done()
 	}()
 	go func() {
-		q := QIno{Dev: baseDev}
+		// Very high (>maxPassthruIno) inode numbers on baseDev
+		var q QIno
+		q.Dev = baseDev
 		for i := uint64(1); i <= 10000; i++ {
-			q.Ino = inumTranslateBase + i
+			q.Ino = maxPassthruIno + i
 			out := m.Translate(q)
-			if out < inumTranslateBase {
-				t.Fail()
+			if out < maxPassthruIno {
+				t.Errorf("out=%d", out)
+				break
 			}
 		}
 		wg.Done()
 	}()
 	go func() {
-		q := QIno{Dev: 9999999}
+		// Device 9999999
+		var q QIno
+		q.Dev = 9999999
 		for i := uint64(1); i <= 10000; i++ {
 			q.Ino = i
 			out := m.Translate(q)
-			if out < inumTranslateBase {
-				t.Fail()
+			if out < maxPassthruIno {
+				t.Errorf("out=%d", out)
+				break
 			}
 		}
 		wg.Done()
 	}()
 	go func() {
-		q := QIno{Dev: 4444444}
+		// Device 4444444
+		var q QIno
+		q.Dev = 4444444
 		for i := uint64(1); i <= 10000; i++ {
 			q.Ino = i
 			out := m.Translate(q)
-			if out < inumTranslateBase {
-				t.Fail()
+			if out < maxPassthruIno {
+				t.Errorf("out=%d", out)
+				break
 			}
 		}
 		wg.Done()
 	}()
 	wg.Wait()
-	if m.Count() != 30000 {
-		t.Fail()
+	if len(m.spillMap) != 10000 {
+		t.Errorf("len=%d", len(m.spillMap))
+	}
+	if len(m.namespaceMap) != 3 {
+		t.Errorf("len=%d", len(m.namespaceMap))
+	}
+}
+
+// TestUniqueness checks that unique (Dev, Flags, Ino) tuples get unique inode
+// numbers
+func TestUniqueness(t *testing.T) {
+	m := New()
+	var q QIno
+	outMap := make(map[uint64]struct{})
+	for q.Dev = 0; q.Dev < 10; q.Dev++ {
+		for q.Flags = 0; q.Flags < 10; q.Flags++ {
+			// some go into spill
+			for q.Ino = maxPassthruIno - 100; q.Ino < maxPassthruIno+100; q.Ino++ {
+				out := m.Translate(q)
+				_, found := outMap[out]
+				if found {
+					t.Fatalf("inode number %d already used", out)
+				}
+				outMap[out] = struct{}{}
+			}
+		}
+	}
+	if len(outMap) != 10*10*200 {
+		t.Errorf("%d", len(outMap))
 	}
 }
 
 func BenchmarkTranslateSingleDev(b *testing.B) {
-	m := New(0)
+	m := New()
 	var q QIno
 	for n := 0; n < b.N; n++ {
 		q.Ino = uint64(n % 1000)
@@ -90,7 +133,7 @@ func BenchmarkTranslateSingleDev(b *testing.B) {
 }
 
 func BenchmarkTranslateManyDevs(b *testing.B) {
-	m := New(0)
+	m := New()
 	var q QIno
 	for n := 0; n < b.N; n++ {
 		q.Dev = uint64(n % 10)
diff --git a/internal/inomap/qino.go b/internal/inomap/qino.go
index 8f99004..a74a96d 100644
--- a/internal/inomap/qino.go
+++ b/internal/inomap/qino.go
@@ -4,22 +4,32 @@ import (
 	"syscall"
 )
 
+type namespaceData struct {
+	// Stat_t.Dev is uint64 on 32- and 64-bit Linux
+	Dev uint64
+	// Flags acts like an extension of the Dev field.
+	// It is used by reverse mode for virtual files.
+	Flags uint8
+}
+
 // QIno = Qualified Inode number.
 // Uniquely identifies a backing file through the device number,
 // inode number pair.
 type QIno struct {
-	// Stat_t.{Dev,Ino} is uint64 on 32- and 64-bit Linux
-	Dev uint64
+	namespaceData
+	// Stat_t.Ino is uint64 on 32- and 64-bit Linu
 	Ino uint64
 }
 
 // QInoFromStat fills a new QIno struct with the passed Stat_t info.
 func QInoFromStat(st *syscall.Stat_t) QIno {
 	return QIno{
-		// There are some architectures that use 32-bit values here
-		// (darwin, freebsd-32, maybe others). Add and explicit cast to make
-		// this function work everywhere.
-		Dev: uint64(st.Dev),
+		namespaceData: namespaceData{
+			// There are some architectures that use 32-bit values here
+			// (darwin, freebsd-32, maybe others). Add an explicit cast to make
+			// this function work everywhere.
+			Dev: uint64(st.Dev),
+		},
 		Ino: uint64(st.Ino),
 	}
 }