From 9fbe984dc13f1af42bf3a73b696f7358794dd2d4 Mon Sep 17 00:00:00 2001 From: Ayush Ranjan Date: Tue, 30 Jul 2019 18:19:15 -0700 Subject: ext: block map file reader implementation. Also adds stress tests for block map reader and intensifies extent reader tests. PiperOrigin-RevId: 260838177 --- pkg/sentry/fs/ext/BUILD | 1 + pkg/sentry/fs/ext/block_map_file.go | 178 ++++++++++++++++++++++++++++++++---- pkg/sentry/fs/ext/block_map_test.go | 157 +++++++++++++++++++++++++++++++ pkg/sentry/fs/ext/ext_test.go | 12 --- pkg/sentry/fs/ext/extent_test.go | 54 +++-------- 5 files changed, 333 insertions(+), 69 deletions(-) create mode 100644 pkg/sentry/fs/ext/block_map_test.go (limited to 'pkg/sentry/fs') diff --git a/pkg/sentry/fs/ext/BUILD b/pkg/sentry/fs/ext/BUILD index 8158aa522..e3d617576 100644 --- a/pkg/sentry/fs/ext/BUILD +++ b/pkg/sentry/fs/ext/BUILD @@ -54,6 +54,7 @@ go_test( name = "ext_test", size = "small", srcs = [ + "block_map_test.go", "ext_test.go", "extent_test.go", ], diff --git a/pkg/sentry/fs/ext/block_map_file.go b/pkg/sentry/fs/ext/block_map_file.go index 9aabbd145..e9b11d65d 100644 --- a/pkg/sentry/fs/ext/block_map_file.go +++ b/pkg/sentry/fs/ext/block_map_file.go @@ -16,9 +16,15 @@ package ext import ( "io" - "sync" + "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 @@ -26,14 +32,25 @@ import ( type blockMapFile struct { regFile regularFile - // mu serializes changes to fileToPhysBlks. - mu sync.RWMutex + // 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 - // fileToPhysBlks maps the file block numbers to the physical block numbers. - // the physical block number for the (i)th file block is stored in the (i)th - // index. This is initialized (at max) with the first 12 entries. The rest - // have to be read in from disk when required. Protected by mu. - fileToPhysBlks []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 fileReader. @@ -41,7 +58,12 @@ var _ fileReader = (*blockMapFile)(nil) // Read implements fileReader.getFileReader. func (f *blockMapFile) getFileReader(dev io.ReaderAt, blkSize uint64, offset uint64) io.Reader { - panic("unimplemented") + return &blockMapReader{ + dev: dev, + file: f, + fileOff: offset, + blkSize: blkSize, + } } // newBlockMapFile is the blockMapFile constructor. It initializes the file to @@ -50,16 +72,138 @@ func newBlockMapFile(blkSize uint64, regFile regularFile) (*blockMapFile, error) file := &blockMapFile{regFile: regFile} file.regFile.impl = file - toFill := uint64(12) - blksUsed := regFile.blksUsed(blkSize) - if blksUsed < toFill { - toFill = blksUsed + for i := uint(0); i < 4; i++ { + file.coverage[i] = getCoverage(blkSize, i) } blkMap := regFile.inode.diskInode.Data() - file.fileToPhysBlks = make([]uint32, toFill) - for i := uint64(0); i < toFill; i++ { - binary.Unmarshal(blkMap[i*4:(i+1)*4], binary.LittleEndian, &file.fileToPhysBlks[i]) - } + 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 } + +// blockMapReader implements io.Reader which will fetch fill data from the +// block maps and build the blockMapFile.fileToPhyBlks array if required. +type blockMapReader struct { + dev io.ReaderAt + file *blockMapFile + fileOff uint64 + blkSize uint64 +} + +// Compiles only if blockMapReader implements io.Reader. +var _ io.Reader = (*blockMapReader)(nil) + +// Read implements io.Reader.Read. +func (r *blockMapReader) Read(dst []byte) (int, error) { + if len(dst) == 0 { + return 0, nil + } + + if r.fileOff >= r.file.regFile.inode.diskInode.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 * r.file.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 + r.file.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 + r.file.coverage[2] + + read := 0 + toRead := len(dst) + for read < toRead { + var err error + var curR int + + // Figure out which block to delegate the read to. + switch { + case r.fileOff < dirBlksEnd: + // Direct block. + curR, err = r.read(r.file.directBlks[r.fileOff/r.blkSize], r.fileOff%r.blkSize, 0, dst[read:]) + case r.fileOff < indirBlkEnd: + // Indirect block. + curR, err = r.read(r.file.indirectBlk, r.fileOff-dirBlksEnd, 1, dst[read:]) + case r.fileOff < doubIndirBlkEnd: + // Doubly indirect block. + curR, err = r.read(r.file.doubleIndirectBlk, r.fileOff-indirBlkEnd, 2, dst[read:]) + default: + // Triply indirect block. + curR, err = r.read(r.file.tripleIndirectBlk, r.fileOff-doubIndirBlkEnd, 3, dst[read:]) + } + + read += curR + if err != nil { + return read, err + } + } + + return read, nil +} + +// read is the recursive step of the Read 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 (r *blockMapReader) read(curPhyBlk uint32, relFileOff uint64, height uint, dst []byte) (int, error) { + curPhyBlkOff := int64(curPhyBlk) * int64(r.blkSize) + if height == 0 { + toRead := int(r.blkSize - relFileOff) + if len(dst) < toRead { + toRead = len(dst) + } + + n, _ := r.dev.ReadAt(dst[:toRead], curPhyBlkOff+int64(relFileOff)) + r.fileOff += uint64(n) + if n < toRead { + return n, syserror.EIO + } + return n, nil + } + + childCov := r.file.coverage[height-1] + startIdx := relFileOff / childCov + endIdx := r.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 + if err := readFromDisk(r.dev, curPhyBlkOff+int64(i*4), &childPhyBlk); err != nil { + return read, err + } + + n, err := r.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))) +} diff --git a/pkg/sentry/fs/ext/block_map_test.go b/pkg/sentry/fs/ext/block_map_test.go new file mode 100644 index 000000000..b92ae80c8 --- /dev/null +++ b/pkg/sentry/fs/ext/block_map_test.go @@ -0,0 +1,157 @@ +// 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 ( + "bytes" + "io" + "math/rand" + "testing" + + "github.com/google/go-cmp/cmp" + "gvisor.dev/gvisor/pkg/binary" + "gvisor.dev/gvisor/pkg/sentry/fs/ext/disklayout" +) + +// These consts are for mocking the block map tree. +const ( + mockBMBlkSize = uint32(16) + mockBMDiskSize = 2500 +) + +// TestBlockMapReader stress tests block map reader functionality. It performs +// random length reads from all possible positions in the block map structure. +func TestBlockMapReader(t *testing.T) { + dev, mockBMFile, want := blockMapSetUp(t) + n := len(want) + + for from := 0; from < n; from++ { + fileReader := mockBMFile.getFileReader(dev, uint64(mockBMBlkSize), uint64(from)) + got := make([]byte, n-from) + + if read, err := io.ReadFull(fileReader, got); err != nil { + t.Fatalf("file read operation from offset %d to %d only read %d bytes: %v", from, n, read, err) + } + + if diff := cmp.Diff(got, want[from:]); diff != "" { + t.Fatalf("file data from offset %d to %d mismatched (-want +got):\n%s", from, n, diff) + } + } +} + +// blkNumGen is a number generator which gives block numbers for building the +// block map file on disk. It gives unique numbers in a random order which +// facilitates in creating an extremely fragmented filesystem. +type blkNumGen struct { + nums []uint32 +} + +// newBlkNumGen is the blkNumGen constructor. +func newBlkNumGen() *blkNumGen { + blkNums := &blkNumGen{} + lim := mockBMDiskSize / mockBMBlkSize + blkNums.nums = make([]uint32, lim) + for i := uint32(0); i < lim; i++ { + blkNums.nums[i] = i + } + + rand.Shuffle(int(lim), func(i, j int) { + blkNums.nums[i], blkNums.nums[j] = blkNums.nums[j], blkNums.nums[i] + }) + return blkNums +} + +// next returns the next random block number. +func (n *blkNumGen) next() uint32 { + ret := n.nums[0] + n.nums = n.nums[1:] + return ret +} + +// blockMapSetUp creates a mock disk and a block map file. It initializes the +// block map file with 12 direct block, 1 indirect block, 1 double indirect +// block and 1 triple indirect block (basically fill it till the rim). It +// initializes the disk to reflect the inode. Also returns the file data that +// the inode covers and that is written to disk. +func blockMapSetUp(t *testing.T) (io.ReaderAt, *blockMapFile, []byte) { + mockDisk := make([]byte, mockBMDiskSize) + regFile := regularFile{ + inode: inode{ + diskInode: &disklayout.InodeNew{ + InodeOld: disklayout.InodeOld{ + SizeLo: getMockBMFileFize(), + }, + }, + }, + } + + var fileData []byte + blkNums := newBlkNumGen() + var data []byte + + // Write the direct blocks. + for i := 0; i < numDirectBlks; i++ { + curBlkNum := blkNums.next() + data = binary.Marshal(data, binary.LittleEndian, curBlkNum) + fileData = append(fileData, writeFileDataToBlock(mockDisk, curBlkNum, 0, blkNums)...) + } + + // Write to indirect block. + indirectBlk := blkNums.next() + data = binary.Marshal(data, binary.LittleEndian, indirectBlk) + fileData = append(fileData, writeFileDataToBlock(mockDisk, indirectBlk, 1, blkNums)...) + + // Write to indirect block. + doublyIndirectBlk := blkNums.next() + data = binary.Marshal(data, binary.LittleEndian, doublyIndirectBlk) + fileData = append(fileData, writeFileDataToBlock(mockDisk, doublyIndirectBlk, 2, blkNums)...) + + // Write to indirect block. + triplyIndirectBlk := blkNums.next() + data = binary.Marshal(data, binary.LittleEndian, triplyIndirectBlk) + fileData = append(fileData, writeFileDataToBlock(mockDisk, triplyIndirectBlk, 3, blkNums)...) + + copy(regFile.inode.diskInode.Data(), data) + + mockFile, err := newBlockMapFile(uint64(mockBMBlkSize), regFile) + if err != nil { + t.Fatalf("newBlockMapFile failed: %v", err) + } + return bytes.NewReader(mockDisk), mockFile, fileData +} + +// writeFileDataToBlock writes random bytes to the block on disk. +func writeFileDataToBlock(disk []byte, blkNum uint32, height uint, blkNums *blkNumGen) []byte { + if height == 0 { + start := blkNum * mockBMBlkSize + end := start + mockBMBlkSize + rand.Read(disk[start:end]) + return disk[start:end] + } + + var fileData []byte + for off := blkNum * mockBMBlkSize; off < (blkNum+1)*mockBMBlkSize; off += 4 { + curBlkNum := blkNums.next() + copy(disk[off:off+4], binary.Marshal(nil, binary.LittleEndian, curBlkNum)) + fileData = append(fileData, writeFileDataToBlock(disk, curBlkNum, height-1, blkNums)...) + } + return fileData +} + +// getMockBMFileFize gets the size of the mock block map file which is used for +// testing. +func getMockBMFileFize() uint32 { + return uint32(numDirectBlks*getCoverage(uint64(mockBMBlkSize), 0) + getCoverage(uint64(mockBMBlkSize), 1) + getCoverage(uint64(mockBMBlkSize), 2) + getCoverage(uint64(mockBMBlkSize), 3)) +} diff --git a/pkg/sentry/fs/ext/ext_test.go b/pkg/sentry/fs/ext/ext_test.go index 18764e92a..6396886cc 100644 --- a/pkg/sentry/fs/ext/ext_test.go +++ b/pkg/sentry/fs/ext/ext_test.go @@ -41,18 +41,6 @@ var ( ext4ImagePath = path.Join(assetsDir, "tiny.ext4") ) -func beginning(_ uint64) uint64 { - return 0 -} - -func middle(i uint64) uint64 { - return i / 2 -} - -func end(i uint64) uint64 { - return i -} - // setUp opens imagePath as an ext Filesystem and returns all necessary // elements required to run tests. If error is non-nil, it also returns a tear // down function which must be called after the test is run for clean up. diff --git a/pkg/sentry/fs/ext/extent_test.go b/pkg/sentry/fs/ext/extent_test.go index dff401114..9b3f5469e 100644 --- a/pkg/sentry/fs/ext/extent_test.go +++ b/pkg/sentry/fs/ext/extent_test.go @@ -142,48 +142,22 @@ var ( } ) -// TestExtentReader tests extentReader functionality. We should be able to use -// the file reader like any other io.Reader. +// TestExtentReader stress tests extentReader functionality. It performs random +// length reads from all possible positions in the extent tree. func TestExtentReader(t *testing.T) { - type extentReaderTest struct { - name string - from func(uint64) uint64 - to func(uint64) uint64 - } - - tests := []extentReaderTest{ - { - name: "read first half", - from: beginning, - to: middle, - }, - { - name: "read entire file", - from: beginning, - to: end, - }, - { - name: "read second half", - from: middle, - to: end, - }, - } - dev, mockExtentFile, want := extentTreeSetUp(t, node0) - size := mockExtentFile.regFile.inode.diskInode.Size() + n := len(want) - for _, test := range tests { - from := test.from(size) - to := test.to(size) - fileReader := mockExtentFile.getFileReader(dev, mockExtentBlkSize, from) + for from := 0; from < n; from++ { + fileReader := mockExtentFile.getFileReader(dev, mockExtentBlkSize, uint64(from)) + got := make([]byte, n-from) - got := make([]byte, to-from) - if _, err := io.ReadFull(fileReader, got); err != nil { - t.Errorf("file read failed: %v", err) + if read, err := io.ReadFull(fileReader, got); err != nil { + t.Fatalf("file read operation from offset %d to %d only read %d bytes: %v", from, n, read, err) } - if diff := cmp.Diff(got, want[from:to]); diff != "" { - t.Errorf("file data mismatch (-want +got):\n%s", diff) + if diff := cmp.Diff(got, want[from:]); diff != "" { + t.Fatalf("file data from offset %d to %d mismatched (-want +got):\n%s", from, n, diff) } } } @@ -239,7 +213,7 @@ func writeTree(in *inode, disk []byte, root *disklayout.ExtentNode, mockExtentBl var fileData []byte for _, ep := range root.Entries { if root.Header.Height == 0 { - fileData = append(fileData, writeRandomFileData(disk, ep.Entry.(*disklayout.Extent))...) + fileData = append(fileData, writeFileDataToExtent(disk, ep.Entry.(*disklayout.Extent))...) } else { fileData = append(fileData, writeTreeToDisk(disk, ep)...) } @@ -260,7 +234,7 @@ func writeTreeToDisk(disk []byte, curNode disklayout.ExtentEntryPair) []byte { var fileData []byte for _, ep := range curNode.Node.Entries { if curNode.Node.Header.Height == 0 { - fileData = append(fileData, writeRandomFileData(disk, ep.Entry.(*disklayout.Extent))...) + fileData = append(fileData, writeFileDataToExtent(disk, ep.Entry.(*disklayout.Extent))...) } else { fileData = append(fileData, writeTreeToDisk(disk, ep)...) } @@ -268,9 +242,9 @@ func writeTreeToDisk(disk []byte, curNode disklayout.ExtentEntryPair) []byte { return fileData } -// writeRandomFileData writes random bytes to the blocks on disk that the +// writeFileDataToExtent writes random bytes to the blocks on disk that the // passed extent points to. -func writeRandomFileData(disk []byte, ex *disklayout.Extent) []byte { +func writeFileDataToExtent(disk []byte, ex *disklayout.Extent) []byte { phyExStartBlk := ex.PhysicalBlock() phyExStartOff := phyExStartBlk * mockExtentBlkSize phyExEndOff := phyExStartOff + uint64(ex.Length)*mockExtentBlkSize -- cgit v1.2.3