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