Skip to main content

webbluetooth_core/
backlog.rs

1//! A bounded queue for things a peer sends us.
2//!
3//! Notifications, L2CAP data and writes to a published characteristic all
4//! arrive on a platform's callback thread: CoreBluetooth's dispatch queue, the
5//! D-Bus reader, the ATT reader, a JNI callback. Every one of those must return
6//! promptly. Blocking one stalls the whole stack, and blocking CoreBluetooth's
7//! dispatch queue can deadlock the framework.
8//!
9//! So there is no backpressure to apply. The peer has already sent the value;
10//! nobody is left to push back on. The only real choices are to queue without
11//! limit — which turns a stalled consumer into an out-of-memory crash — or to
12//! bound the queue and lose something.
13//!
14//! This bounds it, keeps the newest, and counts what it dropped. The count is
15//! the part that matters: a consumer that silently reassembles a byte stream
16//! with a hole in it produces a bug that takes days to find, whereas one that
17//! can see [`Receiver::lost`] move can decide for itself whether to start over.
18//!
19//! Keeping the *newest* is right for the common case — a sensor whose old
20//! readings are worthless — and wrong for a transfer being reassembled, which
21//! wants the intact prefix. That is a per-subscription choice; see
22//! [`Overflow`].
23
24use futures_core::Stream;
25use std::collections::VecDeque;
26use std::pin::Pin;
27use std::sync::{Arc, Mutex};
28use std::task::{Context, Poll, Waker};
29
30/// What to discard when the queue is full.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum Overflow {
33    /// Drop the oldest queued value.
34    ///
35    /// The default, and right for anything that reports current state: a
36    /// stale battery level or heart rate is worthless once a newer one has
37    /// arrived.
38    KeepNewest,
39    /// Drop the value just arrived.
40    ///
41    /// Right for anything being reassembled in order — a firmware image, a
42    /// log download — where a contiguous prefix and a known stopping point
43    /// beat a fresher fragment with a hole before it.
44    KeepOldest,
45}
46
47/// How many values a subscription queues before it has to drop one.
48///
49/// At the largest ATT payload this is about 250 KB per subscription, which is
50/// enough to absorb a consumer stalling for seconds at the fastest rate a
51/// connection interval allows, and small enough that a forgotten subscription
52/// cannot exhaust memory.
53pub const DEFAULT_CAPACITY: usize = 1024;
54
55struct Shared<T> {
56    queue: VecDeque<T>,
57    capacity: usize,
58    overflow: Overflow,
59    /// Cumulative, never reset: a caller compares it across reads to find the
60    /// size of a gap, and a counter that reset under them could not be
61    /// compared at all.
62    lost: u64,
63    waker: Option<Waker>,
64    /// Set when the receiving half goes away.
65    closed: bool,
66    /// Set when a sender declares the stream over.
67    ///
68    /// Distinct from every sender being dropped: a producer can know the peer
69    /// has hung up while still holding its handle — an L2CAP channel closing
70    /// is exactly that — and the reader should finish rather than wait.
71    finished: bool,
72    /// How many senders exist.
73    ///
74    /// When the last one goes the stream is finished, not merely idle, and the
75    /// receiver says so — otherwise a caller waiting on a subscription that
76    /// has been torn down waits for ever. A quiet peer is a different thing
77    /// and does *not* end the stream: the sender is still there.
78    senders: usize,
79}
80
81/// The producer half. Never blocks, never waits.
82pub struct Sender<T>(Arc<Mutex<Shared<T>>>);
83
84/// The consumer half, as a [`Stream`].
85pub struct Receiver<T>(Arc<Mutex<Shared<T>>>);
86
87/// A bounded queue with the given policy.
88pub fn bounded<T>(capacity: usize, overflow: Overflow) -> (Sender<T>, Receiver<T>) {
89    // A zero-capacity queue would drop everything and report nothing useful,
90    // which is never what a caller means.
91    let capacity = capacity.max(1);
92    let shared = Arc::new(Mutex::new(Shared {
93        queue: VecDeque::new(),
94        capacity,
95        overflow,
96        lost: 0,
97        waker: None,
98        closed: false,
99        finished: false,
100        senders: 1,
101    }));
102    (Sender(shared.clone()), Receiver(shared))
103}
104
105/// A bounded queue with the default capacity and policy.
106pub fn channel<T>() -> (Sender<T>, Receiver<T>) {
107    bounded(DEFAULT_CAPACITY, Overflow::KeepNewest)
108}
109
110impl<T> Sender<T> {
111    /// Queue a value.
112    ///
113    /// `Err` only when the receiver is gone — which is how a producer knows to
114    /// stop, and why the backends can drop a subscription by testing this. A
115    /// full queue is not an error: something is dropped, counted, and the send
116    /// still succeeds, because the alternative is telling a platform callback
117    /// about a problem it cannot do anything about.
118    pub fn send(&self, value: T) -> Result<(), Closed> {
119        let waker = {
120            let mut shared = self.0.lock().unwrap();
121            if shared.closed || shared.finished {
122                return Err(Closed);
123            }
124            if shared.queue.len() >= shared.capacity {
125                shared.lost += 1;
126                match shared.overflow {
127                    Overflow::KeepNewest => {
128                        shared.queue.pop_front();
129                    }
130                    Overflow::KeepOldest => return Ok(()),
131                }
132            }
133            shared.queue.push_back(value);
134            shared.waker.take()
135        };
136        // Woken outside the lock: waking polls the stream, which locks.
137        if let Some(waker) = waker {
138            waker.wake();
139        }
140        Ok(())
141    }
142
143    /// Whether anything is still listening.
144    pub fn is_open(&self) -> bool {
145        let shared = self.0.lock().unwrap();
146        !shared.closed && !shared.finished
147    }
148
149    /// Declare the stream over while still holding this handle.
150    ///
151    /// For a producer that learns the source has ended — a peer closing an
152    /// L2CAP channel — and cannot simply drop its sender because something
153    /// else owns it. Whatever is queued is still delivered first.
154    pub fn close(&self) {
155        let waker = {
156            let mut shared = self.0.lock().unwrap();
157            shared.finished = true;
158            shared.waker.take()
159        };
160        if let Some(waker) = waker {
161            waker.wake();
162        }
163    }
164}
165
166// Derived would demand `T: Clone`, which is not what is being cloned — the
167// handle is. Several producers feeding one queue is the ordinary case: a
168// characteristic can be registered under more than one key, and each
169// registration keeps its own sender.
170impl<T> Clone for Sender<T> {
171    fn clone(&self) -> Self {
172        self.0.lock().unwrap().senders += 1;
173        Self(self.0.clone())
174    }
175}
176
177impl<T> Drop for Sender<T> {
178    fn drop(&mut self) {
179        let waker = {
180            let mut shared = self.0.lock().unwrap();
181            shared.senders -= 1;
182            if shared.senders > 0 {
183                return;
184            }
185            // The last one. Anyone waiting is woken to discover the stream is
186            // over rather than waiting for a value that cannot come.
187            shared.waker.take()
188        };
189        if let Some(waker) = waker {
190            waker.wake();
191        }
192    }
193}
194
195/// The receiver is gone.
196#[derive(Debug, Clone, Copy, PartialEq, Eq)]
197pub struct Closed;
198
199impl<T> Receiver<T> {
200    /// How many values have been dropped, in total, since this was created.
201    ///
202    /// Cumulative rather than reset-on-read, so two reads can be compared: if
203    /// this has moved between one value and the next, the difference is
204    /// exactly how many went missing in between.
205    pub fn lost(&self) -> u64 {
206        self.0.lock().unwrap().lost
207    }
208
209    /// Take the next value if one is waiting, without registering interest.
210    ///
211    /// For a caller draining what has already arrived rather than awaiting
212    /// what has not — a chooser sweeping up the candidates seen so far. It
213    /// deliberately does not store a waker: nobody is going to be woken.
214    pub fn try_recv(&mut self) -> Option<T> {
215        self.0.lock().unwrap().queue.pop_front()
216    }
217
218    /// How many values are waiting.
219    ///
220    /// A number that stays near [`DEFAULT_CAPACITY`] is a consumer that is not
221    /// keeping up, which is worth knowing before [`lost`](Self::lost) starts
222    /// moving.
223    pub fn depth(&self) -> usize {
224        self.0.lock().unwrap().queue.len()
225    }
226}
227
228impl<T> Stream for Receiver<T> {
229    type Item = T;
230
231    fn poll_next(self: Pin<&mut Self>, context: &mut Context<'_>) -> Poll<Option<T>> {
232        let mut shared = self.0.lock().unwrap();
233        if let Some(value) = shared.queue.pop_front() {
234            return Poll::Ready(Some(value));
235        }
236        // Drained *and* nobody left to send: the stream is over. Checked after
237        // the queue, so values already sent are delivered before the end.
238        if shared.senders == 0 || shared.finished {
239            return Poll::Ready(None);
240        }
241        // A quiet peer is not an ending — the sender is still there, and a
242        // subscription lasts until the caller drops it.
243        shared.waker = Some(context.waker().clone());
244        Poll::Pending
245    }
246}
247
248impl<T> Drop for Receiver<T> {
249    fn drop(&mut self) {
250        let mut shared = self.0.lock().unwrap();
251        shared.closed = true;
252        // Anything still queued is never going to be read.
253        shared.queue.clear();
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use super::*;
260    use std::task::{RawWaker, RawWakerVTable};
261
262    fn noop_waker() -> Waker {
263        fn clone(_: *const ()) -> RawWaker {
264            RawWaker::new(std::ptr::null(), &VTABLE)
265        }
266        fn noop(_: *const ()) {}
267        static VTABLE: RawWakerVTable = RawWakerVTable::new(clone, noop, noop, noop);
268        unsafe { Waker::from_raw(RawWaker::new(std::ptr::null(), &VTABLE)) }
269    }
270
271    fn drain<T>(rx: &mut Receiver<T>) -> Vec<T> {
272        let waker = noop_waker();
273        let mut context = Context::from_waker(&waker);
274        let mut out = Vec::new();
275        while let Poll::Ready(Some(v)) = Pin::new(&mut *rx).poll_next(&mut context) {
276            out.push(v);
277        }
278        out
279    }
280
281    #[test]
282    fn values_come_out_in_the_order_they_went_in() {
283        let (tx, mut rx) = channel();
284        for i in 0..5 {
285            tx.send(i).unwrap();
286        }
287        assert_eq!(drain(&mut rx), vec![0, 1, 2, 3, 4]);
288        assert_eq!(rx.lost(), 0);
289    }
290
291    /// The default: a full queue keeps the newest, because a stale sensor
292    /// reading is worthless once a newer one exists.
293    #[test]
294    fn keeping_the_newest_drops_from_the_front() {
295        let (tx, mut rx) = bounded(3, Overflow::KeepNewest);
296        for i in 0..5 {
297            tx.send(i).expect("a full queue is not an error");
298        }
299        assert_eq!(drain(&mut rx), vec![2, 3, 4], "the newest three survive");
300        assert_eq!(rx.lost(), 2, "and the two it dropped are counted");
301    }
302
303    /// The opposite policy, for something being reassembled in order: the
304    /// prefix stays contiguous and the loss is at the end, where a consumer
305    /// can see it and stop.
306    #[test]
307    fn keeping_the_oldest_drops_what_just_arrived() {
308        let (tx, mut rx) = bounded(3, Overflow::KeepOldest);
309        for i in 0..5 {
310            tx.send(i).unwrap();
311        }
312        assert_eq!(drain(&mut rx), vec![0, 1, 2], "the first three survive");
313        assert_eq!(rx.lost(), 2);
314    }
315
316    /// The property the whole design rests on: a gap is always visible. A
317    /// consumer comparing `lost()` across two reads learns exactly how many
318    /// values went missing between them.
319    #[test]
320    fn a_gap_is_measurable_between_two_reads() {
321        let (tx, mut rx) = bounded(2, Overflow::KeepNewest);
322        tx.send(1).unwrap();
323
324        let waker = noop_waker();
325        let mut context = Context::from_waker(&waker);
326        let before = rx.lost();
327        assert_eq!(
328            Pin::new(&mut rx).poll_next(&mut context),
329            Poll::Ready(Some(1))
330        );
331
332        // The consumer stalls; seven more arrive into a queue of two.
333        for i in 2..9 {
334            tx.send(i).unwrap();
335        }
336        let next = match Pin::new(&mut rx).poll_next(&mut context) {
337            Poll::Ready(Some(v)) => v,
338            other => panic!("expected a value, got {other:?}"),
339        };
340        let gap = rx.lost() - before;
341
342        assert_eq!(gap, 5, "five values went missing");
343        assert_eq!(next, 7, "and the stream resumes after them");
344    }
345
346    /// A full queue must not be an error: a platform callback cannot do
347    /// anything about it, and failing the send would only lose the value
348    /// *and* the information that it was lost.
349    #[test]
350    fn overflow_is_not_a_send_failure() {
351        let (tx, _rx) = bounded(1, Overflow::KeepNewest);
352        assert!(tx.send(1).is_ok());
353        assert!(tx.send(2).is_ok());
354        assert!(tx.send(3).is_ok());
355    }
356
357    /// Dropping the consumer is how a producer learns to stop — the backends
358    /// prune their subscriber lists by testing exactly this.
359    #[test]
360    fn a_dropped_receiver_closes_the_sender() {
361        let (tx, rx) = channel();
362        assert!(tx.is_open());
363        assert!(tx.send(1).is_ok());
364        drop(rx);
365        assert!(!tx.is_open());
366        assert_eq!(tx.send(2), Err(Closed));
367    }
368
369    /// Queued values go with the receiver rather than being held by a sender
370    /// nobody is reading.
371    #[test]
372    fn a_dropped_receiver_releases_what_was_queued() {
373        let held = Arc::new(());
374        let (tx, rx) = channel();
375        for _ in 0..10 {
376            tx.send(held.clone()).unwrap();
377        }
378        assert_eq!(Arc::strong_count(&held), 11);
379        drop(rx);
380        assert_eq!(Arc::strong_count(&held), 1, "the queue was released");
381    }
382
383    /// A waiting consumer is woken when something arrives.
384    #[test]
385    fn a_waiting_consumer_is_woken() {
386        let (tx, mut rx) = channel::<u32>();
387        let woken = Arc::new(Mutex::new(false));
388
389        struct Flag(Arc<Mutex<bool>>);
390        impl std::task::Wake for Flag {
391            fn wake(self: Arc<Self>) {
392                *self.0.lock().unwrap() = true;
393            }
394        }
395        let waker: Waker = Arc::new(Flag(woken.clone())).into();
396        let mut context = Context::from_waker(&waker);
397
398        assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
399        assert!(!*woken.lock().unwrap());
400
401        tx.send(7).unwrap();
402        assert!(*woken.lock().unwrap(), "sending should wake the consumer");
403        assert_eq!(
404            Pin::new(&mut rx).poll_next(&mut context),
405            Poll::Ready(Some(7))
406        );
407    }
408
409    /// A quiet peer and a finished subscription are different things, and
410    /// conflating them is how a caller ends up waiting for ever.
411    ///
412    /// Nothing arriving means exactly that: the sender is still there and a
413    /// value may come. The sender *going away* is the end, and the stream has
414    /// to say so — a scan whose watcher was removed must finish, not hang.
415    #[test]
416    fn silence_is_pending_but_a_dropped_sender_is_the_end() {
417        let (tx, mut rx) = channel::<u32>();
418        let waker = noop_waker();
419        let mut context = Context::from_waker(&waker);
420
421        // Quiet, but alive.
422        assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
423
424        tx.send(7).unwrap();
425        drop(tx);
426
427        // Anything already sent still arrives before the end.
428        assert_eq!(
429            Pin::new(&mut rx).poll_next(&mut context),
430            Poll::Ready(Some(7)),
431            "a value sent before the sender went must not be lost"
432        );
433        assert_eq!(
434            Pin::new(&mut rx).poll_next(&mut context),
435            Poll::Ready(None),
436            "and then the stream is over"
437        );
438    }
439
440    /// One clone going away is not the end; the last one is.
441    #[test]
442    fn the_stream_ends_only_when_every_sender_is_gone() {
443        let (tx, mut rx) = channel::<u32>();
444        let second = tx.clone();
445        let waker = noop_waker();
446        let mut context = Context::from_waker(&waker);
447
448        drop(second);
449        assert_eq!(
450            Pin::new(&mut rx).poll_next(&mut context),
451            Poll::Pending,
452            "one sender remains, so the stream is merely quiet"
453        );
454
455        drop(tx);
456        assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Ready(None));
457    }
458
459    /// A producer can end the stream without giving up its handle, and what
460    /// is already queued still arrives first.
461    #[test]
462    fn closing_ends_the_stream_after_draining() {
463        let (tx, mut rx) = channel::<u32>();
464        let waker = noop_waker();
465        let mut context = Context::from_waker(&waker);
466
467        tx.send(1).unwrap();
468        tx.send(2).unwrap();
469        tx.close();
470
471        assert!(!tx.is_open(), "a closed sender reports itself closed");
472        assert_eq!(tx.send(3), Err(Closed), "and takes nothing further");
473
474        assert_eq!(
475            Pin::new(&mut rx).poll_next(&mut context),
476            Poll::Ready(Some(1)),
477            "what was queued before the close is still delivered"
478        );
479        assert_eq!(
480            Pin::new(&mut rx).poll_next(&mut context),
481            Poll::Ready(Some(2))
482        );
483        assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Ready(None));
484    }
485
486    /// A capacity of zero would drop everything; it is treated as one.
487    #[test]
488    fn a_zero_capacity_still_carries_a_value() {
489        let (tx, mut rx) = bounded(0, Overflow::KeepNewest);
490        tx.send(9).unwrap();
491        assert_eq!(drain(&mut rx), vec![9]);
492    }
493
494    /// The stream stays open while the peer is quiet — a subscription ends
495    /// when the caller drops it, not when nothing has arrived for a while.
496    #[test]
497    fn an_empty_queue_is_pending_rather_than_finished() {
498        let (tx, mut rx) = channel::<u32>();
499        let waker = noop_waker();
500        let mut context = Context::from_waker(&waker);
501        assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
502        tx.send(1).unwrap();
503        assert_eq!(
504            Pin::new(&mut rx).poll_next(&mut context),
505            Poll::Ready(Some(1))
506        );
507        assert_eq!(Pin::new(&mut rx).poll_next(&mut context), Poll::Pending);
508    }
509
510    /// Sends arriving from several threads at once must all be accounted for:
511    /// every value either comes out or is counted as lost, never neither.
512    #[test]
513    fn nothing_vanishes_unaccounted_under_concurrent_senders() {
514        const THREADS: usize = 8;
515        const EACH: usize = 500;
516
517        let (tx, mut rx) = bounded::<usize>(16, Overflow::KeepNewest);
518        let tx = Arc::new(tx);
519        let threads: Vec<_> = (0..THREADS)
520            .map(|_| {
521                let tx = tx.clone();
522                std::thread::spawn(move || {
523                    for i in 0..EACH {
524                        tx.send(i).unwrap();
525                    }
526                })
527            })
528            .collect();
529        for t in threads {
530            t.join().expect("no sender should have panicked");
531        }
532
533        let received = drain(&mut rx).len() as u64;
534        assert_eq!(
535            received + rx.lost(),
536            (THREADS * EACH) as u64,
537            "every value is either delivered or counted"
538        );
539    }
540
541    /// Several producers, one queue — and cloning the handle must not require
542    /// the payload to be cloneable.
543    #[test]
544    fn senders_clone_and_share_one_queue() {
545        struct NotClone(u32);
546
547        let (tx, mut rx) = bounded::<NotClone>(8, Overflow::KeepNewest);
548        let second = tx.clone();
549        tx.send(NotClone(1)).unwrap();
550        second.send(NotClone(2)).unwrap();
551
552        let got: Vec<u32> = drain(&mut rx).into_iter().map(|v| v.0).collect();
553        assert_eq!(got, vec![1, 2], "both feed the same queue, in order");
554
555        // And one clone going away does not close the queue under the others.
556        drop(second);
557        assert!(tx.is_open());
558        assert!(tx.send(NotClone(3)).is_ok());
559    }
560
561    /// `try_recv` takes what is there and does not wait for what is not.
562    #[test]
563    fn try_recv_drains_without_waiting() {
564        let (tx, mut rx) = channel();
565        assert_eq!(rx.try_recv(), None, "nothing queued yet");
566
567        tx.send(1).unwrap();
568        tx.send(2).unwrap();
569        assert_eq!(rx.try_recv(), Some(1));
570        assert_eq!(rx.try_recv(), Some(2));
571        assert_eq!(rx.try_recv(), None, "and it stops rather than blocking");
572    }
573
574    #[test]
575    fn depth_reports_what_is_waiting() {
576        let (tx, mut rx) = bounded(4, Overflow::KeepNewest);
577        assert_eq!(rx.depth(), 0);
578        tx.send(1).unwrap();
579        tx.send(2).unwrap();
580        assert_eq!(rx.depth(), 2);
581        drain(&mut rx);
582        assert_eq!(rx.depth(), 0);
583    }
584
585    /// The published default has to be the one the module documents, since
586    /// the memory figure in the docs is derived from it.
587    #[test]
588    fn the_default_is_the_documented_one() {
589        assert_eq!(DEFAULT_CAPACITY, 1024);
590        let (tx, rx) = channel::<u8>();
591        for i in 0..(DEFAULT_CAPACITY + 10) {
592            tx.send(i as u8).unwrap();
593        }
594        assert_eq!(rx.depth(), DEFAULT_CAPACITY);
595        assert_eq!(rx.lost(), 10);
596    }
597}