map_test.go

     1  // Copyright 2024 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 maps_test
     6  
     7  import (
     8  	"fmt"
     9  	"internal/abi"
    10  	"internal/runtime/maps"
    11  	"math"
    12  	"testing"
    13  	"unsafe"
    14  )
    15  
    16  func TestCtrlSize(t *testing.T) {
    17  	cs := unsafe.Sizeof(maps.CtrlGroup(0))
    18  	if cs != abi.SwissMapGroupSlots {
    19  		t.Errorf("ctrlGroup size got %d want abi.SwissMapGroupSlots %d", cs, abi.SwissMapGroupSlots)
    20  	}
    21  }
    22  
    23  func TestMapPut(t *testing.T) {
    24  	m, typ := maps.NewTestMap[uint32, uint64](8)
    25  
    26  	key := uint32(0)
    27  	elem := uint64(256 + 0)
    28  
    29  	for i := 0; i < 31; i++ {
    30  		key += 1
    31  		elem += 1
    32  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
    33  
    34  		if maps.DebugLog {
    35  			fmt.Printf("After put %d: %v\n", key, m)
    36  		}
    37  	}
    38  
    39  	if m.Used() != 31 {
    40  		t.Errorf("Used() used got %d want 31", m.Used())
    41  	}
    42  
    43  	key = uint32(0)
    44  	elem = uint64(256 + 0)
    45  
    46  	for i := 0; i < 31; i++ {
    47  		key += 1
    48  		elem += 1
    49  		got, ok := m.Get(typ, unsafe.Pointer(&key))
    50  		if !ok {
    51  			t.Errorf("Get(%d) got ok false want true", key)
    52  		}
    53  		gotElem := *(*uint64)(got)
    54  		if gotElem != elem {
    55  			t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
    56  		}
    57  	}
    58  }
    59  
    60  // Grow enough to cause a table split.
    61  func TestMapSplit(t *testing.T) {
    62  	m, typ := maps.NewTestMap[uint32, uint64](0)
    63  
    64  	key := uint32(0)
    65  	elem := uint64(256 + 0)
    66  
    67  	for i := 0; i < 2*maps.MaxTableCapacity; i++ {
    68  		key += 1
    69  		elem += 1
    70  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
    71  
    72  		if maps.DebugLog {
    73  			fmt.Printf("After put %d: %v\n", key, m)
    74  		}
    75  	}
    76  
    77  	if m.Used() != 2*maps.MaxTableCapacity {
    78  		t.Errorf("Used() used got %d want 31", m.Used())
    79  	}
    80  
    81  	key = uint32(0)
    82  	elem = uint64(256 + 0)
    83  
    84  	for i := 0; i < 2*maps.MaxTableCapacity; i++ {
    85  		key += 1
    86  		elem += 1
    87  		got, ok := m.Get(typ, unsafe.Pointer(&key))
    88  		if !ok {
    89  			t.Errorf("Get(%d) got ok false want true", key)
    90  		}
    91  		gotElem := *(*uint64)(got)
    92  		if gotElem != elem {
    93  			t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
    94  		}
    95  	}
    96  }
    97  
    98  func TestMapDelete(t *testing.T) {
    99  	m, typ := maps.NewTestMap[uint32, uint64](32)
   100  
   101  	key := uint32(0)
   102  	elem := uint64(256 + 0)
   103  
   104  	for i := 0; i < 31; i++ {
   105  		key += 1
   106  		elem += 1
   107  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   108  
   109  		if maps.DebugLog {
   110  			fmt.Printf("After put %d: %v\n", key, m)
   111  		}
   112  	}
   113  
   114  	key = uint32(0)
   115  	elem = uint64(256 + 0)
   116  
   117  	for i := 0; i < 31; i++ {
   118  		key += 1
   119  		m.Delete(typ, unsafe.Pointer(&key))
   120  	}
   121  
   122  	if m.Used() != 0 {
   123  		t.Errorf("Used() used got %d want 0", m.Used())
   124  	}
   125  
   126  	key = uint32(0)
   127  	elem = uint64(256 + 0)
   128  
   129  	for i := 0; i < 31; i++ {
   130  		key += 1
   131  		elem += 1
   132  		_, ok := m.Get(typ, unsafe.Pointer(&key))
   133  		if ok {
   134  			t.Errorf("Get(%d) got ok true want false", key)
   135  		}
   136  	}
   137  }
   138  
   139  func TestTableClear(t *testing.T) {
   140  	m, typ := maps.NewTestMap[uint32, uint64](32)
   141  
   142  	key := uint32(0)
   143  	elem := uint64(256 + 0)
   144  
   145  	for i := 0; i < 31; i++ {
   146  		key += 1
   147  		elem += 1
   148  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   149  
   150  		if maps.DebugLog {
   151  			fmt.Printf("After put %d: %v\n", key, m)
   152  		}
   153  	}
   154  
   155  	m.Clear(typ)
   156  
   157  	if m.Used() != 0 {
   158  		t.Errorf("Clear() used got %d want 0", m.Used())
   159  	}
   160  
   161  	key = uint32(0)
   162  	elem = uint64(256 + 0)
   163  
   164  	for i := 0; i < 31; i++ {
   165  		key += 1
   166  		elem += 1
   167  		_, ok := m.Get(typ, unsafe.Pointer(&key))
   168  		if ok {
   169  			t.Errorf("Get(%d) got ok true want false", key)
   170  		}
   171  	}
   172  }
   173  
   174  // +0.0 and -0.0 compare equal, but we must still must update the key slot when
   175  // overwriting.
   176  func TestTableKeyUpdate(t *testing.T) {
   177  	m, typ := maps.NewTestMap[float64, uint64](8)
   178  
   179  	zero := float64(0.0)
   180  	negZero := math.Copysign(zero, -1.0)
   181  	elem := uint64(0)
   182  
   183  	m.Put(typ, unsafe.Pointer(&zero), unsafe.Pointer(&elem))
   184  	if maps.DebugLog {
   185  		fmt.Printf("After put %f: %v\n", zero, m)
   186  	}
   187  
   188  	elem = 1
   189  	m.Put(typ, unsafe.Pointer(&negZero), unsafe.Pointer(&elem))
   190  	if maps.DebugLog {
   191  		fmt.Printf("After put %f: %v\n", negZero, m)
   192  	}
   193  
   194  	if m.Used() != 1 {
   195  		t.Errorf("Used() used got %d want 1", m.Used())
   196  	}
   197  
   198  	it := new(maps.Iter)
   199  	it.Init(typ, m)
   200  	it.Next()
   201  	keyPtr, elemPtr := it.Key(), it.Elem()
   202  	if keyPtr == nil {
   203  		t.Fatal("it.Key() got nil want key")
   204  	}
   205  
   206  	key := *(*float64)(keyPtr)
   207  	elem = *(*uint64)(elemPtr)
   208  	if math.Copysign(1.0, key) > 0 {
   209  		t.Errorf("map key %f has positive sign", key)
   210  	}
   211  	if elem != 1 {
   212  		t.Errorf("map elem got %d want 1", elem)
   213  	}
   214  }
   215  
   216  // Put should reuse a deleted slot rather than consuming an empty slot.
   217  func TestTablePutDelete(t *testing.T) {
   218  	// Put will reuse the first deleted slot it encounters.
   219  	//
   220  	// This is awkward to test because Delete will only install ctrlDeleted
   221  	// if the group is full, otherwise it goes straight to empty.
   222  	//
   223  	// So first we must add to the table continuously until we happen to
   224  	// fill a group.
   225  
   226  	// Avoid small maps, they have no tables.
   227  	m, typ := maps.NewTestMap[uint32, uint32](16)
   228  
   229  	key := uint32(0)
   230  	elem := uint32(256 + 0)
   231  
   232  	for {
   233  		key += 1
   234  		elem += 1
   235  
   236  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   237  
   238  		// Normally a Put that fills a group would fill it with the
   239  		// inserted key, so why search the whole map for a potentially
   240  		// different key in a full group?
   241  		//
   242  		// Put may grow/split a table. Initial construction of the new
   243  		// table(s) could result in a full group consisting of
   244  		// arbitrary keys.
   245  		fullKeyPtr := m.KeyFromFullGroup(typ)
   246  		if fullKeyPtr != nil {
   247  			// Found a full group.
   248  			key = *(*uint32)(fullKeyPtr)
   249  			elem = 256 + key
   250  			break
   251  		}
   252  	}
   253  
   254  	// Key is in a full group. Deleting it will result in a ctrlDeleted
   255  	// slot.
   256  	m.Delete(typ, unsafe.Pointer(&key))
   257  
   258  	// Re-insert key. This should reuse the deleted slot rather than
   259  	// consuming space.
   260  	tabWant := m.TableFor(typ, unsafe.Pointer(&key))
   261  	growthLeftWant := tabWant.GrowthLeft()
   262  
   263  	m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   264  
   265  	tabGot := m.TableFor(typ, unsafe.Pointer(&key))
   266  	growthLeftGot := tabGot.GrowthLeft()
   267  
   268  	if tabGot != tabWant {
   269  		// There shouldn't be a grow, as replacing a deleted slot
   270  		// doesn't require more space.
   271  		t.Errorf("Put(%d) grew table got %v want %v map %v", key, tabGot, tabWant, m)
   272  	}
   273  
   274  	if growthLeftGot != growthLeftWant {
   275  		t.Errorf("GrowthLeft got %d want %d: map %v tab %v", growthLeftGot, growthLeftWant, m, tabGot)
   276  	}
   277  }
   278  
   279  func TestTableIteration(t *testing.T) {
   280  	m, typ := maps.NewTestMap[uint32, uint64](8)
   281  
   282  	key := uint32(0)
   283  	elem := uint64(256 + 0)
   284  
   285  	for i := 0; i < 31; i++ {
   286  		key += 1
   287  		elem += 1
   288  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   289  
   290  		if maps.DebugLog {
   291  			fmt.Printf("After put %d: %v\n", key, m)
   292  		}
   293  	}
   294  
   295  	got := make(map[uint32]uint64)
   296  
   297  	it := new(maps.Iter)
   298  	it.Init(typ, m)
   299  	for {
   300  		it.Next()
   301  		keyPtr, elemPtr := it.Key(), it.Elem()
   302  		if keyPtr == nil {
   303  			break
   304  		}
   305  
   306  		key := *(*uint32)(keyPtr)
   307  		elem := *(*uint64)(elemPtr)
   308  		got[key] = elem
   309  	}
   310  
   311  	if len(got) != 31 {
   312  		t.Errorf("Iteration got %d entries, want 31: %+v", len(got), got)
   313  	}
   314  
   315  	key = uint32(0)
   316  	elem = uint64(256 + 0)
   317  
   318  	for i := 0; i < 31; i++ {
   319  		key += 1
   320  		elem += 1
   321  		gotElem, ok := got[key]
   322  		if !ok {
   323  			t.Errorf("Iteration missing key %d", key)
   324  			continue
   325  		}
   326  		if gotElem != elem {
   327  			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
   328  		}
   329  	}
   330  }
   331  
   332  // Deleted keys shouldn't be visible in iteration.
   333  func TestTableIterationDelete(t *testing.T) {
   334  	m, typ := maps.NewTestMap[uint32, uint64](8)
   335  
   336  	key := uint32(0)
   337  	elem := uint64(256 + 0)
   338  
   339  	for i := 0; i < 31; i++ {
   340  		key += 1
   341  		elem += 1
   342  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   343  
   344  		if maps.DebugLog {
   345  			fmt.Printf("After put %d: %v\n", key, m)
   346  		}
   347  	}
   348  
   349  	got := make(map[uint32]uint64)
   350  	first := true
   351  	deletedKey := uint32(1)
   352  	it := new(maps.Iter)
   353  	it.Init(typ, m)
   354  	for {
   355  		it.Next()
   356  		keyPtr, elemPtr := it.Key(), it.Elem()
   357  		if keyPtr == nil {
   358  			break
   359  		}
   360  
   361  		key := *(*uint32)(keyPtr)
   362  		elem := *(*uint64)(elemPtr)
   363  		got[key] = elem
   364  
   365  		if first {
   366  			first = false
   367  
   368  			// If the key we intended to delete was the one we just
   369  			// saw, pick another to delete.
   370  			if key == deletedKey {
   371  				deletedKey++
   372  			}
   373  			m.Delete(typ, unsafe.Pointer(&deletedKey))
   374  		}
   375  	}
   376  
   377  	if len(got) != 30 {
   378  		t.Errorf("Iteration got %d entries, want 30: %+v", len(got), got)
   379  	}
   380  
   381  	key = uint32(0)
   382  	elem = uint64(256 + 0)
   383  
   384  	for i := 0; i < 31; i++ {
   385  		key += 1
   386  		elem += 1
   387  
   388  		wantOK := true
   389  		if key == deletedKey {
   390  			wantOK = false
   391  		}
   392  
   393  		gotElem, gotOK := got[key]
   394  		if gotOK != wantOK {
   395  			t.Errorf("Iteration key %d got ok %v want ok %v", key, gotOK, wantOK)
   396  			continue
   397  		}
   398  		if wantOK && gotElem != elem {
   399  			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
   400  		}
   401  	}
   402  }
   403  
   404  // Deleted keys shouldn't be visible in iteration even after a grow.
   405  func TestTableIterationGrowDelete(t *testing.T) {
   406  	m, typ := maps.NewTestMap[uint32, uint64](8)
   407  
   408  	key := uint32(0)
   409  	elem := uint64(256 + 0)
   410  
   411  	for i := 0; i < 31; i++ {
   412  		key += 1
   413  		elem += 1
   414  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   415  
   416  		if maps.DebugLog {
   417  			fmt.Printf("After put %d: %v\n", key, m)
   418  		}
   419  	}
   420  
   421  	got := make(map[uint32]uint64)
   422  	first := true
   423  	deletedKey := uint32(1)
   424  	it := new(maps.Iter)
   425  	it.Init(typ, m)
   426  	for {
   427  		it.Next()
   428  		keyPtr, elemPtr := it.Key(), it.Elem()
   429  		if keyPtr == nil {
   430  			break
   431  		}
   432  
   433  		key := *(*uint32)(keyPtr)
   434  		elem := *(*uint64)(elemPtr)
   435  		got[key] = elem
   436  
   437  		if first {
   438  			first = false
   439  
   440  			// If the key we intended to delete was the one we just
   441  			// saw, pick another to delete.
   442  			if key == deletedKey {
   443  				deletedKey++
   444  			}
   445  
   446  			// Double the number of elements to force a grow.
   447  			key := uint32(32)
   448  			elem := uint64(256 + 32)
   449  
   450  			for i := 0; i < 31; i++ {
   451  				key += 1
   452  				elem += 1
   453  				m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   454  
   455  				if maps.DebugLog {
   456  					fmt.Printf("After put %d: %v\n", key, m)
   457  				}
   458  			}
   459  
   460  			// Then delete from the grown map.
   461  			m.Delete(typ, unsafe.Pointer(&deletedKey))
   462  		}
   463  	}
   464  
   465  	// Don't check length: the number of new elements we'll see is
   466  	// unspecified.
   467  
   468  	// Check values only of the original pre-iteration entries.
   469  	key = uint32(0)
   470  	elem = uint64(256 + 0)
   471  
   472  	for i := 0; i < 31; i++ {
   473  		key += 1
   474  		elem += 1
   475  
   476  		wantOK := true
   477  		if key == deletedKey {
   478  			wantOK = false
   479  		}
   480  
   481  		gotElem, gotOK := got[key]
   482  		if gotOK != wantOK {
   483  			t.Errorf("Iteration key %d got ok %v want ok %v", key, gotOK, wantOK)
   484  			continue
   485  		}
   486  		if wantOK && gotElem != elem {
   487  			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
   488  		}
   489  	}
   490  }
   491  
   492  func testTableIterationGrowDuplicate(t *testing.T, grow int) {
   493  	m, typ := maps.NewTestMap[uint32, uint64](8)
   494  
   495  	key := uint32(0)
   496  	elem := uint64(256 + 0)
   497  
   498  	for i := 0; i < 31; i++ {
   499  		key += 1
   500  		elem += 1
   501  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   502  
   503  		if maps.DebugLog {
   504  			fmt.Printf("After put %d: %v\n", key, m)
   505  		}
   506  	}
   507  
   508  	got := make(map[uint32]uint64)
   509  	it := new(maps.Iter)
   510  	it.Init(typ, m)
   511  	for i := 0; ; i++ {
   512  		it.Next()
   513  		keyPtr, elemPtr := it.Key(), it.Elem()
   514  		if keyPtr == nil {
   515  			break
   516  		}
   517  
   518  		key := *(*uint32)(keyPtr)
   519  		elem := *(*uint64)(elemPtr)
   520  		if elem != 256 + uint64(key) {
   521  			t.Errorf("iteration got key %d elem %d want elem %d", key, elem, 256 + uint64(key))
   522  		}
   523  		if _, ok := got[key]; ok {
   524  			t.Errorf("iteration got key %d more than once", key)
   525  		}
   526  		got[key] = elem
   527  
   528  		// Grow halfway through iteration.
   529  		if i == 16 {
   530  			key := uint32(32)
   531  			elem := uint64(256 + 32)
   532  
   533  			for i := 0; i < grow; i++ {
   534  				key += 1
   535  				elem += 1
   536  				m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   537  
   538  				if maps.DebugLog {
   539  					fmt.Printf("After put %d: %v\n", key, m)
   540  				}
   541  			}
   542  		}
   543  	}
   544  
   545  	// Don't check length: the number of new elements we'll see is
   546  	// unspecified.
   547  }
   548  
   549  // Grow should not allow duplicate keys to appear.
   550  func TestTableIterationGrowDuplicate(t *testing.T) {
   551  	// Small grow, only enough to cause table grow.
   552  	t.Run("grow", func(t *testing.T) { testTableIterationGrowDuplicate(t, 32) })
   553  
   554  	// Large grow, to cause table split.
   555  	t.Run("split", func(t *testing.T) { testTableIterationGrowDuplicate(t, 2*maps.MaxTableCapacity) })
   556  }
   557  
   558  func TestAlignUpPow2(t *testing.T) {
   559  	tests := []struct {
   560  		in       uint64
   561  		want     uint64
   562  		overflow bool
   563  	}{
   564  		{
   565  			in:   0,
   566  			want: 0,
   567  		},
   568  		{
   569  			in:   3,
   570  			want: 4,
   571  		},
   572  		{
   573  			in:   4,
   574  			want: 4,
   575  		},
   576  		{
   577  			in:   1 << 63,
   578  			want: 1 << 63,
   579  		},
   580  		{
   581  			in:   (1 << 63) - 1,
   582  			want: 1 << 63,
   583  		},
   584  		{
   585  			in:       (1 << 63) + 1,
   586  			overflow: true,
   587  		},
   588  	}
   589  
   590  	for _, tc := range tests {
   591  		got, overflow := maps.AlignUpPow2(tc.in)
   592  		if got != tc.want {
   593  			t.Errorf("alignUpPow2(%d) got %d, want %d", tc.in, got, tc.want)
   594  		}
   595  		if overflow != tc.overflow {
   596  			t.Errorf("alignUpPow2(%d) got overflow %v, want %v", tc.in, overflow, tc.overflow)
   597  		}
   598  	}
   599  }
   600  
   601  // Verify that a map with zero-size slot is safe to use.
   602  func TestMapZeroSizeSlot(t *testing.T) {
   603  	m, typ := maps.NewTestMap[struct{}, struct{}](16)
   604  
   605  	key := struct{}{}
   606  	elem := struct{}{}
   607  
   608  	m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   609  
   610  	if maps.DebugLog {
   611  		fmt.Printf("After put %d: %v\n", key, m)
   612  	}
   613  
   614  	got, ok := m.Get(typ, unsafe.Pointer(&key))
   615  	if !ok {
   616  		t.Errorf("Get(%d) got ok false want true", key)
   617  	}
   618  	gotElem := *(*struct{})(got)
   619  	if gotElem != elem {
   620  		t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
   621  	}
   622  
   623  	tab := m.TableFor(typ, unsafe.Pointer(&key))
   624  	start := tab.GroupsStart()
   625  	length := tab.GroupsLength()
   626  	end := unsafe.Pointer(uintptr(start) + length*typ.Group.Size() - 1) // inclusive to ensure we have a valid pointer
   627  	if uintptr(got) < uintptr(start) || uintptr(got) > uintptr(end) {
   628  		t.Errorf("elem address outside groups allocation; got %p want [%p, %p]", got, start, end)
   629  	}
   630  }
   631  
   632  func TestMapIndirect(t *testing.T) {
   633  	type big [abi.SwissMapMaxKeyBytes + abi.SwissMapMaxElemBytes]byte
   634  
   635  	m, typ := maps.NewTestMap[big, big](8)
   636  
   637  	key := big{}
   638  	elem := big{}
   639  	elem[0] = 128
   640  
   641  	for i := 0; i < 31; i++ {
   642  		key[0] += 1
   643  		elem[0] += 1
   644  		m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   645  
   646  		if maps.DebugLog {
   647  			fmt.Printf("After put %v: %v\n", key, m)
   648  		}
   649  	}
   650  
   651  	if m.Used() != 31 {
   652  		t.Errorf("Used() used got %d want 31", m.Used())
   653  	}
   654  
   655  	key = big{}
   656  	elem = big{}
   657  	elem[0] = 128
   658  
   659  	for i := 0; i < 31; i++ {
   660  		key[0] += 1
   661  		elem[0] += 1
   662  		got, ok := m.Get(typ, unsafe.Pointer(&key))
   663  		if !ok {
   664  			t.Errorf("Get(%v) got ok false want true", key)
   665  		}
   666  		gotElem := *(*big)(got)
   667  		if gotElem != elem {
   668  			t.Errorf("Get(%v) got elem %v want %v", key, gotElem, elem)
   669  		}
   670  	}
   671  }
   672  
   673  // Delete should clear element. See https://go.dev/issue/25936.
   674  func TestMapDeleteClear(t *testing.T) {
   675  	m, typ := maps.NewTestMap[int64, int64](8)
   676  
   677  	key := int64(0)
   678  	elem := int64(128)
   679  
   680  	m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
   681  
   682  	if maps.DebugLog {
   683  		fmt.Printf("After put %d: %v\n", key, m)
   684  	}
   685  
   686  	got, ok := m.Get(typ, unsafe.Pointer(&key))
   687  	if !ok {
   688  		t.Errorf("Get(%d) got ok false want true", key)
   689  	}
   690  	gotElem := *(*int64)(got)
   691  	if gotElem != elem {
   692  		t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
   693  	}
   694  
   695  	m.Delete(typ, unsafe.Pointer(&key))
   696  
   697  	gotElem = *(*int64)(got)
   698  	if gotElem != 0 {
   699  		t.Errorf("Delete(%d) failed to clear element. got %d want 0", key, gotElem)
   700  	}
   701  }
   702
View as plain text