blob: 567523d32c2979e05ae4d3306e8e87e365e38664 (
plain)
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
|
// 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 disklayout
// Extents were introduced in ext4 and provide huge performance gains in terms
// data locality and reduced metadata block usage. Extents are organized in
// extent trees. The root node is contained in inode.BlocksRaw.
//
// Terminology:
// - Physical Block:
// Filesystem data block which is addressed normally wrt the entire
// filesystem (addressed with 48 bits).
//
// - File Block:
// Data block containing *only* file data and addressed wrt to the file
// with only 32 bits. The (i)th file block contains file data from
// byte (i * sb.BlockSize()) to ((i+1) * sb.BlockSize()).
const (
// ExtentStructsSize is the size of all the three extent on-disk structs.
ExtentStructsSize = 12
// ExtentMagic is the magic number which must be present in the header.
ExtentMagic = 0xf30a
)
// ExtentEntryPair couples an in-memory ExtendNode with the ExtentEntry that
// points to it. We want to cache these structs in memory to avoid repeated
// disk reads.
//
// Note: This struct itself does not represent an on-disk struct.
type ExtentEntryPair struct {
// Entry points to the child node on disk.
Entry ExtentEntry
// Node points to child node in memory. Is nil if the current node is a leaf.
Node *ExtentNode
}
// ExtentNode represents an extent tree node. For internal nodes, all Entries
// will be ExtendIdxs. For leaf nodes, they will all be Extents.
//
// Note: This struct itself does not represent an on-disk struct.
type ExtentNode struct {
Header ExtentHeader
Entries []ExtentEntryPair
}
// ExtentEntry reprsents an extent tree node entry. The entry can either be
// an ExtentIdx or Extent itself. This exists to simplify navigation logic.
type ExtentEntry interface {
// FileBlock returns the first file block number covered by this entry.
FileBlock() uint32
// PhysicalBlock returns the child physical block that this entry points to.
PhysicalBlock() uint64
}
// ExtentHeader emulates the ext4_extent_header struct in ext4. Each extent
// tree node begins with this and is followed by `NumEntries` number of:
// - Extent if `Depth` == 0
// - ExtentIdx otherwise
type ExtentHeader struct {
// Magic in the extent magic number, must be 0xf30a.
Magic uint16
// NumEntries indicates the number of valid entries following the header.
NumEntries uint16
// MaxEntries that could follow the header. Used while adding entries.
MaxEntries uint16
// Height represents the distance of this node from the farthest leaf. Please
// note that Linux incorrectly calls this `Depth` (which means the distance
// of the node from the root).
Height uint16
_ uint32
}
// ExtentIdx emulates the ext4_extent_idx struct in ext4. Only present in
// internal nodes. Sorted in ascending order based on FirstFileBlock since
// Linux does a binary search on this. This points to a block containing the
// child node.
type ExtentIdx struct {
FirstFileBlock uint32
ChildBlockLo uint32
ChildBlockHi uint16
_ uint16
}
// Compiles only if ExtentIdx implements ExtentEntry.
var _ ExtentEntry = (*ExtentIdx)(nil)
// FileBlock implements ExtentEntry.FileBlock.
func (ei *ExtentIdx) FileBlock() uint32 {
return ei.FirstFileBlock
}
// PhysicalBlock implements ExtentEntry.PhysicalBlock. It returns the
// physical block number of the child block.
func (ei *ExtentIdx) PhysicalBlock() uint64 {
return (uint64(ei.ChildBlockHi) << 32) | uint64(ei.ChildBlockLo)
}
// Extent represents the ext4_extent struct in ext4. Only present in leaf
// nodes. Sorted in ascending order based on FirstFileBlock since Linux does a
// binary search on this. This points to an array of data blocks containing the
// file data. It covers `Length` data blocks starting from `StartBlock`.
type Extent struct {
FirstFileBlock uint32
Length uint16
StartBlockHi uint16
StartBlockLo uint32
}
// Compiles only if Extent implements ExtentEntry.
var _ ExtentEntry = (*Extent)(nil)
// FileBlock implements ExtentEntry.FileBlock.
func (e *Extent) FileBlock() uint32 {
return e.FirstFileBlock
}
// PhysicalBlock implements ExtentEntry.PhysicalBlock. It returns the
// physical block number of the first data block this extent covers.
func (e *Extent) PhysicalBlock() uint64 {
return (uint64(e.StartBlockHi) << 32) | uint64(e.StartBlockLo)
}
|
