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
5package runtime_test
6
7import (
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
19func 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
61func 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
99func 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
111func 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
123func 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
146func 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.
175func copyref(dst, src []byte) {
176	for i, v := range src {
177		dst[i] = v
178	}
179}
180
181// Backwards copy
182func 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
192func 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
203func 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.
213func 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
276func 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
285var 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
290func 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
300func 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
310func 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
320func 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
352func 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
373func 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
384func BenchmarkClearFat8(b *testing.B) {
385	for i := 0; i < b.N; i++ {
386		var x [8 / 4]uint32
387		_ = x
388	}
389}
390func BenchmarkClearFat12(b *testing.B) {
391	for i := 0; i < b.N; i++ {
392		var x [12 / 4]uint32
393		_ = x
394	}
395}
396func BenchmarkClearFat16(b *testing.B) {
397	for i := 0; i < b.N; i++ {
398		var x [16 / 4]uint32
399		_ = x
400	}
401}
402func BenchmarkClearFat24(b *testing.B) {
403	for i := 0; i < b.N; i++ {
404		var x [24 / 4]uint32
405		_ = x
406	}
407}
408func BenchmarkClearFat32(b *testing.B) {
409	for i := 0; i < b.N; i++ {
410		var x [32 / 4]uint32
411		_ = x
412	}
413}
414func BenchmarkClearFat40(b *testing.B) {
415	for i := 0; i < b.N; i++ {
416		var x [40 / 4]uint32
417		_ = x
418	}
419}
420func BenchmarkClearFat48(b *testing.B) {
421	for i := 0; i < b.N; i++ {
422		var x [48 / 4]uint32
423		_ = x
424	}
425}
426func BenchmarkClearFat56(b *testing.B) {
427	for i := 0; i < b.N; i++ {
428		var x [56 / 4]uint32
429		_ = x
430	}
431}
432func BenchmarkClearFat64(b *testing.B) {
433	for i := 0; i < b.N; i++ {
434		var x [64 / 4]uint32
435		_ = x
436	}
437}
438func BenchmarkClearFat128(b *testing.B) {
439	for i := 0; i < b.N; i++ {
440		var x [128 / 4]uint32
441		_ = x
442	}
443}
444func BenchmarkClearFat256(b *testing.B) {
445	for i := 0; i < b.N; i++ {
446		var x [256 / 4]uint32
447		_ = x
448	}
449}
450func BenchmarkClearFat512(b *testing.B) {
451	for i := 0; i < b.N; i++ {
452		var x [512 / 4]uint32
453		_ = x
454	}
455}
456func BenchmarkClearFat1024(b *testing.B) {
457	for i := 0; i < b.N; i++ {
458		var x [1024 / 4]uint32
459		_ = x
460	}
461}
462
463func 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}
470func 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}
477func 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}
484func 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}
491func 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}
498func 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}
505func 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}
512func 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}
519func 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}
526func 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}
533func 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
541func 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
558var g [4096]byte
559