Speed up globs with sharding

There are a few cases that force all globs to be rerun at the beginning
of the build (changes to bpglob or dependencies, second build after a
clean build).  The number of globs has gotten high enough that rerunning
them all can have significant overhead to start bpglob for each one.

Replace the per-glob bpglob invocations with sharded invocations using
1024 hash buckets.

Bug: 159845846
Test: glob_test.go
Test: m nothing && m nothing
Test: build/soong/bootstrap_test.sh
Change-Id: Ife1f7a03c8f6b25d1be01531425d8dc2c76d1ea0

1 files changed, 37 insertions, 56 deletions

diff --git a/glob.go b/glob.go
index 67d060e..91ae723 100644
--- a/glob.go
+++ b/glob.go
@@ -15,50 +15,44 @@
 package blueprint
 
 import (
-	"crypto/md5"
 	"fmt"
-	"path/filepath"
 	"sort"
 	"strings"
 
 	"github.com/google/blueprint/pathtools"
 )
 
-type GlobPath struct {
-	pathtools.GlobResult
-	Name string
-}
-
-func (g *GlobPath) FileListFile(buildDir string) string {
-	return filepath.Join(buildDir, ".glob", g.Name)
-}
-
-func verifyGlob(fileName, pattern string, excludes []string, g GlobPath) {
+func verifyGlob(key globKey, pattern string, excludes []string, g pathtools.GlobResult) {
 	if pattern != g.Pattern {
-		panic(fmt.Errorf("Mismatched patterns %q and %q for glob file %q", pattern, g.Pattern, fileName))
+		panic(fmt.Errorf("Mismatched patterns %q and %q for glob key %q", pattern, g.Pattern, key))
 	}
 	if len(excludes) != len(g.Excludes) {
-		panic(fmt.Errorf("Mismatched excludes %v and %v for glob file %q", excludes, g.Excludes, fileName))
+		panic(fmt.Errorf("Mismatched excludes %v and %v for glob key %q", excludes, g.Excludes, key))
 	}
 
 	for i := range excludes {
 		if g.Excludes[i] != excludes[i] {
-			panic(fmt.Errorf("Mismatched excludes %v and %v for glob file %q", excludes, g.Excludes, fileName))
+			panic(fmt.Errorf("Mismatched excludes %v and %v for glob key %q", excludes, g.Excludes, key))
 		}
 	}
 }
 
 func (c *Context) glob(pattern string, excludes []string) ([]string, error) {
-	fileName := globToFileName(pattern, excludes)
+	// Sort excludes so that two globs with the same excludes in a different order reuse the same
+	// key.  Make a copy first to avoid modifying the caller's version.
+	excludes = append([]string(nil), excludes...)
+	sort.Strings(excludes)
+
+	key := globToKey(pattern, excludes)
 
 	// Try to get existing glob from the stored results
 	c.globLock.Lock()
-	g, exists := c.globs[fileName]
+	g, exists := c.globs[key]
 	c.globLock.Unlock()
 
 	if exists {
 		// Glob has already been done, double check it is identical
-		verifyGlob(fileName, pattern, excludes, g)
+		verifyGlob(key, pattern, excludes, g)
 		// Return a copy so that modifications don't affect the cached value.
 		return append([]string(nil), g.Matches...), nil
 	}
@@ -71,14 +65,14 @@ func (c *Context) glob(pattern string, excludes []string) ([]string, error) {
 
 	// Store the results
 	c.globLock.Lock()
-	if g, exists = c.globs[fileName]; !exists {
-		c.globs[fileName] = GlobPath{result, fileName}
+	if g, exists = c.globs[key]; !exists {
+		c.globs[key] = result
 	}
 	c.globLock.Unlock()
 
 	if exists {
 		// Getting the list raced with another goroutine, throw away the results and use theirs
-		verifyGlob(fileName, pattern, excludes, g)
+		verifyGlob(key, pattern, excludes, g)
 		// Return a copy so that modifications don't affect the cached value.
 		return append([]string(nil), g.Matches...), nil
 	}
@@ -87,49 +81,36 @@ func (c *Context) glob(pattern string, excludes []string) ([]string, error) {
 	return append([]string(nil), result.Matches...), nil
 }
 
-func (c *Context) Globs() []GlobPath {
-	fileNames := make([]string, 0, len(c.globs))
+func (c *Context) Globs() pathtools.MultipleGlobResults {
+	keys := make([]globKey, 0, len(c.globs))
 	for k := range c.globs {
-		fileNames = append(fileNames, k)
+		keys = append(keys, k)
 	}
-	sort.Strings(fileNames)
 
-	globs := make([]GlobPath, len(fileNames))
-	for i, fileName := range fileNames {
-		globs[i] = c.globs[fileName]
+	sort.Slice(keys, func(i, j int) bool {
+		if keys[i].pattern != keys[j].pattern {
+			return keys[i].pattern < keys[j].pattern
+		}
+		return keys[i].excludes < keys[j].excludes
+	})
+
+	globs := make(pathtools.MultipleGlobResults, len(keys))
+	for i, key := range keys {
+		globs[i] = c.globs[key]
 	}
 
 	return globs
 }
 
-func globToString(pattern string) string {
-	ret := ""
-	for _, c := range pattern {
-		switch {
-		case c >= 'a' && c <= 'z',
-			c >= 'A' && c <= 'Z',
-			c >= '0' && c <= '9',
-			c == '_', c == '-', c == '/':
-			ret += string(c)
-		default:
-			ret += "_"
-		}
-	}
-
-	return ret
+// globKey combines a pattern and a list of excludes into a hashable struct to be used as a key in
+// a map.
+type globKey struct {
+	pattern  string
+	excludes string
 }
 
-func globToFileName(pattern string, excludes []string) string {
-	name := globToString(pattern)
-	excludeName := ""
-	for _, e := range excludes {
-		excludeName += "__" + globToString(e)
-	}
-
-	// Prevent file names from reaching ninja's path component limit
-	if strings.Count(name, "/")+strings.Count(excludeName, "/") > 30 {
-		excludeName = fmt.Sprintf("___%x", md5.Sum([]byte(excludeName)))
-	}
-
-	return name + excludeName + ".glob"
+// globToKey converts a pattern and an excludes list into a globKey struct that is hashable and
+// usable as a key in a map.
+func globToKey(pattern string, excludes []string) globKey {
+	return globKey{pattern, strings.Join(excludes, "|")}
 }