Source file src/runtime/memmove_test.go

     1  // Copyright 2013 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 runtime_test
     6  
     7  import (
     8  	"crypto/rand"
     9  	"encoding/binary"
    10  	"fmt"
    11  	"internal/race"
    12  	"internal/testenv"
    13  	. "runtime"
    14  	"sync/atomic"
    15  	"testing"
    16  	"unsafe"
    17  )
    18  
    19  func TestMemmove(t *testing.T) {
    20  	if *flagQuick {
    21  		t.Skip("-quick")
    22  	}
    23  	t.Parallel()
    24  	size := 256
    25  	if testing.Short() {
    26  		size = 128 + 16
    27  	}
    28  	src := make([]byte, size)
    29  	dst := make([]byte, size)
    30  	for i := 0; i < size; i++ {
    31  		src[i] = byte(128 + (i & 127))
    32  	}
    33  	for i := 0; i < size; i++ {
    34  		dst[i] = byte(i & 127)
    35  	}
    36  	for n := 0; n <= size; n++ {
    37  		for x := 0; x <= size-n; x++ { // offset in src
    38  			for y := 0; y <= size-n; y++ { // offset in dst
    39  				copy(dst[y:y+n], src[x:x+n])
    40  				for i := 0; i < y; i++ {
    41  					if dst[i] != byte(i&127) {
    42  						t.Fatalf("prefix dst[%d] = %d", i, dst[i])
    43  					}
    44  				}
    45  				for i := y; i < y+n; i++ {
    46  					if dst[i] != byte(128+((i-y+x)&127)) {
    47  						t.Fatalf("copied dst[%d] = %d", i, dst[i])
    48  					}
    49  					dst[i] = byte(i & 127) // reset dst
    50  				}
    51  				for i := y + n; i < size; i++ {
    52  					if dst[i] != byte(i&127) {
    53  						t.Fatalf("suffix dst[%d] = %d", i, dst[i])
    54  					}
    55  				}
    56  			}
    57  		}
    58  	}
    59  }
    60  
    61  func TestMemmoveAlias(t *testing.T) {
    62  	if *flagQuick {
    63  		t.Skip("-quick")
    64  	}
    65  	t.Parallel()
    66  	size := 256
    67  	if testing.Short() {
    68  		size = 128 + 16
    69  	}
    70  	buf := make([]byte, size)
    71  	for i := 0; i < size; i++ {
    72  		buf[i] = byte(i)
    73  	}
    74  	for n := 0; n <= size; n++ {
    75  		for x := 0; x <= size-n; x++ { // src offset
    76  			for y := 0; y <= size-n; y++ { // dst offset
    77  				copy(buf[y:y+n], buf[x:x+n])
    78  				for i := 0; i < y; i++ {
    79  					if buf[i] != byte(i) {
    80  						t.Fatalf("prefix buf[%d] = %d", i, buf[i])
    81  					}
    82  				}
    83  				for i := y; i < y+n; i++ {
    84  					if buf[i] != byte(i-y+x) {
    85  						t.Fatalf("copied buf[%d] = %d", i, buf[i])
    86  					}
    87  					buf[i] = byte(i) // reset buf
    88  				}
    89  				for i := y + n; i < size; i++ {
    90  					if buf[i] != byte(i) {
    91  						t.Fatalf("suffix buf[%d] = %d", i, buf[i])
    92  					}
    93  				}
    94  			}
    95  		}
    96  	}
    97  }
    98  
    99  func TestMemmoveLarge0x180000(t *testing.T) {
   100  	if testing.Short() && testenv.Builder() == "" {
   101  		t.Skip("-short")
   102  	}
   103  
   104  	t.Parallel()
   105  	if race.Enabled {
   106  		t.Skip("skipping large memmove test under race detector")
   107  	}
   108  	testSize(t, 0x180000)
   109  }
   110  
   111  func TestMemmoveOverlapLarge0x120000(t *testing.T) {
   112  	if testing.Short() && testenv.Builder() == "" {
   113  		t.Skip("-short")
   114  	}
   115  
   116  	t.Parallel()
   117  	if race.Enabled {
   118  		t.Skip("skipping large memmove test under race detector")
   119  	}
   120  	testOverlap(t, 0x120000)
   121  }
   122  
   123  func testSize(t *testing.T, size int) {
   124  	src := make([]byte, size)
   125  	dst := make([]byte, size)
   126  	_, _ = rand.Read(src)
   127  	_, _ = rand.Read(dst)
   128  
   129  	ref := make([]byte, size)
   130  	copyref(ref, dst)
   131  
   132  	for n := size - 50; n > 1; n >>= 1 {
   133  		for x := 0; x <= size-n; x = x*7 + 1 { // offset in src
   134  			for y := 0; y <= size-n; y = y*9 + 1 { // offset in dst
   135  				copy(dst[y:y+n], src[x:x+n])
   136  				copyref(ref[y:y+n], src[x:x+n])
   137  				p := cmpb(dst, ref)
   138  				if p >= 0 {
   139  					t.Fatalf("Copy failed, copying from src[%d:%d] to dst[%d:%d].\nOffset %d is different, %v != %v", x, x+n, y, y+n, p, dst[p], ref[p])
   140  				}
   141  			}
   142  		}
   143  	}
   144  }
   145  
   146  func testOverlap(t *testing.T, size int) {
   147  	src := make([]byte, size)
   148  	test := make([]byte, size)
   149  	ref := make([]byte, size)
   150  	_, _ = rand.Read(src)
   151  
   152  	for n := size - 50; n > 1; n >>= 1 {
   153  		for x := 0; x <= size-n; x = x*7 + 1 { // offset in src
   154  			for y := 0; y <= size-n; y = y*9 + 1 { // offset in dst
   155  				// Reset input
   156  				copyref(test, src)
   157  				copyref(ref, src)
   158  				copy(test[y:y+n], test[x:x+n])
   159  				if y <= x {
   160  					copyref(ref[y:y+n], ref[x:x+n])
   161  				} else {
   162  					copybw(ref[y:y+n], ref[x:x+n])
   163  				}
   164  				p := cmpb(test, ref)
   165  				if p >= 0 {
   166  					t.Fatalf("Copy failed, copying from src[%d:%d] to dst[%d:%d].\nOffset %d is different, %v != %v", x, x+n, y, y+n, p, test[p], ref[p])
   167  				}
   168  			}
   169  		}
   170  	}
   171  
   172  }
   173  
   174  // Forward copy.
   175  func copyref(dst, src []byte) {
   176  	for i, v := range src {
   177  		dst[i] = v
   178  	}
   179  }
   180  
   181  // Backwards copy
   182  func copybw(dst, src []byte) {
   183  	if len(src) == 0 {
   184  		return
   185  	}
   186  	for i := len(src) - 1; i >= 0; i-- {
   187  		dst[i] = src[i]
   188  	}
   189  }
   190  
   191  // Returns offset of difference
   192  func matchLen(a, b []byte, max int) int {
   193  	a = a[:max]
   194  	b = b[:max]
   195  	for i, av := range a {
   196  		if b[i] != av {
   197  			return i
   198  		}
   199  	}
   200  	return max
   201  }
   202  
   203  func cmpb(a, b []byte) int {
   204  	l := matchLen(a, b, len(a))
   205  	if l == len(a) {
   206  		return -1
   207  	}
   208  	return l
   209  }
   210  
   211  // Ensure that memmove writes pointers atomically, so the GC won't
   212  // observe a partially updated pointer.
   213  func TestMemmoveAtomicity(t *testing.T) {
   214  	if race.Enabled {
   215  		t.Skip("skip under the race detector -- this test is intentionally racy")
   216  	}
   217  
   218  	var x int
   219  
   220  	for _, backward := range []bool{true, false} {
   221  		for _, n := range []int{3, 4, 5, 6, 7, 8, 9, 10, 15, 25, 49} {
   222  			n := n
   223  
   224  			// test copying [N]*int.
   225  			sz := uintptr(n * PtrSize)
   226  			name := fmt.Sprint(sz)
   227  			if backward {
   228  				name += "-backward"
   229  			} else {
   230  				name += "-forward"
   231  			}
   232  			t.Run(name, func(t *testing.T) {
   233  				// Use overlapping src and dst to force forward/backward copy.
   234  				var s [100]*int
   235  				src := s[n-1 : 2*n-1]
   236  				dst := s[:n]
   237  				if backward {
   238  					src, dst = dst, src
   239  				}
   240  				for i := range src {
   241  					src[i] = &x
   242  				}
   243  				for i := range dst {
   244  					dst[i] = nil
   245  				}
   246  
   247  				var ready uint32
   248  				go func() {
   249  					sp := unsafe.Pointer(&src[0])
   250  					dp := unsafe.Pointer(&dst[0])
   251  					atomic.StoreUint32(&ready, 1)
   252  					for i := 0; i < 10000; i++ {
   253  						Memmove(dp, sp, sz)
   254  						MemclrNoHeapPointers(dp, sz)
   255  					}
   256  					atomic.StoreUint32(&ready, 2)
   257  				}()
   258  
   259  				for atomic.LoadUint32(&ready) == 0 {
   260  					Gosched()
   261  				}
   262  
   263  				for atomic.LoadUint32(&ready) != 2 {
   264  					for i := range dst {
   265  						p := dst[i]
   266  						if p != nil && p != &x {
   267  							t.Fatalf("got partially updated pointer %p at dst[%d], want either nil or %p", p, i, &x)
   268  						}
   269  					}
   270  				}
   271  			})
   272  		}
   273  	}
   274  }
   275  
   276  func benchmarkSizes(b *testing.B, sizes []int, fn func(b *testing.B, n int)) {
   277  	for _, n := range sizes {
   278  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   279  			b.SetBytes(int64(n))
   280  			fn(b, n)
   281  		})
   282  	}
   283  }
   284  
   285  var bufSizes = []int{
   286  	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
   287  	32, 64, 128, 256, 512, 1024, 2048, 4096,
   288  }
   289  var bufSizesOverlap = []int{
   290  	32, 64, 128, 256, 512, 1024, 2048, 4096,
   291  }
   292  
   293  func BenchmarkMemmove(b *testing.B) {
   294  	benchmarkSizes(b, bufSizes, func(b *testing.B, n int) {
   295  		x := make([]byte, n)
   296  		y := make([]byte, n)
   297  		for i := 0; i < b.N; i++ {
   298  			copy(x, y)
   299  		}
   300  	})
   301  }
   302  
   303  func BenchmarkMemmoveOverlap(b *testing.B) {
   304  	benchmarkSizes(b, bufSizesOverlap, func(b *testing.B, n int) {
   305  		x := make([]byte, n+16)
   306  		for i := 0; i < b.N; i++ {
   307  			copy(x[16:n+16], x[:n])
   308  		}
   309  	})
   310  }
   311  
   312  func BenchmarkMemmoveUnalignedDst(b *testing.B) {
   313  	benchmarkSizes(b, bufSizes, func(b *testing.B, n int) {
   314  		x := make([]byte, n+1)
   315  		y := make([]byte, n)
   316  		for i := 0; i < b.N; i++ {
   317  			copy(x[1:], y)
   318  		}
   319  	})
   320  }
   321  
   322  func BenchmarkMemmoveUnalignedDstOverlap(b *testing.B) {
   323  	benchmarkSizes(b, bufSizesOverlap, func(b *testing.B, n int) {
   324  		x := make([]byte, n+16)
   325  		for i := 0; i < b.N; i++ {
   326  			copy(x[16:n+16], x[1:n+1])
   327  		}
   328  	})
   329  }
   330  
   331  func BenchmarkMemmoveUnalignedSrc(b *testing.B) {
   332  	benchmarkSizes(b, bufSizes, func(b *testing.B, n int) {
   333  		x := make([]byte, n)
   334  		y := make([]byte, n+1)
   335  		for i := 0; i < b.N; i++ {
   336  			copy(x, y[1:])
   337  		}
   338  	})
   339  }
   340  
   341  func BenchmarkMemmoveUnalignedSrcOverlap(b *testing.B) {
   342  	benchmarkSizes(b, bufSizesOverlap, func(b *testing.B, n int) {
   343  		x := make([]byte, n+1)
   344  		for i := 0; i < b.N; i++ {
   345  			copy(x[1:n+1], x[:n])
   346  		}
   347  	})
   348  }
   349  
   350  func TestMemclr(t *testing.T) {
   351  	size := 512
   352  	if testing.Short() {
   353  		size = 128 + 16
   354  	}
   355  	mem := make([]byte, size)
   356  	for i := 0; i < size; i++ {
   357  		mem[i] = 0xee
   358  	}
   359  	for n := 0; n < size; n++ {
   360  		for x := 0; x <= size-n; x++ { // offset in mem
   361  			MemclrBytes(mem[x : x+n])
   362  			for i := 0; i < x; i++ {
   363  				if mem[i] != 0xee {
   364  					t.Fatalf("overwrite prefix mem[%d] = %d", i, mem[i])
   365  				}
   366  			}
   367  			for i := x; i < x+n; i++ {
   368  				if mem[i] != 0 {
   369  					t.Fatalf("failed clear mem[%d] = %d", i, mem[i])
   370  				}
   371  				mem[i] = 0xee
   372  			}
   373  			for i := x + n; i < size; i++ {
   374  				if mem[i] != 0xee {
   375  					t.Fatalf("overwrite suffix mem[%d] = %d", i, mem[i])
   376  				}
   377  			}
   378  		}
   379  	}
   380  }
   381  
   382  func BenchmarkMemclr(b *testing.B) {
   383  	for _, n := range []int{5, 16, 64, 256, 4096, 65536} {
   384  		x := make([]byte, n)
   385  		b.Run(fmt.Sprint(n), func(b *testing.B) {
   386  			b.SetBytes(int64(n))
   387  			for i := 0; i < b.N; i++ {
   388  				MemclrBytes(x)
   389  			}
   390  		})
   391  	}
   392  	for _, m := range []int{1, 4, 8, 16, 64} {
   393  		x := make([]byte, m<<20)
   394  		b.Run(fmt.Sprint(m, "M"), func(b *testing.B) {
   395  			b.SetBytes(int64(m << 20))
   396  			for i := 0; i < b.N; i++ {
   397  				MemclrBytes(x)
   398  			}
   399  		})
   400  	}
   401  }
   402  
   403  func BenchmarkGoMemclr(b *testing.B) {
   404  	benchmarkSizes(b, []int{5, 16, 64, 256}, func(b *testing.B, n int) {
   405  		x := make([]byte, n)
   406  		for i := 0; i < b.N; i++ {
   407  			for j := range x {
   408  				x[j] = 0
   409  			}
   410  		}
   411  	})
   412  }
   413  
   414  func BenchmarkMemclrRange(b *testing.B) {
   415  	type RunData struct {
   416  		data []int
   417  	}
   418  
   419  	benchSizes := []RunData{
   420  		RunData{[]int{1043, 1078, 1894, 1582, 1044, 1165, 1467, 1100, 1919, 1562, 1932, 1645,
   421  			1412, 1038, 1576, 1200, 1029, 1336, 1095, 1494, 1350, 1025, 1502, 1548, 1316, 1296,
   422  			1868, 1639, 1546, 1626, 1642, 1308, 1726, 1665, 1678, 1187, 1515, 1598, 1353, 1237,
   423  			1977, 1452, 2012, 1914, 1514, 1136, 1975, 1618, 1536, 1695, 1600, 1733, 1392, 1099,
   424  			1358, 1996, 1224, 1783, 1197, 1838, 1460, 1556, 1554, 2020}}, // 1kb-2kb
   425  		RunData{[]int{3964, 5139, 6573, 7775, 6553, 2413, 3466, 5394, 2469, 7336, 7091, 6745,
   426  			4028, 5643, 6164, 3475, 4138, 6908, 7559, 3335, 5660, 4122, 3945, 2082, 7564, 6584,
   427  			5111, 2288, 6789, 2797, 4928, 7986, 5163, 5447, 2999, 4968, 3174, 3202, 7908, 8137,
   428  			4735, 6161, 4646, 7592, 3083, 5329, 3687, 2754, 3599, 7231, 6455, 2549, 8063, 2189,
   429  			7121, 5048, 4277, 6626, 6306, 2815, 7473, 3963, 7549, 7255}}, // 2kb-8kb
   430  		RunData{[]int{16304, 15936, 15760, 4736, 9136, 11184, 10160, 5952, 14560, 15744,
   431  			6624, 5872, 13088, 14656, 14192, 10304, 4112, 10384, 9344, 4496, 11392, 7024,
   432  			5200, 10064, 14784, 5808, 13504, 10480, 8512, 4896, 13264, 5600}}, // 4kb-16kb
   433  		RunData{[]int{164576, 233136, 220224, 183280, 214112, 217248, 228560, 201728}}, // 128kb-256kb
   434  	}
   435  
   436  	for _, t := range benchSizes {
   437  		total := 0
   438  		minLen := 0
   439  		maxLen := 0
   440  
   441  		for _, clrLen := range t.data {
   442  			if clrLen > maxLen {
   443  				maxLen = clrLen
   444  			}
   445  			if clrLen < minLen || minLen == 0 {
   446  				minLen = clrLen
   447  			}
   448  			total += clrLen
   449  		}
   450  		buffer := make([]byte, maxLen)
   451  
   452  		text := ""
   453  		if minLen >= (1 << 20) {
   454  			text = fmt.Sprint(minLen>>20, "M ", (maxLen+(1<<20-1))>>20, "M")
   455  		} else if minLen >= (1 << 10) {
   456  			text = fmt.Sprint(minLen>>10, "K ", (maxLen+(1<<10-1))>>10, "K")
   457  		} else {
   458  			text = fmt.Sprint(minLen, " ", maxLen)
   459  		}
   460  		b.Run(text, func(b *testing.B) {
   461  			b.SetBytes(int64(total))
   462  			for i := 0; i < b.N; i++ {
   463  				for _, clrLen := range t.data {
   464  					MemclrBytes(buffer[:clrLen])
   465  				}
   466  			}
   467  		})
   468  	}
   469  }
   470  
   471  func BenchmarkClearFat8(b *testing.B) {
   472  	for i := 0; i < b.N; i++ {
   473  		var x [8 / 4]uint32
   474  		_ = x
   475  	}
   476  }
   477  func BenchmarkClearFat12(b *testing.B) {
   478  	for i := 0; i < b.N; i++ {
   479  		var x [12 / 4]uint32
   480  		_ = x
   481  	}
   482  }
   483  func BenchmarkClearFat16(b *testing.B) {
   484  	for i := 0; i < b.N; i++ {
   485  		var x [16 / 4]uint32
   486  		_ = x
   487  	}
   488  }
   489  func BenchmarkClearFat24(b *testing.B) {
   490  	for i := 0; i < b.N; i++ {
   491  		var x [24 / 4]uint32
   492  		_ = x
   493  	}
   494  }
   495  func BenchmarkClearFat32(b *testing.B) {
   496  	for i := 0; i < b.N; i++ {
   497  		var x [32 / 4]uint32
   498  		_ = x
   499  	}
   500  }
   501  func BenchmarkClearFat40(b *testing.B) {
   502  	for i := 0; i < b.N; i++ {
   503  		var x [40 / 4]uint32
   504  		_ = x
   505  	}
   506  }
   507  func BenchmarkClearFat48(b *testing.B) {
   508  	for i := 0; i < b.N; i++ {
   509  		var x [48 / 4]uint32
   510  		_ = x
   511  	}
   512  }
   513  func BenchmarkClearFat56(b *testing.B) {
   514  	for i := 0; i < b.N; i++ {
   515  		var x [56 / 4]uint32
   516  		_ = x
   517  	}
   518  }
   519  func BenchmarkClearFat64(b *testing.B) {
   520  	for i := 0; i < b.N; i++ {
   521  		var x [64 / 4]uint32
   522  		_ = x
   523  	}
   524  }
   525  func BenchmarkClearFat128(b *testing.B) {
   526  	for i := 0; i < b.N; i++ {
   527  		var x [128 / 4]uint32
   528  		_ = x
   529  	}
   530  }
   531  func BenchmarkClearFat256(b *testing.B) {
   532  	for i := 0; i < b.N; i++ {
   533  		var x [256 / 4]uint32
   534  		_ = x
   535  	}
   536  }
   537  func BenchmarkClearFat512(b *testing.B) {
   538  	for i := 0; i < b.N; i++ {
   539  		var x [512 / 4]uint32
   540  		_ = x
   541  	}
   542  }
   543  func BenchmarkClearFat1024(b *testing.B) {
   544  	for i := 0; i < b.N; i++ {
   545  		var x [1024 / 4]uint32
   546  		_ = x
   547  	}
   548  }
   549  
   550  func BenchmarkCopyFat8(b *testing.B) {
   551  	var x [8 / 4]uint32
   552  	for i := 0; i < b.N; i++ {
   553  		y := x
   554  		_ = y
   555  	}
   556  }
   557  func BenchmarkCopyFat12(b *testing.B) {
   558  	var x [12 / 4]uint32
   559  	for i := 0; i < b.N; i++ {
   560  		y := x
   561  		_ = y
   562  	}
   563  }
   564  func BenchmarkCopyFat16(b *testing.B) {
   565  	var x [16 / 4]uint32
   566  	for i := 0; i < b.N; i++ {
   567  		y := x
   568  		_ = y
   569  	}
   570  }
   571  func BenchmarkCopyFat24(b *testing.B) {
   572  	var x [24 / 4]uint32
   573  	for i := 0; i < b.N; i++ {
   574  		y := x
   575  		_ = y
   576  	}
   577  }
   578  func BenchmarkCopyFat32(b *testing.B) {
   579  	var x [32 / 4]uint32
   580  	for i := 0; i < b.N; i++ {
   581  		y := x
   582  		_ = y
   583  	}
   584  }
   585  func BenchmarkCopyFat64(b *testing.B) {
   586  	var x [64 / 4]uint32
   587  	for i := 0; i < b.N; i++ {
   588  		y := x
   589  		_ = y
   590  	}
   591  }
   592  func BenchmarkCopyFat128(b *testing.B) {
   593  	var x [128 / 4]uint32
   594  	for i := 0; i < b.N; i++ {
   595  		y := x
   596  		_ = y
   597  	}
   598  }
   599  func BenchmarkCopyFat256(b *testing.B) {
   600  	var x [256 / 4]uint32
   601  	for i := 0; i < b.N; i++ {
   602  		y := x
   603  		_ = y
   604  	}
   605  }
   606  func BenchmarkCopyFat512(b *testing.B) {
   607  	var x [512 / 4]uint32
   608  	for i := 0; i < b.N; i++ {
   609  		y := x
   610  		_ = y
   611  	}
   612  }
   613  func BenchmarkCopyFat520(b *testing.B) {
   614  	var x [520 / 4]uint32
   615  	for i := 0; i < b.N; i++ {
   616  		y := x
   617  		_ = y
   618  	}
   619  }
   620  func BenchmarkCopyFat1024(b *testing.B) {
   621  	var x [1024 / 4]uint32
   622  	for i := 0; i < b.N; i++ {
   623  		y := x
   624  		_ = y
   625  	}
   626  }
   627  
   628  // BenchmarkIssue18740 ensures that memmove uses 4 and 8 byte load/store to move 4 and 8 bytes.
   629  // It used to do 2 2-byte load/stores, which leads to a pipeline stall
   630  // when we try to read the result with one 4-byte load.
   631  func BenchmarkIssue18740(b *testing.B) {
   632  	benchmarks := []struct {
   633  		name  string
   634  		nbyte int
   635  		f     func([]byte) uint64
   636  	}{
   637  		{"2byte", 2, func(buf []byte) uint64 { return uint64(binary.LittleEndian.Uint16(buf)) }},
   638  		{"4byte", 4, func(buf []byte) uint64 { return uint64(binary.LittleEndian.Uint32(buf)) }},
   639  		{"8byte", 8, func(buf []byte) uint64 { return binary.LittleEndian.Uint64(buf) }},
   640  	}
   641  
   642  	var g [4096]byte
   643  	for _, bm := range benchmarks {
   644  		buf := make([]byte, bm.nbyte)
   645  		b.Run(bm.name, func(b *testing.B) {
   646  			for j := 0; j < b.N; j++ {
   647  				for i := 0; i < 4096; i += bm.nbyte {
   648  					copy(buf[:], g[i:])
   649  					sink += bm.f(buf[:])
   650  				}
   651  			}
   652  		})
   653  	}
   654  }
   655  

View as plain text