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