Nothing to see here, move along meow
1use lancer_core::header::NONE_SENTINEL;
2use lancer_core::intrusive_list::ListLinks;
3use lancer_core::timer_wheel::{TimerEntryStorage, TimerTag, TimerWheel};
4use proptest::prelude::*;
5
6const MAX_ENTRIES: usize = 2048;
7
8struct TestStorage {
9 tw_next: [u32; MAX_ENTRIES],
10 tw_prev: [u32; MAX_ENTRIES],
11 tw_slot: [u16; MAX_ENTRIES],
12 tw_deadline: [u64; MAX_ENTRIES],
13}
14
15impl TestStorage {
16 fn new() -> Self {
17 Self {
18 tw_next: [NONE_SENTINEL; MAX_ENTRIES],
19 tw_prev: [NONE_SENTINEL; MAX_ENTRIES],
20 tw_slot: [0; MAX_ENTRIES],
21 tw_deadline: [0; MAX_ENTRIES],
22 }
23 }
24}
25
26impl ListLinks<TimerTag> for TestStorage {
27 fn link_next(&self, id: u32) -> u32 {
28 self.tw_next[id as usize]
29 }
30 fn link_prev(&self, id: u32) -> u32 {
31 self.tw_prev[id as usize]
32 }
33 fn set_link_next(&mut self, id: u32, next: u32) {
34 self.tw_next[id as usize] = next;
35 }
36 fn set_link_prev(&mut self, id: u32, prev: u32) {
37 self.tw_prev[id as usize] = prev;
38 }
39}
40
41impl TimerEntryStorage for TestStorage {
42 fn tw_slot(&self, id: u32) -> u16 {
43 self.tw_slot[id as usize]
44 }
45 fn set_tw_slot(&mut self, id: u32, slot: u16) {
46 self.tw_slot[id as usize] = slot;
47 }
48 fn tw_deadline(&self, id: u32) -> u64 {
49 self.tw_deadline[id as usize]
50 }
51 fn set_tw_deadline(&mut self, id: u32, deadline: u64) {
52 self.tw_deadline[id as usize] = deadline;
53 }
54}
55
56#[test]
57fn exact_level0_firing() {
58 let mut tw = TimerWheel::new();
59 let mut store = TestStorage::new();
60 let mut fired = Vec::new();
61
62 tw.insert(0, 5, &mut store);
63 tw.advance(4, &mut store, |id| fired.push(id));
64 assert!(fired.is_empty());
65
66 tw.advance(5, &mut store, |id| fired.push(id));
67 assert_eq!(fired, vec![0]);
68}
69
70#[test]
71fn level1_granularity_firing() {
72 let mut tw = TimerWheel::new();
73 let mut store = TestStorage::new();
74 let mut fired = Vec::new();
75
76 tw.insert(0, 100, &mut store);
77
78 tw.advance(63, &mut store, |id| fired.push(id));
79 assert!(fired.is_empty());
80
81 tw.advance(100, &mut store, |id| fired.push(id));
82 assert_eq!(fired, vec![0]);
83}
84
85#[test]
86fn cancel_prevents_firing() {
87 let mut tw = TimerWheel::new();
88 let mut store = TestStorage::new();
89 let mut fired = Vec::new();
90
91 tw.insert(0, 10, &mut store);
92 tw.cancel(0, &mut store);
93
94 tw.advance(20, &mut store, |id| fired.push(id));
95 assert!(fired.is_empty());
96}
97
98#[test]
99fn bulk_insert_all_fire_once() {
100 let mut tw = TimerWheel::new();
101 let mut store = TestStorage::new();
102 let mut fired = vec![0u32; 1000];
103
104 (0..1000u32).for_each(|i| {
105 tw.insert(i, (i + 1) as u64, &mut store);
106 });
107
108 tw.advance(1000, &mut store, |id| {
109 fired[id as usize] += 1;
110 });
111
112 fired.iter().enumerate().for_each(|(i, &count)| {
113 assert_eq!(count, 1, "timer {} fired {} times", i, count);
114 });
115}
116
117#[test]
118fn cascade_level2() {
119 let mut tw = TimerWheel::new();
120 let mut store = TestStorage::new();
121 let mut fired = Vec::new();
122
123 tw.insert(0, 5000, &mut store);
124
125 tw.advance(4999, &mut store, |id| fired.push(id));
126 assert!(fired.is_empty());
127
128 tw.advance(5000, &mut store, |id| fired.push(id));
129 assert_eq!(fired, vec![0]);
130}
131
132#[test]
133fn cascade_level3() {
134 let mut tw = TimerWheel::new();
135 let mut store = TestStorage::new();
136 let mut fired = Vec::new();
137
138 tw.insert(0, 300000, &mut store);
139
140 tw.advance(299999, &mut store, |id| fired.push(id));
141 assert!(fired.is_empty());
142
143 tw.advance(300000, &mut store, |id| fired.push(id));
144 assert_eq!(fired, vec![0]);
145}
146
147#[test]
148fn multiple_same_deadline() {
149 let mut tw = TimerWheel::new();
150 let mut store = TestStorage::new();
151 let mut fired = Vec::new();
152
153 tw.insert(0, 10, &mut store);
154 tw.insert(1, 10, &mut store);
155 tw.insert(2, 10, &mut store);
156
157 tw.advance(10, &mut store, |id| fired.push(id));
158
159 fired.sort();
160 assert_eq!(fired, vec![0, 1, 2]);
161}
162
163#[test]
164fn deadline_in_past_fires_immediately() {
165 let mut tw = TimerWheel::new();
166 let mut store = TestStorage::new();
167 let mut fired = Vec::new();
168
169 tw.advance(100, &mut store, |_| {});
170 tw.insert(0, 50, &mut store);
171
172 tw.advance(101, &mut store, |id| fired.push(id));
173 assert_eq!(fired, vec![0]);
174}
175
176proptest! {
177 #[test]
178 fn random_insert_cancel_advance(
179 inserts in proptest::collection::vec(
180 (0u32..512, 1u64..10000),
181 1..100
182 ),
183 cancels in proptest::collection::vec(0u32..512, 0..30)
184 ) {
185 let mut tw = TimerWheel::new();
186 let mut store = TestStorage::new();
187 let mut expected: std::collections::HashSet<u32> = std::collections::HashSet::new();
188 let mut cancelled: std::collections::HashSet<u32> = std::collections::HashSet::new();
189
190 inserts.iter().for_each(|&(id, deadline)| {
191 if !expected.contains(&id) {
192 tw.insert(id, deadline, &mut store);
193 expected.insert(id);
194 }
195 });
196
197 cancels.iter().for_each(|&id| {
198 if expected.contains(&id) && !cancelled.contains(&id) {
199 tw.cancel(id, &mut store);
200 cancelled.insert(id);
201 }
202 });
203
204 let mut fired: std::collections::HashSet<u32> = std::collections::HashSet::new();
205 tw.advance(10000, &mut store, |id| {
206 assert!(!fired.contains(&id), "timer {} fired twice", id);
207 fired.insert(id);
208 });
209
210 expected.difference(&cancelled).for_each(|&id| {
211 assert!(fired.contains(&id), "timer {} should have fired", id);
212 });
213 cancelled.iter().for_each(|&id| {
214 assert!(!fired.contains(&id), "cancelled timer {} should not fire", id);
215 });
216 }
217
218 #[test]
219 fn staggered_deadlines_fire_in_order(
220 deltas in proptest::collection::vec(1u64..500, 1..50)
221 ) {
222 let mut tw = TimerWheel::new();
223 let mut store = TestStorage::new();
224 let mut deadlines: Vec<(u32, u64)> = Vec::new();
225
226 let mut cumulative = 0u64;
227 deltas.iter().enumerate().for_each(|(i, &d)| {
228 cumulative += d;
229 tw.insert(i as u32, cumulative, &mut store);
230 deadlines.push((i as u32, cumulative));
231 });
232
233 let max_deadline = cumulative;
234 let mut fired_order: Vec<u32> = Vec::new();
235 tw.advance(max_deadline, &mut store, |id| {
236 fired_order.push(id);
237 });
238
239 assert_eq!(fired_order.len(), deadlines.len());
240
241 deadlines.sort_by_key(|&(_, d)| d);
242 let expected_order: Vec<u32> = deadlines.iter().map(|&(id, _)| id).collect();
243 assert_eq!(fired_order, expected_order);
244 }
245}