Skip to content

misterdownloadmanager: The ultimate open-source, clean-room download manager written from scratch in pure Rust for Windows, Mac, and Linux

10.9 KB
Raw Blame
//! Per-download speed limiter (IDM: "Maximum download speed for one file", notes/ENGINE.md §4).
//! A token bucket shared by all of a download's connections; the limit can change while the
//! download runs, and a new limit applies to the waits already started too (#621). Throttling
//! the socket reads makes TCP slow the server down.

use std::sync::Mutex;
use std::sync::atomic::{AtomicU64, Ordering};
use std::time::Duration;

use tokio::sync::Notify;
// Tokio's clock: the system's, except in tests that pause it.
use tokio::time::Instant;

/// Bytes per second; 0 = unlimited. One per download, and optionally one shared by all of them
/// (the global cap, `Options::global`).
#[derive(Debug)]
pub struct Limiter {
    /// Changed under the bucket's lock, read without it by [`Limiter::get`].
    rate: AtomicU64,
    bucket: Mutex<Bucket>,
    /// Every byte that went through it (less what was given back), limited or not: what the
    /// downloads under it took, for the global cap's split with torrents.
    taken: AtomicU64,
    /// Wakes the waits when the limit changes, so they count what is left at the new rate.
    changed: Notify,
}

#[derive(Debug)]
struct Bucket {
    /// Bytes that may be read right now (may go negative: debt to wait off).
    tokens: f64,
    last: Instant,
    /// The budget earned since the limiter was made, bytes, at whatever the rate was each
    /// moment: a wait ends when this reaches its mark, so a new rate applies to the rest of it.
    earned: f64,
    /// Goes up each time the limit is removed: the debt is forgiven then, and every wait from
    /// before ends, even if a limit is set again before that wait looks.
    era: u64,
}

impl Bucket {
    /// Add what `rate` earned since the last time.
    fn refill(&mut self, rate: u64, now: Instant) {
        let earned = now.saturating_duration_since(self.last).as_secs_f64() * rate as f64;
        self.last = now;
        if rate > 0 {
            self.earned += earned;
            self.tokens = (self.tokens + earned).min(rate as f64 * BURST_SECS);
        }
    }
}

/// Where a wait ends: once the bucket has earned `at` bytes, in the same `era`.
#[derive(Debug)]
struct Mark {
    at: f64,
    era: u64,
}

/// Burst allowance: up to one second's budget accumulates while no connection is reading (e.g.
/// all between requests), so short gaps don't lower the average below the limit.
const BURST_SECS: f64 = 1.0;

impl Limiter {
    pub fn new(rate: Option<u64>) -> Self {
        Limiter {
            rate: AtomicU64::new(rate.unwrap_or(0)),
            bucket: Mutex::new(Bucket {
                tokens: 0.0,
                last: Instant::now(),
                earned: 0.0,
                era: 0,
            }),
            taken: AtomicU64::new(0),
            changed: Notify::new(),
        }
    }

    /// The bytes that went through it so far (less those given back).
    pub fn taken(&self) -> u64 {
        self.taken.load(Ordering::Relaxed)
    }

    /// A new limit (None = unlimited), for the waits already started too: they wake and wait
    /// only for what is left of their debt at the new rate, and end at once without a limit.
    pub fn set(&self, rate: Option<u64>) {
        let rate = rate.unwrap_or(0);
        {
            let mut b = self.bucket.lock().unwrap();
            let old = self.rate.load(Ordering::Relaxed);
            if old == rate {
                return;
            }
            // What the old rate earned until now.
            b.refill(old, Instant::now());
            if rate == 0 {
                // No limit: the debt is forgiven (a limit set later starts afresh).
                b.tokens = 0.0;
                b.era += 1;
            }
            self.rate.store(rate, Ordering::Relaxed);
        }
        self.changed.notify_waiters();
    }

    pub fn get(&self) -> Option<u64> {
        Some(self.rate.load(Ordering::Relaxed)).filter(|r| *r > 0)
    }

    /// Account for `n` received bytes; where the caller's wait ends, if it must wait.
    fn take(&self, n: u64) -> Option<Mark> {
        self.taken.fetch_add(n, Ordering::Relaxed);
        if self.rate.load(Ordering::Relaxed) == 0 {
            return None;
        }
        let mut b = self.bucket.lock().unwrap();
        let rate = self.rate.load(Ordering::Relaxed);
        if rate == 0 {
            return None;
        }
        b.refill(rate, Instant::now());
        b.tokens -= n as f64;
        (b.tokens < 0.0).then(|| Mark {
            at: b.earned - b.tokens,
            era: b.era,
        })
    }

    /// How much longer the wait ending at `mark` lasts at the rate now; None once it is over.
    fn left(&self, mark: &Mark) -> Option<Duration> {
        let mut b = self.bucket.lock().unwrap();
        let rate = self.rate.load(Ordering::Relaxed);
        if rate == 0 || b.era != mark.era {
            return None;
        }
        b.refill(rate, Instant::now());
        let owed = mark.at - b.earned;
        // Under a byte is paid (the float's rounding would only add waits of nothing).
        (owed >= 1.0).then(|| Duration::from_secs_f64(owed / rate as f64))
    }

    /// Give back budget for `n` bytes that were paid for but not kept.
    pub fn refund(&self, n: u64) {
        let mut t = self.taken.load(Ordering::Relaxed);
        while let Err(now) = self.taken.compare_exchange_weak(
            t,
            t.saturating_sub(n),
            Ordering::Relaxed,
            Ordering::Relaxed,
        ) {
            t = now;
        }
        if self.rate.load(Ordering::Relaxed) > 0 {
            self.bucket.lock().unwrap().tokens += n as f64;
        }
    }

