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 BenchmarkClearFat8(b *testing.B) {
   415  	for i := 0; i < b.N; i++ {
   416  		var x [8 / 4]uint32
   417  		_ = x
   418  	}
   419  }
   420  func BenchmarkClearFat12(b *testing.B) {
   421  	for i := 0; i < b.N; i++ {
   422  		var x [12 / 4]uint32
   423  		_ = x
   424  	}
   425  }
   426  func BenchmarkClearFat16(b *testing.B) {
   427  	for i := 0; i < b.N; i++ {
   428  		var x [16 / 4]uint32
   429  		_ = x
   430  	}
   431  }
   432  func BenchmarkClearFat24(b *testing.B) {
   433  	for i := 0; i < b.N; i++ {
   434  		var x [24 / 4]uint32
   435  		_ = x
   436  	}
   437  }
   438  func BenchmarkClearFat32(b *testing.B) {
   439  	for i := 0; i < b.N; i++ {
   440  		var x [32 / 4]uint32
   441  		_ = x
   442  	}
   443  }
   444  func BenchmarkClearFat40(b *testing.B) {
   445  	for i := 0; i < b.N; i++ {
   446  		var x [40 / 4]uint32
   447  		_ = x
   448  	}
   449  }
   450  func BenchmarkClearFat48(b *testing.B) {
   451  	for i := 0; i < b.N; i++ {
   452  		var x [48 / 4]uint32
   453  		_ = x
   454  	}
   455  }
   456  func BenchmarkClearFat56(b *testing.B) {
   457  	for i := 0; i < b.N; i++ {
   458  		var x [56 / 4]uint32
   459  		_ = x
   460  	}
   461  }
   462  func BenchmarkClearFat64(b *testing.B) {
   463  	for i := 0; i < b.N; i++ {
   464  		var x [64 / 4]uint32
   465  		_ = x
   466  	}
   467  }
   468  func BenchmarkClearFat128(b *testing.B) {
   469  	for i := 0; i < b.N; i++ {
   470  		var x [128 / 4]uint32
   471  		_ = x
   472  	}
   473  }
   474  func BenchmarkClearFat256(b *testing.B) {
   475  	for i := 0; i < b.N; i++ {
   476  		var x [256 / 4]uint32
   477  		_ = x
   478  	}
   479  }
   480  func BenchmarkClearFat512(b *testing.B) {
   481  	for i := 0; i < b.N; i++ {
   482  		var x [512 / 4]uint32
   483  		_ = x
   484  	}
   485  }
   486  func BenchmarkClearFat1024(b *testing.B) {
   487  	for i := 0; i < b.N; i++ {
   488  		var x [1024 / 4]uint32
   489  		_ = x
   490  	}
   491  }
   492  
   493  func BenchmarkCopyFat8(b *testing.B) {
   494  	var x [8 / 4]uint32
   495  	for i := 0; i < b.N; i++ {
   496  		y := x
   497  		_ = y
   498  	}
   499  }
   500  func BenchmarkCopyFat12(b *testing.B) {
   501  	var x [12 / 4]uint32
   502  	for i := 0; i < b.N; i++ {
   503  		y := x
   504  		_ = y
   505  	}
   506  }
   507  func BenchmarkCopyFat16(b *testing.B) {
   508  	var x [16 / 4]uint32
   509  	for i := 0; i < b.N; i++ {
   510  		y := x
   511  		_ = y
   512  	}
   513  }
   514  func BenchmarkCopyFat24(b *testing.B) {
   515  	var x [24 / 4]uint32
   516  	for i := 0; i < b.N; i++ {
   517  		y := x
   518  		_ = y
   519  	}
   520  }
   521  func BenchmarkCopyFat32(b *testing.B) {
   522  	var x [32 / 4]uint32
   523  	for i := 0; i < b.N; i++ {
   524  		y := x
   525  		_ = y
   526  	}
   527  }
   528  func BenchmarkCopyFat64(b *testing.B) {
   529  	var x [64 / 4]uint32
   530  	for i := 0; i < b.N; i++ {
   531  		y := x
   532  		_ = y
   533  	}
   534  }
   535  func BenchmarkCopyFat128(b *testing.B) {
   536  	var x [128 / 4]uint32
   537  	for i := 0; i < b.N; i++ {
   538  		y := x
   539  		_ = y
   540  	}
   541  }
   542  func BenchmarkCopyFat256(b *testing.B) {
   543  	var x [256 / 4]uint32
   544  	for i := 0; i < b.N; i++ {
   545  		y := x
   546  		_ = y
   547  	}
   548  }
   549  func BenchmarkCopyFat512(b *testing.B) {
   550  	var x [512 / 4]uint32
   551  	for i := 0; i < b.N; i++ {
   552  		y := x
   553  		_ = y
   554  	}
   555  }
   556  func BenchmarkCopyFat520(b *testing.B) {
   557  	var x [520 / 4]uint32
   558  	for i := 0; i < b.N; i++ {
   559  		y := x
   560  		_ = y
   561  	}
   562  }
   563  func BenchmarkCopyFat1024(b *testing.B) {
   564  	var x [1024 / 4]uint32
   565  	for i := 0; i < b.N; i++ {
   566  		y := x
   567  		_ = y
   568  	}
   569  }
   570  
   571  // BenchmarkIssue18740 ensures that memmove uses 4 and 8 byte load/store to move 4 and 8 bytes.
   572  // It used to do 2 2-byte load/stores, which leads to a pipeline stall
   573  // when we try to read the result with one 4-byte load.
   574  func BenchmarkIssue18740(b *testing.B) {
   575  	benchmarks := []struct {
   576  		name  string
   577  		nbyte int
   578  		f     func([]byte) uint64
   579  	}{
   580  		{"2byte", 2, func(buf []byte) uint64 { return uint64(binary.LittleEndian.Uint16(buf)) }},
   581  		{"4byte", 4, func(buf []byte) uint64 { return uint64(binary.LittleEndian.Uint32(buf)) }},
   582  		{"8byte", 8, func(buf []byte) uint64 { return binary.LittleEndian.Uint64(buf) }},
   583  	}
   584  
   585  	var g [4096]byte
   586  	for _, bm := range benchmarks {
   587  		buf := make([]byte, bm.nbyte)
   588  		b.Run(bm.name, func(b *testing.B) {
   589  			for j := 0; j < b.N; j++ {
   590  				for i := 0; i < 4096; i += bm.nbyte {
   591  					copy(buf[:], g[i:])
   592  					sink += bm.f(buf[:])
   593  				}
   594  			}
   595  		})
   596  	}
   597  }
   598  

View as plain text