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

View as plain text