.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/mod@v0.4.1/sumdb/tlog/tile.go

   1 // Copyright 2019 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package tlog
   6
   7 import (
   8         "fmt"
   9         "strconv"
  10         "strings"
  11 )
  12
  13 // A Tile is a description of a transparency log tile.
  14 // A tile of height H at level L offset N lists W consecutive hashes
  15 // at level H*L of the tree starting at offset N*(2**H).
  16 // A complete tile lists 2**H hashes; a partial tile lists fewer.
  17 // Note that a tile represents the entire subtree of height H
  18 // with those hashes as the leaves. The levels above H*L
  19 // can be reconstructed by hashing the leaves.
  20 //
  21 // Each Tile can be encoded as a “tile coordinate path”
  22 // of the form tile/H/L/NNN[.p/W].
  23 // The .p/W suffix is present only for partial tiles, meaning W < 2**H.
  24 // The NNN element is an encoding of N into 3-digit path elements.
  25 // All but the last path element begins with an "x".
  26 // For example,
  27 // Tile{H: 3, L: 4, N: 1234067, W: 1}'s path
  28 // is tile/3/4/x001/x234/067.p/1, and
  29 // Tile{H: 3, L: 4, N: 1234067, W: 8}'s path
  30 // is tile/3/4/x001/x234/067.
  31 // See Tile's Path method and the ParseTilePath function.
  32 //
  33 // The special level L=-1 holds raw record data instead of hashes.
  34 // In this case, the level encodes into a tile path as the path element
  35 // "data" instead of "-1".
  36 //
  37 // See also https://golang.org/design/25530-sumdb#checksum-database
  38 // and https://research.swtch.com/tlog#tiling_a_log.
  39 type Tile struct {
  40         H int   // height of tile (1 ≤ H ≤ 30)
  41         L int   // level in tiling (-1 ≤ L ≤ 63)
  42         N int64 // number within level (0 ≤ N, unbounded)
  43         W int   // width of tile (1 ≤ W ≤ 2**H; 2**H is complete tile)
  44 }
  45
  46 // TileForIndex returns the tile of fixed height h ≥ 1
  47 // and least width storing the given hash storage index.
  48 //
  49 // If h ≤ 0, TileForIndex panics.
  50 func TileForIndex(h int, index int64) Tile {
  51         if h <= 0 {
  52                 panic(fmt.Sprintf("TileForIndex: invalid height %d", h))
  53         }
  54         t, _, _ := tileForIndex(h, index)
  55         return t
  56 }
  57
  58 // tileForIndex returns the tile of height h ≥ 1
  59 // storing the given hash index, which can be
  60 // reconstructed using tileHash(data[start:end]).
  61 func tileForIndex(h int, index int64) (t Tile, start, end int) {
  62         level, n := SplitStoredHashIndex(index)
  63         t.H = h
  64         t.L = level / h
  65         level -= t.L * h // now level within tile
  66         t.N = n << uint(level) >> uint(t.H)
  67         n -= t.N << uint(t.H) >> uint(level) // now n within tile at level
  68         t.W = int((n + 1) << uint(level))
  69         return t, int(n<<uint(level)) * HashSize, int((n+1)<<uint(level)) * HashSize
  70 }
  71
  72 // HashFromTile returns the hash at the given storage index,
  73 // provided that t == TileForIndex(t.H, index) or a wider version,
  74 // and data is t's tile data (of length at least t.W*HashSize).
  75 func HashFromTile(t Tile, data []byte, index int64) (Hash, error) {
  76         if t.H < 1 || t.H > 30 || t.L < 0 || t.L >= 64 || t.W < 1 || t.W > 1<<uint(t.H) {
  77                 return Hash{}, fmt.Errorf("invalid tile %v", t.Path())
  78         }
  79         if len(data) < t.W*HashSize {
  80                 return Hash{}, fmt.Errorf("data len %d too short for tile %v", len(data), t.Path())
  81         }
  82         t1, start, end := tileForIndex(t.H, index)
  83         if t.L != t1.L || t.N != t1.N || t.W < t1.W {
  84                 return Hash{}, fmt.Errorf("index %v is in %v not %v", index, t1.Path(), t.Path())
  85         }
  86         return tileHash(data[start:end]), nil
  87 }
  88
  89 // tileHash computes the subtree hash corresponding to the (2^K)-1 hashes in data.
  90 func tileHash(data []byte) Hash {
  91         if len(data) == 0 {
  92                 panic("bad math in tileHash")
  93         }
  94         if len(data) == HashSize {
  95                 var h Hash
  96                 copy(h[:], data)
  97                 return h
  98         }
  99         n := len(data) / 2
 100         return NodeHash(tileHash(data[:n]), tileHash(data[n:]))
 101 }
 102
 103 // NewTiles returns the coordinates of the tiles of height h ≥ 1
 104 // that must be published when publishing from a tree of
 105 // size newTreeSize to replace a tree of size oldTreeSize.
 106 // (No tiles need to be published for a tree of size zero.)
 107 //
 108 // If h ≤ 0, TileForIndex panics.
 109 func NewTiles(h int, oldTreeSize, newTreeSize int64) []Tile {
 110         if h <= 0 {
 111                 panic(fmt.Sprintf("NewTiles: invalid height %d", h))
 112         }
 113         H := uint(h)
 114         var tiles []Tile
 115         for level := uint(0); newTreeSize>>(H*level) > 0; level++ {
 116                 oldN := oldTreeSize >> (H * level)
 117                 newN := newTreeSize >> (H * level)
 118                 for n := oldN >> H; n < newN>>H; n++ {
 119                         tiles = append(tiles, Tile{H: h, L: int(level), N: n, W: 1 << H})
 120                 }
 121                 n := newN >> H
 122                 maxW := int(newN - n<<H)
 123                 minW := 1
 124                 if oldN > n<<H {
 125                         minW = int(oldN - n<<H)
 126                 }
 127                 for w := minW; w <= maxW; w++ {
 128                         tiles = append(tiles, Tile{H: h, L: int(level), N: n, W: w})
 129                 }
 130         }
 131         return tiles
 132 }
 133
 134 // ReadTileData reads the hashes for tile t from r
 135 // and returns the corresponding tile data.
 136 func ReadTileData(t Tile, r HashReader) ([]byte, error) {
 137         size := t.W
 138         if size == 0 {
 139                 size = 1 << uint(t.H)
 140         }
 141         start := t.N << uint(t.H)
 142         indexes := make([]int64, size)
 143         for i := 0; i < size; i++ {
 144                 indexes[i] = StoredHashIndex(t.H*t.L, start+int64(i))
 145         }
 146
 147         hashes, err := r.ReadHashes(indexes)
 148         if err != nil {
 149                 return nil, err
 150         }
 151         if len(hashes) != len(indexes) {
 152                 return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
 153         }
 154
 155         tile := make([]byte, size*HashSize)
 156         for i := 0; i < size; i++ {
 157                 copy(tile[i*HashSize:], hashes[i][:])
 158         }
 159         return tile, nil
 160 }
 161
 162 // To limit the size of any particular directory listing,
 163 // we encode the (possibly very large) number N
 164 // by encoding three digits at a time.
 165 // For example, 123456789 encodes as x123/x456/789.
 166 // Each directory has at most 1000 each xNNN, NNN, and NNN.p children,
 167 // so there are at most 3000 entries in any one directory.
 168 const pathBase = 1000
 169
 170 // Path returns a tile coordinate path describing t.
 171 func (t Tile) Path() string {
 172         n := t.N
 173         nStr := fmt.Sprintf("%03d", n%pathBase)
 174         for n >= pathBase {
 175                 n /= pathBase
 176                 nStr = fmt.Sprintf("x%03d/%s", n%pathBase, nStr)
 177         }
 178         pStr := ""
 179         if t.W != 1<<uint(t.H) {
 180                 pStr = fmt.Sprintf(".p/%d", t.W)
 181         }
 182         var L string
 183         if t.L == -1 {
 184                 L = "data"
 185         } else {
 186                 L = fmt.Sprintf("%d", t.L)
 187         }
 188         return fmt.Sprintf("tile/%d/%s/%s%s", t.H, L, nStr, pStr)
 189 }
 190
 191 // ParseTilePath parses a tile coordinate path.
 192 func ParseTilePath(path string) (Tile, error) {
 193         f := strings.Split(path, "/")
 194         if len(f) < 4 || f[0] != "tile" {
 195                 return Tile{}, &badPathError{path}
 196         }
 197         h, err1 := strconv.Atoi(f[1])
 198         isData := false
 199         if f[2] == "data" {
 200                 isData = true
 201                 f[2] = "0"
 202         }
 203         l, err2 := strconv.Atoi(f[2])
 204         if err1 != nil || err2 != nil || h < 1 || l < 0 || h > 30 {
 205                 return Tile{}, &badPathError{path}
 206         }
 207         w := 1 << uint(h)
 208         if dotP := f[len(f)-2]; strings.HasSuffix(dotP, ".p") {
 209                 ww, err := strconv.Atoi(f[len(f)-1])
 210                 if err != nil || ww <= 0 || ww >= w {
 211                         return Tile{}, &badPathError{path}
 212                 }
 213                 w = ww
 214                 f[len(f)-2] = dotP[:len(dotP)-len(".p")]
 215                 f = f[:len(f)-1]
 216         }
 217         f = f[3:]
 218         n := int64(0)
 219         for _, s := range f {
 220                 nn, err := strconv.Atoi(strings.TrimPrefix(s, "x"))
 221                 if err != nil || nn < 0 || nn >= pathBase {
 222                         return Tile{}, &badPathError{path}
 223                 }
 224                 n = n*pathBase + int64(nn)
 225         }
 226         if isData {
 227                 l = -1
 228         }
 229         t := Tile{H: h, L: l, N: n, W: w}
 230         if path != t.Path() {
 231                 return Tile{}, &badPathError{path}
 232         }
 233         return t, nil
 234 }
 235
 236 type badPathError struct {
 237         path string
 238 }
 239
 240 func (e *badPathError) Error() string {
 241         return fmt.Sprintf("malformed tile path %q", e.path)
 242 }
 243
 244 // A TileReader reads tiles from a go.sum database log.
 245 type TileReader interface {
 246         // Height returns the height of the available tiles.
 247         Height() int
 248
 249         // ReadTiles returns the data for each requested tile.
 250         // If ReadTiles returns err == nil, it must also return
 251         // a data record for each tile (len(data) == len(tiles))
 252         // and each data record must be the correct length
 253         // (len(data[i]) == tiles[i].W*HashSize).
 254         //
 255         // An implementation of ReadTiles typically reads
 256         // them from an on-disk cache or else from a remote
 257         // tile server. Tile data downloaded from a server should
 258         // be considered suspect and not saved into a persistent
 259         // on-disk cache before returning from ReadTiles.
 260         // When the client confirms the validity of the tile data,
 261         // it will call SaveTiles to signal that they can be safely
 262         // written to persistent storage.
 263         // See also https://research.swtch.com/tlog#authenticating_tiles.
 264         ReadTiles(tiles []Tile) (data [][]byte, err error)
 265
 266         // SaveTiles informs the TileReader that the tile data
 267         // returned by ReadTiles has been confirmed as valid
 268         // and can be saved in persistent storage (on disk).
 269         SaveTiles(tiles []Tile, data [][]byte)
 270 }
 271
 272 // TileHashReader returns a HashReader that satisfies requests
 273 // by loading tiles of the given tree.
 274 //
 275 // The returned HashReader checks that loaded tiles are
 276 // valid for the given tree. Therefore, any hashes returned
 277 // by the HashReader are already proven to be in the tree.
 278 func TileHashReader(tree Tree, tr TileReader) HashReader {
 279         return &tileHashReader{tree: tree, tr: tr}
 280 }
 281
 282 type tileHashReader struct {
 283         tree Tree
 284         tr   TileReader
 285 }
 286
 287 // tileParent returns t's k'th tile parent in the tiles for a tree of size n.
 288 // If there is no such parent, tileParent returns Tile{}.
 289 func tileParent(t Tile, k int, n int64) Tile {
 290         t.L += k
 291         t.N >>= uint(k * t.H)
 292         t.W = 1 << uint(t.H)
 293         if max := n >> uint(t.L*t.H); t.N<<uint(t.H)+int64(t.W) >= max {
 294                 if t.N<<uint(t.H) >= max {
 295                         return Tile{}
 296                 }
 297                 t.W = int(max - t.N<<uint(t.H))
 298         }
 299         return t
 300 }
 301
 302 func (r *tileHashReader) ReadHashes(indexes []int64) ([]Hash, error) {
 303         h := r.tr.Height()
 304
 305         tileOrder := make(map[Tile]int) // tileOrder[tileKey(tiles[i])] = i
 306         var tiles []Tile
 307
 308         // Plan to fetch tiles necessary to recompute tree hash.
 309         // If it matches, those tiles are authenticated.
 310         stx := subTreeIndex(0, r.tree.N, nil)
 311         stxTileOrder := make([]int, len(stx))
 312         for i, x := range stx {
 313                 tile, _, _ := tileForIndex(h, x)
 314                 tile = tileParent(tile, 0, r.tree.N)
 315                 if j, ok := tileOrder[tile]; ok {
 316                         stxTileOrder[i] = j
 317                         continue
 318                 }
 319                 stxTileOrder[i] = len(tiles)
 320                 tileOrder[tile] = len(tiles)
 321                 tiles = append(tiles, tile)
 322         }
 323
 324         // Plan to fetch tiles containing the indexes,
 325         // along with any parent tiles needed
 326         // for authentication. For most calls,
 327         // the parents are being fetched anyway.
 328         indexTileOrder := make([]int, len(indexes))
 329         for i, x := range indexes {
 330                 if x >= StoredHashIndex(0, r.tree.N) {
 331                         return nil, fmt.Errorf("indexes not in tree")
 332                 }
 333
 334                 tile, _, _ := tileForIndex(h, x)
 335
 336                 // Walk up parent tiles until we find one we've requested.
 337                 // That one will be authenticated.
 338                 k := 0
 339                 for ; ; k++ {
 340                         p := tileParent(tile, k, r.tree.N)
 341                         if j, ok := tileOrder[p]; ok {
 342                                 if k == 0 {
 343                                         indexTileOrder[i] = j
 344                                 }
 345                                 break
 346                         }
 347                 }
 348
 349                 // Walk back down recording child tiles after parents.
 350                 // This loop ends by revisiting the tile for this index
 351                 // (tileParent(tile, 0, r.tree.N)) unless k == 0, in which
 352                 // case the previous loop did it.
 353                 for k--; k >= 0; k-- {
 354                         p := tileParent(tile, k, r.tree.N)
 355                         if p.W != 1<<uint(p.H) {
 356                                 // Only full tiles have parents.
 357                                 // This tile has a parent, so it must be full.
 358                                 return nil, fmt.Errorf("bad math in tileHashReader: %d %d %v", r.tree.N, x, p)
 359                         }
 360                         tileOrder[p] = len(tiles)
 361                         if k == 0 {
 362                                 indexTileOrder[i] = len(tiles)
 363                         }
 364                         tiles = append(tiles, p)
 365                 }
 366         }
 367
 368         // Fetch all the tile data.
 369         data, err := r.tr.ReadTiles(tiles)
 370         if err != nil {
 371                 return nil, err
 372         }
 373         if len(data) != len(tiles) {
 374                 return nil, fmt.Errorf("TileReader returned bad result slice (len=%d, want %d)", len(data), len(tiles))
 375         }
 376         for i, tile := range tiles {
 377                 if len(data[i]) != tile.W*HashSize {
 378                         return nil, fmt.Errorf("TileReader returned bad result slice (%v len=%d, want %d)", tile.Path(), len(data[i]), tile.W*HashSize)
 379                 }
 380         }
 381
 382         // Authenticate the initial tiles against the tree hash.
 383         // They are arranged so that parents are authenticated before children.
 384         // First the tiles needed for the tree hash.
 385         th, err := HashFromTile(tiles[stxTileOrder[len(stx)-1]], data[stxTileOrder[len(stx)-1]], stx[len(stx)-1])
 386         if err != nil {
 387                 return nil, err
 388         }
 389         for i := len(stx) - 2; i >= 0; i-- {
 390                 h, err := HashFromTile(tiles[stxTileOrder[i]], data[stxTileOrder[i]], stx[i])
 391                 if err != nil {
 392                         return nil, err
 393                 }
 394                 th = NodeHash(h, th)
 395         }
 396         if th != r.tree.Hash {
 397                 // The tiles do not support the tree hash.
 398                 // We know at least one is wrong, but not which one.
 399                 return nil, fmt.Errorf("downloaded inconsistent tile")
 400         }
 401
 402         // Authenticate full tiles against their parents.
 403         for i := len(stx); i < len(tiles); i++ {
 404                 tile := tiles[i]
 405                 p := tileParent(tile, 1, r.tree.N)
 406                 j, ok := tileOrder[p]
 407                 if !ok {
 408                         return nil, fmt.Errorf("bad math in tileHashReader %d %v: lost parent of %v", r.tree.N, indexes, tile)
 409                 }
 410                 h, err := HashFromTile(p, data[j], StoredHashIndex(p.L*p.H, tile.N))
 411                 if err != nil {
 412                         return nil, fmt.Errorf("bad math in tileHashReader %d %v: lost hash of %v: %v", r.tree.N, indexes, tile, err)
 413                 }
 414                 if h != tileHash(data[i]) {
 415                         return nil, fmt.Errorf("downloaded inconsistent tile")
 416                 }
 417         }
 418
 419         // Now we have all the tiles needed for the requested hashes,
 420         // and we've authenticated the full tile set against the trusted tree hash.
 421         r.tr.SaveTiles(tiles, data)
 422
 423         // Pull out the requested hashes.
 424         hashes := make([]Hash, len(indexes))
 425         for i, x := range indexes {
 426                 j := indexTileOrder[i]
 427                 h, err := HashFromTile(tiles[j], data[j], x)
 428                 if err != nil {
 429                         return nil, fmt.Errorf("bad math in tileHashReader %d %v: lost hash %v: %v", r.tree.N, indexes, x, err)
 430                 }
 431                 hashes[i] = h
 432         }
 433
 434         return hashes, nil
 435 }