/src/h2o/deps/quicly/lib/rate.c

Source (jump to first uncovered line)
/*
 * Copyright (c) 2021 Fastly, Kazuho Oku
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */

#include <math.h>
#include "picotls.h"
#include "quicly/rate.h"

static void start_sampling(quicly_ratemeter_t *meter, int64_t now, uint64_t bytes_acked)
{
    meter->current.start.at = now;
    meter->current.start.bytes_acked = bytes_acked;
}

static void commit_sample(quicly_ratemeter_t *meter)
{
    ++meter->past_samples.latest;
    if (meter->past_samples.latest >= PTLS_ELEMENTSOF(meter->past_samples.entries))
        meter->past_samples.latest = 0;
    meter->past_samples.entries[meter->past_samples.latest] = meter->current.sample;

    meter->current.start.at = INT64_MAX;
    meter->current.sample = (struct st_quicly_rate_sample_t){};
}

void quicly_ratemeter_init(quicly_ratemeter_t *meter)
{
    *meter = (quicly_ratemeter_t){
        .past_samples = {.latest = PTLS_ELEMENTSOF(meter->past_samples.entries) - 1},
        .pn_cwnd_limited = {.start = UINT64_MAX, .end = UINT64_MAX},
        .current = {.start = {.at = INT64_MAX}},
    };
}

void quicly_ratemeter_in_cwnd_limited(quicly_ratemeter_t *meter, uint64_t pn)
{
    /* bail out if already in cwnd-limited phase */
    if (meter->pn_cwnd_limited.start != UINT64_MAX && meter->pn_cwnd_limited.end == UINT64_MAX)
        return;

    /* if the estimator was waiting for the end of the previous phase, and if a valid partial sample exists, commit it now */
    if (meter->pn_cwnd_limited.end != UINT64_MAX && meter->current.sample.elapsed != 0)
        commit_sample(meter);

    /* begin new cwnd-limited phase */
    meter->pn_cwnd_limited = (quicly_range_t){.start = pn, .end = UINT64_MAX};
}

void quicly_ratemeter_not_cwnd_limited(quicly_ratemeter_t *meter, uint64_t pn)
{
    if (meter->pn_cwnd_limited.start != UINT64_MAX && meter->pn_cwnd_limited.end == UINT64_MAX)
        meter->pn_cwnd_limited.end = pn;
}

void quicly_ratemeter_on_ack(quicly_ratemeter_t *meter, int64_t now, uint64_t bytes_acked, uint64_t pn)
{
    if (meter->pn_cwnd_limited.start <= pn && pn < meter->pn_cwnd_limited.end) {
        /* At the moment, the flow is CWND-limited. Either start the timer or update. */
        if (meter->current.start.at == INT64_MAX) {
            start_sampling(meter, now, bytes_acked);
        } else {
            /* Update current sample whenever receiving an ACK, so that the sample can be committed other than when receiving an ACK
             * (i.e., when opening a new CWND-limited phase). */
            meter->current.sample = (struct st_quicly_rate_sample_t){
                .elapsed = (uint32_t)(now - meter->current.start.at),
                .bytes_acked = (uint32_t)(bytes_acked - meter->current.start.bytes_acked),
            };
            if (meter->current.sample.elapsed >= QUICLY_DELIVERY_RATE_SAMPLE_PERIOD) {
                commit_sample(meter);
                start_sampling(meter, now, bytes_acked);
            }
        }
    } else if (meter->pn_cwnd_limited.end <= pn) {
        /* We have exited CWND-limited state. Save current value, if any. */
        if (meter->current.start.at != INT64_MAX) {
            if (meter->current.sample.elapsed != 0)
                commit_sample(meter);
            meter->pn_cwnd_limited = (quicly_range_t){.start = UINT64_MAX, .end = UINT64_MAX};
            meter->current.start.at = INT64_MAX;
        }
    }
}

static uint64_t to_speed(uint64_t bytes_acked, uint32_t elapsed)
{
    return bytes_acked * 1000 / elapsed;
}

