test_minmax.c revision a74702c6 
1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
2/* Tests adopted from Chromium windowed_filter_test.cc */
3// Copyright (c) 2016 The Chromium Authors. All rights reserved.
4
5#include <assert.h>
6#include <stdint.h>
7#include <string.h>
8
9#include "lsquic_minmax.h"
10
11#ifdef _MSC_VER
12#include "vc_compat.h"
13#endif
14
15/* Convert milliseconds to lsquic_time_t, which is microseconds */
16#define ms(val) ((val) * 1000)
17
18static void
19init_minmax (struct minmax *minmax)
20{
21    minmax_init(minmax, ms(99));
22}
23
24
25// Sets up windowed_min_rtt_ to have the following values:
26// Best = 20ms, recorded at 25ms
27// Second best = 30ms, recorded at 50ms
28// Third best = 50ms, recorded at 100ms
29static void
30init_min_filter (struct minmax *minmax)
31{
32    uint64_t now, rtt;
33    unsigned i;
34
35    now = 0;
36    rtt = ms(10);
37    for (i = 0; i < 5; ++i)
38    {
39        minmax_upmin(minmax, now, rtt);
40        now += ms(25);
41        rtt += ms(10);
42    }
43    assert(ms(20) == minmax_get_idx(minmax, 0));
44    assert(ms(30) == minmax_get_idx(minmax, 1));
45    assert(ms(50) == minmax_get_idx(minmax, 2));
46}
47
48
49// Sets up windowed_max_bw_ to have the following values:
50// Best = 900 bps, recorded at 25ms
51// Second best = 800 bps, recorded at 50ms
52// Third best = 600 bps, recorded at 100ms
53static void
54init_max_filter (struct minmax *minmax)
55{
56    uint64_t now, bw;
57    unsigned i;
58
59    now = 0;
60    bw = 1000;
61    for (i = 0; i < 5; ++i)
62    {
63        minmax_upmax(minmax, now, bw);
64        now += ms(25);
65        bw -= 100;
66    }
67    assert(900 == minmax_get_idx(minmax, 0));
68    assert(800 == minmax_get_idx(minmax, 1));
69    assert(600 == minmax_get_idx(minmax, 2));
70}
71
72
73// Test helper function: updates the filter with a lot of small values in order
74// to ensure that it is not susceptible to noise.
75static void
76update_with_irrelevant_samples (struct minmax *minmax, uint64_t max_value,
77                                                                uint64_t time)
78{
79    uint64_t i;
80
81    for (i = 0; i < 1000; ++i)
82        minmax_upmax(minmax, time, i % max_value);
83}
84
85
86static void
87test_uninitialized_estimates (void)
88{
89    struct minmax minmax;
90
91    init_minmax(&minmax);
92    assert(0 == minmax_get_idx(&minmax, 0));
93    assert(0 == minmax_get_idx(&minmax, 1));
94    assert(0 == minmax_get_idx(&minmax, 2));
95}
96
97
98static void
99test_monotonically_increasing_min (void)
100{
101    struct minmax minmax;
102    uint64_t rtt, now;
103    unsigned i;
104
105    rtt = ms(10);
106    now = 0;
107
108    init_minmax(&minmax);
109    minmax_upmin(&minmax, now, rtt);
110
111    assert(ms(10) == minmax_get(&minmax));
112    // Gradually increase the rtt samples and ensure the windowed min rtt starts
113    // rising.
114    for (i = 0; i < 6; ++i)
115    {
116        now += ms(25);
117        rtt += ms(10);
118        minmax_upmin(&minmax, now, rtt);
119        if (i < 3)
120            assert(minmax_get(&minmax) == ms(10));
121        else if (i == 3)
122            assert(minmax_get(&minmax) == ms(20));
123        else if (i == 4)
124            assert(minmax_get(&minmax) == ms(30));
125        else
126            assert(minmax_get(&minmax) == ms(50));
127    }
128}
129
130
131static void
132test_monotonically_decreasing_max (void)
133{
134    struct minmax minmax;
135    uint64_t bw, now;
136    unsigned i;
137
138    bw = 1000;
139    now = 0;
140
141    init_minmax(&minmax);
142    minmax_upmax(&minmax, now, bw);
143
144    assert(1000 == minmax_get(&minmax));
145    // Gradually decrease the bw samples and ensure the windowed max bw starts
146    // decreasing.
147    for (i = 0; i < 6; ++i)
148    {
149        now += ms(25);
150        bw -= 100;
151        minmax_upmax(&minmax, now, bw);
152        if (i < 3)
153            assert(minmax_get(&minmax) == 1000);
154        else if (i == 3)
155            assert(minmax_get(&minmax) == 900);
156        else if (i == 4)
157            assert(minmax_get(&minmax) == 800);
158        else
159            assert(minmax_get(&minmax) == 600);
160    }
161}
162
163
164static void
165sample_changes_third_best_min (void)
166{
167    struct minmax minmax;
168    uint64_t rtt, now;
169
170    init_minmax(&minmax);
171    init_min_filter(&minmax);
172    rtt = minmax_get_idx(&minmax, 2);
173    rtt -= ms(5);
174    now = ms(101);
175    minmax_upmin(&minmax, now, rtt);
176    assert(rtt == minmax_get_idx(&minmax, 2));
177    assert(ms(30) == minmax_get_idx(&minmax, 1));
178    assert(ms(20) == minmax_get_idx(&minmax, 0));
179}
180
181
182static void
183sample_changes_third_best_max (void)
184{
185    struct minmax minmax;
186    uint64_t bw, now;
187
188    init_minmax(&minmax);
189    init_max_filter(&minmax);
190    bw = minmax_get_idx(&minmax, 2);
191    bw += 50;
192    now = ms(101);
193    minmax_upmax(&minmax, now, bw);
194    assert(bw == minmax_get_idx(&minmax, 2));
195    assert(800 == minmax_get_idx(&minmax, 1));
196    assert(900 == minmax_get_idx(&minmax, 0));
197}
198
199
200// RTT sample lower than the second-choice min sets that and also
201// the third-choice min.
202static void
203sample_changes_second_best_min (void)
204{
205    struct minmax minmax;
206    uint64_t rtt, now;
207
208    init_minmax(&minmax);
209    init_min_filter(&minmax);
210    rtt = minmax_get_idx(&minmax, 1);
211    rtt -= ms(5);
212    now = ms(101);
213    minmax_upmin(&minmax, now, rtt);
214    assert(rtt == minmax_get_idx(&minmax, 2));
215    assert(rtt == minmax_get_idx(&minmax, 1));
216    assert(ms(20) == minmax_get_idx(&minmax, 0));
217}
218
219
220// BW sample higher than the second-choice max sets that and also
221// the third-choice max.
222static void
223sample_changes_second_best_max (void)
224{
225    struct minmax minmax;
226    uint64_t bw, now;
227
228    init_minmax(&minmax);
229    init_max_filter(&minmax);
230    bw = minmax_get_idx(&minmax, 1);
231    bw += 50;
232    now = ms(101);
233    minmax_upmax(&minmax, now, bw);
234    assert(bw == minmax_get_idx(&minmax, 2));
235    assert(bw == minmax_get_idx(&minmax, 1));
236    assert(900 == minmax_get_idx(&minmax, 0));
237}
238
239
240// RTT sample lower than the first-choice min-rtt sets that and also
241// the second and third-choice mins.
242static void
243sample_changes_all_mins (void)
244{
245    struct minmax minmax;
246    uint64_t rtt, now;
247
248    init_minmax(&minmax);
249    init_min_filter(&minmax);
250    rtt = minmax_get(&minmax);
251    rtt -= ms(5);
252    now = ms(101);
253    minmax_upmin(&minmax, now, rtt);
254    assert(rtt == minmax_get_idx(&minmax, 2));
255    assert(rtt == minmax_get_idx(&minmax, 1));
256    assert(rtt == minmax_get_idx(&minmax, 0));
257}
258
259
260// BW sample higher than the first-choice max sets that and also
261// the second and third-choice maxs.
262static void
263sample_changes_all_maxs (void)
264{
265    struct minmax minmax;
266    uint64_t bw, now;
267
268    init_minmax(&minmax);
269    init_max_filter(&minmax);
270    bw = minmax_get(&minmax);
271    bw += 50;
272    now = ms(101);
273    minmax_upmax(&minmax, now, bw);
274    assert(bw == minmax_get_idx(&minmax, 2));
275    assert(bw == minmax_get_idx(&minmax, 1));
276    assert(bw == minmax_get_idx(&minmax, 0));
277}
278
279
280// Best min sample was recorded at 25ms, so expiry time is 124ms.
281static void
282expire_best_min (void)
283{
284    struct minmax minmax;
285    uint64_t rtt, now, old_2nd, old_3rd;
286
287    init_minmax(&minmax);
288    init_min_filter(&minmax);
289    old_3rd = minmax_get_idx(&minmax, 2);
290    old_2nd = minmax_get_idx(&minmax, 1);
291    rtt = old_3rd + ms(5);
292    now = ms(125);
293    minmax_upmin(&minmax, now, rtt);
294    assert(rtt == minmax_get_idx(&minmax, 2));
295    assert(old_3rd == minmax_get_idx(&minmax, 1));
296    assert(old_2nd == minmax_get(&minmax));
297}
298
299
300// Best max sample was recorded at 25ms, so expiry time is 124ms.
301static void
302expire_best_max (void)
303{
304    struct minmax minmax;
305    uint64_t bw, now, old_2nd, old_3rd;
306
307    init_minmax(&minmax);
308    init_max_filter(&minmax);
309    old_3rd = minmax_get_idx(&minmax, 2);
310    old_2nd = minmax_get_idx(&minmax, 1);
311    bw = old_3rd - 50;
312    now = ms(125);
313    minmax_upmax(&minmax, now, bw);
314    assert(bw == minmax_get_idx(&minmax, 2));
315    assert(old_3rd == minmax_get_idx(&minmax, 1));
316    assert(old_2nd == minmax_get(&minmax));
317}
318
319
320// Second best min sample was recorded at 75ms, so expiry time is 174ms.
321static void
322expire_second_best_min (void)
323{
324    struct minmax minmax;
325    uint64_t rtt, now, old_3rd;
326
327    init_minmax(&minmax);
328    init_min_filter(&minmax);
329    old_3rd = minmax_get_idx(&minmax, 2);
330    rtt = old_3rd + ms(5);
331    now = ms(175);
332    minmax_upmin(&minmax, now, rtt);
333    assert(rtt == minmax_get_idx(&minmax, 2));
334    assert(rtt == minmax_get_idx(&minmax, 1));
335    assert(old_3rd == minmax_get(&minmax));
336}
337
338
339// Second best max sample was recorded at 75ms, so expiry time is 174ms.
340static void
341expire_second_best_max (void)
342{
343    struct minmax minmax;
344    uint64_t bw, now, old_3rd;
345
346    init_minmax(&minmax);
347    init_max_filter(&minmax);
348    old_3rd = minmax_get_idx(&minmax, 2);
349    bw = old_3rd - 50;
350    now = ms(175);
351    minmax_upmax(&minmax, now, bw);
352    assert(bw == minmax_get_idx(&minmax, 2));
353    assert(bw == minmax_get_idx(&minmax, 1));
354    assert(old_3rd == minmax_get(&minmax));
355}
356
357
358// Third best min sample was recorded at 100ms, so expiry time is 199ms.
359static void
360expire_all_mins (void)
361{
362    struct minmax minmax;
363    uint64_t rtt, now, old_3rd;
364
365    init_minmax(&minmax);
366    init_min_filter(&minmax);
367    old_3rd = minmax_get_idx(&minmax, 2);
368    rtt = old_3rd + ms(5);
369    now = ms(200);
370    minmax_upmin(&minmax, now, rtt);
371    assert(rtt == minmax_get_idx(&minmax, 2));
372    assert(rtt == minmax_get_idx(&minmax, 1));
373    assert(rtt == minmax_get(&minmax));
374}
375
376
377// Third best max sample was recorded at 100ms, so expiry time is 199ms.
378static void
379expire_all_maxs (void)
380{
381    struct minmax minmax;
382    uint64_t bw, now, old_3rd;
383
384    init_minmax(&minmax);
385    init_max_filter(&minmax);
386    old_3rd = minmax_get_idx(&minmax, 2);
387    bw = old_3rd - 50;
388    now = ms(200);
389    minmax_upmax(&minmax, now, bw);
390    assert(bw == minmax_get_idx(&minmax, 2));
391    assert(bw == minmax_get_idx(&minmax, 1));
392    assert(bw == minmax_get(&minmax));
393}
394
395
396// Test the windowed filter where the time used is an exact counter instead of a
397// timestamp.  This is useful if, for example, the time is measured in round
398// trips.
399static void
400expire_counter_based_max (void)
401{
402    struct minmax minmax;
403
404    // Create a window which starts at t = 0 and expires after two cycles.
405    minmax_init(&minmax, 2);
406
407    const uint64_t kBest = 50000;
408    // Insert 50000 at t = 1.
409    minmax_upmax(&minmax, 1, 50000);
410    assert(kBest == minmax_get(&minmax));
411    update_with_irrelevant_samples(&minmax, 20, 1);
412    assert(kBest == minmax_get(&minmax));
413
414    // Insert 40000 at t = 2.  Nothing is expected to expire.
415    minmax_upmax(&minmax, 2, 40000);
416    assert(kBest == minmax_get(&minmax));
417    update_with_irrelevant_samples(&minmax, 20, 2);
418    assert(kBest == minmax_get(&minmax));
419
420    // Insert 30000 at t = 3.  Nothing is expected to expire yet.
421    minmax_upmax(&minmax, 3, 30000);
422    assert(kBest == minmax_get(&minmax));
423    update_with_irrelevant_samples(&minmax, 20, 3);
424    assert(kBest == minmax_get(&minmax));
425
426    // Insert 20000 at t = 4.  50000 at t = 1 expires, so 40000 becomes the new
427    // maximum.
428    const uint64_t kNewBest = 40000;
429    minmax_upmax(&minmax, 4, 20000);
430    assert(kNewBest == minmax_get(&minmax));
431    update_with_irrelevant_samples(&minmax, 20, 4);
432    assert(kNewBest == minmax_get(&minmax));
433}
434
435
436int
437main (void)
438{
439    test_uninitialized_estimates();
440    test_monotonically_increasing_min();
441    test_monotonically_decreasing_max();
442    sample_changes_third_best_min();
443    sample_changes_third_best_max();
444    sample_changes_second_best_min();
445    sample_changes_second_best_max();
446    sample_changes_all_mins();
447    sample_changes_all_maxs();
448    expire_best_min();
449    expire_best_max();
450    expire_second_best_min();
451    expire_second_best_max();
452    expire_all_mins();
453    expire_all_maxs();
454    expire_counter_based_max();
455
456    return 0;
457}
458