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

View as plain text