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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
// Copyright 2019 The gVisor Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package ext
import (
"io"
"math"
"gvisor.dev/gvisor/pkg/binary"
"gvisor.dev/gvisor/pkg/syserror"
)
const (
// numDirectBlks is the number of direct blocks in ext block map inodes.
numDirectBlks = 12
)
// blockMapFile is a type of regular file which uses direct/indirect block
// addressing to store file data. This was deprecated in ext4.
type blockMapFile struct {
regFile regularFile
// directBlks are the direct blocks numbers. The physical blocks pointed by
// these holds file data. Contains file blocks 0 to 11.
directBlks [numDirectBlks]uint32
// indirectBlk is the physical block which contains (blkSize/4) direct block
// numbers (as uint32 integers).
indirectBlk uint32
// doubleIndirectBlk is the physical block which contains (blkSize/4) indirect
// block numbers (as uint32 integers).
doubleIndirectBlk uint32
// tripleIndirectBlk is the physical block which contains (blkSize/4) doubly
// indirect block numbers (as uint32 integers).
tripleIndirectBlk uint32
// coverage at (i)th index indicates the amount of file data a node at
// height (i) covers. Height 0 is the direct block.
coverage [4]uint64
}
// Compiles only if blockMapFile implements io.ReaderAt.
var _ io.ReaderAt = (*blockMapFile)(nil)
// newBlockMapFile is the blockMapFile constructor. It initializes the file to
// physical blocks map with (at most) the first 12 (direct) blocks.
func newBlockMapFile(regFile regularFile) (*blockMapFile, error) {
file := &blockMapFile{regFile: regFile}
file.regFile.impl = file
for i := uint(0); i < 4; i++ {
file.coverage[i] = getCoverage(regFile.inode.blkSize, i)
}
blkMap := regFile.inode.diskInode.Data()
binary.Unmarshal(blkMap[:numDirectBlks*4], binary.LittleEndian, &file.directBlks)
binary.Unmarshal(blkMap[numDirectBlks*4:(numDirectBlks+1)*4], binary.LittleEndian, &file.indirectBlk)
binary.Unmarshal(blkMap[(numDirectBlks+1)*4:(numDirectBlks+2)*4], binary.LittleEndian, &file.doubleIndirectBlk)
binary.Unmarshal(blkMap[(numDirectBlks+2)*4:(numDirectBlks+3)*4], binary.LittleEndian, &file.tripleIndirectBlk)
return file, nil
}
// ReadAt implements io.ReaderAt.ReadAt.
func (f *blockMapFile) ReadAt(dst []byte, off int64) (int, error) {
if len(dst) == 0 {
return 0, nil
}
if off < 0 {
return 0, syserror.EINVAL
}
offset := uint64(off)
size := f.regFile.inode.diskInode.Size()
if offset >= size {
return 0, io.EOF
}
// dirBlksEnd is the file offset until which direct blocks cover file data.
// Direct blocks cover 0 <= file offset < dirBlksEnd.
dirBlksEnd := numDirectBlks * f.coverage[0]
// indirBlkEnd is the file offset until which the indirect block covers file
// data. The indirect block covers dirBlksEnd <= file offset < indirBlkEnd.
indirBlkEnd := dirBlksEnd + f.coverage[1]
// doubIndirBlkEnd is the file offset until which the double indirect block
// covers file data. The double indirect block covers the range
// indirBlkEnd <= file offset < doubIndirBlkEnd.
doubIndirBlkEnd := indirBlkEnd + f.coverage[2]
read := 0
toRead := len(dst)
if uint64(toRead)+offset > size {
toRead = int(size - offset)
}
for read < toRead {
var err error
var curR int
// Figure out which block to delegate the read to.
switch {
case offset < dirBlksEnd:
// Direct block.
curR, err = f.read(f.directBlks[offset/f.regFile.inode.blkSize], offset%f.regFile.inode.blkSize, 0, dst[read:])
case offset < indirBlkEnd:
// Indirect block.
curR, err = f.read(f.indirectBlk, offset-dirBlksEnd, 1, dst[read:])
case offset < doubIndirBlkEnd:
// Doubly indirect block.
curR, err = f.read(f.doubleIndirectBlk, offset-indirBlkEnd, 2, dst[read:])
default:
// Triply indirect block.
curR, err = f.read(f.tripleIndirectBlk, offset-doubIndirBlkEnd, 3, dst[read:])
}
read += curR
offset += uint64(curR)
if err != nil {
return read, err
}
}
if read < len(dst) {
return read, io.EOF
}
return read, nil
}
// read is the recursive step of the ReadAt function. It relies on knowing the
// current node's location on disk (curPhyBlk) and its height in the block map
// tree. A height of 0 shows that the current node is actually holding file
// data. relFileOff tells the offset from which we need to start to reading
// under the current node. It is completely relative to the current node.
func (f *blockMapFile) read(curPhyBlk uint32, relFileOff uint64, height uint, dst []byte) (int, error) {
curPhyBlkOff := int64(curPhyBlk) * int64(f.regFile.inode.blkSize)
if height == 0 {
toRead := int(f.regFile.inode.blkSize - relFileOff)
if len(dst) < toRead {
toRead = len(dst)
}
n, _ := f.regFile.inode.fs.dev.ReadAt(dst[:toRead], curPhyBlkOff+int64(relFileOff))
if n < toRead {
return n, syserror.EIO
}
return n, nil
}
childCov := f.coverage[height-1]
startIdx := relFileOff / childCov
endIdx := f.regFile.inode.blkSize / 4 // This is exclusive.
wantEndIdx := (relFileOff + uint64(len(dst))) / childCov
wantEndIdx++ // Make this exclusive.
if wantEndIdx < endIdx {
endIdx = wantEndIdx
}
read := 0
curChildOff := relFileOff % childCov
for i := startIdx; i < endIdx; i++ {
var childPhyBlk uint32
err := readFromDisk(f.regFile.inode.fs.dev, curPhyBlkOff+int64(i*4), &childPhyBlk)
if err != nil {
return read, err
}
n, err := f.read(childPhyBlk, curChildOff, height-1, dst[read:])
read += n
if err != nil {
return read, err
}
curChildOff = 0
}
return read, nil
}
// getCoverage returns the number of bytes a node at the given height covers.
// Height 0 is the file data block itself. Height 1 is the indirect block.
//
// Formula: blkSize * ((blkSize / 4)^height)
func getCoverage(blkSize uint64, height uint) uint64 {
return blkSize * uint64(math.Pow(float64(blkSize/4), float64(height)))
}
|
