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