/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_enter_cc_limited(quicly_ratemeter_t *meter, uint64_t pn)
{
    assert(!quicly_ratemeter_is_cc_limited(meter));

    /* 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_exit_cc_limited(quicly_ratemeter_t *meter, uint64_t pn)
{
    assert(quicly_ratemeter_is_cc_limited(meter));

    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_enter_cc_limited(quicly_ratemeter_t *meter, uint64_t pn)
54	0	{
55	0	assert(!quicly_ratemeter_is_cc_limited(meter));
56
57		/* if the estimator was waiting for the end of the previous phase, and if a valid partial sample exists, commit it now */
58	0	if (meter->pn_cwnd_limited.end != UINT64_MAX && meter->current.sample.elapsed != 0)
59	0	commit_sample(meter);
60
61		/* begin new cwnd-limited phase */
62	0	meter->pn_cwnd_limited = (quicly_range_t){.start = pn, .end = UINT64_MAX};
63	0	}
64
65		void quicly_ratemeter_exit_cc_limited(quicly_ratemeter_t *meter, uint64_t pn)
66	0	{
67	0	assert(quicly_ratemeter_is_cc_limited(meter));
68
69	0	meter->pn_cwnd_limited.end = pn;
70	0	}
71
72		void quicly_ratemeter_on_ack(quicly_ratemeter_t *meter, int64_t now, uint64_t bytes_acked, uint64_t pn)
73	0	{
74	0	if (meter->pn_cwnd_limited.start <= pn && pn < meter->pn_cwnd_limited.end) {
75		/* At the moment, the flow is CWND-limited. Either start the timer or update. */
76	0	if (meter->current.start.at == INT64_MAX) {
77	0	start_sampling(meter, now, bytes_acked);
78	0	} else {
79		/* Update current sample whenever receiving an ACK, so that the sample can be committed other than when receiving an ACK
80		* (i.e., when opening a new CWND-limited phase). */
81	0	meter->current.sample = (struct st_quicly_rate_sample_t){
82	0	.elapsed = (uint32_t)(now - meter->current.start.at),
83	0	.bytes_acked = (uint32_t)(bytes_acked - meter->current.start.bytes_acked),
84	0	};
85	0	if (meter->current.sample.elapsed >= QUICLY_DELIVERY_RATE_SAMPLE_PERIOD) {
86	0	commit_sample(meter);
87	0	start_sampling(meter, now, bytes_acked);
88	0	}
89	0	}
90	0	} else if (meter->pn_cwnd_limited.end <= pn) {
91		/* We have exited CWND-limited state. Save current value, if any. */
92	0	if (meter->current.start.at != INT64_MAX) {
93	0	if (meter->current.sample.elapsed != 0)
94	0	commit_sample(meter);
95	0	meter->pn_cwnd_limited = (quicly_range_t){.start = UINT64_MAX, .end = UINT64_MAX};
96	0	meter->current.start.at = INT64_MAX;
97	0	}
98	0	}
99	0	}
100
101		static uint64_t to_speed(uint64_t bytes_acked, uint32_t elapsed)
102	0	{
103	0	return bytes_acked * 1000 / elapsed;
104	0	}
105
106		void quicly_ratemeter_report(quicly_ratemeter_t meter, quicly_rate_t rate)
107	0	{
108	0	{ /* Calculate latest, or return if there are no samples at all. `latest` being reported will be the most recent "full" sample
109		* if available, or else a partial sample. */
110	0	const struct st_quicly_rate_sample_t *latest_sample = &meter->past_samples.entries[meter->past_samples.latest];
111	0	if (latest_sample->elapsed == 0) {
112	0	latest_sample = &meter->current.sample;
113	0	if (latest_sample->elapsed == 0) {
114	0	rate->latest = rate->smoothed = rate->stdev = 0;
115	0	return;
116	0	}
117	0	}
118	0	rate->latest = to_speed(latest_sample->bytes_acked, latest_sample->elapsed);
119	0	}
120
121	0	#define FOREACH_SAMPLE(func) \
122	0	do { \
123	0	const struct st_quicly_rate_sample_t *sample; \
124	0	for (size_t i = 0; i < PTLS_ELEMENTSOF(meter->past_samples.entries); ++i) { \
125	0	if ((sample = &meter->past_samples.entries[i])->elapsed != 0) { \
126	0	func \
127	0	} \
128	0	} \
129	0	if ((sample = &meter->current.sample)->elapsed != 0) { \
130	0	func \
131	0	} \
132	0	} while (0)
133
134	0	{ /* calculate average */
135	0	uint64_t total_acked = 0;
136	0	uint32_t total_elapsed = 0;
137	0	FOREACH_SAMPLE({
138	0	total_acked += sample->bytes_acked;
139	0	total_elapsed += sample->elapsed;
140	0	});
141	0	rate->smoothed = to_speed(total_acked, total_elapsed);
142	0	}
143
144	0	{ /* calculate stdev */
145	0	uint64_t sum = 0;
146	0	size_t count = 0;
147	0	FOREACH_SAMPLE({
148	0	uint64_t sample_speed = to_speed(sample->bytes_acked, sample->elapsed);
149	0	sum += (sample_speed - rate->smoothed) * (sample_speed - rate->smoothed);
150	0	++count;
151	0	});
152	0	rate->stdev = sqrt(sum / count);
153	0	}
154
155	0	#undef FOREACH_SAMPLE
156	0	}

Coverage Report

Created: 2025-06-22 06:18