12340184181

Committed 15 Dec 2024 03:49PM UTC coverage: 74.626% (+0.5%) from 74.114%

Build # 12340184181

Build Type

push

github

Committed by

smallnest

Commit Message

add Broadcaster

Run Details

7 of 7 new or added lines in 1 file covered. (100.0%)

18 existing lines in 2 files now uncovered.

2594 of 3476 relevant lines covered (74.63%)

3013519.66 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

31.88

/sync/sync_map.go

// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package sync

import (
        "sync"
        "sync/atomic"
        "unsafe"
)

// Map is like a Go map[interface{}]interface{} but is safe for concurrent use
// by multiple goroutines without additional locking or coordination.
// Loads, stores, and deletes run in amortized constant time.
//
// The Map type is specialized. Most code should use a plain Go map instead,
// with separate locking or coordination, for better type safety and to make it
// easier to maintain other invariants along with the map content.
//
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate Mutex or RWMutex.
//
// The zero Map is empty and ready for use. A Map must not be copied after first use.
//
// In the terminology of the Go memory model, Map arranges that a write operation
// “synchronizes before” any read operation that observes the effect of the write, where
// read and write operations are defined as follows.
// Load, LoadAndDelete, LoadOrStore, Swap, CompareAndSwap, and CompareAndDelete
// are read operations; Delete, LoadAndDelete, Store, and Swap are write operations;
// LoadOrStore is a write operation when it returns loaded set to false;
// CompareAndSwap is a write operation when it returns swapped set to true;
// and CompareAndDelete is a write operation when it returns deleted set to true.
type Map[K comparable, V any] struct {
        mu sync.Mutex

        // read contains the portion of the map's contents that are safe for
        // concurrent access (with or without mu held).
        //
        // The read field itself is always safe to load, but must only be stored with
        // mu held.
        //
        // Entries stored in read may be updated concurrently without mu, but updating
        // a previously-expunged entry requires that the entry be copied to the dirty
        // map and unexpunged with mu held.
        read atomic.Pointer[readOnly[K, V]]

        // dirty contains the portion of the map's contents that require mu to be
        // held. To ensure that the dirty map can be promoted to the read map quickly,
        // it also includes all of the non-expunged entries in the read map.
        //
        // Expunged entries are not stored in the dirty map. An expunged entry in the
        // clean map must be unexpunged and added to the dirty map before a new value
        // can be stored to it.
        //
        // If the dirty map is nil, the next write to the map will initialize it by
        // making a shallow copy of the clean map, omitting stale entries.
        dirty map[K]*entry[V]

        // misses counts the number of loads since the read map was last updated that
        // needed to lock mu to determine whether the key was present.
        //
        // Once enough misses have occurred to cover the cost of copying the dirty
        // map, the dirty map will be promoted to the read map (in the unamended
        // state) and the next store to the map will make a new dirty copy.
        misses int
}

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly[K comparable, V any] struct {
        m       map[K]*entry[V]
        amended bool // true if the dirty map contains some key not in m.
}

// expunged is an arbitrary pointer that marks entries which have been deleted
// from the dirty map.
var expunged = unsafe.Pointer(new(any))

// An entry is a slot in the map corresponding to a particular key.
type entry[V any] struct {
        // p points to the interface{} value stored for the entry.
        //
        // If p == nil, the entry has been deleted, and either m.dirty == nil or
        // m.dirty[key] is e.
        //
        // If unsafe.Pointer(p) == expunged, the entry has been deleted, m.dirty != nil, and the entry
        // is missing from m.dirty.
        //
        // Otherwise, the entry is valid and recorded in m.read.m[key] and, if m.dirty
        // != nil, in m.dirty[key].
        //
        // An entry can be deleted by atomic replacement with nil: when m.dirty is
        // next created, it will atomically replace nil with expunged and leave
        // m.dirty[key] unset.
        //
        // An entry's associated value can be updated by atomic replacement, provided
        // p != expunged. If unsafe.Pointer(p) == expunged, an entry's associated value can be updated
        // only after first setting m.dirty[key] = e so that lookups using the dirty
        // map find the entry.
        p atomic.Pointer[V]
}