void quicly_ratemeter_report(quicly_ratemeter_t *meter, quicly_rate_t *rate)
{
    { /* Calculate latest, or return if there are no samples at all. `latest` being reported will be the most recent "full" sample
       * if available, or else a partial sample. */
        const struct st_quicly_rate_sample_t *latest_sample = &meter->past_samples.entries[meter->past_samples.latest];
        if (latest_sample->elapsed == 0) {
            latest_sample = &meter->current.sample;
            if (latest_sample->elapsed == 0) {
                rate->latest = rate->smoothed = rate->stdev = 0;
                return;
            }
        }
        rate->latest = to_speed(latest_sample->bytes_acked, latest_sample->elapsed);
    }

#define FOREACH_SAMPLE(func)                                                                                                       \
    do {                                                                                                                           \
        const struct st_quicly_rate_sample_t *sample;                                                                              \
        for (size_t i = 0; i < PTLS_ELEMENTSOF(meter->past_samples.entries); ++i) {                                                \
            if ((sample = &meter->past_samples.entries[i])->elapsed != 0) {                                                        \
                func                                                                                                               \
            }                                                                                                                      \
        }                                                                                                                          \
        if ((sample = &meter->current.sample)->elapsed != 0) {                                                                     \
            func                                                                                                                   \
        }                                                                                                                          \
    } while (0)

    { /* calculate average */
        uint64_t total_acked = 0;
        uint32_t total_elapsed = 0;
        FOREACH_SAMPLE({
            total_acked += sample->bytes_acked;
            total_elapsed += sample->elapsed;
        });
        rate->smoothed = to_speed(total_acked, total_elapsed);
    }

    { /* calculate stdev */
        uint64_t sum = 0;
        size_t count = 0;
        FOREACH_SAMPLE({
            uint64_t sample_speed = to_speed(sample->bytes_acked, sample->elapsed);
            sum += (sample_speed - rate->smoothed) * (sample_speed - rate->smoothed);
            ++count;
        });
        rate->stdev = sqrt(sum / count);
    }

#undef FOREACH_SAMPLE
}

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) 2021 Fastly, Kazuho Oku
3		*
4		* Permission is hereby granted, free of charge, to any person obtaining a copy
5		* of this software and associated documentation files (the "Software"), to
6		* deal in the Software without restriction, including without limitation the
7		* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8		* sell copies of the Software, and to permit persons to whom the Software is
9		* furnished to do so, subject to the following conditions:
10		*
11		* The above copyright notice and this permission notice shall be included in
12		* all copies or substantial portions of the Software.
13		*
14		* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15		* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16		* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17		* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18		* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19		* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20		* IN THE SOFTWARE.
21		*/
22
23		#include <math.h>
24		#include "picotls.h"
25		#include "quicly/rate.h"
26
27		static void start_sampling(quicly_ratemeter_t *meter, int64_t now, uint64_t bytes_acked)
28	0	{
29	0	meter->current.start.at = now;
30	0	meter->current.start.bytes_acked = bytes_acked;
31	0	}
32
33		static void commit_sample(quicly_ratemeter_t *meter)
34	0	{
35	0	++meter->past_samples.latest;
36	0	if (meter->past_samples.latest >= PTLS_ELEMENTSOF(meter->past_samples.entries))
37	0	meter->past_samples.latest = 0;
38	0	meter->past_samples.entries[meter->past_samples.latest] = meter->current.sample;
39
40	0	meter->current.start.at = INT64_MAX;
41	0	meter->current.sample = (struct st_quicly_rate_sample_t){};
42	0	}
43
44		void quicly_ratemeter_init(quicly_ratemeter_t *meter)
45	0	{
46	0	*meter = (quicly_ratemeter_t){
47	0	.past_samples = {.latest = PTLS_ELEMENTSOF(meter->past_samples.entries) - 1},
48	0	.pn_cwnd_limited = {.start = UINT64_MAX, .end = UINT64_MAX},
49	0	.current = {.start = {.at = INT64_MAX}},
50	0	};
51	0	}
52
53		void quicly_ratemeter_in_cwnd_limited(quicly_ratemeter_t *meter, uint64_t pn)
54	0	{
55		/* bail out if already in cwnd-limited phase */
56	0	if (meter->pn_cwnd_limited.start != UINT64_MAX && meter->pn_cwnd_limited.end == UINT64_MAX)
57	0	return;
58
59		/* if the estimator was waiting for the end of the previous phase, and if a valid partial sample exists, commit it now */
60	0	if (meter->pn_cwnd_limited.end != UINT64_MAX && meter->current.sample.elapsed != 0)
61	0	commit_sample(meter);
62
63		/* begin new cwnd-limited phase */
64	0	meter->pn_cwnd_limited = (quicly_range_t){.start = pn, .end = UINT64_MAX};
65	0	}
66
67		void quicly_ratemeter_not_cwnd_limited(quicly_ratemeter_t *meter, uint64_t pn)
68	0	{
69	0	if (meter->pn_cwnd_limited.start != UINT64_MAX && meter->pn_cwnd_limited.end == UINT64_MAX)
70	0	meter->pn_cwnd_limited.end = pn;
71	0	}
72
73		void quicly_ratemeter_on_ack(quicly_ratemeter_t *meter, int64_t now, uint64_t bytes_acked, uint64_t pn)
74	0	{
75	0	if (meter->pn_cwnd_limited.start <= pn && pn < meter->pn_cwnd_limited.end) {
76		/* At the moment, the flow is CWND-limited. Either start the timer or update. */
77	0	if (meter->current.start.at == INT64_MAX) {
78	0	start_sampling(meter, now, bytes_acked);
79	0	} else {
80		/* Update current sample whenever receiving an ACK, so that the sample can be committed other than when receiving an ACK
81		* (i.e., when opening a new CWND-limited phase). */
82	0	meter->current.sample = (struct st_quicly_rate_sample_t){
83	0	.elapsed = (uint32_t)(now - meter->current.start.at),
84	0	.bytes_acked = (uint32_t)(bytes_acked - meter->current.start.bytes_acked),
85	0	};
86	0	if (meter->current.sample.elapsed >= QUICLY_DELIVERY_RATE_SAMPLE_PERIOD) {
87	0	commit_sample(meter);
88	0	start_sampling(meter, now, bytes_acked);
89	0	}
90	0	}
91	0	} else if (meter->pn_cwnd_limited.end <= pn) {
92		/* We have exited CWND-limited state. Save current value, if any. */
93	0	if (meter->current.start.at != INT64_MAX) {
94	0	if (meter->current.sample.elapsed != 0)
95	0	commit_sample(meter);
96	0	meter->pn_cwnd_limited = (quicly_range_t){.start = UINT64_MAX, .end = UINT64_MAX};
97	0	meter->current.start.at = INT64_MAX;
98	0	}
99	0	}
100	0	}
101
102		static uint64_t to_speed(uint64_t bytes_acked, uint32_t elapsed)
103	0	{
104	0	return bytes_acked * 1000 / elapsed;
105	0	}
106
107		void quicly_ratemeter_report(quicly_ratemeter_t meter, quicly_rate_t rate)
108	0	{
109	0	{ /* Calculate latest, or return if there are no samples at all. `latest` being reported will be the most recent "full" sample
110		* if available, or else a partial sample. */
111	0	const struct st_quicly_rate_sample_t *latest_sample = &meter->past_samples.entries[meter->past_samples.latest];
112	0	if (latest_sample->elapsed == 0) {
113	0	latest_sample = &meter->current.sample;
114	0	if (latest_sample->elapsed == 0) {
115	0	rate->latest = rate->smoothed = rate->stdev = 0;
116	0	return;
117	0	}
118	0	}
119	0	rate->latest = to_speed(latest_sample->bytes_acked, latest_sample->elapsed);
120	0	}
121
122	0	#define FOREACH_SAMPLE(func) \
123	0	do { \
124	0	const struct st_quicly_rate_sample_t *sample; \
125	0	for (size_t i = 0; i < PTLS_ELEMENTSOF(meter->past_samples.entries); ++i) { \
126	0	if ((sample = &meter->past_samples.entries[i])->elapsed != 0) { \
127	0	func \
128	0	} \
129	0	} \
130	0	if ((sample = &meter->current.sample)->elapsed != 0) { \
131	0	func \
132	0	} \
133	0	} while (0)
134
135	0	{ /* calculate average */
136	0	uint64_t total_acked = 0;
137	0	uint32_t total_elapsed = 0;
138	0	FOREACH_SAMPLE({
139	0	total_acked += sample->bytes_acked;
140	0	total_elapsed += sample->elapsed;
141	0	});
142	0	rate->smoothed = to_speed(total_acked, total_elapsed);
143	0	}
144
145	0	{ /* calculate stdev */
146	0	uint64_t sum = 0;
147	0	size_t count = 0;
148	0	FOREACH_SAMPLE({
149	0	uint64_t sample_speed = to_speed(sample->bytes_acked, sample->elapsed);
150	0	sum += (sample_speed - rate->smoothed) * (sample_speed - rate->smoothed);
151	0	++count;
152	0	});
153	0	rate->stdev = sqrt(sum / count);
154	0	}
155
156	0	#undef FOREACH_SAMPLE
157	0	}

Coverage Report

Created: 2023-06-07 06:21