/src/curl/lib/ratelimit.c

Source
/***************************************************************************
 *                                  _   _ ____  _
 *  Project                     ___| | | |  _ \| |
 *                             / __| | | | |_) | |
 *                            | (__| |_| |  _ <| |___
 *                             \___|\___/|_| \_\_____|
 *
 * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution. The terms
 * are also available at https://curl.se/docs/copyright.html.
 *
 * You may opt to use, copy, modify, merge, publish, distribute and/or sell
 * copies of the Software, and permit persons to whom the Software is
 * furnished to do so, under the terms of the COPYING file.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 * SPDX-License-Identifier: curl
 *
 ***************************************************************************/
#include "curl_setup.h"

#include "urldata.h"
#include "ratelimit.h"

#define CURL_US_PER_SEC         1000000
#define CURL_RLIMIT_MIN_RATE    (4 * 1024)  /* minimum step rate */
#define CURL_RLIMIT_STEP_MIN_MS 2  /* minimum step duration */

static void rlimit_update(struct Curl_rlimit *r,
                          const struct curltime *pts)
{
  timediff_t elapsed_us, elapsed_steps;
  int64_t token_gain;

  DEBUGASSERT(r->rate_per_step);
  if((r->ts.tv_sec == pts->tv_sec) && (r->ts.tv_usec == pts->tv_usec))
    return;

  elapsed_us = curlx_ptimediff_us(pts, &r->ts);
  if(elapsed_us < 0) { /* not going back in time */
    DEBUGASSERT(0);
    return;
  }

  elapsed_us += r->spare_us;
  if(elapsed_us < r->step_us)
    return;

  /* we do the update */
  r->ts = *pts;
  elapsed_steps = elapsed_us / r->step_us;
  r->spare_us = elapsed_us % r->step_us;

  /* How many tokens did we gain since the last update? */
  if(r->rate_per_step > (INT64_MAX / elapsed_steps))
    token_gain = INT64_MAX;
  else {
    token_gain = r->rate_per_step * elapsed_steps;
  }

  if((INT64_MAX - token_gain) > r->tokens)
    r->tokens += token_gain;
  else
    r->tokens = INT64_MAX;

  /* Limit the token again by the burst rate (if set), so we
   * do not suddenly have a huge number of tokens after inactivity. */
  if(r->burst_per_step && (r->tokens > r->burst_per_step)) {
    r->tokens = r->burst_per_step;
  }
}

