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 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 }