func newEntry[V any](i V) *entry[V] {
        e := &entry[V]{}
        e.p.Store(&i)
        return e
}

func (m *Map[K, V]) loadReadOnly() readOnly[K, V] {
        if p := m.read.Load(); p != nil {
                return *p
        }
        return readOnly[K, V]{}
}

// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map[K, V]) Load(key K) (value V, ok bool) {
        read := m.loadReadOnly()
        e, ok := read.m[key]
        if !ok && read.amended {
                m.mu.Lock()
                // Avoid reporting a spurious miss if m.dirty got promoted while we were
                // blocked on m.mu. (If further loads of the same key will not miss, it's
                // not worth copying the dirty map for this key.)
                read = m.loadReadOnly()
                e, ok = read.m[key]
                if !ok && read.amended {
                        e, ok = m.dirty[key]
                        // Regardless of whether the entry was present, record a miss: this key
                        // will take the slow path until the dirty map is promoted to the read
                        // map.
                        m.missLocked()
                }
                m.mu.Unlock()
        }
        if !ok {
                var zero V
                return zero, false
        }
        return e.load()
}

func (e *entry[V]) load() (value V, ok bool) {
        p := e.p.Load()
        if p == nil || unsafe.Pointer(p) == expunged {
                var zero V
                return zero, false
        }
        return *p, true
}

// Store sets the value for a key.
func (m *Map[K, V]) Store(key K, value V) {
        _, _ = m.Swap(key, value)
}

// tryCompareAndSwap compare the entry with the given old value and swaps
// it with a new value if the entry is equal to the old value, and the entry
// has not been expunged.
//
// If the entry is expunged, tryCompareAndSwap returns false and leaves
// the entry unchanged.
func (e *entry[V]) tryCompareAndSwap(old, new V) bool {
        p := e.p.Load()
        if p == nil || unsafe.Pointer(p) == expunged {
                return false
        }

        // Copy the interface after the first load to make this method more amenable
        // to escape analysis: if the comparison fails from the start, we shouldn't
        // bother heap-allocating an interface value to store.
        nc := new
        for {
                if e.p.CompareAndSwap(p, &nc) {
                        return true
                }
                p = e.p.Load()
                if p == nil || unsafe.Pointer(p) == expunged {
                        return false
                }
        }
}

// unexpungeLocked ensures that the entry is not marked as expunged.
//
// If the entry was previously expunged, it must be added to the dirty map
// before m.mu is unlocked.
func (e *entry[V]) unexpungeLocked() (wasExpunged bool) {
        return e.p.CompareAndSwap((*V)(expunged), nil)
}

// swapLocked unconditionally swaps a value into the entry.
//
// The entry must be known not to be expunged.
func (e *entry[V]) swapLocked(i *V) *V {
        return e.p.Swap(i)
}

