map_test.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_test
     6  
     7  import (
     8  	isync "internal/sync"
     9  	"internal/testenv"
    10  	"math/rand"
    11  	"reflect"
    12  	"runtime"
    13  	"sync"
    14  	"sync/atomic"
    15  	"testing"
    16  	"testing/quick"
    17  )
    18  
    19  type mapOp string
    20  
    21  const (
    22  	opLoad             = mapOp("Load")
    23  	opStore            = mapOp("Store")
    24  	opLoadOrStore      = mapOp("LoadOrStore")
    25  	opLoadAndDelete    = mapOp("LoadAndDelete")
    26  	opDelete           = mapOp("Delete")
    27  	opSwap             = mapOp("Swap")
    28  	opCompareAndSwap   = mapOp("CompareAndSwap")
    29  	opCompareAndDelete = mapOp("CompareAndDelete")
    30  	opClear            = mapOp("Clear")
    31  )
    32  
    33  var mapOps = [...]mapOp{
    34  	opLoad,
    35  	opStore,
    36  	opLoadOrStore,
    37  	opLoadAndDelete,
    38  	opDelete,
    39  	opSwap,
    40  	opCompareAndSwap,
    41  	opCompareAndDelete,
    42  	opClear,
    43  }
    44  
    45  // mapCall is a quick.Generator for calls on mapInterface.
    46  type mapCall struct {
    47  	op   mapOp
    48  	k, v any
    49  }
    50  
    51  func (c mapCall) apply(m mapInterface) (any, bool) {
    52  	switch c.op {
    53  	case opLoad:
    54  		return m.Load(c.k)
    55  	case opStore:
    56  		m.Store(c.k, c.v)
    57  		return nil, false
    58  	case opLoadOrStore:
    59  		return m.LoadOrStore(c.k, c.v)
    60  	case opLoadAndDelete:
    61  		return m.LoadAndDelete(c.k)
    62  	case opDelete:
    63  		m.Delete(c.k)
    64  		return nil, false
    65  	case opSwap:
    66  		return m.Swap(c.k, c.v)
    67  	case opCompareAndSwap:
    68  		if m.CompareAndSwap(c.k, c.v, rand.Int()) {
    69  			m.Delete(c.k)
    70  			return c.v, true
    71  		}
    72  		return nil, false
    73  	case opCompareAndDelete:
    74  		if m.CompareAndDelete(c.k, c.v) {
    75  			if _, ok := m.Load(c.k); !ok {
    76  				return nil, true
    77  			}
    78  		}
    79  		return nil, false
    80  	case opClear:
    81  		m.Clear()
    82  		return nil, false
    83  	default:
    84  		panic("invalid mapOp")
    85  	}
    86  }
    87  
    88  type mapResult struct {
    89  	value any
    90  	ok    bool
    91  }
    92  
    93  func randValue(r *rand.Rand) any {
    94  	b := make([]byte, r.Intn(4))
    95  	for i := range b {
    96  		b[i] = 'a' + byte(rand.Intn(26))
    97  	}
    98  	return string(b)
    99  }
   100  
   101  func (mapCall) Generate(r *rand.Rand, size int) reflect.Value {
   102  	c := mapCall{op: mapOps[rand.Intn(len(mapOps))], k: randValue(r)}
   103  	switch c.op {
   104  	case opStore, opLoadOrStore:
   105  		c.v = randValue(r)
   106  	}
   107  	return reflect.ValueOf(c)
   108  }
   109  
   110  func applyCalls(m mapInterface, calls []mapCall) (results []mapResult, final map[any]any) {
   111  	for _, c := range calls {
   112  		v, ok := c.apply(m)
   113  		results = append(results, mapResult{v, ok})
   114  	}
   115  
   116  	final = make(map[any]any)
   117  	m.Range(func(k, v any) bool {
   118  		final[k] = v
   119  		return true
   120  	})
   121  
   122  	return results, final
   123  }
   124  
   125  func applyMap(calls []mapCall) ([]mapResult, map[any]any) {
   126  	return applyCalls(new(sync.Map), calls)
   127  }
   128  
   129  func applyRWMutexMap(calls []mapCall) ([]mapResult, map[any]any) {
   130  	return applyCalls(new(RWMutexMap), calls)
   131  }
   132  
   133  func applyDeepCopyMap(calls []mapCall) ([]mapResult, map[any]any) {
   134  	return applyCalls(new(DeepCopyMap), calls)
   135  }
   136  
   137  func applyHashTrieMap(calls []mapCall) ([]mapResult, map[any]any) {
   138  	return applyCalls(new(isync.HashTrieMap[any, any]), calls)
   139  }
   140  
   141  func TestMapMatchesRWMutex(t *testing.T) {
   142  	if err := quick.CheckEqual(applyMap, applyRWMutexMap, nil); err != nil {
   143  		t.Error(err)
   144  	}
   145  }
   146  
   147  func TestMapMatchesDeepCopy(t *testing.T) {
   148  	if err := quick.CheckEqual(applyMap, applyDeepCopyMap, nil); err != nil {
   149  		t.Error(err)
   150  	}
   151  }
   152  
   153  func TestMapMatchesHashTrieMap(t *testing.T) {
   154  	if err := quick.CheckEqual(applyMap, applyHashTrieMap, nil); err != nil {
   155  		t.Error(err)
   156  	}
   157  }
   158  
   159  func TestConcurrentRange(t *testing.T) {
   160  	const mapSize = 1 << 10
   161  
   162  	m := new(sync.Map)
   163  	for n := int64(1); n <= mapSize; n++ {
   164  		m.Store(n, int64(n))
   165  	}
   166  
   167  	done := make(chan struct{})
   168  	var wg sync.WaitGroup
   169  	defer func() {
   170  		close(done)
   171  		wg.Wait()
   172  	}()
   173  	for g := int64(runtime.GOMAXPROCS(0)); g > 0; g-- {
   174  		r := rand.New(rand.NewSource(g))
   175  		wg.Add(1)
   176  		go func(g int64) {
   177  			defer wg.Done()
   178  			for i := int64(0); ; i++ {
   179  				select {
   180  				case <-done:
   181  					return
   182  				default:
   183  				}
   184  				for n := int64(1); n < mapSize; n++ {
   185  					if r.Int63n(mapSize) == 0 {
   186  						m.Store(n, n*i*g)
   187  					} else {
   188  						m.Load(n)
   189  					}
   190  				}
   191  			}
   192  		}(g)
   193  	}
   194  
   195  	iters := 1 << 10
   196  	if testing.Short() {
   197  		iters = 16
   198  	}
   199  	for n := iters; n > 0; n-- {
   200  		seen := make(map[int64]bool, mapSize)
   201  
   202  		m.Range(func(ki, vi any) bool {
   203  			k, v := ki.(int64), vi.(int64)
   204  			if v%k != 0 {
   205  				t.Fatalf("while Storing multiples of %v, Range saw value %v", k, v)
   206  			}
   207  			if seen[k] {
   208  				t.Fatalf("Range visited key %v twice", k)
   209  			}
   210  			seen[k] = true
   211  			return true
   212  		})
   213  
   214  		if len(seen) != mapSize {
   215  			t.Fatalf("Range visited %v elements of %v-element Map", len(seen), mapSize)
   216  		}
   217  	}
   218  }
   219  
   220  func TestIssue40999(t *testing.T) {
   221  	var m sync.Map
   222  
   223  	// Since the miss-counting in missLocked (via Delete)
   224  	// compares the miss count with len(m.dirty),
   225  	// add an initial entry to bias len(m.dirty) above the miss count.
   226  	m.Store(nil, struct{}{})
   227  
   228  	var finalized uint32
   229  
   230  	// Set finalizers that count for collected keys. A non-zero count
   231  	// indicates that keys have not been leaked.
   232  	for atomic.LoadUint32(&finalized) == 0 {
   233  		p := new(int)
   234  		runtime.SetFinalizer(p, func(*int) {
   235  			atomic.AddUint32(&finalized, 1)
   236  		})
   237  		m.Store(p, struct{}{})
   238  		m.Delete(p)
   239  		runtime.GC()
   240  	}
   241  }
   242  
   243  func TestMapRangeNestedCall(t *testing.T) { // Issue 46399
   244  	var m sync.Map
   245  	for i, v := range [3]string{"hello", "world", "Go"} {
   246  		m.Store(i, v)
   247  	}
   248  	m.Range(func(key, value any) bool {
   249  		m.Range(func(key, value any) bool {
   250  			// We should be able to load the key offered in the Range callback,
   251  			// because there are no concurrent Delete involved in this tested map.
   252  			if v, ok := m.Load(key); !ok || !reflect.DeepEqual(v, value) {
   253  				t.Fatalf("Nested Range loads unexpected value, got %+v want %+v", v, value)
   254  			}
   255  
   256  			// We didn't keep 42 and a value into the map before, if somehow we loaded
   257  			// a value from such a key, meaning there must be an internal bug regarding
   258  			// nested range in the Map.
   259  			if _, loaded := m.LoadOrStore(42, "dummy"); loaded {
   260  				t.Fatalf("Nested Range loads unexpected value, want store a new value")
   261  			}
   262  
   263  			// Try to Store then LoadAndDelete the corresponding value with the key
   264  			// 42 to the Map. In this case, the key 42 and associated value should be
   265  			// removed from the Map. Therefore any future range won't observe key 42
   266  			// as we checked in above.
   267  			val := "sync.Map"
   268  			m.Store(42, val)
   269  			if v, loaded := m.LoadAndDelete(42); !loaded || !reflect.DeepEqual(v, val) {
   270  				t.Fatalf("Nested Range loads unexpected value, got %v, want %v", v, val)
   271  			}
   272  			return true
   273  		})
   274  
   275  		// Remove key from Map on-the-fly.
   276  		m.Delete(key)
   277  		return true
   278  	})
   279  
   280  	// After a Range of Delete, all keys should be removed and any
   281  	// further Range won't invoke the callback. Hence length remains 0.
   282  	length := 0
   283  	m.Range(func(key, value any) bool {
   284  		length++
   285  		return true
   286  	})
   287  
   288  	if length != 0 {
   289  		t.Fatalf("Unexpected sync.Map size, got %v want %v", length, 0)
   290  	}
   291  }
   292  
   293  func TestCompareAndSwap_NonExistingKey(t *testing.T) {
   294  	m := &sync.Map{}
   295  	if m.CompareAndSwap(m, nil, 42) {
   296  		// See https://go.dev/issue/51972#issuecomment-1126408637.
   297  		t.Fatalf("CompareAndSwap on a non-existing key succeeded")
   298  	}
   299  }
   300  
   301  func TestMapRangeNoAllocations(t *testing.T) { // Issue 62404
   302  	testenv.SkipIfOptimizationOff(t)
   303  	var m sync.Map
   304  	allocs := testing.AllocsPerRun(10, func() {
   305  		m.Range(func(key, value any) bool {
   306  			return true
   307  		})
   308  	})
   309  	if allocs > 0 {
   310  		t.Errorf("AllocsPerRun of m.Range = %v; want 0", allocs)
   311  	}
   312  }
   313  
   314  // TestConcurrentClear tests concurrent behavior of sync.Map properties to ensure no data races.
   315  // Checks for proper synchronization between Clear, Store, Load operations.
   316  func TestConcurrentClear(t *testing.T) {
   317  	var m sync.Map
   318  
   319  	wg := sync.WaitGroup{}
   320  	wg.Add(30) // 10 goroutines for writing, 10 goroutines for reading, 10 goroutines for waiting
   321  
   322  	// Writing data to the map concurrently
   323  	for i := 0; i < 10; i++ {
   324  		go func(k, v int) {
   325  			defer wg.Done()
   326  			m.Store(k, v)
   327  		}(i, i*10)
   328  	}
   329  
   330  	// Reading data from the map concurrently
   331  	for i := 0; i < 10; i++ {
   332  		go func(k int) {
   333  			defer wg.Done()
   334  			if value, ok := m.Load(k); ok {
   335  				t.Logf("Key: %v, Value: %v\n", k, value)
   336  			} else {
   337  				t.Logf("Key: %v not found\n", k)
   338  			}
   339  		}(i)
   340  	}
   341  
   342  	// Clearing data from the map concurrently
   343  	for i := 0; i < 10; i++ {
   344  		go func() {
   345  			defer wg.Done()
   346  			m.Clear()
   347  		}()
   348  	}
   349  
   350  	wg.Wait()
   351  
   352  	m.Clear()
   353  
   354  	m.Range(func(k, v any) bool {
   355  		t.Errorf("after Clear, Map contains (%v, %v); expected to be empty", k, v)
   356  
   357  		return true
   358  	})
   359  }
   360  
   361  func TestMapClearOneAllocation(t *testing.T) {
   362  	testenv.SkipIfOptimizationOff(t)
   363  	var m sync.Map
   364  	allocs := testing.AllocsPerRun(10, func() {
   365  		m.Clear()
   366  	})
   367  	if allocs > 1 {
   368  		t.Errorf("AllocsPerRun of m.Clear = %v; want 1", allocs)
   369  	}
   370  }
   371
View as plain text