diff options
| -rw-r--r-- | pkg/sentry/fs/ext/disklayout/BUILD | 2 | ||||
| -rw-r--r-- | pkg/sentry/fs/ext/disklayout/extent.go | 139 | ||||
| -rw-r--r-- | pkg/sentry/fs/ext/disklayout/extent_test.go | 27 |
3 files changed, 168 insertions, 0 deletions
diff --git a/pkg/sentry/fs/ext/disklayout/BUILD b/pkg/sentry/fs/ext/disklayout/BUILD index e4cb26645..dde15110d 100644 --- a/pkg/sentry/fs/ext/disklayout/BUILD +++ b/pkg/sentry/fs/ext/disklayout/BUILD @@ -12,6 +12,7 @@ go_library( "dirent_new.go", "dirent_old.go", "disklayout.go", + "extent.go", "inode.go", "inode_new.go", "inode_old.go", @@ -38,6 +39,7 @@ go_test( srcs = [ "block_group_test.go", "dirent_test.go", + "extent_test.go", "inode_test.go", "superblock_test.go", ], diff --git a/pkg/sentry/fs/ext/disklayout/extent.go b/pkg/sentry/fs/ext/disklayout/extent.go new file mode 100644 index 000000000..567523d32 --- /dev/null +++ b/pkg/sentry/fs/ext/disklayout/extent.go @@ -0,0 +1,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) +} diff --git a/pkg/sentry/fs/ext/disklayout/extent_test.go b/pkg/sentry/fs/ext/disklayout/extent_test.go new file mode 100644 index 000000000..b0fad9b71 --- /dev/null +++ b/pkg/sentry/fs/ext/disklayout/extent_test.go @@ -0,0 +1,27 @@ +// 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 + +import ( + "testing" +) + +// TestExtentSize tests that the extent structs are of the correct +// size. +func TestExtentSize(t *testing.T) { + assertSize(t, ExtentHeader{}, ExtentStructsSize) + assertSize(t, ExtentIdx{}, ExtentStructsSize) + assertSize(t, Extent{}, ExtentStructsSize) +} |