static void rlimit_tune_steps(struct Curl_rlimit *r,
                              int64_t tokens_total)
{
  int64_t tokens_last, tokens_main, msteps;

  /* Tune the ratelimit at the start *if* we know how many tokens
   * are expected to be consumed in total.
   * The reason for tuning is that rlimit provides tokens to be consumed
   * per "step" which starts out to be a second. The tokens may be consumed
   * in full at the beginning of a step. The remainder of the second will
   * have no tokens available, effectively blocking the consumption and
   * so keeping the "step average" in line.
   * This works will up to the last step. When no more tokens are needed,
   * no wait will happen and the last step would be too fast. This is
   * especially noticeable when only a few steps are needed.
   *
   * Example: downloading 1.5kb with a ratelimit of 1k could be done in
   * roughly 1 second (1k in the first second and the 0.5 at the start of
   * the second one).
   *
   * The tuning tries to make the last step small, using only
   * 1 percent of the total tokens (at least 1). The rest of the tokens
   * are to be consumed in the steps before by adjusting the duration of
   * the step and the amount of tokens it provides. */
  if(!r->rate_per_step ||
     (tokens_total <= 1) ||
     (tokens_total > (INT64_MAX / 1000)))
    return;

  /* Calculate tokens for the last step and the ones before. */
  tokens_last = tokens_total / 100;
  if(!tokens_last) /* less than 100 total, use 1 */
    tokens_last = 1;
  else if(tokens_last > CURL_RLIMIT_MIN_RATE)
    tokens_last = CURL_RLIMIT_MIN_RATE;
  DEBUGASSERT(tokens_last);
  tokens_main = tokens_total - tokens_last;
  DEBUGASSERT(tokens_main);

  /* how many milli-steps will it take to consume those, give the
  * original rate limit per second? */
  DEBUGASSERT(r->step_us == CURL_US_PER_SEC);

  msteps = (tokens_main * 1000 / r->rate_per_step);
  if(msteps < CURL_RLIMIT_STEP_MIN_MS) {
    /* Steps this small will not work. Do not tune. */
    return;
  }
  else if(msteps < 1000) {
    /* It needs less than one step to provide the needed tokens.
     * Make it exactly that long and with exactly those tokens. */
    r->step_us = (timediff_t)msteps * 1000;
    r->rate_per_step = tokens_main;
    r->tokens = r->rate_per_step;
  }
  else {
    /* More than 1 step. Spread the remainder milli steps and
     * the tokens they need to provide across all steps. If integer
     * arithmetic can do it. */
    curl_off_t ms_unaccounted = (msteps % 1000);
    curl_off_t mstep_inc = (ms_unaccounted / (msteps / 1000));
    if(mstep_inc) {
      curl_off_t rate_inc = ((r->rate_per_step * mstep_inc) / 1000);
      if(rate_inc) {
        r->step_us = CURL_US_PER_SEC + ((timediff_t)mstep_inc * 1000);
        r->rate_per_step += rate_inc;
        r->tokens = r->rate_per_step;
        if(r->burst_per_step) {
          curl_off_t burst_inc = ((r->burst_per_step * mstep_inc) / 1000);
          if(burst_inc)
            r->burst_per_step += burst_inc;
        }
      }
    }
  }
}

void Curl_rlimit_init(struct Curl_rlimit *r,
                      int64_t rate_per_sec,
                      int64_t burst_per_sec,
                      const struct curltime *pts)
{
  DEBUGASSERT(rate_per_sec >= 0);
  DEBUGASSERT(burst_per_sec >= rate_per_sec || !burst_per_sec);
  DEBUGASSERT(pts);
  r->rate_per_step = r->rate_per_sec = rate_per_sec;
  r->burst_per_step = r->burst_per_sec = burst_per_sec;
  r->step_us = CURL_US_PER_SEC;
  r->spare_us = 0;
  r->tokens = r->rate_per_step;
  r->ts = *pts;
  r->blocked = FALSE;
}

void Curl_rlimit_start(struct Curl_rlimit *r, const struct curltime *pts,
                       int64_t total_tokens)
{
  /* A start always resets the values to initial defaults, then
   * fine tunes the intervals for the total_tokens expected. */
  r->rate_per_step = r->rate_per_sec;
  r->burst_per_step = r->burst_per_sec;
  r->step_us = CURL_US_PER_SEC;
  r->spare_us = 0;
  r->tokens = r->rate_per_step;
  r->ts = *pts;
  rlimit_tune_steps(r, total_tokens);
}

int64_t Curl_rlimit_per_step(struct Curl_rlimit *r)
{
  return r->rate_per_step;
}

bool Curl_rlimit_active(struct Curl_rlimit *r)
{
  return (r->rate_per_step > 0) || r->blocked;
}

bool Curl_rlimit_is_blocked(struct Curl_rlimit *r)
{
  return (bool)r->blocked;
}

int64_t Curl_rlimit_avail(struct Curl_rlimit *r,
                          const struct curltime *pts)
{
  struct curltime ts;

  if(r->blocked)
    return 0;
  else if(r->rate_per_step) {
    if(!pts) {
      curlx_pnow(&ts);
      pts = &ts;
    }
    rlimit_update(r, pts);
    return r->tokens;
  }
  else
    return INT64_MAX;
}

