From 6f933a934f715f4bcd4f4e4430d4040b6cf61032 Mon Sep 17 00:00:00 2001 From: Michael Pratt Date: Fri, 21 Jun 2019 16:26:26 -0700 Subject: Remove O(n) lookup on unlink/rename Currently, the path tracking in the gofer involves an O(n) lookup of child fidRefs. This causes a significant overhead on unlinks in directories with lots of child fidRefs (<4k). In this transition, pathNode moves from sync.Map to normal synchronized maps. There is a small chance of contention in walk, but the lock is held for a very short time (and sync.Map also had a chance of requiring locking). OTOH, sync.Map makes it very difficult to add a fidRef reverse map. PiperOrigin-RevId: 254489952 --- pkg/p9/path_tree.go | 211 +++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 159 insertions(+), 52 deletions(-) (limited to 'pkg/p9/path_tree.go') diff --git a/pkg/p9/path_tree.go b/pkg/p9/path_tree.go index 5a209b291..865459411 100644 --- a/pkg/p9/path_tree.go +++ b/pkg/p9/path_tree.go @@ -22,93 +22,200 @@ import ( // pathNode is a single node in a path traversal. // // These are shared by all fidRefs that point to the same path. +// +// Lock ordering: +// opMu +// childMu +// +// Two different pathNodes may only be locked if Server.renameMu is held for +// write, in which case they can be acquired in any order. type pathNode struct { - // fidRefName is a map[*fidRef]string mapping child fidRefs to their - // path component name. - fidRefNames sync.Map + // opMu synchronizes high-level, sematic operations, such as the + // simultaneous creation and deletion of a file. + // + // opMu does not directly protect any fields in pathNode. + opMu sync.RWMutex - // childNodes is a map[string]*pathNode mapping child path component - // names to their pathNode. - childNodes sync.Map + // childMu protects the fields below. + childMu sync.RWMutex - // mu does *not* protect the fields above. - // - // They are not synchronized because we allow certain operations (file - // walk) to proceed without having to acquire a write lock. mu exists - // to synchronize high-level, semantic operations, such as the - // simultaneous creation and deletion of a file. - mu sync.RWMutex + // childNodes maps child path component names to their pathNode. + childNodes map[string]*pathNode + + // childRefs maps child path component names to all of the their + // references. + childRefs map[string]map[*fidRef]struct{} + + // childRefNames maps child references back to their path component + // name. + childRefNames map[*fidRef]string +} + +func newPathNode() *pathNode { + return &pathNode{ + childNodes: make(map[string]*pathNode), + childRefs: make(map[string]map[*fidRef]struct{}), + childRefNames: make(map[*fidRef]string), + } +} + +// forEachChildRef calls fn for each child reference. +func (p *pathNode) forEachChildRef(fn func(ref *fidRef, name string)) { + p.childMu.RLock() + defer p.childMu.RUnlock() + + for name, m := range p.childRefs { + for ref := range m { + fn(ref, name) + } + } +} + +// forEachChildNode calls fn for each child pathNode. +func (p *pathNode) forEachChildNode(fn func(pn *pathNode)) { + p.childMu.RLock() + defer p.childMu.RUnlock() + + for _, pn := range p.childNodes { + fn(pn) + } } // pathNodeFor returns the path node for the given name, or a new one. -// -// Precondition: This call is synchronized w.r.t. other adding or removing of -// children. func (p *pathNode) pathNodeFor(name string) *pathNode { - // Load the existing path node. - if pn, ok := p.childNodes.Load(name); ok { - return pn.(*pathNode) + p.childMu.RLock() + // Fast path, node already exists. + if pn, ok := p.childNodes[name]; ok { + p.childMu.RUnlock() + return pn + } + p.childMu.RUnlock() + + // Slow path, create a new pathNode for shared use. + p.childMu.Lock() + + // Re-check after re-lock. + if pn, ok := p.childNodes[name]; ok { + p.childMu.Unlock() + return pn } - // Create a new pathNode for shared use. - pn, _ := p.childNodes.LoadOrStore(name, new(pathNode)) - return pn.(*pathNode) + pn := newPathNode() + p.childNodes[name] = pn + p.childMu.Unlock() + return pn } // nameFor returns the name for the given fidRef. // // Precondition: addChild is called for ref before nameFor. func (p *pathNode) nameFor(ref *fidRef) string { - if s, ok := p.fidRefNames.Load(ref); ok { - return s.(string) + p.childMu.RLock() + n, ok := p.childRefNames[ref] + p.childMu.RUnlock() + + if !ok { + // This should not happen, don't proceed. + panic(fmt.Sprintf("expected name for %+v, none found", ref)) } - // This should not happen, don't proceed. - panic(fmt.Sprintf("expected name for %+v, none found", ref)) + return n } -// addChild adds a child to p. +// addChildLocked adds a child reference to p. // -// This applies only to an individual fidRef. -// -// Precondition: ref is added only once unless it is removed before adding with -// a new name. -func (p *pathNode) addChild(ref *fidRef, name string) { - if s, ok := p.fidRefNames.Load(ref); ok { +// Precondition: As addChild, plus childMu is locked for write. +func (p *pathNode) addChildLocked(ref *fidRef, name string) { + if n, ok := p.childRefNames[ref]; ok { // This should not happen, don't proceed. - panic(fmt.Sprintf("unexpected fidRef %+v with path %q, wanted %q", ref, s, name)) + panic(fmt.Sprintf("unexpected fidRef %+v with path %q, wanted %q", ref, n, name)) } - p.fidRefNames.Store(ref, name) + p.childRefNames[ref] = name + + m, ok := p.childRefs[name] + if !ok { + m = make(map[*fidRef]struct{}) + p.childRefs[name] = m + } + + m[ref] = struct{}{} +} + +// addChild adds a child reference to p. +// +// Precondition: ref may only be added once at a time. +func (p *pathNode) addChild(ref *fidRef, name string) { + p.childMu.Lock() + p.addChildLocked(ref, name) + p.childMu.Unlock() } // removeChild removes the given child. // -// This applies only to an individual fidRef. +// This applies only to an individual fidRef, which is not required to exist. func (p *pathNode) removeChild(ref *fidRef) { - p.fidRefNames.Delete(ref) + p.childMu.Lock() + + // This ref may not exist anymore. This can occur, e.g., in unlink, + // where a removeWithName removes the ref, and then a DecRef on the ref + // attempts to remove again. + if name, ok := p.childRefNames[ref]; ok { + m, ok := p.childRefs[name] + if !ok { + // This should not happen, don't proceed. + p.childMu.Unlock() + panic(fmt.Sprintf("name %s missing from childfidRefs", name)) + } + + delete(m, ref) + if len(m) == 0 { + delete(p.childRefs, name) + } + } + + delete(p.childRefNames, ref) + + p.childMu.Unlock() } -// removeWithName removes all references with the given name. +// addPathNodeFor adds an existing pathNode as the node for name. // -// The original pathNode is returned by this function, and removed from this -// pathNode. Any operations on the removed tree must use this value. +// Preconditions: newName does not exist. +func (p *pathNode) addPathNodeFor(name string, pn *pathNode) { + p.childMu.Lock() + + if opn, ok := p.childNodes[name]; ok { + p.childMu.Unlock() + panic(fmt.Sprintf("unexpected pathNode %+v with path %q", opn, name)) + } + + p.childNodes[name] = pn + p.childMu.Unlock() +} + +// removeWithName removes all references with the given name. // -// The provided function is executed after removal. +// The provided function is executed after reference removal. The only method +// it may (transitively) call on this pathNode is addChildLocked. // -// Precondition: This call is synchronized w.r.t. other adding or removing of -// children. +// If a child pathNode for name exists, it is removed from this pathNode and +// returned by this function. Any operations on the removed tree must use this +// value. func (p *pathNode) removeWithName(name string, fn func(ref *fidRef)) *pathNode { - p.fidRefNames.Range(func(key, value interface{}) bool { - if value.(string) == name { - p.fidRefNames.Delete(key) - fn(key.(*fidRef)) + p.childMu.Lock() + defer p.childMu.Unlock() + + if m, ok := p.childRefs[name]; ok { + for ref := range m { + delete(m, ref) + delete(p.childRefNames, ref) + fn(ref) } - return true - }) + } - // Return the original path node. - origPathNode := p.pathNodeFor(name) - p.childNodes.Delete(name) + // Return the original path node, if it exists. + origPathNode := p.childNodes[name] + delete(p.childNodes, name) return origPathNode } -- cgit v1.2.3