summaryrefslogtreecommitdiffhomepage
path: root/pkg
diff options
context:
space:
mode:
Diffstat (limited to 'pkg')
-rw-r--r--pkg/flipcall/BUILD1
-rw-r--r--pkg/flipcall/flipcall.go2
-rw-r--r--pkg/flipcall/packet_window_mmap.go25
-rw-r--r--pkg/merkletree/BUILD16
-rw-r--r--pkg/merkletree/merkletree.go135
-rw-r--r--pkg/merkletree/merkletree_test.go122
6 files changed, 300 insertions, 1 deletions
diff --git a/pkg/flipcall/BUILD b/pkg/flipcall/BUILD
index 9c5ad500b..aa8e4e1f3 100644
--- a/pkg/flipcall/BUILD
+++ b/pkg/flipcall/BUILD
@@ -11,6 +11,7 @@ go_library(
"futex_linux.go",
"io.go",
"packet_window_allocator.go",
+ "packet_window_mmap.go",
],
visibility = ["//visibility:public"],
deps = [
diff --git a/pkg/flipcall/flipcall.go b/pkg/flipcall/flipcall.go
index 3cdb576e1..ec742c091 100644
--- a/pkg/flipcall/flipcall.go
+++ b/pkg/flipcall/flipcall.go
@@ -95,7 +95,7 @@ func (ep *Endpoint) Init(side EndpointSide, pwd PacketWindowDescriptor, opts ...
if pwd.Length > math.MaxUint32 {
return fmt.Errorf("packet window size (%d) exceeds maximum (%d)", pwd.Length, math.MaxUint32)
}
- m, _, e := syscall.RawSyscall6(syscall.SYS_MMAP, 0, uintptr(pwd.Length), syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_SHARED, uintptr(pwd.FD), uintptr(pwd.Offset))
+ m, e := packetWindowMmap(pwd)
if e != 0 {
return fmt.Errorf("failed to mmap packet window: %v", e)
}
diff --git a/pkg/flipcall/packet_window_mmap.go b/pkg/flipcall/packet_window_mmap.go
new file mode 100644
index 000000000..869183b11
--- /dev/null
+++ b/pkg/flipcall/packet_window_mmap.go
@@ -0,0 +1,25 @@
+// Copyright 2020 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 flipcall
+
+import (
+ "syscall"
+)
+
+// Return a memory mapping of the pwd in memory that can be shared outside the sandbox.
+func packetWindowMmap(pwd PacketWindowDescriptor) (uintptr, syscall.Errno) {
+ m, _, err := syscall.RawSyscall6(syscall.SYS_MMAP, 0, uintptr(pwd.Length), syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_SHARED, uintptr(pwd.FD), uintptr(pwd.Offset))
+ return m, err
+}
diff --git a/pkg/merkletree/BUILD b/pkg/merkletree/BUILD
new file mode 100644
index 000000000..5b0e4143a
--- /dev/null
+++ b/pkg/merkletree/BUILD
@@ -0,0 +1,16 @@
+load("//tools:defs.bzl", "go_library", "go_test")
+
+package(licenses = ["notice"])
+
+go_library(
+ name = "merkletree",
+ srcs = ["merkletree.go"],
+ deps = ["//pkg/usermem"],
+)
+
+go_test(
+ name = "merkletree_test",
+ srcs = ["merkletree_test.go"],
+ library = ":merkletree",
+ deps = ["//pkg/usermem"],
+)
diff --git a/pkg/merkletree/merkletree.go b/pkg/merkletree/merkletree.go
new file mode 100644
index 000000000..906f67943
--- /dev/null
+++ b/pkg/merkletree/merkletree.go
@@ -0,0 +1,135 @@
+// Copyright 2020 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 merkletree implements Merkle tree generating and verification.
+package merkletree
+
+import (
+ "crypto/sha256"
+ "io"
+
+ "gvisor.dev/gvisor/pkg/usermem"
+)
+
+const (
+ // sha256DigestSize specifies the digest size of a SHA256 hash.
+ sha256DigestSize = 32
+)
+
+// Size defines the scale of a Merkle tree.
+type Size struct {
+ // blockSize is the size of a data block to be hashed.
+ blockSize int64
+ // digestSize is the size of a generated hash.
+ digestSize int64
+ // hashesPerBlock is the number of hashes in a block. For example, if
+ // blockSize is 4096 bytes, and digestSize is 32 bytes, there will be 128
+ // hashesPerBlock. Therefore 128 hashes in a lower level will be put into a
+ // block and generate a single hash in an upper level.
+ hashesPerBlock int64
+ // levelStart is the start block index of each level. The number of levels in
+ // the tree is the length of the slice. The leafs (level 0) are hashes of
+ // blocks in the input data. The levels above are hashes of lower level
+ // hashes. The highest level is the root hash.
+ levelStart []int64
+}
+
+// MakeSize initializes and returns a new Size object describing the structure
+// of a tree. dataSize specifies the number of the file system size in bytes.
+func MakeSize(dataSize int64) Size {
+ size := Size{
+ blockSize: usermem.PageSize,
+ // TODO(b/156980949): Allow config other hash methods (SHA384/SHA512).
+ digestSize: sha256DigestSize,
+ hashesPerBlock: usermem.PageSize / sha256DigestSize,
+ }
+ numBlocks := (dataSize + size.blockSize - 1) / size.blockSize
+ level := int64(0)
+ offset := int64(0)
+
+ // Calcuate the number of levels in the Merkle tree and the beginning offset
+ // of each level. Level 0 is the level directly above the data blocks, while
+ // level NumLevels - 1 is the root.
+ for numBlocks > 1 {
+ size.levelStart = append(size.levelStart, offset)
+ // Round numBlocks up to fill up a block.
+ numBlocks += (size.hashesPerBlock - numBlocks%size.hashesPerBlock) % size.hashesPerBlock
+ offset += numBlocks / size.hashesPerBlock
+ numBlocks = numBlocks / size.hashesPerBlock
+ level++
+ }
+ size.levelStart = append(size.levelStart, offset)
+ return size
+}
+
+// Generate constructs a Merkle tree for the contents of data. The output is
+// written to treeWriter. The treeReader should be able to read the tree after
+// it has been written. That is, treeWriter and treeReader should point to the
+// same underlying data but have separate cursors.
+func Generate(data io.Reader, dataSize int64, treeReader io.Reader, treeWriter io.Writer) ([]byte, error) {
+ size := MakeSize(dataSize)
+
+ numBlocks := (dataSize + size.blockSize - 1) / size.blockSize
+
+ var root []byte
+ for level := 0; level < len(size.levelStart); level++ {
+ for i := int64(0); i < numBlocks; i++ {
+ buf := make([]byte, size.blockSize)
+ var (
+ n int
+ err error
+ )
+ if level == 0 {
+ // Read data block from the target file since level 0 is directly above
+ // the raw data block.
+ n, err = data.Read(buf)
+ } else {
+ // Read data block from the tree file since levels higher than 0 are
+ // hashing the lower level hashes.
+ n, err = treeReader.Read(buf)
+ }
+
+ // err is populated as long as the bytes read is smaller than the buffer
+ // size. This could be the case if we are reading the last block, and
+ // break in that case. If this is the last block, the end of the block
+ // will be zero-padded.
+ if n == 0 && err == io.EOF {
+ break
+ } else if err != nil && err != io.EOF {
+ return nil, err
+ }
+ // Hash the bytes in buf.
+ digest := sha256.Sum256(buf)
+
+ if level == len(size.levelStart)-1 {
+ root = digest[:]
+ }
+
+ // Write the generated hash to the end of the tree file.
+ if _, err = treeWriter.Write(digest[:]); err != nil {
+ return nil, err
+ }
+ }
+ // If the genereated digests do not round up to a block, zero-padding the
+ // remaining of the last block. But no need to do so for root.
+ if level != len(size.levelStart)-1 && numBlocks%size.hashesPerBlock != 0 {
+ zeroBuf := make([]byte, size.blockSize-(numBlocks%size.hashesPerBlock)*size.digestSize)
+ if _, err := treeWriter.Write(zeroBuf[:]); err != nil {
+ return nil, err
+ }
+ }
+ numBlocks = (numBlocks + size.hashesPerBlock - 1) / size.hashesPerBlock
+ }
+ return root, nil
+}
diff --git a/pkg/merkletree/merkletree_test.go b/pkg/merkletree/merkletree_test.go
new file mode 100644
index 000000000..7344db0b6
--- /dev/null
+++ b/pkg/merkletree/merkletree_test.go
@@ -0,0 +1,122 @@
+// Copyright 2020 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 merkletree
+
+import (
+ "bytes"
+ "fmt"
+ "testing"
+
+ "gvisor.dev/gvisor/pkg/usermem"
+)
+
+func TestSize(t *testing.T) {
+ testCases := []struct {
+ dataSize int64
+ expectedLevelStart []int64
+ }{
+ {
+ dataSize: 100,
+ expectedLevelStart: []int64{0},
+ },
+ {
+ dataSize: 1000000,
+ expectedLevelStart: []int64{0, 2, 3},
+ },
+ {
+ dataSize: 4096 * int64(usermem.PageSize),
+ expectedLevelStart: []int64{0, 32, 33},
+ },
+ }
+
+ for _, tc := range testCases {
+ t.Run(fmt.Sprintf("%d", tc.dataSize), func(t *testing.T) {
+ s := MakeSize(tc.dataSize)
+ if s.blockSize != int64(usermem.PageSize) {
+ t.Errorf("got blockSize %d, want %d", s.blockSize, usermem.PageSize)
+ }
+ if s.digestSize != sha256DigestSize {
+ t.Errorf("got digestSize %d, want %d", s.digestSize, sha256DigestSize)
+ }
+ if len(s.levelStart) != len(tc.expectedLevelStart) {
+ t.Errorf("got levels %d, want %d", len(s.levelStart), len(tc.expectedLevelStart))
+ }
+ for i := 0; i < len(s.levelStart) && i < len(tc.expectedLevelStart); i++ {
+ if s.levelStart[i] != tc.expectedLevelStart[i] {
+ t.Errorf("got levelStart[%d] %d, want %d", i, s.levelStart[i], tc.expectedLevelStart[i])
+ }
+ }
+ })
+ }
+}
+
+func TestGenerate(t *testing.T) {
+ // The input data has size dataSize. It starts with the data in startWith,
+ // and all other bytes are zeroes.
+ testCases := []struct {
+ dataSize int
+ startWith []byte
+ expectedRoot []byte
+ }{
+ {
+ dataSize: usermem.PageSize,
+ startWith: nil,
+ expectedRoot: []byte{173, 127, 172, 178, 88, 111, 198, 233, 102, 192, 4, 215, 209, 209, 107, 2, 79, 88, 5, 255, 124, 180, 124, 122, 133, 218, 189, 139, 72, 137, 44, 167},
+ },
+ {
+ dataSize: 128*usermem.PageSize + 1,
+ startWith: nil,
+ expectedRoot: []byte{62, 93, 40, 92, 161, 241, 30, 223, 202, 99, 39, 2, 132, 113, 240, 139, 117, 99, 79, 243, 54, 18, 100, 184, 141, 121, 238, 46, 149, 202, 203, 132},
+ },
+ {
+ dataSize: 1,
+ startWith: []byte{'a'},
+ expectedRoot: []byte{52, 75, 204, 142, 172, 129, 37, 14, 145, 137, 103, 203, 11, 162, 209, 205, 30, 169, 213, 72, 20, 28, 243, 24, 242, 2, 92, 43, 169, 59, 110, 210},
+ },
+ {
+ dataSize: 1,
+ startWith: []byte{'1'},
+ expectedRoot: []byte{74, 35, 103, 179, 176, 149, 254, 112, 42, 65, 104, 66, 119, 56, 133, 124, 228, 15, 65, 161, 150, 0, 117, 174, 242, 34, 115, 115, 218, 37, 3, 105},
+ },
+ }
+
+ for _, tc := range testCases {
+ t.Run(fmt.Sprintf("%d", tc.dataSize), func(t *testing.T) {
+ var (
+ data bytes.Buffer
+ tree bytes.Buffer
+ )
+
+ startSize := len(tc.startWith)
+ _, err := data.Write(tc.startWith)
+ if err != nil {
+ t.Fatalf("Failed to write to data: %v", err)
+ }
+ _, err = data.Write(make([]byte, tc.dataSize-startSize))
+ if err != nil {
+ t.Fatalf("Failed to write to data: %v", err)
+ }
+
+ root, err := Generate(&data, int64(tc.dataSize), &tree, &tree)
+ if err != nil {
+ t.Fatalf("Generate failed: %v", err)
+ }
+
+ if !bytes.Equal(root, tc.expectedRoot) {
+ t.Errorf("Unexpected root")
+ }
+ })
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-16 18:52:20 +0000