1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
// inomap translates (Dev, Tag, 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] = 64 bit translated inode number
// [spill bit = 1][63 bit counter ] = 64 bit spill inode number
//
// Each (Dev, Tag) tuple gets a namespace id assigned. The original inode
// number is then passed through in the lower 48 bits.
//
// If namespace ids are exhausted, or the original id is larger than 48 bits,
// the whole (Dev, Tag, Ino) tuple gets mapped in the spill map, and the
// spill bit is set to 1.
package inomap
import (
"log"
"math"
"sync"
"syscall"
"github.com/rfjakob/gocryptfs/v2/internal/tlog"
)
const (
// max value of 15 bit namespace id
maxNamespaceId = 1<<15 - 1
// max value of 48 bit passthru inode number
maxPassthruIno = 1<<48 - 1
// the spill inode number space starts at 0b10000...0.
spillSpaceStart = 1 << 63
)
// InoMap stores the maps using for inode number translation.
// See package comment for details.
type InoMap struct {
sync.Mutex
// namespaceMap keeps the mapping of (Dev,Flags) tuples to
// 15-bit identifiers (stored in an uint16 with the high bit always zero)
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.
// Inode numbers on device `rootDev` will be passed through as-is.
// If `rootDev` is zero, the first Translate() call decides the effective
// rootDev.
func New(rootDev uint64) *InoMap {
m := &InoMap{
namespaceMap: make(map[namespaceData]uint16),
namespaceNext: 0,
spillMap: make(map[QIno]uint64),
spillNext: spillSpaceStart,
}
if rootDev > 0 {
// Reserve namespace 0 for rootDev
m.namespaceMap[namespaceData{rootDev, 0}] = 0
m.namespaceNext = 1
}
return m
}
var spillWarn sync.Once
func (m *InoMap) spill(in QIno) (out uint64) {
spillWarn.Do(func() { tlog.Warn.Printf("InoMap: opening spillMap for %v", in) })
out, found := m.spillMap[in]
if found {
return out
}
if m.spillNext == math.MaxUint64 {
log.Panicf("spillMap overflow: spillNext = 0x%x", m.spillNext)
}
out = m.spillNext
m.spillNext++
m.spillMap[in] = out
return out
}
// Translate maps the passed-in (device, tag, inode) tuple to a unique inode number.
func (m *InoMap) Translate(in QIno) (out uint64) {
m.Lock()
defer m.Unlock()
if in.Ino > maxPassthruIno {
out = m.spill(in)
return out
}
ns, found := m.namespaceMap[in.namespaceData]
// Use existing namespace
if found {
out = uint64(ns)<<48 | in.Ino
return out
}
// No free namespace slots?
if m.namespaceNext >= maxNamespaceId {
out = m.spill(in)
return out
}
ns = m.namespaceNext
m.namespaceNext++
m.namespaceMap[in.namespaceData] = ns
out = uint64(ns)<<48 | in.Ino
return out
}
// TranslateStat translates (device, ino) pair contained in "st" into a unique
// inode number and overwrites the ino in "st" with it.
// Convenience wrapper around Translate().
func (m *InoMap) TranslateStat(st *syscall.Stat_t) {
in := QInoFromStat(st)
st.Ino = m.Translate(in)
}
|
