1use std::fmt;
4use std::sync::Arc;
5use std::sync::atomic::{AtomicU64, Ordering};
6
7use crate::limits::SizeClass;
8
9pub struct Buffer {
23 data: Box<[u8]>,
24 len: usize,
25 class: SizeClass,
26}
27
28impl Buffer {
29 pub(crate) fn detached(class: SizeClass) -> Buffer {
31 Buffer::new(class)
32 }
33
34 #[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 #[must_use]
55 pub fn as_slice(&self) -> &[u8] {
56 &self.data[..self.len]
57 }
58
59 pub fn as_mut_slice(&mut self) -> &mut [u8] {
61 &mut self.data[..self.len]
62 }
63
64 pub fn spare(&mut self) -> &mut [u8] {
66 &mut self.data[self.len..]
67 }
68
69 #[must_use]
71 pub fn len(&self) -> usize {
72 self.len
73 }
74
75 #[must_use]
77 pub fn is_empty(&self) -> bool {
78 self.len == 0
79 }
80
81 pub fn set_len(&mut self, n: usize) {
83 self.len = n.min(self.data.len());
84 }
85
86 #[must_use]
88 pub fn capacity(&self) -> usize {
89 self.data.len()
90 }
91
92 #[must_use]
94 pub fn class(&self) -> SizeClass {
95 self.class
96 }
97
98 pub fn clear(&mut self) {
100 self.len = 0;
101 }
102
103 pub(crate) fn wipe(&mut self) {
105 let used = &mut self.data[..self.len];
106 used.fill(0);
107 std::hint::black_box(&*used);
110 self.len = 0;
111 }
112
113 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#[non_exhaustive]
137#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
138pub struct PoolStats {
139 pub allocated: u64,
141 pub free: u64,
143 pub budget_left: u64,
145 pub budget_refusals: u64,
147 pub freed: u64,
150}
151
152pub struct BufferPool {
161 lists: Vec<(SizeClass, Vec<Buffer>)>,
162 budget: Arc<AtomicU64>,
163 wipe: bool,
164 allocated: u64,
165 refusals: u64,
166 free_bytes: u64,
168 keep: u64,
170 freed: u64,
171}
172
173impl BufferPool {
174 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 #[must_use]
197 pub fn standalone(bytes: u64) -> BufferPool {
198 BufferPool::new(Arc::new(AtomicU64::new(bytes)), true, bytes)
199 }
200
201 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 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 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 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 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 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 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 pub fn put(&mut self, mut buf: Buffer) {
323 if buf.data.is_empty() {
324 return;
326 }
327 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 #[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 #[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 pool.put(m);
463 let m = pool.take(SizeClass::MEDIUM).unwrap();
464 assert_eq!(pool.stats().freed, 1);
465 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 #[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 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 #[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 #[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 #[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 #[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}