    /// Wait until `n` more bytes fit under the limit: the limit at each moment of the wait, not
    /// only the one when it started (#621).
    pub async fn acquire(&self, n: u64) {
        let Some(mark) = self.take(n) else { return };
        loop {
            let mut changed = std::pin::pin!(self.changed.notified());
            // Listening before counting: a change from here on wakes this wait.
            changed.as_mut().enable();
            let Some(wait) = self.left(&mark) else { return };
            tokio::select! {
                () = tokio::time::sleep(wait) => {}
                () = changed => {}
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[tokio::test]
    async fn limits_average_rate() {
        let l = Limiter::new(Some(400 * 1024));
        let t = Instant::now();
        for _ in 0..20 {
            l.acquire(10 * 1024).await; // 200 KB at 400 KB/s ≈ 0.5 s
        }
        let secs = t.elapsed().as_secs_f64();
        assert!((0.4..0.75).contains(&secs), "{secs:.2}s");
    }

    #[tokio::test]
    async fn unlimited_and_changeable() {
        let l = Limiter::new(None);
        let t = Instant::now();
        l.acquire(100 << 20).await;
        assert!(t.elapsed() < Duration::from_millis(20));
        l.set(Some(1024));
        assert_eq!(l.get(), Some(1024));
        l.set(None);
        assert_eq!(l.get(), None);
    }

    #[tokio::test]
    async fn counts_what_went_through() {
        let l = Limiter::new(None);
        l.acquire(1000).await;
        l.set(Some(1 << 30));
        l.acquire(500).await;
        l.refund(200);
        assert_eq!(l.taken(), 1300, "limited or not, less what was given back");
    }

    /// #621, the reporter's witness: a wait that has started ends as soon as the limit is
    /// raised or removed, not at the deadline the old limit set (64 s here).
    #[tokio::test(start_paused = true)]
    async fn a_new_limit_applies_to_a_wait_already_started() {
        use std::future::Future;
        use std::task::{Context, Poll, Waker};
        for new_rate in [None, Some(1024 * 1024)] {
            let limiter = Limiter::new(Some(1024));
            let mut pending = Box::pin(limiter.acquire(64 * 1024));
            let mut cx = Context::from_waker(Waker::noop());
            assert!(pending.as_mut().poll(&mut cx).is_pending());
            limiter.set(new_rate);
            assert_eq!(limiter.get(), new_rate);
            tokio::time::advance(Duration::from_secs(1)).await;
            assert!(
                matches!(pending.as_mut().poll(&mut cx), Poll::Ready(())),
                "still waiting after the limit went to {new_rate:?}"
            );
        }
    }

    /// The time from `t` to now, to the millisecond (Tokio's paused clock).
    fn ms_since(t: Instant) -> u128 {
        t.elapsed().as_millis()
    }

    /// Two waits under one limit share it, before and after it changes: what each still owes
    /// is counted at the new rate, in turn.
    #[tokio::test(start_paused = true)]
    async fn waits_count_what_is_left_at_the_new_rate() {
        let l = Limiter::new(Some(1024));
        let t = Instant::now();
        let l = &l;
        let wait = |n| async move {
            l.acquire(n).await;
            ms_since(t)
        };
        // 1 KB each at 1 KB/s: at 1 s and 2 s. At 0.5 s the limit doubles: the first has 512
        // bytes left (0.25 s more), the second 1536 (0.75 s).
        let (a, b, ()) = tokio::join!(wait(1024), wait(1024), async {
            tokio::time::sleep(Duration::from_millis(500)).await;
            l.set(Some(2048));
        });
        assert!((750..760).contains(&a), "{a} ms");
        assert!((1250..1260).contains(&b), "{b} ms");
        // Halved: 2 KB at 2 KB/s, and at 0.5 s 1 KB left at 1 KB/s.
        let t = Instant::now();
        let (a, ()) = tokio::join!(
            async {
                l.acquire(2048).await;
                ms_since(t)
            },
            async {
                tokio::time::sleep(Duration::from_millis(500)).await;
                l.set(Some(1024));
            }
        );
        assert!((1500..1510).contains(&a), "{a} ms");
    }

    /// Without a limit the debt is gone: a limit set again starts afresh, and a wait from
    /// before ends even when the limit came back before it looked.
    #[tokio::test(start_paused = true)]
    async fn removing_the_limit_forgives_the_debt() {
        use std::future::Future;
        use std::task::{Context, Waker};
        let l = Limiter::new(Some(1024));
        let mut owed = Box::pin(l.acquire(64 * 1024));
        let mut cx = Context::from_waker(Waker::noop());
        assert!(owed.as_mut().poll(&mut cx).is_pending());
        l.set(None);
        l.set(Some(1024));
        assert!(owed.as_mut().poll(&mut cx).is_ready());
        let t = Instant::now();
        l.acquire(1024).await;
        assert!((1000..1010).contains(&ms_since(t)), "{} ms", ms_since(t));
    }

    /// The same limit again changes nothing (the app sets the global cap's every frame).
    #[tokio::test(start_paused = true)]
    async fn the_same_limit_again_changes_nothing() {
        let l = Limiter::new(Some(1024));
        let t = Instant::now();
        tokio::join!(l.acquire(2048), async {
            for _ in 0..10 {
                tokio::time::sleep(Duration::from_millis(100)).await;
                l.set(Some(1024));
            }
        });
        assert!((2000..2010).contains(&ms_since(t)), "{} ms", ms_since(t));
    }
}