void Curl_rlimit_drain(struct Curl_rlimit *r, size_t tokens,
                       const struct curltime *pts)
{
  struct curltime ts;

  if(r->blocked || !r->rate_per_step)
    return;

  if(!pts) {
    curlx_pnow(&ts);
    pts = &ts;
  }
  rlimit_update(r, pts);
#if 8 <= SIZEOF_SIZE_T
  if(tokens > INT64_MAX) {
    r->tokens = INT64_MAX;
  }
  else
#endif
  {
    int64_t val = (int64_t)tokens;
    if((INT64_MIN + val) < r->tokens)
      r->tokens -= val;
    else
      r->tokens = INT64_MIN;
  }
}

timediff_t Curl_rlimit_wait_ms(struct Curl_rlimit *r,
                               const struct curltime *pts)
{
  timediff_t wait_us, elapsed_us;

  if(r->blocked || !r->rate_per_step)
    return 0;
  rlimit_update(r, pts);
  if(r->tokens > 0)
    return 0;

  /* How much time will it take tokens to become positive again?
   * Deduct `spare_us` and check against already elapsed time */
  wait_us = r->step_us - r->spare_us;
  if(r->tokens < 0) {
    curl_off_t debt_pct = ((-r->tokens) * 100 / r->rate_per_step);
    if(debt_pct)
      wait_us += (r->step_us * debt_pct / 100);
  }

  elapsed_us = curlx_ptimediff_us(pts, &r->ts);
  if(elapsed_us >= wait_us)
    return 0;
  wait_us -= elapsed_us;
  return (wait_us + 999) / 1000; /* in milliseconds */
}

timediff_t Curl_rlimit_next_step_ms(struct Curl_rlimit *r,
                                    const struct curltime *pts)
{
  if(!r->blocked && r->rate_per_step) {
    timediff_t elapsed_us, next_us;

    elapsed_us = curlx_ptimediff_us(pts, &r->ts) + r->spare_us;
    if(r->step_us > elapsed_us) {
      next_us = r->step_us - elapsed_us;
      return (next_us + 999) / 1000; /* in milliseconds */
    }
  }
  return 0;
}

void Curl_rlimit_block(struct Curl_rlimit *r,
                       bool activate,
                       const struct curltime *pts)
{
  if(!activate == !r->blocked)
    return;

  r->ts = *pts;
  r->blocked = activate;
  if(!r->blocked) {
    /* Start rate limiting fresh. The amount of time this was blocked
     * does not generate extra tokens. */
    Curl_rlimit_start(r, pts, -1);
  }
  else {
    r->tokens = 0;
  }
}

Coverage Report

Created: 2026-09-04 07:16

