Skip to main content

net_io/
buf.rs

1//! Pooled buffers with a total budget, wiped on release.
2
3use std::fmt;
4use std::sync::Arc;
5use std::sync::atomic::{AtomicU64, Ordering};
6
7use crate::limits::SizeClass;
8
9/// A byte buffer from a pool: a fixed capacity (its size class) and a filled length.
10///
11/// # Examples
12///
13/// ```
14/// use net_io::{BufferPool, SizeClass};
15/// let mut pool = BufferPool::standalone(1 << 20);
16/// let mut buf = pool.take(SizeClass::SMALL).unwrap();
17/// buf.spare()[..5].copy_from_slice(b"hello");
18/// buf.set_len(5);
19/// assert_eq!(buf.as_slice(), b"hello");
20/// pool.put(buf);
21/// ```
22pub struct Buffer {
23    data: Box<[u8]>,
24    len: usize,
25    /// The longest `len` since the last wipe: `clear`, `compact`, and a consumed
26    /// input shrink `len` but leave the bytes, so the wipe covers this much. A `u32`
27    /// (buffers are at most 1 MiB), so it packs beside the class.
28    dirty: u32,
29    class: SizeClass,
30}
31
32impl Buffer {
33    /// A buffer not drawn from any pool's free list (the caller already charged the budget).
34    pub(crate) fn detached(class: SizeClass) -> Buffer {
35        Buffer::new(class)
36    }
37
38    /// An empty stand-in that owns no memory, left where a buffer travels with a
39    /// driver operation.
40    #[cfg(feature = "reactor")]
41    pub(crate) fn placeholder() -> Buffer {
42        Buffer {
43            data: Box::default(),
44            len: 0,
45            dirty: 0,
46            class: SizeClass::SMALL,
47        }
48    }
49
50    fn new(class: SizeClass) -> Buffer {
51        Buffer {
52            data: vec![0u8; class.bytes() as usize].into_boxed_slice(),
53            len: 0,
54            dirty: 0,
55            class,
56        }
57    }
58
59    /// The filled part.
60    #[must_use]
61    pub fn as_slice(&self) -> &[u8] {
62        &self.data[..self.len]
63    }
64
65    /// The filled part, mutable.
66    pub fn as_mut_slice(&mut self) -> &mut [u8] {
67        &mut self.data[..self.len]
68    }
69
70    /// The unfilled tail.
71    pub fn spare(&mut self) -> &mut [u8] {
72        &mut self.data[self.len..]
73    }
74
75    /// The filled length.
76    #[must_use]
77    pub fn len(&self) -> usize {
78        self.len
79    }
80
81    /// Whether nothing is filled.
82    #[must_use]
83    pub fn is_empty(&self) -> bool {
84        self.len == 0
85    }
86
87    /// Sets the filled length; saturates at the capacity.
88    pub fn set_len(&mut self, n: usize) {
89        self.len = n.min(self.data.len());
90        self.dirty = self.dirty.max(u32::try_from(self.len).unwrap_or(u32::MAX));
91    }
92
93    /// The capacity in bytes.
94    #[must_use]
95    pub fn capacity(&self) -> usize {
96        self.data.len()
97    }
98
99    /// The size class.
100    #[must_use]
101    pub fn class(&self) -> SizeClass {
102        self.class
103    }
104
105    /// Empties the buffer (does not wipe; the pool wipes on release).
106    pub fn clear(&mut self) {
107        self.len = 0;
108    }
109
110    /// Overwrites everything filled since the last wipe with zeroes and empties the
111    /// buffer.
112    pub(crate) fn wipe(&mut self) {
113        let held = (self.dirty as usize).max(self.len).min(self.data.len());
114        let used = &mut self.data[..held];
115        used.fill(0);
116        // The buffer stays reachable and is read again by the next owner, so the
117        // stores cannot be removed as dead; black_box makes that explicit.
118        std::hint::black_box(&*used);
119        self.len = 0;
120        self.dirty = 0;
121    }
122
123    /// Moves the bytes `from..` to the front.
124    pub(crate) fn compact(&mut self, from: usize) {
125        let from = from.min(self.len);
126        self.data.copy_within(from..self.len, 0);
127        self.len -= from;
128    }
129}
130
131impl fmt::Debug for Buffer {
132    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
133        f.debug_struct("Buffer")
134            .field("len", &self.len)
135            .field("capacity", &self.data.len())
136            .finish()
137    }
138}
139
140/// Counts of one pool.
141///
142/// ```
143/// let pool = net_io::BufferPool::standalone(1 << 20);
144/// assert_eq!(pool.stats().allocated, 0);
145/// ```
146#[non_exhaustive]
147#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
148pub struct PoolStats {
149    /// Buffers this pool allocated.
150    pub allocated: u64,
151    /// Buffers in its free lists.
152    pub free: u64,
153    /// Bytes left in the shared budget.
154    pub budget_left: u64,
155    /// Takes refused because the budget was spent.
156    pub budget_refusals: u64,
157    /// Buffers this pool freed and gave back to the shared budget: released above
158    /// what the pool keeps, or freed to make room for a buffer of another class.
159    pub freed: u64,
160}
161
162/// A worker's buffer pool: free lists per size class, drawing new buffers from a
163/// budget shared by every worker of a server.
164///
165/// The budget comes back: a pool keeps at most a fixed number of bytes in its free
166/// lists (a server's pools keep the budget divided by the workers, a fair share)
167/// and frees what is released above that, and a take that finds its own class's
168/// list empty and the budget short frees buffers of other classes first, so a
169/// burst of one size class does not hold the budget from the others for good.
170pub struct BufferPool {
171    lists: Vec<(SizeClass, Vec<Buffer>)>,
172    budget: Arc<AtomicU64>,
173    wipe: bool,
174    allocated: u64,
175    refusals: u64,
176    /// Bytes in the free lists.
177    free_bytes: u64,
178    /// The most bytes the free lists hold; a release above it frees the buffer.
179    keep: u64,
180    freed: u64,
181}
182
183impl BufferPool {
184    /// A pool drawing on `budget` that keeps at most `keep` bytes in its free lists.
185    pub(crate) fn new(budget: Arc<AtomicU64>, wipe: bool, keep: u64) -> BufferPool {
186        BufferPool {
187            lists: Vec::with_capacity(4),
188            budget,
189            wipe,
190            allocated: 0,
191            refusals: 0,
192            free_bytes: 0,
193            keep,
194            freed: 0,
195        }
196    }
197
198    /// A pool with its own budget of `bytes`, for use outside a server. It keeps
199    /// every buffer released to it, up to the whole budget.
200    ///
201    /// ```
202    /// let mut pool = net_io::BufferPool::standalone(64 * 1024);
203    /// assert!(pool.take(net_io::SizeClass::LARGE).is_some());
204    /// assert!(pool.take(net_io::SizeClass::LARGE).is_none()); // budget spent
205    /// ```
206    #[must_use]
207    pub fn standalone(bytes: u64) -> BufferPool {
208        BufferPool::new(Arc::new(AtomicU64::new(bytes)), true, bytes)
209    }
210
211    /// A buffer of `class`, or `None` when the free list is empty and the budget is
212    /// spent even after freeing what this pool holds of other classes.
213    ///
214    /// ```
215    /// use net_io::{BufferPool, SizeClass};
216    /// let mut pool = BufferPool::standalone(64 * 1024);
217    /// let large = pool.take(SizeClass::LARGE).unwrap();
218    /// pool.put(large); // the budget is spent, the buffer is cached
219    /// // A smaller class frees the cached 64 KiB buffer to make room.
220    /// assert!(pool.take(SizeClass::MEDIUM).is_some());
221    /// assert_eq!(pool.stats().freed, 1);
222    /// ```
223    pub fn take(&mut self, class: SizeClass) -> Option<Buffer> {
224        if let Some(buf) = self.pop(class) {
225            return Some(buf);
226        }
227        let bytes = u64::from(class.bytes());
228        while !self.charge(bytes) {
229            // Buffers cached for other classes hold budget this class needs: free
230            // them, the largest first, until the charge fits. Its own list is empty
231            // here, so `free_bytes` is theirs; when even all of it cannot cover the
232            // charge, nothing is freed for nothing.
233            let reachable = self
234                .budget
235                .load(Ordering::Relaxed)
236                .saturating_add(self.free_bytes);
237            if reachable < bytes || !self.free_other(class) {
238                self.refusals += 1;
239                return None;
240            }
241        }
242        self.allocated += 1;
243        Some(Buffer::new(class))
244    }
245
246    /// Takes `bytes` from the shared budget; `false`, with nothing taken, when
247    /// fewer are left.
248    fn charge(&self, bytes: u64) -> bool {
249        let mut left = self.budget.load(Ordering::Relaxed);
250        loop {
251            if left < bytes {
252                return false;
253            }
254            match self.budget.compare_exchange_weak(
255                left,
256                left - bytes,
257                Ordering::AcqRel,
258                Ordering::Relaxed,
259            ) {
260                Ok(_) => return true,
261                Err(actual) => left = actual,
262            }
263        }
264    }
265
266    /// Frees one cached buffer of a class other than `class`, the largest class
267    /// first, and gives its bytes back to the budget; `false` when there is none.
268    fn free_other(&mut self, class: SizeClass) -> bool {
269        let pick = self
270            .lists
271            .iter()
272            .enumerate()
273            .filter(|(_, (c, l))| *c != class && !l.is_empty())
274            .max_by_key(|(_, (c, _))| *c)
275            .map(|(i, _)| i);
276        let Some(buf) = pick.and_then(|i| self.lists[i].1.pop()) else {
277            return false;
278        };
279        self.free_bytes = self.free_bytes.saturating_sub(buf.capacity() as u64);
280        self.refund(buf);
281        true
282    }
283
284    /// Drops a buffer this pool will not keep and gives its bytes back to the
285    /// shared budget. The caller wiped it already (or wiping is off): every buffer
286    /// in a free list was wiped by `put`.
287    fn refund(&mut self, buf: Buffer) {
288        let bytes = buf.capacity() as u64;
289        drop(buf);
290        self.budget.fetch_add(bytes, Ordering::Release);
291        self.freed += 1;
292    }
293
294    /// Frees cached buffers of classes other than `class` until the budget holds
295    /// one buffer of `class`, for an output that charges the budget itself
296    /// (`Output::refill`). Looks at the shared budget only when this pool caches
297    /// something, so the common case costs no atomic read.
298    pub(crate) fn make_room(&mut self, class: SizeClass) {
299        let bytes = u64::from(class.bytes());
300        while self.free_bytes > 0 && self.budget.load(Ordering::Relaxed) < bytes {
301            if !self.free_other(class) {
302                return;
303            }
304        }
305    }
306
307    /// A buffer of `class` this pool already holds; never allocates or charges the
308    /// budget.
309    pub(crate) fn take_cached(&mut self, class: SizeClass) -> Option<Buffer> {
310        self.pop(class)
311    }
312
313    fn pop(&mut self, class: SizeClass) -> Option<Buffer> {
314        let buf = self.list(class).pop()?;
315        self.free_bytes = self.free_bytes.saturating_sub(buf.capacity() as u64);
316        Some(buf)
317    }
318
319    /// Returns a buffer; its used part is wiped first unless wiping is off.
320    ///
321    /// A buffer from another worker's pool is accepted (it is just memory). When the
322    /// free lists already hold what this pool keeps, the buffer is freed and its
323    /// bytes go back to the shared budget instead.
324    ///
325    /// ```
326    /// use net_io::{BufferPool, SizeClass};
327    /// let mut pool = BufferPool::standalone(1 << 20);
328    /// let b = pool.take(SizeClass::SMALL).unwrap();
329    /// pool.put(b);
330    /// assert_eq!(pool.stats().free, 1);
331    /// ```
332    pub fn put(&mut self, mut buf: Buffer) {
333        if buf.data.is_empty() {
334            // A stand-in owns no memory and was never charged to the budget.
335            return;
336        }
337        // Wiped before it is kept or freed: freed memory goes back to the
338        // allocator, which hands it to other code in the process.
339        if self.wipe {
340            buf.wipe();
341        } else {
342            buf.clear();
343        }
344        let bytes = buf.capacity() as u64;
345        if self.free_bytes.saturating_add(bytes) > self.keep {
346            return self.refund(buf);
347        }
348        self.free_bytes += bytes;
349        let class = buf.class;
350        self.list(class).push(buf);
351    }
352
353    /// Counts of this pool.
354    #[must_use]
355    pub fn stats(&self) -> PoolStats {
356        PoolStats {
357            allocated: self.allocated,
358            free: self.lists.iter().map(|(_, l)| l.len() as u64).sum(),
359            budget_left: self.budget.load(Ordering::Relaxed),
360            budget_refusals: self.refusals,
361            freed: self.freed,
362        }
363    }
364
365    fn list(&mut self, class: SizeClass) -> &mut Vec<Buffer> {
366        let pos = match self.lists.iter().position(|(c, _)| *c == class) {
367            Some(p) => p,
368            None => {
369                self.lists.push((class, Vec::new()));
370                self.lists.len() - 1
371            }
372        };
373        &mut self.lists[pos].1
374    }
375}
376
377impl fmt::Debug for BufferPool {
378    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
379        f.debug_struct("BufferPool")
380            .field("stats", &self.stats())
381            .finish()
382    }
383}
384
385#[cfg(test)]
386mod tests {
387    use super::*;
388
389    #[test]
390    fn test_pool_reuses_and_wipes() {
391        let mut pool = BufferPool::standalone(1 << 20);
392        let mut b = pool.take(SizeClass::SMALL).unwrap();
393        b.spare()[..6].copy_from_slice(b"secret");
394        b.set_len(6);
395        pool.put(b);
396        let mut b = pool.take(SizeClass::SMALL).unwrap();
397        assert_eq!(pool.stats().allocated, 1);
398        assert!(b.is_empty());
399        b.set_len(6);
400        assert_eq!(b.as_slice(), &[0u8; 6]);
401    }
402
403    /// Bytes left behind a shorter `len` are wiped too: a cleared buffer, a
404    /// compacted one, and a consumed input (only `[..len]` was, once).
405    #[test]
406    fn test_pool_wipes_what_a_shorter_len_left_behind() {
407        let mut pool = BufferPool::standalone(1 << 20);
408        let mut b = pool.take(SizeClass::SMALL).unwrap();
409        b.spare()[..12].copy_from_slice(b"token=secret");
410        b.set_len(12);
411        b.clear();
412        pool.put(b);
413        let mut b = pool.take(SizeClass::SMALL).unwrap();
414        b.set_len(b.capacity());
415        assert!(
416            b.as_slice().iter().all(|&x| x == 0),
417            "cleared bytes survived"
418        );
419        b.set_len(0);
420        b.spare()[..12].copy_from_slice(b"token=secret");
421        b.set_len(12);
422        b.compact(6);
423        assert_eq!(b.as_slice(), b"secret");
424        pool.put(b);
425        let mut b = pool.take(SizeClass::SMALL).unwrap();
426        b.set_len(b.capacity());
427        assert!(
428            b.as_slice().iter().all(|&x| x == 0),
429            "compacted tail survived"
430        );
431        let mut input = crate::session::Input::new({
432            b.set_len(0);
433            b
434        });
435        input.buf.spare()[..6].copy_from_slice(b"secret");
436        input.filled(6);
437        input.consume(6);
438        pool.put(input.buf);
439        let mut b = pool.take(SizeClass::SMALL).unwrap();
440        b.set_len(b.capacity());
441        assert!(
442            b.as_slice().iter().all(|&x| x == 0),
443            "consumed input survived"
444        );
445    }
446
447    #[test]
448    fn test_pool_budget_bounds_allocation() {
449        let mut pool = BufferPool::standalone(u64::from(SizeClass::SMALL.bytes()) * 2);
450        let a = pool.take(SizeClass::SMALL).unwrap();
451        let _b = pool.take(SizeClass::SMALL).unwrap();
452        assert!(pool.take(SizeClass::SMALL).is_none());
453        assert_eq!(pool.stats().budget_refusals, 1);
454        pool.put(a);
455        assert!(pool.take(SizeClass::SMALL).is_some());
456    }
457
458    #[test]
459    fn test_set_len_saturates_and_compact_moves_tail() {
460        let mut pool = BufferPool::standalone(1 << 20);
461        let mut b = pool.take(SizeClass::SMALL).unwrap();
462        b.set_len(usize::MAX);
463        assert_eq!(b.len(), b.capacity());
464        b.set_len(0);
465        b.spare()[..4].copy_from_slice(b"abcd");
466        b.set_len(4);
467        b.compact(2);
468        assert_eq!(b.as_slice(), b"cd");
469        b.compact(99);
470        assert!(b.is_empty());
471    }
472
473    #[test]
474    fn test_pool_without_wipe_keeps_bytes_but_empties() {
475        let mut pool = BufferPool::new(Arc::new(AtomicU64::new(1 << 20)), false, 1 << 20);
476        let mut b = pool.take(SizeClass::SMALL).unwrap();
477        b.spare()[0] = 9;
478        b.set_len(1);
479        pool.put(b);
480        let b = pool.take(SizeClass::SMALL).unwrap();
481        assert!(b.is_empty());
482    }
483
484    const LARGE: u64 = SizeClass::LARGE.bytes() as u64;
485    const MEDIUM: u64 = SizeClass::MEDIUM.bytes() as u64;
486
487    /// A take whose class has nothing cached and finds the budget spent frees what
488    /// the pool caches of other classes, the largest first, and only as much as the
489    /// charge needs (before, those bytes stayed spent until the process ended).
490    #[test]
491    fn test_take_frees_other_classes_for_the_charge() {
492        let mut pool = BufferPool::standalone(2 * LARGE + 2 * u64::from(SizeClass::SMALL.bytes()));
493        let held: Vec<Buffer> = vec![
494            pool.take(SizeClass::LARGE).unwrap(),
495            pool.take(SizeClass::LARGE).unwrap(),
496            pool.take(SizeClass::SMALL).unwrap(),
497            pool.take(SizeClass::SMALL).unwrap(),
498        ];
499        assert!(pool.take(SizeClass::MEDIUM).is_none(), "budget spent");
500        assert_eq!(pool.stats().budget_refusals, 1);
501        for b in held {
502            pool.put(b);
503        }
504        assert_eq!(pool.stats().budget_left, 0);
505        assert_eq!(pool.stats().free, 4);
506
507        let m = pool
508            .take(SizeClass::MEDIUM)
509            .expect("room made from other classes");
510        assert_eq!(m.capacity() as u64, MEDIUM);
511        let s = pool.stats();
512        assert_eq!(s.freed, 1, "one 64 KiB buffer covers the charge: {s:?}");
513        assert_eq!(s.budget_left, LARGE - MEDIUM);
514        assert_eq!(s.free, 3, "the small buffers and one large stay cached");
515        // Its own class is reused before anything is freed.
516        pool.put(m);
517        let m = pool.take(SizeClass::MEDIUM).unwrap();
518        assert_eq!(pool.stats().freed, 1);
519        // A charge that all the cached buffers could not cover is refused without
520        // freeing any of them.
521        let big = SizeClass::new(1 << 20).unwrap();
522        assert!(pool.take(big).is_none());
523        let s = pool.stats();
524        assert_eq!((s.budget_refusals, s.freed, s.free), (2, 1, 3), "{s:?}");
525        drop(m);
526    }
527
528    /// A release above what a pool keeps frees the buffer and refunds the budget;
529    /// below it the buffer is cached as before.
530    #[test]
531    fn test_put_above_the_keep_limit_refunds_the_budget() {
532        let budget = Arc::new(AtomicU64::new(4 * LARGE));
533        let mut pool = BufferPool::new(budget.clone(), true, LARGE + MEDIUM);
534        let held: Vec<Buffer> = (0..4)
535            .map(|_| pool.take(SizeClass::LARGE).unwrap())
536            .collect();
537        assert_eq!(budget.load(Ordering::Relaxed), 0);
538        for b in held {
539            pool.put(b);
540        }
541        let s = pool.stats();
542        assert_eq!(s.free, 1, "{s:?}");
543        assert_eq!(s.freed, 3);
544        assert_eq!(s.budget_left, 3 * LARGE, "memory freed, budget refunded");
545        // A smaller buffer still fits beside the kept one.
546        let m = pool.take(SizeClass::MEDIUM).unwrap();
547        pool.put(m);
548        assert_eq!(pool.stats().free, 2);
549        assert_eq!(pool.stats().freed, 3);
550        // A stand-in is neither kept nor refunded.
551        #[cfg(feature = "reactor")]
552        pool.put(Buffer::placeholder());
553        assert_eq!(pool.stats().freed, 3);
554        assert_eq!(budget.load(Ordering::Relaxed), 3 * LARGE - MEDIUM);
555    }
556
557    /// `standalone` keeps everything released to it, as before: its keep limit is
558    /// its whole budget, so released buffers are reused and the budget stays spent.
559    #[test]
560    fn test_standalone_pool_keeps_what_it_releases() {
561        let mut pool = BufferPool::standalone(4 * LARGE);
562        let held: Vec<Buffer> = (0..4)
563            .map(|_| pool.take(SizeClass::LARGE).unwrap())
564            .collect();
565        for b in held {
566            pool.put(b);
567        }
568        let s = pool.stats();
569        assert_eq!((s.free, s.freed, s.budget_left), (4, 0, 0), "{s:?}");
570        for _ in 0..4 {
571            assert!(pool.take(SizeClass::LARGE).is_some());
572        }
573        assert_eq!(pool.stats().allocated, 4, "reused, not allocated again");
574    }
575
576    /// An output's room comes from other classes' cached buffers too.
577    #[test]
578    fn test_make_room_frees_other_classes_only_when_short() {
579        let mut pool = BufferPool::standalone(LARGE + MEDIUM);
580        let l = pool.take(SizeClass::LARGE).unwrap();
581        pool.put(l);
582        pool.make_room(SizeClass::MEDIUM);
583        assert_eq!(pool.stats().freed, 0, "the budget already holds one");
584        let m = pool.take(SizeClass::MEDIUM).unwrap();
585        pool.make_room(SizeClass::MEDIUM);
586        let s = pool.stats();
587        assert_eq!((s.freed, s.budget_left, s.free), (1, LARGE, 0), "{s:?}");
588        drop(m);
589    }
590
591    /// The cost of T-16: `cargo test --release --lib bench_ -- --ignored --nocapture`.
592    #[test]
593    #[ignore = "a benchmark"]
594    fn bench_wipe() {
595        for (name, used) in [("2 KiB", 2048), ("16 KiB", 16 * 1024)] {
596            let mut b = Buffer::new(SizeClass::MEDIUM);
597            let rounds = 1_000_000u32;
598            let started = std::time::Instant::now();
599            for _ in 0..rounds {
600                b.set_len(used);
601                b.wipe();
602            }
603            let ns = started.elapsed().as_nanos() as f64 / f64::from(rounds);
604            println!("Wipe {name}: {ns:.1} ns");
605        }
606    }
607}