aboutsummaryrefslogtreecommitdiff
path: root/internal/inomap
diff options
context:
space:
mode:
Diffstat (limited to 'internal/inomap')
-rw-r--r--internal/inomap/inomap.go99
-rw-r--r--internal/inomap/inomap_test.go89
-rw-r--r--internal/inomap/qino.go22
3 files changed, 148 insertions, 62 deletions
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),
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-02 19:20:16 +0000