Line	Count	Source
1		/***************************************************************************
2		* _ _ ____ _
3		* Project ___\| \| \| \| _ \\| \|
4		* / __\| \| \| \| \|_) \| \|
5		* \| (__\| \|_\| \| _ <\| \|___
6		* \___\|\___/\|_\| \_\_____\|
7		*
8		* Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
9		*
10		* This software is licensed as described in the file COPYING, which
11		* you should have received as part of this distribution. The terms
12		* are also available at https://curl.se/docs/copyright.html.
13		*
14		* You may opt to use, copy, modify, merge, publish, distribute and/or sell
15		* copies of the Software, and permit persons to whom the Software is
16		* furnished to do so, under the terms of the COPYING file.
17		*
18		* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19		* KIND, either express or implied.
20		*
21		* SPDX-License-Identifier: curl
22		*
23		***************************************************************************/
24		#include "curl_setup.h"
25
26		#include "urldata.h"
27		#include "ratelimit.h"
28
29	6.77k	#define CURL_US_PER_SEC 1000000
30	27	#define CURL_RLIMIT_MIN_RATE (4 * 1024) /* minimum step rate */
31	43	#define CURL_RLIMIT_STEP_MIN_MS 2 /* minimum step duration */
32
33		static void rlimit_update(struct Curl_rlimit *r,
34		const struct curltime *pts)
35	11.4k	{
36	11.4k	timediff_t elapsed_us, elapsed_steps;
37	11.4k	int64_t token_gain;
38
39	11.4k	DEBUGASSERT(r->rate_per_step);
40	11.4k	if((r->ts.tv_sec == pts->tv_sec) && (r->ts.tv_usec == pts->tv_usec))
41	302	return;
42
43	11.1k	elapsed_us = curlx_ptimediff_us(pts, &r->ts);
44	11.1k	if(elapsed_us < 0) { /* not going back in time */
45	0	DEBUGASSERT(0);
46	0	return;
47	0	}
48
49	11.1k	elapsed_us += r->spare_us;
50	11.1k	if(elapsed_us < r->step_us)
51	11.1k	return;
52
53		/* we do the update */
54	2	r->ts = *pts;
55	2	elapsed_steps = elapsed_us / r->step_us;
56	2	r->spare_us = elapsed_us % r->step_us;
57
58		/* How many tokens did we gain since the last update? */
59	2	if(r->rate_per_step > (INT64_MAX / elapsed_steps))
60	0	token_gain = INT64_MAX;
61	2	else {
62	2	token_gain = r->rate_per_step * elapsed_steps;
63	2	}
64
65	2	if((INT64_MAX - token_gain) > r->tokens)
66	2	r->tokens += token_gain;
67	0	else
68	0	r->tokens = INT64_MAX;
69
70		/* Limit the token again by the burst rate (if set), so we
71		* do not suddenly have a huge number of tokens after inactivity. */
72	2	if(r->burst_per_step && (r->tokens > r->burst_per_step)) {
73	0	r->tokens = r->burst_per_step;
74	0	}
75	2	}
76
77		static void rlimit_tune_steps(struct Curl_rlimit *r,
78		int64_t tokens_total)
79	5.45k	{
80	5.45k	int64_t tokens_last, tokens_main, msteps;
81
82		/* Tune the ratelimit at the start if we know how many tokens
83		* are expected to be consumed in total.
84		* The reason for tuning is that rlimit provides tokens to be consumed
85		* per "step" which starts out to be a second. The tokens may be consumed
86		* in full at the beginning of a step. The remainder of the second will
87		* have no tokens available, effectively blocking the consumption and
88		* so keeping the "step average" in line.
89		* This works will up to the last step. When no more tokens are needed,
90		* no wait will happen and the last step would be too fast. This is
91		* especially noticeable when only a few steps are needed.
92		*
93		* Example: downloading 1.5kb with a ratelimit of 1k could be done in
94		* roughly 1 second (1k in the first second and the 0.5 at the start of
95		* the second one).
96		*
97		* The tuning tries to make the last step small, using only
98		* 1 percent of the total tokens (at least 1). The rest of the tokens
99		* are to be consumed in the steps before by adjusting the duration of
100		* the step and the amount of tokens it provides. */
101	5.45k	if(!r->rate_per_step \|\|
102	658	(tokens_total <= 1) \|\|
103	43	(tokens_total > (INT64_MAX / 1000)))
104	5.40k	return;
105
106		/* Calculate tokens for the last step and the ones before. */
107	43	tokens_last = tokens_total / 100;
108	43	if(!tokens_last) /* less than 100 total, use 1 */
109	17	tokens_last = 1;
110	26	else if(tokens_last > CURL_RLIMIT_MIN_RATE)
111	1	tokens_last = CURL_RLIMIT_MIN_RATE;
112	43	DEBUGASSERT(tokens_last);
113	43	tokens_main = tokens_total - tokens_last;
114	43	DEBUGASSERT(tokens_main);
115
116		/* how many milli-steps will it take to consume those, give the
117		* original rate limit per second? */
118	43	DEBUGASSERT(r->step_us == CURL_US_PER_SEC);
119
120	43	msteps = (tokens_main * 1000 / r->rate_per_step);
121	43	if(msteps < CURL_RLIMIT_STEP_MIN_MS) {
122		/* Steps this small will not work. Do not tune. */
123	13	return;
124	13	}
125	30	else if(msteps < 1000) {
126		/* It needs less than one step to provide the needed tokens.
127		* Make it exactly that long and with exactly those tokens. */
128	9	r->step_us = (timediff_t)msteps * 1000;
129	9	r->rate_per_step = tokens_main;
130	9	r->tokens = r->rate_per_step;
131	9	}
132	21	else {
133		/* More than 1 step. Spread the remainder milli steps and
134		* the tokens they need to provide across all steps. If integer
135		* arithmetic can do it. */
136	21	curl_off_t ms_unaccounted = (msteps % 1000);
137	21	curl_off_t mstep_inc = (ms_unaccounted / (msteps / 1000));
138	21	if(mstep_inc) {
139	19	curl_off_t rate_inc = ((r->rate_per_step * mstep_inc) / 1000);
140	19	if(rate_inc) {
141	16	r->step_us = CURL_US_PER_SEC + ((timediff_t)mstep_inc * 1000);
142	16	r->rate_per_step += rate_inc;
143	16	r->tokens = r->rate_per_step;
144	16	if(r->burst_per_step) {
145	16	curl_off_t burst_inc = ((r->burst_per_step * mstep_inc) / 1000);
146	16	if(burst_inc)
147	16	r->burst_per_step += burst_inc;
148	16	}
149	16	}
150	19	}
151	21	}
152	43	}
153
154		void Curl_rlimit_init(struct Curl_rlimit *r,
155		int64_t rate_per_sec,
156		int64_t burst_per_sec,
157		const struct curltime *pts)
158	1.30k	{
159	1.30k	DEBUGASSERT(rate_per_sec >= 0);
160	1.30k	DEBUGASSERT(burst_per_sec >= rate_per_sec \|\| !burst_per_sec);
161	1.30k	DEBUGASSERT(pts);
162	1.30k	r->rate_per_step = r->rate_per_sec = rate_per_sec;
163	1.30k	r->burst_per_step = r->burst_per_sec = burst_per_sec;
164	1.30k	r->step_us = CURL_US_PER_SEC;
165	1.30k	r->spare_us = 0;
166	1.30k	r->tokens = r->rate_per_step;
167	1.30k	r->ts = *pts;
168	1.30k	r->blocked = FALSE;
169	1.30k	}
170
171		void Curl_rlimit_start(struct Curl_rlimit r, const struct curltime pts,
172		int64_t total_tokens)
173	5.45k	{
174		/* A start always resets the values to initial defaults, then
175		* fine tunes the intervals for the total_tokens expected. */
176	5.45k	r->rate_per_step = r->rate_per_sec;
177	5.45k	r->burst_per_step = r->burst_per_sec;
178	5.45k	r->step_us = CURL_US_PER_SEC;
179	5.45k	r->spare_us = 0;
180	5.45k	r->tokens = r->rate_per_step;
181	5.45k	r->ts = *pts;
182	5.45k	rlimit_tune_steps(r, total_tokens);
183	5.45k	}
184
185		int64_t Curl_rlimit_per_step(struct Curl_rlimit *r)
186	2.90k	{
187	2.90k	return r->rate_per_step;
188	2.90k	}
189
190		bool Curl_rlimit_active(struct Curl_rlimit *r)
191	39.4k	{
192	39.4k	return (r->rate_per_step > 0) \|\| r->blocked;
193	39.4k	}
194
195		bool Curl_rlimit_is_blocked(struct Curl_rlimit *r)
196	34.9k	{
197	34.9k	return (bool)r->blocked;
198	34.9k	}
199
200		int64_t Curl_rlimit_avail(struct Curl_rlimit *r,
201		const struct curltime *pts)
202	17.7k	{
203	17.7k	struct curltime ts;
204
205	17.7k	if(r->blocked)
206	0	return 0;
207	17.7k	else if(r->rate_per_step) {
208	7.11k	if(!pts) {
209	7.11k	curlx_pnow(&ts);
210	7.11k	pts = &ts;
211	7.11k	}
212	7.11k	rlimit_update(r, pts);
213	7.11k	return r->tokens;
214	7.11k	}
215	10.6k	else
216	10.6k	return INT64_MAX;
217	17.7k	}
218
219		void Curl_rlimit_drain(struct Curl_rlimit *r, size_t tokens,
220		const struct curltime *pts)
221	6.06k	{
222	6.06k	struct curltime ts;
223
224	6.06k	if(r->blocked \|\| !r->rate_per_step)
225	5.33k	return;
226
227	727	if(!pts) {
228	727	curlx_pnow(&ts);
229	727	pts = &ts;
230	727	}
231	727	rlimit_update(r, pts);
232	727	#if 8 <= SIZEOF_SIZE_T
233	727	if(tokens > INT64_MAX) {
234	0	r->tokens = INT64_MAX;
235	0	}
236	727	else
237	727	#endif
238	727	{
239	727	int64_t val = (int64_t)tokens;
240	727	if((INT64_MIN + val) < r->tokens)
241	727	r->tokens -= val;
242	0	else
243	0	r->tokens = INT64_MIN;
244	727	}
245	727	}
246
247		timediff_t Curl_rlimit_wait_ms(struct Curl_rlimit *r,
248		const struct curltime *pts)
249	6.43k	{
250	6.43k	timediff_t wait_us, elapsed_us;
251
252	6.43k	if(r->blocked \|\| !r->rate_per_step)
253	2.83k	return 0;
254	3.60k	rlimit_update(r, pts);
255	3.60k	if(r->tokens > 0)
256	3.34k	return 0;
257
258		/* How much time will it take tokens to become positive again?
259		* Deduct `spare_us` and check against already elapsed time */
260	260	wait_us = r->step_us - r->spare_us;
261	260	if(r->tokens < 0) {
262	28	curl_off_t debt_pct = ((-r->tokens) * 100 / r->rate_per_step);
263	28	if(debt_pct)
264	23	wait_us += (r->step_us * debt_pct / 100);
265	28	}
266
267	260	elapsed_us = curlx_ptimediff_us(pts, &r->ts);
268	260	if(elapsed_us >= wait_us)
269	0	return 0;
270	260	wait_us -= elapsed_us;
271	260	return (wait_us + 999) / 1000; /* in milliseconds */
272	260	}
273
274		timediff_t Curl_rlimit_next_step_ms(struct Curl_rlimit *r,
275		const struct curltime *pts)
276	5.92k	{
277	5.92k	if(!r->blocked && r->rate_per_step) {
278	3.30k	timediff_t elapsed_us, next_us;
279
280	3.30k	elapsed_us = curlx_ptimediff_us(pts, &r->ts) + r->spare_us;
281	3.30k	if(r->step_us > elapsed_us) {
282	3.30k	next_us = r->step_us - elapsed_us;
283	3.30k	return (next_us + 999) / 1000; /* in milliseconds */
284	3.30k	}
285	3.30k	}
286	2.61k	return 0;
287	5.92k	}
288
289		void Curl_rlimit_block(struct Curl_rlimit *r,
290		bool activate,
291		const struct curltime *pts)
292	22.2k	{
293	22.2k	if(!activate == !r->blocked)
294	22.2k	return;
295
296	0	r->ts = *pts;
297	0	r->blocked = activate;
298	0	if(!r->blocked) {
299		/* Start rate limiting fresh. The amount of time this was blocked
300		* does not generate extra tokens. */
301	0	Curl_rlimit_start(r, pts, -1);
302	0	}
303	0	else {
304	0	r->tokens = 0;
305	0	}
306	0	}