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