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