libgo/go/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
 290 func BenchmarkMemmove(b *testing.B) {
 291         benchmarkSizes(b, bufSizes, func(b *testing.B, n int) {
 292                 x := make([]byte, n)
 293                 y := make([]byte, n)
 294                 for i := 0; i < b.N; i++ {
 295                         copy(x, y)
 296                 }
 297         })
 298 }
 299
 300 func BenchmarkMemmoveUnalignedDst(b *testing.B) {
 301         benchmarkSizes(b, bufSizes, func(b *testing.B, n int) {
 302                 x := make([]byte, n+1)
 303                 y := make([]byte, n)
 304                 for i := 0; i < b.N; i++ {
 305                         copy(x[1:], y)
 306                 }
 307         })
 308 }
 309
 310 func BenchmarkMemmoveUnalignedSrc(b *testing.B) {
 311         benchmarkSizes(b, bufSizes, func(b *testing.B, n int) {
 312                 x := make([]byte, n)
 313                 y := make([]byte, n+1)
 314                 for i := 0; i < b.N; i++ {
 315                         copy(x, y[1:])
 316                 }
 317         })
 318 }
 319
 320 func TestMemclr(t *testing.T) {
 321         size := 512
 322         if testing.Short() {
 323                 size = 128 + 16
 324         }
 325         mem := make([]byte, size)
 326         for i := 0; i < size; i++ {
 327                 mem[i] = 0xee
 328         }
 329         for n := 0; n < size; n++ {
 330                 for x := 0; x <= size-n; x++ { // offset in mem
 331                         MemclrBytes(mem[x : x+n])
 332                         for i := 0; i < x; i++ {
 333                                 if mem[i] != 0xee {
 334                                         t.Fatalf("overwrite prefix mem[%d] = %d", i, mem[i])
 335                                 }
 336                         }
 337                         for i := x; i < x+n; i++ {
 338                                 if mem[i] != 0 {
 339                                         t.Fatalf("failed clear mem[%d] = %d", i, mem[i])
 340                                 }
 341                                 mem[i] = 0xee
 342                         }
 343                         for i := x + n; i < size; i++ {
 344                                 if mem[i] != 0xee {
 345                                         t.Fatalf("overwrite suffix mem[%d] = %d", i, mem[i])
 346                                 }
 347                         }
 348                 }
 349         }
 350 }
 351
 352 func BenchmarkMemclr(b *testing.B) {
 353         for _, n := range []int{5, 16, 64, 256, 4096, 65536} {
 354                 x := make([]byte, n)
 355                 b.Run(fmt.Sprint(n), func(b *testing.B) {
 356                         b.SetBytes(int64(n))
 357                         for i := 0; i < b.N; i++ {
 358                                 MemclrBytes(x)
 359                         }
 360                 })
 361         }
 362         for _, m := range []int{1, 4, 8, 16, 64} {
 363                 x := make([]byte, m<<20)
 364                 b.Run(fmt.Sprint(m, "M"), func(b *testing.B) {
 365                         b.SetBytes(int64(m << 20))
 366                         for i := 0; i < b.N; i++ {
 367                                 MemclrBytes(x)
 368                         }
 369                 })
 370         }
 371 }
 372
 373 func BenchmarkGoMemclr(b *testing.B) {
 374         benchmarkSizes(b, []int{5, 16, 64, 256}, func(b *testing.B, n int) {
 375                 x := make([]byte, n)
 376                 for i := 0; i < b.N; i++ {
 377                         for j := range x {
 378                                 x[j] = 0
 379                         }
 380                 }
 381         })
 382 }
 383
 384 func BenchmarkClearFat8(b *testing.B) {
 385         for i := 0; i < b.N; i++ {
 386                 var x [8 / 4]uint32
 387                 _ = x
 388         }
 389 }
 390 func BenchmarkClearFat12(b *testing.B) {
 391         for i := 0; i < b.N; i++ {
 392                 var x [12 / 4]uint32
 393                 _ = x
 394         }
 395 }
 396 func BenchmarkClearFat16(b *testing.B) {
 397         for i := 0; i < b.N; i++ {
 398                 var x [16 / 4]uint32
 399                 _ = x
 400         }
 401 }
 402 func BenchmarkClearFat24(b *testing.B) {
 403         for i := 0; i < b.N; i++ {
 404                 var x [24 / 4]uint32
 405                 _ = x
 406         }
 407 }
 408 func BenchmarkClearFat32(b *testing.B) {
 409         for i := 0; i < b.N; i++ {
 410                 var x [32 / 4]uint32
 411                 _ = x
 412         }
 413 }
 414 func BenchmarkClearFat40(b *testing.B) {
 415         for i := 0; i < b.N; i++ {
 416                 var x [40 / 4]uint32
 417                 _ = x
 418         }
 419 }
 420 func BenchmarkClearFat48(b *testing.B) {
 421         for i := 0; i < b.N; i++ {
 422                 var x [48 / 4]uint32
 423                 _ = x
 424         }
 425 }
 426 func BenchmarkClearFat56(b *testing.B) {
 427         for i := 0; i < b.N; i++ {
 428                 var x [56 / 4]uint32
 429                 _ = x
 430         }
 431 }
 432 func BenchmarkClearFat64(b *testing.B) {
 433         for i := 0; i < b.N; i++ {
 434                 var x [64 / 4]uint32
 435                 _ = x
 436         }
 437 }
 438 func BenchmarkClearFat128(b *testing.B) {
 439         for i := 0; i < b.N; i++ {
 440                 var x [128 / 4]uint32
 441                 _ = x
 442         }
 443 }
 444 func BenchmarkClearFat256(b *testing.B) {
 445         for i := 0; i < b.N; i++ {
 446                 var x [256 / 4]uint32
 447                 _ = x
 448         }
 449 }
 450 func BenchmarkClearFat512(b *testing.B) {
 451         for i := 0; i < b.N; i++ {
 452                 var x [512 / 4]uint32
 453                 _ = x
 454         }
 455 }
 456 func BenchmarkClearFat1024(b *testing.B) {
 457         for i := 0; i < b.N; i++ {
 458                 var x [1024 / 4]uint32
 459                 _ = x
 460         }
 461 }
 462
 463 func BenchmarkCopyFat8(b *testing.B) {
 464         var x [8 / 4]uint32
 465         for i := 0; i < b.N; i++ {
 466                 y := x
 467                 _ = y
 468         }
 469 }
 470 func BenchmarkCopyFat12(b *testing.B) {
 471         var x [12 / 4]uint32
 472         for i := 0; i < b.N; i++ {
 473                 y := x
 474                 _ = y
 475         }
 476 }
 477 func BenchmarkCopyFat16(b *testing.B) {
 478         var x [16 / 4]uint32
 479         for i := 0; i < b.N; i++ {
 480                 y := x
 481                 _ = y
 482         }
 483 }
 484 func BenchmarkCopyFat24(b *testing.B) {
 485         var x [24 / 4]uint32
 486         for i := 0; i < b.N; i++ {
 487                 y := x
 488                 _ = y
 489         }
 490 }
 491 func BenchmarkCopyFat32(b *testing.B) {
 492         var x [32 / 4]uint32
 493         for i := 0; i < b.N; i++ {
 494                 y := x
 495                 _ = y
 496         }
 497 }
 498 func BenchmarkCopyFat64(b *testing.B) {
 499         var x [64 / 4]uint32
 500         for i := 0; i < b.N; i++ {
 501                 y := x
 502                 _ = y
 503         }
 504 }
 505 func BenchmarkCopyFat128(b *testing.B) {
 506         var x [128 / 4]uint32
 507         for i := 0; i < b.N; i++ {
 508                 y := x
 509                 _ = y
 510         }
 511 }
 512 func BenchmarkCopyFat256(b *testing.B) {
 513         var x [256 / 4]uint32
 514         for i := 0; i < b.N; i++ {
 515                 y := x
 516                 _ = y
 517         }
 518 }
 519 func BenchmarkCopyFat512(b *testing.B) {
 520         var x [512 / 4]uint32
 521         for i := 0; i < b.N; i++ {
 522                 y := x
 523                 _ = y
 524         }
 525 }
 526 func BenchmarkCopyFat520(b *testing.B) {
 527         var x [520 / 4]uint32
 528         for i := 0; i < b.N; i++ {
 529                 y := x
 530                 _ = y
 531         }
 532 }
 533 func BenchmarkCopyFat1024(b *testing.B) {
 534         var x [1024 / 4]uint32
 535         for i := 0; i < b.N; i++ {
 536                 y := x
 537                 _ = y
 538         }
 539 }
 540
 541 func BenchmarkIssue18740(b *testing.B) {
 542         // This tests that memmove uses one 4-byte load/store to move 4 bytes.
 543         // It used to do 2 2-byte load/stores, which leads to a pipeline stall
 544         // when we try to read the result with one 4-byte load.
 545         var buf [4]byte
 546         for j := 0; j < b.N; j++ {
 547                 s := uint32(0)
 548                 for i := 0; i < 4096; i += 4 {
 549                         copy(buf[:], g[i:])
 550                         s += binary.LittleEndian.Uint32(buf[:])
 551                 }
 552                 sink = uint64(s)
 553         }
 554 }
 555
 556 // TODO: 2 byte and 8 byte benchmarks also.
 557
 558 var g [4096]byte