12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565 |
- // Copyright 2017 Google Inc. All rights reserved.
- //
- // 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 finder
- import (
- "bufio"
- "bytes"
- "encoding/json"
- "errors"
- "fmt"
- "io"
- "os"
- "path/filepath"
- "runtime"
- "sort"
- "strings"
- "sync"
- "sync/atomic"
- "time"
- "android/soong/finder/fs"
- )
- // This file provides a Finder struct that can quickly search for files satisfying
- // certain criteria.
- // This Finder gets its speed partially from parallelism and partially from caching.
- // If a Stat call returns the same result as last time, then it means Finder
- // can skip the ReadDir call for that dir.
- // The primary data structure used by the finder is the field Finder.nodes ,
- // which is a tree of nodes of type *pathMap .
- // Each node represents a directory on disk, along with its stats, subdirectories,
- // and contained files.
- // The common use case for the Finder is that the caller creates a Finder and gives
- // it the same query that was given to it in the previous execution.
- // In this situation, the major events that take place are:
- // 1. The Finder begins to load its db
- // 2. The Finder begins to stat the directories mentioned in its db (using multiple threads)
- // Calling Stat on each of these directories is generally a large fraction of the total time
- // 3. The Finder begins to construct a separate tree of nodes in each of its threads
- // 4. The Finder merges the individual node trees into the main node tree
- // 5. The Finder may call ReadDir a few times if there are a few directories that are out-of-date
- // These ReadDir calls might prompt additional Stat calls, etc
- // 6. The Finder waits for all loading to complete
- // 7. The Finder searches the cache for files matching the user's query (using multiple threads)
- // These are the invariants regarding concurrency:
- // 1. The public methods of Finder are threadsafe.
- // The public methods are only performance-optimized for one caller at a time, however.
- // For the moment, multiple concurrent callers shouldn't expect any better performance than
- // multiple serial callers.
- // 2. While building the node tree, only one thread may ever access the <children> collection of a
- // *pathMap at once.
- // a) The thread that accesses the <children> collection is the thread that discovers the
- // children (by reading them from the cache or by having received a response to ReadDir).
- // 1) Consequently, the thread that discovers the children also spawns requests to stat
- // subdirs.
- // b) Consequently, while building the node tree, no thread may do a lookup of its
- // *pathMap via filepath because another thread may be adding children to the
- // <children> collection of an ancestor node. Additionally, in rare cases, another thread
- // may be removing children from an ancestor node if the children were only discovered to
- // be irrelevant after calling ReadDir (which happens if a prune-file was just added).
- // 3. No query will begin to be serviced until all loading (both reading the db
- // and scanning the filesystem) is complete.
- // Tests indicate that it only takes about 10% as long to search the in-memory cache as to
- // generate it, making this not a huge loss in performance.
- // 4. The parsing of the db and the initial setup of the pathMap tree must complete before
- // beginning to call listDirSync (because listDirSync can create new entries in the pathMap)
- // see cmd/finder.go or finder_test.go for usage examples
- // Update versionString whenever making a backwards-incompatible change to the cache file format
- const versionString = "Android finder version 1"
- // a CacheParams specifies which files and directories the user wishes be scanned and
- // potentially added to the cache
- type CacheParams struct {
- // WorkingDirectory is used as a base for any relative file paths given to the Finder
- WorkingDirectory string
- // RootDirs are the root directories used to initiate the search
- RootDirs []string
- // Whether symlinks are followed. If set, symlinks back to their own parent
- // directory don't work.
- FollowSymlinks bool
- // ExcludeDirs are directory names that if encountered are removed from the search
- ExcludeDirs []string
- // PruneFiles are file names that if encountered prune their entire directory
- // (including siblings)
- PruneFiles []string
- // IncludeFiles are file names to include as matches
- IncludeFiles []string
- // IncludeSuffixes are filename suffixes to include as matches.
- IncludeSuffixes []string
- }
- // a cacheConfig stores the inputs that determine what should be included in the cache
- type cacheConfig struct {
- CacheParams
- // FilesystemView is a unique identifier telling which parts of which file systems
- // are readable by the Finder. In practice its value is essentially username@hostname.
- // FilesystemView is set to ensure that a cache file copied to another host or
- // found by another user doesn't inadvertently get reused.
- FilesystemView string
- }
- func (p *cacheConfig) Dump() ([]byte, error) {
- bytes, err := json.Marshal(p)
- return bytes, err
- }
- // a cacheMetadata stores version information about the cache
- type cacheMetadata struct {
- // The Version enables the Finder to determine whether it can even parse the file
- // If the version changes, the entire cache file must be regenerated
- Version string
- // The CacheParams enables the Finder to determine whether the parameters match
- // If the CacheParams change, the Finder can choose how much of the cache file to reuse
- // (although in practice, the Finder will probably choose to ignore the entire file anyway)
- Config cacheConfig
- }
- type Logger interface {
- Output(calldepth int, s string) error
- }
- // the Finder is the main struct that callers will want to use
- type Finder struct {
- // configuration
- DbPath string
- numDbLoadingThreads int
- numSearchingThreads int
- cacheMetadata cacheMetadata
- logger Logger
- filesystem fs.FileSystem
- // temporary state
- threadPool *threadPool
- mutex sync.Mutex
- fsErrs []fsErr
- errlock sync.Mutex
- shutdownWaitgroup sync.WaitGroup
- // non-temporary state
- modifiedFlag int32
- nodes pathMap
- }
- var defaultNumThreads = runtime.NumCPU() * 2
- // New creates a new Finder for use
- func New(cacheParams CacheParams, filesystem fs.FileSystem,
- logger Logger, dbPath string) (f *Finder, err error) {
- return newImpl(cacheParams, filesystem, logger, dbPath, defaultNumThreads)
- }
- // newImpl is like New but accepts more params
- func newImpl(cacheParams CacheParams, filesystem fs.FileSystem,
- logger Logger, dbPath string, numThreads int) (f *Finder, err error) {
- numDbLoadingThreads := numThreads
- numSearchingThreads := numThreads
- metadata := cacheMetadata{
- Version: versionString,
- Config: cacheConfig{
- CacheParams: cacheParams,
- FilesystemView: filesystem.ViewId(),
- },
- }
- f = &Finder{
- numDbLoadingThreads: numDbLoadingThreads,
- numSearchingThreads: numSearchingThreads,
- cacheMetadata: metadata,
- logger: logger,
- filesystem: filesystem,
- nodes: *newPathMap("/"),
- DbPath: dbPath,
- shutdownWaitgroup: sync.WaitGroup{},
- }
- f.loadFromFilesystem()
- // check for any filesystem errors
- err = f.getErr()
- if err != nil {
- return nil, err
- }
- // confirm that every path mentioned in the CacheConfig exists
- for _, path := range cacheParams.RootDirs {
- if !filepath.IsAbs(path) {
- path = filepath.Join(f.cacheMetadata.Config.WorkingDirectory, path)
- }
- node := f.nodes.GetNode(filepath.Clean(path), false)
- if node == nil || node.ModTime == 0 {
- return nil, fmt.Errorf("path %v was specified to be included in the cache but does not exist\n", path)
- }
- }
- return f, nil
- }
- // FindNamed searches for every cached file
- func (f *Finder) FindAll() []string {
- return f.FindAt("/")
- }
- // FindNamed searches for every cached file under <rootDir>
- func (f *Finder) FindAt(rootDir string) []string {
- filter := func(entries DirEntries) (dirNames []string, fileNames []string) {
- return entries.DirNames, entries.FileNames
- }
- return f.FindMatching(rootDir, filter)
- }
- // FindNamed searches for every cached file named <fileName>
- func (f *Finder) FindNamed(fileName string) []string {
- return f.FindNamedAt("/", fileName)
- }
- // FindNamedAt searches under <rootPath> for every file named <fileName>
- // The reason a caller might use FindNamedAt instead of FindNamed is if they want
- // to limit their search to a subset of the cache
- func (f *Finder) FindNamedAt(rootPath string, fileName string) []string {
- filter := func(entries DirEntries) (dirNames []string, fileNames []string) {
- matches := []string{}
- for _, foundName := range entries.FileNames {
- if foundName == fileName {
- matches = append(matches, foundName)
- }
- }
- return entries.DirNames, matches
- }
- return f.FindMatching(rootPath, filter)
- }
- // FindFirstNamed searches for every file named <fileName>
- // Whenever it finds a match, it stops search subdirectories
- func (f *Finder) FindFirstNamed(fileName string) []string {
- return f.FindFirstNamedAt("/", fileName)
- }
- // FindFirstNamedAt searches for every file named <fileName>
- // Whenever it finds a match, it stops search subdirectories
- func (f *Finder) FindFirstNamedAt(rootPath string, fileName string) []string {
- filter := func(entries DirEntries) (dirNames []string, fileNames []string) {
- matches := []string{}
- for _, foundName := range entries.FileNames {
- if foundName == fileName {
- matches = append(matches, foundName)
- }
- }
- if len(matches) > 0 {
- return []string{}, matches
- }
- return entries.DirNames, matches
- }
- return f.FindMatching(rootPath, filter)
- }
- // FindMatching is the most general exported function for searching for files in the cache
- // The WalkFunc will be invoked repeatedly and is expected to modify the provided DirEntries
- // in place, removing file paths and directories as desired.
- // WalkFunc will be invoked potentially many times in parallel, and must be threadsafe.
- func (f *Finder) FindMatching(rootPath string, filter WalkFunc) []string {
- // set up some parameters
- scanStart := time.Now()
- var isRel bool
- workingDir := f.cacheMetadata.Config.WorkingDirectory
- isRel = !filepath.IsAbs(rootPath)
- if isRel {
- rootPath = filepath.Join(workingDir, rootPath)
- }
- rootPath = filepath.Clean(rootPath)
- // ensure nothing else is using the Finder
- f.verbosef("FindMatching waiting for finder to be idle\n")
- f.lock()
- defer f.unlock()
- node := f.nodes.GetNode(rootPath, false)
- if node == nil {
- f.verbosef("No data for path %v ; apparently not included in cache params: %v\n",
- rootPath, f.cacheMetadata.Config.CacheParams)
- // path is not found; don't do a search
- return []string{}
- }
- // search for matching files
- f.verbosef("Finder finding %v using cache\n", rootPath)
- results := f.findInCacheMultithreaded(node, filter, f.numSearchingThreads)
- // format and return results
- if isRel {
- for i := 0; i < len(results); i++ {
- results[i] = strings.Replace(results[i], workingDir+"/", "", 1)
- }
- }
- sort.Strings(results)
- f.verbosef("Found %v files under %v in %v using cache\n",
- len(results), rootPath, time.Since(scanStart))
- return results
- }
- // Shutdown declares that the finder is no longer needed and waits for its cleanup to complete
- // Currently, that only entails waiting for the database dump to complete.
- func (f *Finder) Shutdown() {
- f.WaitForDbDump()
- }
- // WaitForDbDump returns once the database has been written to f.DbPath.
- func (f *Finder) WaitForDbDump() {
- f.shutdownWaitgroup.Wait()
- }
- // End of public api
- func (f *Finder) goDumpDb() {
- if f.wasModified() {
- f.shutdownWaitgroup.Add(1)
- go func() {
- err := f.dumpDb()
- if err != nil {
- f.verbosef("%v\n", err)
- }
- f.shutdownWaitgroup.Done()
- }()
- } else {
- f.verbosef("Skipping dumping unmodified db\n")
- }
- }
- // joinCleanPaths is like filepath.Join but is faster because
- // joinCleanPaths doesn't have to support paths ending in "/" or containing ".."
- func joinCleanPaths(base string, leaf string) string {
- if base == "" {
- return leaf
- }
- if base == "/" {
- return base + leaf
- }
- if leaf == "" {
- return base
- }
- return base + "/" + leaf
- }
- func (f *Finder) verbosef(format string, args ...interface{}) {
- f.logger.Output(2, fmt.Sprintf(format, args...))
- }
- // loadFromFilesystem populates the in-memory cache based on the contents of the filesystem
- func (f *Finder) loadFromFilesystem() {
- f.threadPool = newThreadPool(f.numDbLoadingThreads)
- err := f.startFromExternalCache()
- if err != nil {
- f.startWithoutExternalCache()
- }
- f.goDumpDb()
- f.threadPool = nil
- }
- func (f *Finder) startFind(path string) {
- if !filepath.IsAbs(path) {
- path = filepath.Join(f.cacheMetadata.Config.WorkingDirectory, path)
- }
- node := f.nodes.GetNode(path, true)
- f.statDirAsync(node)
- }
- func (f *Finder) lock() {
- f.mutex.Lock()
- }
- func (f *Finder) unlock() {
- f.mutex.Unlock()
- }
- // a statResponse is the relevant portion of the response from the filesystem to a Stat call
- type statResponse struct {
- ModTime int64
- Inode uint64
- Device uint64
- }
- // a pathAndStats stores a path and its stats
- type pathAndStats struct {
- statResponse
- Path string
- }
- // a dirFullInfo stores all of the relevant information we know about a directory
- type dirFullInfo struct {
- pathAndStats
- FileNames []string
- }
- // a PersistedDirInfo is the information about a dir that we save to our cache on disk
- type PersistedDirInfo struct {
- // These field names are short because they are repeated many times in the output json file
- P string // path
- T int64 // modification time
- I uint64 // inode number
- F []string // relevant filenames contained
- }
- // a PersistedDirs is the information that we persist for a group of dirs
- type PersistedDirs struct {
- // the device on which each directory is stored
- Device uint64
- // the common root path to which all contained dirs are relative
- Root string
- // the directories themselves
- Dirs []PersistedDirInfo
- }
- // a CacheEntry is the smallest unit that can be read and parsed from the cache (on disk) at a time
- type CacheEntry []PersistedDirs
- // a DirEntries lists the files and directories contained directly within a specific directory
- type DirEntries struct {
- Path string
- // elements of DirNames are just the dir names; they don't include any '/' character
- DirNames []string
- // elements of FileNames are just the file names; they don't include '/' character
- FileNames []string
- }
- // a WalkFunc is the type that is passed into various Find functions for determining which
- // directories the caller wishes be walked. The WalkFunc is expected to decide which
- // directories to walk and which files to consider as matches to the original query.
- type WalkFunc func(DirEntries) (dirs []string, files []string)
- // a mapNode stores the relevant stats about a directory to be stored in a pathMap
- type mapNode struct {
- statResponse
- FileNames []string
- }
- // a pathMap implements the directory tree structure of nodes
- type pathMap struct {
- mapNode
- path string
- children map[string]*pathMap
- // number of descendent nodes, including self
- approximateNumDescendents int
- }
- func newPathMap(path string) *pathMap {
- result := &pathMap{path: path, children: make(map[string]*pathMap, 4),
- approximateNumDescendents: 1}
- return result
- }
- // GetNode returns the node at <path>
- func (m *pathMap) GetNode(path string, createIfNotFound bool) *pathMap {
- if len(path) > 0 && path[0] == '/' {
- path = path[1:]
- }
- node := m
- for {
- if path == "" {
- return node
- }
- index := strings.Index(path, "/")
- var firstComponent string
- if index >= 0 {
- firstComponent = path[:index]
- path = path[index+1:]
- } else {
- firstComponent = path
- path = ""
- }
- child, found := node.children[firstComponent]
- if !found {
- if createIfNotFound {
- child = node.newChild(firstComponent)
- } else {
- return nil
- }
- }
- node = child
- }
- }
- func (m *pathMap) newChild(name string) (child *pathMap) {
- path := joinCleanPaths(m.path, name)
- newChild := newPathMap(path)
- m.children[name] = newChild
- return m.children[name]
- }
- func (m *pathMap) UpdateNumDescendents() int {
- count := 1
- for _, child := range m.children {
- count += child.approximateNumDescendents
- }
- m.approximateNumDescendents = count
- return count
- }
- func (m *pathMap) UpdateNumDescendentsRecursive() {
- for _, child := range m.children {
- child.UpdateNumDescendentsRecursive()
- }
- m.UpdateNumDescendents()
- }
- func (m *pathMap) MergeIn(other *pathMap) {
- for key, theirs := range other.children {
- ours, found := m.children[key]
- if found {
- ours.MergeIn(theirs)
- } else {
- m.children[key] = theirs
- }
- }
- if other.ModTime != 0 {
- m.mapNode = other.mapNode
- }
- m.UpdateNumDescendents()
- }
- func (m *pathMap) DumpAll() []dirFullInfo {
- results := []dirFullInfo{}
- m.dumpInto("", &results)
- return results
- }
- func (m *pathMap) dumpInto(path string, results *[]dirFullInfo) {
- *results = append(*results,
- dirFullInfo{
- pathAndStats{statResponse: m.statResponse, Path: path},
- m.FileNames},
- )
- for key, child := range m.children {
- childPath := joinCleanPaths(path, key)
- if len(childPath) == 0 || childPath[0] != '/' {
- childPath = "/" + childPath
- }
- child.dumpInto(childPath, results)
- }
- }
- // a semaphore can be locked by up to <capacity> callers at once
- type semaphore struct {
- pool chan bool
- }
- func newSemaphore(capacity int) *semaphore {
- return &semaphore{pool: make(chan bool, capacity)}
- }
- func (l *semaphore) Lock() {
- l.pool <- true
- }
- func (l *semaphore) Unlock() {
- <-l.pool
- }
- // A threadPool runs goroutines and supports throttling and waiting.
- // Without throttling, Go may exhaust the maximum number of various resources, such as
- // threads or file descriptors, and crash the program.
- type threadPool struct {
- receivedRequests sync.WaitGroup
- activeRequests semaphore
- }
- func newThreadPool(maxNumConcurrentThreads int) *threadPool {
- return &threadPool{
- receivedRequests: sync.WaitGroup{},
- activeRequests: *newSemaphore(maxNumConcurrentThreads),
- }
- }
- // Run requests to run the given function in its own goroutine
- func (p *threadPool) Run(function func()) {
- p.receivedRequests.Add(1)
- // If Run() was called from within a goroutine spawned by this threadPool,
- // then we may need to return from Run() before having capacity to actually
- // run <function>.
- //
- // It's possible that the body of <function> contains a statement (such as a syscall)
- // that will cause Go to pin it to a thread, or will contain a statement that uses
- // another resource that is in short supply (such as a file descriptor), so we can't
- // actually run <function> until we have capacity.
- //
- // However, the semaphore used for synchronization is implemented via a channel and
- // shouldn't require a new thread for each access.
- go func() {
- p.activeRequests.Lock()
- function()
- p.activeRequests.Unlock()
- p.receivedRequests.Done()
- }()
- }
- // Wait waits until all goroutines are done, just like sync.WaitGroup's Wait
- func (p *threadPool) Wait() {
- p.receivedRequests.Wait()
- }
- type fsErr struct {
- path string
- err error
- }
- func (e fsErr) String() string {
- return e.path + ": " + e.err.Error()
- }
- func (f *Finder) serializeCacheEntry(dirInfos []dirFullInfo) ([]byte, error) {
- // group each dirFullInfo by its Device, to avoid having to repeat it in the output
- dirsByDevice := map[uint64][]PersistedDirInfo{}
- for _, entry := range dirInfos {
- _, found := dirsByDevice[entry.Device]
- if !found {
- dirsByDevice[entry.Device] = []PersistedDirInfo{}
- }
- dirsByDevice[entry.Device] = append(dirsByDevice[entry.Device],
- PersistedDirInfo{P: entry.Path, T: entry.ModTime, I: entry.Inode, F: entry.FileNames})
- }
- cacheEntry := CacheEntry{}
- for device, infos := range dirsByDevice {
- // find common prefix
- prefix := ""
- if len(infos) > 0 {
- prefix = infos[0].P
- }
- for _, info := range infos {
- for !strings.HasPrefix(info.P+"/", prefix+"/") {
- prefix = filepath.Dir(prefix)
- if prefix == "/" {
- break
- }
- }
- }
- // remove common prefix
- for i := range infos {
- suffix := strings.Replace(infos[i].P, prefix, "", 1)
- if len(suffix) > 0 && suffix[0] == '/' {
- suffix = suffix[1:]
- }
- infos[i].P = suffix
- }
- // turn the map (keyed by device) into a list of structs with labeled fields
- // this is to improve readability of the output
- cacheEntry = append(cacheEntry, PersistedDirs{Device: device, Root: prefix, Dirs: infos})
- }
- // convert to json.
- // it would save some space to use a different format than json for the db file,
- // but the space and time savings are small, and json is easy for humans to read
- bytes, err := json.Marshal(cacheEntry)
- return bytes, err
- }
- func (f *Finder) parseCacheEntry(bytes []byte) ([]dirFullInfo, error) {
- var cacheEntry CacheEntry
- err := json.Unmarshal(bytes, &cacheEntry)
- if err != nil {
- return nil, err
- }
- // convert from a CacheEntry to a []dirFullInfo (by copying a few fields)
- capacity := 0
- for _, element := range cacheEntry {
- capacity += len(element.Dirs)
- }
- nodes := make([]dirFullInfo, capacity)
- count := 0
- for _, element := range cacheEntry {
- for _, dir := range element.Dirs {
- path := joinCleanPaths(element.Root, dir.P)
- nodes[count] = dirFullInfo{
- pathAndStats: pathAndStats{
- statResponse: statResponse{
- ModTime: dir.T, Inode: dir.I, Device: element.Device,
- },
- Path: path},
- FileNames: dir.F}
- count++
- }
- }
- return nodes, nil
- }
- // We use the following separator byte to distinguish individually parseable blocks of json
- // because we know this separator won't appear in the json that we're parsing.
- //
- // The newline byte can only appear in a UTF-8 stream if the newline character appears, because:
- // - The newline character is encoded as "0000 1010" in binary ("0a" in hex)
- // - UTF-8 dictates that bytes beginning with a "0" bit are never emitted as part of a multibyte
- // character.
- //
- // We know that the newline character will never appear in our json string, because:
- // - If a newline character appears as part of a data string, then json encoding will
- // emit two characters instead: '\' and 'n'.
- // - The json encoder that we use doesn't emit the optional newlines between any of its
- // other outputs.
- const lineSeparator = byte('\n')
- func (f *Finder) readLine(reader *bufio.Reader) ([]byte, error) {
- return reader.ReadBytes(lineSeparator)
- }
- // validateCacheHeader reads the cache header from cacheReader and tells whether the cache is compatible with this Finder
- func (f *Finder) validateCacheHeader(cacheReader *bufio.Reader) bool {
- cacheVersionBytes, err := f.readLine(cacheReader)
- if err != nil {
- f.verbosef("Failed to read database header; database is invalid\n")
- return false
- }
- if len(cacheVersionBytes) > 0 && cacheVersionBytes[len(cacheVersionBytes)-1] == lineSeparator {
- cacheVersionBytes = cacheVersionBytes[:len(cacheVersionBytes)-1]
- }
- cacheVersionString := string(cacheVersionBytes)
- currentVersion := f.cacheMetadata.Version
- if cacheVersionString != currentVersion {
- f.verbosef("Version changed from %q to %q, database is not applicable\n", cacheVersionString, currentVersion)
- return false
- }
- cacheParamBytes, err := f.readLine(cacheReader)
- if err != nil {
- f.verbosef("Failed to read database search params; database is invalid\n")
- return false
- }
- if len(cacheParamBytes) > 0 && cacheParamBytes[len(cacheParamBytes)-1] == lineSeparator {
- cacheParamBytes = cacheParamBytes[:len(cacheParamBytes)-1]
- }
- currentParamBytes, err := f.cacheMetadata.Config.Dump()
- if err != nil {
- panic("Finder failed to serialize its parameters")
- }
- cacheParamString := string(cacheParamBytes)
- currentParamString := string(currentParamBytes)
- if cacheParamString != currentParamString {
- f.verbosef("Params changed from %q to %q, database is not applicable\n", cacheParamString, currentParamString)
- return false
- }
- return true
- }
- // loadBytes compares the cache info in <data> to the state of the filesystem
- // loadBytes returns a map representing <data> and also a slice of dirs that need to be re-walked
- func (f *Finder) loadBytes(id int, data []byte) (m *pathMap, dirsToWalk []string, err error) {
- helperStartTime := time.Now()
- cachedNodes, err := f.parseCacheEntry(data)
- if err != nil {
- return nil, nil, fmt.Errorf("Failed to parse block %v: %v\n", id, err.Error())
- }
- unmarshalDate := time.Now()
- f.verbosef("Unmarshaled %v objects for %v in %v\n",
- len(cachedNodes), id, unmarshalDate.Sub(helperStartTime))
- tempMap := newPathMap("/")
- stats := make([]statResponse, len(cachedNodes))
- for i, node := range cachedNodes {
- // check the file system for an updated timestamp
- stats[i] = f.statDirSync(node.Path)
- }
- dirsToWalk = []string{}
- for i, cachedNode := range cachedNodes {
- updated := stats[i]
- // save the cached value
- container := tempMap.GetNode(cachedNode.Path, true)
- container.mapNode = mapNode{statResponse: updated}
- // if the metadata changed and the directory still exists, then
- // make a note to walk it later
- if !f.isInfoUpToDate(cachedNode.statResponse, updated) && updated.ModTime != 0 {
- f.setModified()
- // make a note that the directory needs to be walked
- dirsToWalk = append(dirsToWalk, cachedNode.Path)
- } else {
- container.mapNode.FileNames = cachedNode.FileNames
- }
- }
- // count the number of nodes to improve our understanding of the shape of the tree,
- // thereby improving parallelism of subsequent searches
- tempMap.UpdateNumDescendentsRecursive()
- f.verbosef("Statted inodes of block %v in %v\n", id, time.Now().Sub(unmarshalDate))
- return tempMap, dirsToWalk, nil
- }
- // startFromExternalCache loads the cache database from disk
- // startFromExternalCache waits to return until the load of the cache db is complete, but
- // startFromExternalCache does not wait for all every listDir() or statDir() request to complete
- func (f *Finder) startFromExternalCache() (err error) {
- startTime := time.Now()
- dbPath := f.DbPath
- // open cache file and validate its header
- reader, err := f.filesystem.Open(dbPath)
- if err != nil {
- return errors.New("No data to load from database\n")
- }
- defer reader.Close()
- bufferedReader := bufio.NewReader(reader)
- if !f.validateCacheHeader(bufferedReader) {
- return errors.New("Cache header does not match")
- }
- f.verbosef("Database header matches, will attempt to use database %v\n", f.DbPath)
- // read the file and spawn threads to process it
- nodesToWalk := [][]*pathMap{}
- mainTree := newPathMap("/")
- // read the blocks and stream them into <blockChannel>
- type dataBlock struct {
- id int
- err error
- data []byte
- }
- blockChannel := make(chan dataBlock, f.numDbLoadingThreads)
- readBlocks := func() {
- index := 0
- for {
- // It takes some time to unmarshal the input from json, so we want
- // to unmarshal it in parallel. In order to find valid places to
- // break the input, we scan for the line separators that we inserted
- // (for this purpose) when we dumped the database.
- data, err := f.readLine(bufferedReader)
- var response dataBlock
- done := false
- if err != nil && err != io.EOF {
- response = dataBlock{id: index, err: err, data: nil}
- done = true
- } else {
- done = (err == io.EOF)
- response = dataBlock{id: index, err: nil, data: data}
- }
- blockChannel <- response
- index++
- duration := time.Since(startTime)
- f.verbosef("Read block %v after %v\n", index, duration)
- if done {
- f.verbosef("Read %v blocks in %v\n", index, duration)
- close(blockChannel)
- return
- }
- }
- }
- go readBlocks()
- // Read from <blockChannel> and stream the responses into <resultChannel>.
- type workResponse struct {
- id int
- err error
- tree *pathMap
- updatedDirs []string
- }
- resultChannel := make(chan workResponse)
- processBlocks := func() {
- numProcessed := 0
- threadPool := newThreadPool(f.numDbLoadingThreads)
- for {
- // get a block to process
- block, received := <-blockChannel
- if !received {
- break
- }
- if block.err != nil {
- resultChannel <- workResponse{err: block.err}
- break
- }
- numProcessed++
- // wait until there is CPU available to process it
- threadPool.Run(
- func() {
- processStartTime := time.Now()
- f.verbosef("Starting to process block %v after %v\n",
- block.id, processStartTime.Sub(startTime))
- tempMap, updatedDirs, err := f.loadBytes(block.id, block.data)
- var response workResponse
- if err != nil {
- f.verbosef(
- "Block %v failed to parse with error %v\n",
- block.id, err)
- response = workResponse{err: err}
- } else {
- response = workResponse{
- id: block.id,
- err: nil,
- tree: tempMap,
- updatedDirs: updatedDirs,
- }
- }
- f.verbosef("Processed block %v in %v\n",
- block.id, time.Since(processStartTime),
- )
- resultChannel <- response
- },
- )
- }
- threadPool.Wait()
- f.verbosef("Finished processing %v blocks in %v\n",
- numProcessed, time.Since(startTime))
- close(resultChannel)
- }
- go processBlocks()
- // Read from <resultChannel> and use the results
- combineResults := func() (err error) {
- for {
- result, received := <-resultChannel
- if !received {
- break
- }
- if err != nil {
- // In case of an error, wait for work to complete before
- // returning the error. This ensures that any subsequent
- // work doesn't need to compete for resources (and possibly
- // fail due to, for example, a filesystem limit on the number of
- // concurrently open files) with past work.
- continue
- }
- if result.err != nil {
- err = result.err
- continue
- }
- // update main tree
- mainTree.MergeIn(result.tree)
- // record any new directories that we will need to Stat()
- updatedNodes := make([]*pathMap, len(result.updatedDirs))
- for j, dir := range result.updatedDirs {
- node := mainTree.GetNode(dir, false)
- updatedNodes[j] = node
- }
- nodesToWalk = append(nodesToWalk, updatedNodes)
- }
- return err
- }
- err = combineResults()
- if err != nil {
- return err
- }
- f.nodes = *mainTree
- // after having loaded the entire db and therefore created entries for
- // the directories we know of, now it's safe to start calling ReadDir on
- // any updated directories
- for i := range nodesToWalk {
- f.listDirsAsync(nodesToWalk[i])
- }
- f.verbosef("Loaded db and statted known dirs in %v\n", time.Since(startTime))
- f.threadPool.Wait()
- f.verbosef("Loaded db and statted all dirs in %v\n", time.Now().Sub(startTime))
- return err
- }
- // startWithoutExternalCache starts scanning the filesystem according to the cache config
- // startWithoutExternalCache should be called if startFromExternalCache is not applicable
- func (f *Finder) startWithoutExternalCache() {
- startTime := time.Now()
- configDirs := f.cacheMetadata.Config.RootDirs
- // clean paths
- candidates := make([]string, len(configDirs))
- for i, dir := range configDirs {
- candidates[i] = filepath.Clean(dir)
- }
- // remove duplicates
- dirsToScan := make([]string, 0, len(configDirs))
- for _, candidate := range candidates {
- include := true
- for _, included := range dirsToScan {
- if included == "/" || strings.HasPrefix(candidate+"/", included+"/") {
- include = false
- break
- }
- }
- if include {
- dirsToScan = append(dirsToScan, candidate)
- }
- }
- // start searching finally
- for _, path := range dirsToScan {
- f.verbosef("Starting find of %v\n", path)
- f.startFind(path)
- }
- f.threadPool.Wait()
- f.verbosef("Scanned filesystem (not using cache) in %v\n", time.Now().Sub(startTime))
- }
- // isInfoUpToDate tells whether <new> can confirm that results computed at <old> are still valid
- func (f *Finder) isInfoUpToDate(old statResponse, new statResponse) (equal bool) {
- if old.Inode != new.Inode {
- return false
- }
- if old.ModTime != new.ModTime {
- return false
- }
- if old.Device != new.Device {
- return false
- }
- return true
- }
- func (f *Finder) wasModified() bool {
- return atomic.LoadInt32(&f.modifiedFlag) > 0
- }
- func (f *Finder) setModified() {
- var newVal int32
- newVal = 1
- atomic.StoreInt32(&f.modifiedFlag, newVal)
- }
- // sortedDirEntries exports directory entries to facilitate dumping them to the external cache
- func (f *Finder) sortedDirEntries() []dirFullInfo {
- startTime := time.Now()
- nodes := make([]dirFullInfo, 0)
- for _, node := range f.nodes.DumpAll() {
- if node.ModTime != 0 {
- nodes = append(nodes, node)
- }
- }
- discoveryDate := time.Now()
- f.verbosef("Generated %v cache entries in %v\n", len(nodes), discoveryDate.Sub(startTime))
- less := func(i int, j int) bool {
- return nodes[i].Path < nodes[j].Path
- }
- sort.Slice(nodes, less)
- sortDate := time.Now()
- f.verbosef("Sorted %v cache entries in %v\n", len(nodes), sortDate.Sub(discoveryDate))
- return nodes
- }
- // serializeDb converts the cache database into a form to save to disk
- func (f *Finder) serializeDb() ([]byte, error) {
- // sort dir entries
- var entryList = f.sortedDirEntries()
- // Generate an output file that can be conveniently loaded using the same number of threads
- // as were used in this execution (because presumably that will be the number of threads
- // used in the next execution too)
- // generate header
- header := []byte{}
- header = append(header, []byte(f.cacheMetadata.Version)...)
- header = append(header, lineSeparator)
- configDump, err := f.cacheMetadata.Config.Dump()
- if err != nil {
- return nil, err
- }
- header = append(header, configDump...)
- // serialize individual blocks in parallel
- numBlocks := f.numDbLoadingThreads
- if numBlocks > len(entryList) {
- numBlocks = len(entryList)
- }
- blocks := make([][]byte, 1+numBlocks)
- blocks[0] = header
- blockMin := 0
- wg := sync.WaitGroup{}
- var errLock sync.Mutex
- for i := 1; i <= numBlocks; i++ {
- // identify next block
- blockMax := len(entryList) * i / numBlocks
- block := entryList[blockMin:blockMax]
- // process block
- wg.Add(1)
- go func(index int, block []dirFullInfo) {
- byteBlock, subErr := f.serializeCacheEntry(block)
- f.verbosef("Serialized block %v into %v bytes\n", index, len(byteBlock))
- if subErr != nil {
- f.verbosef("%v\n", subErr.Error())
- errLock.Lock()
- err = subErr
- errLock.Unlock()
- } else {
- blocks[index] = byteBlock
- }
- wg.Done()
- }(i, block)
- blockMin = blockMax
- }
- wg.Wait()
- if err != nil {
- return nil, err
- }
- content := bytes.Join(blocks, []byte{lineSeparator})
- return content, nil
- }
- // dumpDb saves the cache database to disk
- func (f *Finder) dumpDb() error {
- startTime := time.Now()
- f.verbosef("Dumping db\n")
- tempPath := f.DbPath + ".tmp"
- bytes, err := f.serializeDb()
- if err != nil {
- return err
- }
- serializeDate := time.Now()
- f.verbosef("Serialized db in %v\n", serializeDate.Sub(startTime))
- // dump file and atomically move
- err = f.filesystem.WriteFile(tempPath, bytes, 0777)
- if err != nil {
- return err
- }
- err = f.filesystem.Rename(tempPath, f.DbPath)
- if err != nil {
- return err
- }
- f.verbosef("Wrote db in %v\n", time.Now().Sub(serializeDate))
- return nil
- }
- // canIgnoreFsErr checks for certain classes of filesystem errors that are safe to ignore
- func (f *Finder) canIgnoreFsErr(err error) bool {
- pathErr, isPathErr := err.(*os.PathError)
- if !isPathErr {
- // Don't recognize this error
- return false
- }
- if os.IsPermission(pathErr) {
- // Permission errors are ignored:
- // https://issuetracker.google.com/37553659
- // https://github.com/google/kati/pull/116
- return true
- }
- if pathErr.Err == os.ErrNotExist {
- // If a directory doesn't exist, that generally means the cache is out-of-date
- return true
- }
- // Don't recognize this error
- return false
- }
- // onFsError should be called whenever a potentially fatal error is returned from a filesystem call
- func (f *Finder) onFsError(path string, err error) {
- if !f.canIgnoreFsErr(err) {
- // We could send the errors through a channel instead, although that would cause this call
- // to block unless we preallocated a sufficient buffer or spawned a reader thread.
- // Although it wouldn't be too complicated to spawn a reader thread, it's still slightly
- // more convenient to use a lock. Only in an unusual situation should this code be
- // invoked anyway.
- f.errlock.Lock()
- f.fsErrs = append(f.fsErrs, fsErr{path: path, err: err})
- f.errlock.Unlock()
- }
- }
- // discardErrsForPrunedPaths removes any errors for paths that are no longer included in the cache
- func (f *Finder) discardErrsForPrunedPaths() {
- // This function could be somewhat inefficient due to being single-threaded,
- // but the length of f.fsErrs should be approximately 0, so it shouldn't take long anyway.
- relevantErrs := make([]fsErr, 0, len(f.fsErrs))
- for _, fsErr := range f.fsErrs {
- path := fsErr.path
- node := f.nodes.GetNode(path, false)
- if node != nil {
- // The path in question wasn't pruned due to a failure to process a parent directory.
- // So, the failure to process this path is important
- relevantErrs = append(relevantErrs, fsErr)
- }
- }
- f.fsErrs = relevantErrs
- }
- // getErr returns an error based on previous calls to onFsErr, if any
- func (f *Finder) getErr() error {
- f.discardErrsForPrunedPaths()
- numErrs := len(f.fsErrs)
- if numErrs < 1 {
- return nil
- }
- maxNumErrsToInclude := 10
- message := ""
- if numErrs > maxNumErrsToInclude {
- message = fmt.Sprintf("finder encountered %v errors: %v...", numErrs, f.fsErrs[:maxNumErrsToInclude])
- } else {
- message = fmt.Sprintf("finder encountered %v errors: %v", numErrs, f.fsErrs)
- }
- return errors.New(message)
- }
- func (f *Finder) statDirAsync(dir *pathMap) {
- node := dir
- path := dir.path
- f.threadPool.Run(
- func() {
- updatedStats := f.statDirSync(path)
- if !f.isInfoUpToDate(node.statResponse, updatedStats) {
- node.mapNode = mapNode{
- statResponse: updatedStats,
- FileNames: []string{},
- }
- f.setModified()
- if node.statResponse.ModTime != 0 {
- // modification time was updated, so re-scan for
- // child directories
- f.listDirAsync(dir)
- }
- }
- },
- )
- }
- func (f *Finder) statDirSync(path string) statResponse {
- fileInfo, err := f.filesystem.Lstat(path)
- var stats statResponse
- if err != nil {
- // possibly record this error
- f.onFsError(path, err)
- // in case of a failure to stat the directory, treat the directory as missing (modTime = 0)
- return stats
- }
- modTime := fileInfo.ModTime()
- stats = statResponse{}
- inode, err := f.filesystem.InodeNumber(fileInfo)
- if err != nil {
- panic(fmt.Sprintf("Could not get inode number of %v: %v\n", path, err.Error()))
- }
- stats.Inode = inode
- device, err := f.filesystem.DeviceNumber(fileInfo)
- if err != nil {
- panic(fmt.Sprintf("Could not get device number of %v: %v\n", path, err.Error()))
- }
- stats.Device = device
- permissionsChangeTime, err := f.filesystem.PermTime(fileInfo)
- if err != nil {
- panic(fmt.Sprintf("Could not get permissions modification time (CTime) of %v: %v\n", path, err.Error()))
- }
- // We're only interested in knowing whether anything about the directory
- // has changed since last check, so we use the latest of the two
- // modification times (content modification (mtime) and
- // permission modification (ctime))
- if permissionsChangeTime.After(modTime) {
- modTime = permissionsChangeTime
- }
- stats.ModTime = modTime.UnixNano()
- return stats
- }
- func (f *Finder) shouldIncludeFile(fileName string) bool {
- for _, includedName := range f.cacheMetadata.Config.IncludeFiles {
- if fileName == includedName {
- return true
- }
- }
- for _, includeSuffix := range f.cacheMetadata.Config.IncludeSuffixes {
- if strings.HasSuffix(fileName, includeSuffix) {
- return true
- }
- }
- return false
- }
- // pruneCacheCandidates removes the items that we don't want to include in our persistent cache
- func (f *Finder) pruneCacheCandidates(items *DirEntries) {
- for _, fileName := range items.FileNames {
- for _, abortedName := range f.cacheMetadata.Config.PruneFiles {
- if fileName == abortedName {
- items.FileNames = []string{}
- items.DirNames = []string{}
- return
- }
- }
- }
- // remove any files that aren't the ones we want to include
- writeIndex := 0
- for _, fileName := range items.FileNames {
- if f.shouldIncludeFile(fileName) {
- items.FileNames[writeIndex] = fileName
- writeIndex++
- }
- }
- // resize
- items.FileNames = items.FileNames[:writeIndex]
- writeIndex = 0
- for _, dirName := range items.DirNames {
- items.DirNames[writeIndex] = dirName
- // ignore other dirs that are known to not be inputs to the build process
- include := true
- for _, excludedName := range f.cacheMetadata.Config.ExcludeDirs {
- if dirName == excludedName {
- // don't include
- include = false
- break
- }
- }
- if include {
- writeIndex++
- }
- }
- // resize
- items.DirNames = items.DirNames[:writeIndex]
- }
- func (f *Finder) listDirsAsync(nodes []*pathMap) {
- f.threadPool.Run(
- func() {
- for i := range nodes {
- f.listDirSync(nodes[i])
- }
- },
- )
- }
- func (f *Finder) listDirAsync(node *pathMap) {
- f.threadPool.Run(
- func() {
- f.listDirSync(node)
- },
- )
- }
- func (f *Finder) listDirSync(dir *pathMap) {
- path := dir.path
- children, err := f.filesystem.ReadDir(path)
- if err != nil {
- // possibly record this error
- f.onFsError(path, err)
- // if listing the contents of the directory fails (presumably due to
- // permission denied), then treat the directory as empty
- children = nil
- }
- var subdirs []string
- var subfiles []string
- for _, child := range children {
- linkBits := child.Mode() & os.ModeSymlink
- isLink := linkBits != 0
- if isLink {
- childPath := filepath.Join(path, child.Name())
- childStat, err := f.filesystem.Stat(childPath)
- if err != nil {
- // If stat fails this is probably a broken or dangling symlink, treat it as a file.
- subfiles = append(subfiles, child.Name())
- } else if childStat.IsDir() {
- // Skip symlink dirs if not requested otherwise. Android has a number
- // of symlinks creating infinite source trees which would otherwise get
- // us in an infinite loop.
- // TODO(b/197349722): Revisit this once symlink loops are banned in the
- // source tree.
- if f.cacheMetadata.Config.FollowSymlinks {
- subdirs = append(subdirs, child.Name())
- }
- } else {
- // We do have to support symlink files because the link name might be
- // different than the target name
- // (for example, Android.bp -> build/soong/root.bp)
- subfiles = append(subfiles, child.Name())
- }
- } else if child.IsDir() {
- subdirs = append(subdirs, child.Name())
- } else {
- subfiles = append(subfiles, child.Name())
- }
- }
- parentNode := dir
- entry := &DirEntries{Path: path, DirNames: subdirs, FileNames: subfiles}
- f.pruneCacheCandidates(entry)
- // create a pathMap node for each relevant subdirectory
- relevantChildren := map[string]*pathMap{}
- for _, subdirName := range entry.DirNames {
- childNode, found := parentNode.children[subdirName]
- // if we already knew of this directory, then we already have a request pending to Stat it
- // if we didn't already know of this directory, then we must Stat it now
- if !found {
- childNode = parentNode.newChild(subdirName)
- f.statDirAsync(childNode)
- }
- relevantChildren[subdirName] = childNode
- }
- // Note that in rare cases, it's possible that we're reducing the set of
- // children via this statement, if these are all true:
- // 1. we previously had a cache that knew about subdirectories of parentNode
- // 2. the user created a prune-file (described in pruneCacheCandidates)
- // inside <parentNode>, which specifies that the contents of parentNode
- // are to be ignored.
- // The fact that it's possible to remove children here means that *pathMap structs
- // must not be looked up from f.nodes by filepath (and instead must be accessed by
- // direct pointer) until after every listDirSync completes
- parentNode.FileNames = entry.FileNames
- parentNode.children = relevantChildren
- }
- // listMatches takes a node and a function that specifies which subdirectories and
- // files to include, and listMatches returns the matches
- func (f *Finder) listMatches(node *pathMap,
- filter WalkFunc) (subDirs []*pathMap, filePaths []string) {
- entries := DirEntries{
- FileNames: node.FileNames,
- }
- entries.DirNames = make([]string, 0, len(node.children))
- for childName := range node.children {
- entries.DirNames = append(entries.DirNames, childName)
- }
- dirNames, fileNames := filter(entries)
- subDirs = []*pathMap{}
- filePaths = make([]string, 0, len(fileNames))
- for _, fileName := range fileNames {
- filePaths = append(filePaths, joinCleanPaths(node.path, fileName))
- }
- subDirs = make([]*pathMap, 0, len(dirNames))
- for _, childName := range dirNames {
- child, ok := node.children[childName]
- if ok {
- subDirs = append(subDirs, child)
- }
- }
- return subDirs, filePaths
- }
- // findInCacheMultithreaded spawns potentially multiple goroutines with which to search the cache.
- func (f *Finder) findInCacheMultithreaded(node *pathMap, filter WalkFunc,
- approxNumThreads int) []string {
- if approxNumThreads < 2 {
- // Done spawning threads; process remaining directories
- return f.findInCacheSinglethreaded(node, filter)
- }
- totalWork := 0
- for _, child := range node.children {
- totalWork += child.approximateNumDescendents
- }
- childrenResults := make(chan []string, len(node.children))
- subDirs, filePaths := f.listMatches(node, filter)
- // process child directories
- for _, child := range subDirs {
- numChildThreads := approxNumThreads * child.approximateNumDescendents / totalWork
- childProcessor := func(child *pathMap) {
- childResults := f.findInCacheMultithreaded(child, filter, numChildThreads)
- childrenResults <- childResults
- }
- // If we're allowed to use more than 1 thread to process this directory,
- // then instead we use 1 thread for each subdirectory.
- // It would be strange to spawn threads for only some subdirectories.
- go childProcessor(child)
- }
- // collect results
- for i := 0; i < len(subDirs); i++ {
- childResults := <-childrenResults
- filePaths = append(filePaths, childResults...)
- }
- close(childrenResults)
- return filePaths
- }
- // findInCacheSinglethreaded synchronously searches the cache for all matching file paths
- // note findInCacheSinglethreaded runs 2X to 4X as fast by being iterative rather than recursive
- func (f *Finder) findInCacheSinglethreaded(node *pathMap, filter WalkFunc) []string {
- if node == nil {
- return []string{}
- }
- nodes := []*pathMap{node}
- matches := []string{}
- for len(nodes) > 0 {
- currentNode := nodes[0]
- nodes = nodes[1:]
- subDirs, filePaths := f.listMatches(currentNode, filter)
- nodes = append(nodes, subDirs...)
- matches = append(matches, filePaths...)
- }
- return matches
- }
|