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