From b39cc6a80074663047d0c6a4e7cd1b08ab01fec8 Mon Sep 17 00:00:00 2001 From: gVisor bot Date: Thu, 11 Jun 2020 12:21:37 -0700 Subject: Add merkle tree size measure This change creates a merkletree package which will be used in the future for an implementation of file system API. PiperOrigin-RevId: 315952451 --- pkg/merkletree/BUILD | 16 +++++++++ pkg/merkletree/merkletree.go | 71 +++++++++++++++++++++++++++++++++++++++ pkg/merkletree/merkletree_test.go | 62 ++++++++++++++++++++++++++++++++++ 3 files changed, 149 insertions(+) create mode 100644 pkg/merkletree/BUILD create mode 100644 pkg/merkletree/merkletree.go create mode 100644 pkg/merkletree/merkletree_test.go 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..965f3670b --- /dev/null +++ b/pkg/merkletree/merkletree.go @@ -0,0 +1,71 @@ +// 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 ( + "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 +} diff --git a/pkg/merkletree/merkletree_test.go b/pkg/merkletree/merkletree_test.go new file mode 100644 index 000000000..6221eec07 --- /dev/null +++ b/pkg/merkletree/merkletree_test.go @@ -0,0 +1,62 @@ +// 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 ( + "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]) + } + } + }) + } +} -- cgit v1.2.3