1 // Copyright 2016 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Package fastwalk provides a faster version of filepath.Walk for file system
17 // TraverseLink is used as a return value from WalkFuncs to indicate that the
18 // symlink named in the call may be traversed.
19 var TraverseLink = errors.New("fastwalk: traverse symlink, assuming target is a directory")
21 // SkipFiles is a used as a return value from WalkFuncs to indicate that the
22 // callback should not be called for any other files in the current directory.
23 // Child directories will still be traversed.
24 var SkipFiles = errors.New("fastwalk: skip remaining files in directory")
26 // Walk is a faster implementation of filepath.Walk.
28 // filepath.Walk's design necessarily calls os.Lstat on each file,
29 // even if the caller needs less info.
30 // Many tools need only the type of each file.
31 // On some platforms, this information is provided directly by the readdir
32 // system call, avoiding the need to stat each file individually.
33 // fastwalk_unix.go contains a fork of the syscall routines.
35 // See golang.org/issue/16399
37 // Walk walks the file tree rooted at root, calling walkFn for
38 // each file or directory in the tree, including root.
40 // If fastWalk returns filepath.SkipDir, the directory is skipped.
42 // Unlike filepath.Walk:
43 // * file stat calls must be done by the user.
44 // The only provided metadata is the file type, which does not include
45 // any permission bits.
46 // * multiple goroutines stat the filesystem concurrently. The provided
47 // walkFn must be safe for concurrent use.
48 // * fastWalk can follow symlinks if walkFn returns the TraverseLink
49 // sentinel error. It is the walkFn's responsibility to prevent
50 // fastWalk from going into symlink cycles.
51 func Walk(root string, walkFn func(path string, typ os.FileMode) error) error {
52 // TODO(bradfitz): make numWorkers configurable? We used a
53 // minimum of 4 to give the kernel more info about multiple
54 // things we want, in hopes its I/O scheduling can take
55 // advantage of that. Hopefully most are in cache. Maybe 4 is
56 // even too low of a minimum. Profile more.
58 if n := runtime.NumCPU(); n > numWorkers {
62 // Make sure to wait for all workers to finish, otherwise
63 // walkFn could still be called after returning. This Wait call
64 // runs after close(e.donec) below.
70 enqueuec: make(chan walkItem, numWorkers), // buffered for performance
71 workc: make(chan walkItem, numWorkers), // buffered for performance
72 donec: make(chan struct{}),
74 // buffered for correctness & not leaking goroutines:
75 resc: make(chan error, numWorkers),
79 for i := 0; i < numWorkers; i++ {
83 todo := []walkItem{{dir: root}}
91 workItem = todo[len(todo)-1]
94 case workc <- workItem:
95 todo = todo[:len(todo)-1]
97 case it := <-w.enqueuec:
98 todo = append(todo, it)
104 if out == 0 && len(todo) == 0 {
105 // It's safe to quit here, as long as the buffered
106 // enqueue channel isn't also readable, which might
107 // happen if the worker sends both another unit of
108 // work and its result before the other select was
109 // scheduled and both w.resc and w.enqueuec were
112 case it := <-w.enqueuec:
113 todo = append(todo, it)
122 // doWork reads directories as instructed (via workc) and runs the
123 // user's callback function.
124 func (w *walker) doWork(wg *sync.WaitGroup) {
130 case it := <-w.workc:
134 case w.resc <- w.walk(it.dir, !it.callbackDone):
141 fn func(path string, typ os.FileMode) error
143 donec chan struct{} // closed on fastWalk's return
144 workc chan walkItem // to workers
145 enqueuec chan walkItem // from workers
146 resc chan error // from workers
149 type walkItem struct {
151 callbackDone bool // callback already called; don't do it again
154 func (w *walker) enqueue(it walkItem) {
156 case w.enqueuec <- it:
161 func (w *walker) onDirEnt(dirName, baseName string, typ os.FileMode) error {
162 joined := dirName + string(os.PathSeparator) + baseName
163 if typ == os.ModeDir {
164 w.enqueue(walkItem{dir: joined})
168 err := w.fn(joined, typ)
169 if typ == os.ModeSymlink {
170 if err == TraverseLink {
171 // Set callbackDone so we don't call it twice for both the
172 // symlink-as-symlink and the symlink-as-directory later:
173 w.enqueue(walkItem{dir: joined, callbackDone: true})
176 if err == filepath.SkipDir {
177 // Permit SkipDir on symlinks too.
184 func (w *walker) walk(root string, runUserCallback bool) error {
186 err := w.fn(root, os.ModeDir)
187 if err == filepath.SkipDir {
195 return readDir(root, w.onDirEnt)