// LoadOrStore returns the existing value for the key if present.
// Otherwise, it stores and returns the given value.
// The loaded result is true if the value was loaded, false if stored.
func (m *Map[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) {
        // Avoid locking if it's a clean hit.
        read := m.loadReadOnly()
        if e, ok := read.m[key]; ok {
                actual, loaded, ok := e.tryLoadOrStore(value)
                if ok {
                        return actual, loaded
                }
        }

        m.mu.Lock()
        read = m.loadReadOnly()
        if e, ok := read.m[key]; ok {
                if e.unexpungeLocked() {
                        m.dirty[key] = e
                }
                actual, loaded, _ = e.tryLoadOrStore(value)
        } else if e, ok := m.dirty[key]; ok {
                actual, loaded, _ = e.tryLoadOrStore(value)
                m.missLocked()
        } else {
                if !read.amended {
                        // We're adding the first new key to the dirty map.
                        // Make sure it is allocated and mark the read-only map as incomplete.
                        m.dirtyLocked()
                        m.read.Store(&readOnly[K, V]{m: read.m, amended: true})
                }
                m.dirty[key] = newEntry(value)
                actual, loaded = value, false
        }
        m.mu.Unlock()

        return actual, loaded
}

// tryLoadOrStore atomically loads or stores a value if the entry is not
// expunged.
//
// If the entry is expunged, tryLoadOrStore leaves the entry unchanged and
// returns with ok==false.
func (e *entry[V]) tryLoadOrStore(i V) (actual V, loaded, ok bool) {
        p := e.p.Load()
        if unsafe.Pointer(p) == expunged {
                var zero V
                return zero, false, false
        }
        if p != nil {
                return *p, true, true
        }

        // Copy the interface after the first load to make this method more amenable
        // to escape analysis: if we hit the "load" path or the entry is expunged, we
        // shouldn't bother heap-allocating.
        ic := i
        for {
                if e.p.CompareAndSwap(nil, &ic) {
                        return i, false, true
                }
                p = e.p.Load()
                if unsafe.Pointer(p) == expunged {
                        var zero V
                        return zero, false, false
                }
                if p != nil {
                        return *p, true, true
                }
        }
}

// LoadAndDelete deletes the value for a key, returning the previous value if any.
// The loaded result reports whether the key was present.
func (m *Map[K, V]) LoadAndDelete(key K) (value V, loaded bool) {
        read := m.loadReadOnly()
        e, ok := read.m[key]
        if !ok && read.amended {
                m.mu.Lock()
                read = m.loadReadOnly()
                e, ok = read.m[key]
                if !ok && read.amended {
                        e, ok = m.dirty[key]
                        delete(m.dirty, key)
                        // Regardless of whether the entry was present, record a miss: this key
                        // will take the slow path until the dirty map is promoted to the read
                        // map.
                        m.missLocked()
                }
                m.mu.Unlock()
        }
        if ok {
                return e.delete()
        }

        var zero V
        return zero, false
}

// Delete deletes the value for a key.
func (m *Map[K, V]) Delete(key K) {
        m.LoadAndDelete(key)
}

func (e *entry[V]) delete() (value V, ok bool) {
        for {
                p := e.p.Load()
                if p == nil || unsafe.Pointer(p) == expunged {
                        var zero V
                        return zero, false
                }
                if e.p.CompareAndSwap(p, nil) {
                        return *p, true
                }
        }
}

// trySwap swaps a value if the entry has not been expunged.
//
// If the entry is expunged, trySwap returns false and leaves the entry
// unchanged.
func (e *entry[V]) trySwap(i *V) (*V, bool) {
        for {
                p := e.p.Load()
                if unsafe.Pointer(p) == expunged {
                        return nil, false
                }
                if e.p.CompareAndSwap(p, i) {
                        return p, true
                }
        }
}

// Swap swaps the value for a key and returns the previous value if any.
// The loaded result reports whether the key was present.
func (m *Map[K, V]) Swap(key K, value V) (previous V, loaded bool) {
        read := m.loadReadOnly()
        if e, ok := read.m[key]; ok {
                if v, ok := e.trySwap(&value); ok {
                        if v == nil {
                                var zero V
                                return zero, false
                        }
                        return *v, true
                }
        }

        m.mu.Lock()
        read = m.loadReadOnly()
        if e, ok := read.m[key]; ok {
                if e.unexpungeLocked() {
                        // The entry was previously expunged, which implies that there is a
                        // non-nil dirty map and this entry is not in it.
                        m.dirty[key] = e
                }
                if v := e.swapLocked(&value); v != nil {
                        loaded = true
                        previous = *v
                }
        } else if e, ok := m.dirty[key]; ok {
                if v := e.swapLocked(&value); v != nil {
                        loaded = true
                        previous = *v
                }
        } else {
                if !read.amended {
                        // We're adding the first new key to the dirty map.
                        // Make sure it is allocated and mark the read-only map as incomplete.
                        m.dirtyLocked()
                        m.read.Store(&readOnly[K, V]{m: read.m, amended: true})
                }
                m.dirty[key] = newEntry(value)
        }
        m.mu.Unlock()
        return previous, loaded
}

// CompareAndSwap swaps the old and new values for key
// if the value stored in the map is equal to old.
// The old value must be of a comparable type.
func (m *Map[K, V]) CompareAndSwap(key K, old, new V) bool {
        read := m.loadReadOnly()
        if e, ok := read.m[key]; ok {
                return e.tryCompareAndSwap(old, new)
        } else if !read.amended {
                return false // No existing value for key.
        }

        m.mu.Lock()
        defer m.mu.Unlock()
        read = m.loadReadOnly()
        swapped := false
        if e, ok := read.m[key]; ok {
                swapped = e.tryCompareAndSwap(old, new)
        } else if e, ok := m.dirty[key]; ok {
                swapped = e.tryCompareAndSwap(old, new)
                // We needed to lock mu in order to load the entry for key,
                // and the operation didn't change the set of keys in the map
                // (so it would be made more efficient by promoting the dirty
                // map to read-only).
                // Count it as a miss so that we will eventually switch to the
                // more efficient steady state.
                m.missLocked()
        }
        return swapped
}

// CompareAndDelete deletes the entry for key if its value is equal to old.
// The old value must be of a comparable type.
//
// If there is no current value for key in the map, CompareAndDelete
// returns false (even if the old value is the nil interface value).
func (m *Map[K, V]) CompareAndDelete(key K, old V) (deleted bool) {
        read := m.loadReadOnly()
        e, ok := read.m[key]
        if !ok && read.amended {
                m.mu.Lock()
                read = m.loadReadOnly()
                e, ok = read.m[key]
                if !ok && read.amended {
                        e, ok = m.dirty[key]
                        // Don't delete key from m.dirty: we still need to do the “compare” part
                        // of the operation. The entry will eventually be expunged when the
                        // dirty map is promoted to the read map.
                        //
                        // Regardless of whether the entry was present, record a miss: this key
                        // will take the slow path until the dirty map is promoted to the read
                        // map.
                        m.missLocked()
                }
                m.mu.Unlock()
        }
        for ok {
                p := e.p.Load()
                if p == nil || unsafe.Pointer(p) == expunged {
                        return false
                }
                if e.p.CompareAndSwap(p, nil) {
                        return true
                }
        }
        return false
}

// Range calls f sequentially for each key and value present in the map.
// If f returns false, range stops the iteration.
//
// Range does not necessarily correspond to any consistent snapshot of the Map's
// contents: no key will be visited more than once, but if the value for any key
// is stored or deleted concurrently (including by f), Range may reflect any
// mapping for that key from any point during the Range call. Range does not
// block other methods on the receiver; even f itself may call any method on m.
//
// Range may be O(N) with the number of elements in the map even if f returns
// false after a constant number of calls.
func (m *Map[K, V]) Range(f func(key K, value V) bool) {
        // We need to be able to iterate over all of the keys that were already
        // present at the start of the call to Range.
        // If read.amended is false, then read.m satisfies that property without
        // requiring us to hold m.mu for a long time.
        read := m.loadReadOnly()
        if read.amended {
                // m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
                // (assuming the caller does not break out early), so a call to Range
                // amortizes an entire copy of the map: we can promote the dirty copy
                // immediately!
                m.mu.Lock()
                read = m.loadReadOnly()
                if read.amended {
                        read = readOnly[K, V]{m: m.dirty}
                        m.read.Store(&read)
                        m.dirty = nil
                        m.misses = 0
                }
                m.mu.Unlock()
        }

        for k, e := range read.m {
                v, ok := e.load()
                if !ok {
                        continue
                }
                if !f(k, v) {
                        break
                }
        }
}

func (m *Map[K, V]) missLocked() {
        m.misses++
        if m.misses < len(m.dirty) {
                return
        }
        m.read.Store(&readOnly[K, V]{m: m.dirty})
        m.dirty = nil
        m.misses = 0
}

func (m *Map[K, V]) dirtyLocked() {
        if m.dirty != nil {
                return
        }

        read := m.loadReadOnly()
        m.dirty = make(map[K]*entry[V], len(read.m))
        for k, e := range read.m {
                if !e.tryExpungeLocked() {
                        m.dirty[k] = e
                }
        }
}

func (e *entry[V]) tryExpungeLocked() (isExpunged bool) {
        p := e.p.Load()
        for p == nil {
                if e.p.CompareAndSwap(nil, (*V)(expunged)) {
                        return true
                }
                p = e.p.Load()
        }
        return unsafe.Pointer(p) == expunged
}

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

smallnest / exp / 12340184181

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous