1 package peer
2 3 import (
4 "fmt"
5 "testing"
6 )
7 8 // TestMruNonceMap ensures the mruNonceMap behaves as expected including limiting, eviction of least-recently used
9 // entries, specific entry removal, and existence tests.
10 func TestMruNonceMap(t *testing.T) {
11 // Create a bunch of fake nonces to use in testing the mru Nonce code.
12 numNonces := 10
13 nonces := make([]uint64, 0, numNonces)
14 for i := 0; i < numNonces; i++ {
15 nonces = append(nonces, uint64(i))
16 }
17 tests := []struct {
18 name string
19 limit int
20 }{
21 {name: "limit 0", limit: 0},
22 {name: "limit 1", limit: 1},
23 {name: "limit 5", limit: 5},
24 {name: "limit 7", limit: 7},
25 {name: "limit one less than available", limit: numNonces - 1},
26 {name: "limit all available", limit: numNonces},
27 }
28 testLoop:
29 for i, test := range tests {
30 // Create a new mru Nonce map limited by the specified test limit and add all of the test nonces. This will
31 // cause evicition since there are more test nonces than the limits.
32 mruNonceMap := newMruNonceMap(uint(test.limit))
33 for j := 0; j < numNonces; j++ {
34 mruNonceMap.Add(nonces[j])
35 }
36 // Ensure the limited number of most recent entries in the list exist.
37 for j := numNonces - test.limit; j < numNonces; j++ {
38 if !mruNonceMap.Exists(nonces[j]) {
39 t.Errorf("Exists #%d (%s) entry %d does not "+
40 "exist", i, test.name, nonces[j],
41 )
42 continue testLoop
43 }
44 }
45 // Ensure the entries before the limited number of most recent entries in the list do not exist.
46 for j := 0; j < numNonces-test.limit; j++ {
47 if mruNonceMap.Exists(nonces[j]) {
48 t.Errorf("Exists #%d (%s) entry %d exists", i,
49 test.name, nonces[j],
50 )
51 continue testLoop
52 }
53 }
54 // Readd the entry that should currently be the least-recently used entry so it becomes the most-recently used
55 // entry, then force an eviction by adding an entry that doesn't exist and ensure the evicted entry is the new
56 // least-recently used entry. This check needs at least 2 entries.
57 if test.limit > 1 {
58 origLruIndex := numNonces - test.limit
59 mruNonceMap.Add(nonces[origLruIndex])
60 mruNonceMap.Add(uint64(numNonces) + 1)
61 // Ensure the original lru entry still exists since it was updated and should've have become the mru entry.
62 if !mruNonceMap.Exists(nonces[origLruIndex]) {
63 t.Errorf("MRU #%d (%s) entry %d does not exist",
64 i, test.name, nonces[origLruIndex],
65 )
66 continue testLoop
67 }
68 // Ensure the entry that should've become the new lru entry was evicted.
69 newLruIndex := origLruIndex + 1
70 if mruNonceMap.Exists(nonces[newLruIndex]) {
71 t.Errorf("MRU #%d (%s) entry %d exists", i,
72 test.name, nonces[newLruIndex],
73 )
74 continue testLoop
75 }
76 }
77 // Delete all of the entries in the list, including those that don't exist in the map, and ensure they no longer
78 // exist.
79 for j := 0; j < numNonces; j++ {
80 mruNonceMap.Delete(nonces[j])
81 if mruNonceMap.Exists(nonces[j]) {
82 t.Errorf("Delete #%d (%s) entry %d exists", i,
83 test.name, nonces[j],
84 )
85 continue testLoop
86 }
87 }
88 }
89 }
90 91 // TestMruNonceMapStringer tests the stringized output for the mruNonceMap type.
92 func TestMruNonceMapStringer(t *testing.T) {
93 // Create a couple of fake nonces to use in testing the mru Nonce stringer code.
94 nonce1 := uint64(10)
95 nonce2 := uint64(20)
96 // Create new mru Nonce map and add the nonces.
97 mruNonceMap := newMruNonceMap(uint(2))
98 mruNonceMap.Add(nonce1)
99 mruNonceMap.Add(nonce2)
100 // Ensure the stringer gives the expected result. Since map iteration is not ordered, either entry could be first,
101 // so account for both cases.
102 wantStr1 := fmt.Sprintf("<%d>[%d, %d]", 2, nonce1, nonce2)
103 wantStr2 := fmt.Sprintf("<%d>[%d, %d]", 2, nonce2, nonce1)
104 gotStr := mruNonceMap.String()
105 if gotStr != wantStr1 && gotStr != wantStr2 {
106 t.Fatalf("unexpected string representation - got %q, want %q "+
107 "or %q", gotStr, wantStr1, wantStr2,
108 )
109 }
110 }
111 112 // BenchmarkMruNonceList performs basic benchmarks on the most recently used Nonce handling.
113 func BenchmarkMruNonceList(b *testing.B) {
114 // Create a bunch of fake nonces to use in benchmarking the mru Nonce code.
115 b.StopTimer()
116 numNonces := 100000
117 nonces := make([]uint64, 0, numNonces)
118 for i := 0; i < numNonces; i++ {
119 nonces = append(nonces, uint64(i))
120 }
121 b.StartTimer()
122 // Benchmark the add plus evicition code.
123 limit := 20000
124 mruNonceMap := newMruNonceMap(uint(limit))
125 for i := 0; i < b.N; i++ {
126 mruNonceMap.Add(nonces[i%numNonces])
127 }
128 }
129