Source file src/sync/map.go

     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.
     4  
     5  package sync
     6  
     7  import (
     8  	"sync/atomic"
     9  )
    10  
    11  // Map is like a Go map[any]any but is safe for concurrent use
    12  // by multiple goroutines without additional locking or coordination.
    13  // Loads, stores, and deletes run in amortized constant time.
    14  //
    15  // The Map type is specialized. Most code should use a plain Go map instead,
    16  // with separate locking or coordination, for better type safety and to make it
    17  // easier to maintain other invariants along with the map content.
    18  //
    19  // The Map type is optimized for two common use cases: (1) when the entry for a given
    20  // key is only ever written once but read many times, as in caches that only grow,
    21  // or (2) when multiple goroutines read, write, and overwrite entries for disjoint
    22  // sets of keys. In these two cases, use of a Map may significantly reduce lock
    23  // contention compared to a Go map paired with a separate Mutex or RWMutex.
    24  //
    25  // The zero Map is empty and ready for use. A Map must not be copied after first use.
    26  //
    27  // In the terminology of the Go memory model, Map arranges that a write operation
    28  // “synchronizes before” any read operation that observes the effect of the write, where
    29  // read and write operations are defined as follows.
    30  // Load, LoadAndDelete, LoadOrStore, Swap, CompareAndSwap, and CompareAndDelete
    31  // are read operations; Delete, LoadAndDelete, Store, and Swap are write operations;
    32  // LoadOrStore is a write operation when it returns loaded set to false;
    33  // CompareAndSwap is a write operation when it returns swapped set to true;
    34  // and CompareAndDelete is a write operation when it returns deleted set to true.
    35  type Map struct {
    36  	mu Mutex
    37  
    38  	// read contains the portion of the map's contents that are safe for
    39  	// concurrent access (with or without mu held).
    40  	//
    41  	// The read field itself is always safe to load, but must only be stored with
    42  	// mu held.
    43  	//
    44  	// Entries stored in read may be updated concurrently without mu, but updating
    45  	// a previously-expunged entry requires that the entry be copied to the dirty
    46  	// map and unexpunged with mu held.
    47  	read atomic.Pointer[readOnly]
    48  
    49  	// dirty contains the portion of the map's contents that require mu to be
    50  	// held. To ensure that the dirty map can be promoted to the read map quickly,
    51  	// it also includes all of the non-expunged entries in the read map.
    52  	//
    53  	// Expunged entries are not stored in the dirty map. An expunged entry in the
    54  	// clean map must be unexpunged and added to the dirty map before a new value
    55  	// can be stored to it.
    56  	//
    57  	// If the dirty map is nil, the next write to the map will initialize it by
    58  	// making a shallow copy of the clean map, omitting stale entries.
    59  	dirty map[any]*entry
    60  
    61  	// misses counts the number of loads since the read map was last updated that
    62  	// needed to lock mu to determine whether the key was present.
    63  	//
    64  	// Once enough misses have occurred to cover the cost of copying the dirty
    65  	// map, the dirty map will be promoted to the read map (in the unamended
    66  	// state) and the next store to the map will make a new dirty copy.
    67  	misses int
    68  }
    69  
    70  // readOnly is an immutable struct stored atomically in the Map.read field.
    71  type readOnly struct {
    72  	m       map[any]*entry
    73  	amended bool // true if the dirty map contains some key not in m.
    74  }
    75  
    76  // expunged is an arbitrary pointer that marks entries which have been deleted
    77  // from the dirty map.
    78  var expunged = new(any)
    79  
    80  // An entry is a slot in the map corresponding to a particular key.
    81  type entry struct {
    82  	// p points to the interface{} value stored for the entry.
    83  	//
    84  	// If p == nil, the entry has been deleted, and either m.dirty == nil or
    85  	// m.dirty[key] is e.
    86  	//
    87  	// If p == expunged, the entry has been deleted, m.dirty != nil, and the entry
    88  	// is missing from m.dirty.
    89  	//
    90  	// Otherwise, the entry is valid and recorded in m.read.m[key] and, if m.dirty
    91  	// != nil, in m.dirty[key].
    92  	//
    93  	// An entry can be deleted by atomic replacement with nil: when m.dirty is
    94  	// next created, it will atomically replace nil with expunged and leave
    95  	// m.dirty[key] unset.
    96  	//
    97  	// An entry's associated value can be updated by atomic replacement, provided
    98  	// p != expunged. If p == expunged, an entry's associated value can be updated
    99  	// only after first setting m.dirty[key] = e so that lookups using the dirty
   100  	// map find the entry.
   101  	p atomic.Pointer[any]
   102  }
   103  
   104  func newEntry(i any) *entry {
   105  	e := &entry{}
   106  	e.p.Store(&i)
   107  	return e
   108  }
   109  
   110  func (m *Map) loadReadOnly() readOnly {
   111  	if p := m.read.Load(); p != nil {
   112  		return *p
   113  	}
   114  	return readOnly{}
   115  }
   116  
   117  // Load returns the value stored in the map for a key, or nil if no
   118  // value is present.
   119  // The ok result indicates whether value was found in the map.
   120  func (m *Map) Load(key any) (value any, ok bool) {
   121  	read := m.loadReadOnly()
   122  	e, ok := read.m[key]
   123  	if !ok && read.amended {
   124  		m.mu.Lock()
   125  		// Avoid reporting a spurious miss if m.dirty got promoted while we were
   126  		// blocked on m.mu. (If further loads of the same key will not miss, it's
   127  		// not worth copying the dirty map for this key.)
   128  		read = m.loadReadOnly()
   129  		e, ok = read.m[key]
   130  		if !ok && read.amended {
   131  			e, ok = m.dirty[key]
   132  			// Regardless of whether the entry was present, record a miss: this key
   133  			// will take the slow path until the dirty map is promoted to the read
   134  			// map.
   135  			m.missLocked()
   136  		}
   137  		m.mu.Unlock()
   138  	}
   139  	if !ok {
   140  		return nil, false
   141  	}
   142  	return e.load()
   143  }
   144  
   145  func (e *entry) load() (value any, ok bool) {
   146  	p := e.p.Load()
   147  	if p == nil || p == expunged {
   148  		return nil, false
   149  	}
   150  	return *p, true
   151  }
   152  
   153  // Store sets the value for a key.
   154  func (m *Map) Store(key, value any) {
   155  	_, _ = m.Swap(key, value)
   156  }
   157  
   158  // tryCompareAndSwap compare the entry with the given old value and swaps
   159  // it with a new value if the entry is equal to the old value, and the entry
   160  // has not been expunged.
   161  //
   162  // If the entry is expunged, tryCompareAndSwap returns false and leaves
   163  // the entry unchanged.
   164  func (e *entry) tryCompareAndSwap(old, new any) bool {
   165  	p := e.p.Load()
   166  	if p == nil || p == expunged || *p != old {
   167  		return false
   168  	}
   169  
   170  	// Copy the interface after the first load to make this method more amenable
   171  	// to escape analysis: if the comparison fails from the start, we shouldn't
   172  	// bother heap-allocating an interface value to store.
   173  	nc := new
   174  	for {
   175  		if e.p.CompareAndSwap(p, &nc) {
   176  			return true
   177  		}
   178  		p = e.p.Load()
   179  		if p == nil || p == expunged || *p != old {
   180  			return false
   181  		}
   182  	}
   183  }
   184  
   185  // unexpungeLocked ensures that the entry is not marked as expunged.
   186  //
   187  // If the entry was previously expunged, it must be added to the dirty map
   188  // before m.mu is unlocked.
   189  func (e *entry) unexpungeLocked() (wasExpunged bool) {
   190  	return e.p.CompareAndSwap(expunged, nil)
   191  }
   192  
   193  // swapLocked unconditionally swaps a value into the entry.
   194  //
   195  // The entry must be known not to be expunged.
   196  func (e *entry) swapLocked(i *any) *any {
   197  	return e.p.Swap(i)
   198  }
   199  
   200  // LoadOrStore returns the existing value for the key if present.
   201  // Otherwise, it stores and returns the given value.
   202  // The loaded result is true if the value was loaded, false if stored.
   203  func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) {
   204  	// Avoid locking if it's a clean hit.
   205  	read := m.loadReadOnly()
   206  	if e, ok := read.m[key]; ok {
   207  		actual, loaded, ok := e.tryLoadOrStore(value)
   208  		if ok {
   209  			return actual, loaded
   210  		}
   211  	}
   212  
   213  	m.mu.Lock()
   214  	read = m.loadReadOnly()
   215  	if e, ok := read.m[key]; ok {
   216  		if e.unexpungeLocked() {
   217  			m.dirty[key] = e
   218  		}
   219  		actual, loaded, _ = e.tryLoadOrStore(value)
   220  	} else if e, ok := m.dirty[key]; ok {
   221  		actual, loaded, _ = e.tryLoadOrStore(value)
   222  		m.missLocked()
   223  	} else {
   224  		if !read.amended {
   225  			// We're adding the first new key to the dirty map.
   226  			// Make sure it is allocated and mark the read-only map as incomplete.
   227  			m.dirtyLocked()
   228  			m.read.Store(&readOnly{m: read.m, amended: true})
   229  		}
   230  		m.dirty[key] = newEntry(value)
   231  		actual, loaded = value, false
   232  	}
   233  	m.mu.Unlock()
   234  
   235  	return actual, loaded
   236  }
   237  
   238  // tryLoadOrStore atomically loads or stores a value if the entry is not
   239  // expunged.
   240  //
   241  // If the entry is expunged, tryLoadOrStore leaves the entry unchanged and
   242  // returns with ok==false.
   243  func (e *entry) tryLoadOrStore(i any) (actual any, loaded, ok bool) {
   244  	p := e.p.Load()
   245  	if p == expunged {
   246  		return nil, false, false
   247  	}
   248  	if p != nil {
   249  		return *p, true, true
   250  	}
   251  
   252  	// Copy the interface after the first load to make this method more amenable
   253  	// to escape analysis: if we hit the "load" path or the entry is expunged, we
   254  	// shouldn't bother heap-allocating.
   255  	ic := i
   256  	for {
   257  		if e.p.CompareAndSwap(nil, &ic) {
   258  			return i, false, true
   259  		}
   260  		p = e.p.Load()
   261  		if p == expunged {
   262  			return nil, false, false
   263  		}
   264  		if p != nil {
   265  			return *p, true, true
   266  		}
   267  	}
   268  }
   269  
   270  // LoadAndDelete deletes the value for a key, returning the previous value if any.
   271  // The loaded result reports whether the key was present.
   272  func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
   273  	read := m.loadReadOnly()
   274  	e, ok := read.m[key]
   275  	if !ok && read.amended {
   276  		m.mu.Lock()
   277  		read = m.loadReadOnly()
   278  		e, ok = read.m[key]
   279  		if !ok && read.amended {
   280  			e, ok = m.dirty[key]
   281  			delete(m.dirty, key)
   282  			// Regardless of whether the entry was present, record a miss: this key
   283  			// will take the slow path until the dirty map is promoted to the read
   284  			// map.
   285  			m.missLocked()
   286  		}
   287  		m.mu.Unlock()
   288  	}
   289  	if ok {
   290  		return e.delete()
   291  	}
   292  	return nil, false
   293  }
   294  
   295  // Delete deletes the value for a key.
   296  func (m *Map) Delete(key any) {
   297  	m.LoadAndDelete(key)
   298  }
   299  
   300  func (e *entry) delete() (value any, ok bool) {
   301  	for {
   302  		p := e.p.Load()
   303  		if p == nil || p == expunged {
   304  			return nil, false
   305  		}
   306  		if e.p.CompareAndSwap(p, nil) {
   307  			return *p, true
   308  		}
   309  	}
   310  }
   311  
   312  // trySwap swaps a value if the entry has not been expunged.
   313  //
   314  // If the entry is expunged, trySwap returns false and leaves the entry
   315  // unchanged.
   316  func (e *entry) trySwap(i *any) (*any, bool) {
   317  	for {
   318  		p := e.p.Load()
   319  		if p == expunged {
   320  			return nil, false
   321  		}
   322  		if e.p.CompareAndSwap(p, i) {
   323  			return p, true
   324  		}
   325  	}
   326  }
   327  
   328  // Swap swaps the value for a key and returns the previous value if any.
   329  // The loaded result reports whether the key was present.
   330  func (m *Map) Swap(key, value any) (previous any, loaded bool) {
   331  	read := m.loadReadOnly()
   332  	if e, ok := read.m[key]; ok {
   333  		if v, ok := e.trySwap(&value); ok {
   334  			if v == nil {
   335  				return nil, false
   336  			}
   337  			return *v, true
   338  		}
   339  	}
   340  
   341  	m.mu.Lock()
   342  	read = m.loadReadOnly()
   343  	if e, ok := read.m[key]; ok {
   344  		if e.unexpungeLocked() {
   345  			// The entry was previously expunged, which implies that there is a
   346  			// non-nil dirty map and this entry is not in it.
   347  			m.dirty[key] = e
   348  		}
   349  		if v := e.swapLocked(&value); v != nil {
   350  			loaded = true
   351  			previous = *v
   352  		}
   353  	} else if e, ok := m.dirty[key]; ok {
   354  		if v := e.swapLocked(&value); v != nil {
   355  			loaded = true
   356  			previous = *v
   357  		}
   358  	} else {
   359  		if !read.amended {
   360  			// We're adding the first new key to the dirty map.
   361  			// Make sure it is allocated and mark the read-only map as incomplete.
   362  			m.dirtyLocked()
   363  			m.read.Store(&readOnly{m: read.m, amended: true})
   364  		}
   365  		m.dirty[key] = newEntry(value)
   366  	}
   367  	m.mu.Unlock()
   368  	return previous, loaded
   369  }
   370  
   371  // CompareAndSwap swaps the old and new values for key
   372  // if the value stored in the map is equal to old.
   373  // The old value must be of a comparable type.
   374  func (m *Map) CompareAndSwap(key, old, new any) bool {
   375  	read := m.loadReadOnly()
   376  	if e, ok := read.m[key]; ok {
   377  		return e.tryCompareAndSwap(old, new)
   378  	} else if !read.amended {
   379  		return false // No existing value for key.
   380  	}
   381  
   382  	m.mu.Lock()
   383  	defer m.mu.Unlock()
   384  	read = m.loadReadOnly()
   385  	swapped := false
   386  	if e, ok := read.m[key]; ok {
   387  		swapped = e.tryCompareAndSwap(old, new)
   388  	} else if e, ok := m.dirty[key]; ok {
   389  		swapped = e.tryCompareAndSwap(old, new)
   390  		// We needed to lock mu in order to load the entry for key,
   391  		// and the operation didn't change the set of keys in the map
   392  		// (so it would be made more efficient by promoting the dirty
   393  		// map to read-only).
   394  		// Count it as a miss so that we will eventually switch to the
   395  		// more efficient steady state.
   396  		m.missLocked()
   397  	}
   398  	return swapped
   399  }
   400  
   401  // CompareAndDelete deletes the entry for key if its value is equal to old.
   402  // The old value must be of a comparable type.
   403  //
   404  // If there is no current value for key in the map, CompareAndDelete
   405  // returns false (even if the old value is the nil interface value).
   406  func (m *Map) CompareAndDelete(key, old any) (deleted bool) {
   407  	read := m.loadReadOnly()
   408  	e, ok := read.m[key]
   409  	if !ok && read.amended {
   410  		m.mu.Lock()
   411  		read = m.loadReadOnly()
   412  		e, ok = read.m[key]
   413  		if !ok && read.amended {
   414  			e, ok = m.dirty[key]
   415  			// Don't delete key from m.dirty: we still need to do the “compare” part
   416  			// of the operation. The entry will eventually be expunged when the
   417  			// dirty map is promoted to the read map.
   418  			//
   419  			// Regardless of whether the entry was present, record a miss: this key
   420  			// will take the slow path until the dirty map is promoted to the read
   421  			// map.
   422  			m.missLocked()
   423  		}
   424  		m.mu.Unlock()
   425  	}
   426  	for ok {
   427  		p := e.p.Load()
   428  		if p == nil || p == expunged || *p != old {
   429  			return false
   430  		}
   431  		if e.p.CompareAndSwap(p, nil) {
   432  			return true
   433  		}
   434  	}
   435  	return false
   436  }
   437  
   438  // Range calls f sequentially for each key and value present in the map.
   439  // If f returns false, range stops the iteration.
   440  //
   441  // Range does not necessarily correspond to any consistent snapshot of the Map's
   442  // contents: no key will be visited more than once, but if the value for any key
   443  // is stored or deleted concurrently (including by f), Range may reflect any
   444  // mapping for that key from any point during the Range call. Range does not
   445  // block other methods on the receiver; even f itself may call any method on m.
   446  //
   447  // Range may be O(N) with the number of elements in the map even if f returns
   448  // false after a constant number of calls.
   449  func (m *Map) Range(f func(key, value any) bool) {
   450  	// We need to be able to iterate over all of the keys that were already
   451  	// present at the start of the call to Range.
   452  	// If read.amended is false, then read.m satisfies that property without
   453  	// requiring us to hold m.mu for a long time.
   454  	read := m.loadReadOnly()
   455  	if read.amended {
   456  		// m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
   457  		// (assuming the caller does not break out early), so a call to Range
   458  		// amortizes an entire copy of the map: we can promote the dirty copy
   459  		// immediately!
   460  		m.mu.Lock()
   461  		read = m.loadReadOnly()
   462  		if read.amended {
   463  			read = readOnly{m: m.dirty}
   464  			copyRead := read
   465  			m.read.Store(&copyRead)
   466  			m.dirty = nil
   467  			m.misses = 0
   468  		}
   469  		m.mu.Unlock()
   470  	}
   471  
   472  	for k, e := range read.m {
   473  		v, ok := e.load()
   474  		if !ok {
   475  			continue
   476  		}
   477  		if !f(k, v) {
   478  			break
   479  		}
   480  	}
   481  }
   482  
   483  func (m *Map) missLocked() {
   484  	m.misses++
   485  	if m.misses < len(m.dirty) {
   486  		return
   487  	}
   488  	m.read.Store(&readOnly{m: m.dirty})
   489  	m.dirty = nil
   490  	m.misses = 0
   491  }
   492  
   493  func (m *Map) dirtyLocked() {
   494  	if m.dirty != nil {
   495  		return
   496  	}
   497  
   498  	read := m.loadReadOnly()
   499  	m.dirty = make(map[any]*entry, len(read.m))
   500  	for k, e := range read.m {
   501  		if !e.tryExpungeLocked() {
   502  			m.dirty[k] = e
   503  		}
   504  	}
   505  }
   506  
   507  func (e *entry) tryExpungeLocked() (isExpunged bool) {
   508  	p := e.p.Load()
   509  	for p == nil {
   510  		if e.p.CompareAndSwap(nil, expunged) {
   511  			return true
   512  		}
   513  		p = e.p.Load()
   514  	}
   515  	return p == expunged
   516  }
   517  

View as plain text