finder.go 46 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556
  1. // Copyright 2017 Google Inc. All rights reserved.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of the License at
  6. //
  7. // http://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS IS" BASIS,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. package finder
  15. import (
  16. "bufio"
  17. "bytes"
  18. "encoding/json"
  19. "errors"
  20. "fmt"
  21. "io"
  22. "os"
  23. "path/filepath"
  24. "runtime"
  25. "sort"
  26. "strings"
  27. "sync"
  28. "sync/atomic"
  29. "time"
  30. "android/soong/finder/fs"
  31. )
  32. // This file provides a Finder struct that can quickly search for files satisfying
  33. // certain criteria.
  34. // This Finder gets its speed partially from parallelism and partially from caching.
  35. // If a Stat call returns the same result as last time, then it means Finder
  36. // can skip the ReadDir call for that dir.
  37. // The primary data structure used by the finder is the field Finder.nodes ,
  38. // which is a tree of nodes of type *pathMap .
  39. // Each node represents a directory on disk, along with its stats, subdirectories,
  40. // and contained files.
  41. // The common use case for the Finder is that the caller creates a Finder and gives
  42. // it the same query that was given to it in the previous execution.
  43. // In this situation, the major events that take place are:
  44. // 1. The Finder begins to load its db
  45. // 2. The Finder begins to stat the directories mentioned in its db (using multiple threads)
  46. // Calling Stat on each of these directories is generally a large fraction of the total time
  47. // 3. The Finder begins to construct a separate tree of nodes in each of its threads
  48. // 4. The Finder merges the individual node trees into the main node tree
  49. // 5. The Finder may call ReadDir a few times if there are a few directories that are out-of-date
  50. // These ReadDir calls might prompt additional Stat calls, etc
  51. // 6. The Finder waits for all loading to complete
  52. // 7. The Finder searches the cache for files matching the user's query (using multiple threads)
  53. // These are the invariants regarding concurrency:
  54. // 1. The public methods of Finder are threadsafe.
  55. // The public methods are only performance-optimized for one caller at a time, however.
  56. // For the moment, multiple concurrent callers shouldn't expect any better performance than
  57. // multiple serial callers.
  58. // 2. While building the node tree, only one thread may ever access the <children> collection of a
  59. // *pathMap at once.
  60. // a) The thread that accesses the <children> collection is the thread that discovers the
  61. // children (by reading them from the cache or by having received a response to ReadDir).
  62. // 1) Consequently, the thread that discovers the children also spawns requests to stat
  63. // subdirs.
  64. // b) Consequently, while building the node tree, no thread may do a lookup of its
  65. // *pathMap via filepath because another thread may be adding children to the
  66. // <children> collection of an ancestor node. Additionally, in rare cases, another thread
  67. // may be removing children from an ancestor node if the children were only discovered to
  68. // be irrelevant after calling ReadDir (which happens if a prune-file was just added).
  69. // 3. No query will begin to be serviced until all loading (both reading the db
  70. // and scanning the filesystem) is complete.
  71. // Tests indicate that it only takes about 10% as long to search the in-memory cache as to
  72. // generate it, making this not a huge loss in performance.
  73. // 4. The parsing of the db and the initial setup of the pathMap tree must complete before
  74. // beginning to call listDirSync (because listDirSync can create new entries in the pathMap)
  75. // see cmd/finder.go or finder_test.go for usage examples
  76. // Update versionString whenever making a backwards-incompatible change to the cache file format
  77. const versionString = "Android finder version 1"
  78. // a CacheParams specifies which files and directories the user wishes be scanned and
  79. // potentially added to the cache
  80. type CacheParams struct {
  81. // WorkingDirectory is used as a base for any relative file paths given to the Finder
  82. WorkingDirectory string
  83. // RootDirs are the root directories used to initiate the search
  84. RootDirs []string
  85. // ExcludeDirs are directory names that if encountered are removed from the search
  86. ExcludeDirs []string
  87. // PruneFiles are file names that if encountered prune their entire directory
  88. // (including siblings)
  89. PruneFiles []string
  90. // IncludeFiles are file names to include as matches
  91. IncludeFiles []string
  92. // IncludeSuffixes are filename suffixes to include as matches.
  93. IncludeSuffixes []string
  94. }
  95. // a cacheConfig stores the inputs that determine what should be included in the cache
  96. type cacheConfig struct {
  97. CacheParams
  98. // FilesystemView is a unique identifier telling which parts of which file systems
  99. // are readable by the Finder. In practice its value is essentially username@hostname.
  100. // FilesystemView is set to ensure that a cache file copied to another host or
  101. // found by another user doesn't inadvertently get reused.
  102. FilesystemView string
  103. }
  104. func (p *cacheConfig) Dump() ([]byte, error) {
  105. bytes, err := json.Marshal(p)
  106. return bytes, err
  107. }
  108. // a cacheMetadata stores version information about the cache
  109. type cacheMetadata struct {
  110. // The Version enables the Finder to determine whether it can even parse the file
  111. // If the version changes, the entire cache file must be regenerated
  112. Version string
  113. // The CacheParams enables the Finder to determine whether the parameters match
  114. // If the CacheParams change, the Finder can choose how much of the cache file to reuse
  115. // (although in practice, the Finder will probably choose to ignore the entire file anyway)
  116. Config cacheConfig
  117. }
  118. type Logger interface {
  119. Output(calldepth int, s string) error
  120. }
  121. // the Finder is the main struct that callers will want to use
  122. type Finder struct {
  123. // configuration
  124. DbPath string
  125. numDbLoadingThreads int
  126. numSearchingThreads int
  127. cacheMetadata cacheMetadata
  128. logger Logger
  129. filesystem fs.FileSystem
  130. // temporary state
  131. threadPool *threadPool
  132. mutex sync.Mutex
  133. fsErrs []fsErr
  134. errlock sync.Mutex
  135. shutdownWaitgroup sync.WaitGroup
  136. // non-temporary state
  137. modifiedFlag int32
  138. nodes pathMap
  139. }
  140. var defaultNumThreads = runtime.NumCPU() * 2
  141. // New creates a new Finder for use
  142. func New(cacheParams CacheParams, filesystem fs.FileSystem,
  143. logger Logger, dbPath string) (f *Finder, err error) {
  144. return newImpl(cacheParams, filesystem, logger, dbPath, defaultNumThreads)
  145. }
  146. // newImpl is like New but accepts more params
  147. func newImpl(cacheParams CacheParams, filesystem fs.FileSystem,
  148. logger Logger, dbPath string, numThreads int) (f *Finder, err error) {
  149. numDbLoadingThreads := numThreads
  150. numSearchingThreads := numThreads
  151. metadata := cacheMetadata{
  152. Version: versionString,
  153. Config: cacheConfig{
  154. CacheParams: cacheParams,
  155. FilesystemView: filesystem.ViewId(),
  156. },
  157. }
  158. f = &Finder{
  159. numDbLoadingThreads: numDbLoadingThreads,
  160. numSearchingThreads: numSearchingThreads,
  161. cacheMetadata: metadata,
  162. logger: logger,
  163. filesystem: filesystem,
  164. nodes: *newPathMap("/"),
  165. DbPath: dbPath,
  166. shutdownWaitgroup: sync.WaitGroup{},
  167. }
  168. f.loadFromFilesystem()
  169. // check for any filesystem errors
  170. err = f.getErr()
  171. if err != nil {
  172. return nil, err
  173. }
  174. // confirm that every path mentioned in the CacheConfig exists
  175. for _, path := range cacheParams.RootDirs {
  176. if !filepath.IsAbs(path) {
  177. path = filepath.Join(f.cacheMetadata.Config.WorkingDirectory, path)
  178. }
  179. node := f.nodes.GetNode(filepath.Clean(path), false)
  180. if node == nil || node.ModTime == 0 {
  181. return nil, fmt.Errorf("path %v was specified to be included in the cache but does not exist\n", path)
  182. }
  183. }
  184. return f, nil
  185. }
  186. // FindNamed searches for every cached file
  187. func (f *Finder) FindAll() []string {
  188. return f.FindAt("/")
  189. }
  190. // FindNamed searches for every cached file under <rootDir>
  191. func (f *Finder) FindAt(rootDir string) []string {
  192. filter := func(entries DirEntries) (dirNames []string, fileNames []string) {
  193. return entries.DirNames, entries.FileNames
  194. }
  195. return f.FindMatching(rootDir, filter)
  196. }
  197. // FindNamed searches for every cached file named <fileName>
  198. func (f *Finder) FindNamed(fileName string) []string {
  199. return f.FindNamedAt("/", fileName)
  200. }
  201. // FindNamedAt searches under <rootPath> for every file named <fileName>
  202. // The reason a caller might use FindNamedAt instead of FindNamed is if they want
  203. // to limit their search to a subset of the cache
  204. func (f *Finder) FindNamedAt(rootPath string, fileName string) []string {
  205. filter := func(entries DirEntries) (dirNames []string, fileNames []string) {
  206. matches := []string{}
  207. for _, foundName := range entries.FileNames {
  208. if foundName == fileName {
  209. matches = append(matches, foundName)
  210. }
  211. }
  212. return entries.DirNames, matches
  213. }
  214. return f.FindMatching(rootPath, filter)
  215. }
  216. // FindFirstNamed searches for every file named <fileName>
  217. // Whenever it finds a match, it stops search subdirectories
  218. func (f *Finder) FindFirstNamed(fileName string) []string {
  219. return f.FindFirstNamedAt("/", fileName)
  220. }
  221. // FindFirstNamedAt searches for every file named <fileName>
  222. // Whenever it finds a match, it stops search subdirectories
  223. func (f *Finder) FindFirstNamedAt(rootPath string, fileName string) []string {
  224. filter := func(entries DirEntries) (dirNames []string, fileNames []string) {
  225. matches := []string{}
  226. for _, foundName := range entries.FileNames {
  227. if foundName == fileName {
  228. matches = append(matches, foundName)
  229. }
  230. }
  231. if len(matches) > 0 {
  232. return []string{}, matches
  233. }
  234. return entries.DirNames, matches
  235. }
  236. return f.FindMatching(rootPath, filter)
  237. }
  238. // FindMatching is the most general exported function for searching for files in the cache
  239. // The WalkFunc will be invoked repeatedly and is expected to modify the provided DirEntries
  240. // in place, removing file paths and directories as desired.
  241. // WalkFunc will be invoked potentially many times in parallel, and must be threadsafe.
  242. func (f *Finder) FindMatching(rootPath string, filter WalkFunc) []string {
  243. // set up some parameters
  244. scanStart := time.Now()
  245. var isRel bool
  246. workingDir := f.cacheMetadata.Config.WorkingDirectory
  247. isRel = !filepath.IsAbs(rootPath)
  248. if isRel {
  249. rootPath = filepath.Join(workingDir, rootPath)
  250. }
  251. rootPath = filepath.Clean(rootPath)
  252. // ensure nothing else is using the Finder
  253. f.verbosef("FindMatching waiting for finder to be idle\n")
  254. f.lock()
  255. defer f.unlock()
  256. node := f.nodes.GetNode(rootPath, false)
  257. if node == nil {
  258. f.verbosef("No data for path %v ; apparently not included in cache params: %v\n",
  259. rootPath, f.cacheMetadata.Config.CacheParams)
  260. // path is not found; don't do a search
  261. return []string{}
  262. }
  263. // search for matching files
  264. f.verbosef("Finder finding %v using cache\n", rootPath)
  265. results := f.findInCacheMultithreaded(node, filter, f.numSearchingThreads)
  266. // format and return results
  267. if isRel {
  268. for i := 0; i < len(results); i++ {
  269. results[i] = strings.Replace(results[i], workingDir+"/", "", 1)
  270. }
  271. }
  272. sort.Strings(results)
  273. f.verbosef("Found %v files under %v in %v using cache\n",
  274. len(results), rootPath, time.Since(scanStart))
  275. return results
  276. }
  277. // Shutdown declares that the finder is no longer needed and waits for its cleanup to complete
  278. // Currently, that only entails waiting for the database dump to complete.
  279. func (f *Finder) Shutdown() {
  280. f.WaitForDbDump()
  281. }
  282. // WaitForDbDump returns once the database has been written to f.DbPath.
  283. func (f *Finder) WaitForDbDump() {
  284. f.shutdownWaitgroup.Wait()
  285. }
  286. // End of public api
  287. func (f *Finder) goDumpDb() {
  288. if f.wasModified() {
  289. f.shutdownWaitgroup.Add(1)
  290. go func() {
  291. err := f.dumpDb()
  292. if err != nil {
  293. f.verbosef("%v\n", err)
  294. }
  295. f.shutdownWaitgroup.Done()
  296. }()
  297. } else {
  298. f.verbosef("Skipping dumping unmodified db\n")
  299. }
  300. }
  301. // joinCleanPaths is like filepath.Join but is faster because
  302. // joinCleanPaths doesn't have to support paths ending in "/" or containing ".."
  303. func joinCleanPaths(base string, leaf string) string {
  304. if base == "" {
  305. return leaf
  306. }
  307. if base == "/" {
  308. return base + leaf
  309. }
  310. if leaf == "" {
  311. return base
  312. }
  313. return base + "/" + leaf
  314. }
  315. func (f *Finder) verbosef(format string, args ...interface{}) {
  316. f.logger.Output(2, fmt.Sprintf(format, args...))
  317. }
  318. // loadFromFilesystem populates the in-memory cache based on the contents of the filesystem
  319. func (f *Finder) loadFromFilesystem() {
  320. f.threadPool = newThreadPool(f.numDbLoadingThreads)
  321. err := f.startFromExternalCache()
  322. if err != nil {
  323. f.startWithoutExternalCache()
  324. }
  325. f.goDumpDb()
  326. f.threadPool = nil
  327. }
  328. func (f *Finder) startFind(path string) {
  329. if !filepath.IsAbs(path) {
  330. path = filepath.Join(f.cacheMetadata.Config.WorkingDirectory, path)
  331. }
  332. node := f.nodes.GetNode(path, true)
  333. f.statDirAsync(node)
  334. }
  335. func (f *Finder) lock() {
  336. f.mutex.Lock()
  337. }
  338. func (f *Finder) unlock() {
  339. f.mutex.Unlock()
  340. }
  341. // a statResponse is the relevant portion of the response from the filesystem to a Stat call
  342. type statResponse struct {
  343. ModTime int64
  344. Inode uint64
  345. Device uint64
  346. }
  347. // a pathAndStats stores a path and its stats
  348. type pathAndStats struct {
  349. statResponse
  350. Path string
  351. }
  352. // a dirFullInfo stores all of the relevant information we know about a directory
  353. type dirFullInfo struct {
  354. pathAndStats
  355. FileNames []string
  356. }
  357. // a PersistedDirInfo is the information about a dir that we save to our cache on disk
  358. type PersistedDirInfo struct {
  359. // These field names are short because they are repeated many times in the output json file
  360. P string // path
  361. T int64 // modification time
  362. I uint64 // inode number
  363. F []string // relevant filenames contained
  364. }
  365. // a PersistedDirs is the information that we persist for a group of dirs
  366. type PersistedDirs struct {
  367. // the device on which each directory is stored
  368. Device uint64
  369. // the common root path to which all contained dirs are relative
  370. Root string
  371. // the directories themselves
  372. Dirs []PersistedDirInfo
  373. }
  374. // a CacheEntry is the smallest unit that can be read and parsed from the cache (on disk) at a time
  375. type CacheEntry []PersistedDirs
  376. // a DirEntries lists the files and directories contained directly within a specific directory
  377. type DirEntries struct {
  378. Path string
  379. // elements of DirNames are just the dir names; they don't include any '/' character
  380. DirNames []string
  381. // elements of FileNames are just the file names; they don't include '/' character
  382. FileNames []string
  383. }
  384. // a WalkFunc is the type that is passed into various Find functions for determining which
  385. // directories the caller wishes be walked. The WalkFunc is expected to decide which
  386. // directories to walk and which files to consider as matches to the original query.
  387. type WalkFunc func(DirEntries) (dirs []string, files []string)
  388. // a mapNode stores the relevant stats about a directory to be stored in a pathMap
  389. type mapNode struct {
  390. statResponse
  391. FileNames []string
  392. }
  393. // a pathMap implements the directory tree structure of nodes
  394. type pathMap struct {
  395. mapNode
  396. path string
  397. children map[string]*pathMap
  398. // number of descendent nodes, including self
  399. approximateNumDescendents int
  400. }
  401. func newPathMap(path string) *pathMap {
  402. result := &pathMap{path: path, children: make(map[string]*pathMap, 4),
  403. approximateNumDescendents: 1}
  404. return result
  405. }
  406. // GetNode returns the node at <path>
  407. func (m *pathMap) GetNode(path string, createIfNotFound bool) *pathMap {
  408. if len(path) > 0 && path[0] == '/' {
  409. path = path[1:]
  410. }
  411. node := m
  412. for {
  413. if path == "" {
  414. return node
  415. }
  416. index := strings.Index(path, "/")
  417. var firstComponent string
  418. if index >= 0 {
  419. firstComponent = path[:index]
  420. path = path[index+1:]
  421. } else {
  422. firstComponent = path
  423. path = ""
  424. }
  425. child, found := node.children[firstComponent]
  426. if !found {
  427. if createIfNotFound {
  428. child = node.newChild(firstComponent)
  429. } else {
  430. return nil
  431. }
  432. }
  433. node = child
  434. }
  435. }
  436. func (m *pathMap) newChild(name string) (child *pathMap) {
  437. path := joinCleanPaths(m.path, name)
  438. newChild := newPathMap(path)
  439. m.children[name] = newChild
  440. return m.children[name]
  441. }
  442. func (m *pathMap) UpdateNumDescendents() int {
  443. count := 1
  444. for _, child := range m.children {
  445. count += child.approximateNumDescendents
  446. }
  447. m.approximateNumDescendents = count
  448. return count
  449. }
  450. func (m *pathMap) UpdateNumDescendentsRecursive() {
  451. for _, child := range m.children {
  452. child.UpdateNumDescendentsRecursive()
  453. }
  454. m.UpdateNumDescendents()
  455. }
  456. func (m *pathMap) MergeIn(other *pathMap) {
  457. for key, theirs := range other.children {
  458. ours, found := m.children[key]
  459. if found {
  460. ours.MergeIn(theirs)
  461. } else {
  462. m.children[key] = theirs
  463. }
  464. }
  465. if other.ModTime != 0 {
  466. m.mapNode = other.mapNode
  467. }
  468. m.UpdateNumDescendents()
  469. }
  470. func (m *pathMap) DumpAll() []dirFullInfo {
  471. results := []dirFullInfo{}
  472. m.dumpInto("", &results)
  473. return results
  474. }
  475. func (m *pathMap) dumpInto(path string, results *[]dirFullInfo) {
  476. *results = append(*results,
  477. dirFullInfo{
  478. pathAndStats{statResponse: m.statResponse, Path: path},
  479. m.FileNames},
  480. )
  481. for key, child := range m.children {
  482. childPath := joinCleanPaths(path, key)
  483. if len(childPath) == 0 || childPath[0] != '/' {
  484. childPath = "/" + childPath
  485. }
  486. child.dumpInto(childPath, results)
  487. }
  488. }
  489. // a semaphore can be locked by up to <capacity> callers at once
  490. type semaphore struct {
  491. pool chan bool
  492. }
  493. func newSemaphore(capacity int) *semaphore {
  494. return &semaphore{pool: make(chan bool, capacity)}
  495. }
  496. func (l *semaphore) Lock() {
  497. l.pool <- true
  498. }
  499. func (l *semaphore) Unlock() {
  500. <-l.pool
  501. }
  502. // A threadPool runs goroutines and supports throttling and waiting.
  503. // Without throttling, Go may exhaust the maximum number of various resources, such as
  504. // threads or file descriptors, and crash the program.
  505. type threadPool struct {
  506. receivedRequests sync.WaitGroup
  507. activeRequests semaphore
  508. }
  509. func newThreadPool(maxNumConcurrentThreads int) *threadPool {
  510. return &threadPool{
  511. receivedRequests: sync.WaitGroup{},
  512. activeRequests: *newSemaphore(maxNumConcurrentThreads),
  513. }
  514. }
  515. // Run requests to run the given function in its own goroutine
  516. func (p *threadPool) Run(function func()) {
  517. p.receivedRequests.Add(1)
  518. // If Run() was called from within a goroutine spawned by this threadPool,
  519. // then we may need to return from Run() before having capacity to actually
  520. // run <function>.
  521. //
  522. // It's possible that the body of <function> contains a statement (such as a syscall)
  523. // that will cause Go to pin it to a thread, or will contain a statement that uses
  524. // another resource that is in short supply (such as a file descriptor), so we can't
  525. // actually run <function> until we have capacity.
  526. //
  527. // However, the semaphore used for synchronization is implemented via a channel and
  528. // shouldn't require a new thread for each access.
  529. go func() {
  530. p.activeRequests.Lock()
  531. function()
  532. p.activeRequests.Unlock()
  533. p.receivedRequests.Done()
  534. }()
  535. }
  536. // Wait waits until all goroutines are done, just like sync.WaitGroup's Wait
  537. func (p *threadPool) Wait() {
  538. p.receivedRequests.Wait()
  539. }
  540. type fsErr struct {
  541. path string
  542. err error
  543. }
  544. func (e fsErr) String() string {
  545. return e.path + ": " + e.err.Error()
  546. }
  547. func (f *Finder) serializeCacheEntry(dirInfos []dirFullInfo) ([]byte, error) {
  548. // group each dirFullInfo by its Device, to avoid having to repeat it in the output
  549. dirsByDevice := map[uint64][]PersistedDirInfo{}
  550. for _, entry := range dirInfos {
  551. _, found := dirsByDevice[entry.Device]
  552. if !found {
  553. dirsByDevice[entry.Device] = []PersistedDirInfo{}
  554. }
  555. dirsByDevice[entry.Device] = append(dirsByDevice[entry.Device],
  556. PersistedDirInfo{P: entry.Path, T: entry.ModTime, I: entry.Inode, F: entry.FileNames})
  557. }
  558. cacheEntry := CacheEntry{}
  559. for device, infos := range dirsByDevice {
  560. // find common prefix
  561. prefix := ""
  562. if len(infos) > 0 {
  563. prefix = infos[0].P
  564. }
  565. for _, info := range infos {
  566. for !strings.HasPrefix(info.P+"/", prefix+"/") {
  567. prefix = filepath.Dir(prefix)
  568. if prefix == "/" {
  569. break
  570. }
  571. }
  572. }
  573. // remove common prefix
  574. for i := range infos {
  575. suffix := strings.Replace(infos[i].P, prefix, "", 1)
  576. if len(suffix) > 0 && suffix[0] == '/' {
  577. suffix = suffix[1:]
  578. }
  579. infos[i].P = suffix
  580. }
  581. // turn the map (keyed by device) into a list of structs with labeled fields
  582. // this is to improve readability of the output
  583. cacheEntry = append(cacheEntry, PersistedDirs{Device: device, Root: prefix, Dirs: infos})
  584. }
  585. // convert to json.
  586. // it would save some space to use a different format than json for the db file,
  587. // but the space and time savings are small, and json is easy for humans to read
  588. bytes, err := json.Marshal(cacheEntry)
  589. return bytes, err
  590. }
  591. func (f *Finder) parseCacheEntry(bytes []byte) ([]dirFullInfo, error) {
  592. var cacheEntry CacheEntry
  593. err := json.Unmarshal(bytes, &cacheEntry)
  594. if err != nil {
  595. return nil, err
  596. }
  597. // convert from a CacheEntry to a []dirFullInfo (by copying a few fields)
  598. capacity := 0
  599. for _, element := range cacheEntry {
  600. capacity += len(element.Dirs)
  601. }
  602. nodes := make([]dirFullInfo, capacity)
  603. count := 0
  604. for _, element := range cacheEntry {
  605. for _, dir := range element.Dirs {
  606. path := joinCleanPaths(element.Root, dir.P)
  607. nodes[count] = dirFullInfo{
  608. pathAndStats: pathAndStats{
  609. statResponse: statResponse{
  610. ModTime: dir.T, Inode: dir.I, Device: element.Device,
  611. },
  612. Path: path},
  613. FileNames: dir.F}
  614. count++
  615. }
  616. }
  617. return nodes, nil
  618. }
  619. // We use the following separator byte to distinguish individually parseable blocks of json
  620. // because we know this separator won't appear in the json that we're parsing.
  621. //
  622. // The newline byte can only appear in a UTF-8 stream if the newline character appears, because:
  623. // - The newline character is encoded as "0000 1010" in binary ("0a" in hex)
  624. // - UTF-8 dictates that bytes beginning with a "0" bit are never emitted as part of a multibyte
  625. // character.
  626. //
  627. // We know that the newline character will never appear in our json string, because:
  628. // - If a newline character appears as part of a data string, then json encoding will
  629. // emit two characters instead: '\' and 'n'.
  630. // - The json encoder that we use doesn't emit the optional newlines between any of its
  631. // other outputs.
  632. const lineSeparator = byte('\n')
  633. func (f *Finder) readLine(reader *bufio.Reader) ([]byte, error) {
  634. return reader.ReadBytes(lineSeparator)
  635. }
  636. // validateCacheHeader reads the cache header from cacheReader and tells whether the cache is compatible with this Finder
  637. func (f *Finder) validateCacheHeader(cacheReader *bufio.Reader) bool {
  638. cacheVersionBytes, err := f.readLine(cacheReader)
  639. if err != nil {
  640. f.verbosef("Failed to read database header; database is invalid\n")
  641. return false
  642. }
  643. if len(cacheVersionBytes) > 0 && cacheVersionBytes[len(cacheVersionBytes)-1] == lineSeparator {
  644. cacheVersionBytes = cacheVersionBytes[:len(cacheVersionBytes)-1]
  645. }
  646. cacheVersionString := string(cacheVersionBytes)
  647. currentVersion := f.cacheMetadata.Version
  648. if cacheVersionString != currentVersion {
  649. f.verbosef("Version changed from %q to %q, database is not applicable\n", cacheVersionString, currentVersion)
  650. return false
  651. }
  652. cacheParamBytes, err := f.readLine(cacheReader)
  653. if err != nil {
  654. f.verbosef("Failed to read database search params; database is invalid\n")
  655. return false
  656. }
  657. if len(cacheParamBytes) > 0 && cacheParamBytes[len(cacheParamBytes)-1] == lineSeparator {
  658. cacheParamBytes = cacheParamBytes[:len(cacheParamBytes)-1]
  659. }
  660. currentParamBytes, err := f.cacheMetadata.Config.Dump()
  661. if err != nil {
  662. panic("Finder failed to serialize its parameters")
  663. }
  664. cacheParamString := string(cacheParamBytes)
  665. currentParamString := string(currentParamBytes)
  666. if cacheParamString != currentParamString {
  667. f.verbosef("Params changed from %q to %q, database is not applicable\n", cacheParamString, currentParamString)
  668. return false
  669. }
  670. return true
  671. }
  672. // loadBytes compares the cache info in <data> to the state of the filesystem
  673. // loadBytes returns a map representing <data> and also a slice of dirs that need to be re-walked
  674. func (f *Finder) loadBytes(id int, data []byte) (m *pathMap, dirsToWalk []string, err error) {
  675. helperStartTime := time.Now()
  676. cachedNodes, err := f.parseCacheEntry(data)
  677. if err != nil {
  678. return nil, nil, fmt.Errorf("Failed to parse block %v: %v\n", id, err.Error())
  679. }
  680. unmarshalDate := time.Now()
  681. f.verbosef("Unmarshaled %v objects for %v in %v\n",
  682. len(cachedNodes), id, unmarshalDate.Sub(helperStartTime))
  683. tempMap := newPathMap("/")
  684. stats := make([]statResponse, len(cachedNodes))
  685. for i, node := range cachedNodes {
  686. // check the file system for an updated timestamp
  687. stats[i] = f.statDirSync(node.Path)
  688. }
  689. dirsToWalk = []string{}
  690. for i, cachedNode := range cachedNodes {
  691. updated := stats[i]
  692. // save the cached value
  693. container := tempMap.GetNode(cachedNode.Path, true)
  694. container.mapNode = mapNode{statResponse: updated}
  695. // if the metadata changed and the directory still exists, then
  696. // make a note to walk it later
  697. if !f.isInfoUpToDate(cachedNode.statResponse, updated) && updated.ModTime != 0 {
  698. f.setModified()
  699. // make a note that the directory needs to be walked
  700. dirsToWalk = append(dirsToWalk, cachedNode.Path)
  701. } else {
  702. container.mapNode.FileNames = cachedNode.FileNames
  703. }
  704. }
  705. // count the number of nodes to improve our understanding of the shape of the tree,
  706. // thereby improving parallelism of subsequent searches
  707. tempMap.UpdateNumDescendentsRecursive()
  708. f.verbosef("Statted inodes of block %v in %v\n", id, time.Now().Sub(unmarshalDate))
  709. return tempMap, dirsToWalk, nil
  710. }
  711. // startFromExternalCache loads the cache database from disk
  712. // startFromExternalCache waits to return until the load of the cache db is complete, but
  713. // startFromExternalCache does not wait for all every listDir() or statDir() request to complete
  714. func (f *Finder) startFromExternalCache() (err error) {
  715. startTime := time.Now()
  716. dbPath := f.DbPath
  717. // open cache file and validate its header
  718. reader, err := f.filesystem.Open(dbPath)
  719. if err != nil {
  720. return errors.New("No data to load from database\n")
  721. }
  722. defer reader.Close()
  723. bufferedReader := bufio.NewReader(reader)
  724. if !f.validateCacheHeader(bufferedReader) {
  725. return errors.New("Cache header does not match")
  726. }
  727. f.verbosef("Database header matches, will attempt to use database %v\n", f.DbPath)
  728. // read the file and spawn threads to process it
  729. nodesToWalk := [][]*pathMap{}
  730. mainTree := newPathMap("/")
  731. // read the blocks and stream them into <blockChannel>
  732. type dataBlock struct {
  733. id int
  734. err error
  735. data []byte
  736. }
  737. blockChannel := make(chan dataBlock, f.numDbLoadingThreads)
  738. readBlocks := func() {
  739. index := 0
  740. for {
  741. // It takes some time to unmarshal the input from json, so we want
  742. // to unmarshal it in parallel. In order to find valid places to
  743. // break the input, we scan for the line separators that we inserted
  744. // (for this purpose) when we dumped the database.
  745. data, err := f.readLine(bufferedReader)
  746. var response dataBlock
  747. done := false
  748. if err != nil && err != io.EOF {
  749. response = dataBlock{id: index, err: err, data: nil}
  750. done = true
  751. } else {
  752. done = (err == io.EOF)
  753. response = dataBlock{id: index, err: nil, data: data}
  754. }
  755. blockChannel <- response
  756. index++
  757. duration := time.Since(startTime)
  758. f.verbosef("Read block %v after %v\n", index, duration)
  759. if done {
  760. f.verbosef("Read %v blocks in %v\n", index, duration)
  761. close(blockChannel)
  762. return
  763. }
  764. }
  765. }
  766. go readBlocks()
  767. // Read from <blockChannel> and stream the responses into <resultChannel>.
  768. type workResponse struct {
  769. id int
  770. err error
  771. tree *pathMap
  772. updatedDirs []string
  773. }
  774. resultChannel := make(chan workResponse)
  775. processBlocks := func() {
  776. numProcessed := 0
  777. threadPool := newThreadPool(f.numDbLoadingThreads)
  778. for {
  779. // get a block to process
  780. block, received := <-blockChannel
  781. if !received {
  782. break
  783. }
  784. if block.err != nil {
  785. resultChannel <- workResponse{err: block.err}
  786. break
  787. }
  788. numProcessed++
  789. // wait until there is CPU available to process it
  790. threadPool.Run(
  791. func() {
  792. processStartTime := time.Now()
  793. f.verbosef("Starting to process block %v after %v\n",
  794. block.id, processStartTime.Sub(startTime))
  795. tempMap, updatedDirs, err := f.loadBytes(block.id, block.data)
  796. var response workResponse
  797. if err != nil {
  798. f.verbosef(
  799. "Block %v failed to parse with error %v\n",
  800. block.id, err)
  801. response = workResponse{err: err}
  802. } else {
  803. response = workResponse{
  804. id: block.id,
  805. err: nil,
  806. tree: tempMap,
  807. updatedDirs: updatedDirs,
  808. }
  809. }
  810. f.verbosef("Processed block %v in %v\n",
  811. block.id, time.Since(processStartTime),
  812. )
  813. resultChannel <- response
  814. },
  815. )
  816. }
  817. threadPool.Wait()
  818. f.verbosef("Finished processing %v blocks in %v\n",
  819. numProcessed, time.Since(startTime))
  820. close(resultChannel)
  821. }
  822. go processBlocks()
  823. // Read from <resultChannel> and use the results
  824. combineResults := func() (err error) {
  825. for {
  826. result, received := <-resultChannel
  827. if !received {
  828. break
  829. }
  830. if err != nil {
  831. // In case of an error, wait for work to complete before
  832. // returning the error. This ensures that any subsequent
  833. // work doesn't need to compete for resources (and possibly
  834. // fail due to, for example, a filesystem limit on the number of
  835. // concurrently open files) with past work.
  836. continue
  837. }
  838. if result.err != nil {
  839. err = result.err
  840. continue
  841. }
  842. // update main tree
  843. mainTree.MergeIn(result.tree)
  844. // record any new directories that we will need to Stat()
  845. updatedNodes := make([]*pathMap, len(result.updatedDirs))
  846. for j, dir := range result.updatedDirs {
  847. node := mainTree.GetNode(dir, false)
  848. updatedNodes[j] = node
  849. }
  850. nodesToWalk = append(nodesToWalk, updatedNodes)
  851. }
  852. return err
  853. }
  854. err = combineResults()
  855. if err != nil {
  856. return err
  857. }
  858. f.nodes = *mainTree
  859. // after having loaded the entire db and therefore created entries for
  860. // the directories we know of, now it's safe to start calling ReadDir on
  861. // any updated directories
  862. for i := range nodesToWalk {
  863. f.listDirsAsync(nodesToWalk[i])
  864. }
  865. f.verbosef("Loaded db and statted known dirs in %v\n", time.Since(startTime))
  866. f.threadPool.Wait()
  867. f.verbosef("Loaded db and statted all dirs in %v\n", time.Now().Sub(startTime))
  868. return err
  869. }
  870. // startWithoutExternalCache starts scanning the filesystem according to the cache config
  871. // startWithoutExternalCache should be called if startFromExternalCache is not applicable
  872. func (f *Finder) startWithoutExternalCache() {
  873. startTime := time.Now()
  874. configDirs := f.cacheMetadata.Config.RootDirs
  875. // clean paths
  876. candidates := make([]string, len(configDirs))
  877. for i, dir := range configDirs {
  878. candidates[i] = filepath.Clean(dir)
  879. }
  880. // remove duplicates
  881. dirsToScan := make([]string, 0, len(configDirs))
  882. for _, candidate := range candidates {
  883. include := true
  884. for _, included := range dirsToScan {
  885. if included == "/" || strings.HasPrefix(candidate+"/", included+"/") {
  886. include = false
  887. break
  888. }
  889. }
  890. if include {
  891. dirsToScan = append(dirsToScan, candidate)
  892. }
  893. }
  894. // start searching finally
  895. for _, path := range dirsToScan {
  896. f.verbosef("Starting find of %v\n", path)
  897. f.startFind(path)
  898. }
  899. f.threadPool.Wait()
  900. f.verbosef("Scanned filesystem (not using cache) in %v\n", time.Now().Sub(startTime))
  901. }
  902. // isInfoUpToDate tells whether <new> can confirm that results computed at <old> are still valid
  903. func (f *Finder) isInfoUpToDate(old statResponse, new statResponse) (equal bool) {
  904. if old.Inode != new.Inode {
  905. return false
  906. }
  907. if old.ModTime != new.ModTime {
  908. return false
  909. }
  910. if old.Device != new.Device {
  911. return false
  912. }
  913. return true
  914. }
  915. func (f *Finder) wasModified() bool {
  916. return atomic.LoadInt32(&f.modifiedFlag) > 0
  917. }
  918. func (f *Finder) setModified() {
  919. var newVal int32
  920. newVal = 1
  921. atomic.StoreInt32(&f.modifiedFlag, newVal)
  922. }
  923. // sortedDirEntries exports directory entries to facilitate dumping them to the external cache
  924. func (f *Finder) sortedDirEntries() []dirFullInfo {
  925. startTime := time.Now()
  926. nodes := make([]dirFullInfo, 0)
  927. for _, node := range f.nodes.DumpAll() {
  928. if node.ModTime != 0 {
  929. nodes = append(nodes, node)
  930. }
  931. }
  932. discoveryDate := time.Now()
  933. f.verbosef("Generated %v cache entries in %v\n", len(nodes), discoveryDate.Sub(startTime))
  934. less := func(i int, j int) bool {
  935. return nodes[i].Path < nodes[j].Path
  936. }
  937. sort.Slice(nodes, less)
  938. sortDate := time.Now()
  939. f.verbosef("Sorted %v cache entries in %v\n", len(nodes), sortDate.Sub(discoveryDate))
  940. return nodes
  941. }
  942. // serializeDb converts the cache database into a form to save to disk
  943. func (f *Finder) serializeDb() ([]byte, error) {
  944. // sort dir entries
  945. var entryList = f.sortedDirEntries()
  946. // Generate an output file that can be conveniently loaded using the same number of threads
  947. // as were used in this execution (because presumably that will be the number of threads
  948. // used in the next execution too)
  949. // generate header
  950. header := []byte{}
  951. header = append(header, []byte(f.cacheMetadata.Version)...)
  952. header = append(header, lineSeparator)
  953. configDump, err := f.cacheMetadata.Config.Dump()
  954. if err != nil {
  955. return nil, err
  956. }
  957. header = append(header, configDump...)
  958. // serialize individual blocks in parallel
  959. numBlocks := f.numDbLoadingThreads
  960. if numBlocks > len(entryList) {
  961. numBlocks = len(entryList)
  962. }
  963. blocks := make([][]byte, 1+numBlocks)
  964. blocks[0] = header
  965. blockMin := 0
  966. wg := sync.WaitGroup{}
  967. var errLock sync.Mutex
  968. for i := 1; i <= numBlocks; i++ {
  969. // identify next block
  970. blockMax := len(entryList) * i / numBlocks
  971. block := entryList[blockMin:blockMax]
  972. // process block
  973. wg.Add(1)
  974. go func(index int, block []dirFullInfo) {
  975. byteBlock, subErr := f.serializeCacheEntry(block)
  976. f.verbosef("Serialized block %v into %v bytes\n", index, len(byteBlock))
  977. if subErr != nil {
  978. f.verbosef("%v\n", subErr.Error())
  979. errLock.Lock()
  980. err = subErr
  981. errLock.Unlock()
  982. } else {
  983. blocks[index] = byteBlock
  984. }
  985. wg.Done()
  986. }(i, block)
  987. blockMin = blockMax
  988. }
  989. wg.Wait()
  990. if err != nil {
  991. return nil, err
  992. }
  993. content := bytes.Join(blocks, []byte{lineSeparator})
  994. return content, nil
  995. }
  996. // dumpDb saves the cache database to disk
  997. func (f *Finder) dumpDb() error {
  998. startTime := time.Now()
  999. f.verbosef("Dumping db\n")
  1000. tempPath := f.DbPath + ".tmp"
  1001. bytes, err := f.serializeDb()
  1002. if err != nil {
  1003. return err
  1004. }
  1005. serializeDate := time.Now()
  1006. f.verbosef("Serialized db in %v\n", serializeDate.Sub(startTime))
  1007. // dump file and atomically move
  1008. err = f.filesystem.WriteFile(tempPath, bytes, 0777)
  1009. if err != nil {
  1010. return err
  1011. }
  1012. err = f.filesystem.Rename(tempPath, f.DbPath)
  1013. if err != nil {
  1014. return err
  1015. }
  1016. f.verbosef("Wrote db in %v\n", time.Now().Sub(serializeDate))
  1017. return nil
  1018. }
  1019. // canIgnoreFsErr checks for certain classes of filesystem errors that are safe to ignore
  1020. func (f *Finder) canIgnoreFsErr(err error) bool {
  1021. pathErr, isPathErr := err.(*os.PathError)
  1022. if !isPathErr {
  1023. // Don't recognize this error
  1024. return false
  1025. }
  1026. if os.IsPermission(pathErr) {
  1027. // Permission errors are ignored:
  1028. // https://issuetracker.google.com/37553659
  1029. // https://github.com/google/kati/pull/116
  1030. return true
  1031. }
  1032. if pathErr.Err == os.ErrNotExist {
  1033. // If a directory doesn't exist, that generally means the cache is out-of-date
  1034. return true
  1035. }
  1036. // Don't recognize this error
  1037. return false
  1038. }
  1039. // onFsError should be called whenever a potentially fatal error is returned from a filesystem call
  1040. func (f *Finder) onFsError(path string, err error) {
  1041. if !f.canIgnoreFsErr(err) {
  1042. // We could send the errors through a channel instead, although that would cause this call
  1043. // to block unless we preallocated a sufficient buffer or spawned a reader thread.
  1044. // Although it wouldn't be too complicated to spawn a reader thread, it's still slightly
  1045. // more convenient to use a lock. Only in an unusual situation should this code be
  1046. // invoked anyway.
  1047. f.errlock.Lock()
  1048. f.fsErrs = append(f.fsErrs, fsErr{path: path, err: err})
  1049. f.errlock.Unlock()
  1050. }
  1051. }
  1052. // discardErrsForPrunedPaths removes any errors for paths that are no longer included in the cache
  1053. func (f *Finder) discardErrsForPrunedPaths() {
  1054. // This function could be somewhat inefficient due to being single-threaded,
  1055. // but the length of f.fsErrs should be approximately 0, so it shouldn't take long anyway.
  1056. relevantErrs := make([]fsErr, 0, len(f.fsErrs))
  1057. for _, fsErr := range f.fsErrs {
  1058. path := fsErr.path
  1059. node := f.nodes.GetNode(path, false)
  1060. if node != nil {
  1061. // The path in question wasn't pruned due to a failure to process a parent directory.
  1062. // So, the failure to process this path is important
  1063. relevantErrs = append(relevantErrs, fsErr)
  1064. }
  1065. }
  1066. f.fsErrs = relevantErrs
  1067. }
  1068. // getErr returns an error based on previous calls to onFsErr, if any
  1069. func (f *Finder) getErr() error {
  1070. f.discardErrsForPrunedPaths()
  1071. numErrs := len(f.fsErrs)
  1072. if numErrs < 1 {
  1073. return nil
  1074. }
  1075. maxNumErrsToInclude := 10
  1076. message := ""
  1077. if numErrs > maxNumErrsToInclude {
  1078. message = fmt.Sprintf("finder encountered %v errors: %v...", numErrs, f.fsErrs[:maxNumErrsToInclude])
  1079. } else {
  1080. message = fmt.Sprintf("finder encountered %v errors: %v", numErrs, f.fsErrs)
  1081. }
  1082. return errors.New(message)
  1083. }
  1084. func (f *Finder) statDirAsync(dir *pathMap) {
  1085. node := dir
  1086. path := dir.path
  1087. f.threadPool.Run(
  1088. func() {
  1089. updatedStats := f.statDirSync(path)
  1090. if !f.isInfoUpToDate(node.statResponse, updatedStats) {
  1091. node.mapNode = mapNode{
  1092. statResponse: updatedStats,
  1093. FileNames: []string{},
  1094. }
  1095. f.setModified()
  1096. if node.statResponse.ModTime != 0 {
  1097. // modification time was updated, so re-scan for
  1098. // child directories
  1099. f.listDirAsync(dir)
  1100. }
  1101. }
  1102. },
  1103. )
  1104. }
  1105. func (f *Finder) statDirSync(path string) statResponse {
  1106. fileInfo, err := f.filesystem.Lstat(path)
  1107. var stats statResponse
  1108. if err != nil {
  1109. // possibly record this error
  1110. f.onFsError(path, err)
  1111. // in case of a failure to stat the directory, treat the directory as missing (modTime = 0)
  1112. return stats
  1113. }
  1114. modTime := fileInfo.ModTime()
  1115. stats = statResponse{}
  1116. inode, err := f.filesystem.InodeNumber(fileInfo)
  1117. if err != nil {
  1118. panic(fmt.Sprintf("Could not get inode number of %v: %v\n", path, err.Error()))
  1119. }
  1120. stats.Inode = inode
  1121. device, err := f.filesystem.DeviceNumber(fileInfo)
  1122. if err != nil {
  1123. panic(fmt.Sprintf("Could not get device number of %v: %v\n", path, err.Error()))
  1124. }
  1125. stats.Device = device
  1126. permissionsChangeTime, err := f.filesystem.PermTime(fileInfo)
  1127. if err != nil {
  1128. panic(fmt.Sprintf("Could not get permissions modification time (CTime) of %v: %v\n", path, err.Error()))
  1129. }
  1130. // We're only interested in knowing whether anything about the directory
  1131. // has changed since last check, so we use the latest of the two
  1132. // modification times (content modification (mtime) and
  1133. // permission modification (ctime))
  1134. if permissionsChangeTime.After(modTime) {
  1135. modTime = permissionsChangeTime
  1136. }
  1137. stats.ModTime = modTime.UnixNano()
  1138. return stats
  1139. }
  1140. func (f *Finder) shouldIncludeFile(fileName string) bool {
  1141. for _, includedName := range f.cacheMetadata.Config.IncludeFiles {
  1142. if fileName == includedName {
  1143. return true
  1144. }
  1145. }
  1146. for _, includeSuffix := range f.cacheMetadata.Config.IncludeSuffixes {
  1147. if strings.HasSuffix(fileName, includeSuffix) {
  1148. return true
  1149. }
  1150. }
  1151. return false
  1152. }
  1153. // pruneCacheCandidates removes the items that we don't want to include in our persistent cache
  1154. func (f *Finder) pruneCacheCandidates(items *DirEntries) {
  1155. for _, fileName := range items.FileNames {
  1156. for _, abortedName := range f.cacheMetadata.Config.PruneFiles {
  1157. if fileName == abortedName {
  1158. items.FileNames = []string{}
  1159. items.DirNames = []string{}
  1160. return
  1161. }
  1162. }
  1163. }
  1164. // remove any files that aren't the ones we want to include
  1165. writeIndex := 0
  1166. for _, fileName := range items.FileNames {
  1167. if f.shouldIncludeFile(fileName) {
  1168. items.FileNames[writeIndex] = fileName
  1169. writeIndex++
  1170. }
  1171. }
  1172. // resize
  1173. items.FileNames = items.FileNames[:writeIndex]
  1174. writeIndex = 0
  1175. for _, dirName := range items.DirNames {
  1176. items.DirNames[writeIndex] = dirName
  1177. // ignore other dirs that are known to not be inputs to the build process
  1178. include := true
  1179. for _, excludedName := range f.cacheMetadata.Config.ExcludeDirs {
  1180. if dirName == excludedName {
  1181. // don't include
  1182. include = false
  1183. break
  1184. }
  1185. }
  1186. if include {
  1187. writeIndex++
  1188. }
  1189. }
  1190. // resize
  1191. items.DirNames = items.DirNames[:writeIndex]
  1192. }
  1193. func (f *Finder) listDirsAsync(nodes []*pathMap) {
  1194. f.threadPool.Run(
  1195. func() {
  1196. for i := range nodes {
  1197. f.listDirSync(nodes[i])
  1198. }
  1199. },
  1200. )
  1201. }
  1202. func (f *Finder) listDirAsync(node *pathMap) {
  1203. f.threadPool.Run(
  1204. func() {
  1205. f.listDirSync(node)
  1206. },
  1207. )
  1208. }
  1209. func (f *Finder) listDirSync(dir *pathMap) {
  1210. path := dir.path
  1211. children, err := f.filesystem.ReadDir(path)
  1212. if err != nil {
  1213. // possibly record this error
  1214. f.onFsError(path, err)
  1215. // if listing the contents of the directory fails (presumably due to
  1216. // permission denied), then treat the directory as empty
  1217. children = nil
  1218. }
  1219. var subdirs []string
  1220. var subfiles []string
  1221. for _, child := range children {
  1222. linkBits := child.Mode() & os.ModeSymlink
  1223. isLink := linkBits != 0
  1224. if isLink {
  1225. childPath := filepath.Join(path, child.Name())
  1226. childStat, err := f.filesystem.Stat(childPath)
  1227. if err != nil {
  1228. // If stat fails this is probably a broken or dangling symlink, treat it as a file.
  1229. subfiles = append(subfiles, child.Name())
  1230. } else if childStat.IsDir() {
  1231. // Skip symlink dirs.
  1232. // We don't have to support symlink dirs because
  1233. // that would cause duplicates.
  1234. } else {
  1235. // We do have to support symlink files because the link name might be
  1236. // different than the target name
  1237. // (for example, Android.bp -> build/soong/root.bp)
  1238. subfiles = append(subfiles, child.Name())
  1239. }
  1240. } else if child.IsDir() {
  1241. subdirs = append(subdirs, child.Name())
  1242. } else {
  1243. subfiles = append(subfiles, child.Name())
  1244. }
  1245. }
  1246. parentNode := dir
  1247. entry := &DirEntries{Path: path, DirNames: subdirs, FileNames: subfiles}
  1248. f.pruneCacheCandidates(entry)
  1249. // create a pathMap node for each relevant subdirectory
  1250. relevantChildren := map[string]*pathMap{}
  1251. for _, subdirName := range entry.DirNames {
  1252. childNode, found := parentNode.children[subdirName]
  1253. // if we already knew of this directory, then we already have a request pending to Stat it
  1254. // if we didn't already know of this directory, then we must Stat it now
  1255. if !found {
  1256. childNode = parentNode.newChild(subdirName)
  1257. f.statDirAsync(childNode)
  1258. }
  1259. relevantChildren[subdirName] = childNode
  1260. }
  1261. // Note that in rare cases, it's possible that we're reducing the set of
  1262. // children via this statement, if these are all true:
  1263. // 1. we previously had a cache that knew about subdirectories of parentNode
  1264. // 2. the user created a prune-file (described in pruneCacheCandidates)
  1265. // inside <parentNode>, which specifies that the contents of parentNode
  1266. // are to be ignored.
  1267. // The fact that it's possible to remove children here means that *pathMap structs
  1268. // must not be looked up from f.nodes by filepath (and instead must be accessed by
  1269. // direct pointer) until after every listDirSync completes
  1270. parentNode.FileNames = entry.FileNames
  1271. parentNode.children = relevantChildren
  1272. }
  1273. // listMatches takes a node and a function that specifies which subdirectories and
  1274. // files to include, and listMatches returns the matches
  1275. func (f *Finder) listMatches(node *pathMap,
  1276. filter WalkFunc) (subDirs []*pathMap, filePaths []string) {
  1277. entries := DirEntries{
  1278. FileNames: node.FileNames,
  1279. }
  1280. entries.DirNames = make([]string, 0, len(node.children))
  1281. for childName := range node.children {
  1282. entries.DirNames = append(entries.DirNames, childName)
  1283. }
  1284. dirNames, fileNames := filter(entries)
  1285. subDirs = []*pathMap{}
  1286. filePaths = make([]string, 0, len(fileNames))
  1287. for _, fileName := range fileNames {
  1288. filePaths = append(filePaths, joinCleanPaths(node.path, fileName))
  1289. }
  1290. subDirs = make([]*pathMap, 0, len(dirNames))
  1291. for _, childName := range dirNames {
  1292. child, ok := node.children[childName]
  1293. if ok {
  1294. subDirs = append(subDirs, child)
  1295. }
  1296. }
  1297. return subDirs, filePaths
  1298. }
  1299. // findInCacheMultithreaded spawns potentially multiple goroutines with which to search the cache.
  1300. func (f *Finder) findInCacheMultithreaded(node *pathMap, filter WalkFunc,
  1301. approxNumThreads int) []string {
  1302. if approxNumThreads < 2 {
  1303. // Done spawning threads; process remaining directories
  1304. return f.findInCacheSinglethreaded(node, filter)
  1305. }
  1306. totalWork := 0
  1307. for _, child := range node.children {
  1308. totalWork += child.approximateNumDescendents
  1309. }
  1310. childrenResults := make(chan []string, len(node.children))
  1311. subDirs, filePaths := f.listMatches(node, filter)
  1312. // process child directories
  1313. for _, child := range subDirs {
  1314. numChildThreads := approxNumThreads * child.approximateNumDescendents / totalWork
  1315. childProcessor := func(child *pathMap) {
  1316. childResults := f.findInCacheMultithreaded(child, filter, numChildThreads)
  1317. childrenResults <- childResults
  1318. }
  1319. // If we're allowed to use more than 1 thread to process this directory,
  1320. // then instead we use 1 thread for each subdirectory.
  1321. // It would be strange to spawn threads for only some subdirectories.
  1322. go childProcessor(child)
  1323. }
  1324. // collect results
  1325. for i := 0; i < len(subDirs); i++ {
  1326. childResults := <-childrenResults
  1327. filePaths = append(filePaths, childResults...)
  1328. }
  1329. close(childrenResults)
  1330. return filePaths
  1331. }
  1332. // findInCacheSinglethreaded synchronously searches the cache for all matching file paths
  1333. // note findInCacheSinglethreaded runs 2X to 4X as fast by being iterative rather than recursive
  1334. func (f *Finder) findInCacheSinglethreaded(node *pathMap, filter WalkFunc) []string {
  1335. if node == nil {
  1336. return []string{}
  1337. }
  1338. nodes := []*pathMap{node}
  1339. matches := []string{}
  1340. for len(nodes) > 0 {
  1341. currentNode := nodes[0]
  1342. nodes = nodes[1:]
  1343. subDirs, filePaths := f.listMatches(currentNode, filter)
  1344. nodes = append(nodes, subDirs...)
  1345. matches = append(matches, filePaths...)
  1346. }
  1347. return matches
  1348. }