From 6ae56b78f545a5be2fc9e9bb6013443a35716fc4 Mon Sep 17 00:00:00 2001
From: Nick Santos <nick.santos@docker.com>
Date: Thu, 21 Jul 2022 11:20:14 +0100
Subject: [PATCH] kqueue: Make watcher.Close() O(n) instead of O(n^2) (#233)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

In the old implementation watcher.Close() would clone the list of
watches and then run Remove() on that, and every Remove() call would
iterate over the full list of watches.

This stores the watches more efficiently so that Remove() doesn't need
to iterate over the full list: instead of merely a path → fd map, it
also stores a parent-path → list-of-files.

No functional changes, just a performance improvement.
---
 kqueue.go | 43 ++++++++++++++++++++++++++++++-------------
 1 file changed, 30 insertions(+), 13 deletions(-)

diff --git a/kqueue.go b/kqueue.go
index 1b46acb..87c25b0 100644
--- a/kqueue.go
+++ b/kqueue.go
@@ -27,13 +27,14 @@ type Watcher struct {
 
 	kq int // File descriptor (as returned by the kqueue() syscall).
 
-	mu              sync.Mutex        // Protects access to watcher data
-	watches         map[string]int    // Map of watched file descriptors (key: path).
-	externalWatches map[string]bool   // Map of watches added by user of the library.
-	dirFlags        map[string]uint32 // Map of watched directories to fflags used in kqueue.
-	paths           map[int]pathInfo  // Map file descriptors to path names for processing kqueue events.
-	fileExists      map[string]bool   // Keep track of if we know this file exists (to stop duplicate create events).
-	isClosed        bool              // Set to true when Close() is first called
+	mu              sync.Mutex                  // Protects access to watcher data
+	watches         map[string]int              // Map of watched file descriptors (key: path).
+	watchesByDir    map[string]map[int]struct{} // Map of watched file descriptors indexed by the parent directory (key: dirname(path)).
+	externalWatches map[string]bool             // Map of watches added by user of the library.
+	dirFlags        map[string]uint32           // Map of watched directories to fflags used in kqueue.
+	paths           map[int]pathInfo            // Map file descriptors to path names for processing kqueue events.
+	fileExists      map[string]bool             // Keep track of if we know this file exists (to stop duplicate create events).
+	isClosed        bool                        // Set to true when Close() is first called
 }
 
 type pathInfo struct {
@@ -51,6 +52,7 @@ func NewWatcher() (*Watcher, error) {
 	w := &Watcher{
 		kq:              kq,
 		watches:         make(map[string]int),
+		watchesByDir:    make(map[string]map[int]struct{}),
 		dirFlags:        make(map[string]uint32),
 		paths:           make(map[int]pathInfo),
 		fileExists:      make(map[string]bool),
@@ -120,6 +122,14 @@ func (w *Watcher) Remove(name string) error {
 	w.mu.Lock()
 	isDir := w.paths[watchfd].isDir
 	delete(w.watches, name)
+
+	parentName := filepath.Dir(name)
+	delete(w.watchesByDir[parentName], watchfd)
+
+	if len(w.watchesByDir[parentName]) == 0 {
+		delete(w.watchesByDir, parentName)
+	}
+
 	delete(w.paths, watchfd)
 	delete(w.dirFlags, name)
 	w.mu.Unlock()
@@ -128,12 +138,10 @@ func (w *Watcher) Remove(name string) error {
 	if isDir {
 		var pathsToRemove []string
 		w.mu.Lock()
-		for _, path := range w.paths {
-			wdir, _ := filepath.Split(path.name)
-			if filepath.Clean(wdir) == name {
-				if !w.externalWatches[path.name] {
-					pathsToRemove = append(pathsToRemove, path.name)
-				}
+		for fd := range w.watchesByDir[name] {
+			path := w.paths[fd]
+			if !w.externalWatches[path.name] {
+				pathsToRemove = append(pathsToRemove, path.name)
 			}
 		}
 		w.mu.Unlock()
@@ -245,7 +253,16 @@ func (w *Watcher) addWatch(name string, flags uint32) (string, error) {
 
 	if !alreadyWatching {
 		w.mu.Lock()
+		parentName := filepath.Dir(name)
 		w.watches[name] = watchfd
+
+		watchesByDir, ok := w.watchesByDir[parentName]
+		if !ok {
+			watchesByDir = make(map[int]struct{}, 1)
+			w.watchesByDir[parentName] = watchesByDir
+		}
+		watchesByDir[watchfd] = struct{}{}
+
 		w.paths[watchfd] = pathInfo{name: name, isDir: isDir}
 		w.mu.Unlock()
 	}
-- 
2.50.1