sumdb/tlog: make NewTiles only generate strictly necessary tiles
Currently, NewTiles returns tiles for every partial tree size from
oldTreeSize to newTreeSize. However, if a log is only publishing
checkpoints at oldTreeSize and newTreeSize, the trees of sizes
oldTreeSize+1 to newTreeSize-1 are unverifiable, so those tiles are
unnecessary. Also, NewTiles currently returns tiles that already exists
as part of oldTreeSize, which are not new.
This has a significant performance and cost difference when uploading
tiles individually to e.g. object storage.
Change-Id: I92a5d76bc54e7022991e51997e793356ab5e7d5c
Reviewed-on: https://go-review.googlesource.com/c/mod/+/570295
Auto-Submit: Filippo Valsorda <filippo@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Russ Cox <rsc@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
diff --git a/sumdb/tlog/tile.go b/sumdb/tlog/tile.go
index 857d487..37771c5 100644
--- a/sumdb/tlog/tile.go
+++ b/sumdb/tlog/tile.go
@@ -115,16 +115,14 @@
for level := uint(0); newTreeSize>>(H*level) > 0; level++ {
oldN := oldTreeSize >> (H * level)
newN := newTreeSize >> (H * level)
+ if oldN == newN {
+ continue
+ }
for n := oldN >> H; n < newN>>H; n++ {
tiles = append(tiles, Tile{H: h, L: int(level), N: n, W: 1 << H})
}
n := newN >> H
- maxW := int(newN - n<<H)
- minW := 1
- if oldN > n<<H {
- minW = int(oldN - n<<H)
- }
- for w := minW; w <= maxW; w++ {
+ if w := int(newN - n<<H); w > 0 {
tiles = append(tiles, Tile{H: h, L: int(level), N: n, W: w})
}
}
diff --git a/sumdb/tlog/tile_test.go b/sumdb/tlog/tile_test.go
index e451a63..62b50b7 100644
--- a/sumdb/tlog/tile_test.go
+++ b/sumdb/tlog/tile_test.go
@@ -5,6 +5,7 @@
package tlog
import (
+ "fmt"
"testing"
)
@@ -22,3 +23,28 @@
ParseTilePath(path)
})
}
+
+func TestNewTilesForSize(t *testing.T) {
+ for _, tt := range []struct {
+ old, new int64
+ want int
+ }{
+ {1, 1, 0},
+ {100, 101, 1},
+ {1023, 1025, 3},
+ {1024, 1030, 1},
+ {1030, 2000, 1},
+ {1030, 10000, 10},
+ {49516517, 49516586, 3},
+ } {
+ t.Run(fmt.Sprintf("%d-%d", tt.old, tt.new), func(t *testing.T) {
+ tiles := NewTiles(10, tt.old, tt.new)
+ if got := len(tiles); got != tt.want {
+ t.Errorf("got %d, want %d", got, tt.want)
+ for _, tile := range tiles {
+ t.Logf("%+v", tile)
+ }
+ }
+ })
+ }
+}
