arrow_buffer/pool.rs
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! This module contains traits for memory pool traits and an implementation
6//! for tracking memory usage.
7//!
8//! The basic traits are [`MemoryPool`] and [`MemoryReservation`]. And default
9//! implementation of [`MemoryPool`] is [`TrackingMemoryPool`]. Their relationship
10//! is as follows:
11//!
12//! ```text
13//! (pool tracker) (resizable)
14//! ┌──────────────────┐ fn reserve() ┌─────────────────────────┐
15//! │ trait MemoryPool │─────────────►│ trait MemoryReservation │
16//! └──────────────────┘ └─────────────────────────┘
17//! ```
18
19use std::fmt::Debug;
20use std::sync::atomic::{AtomicUsize, Ordering};
21use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
22
23/// A memory reservation within a [`MemoryPool`] that is freed on drop
24pub trait MemoryReservation: Debug + Send + Sync {
25 /// Returns the size of this reservation in bytes.
26 fn size(&self) -> usize;
27
28 /// Resize this reservation to a new size in bytes.
29 fn resize(&mut self, new_size: usize);
30}
31
32/// A pool of memory that can be reserved and released.
33///
34/// This is used to accurately track memory usage when buffers are shared
35/// between multiple arrays or other data structures.
36///
37/// For example, assume we have two arrays that share underlying buffer.
38/// It's hard to tell how much memory is used by them because we can't
39/// tell if the buffer is shared or not.
40///
41/// ```text
42/// Array A Array B
43/// ┌────────────┐ ┌────────────┐
44/// │ slices... │ │ slices... │
45/// │────────────│ │────────────│
46/// │ Arc<Bytes> │ │ Arc<Bytes> │ (shared buffer)
47/// └─────▲──────┘ └───────▲────┘
48/// │ │
49/// │ Bytes │
50/// │ ┌─────────────┐ │
51/// │ │ data... │ │
52/// │ │─────────────│ │
53/// └──│ Memory │──┘ (tracked with a memory pool)
54/// │ Reservation │
55/// └─────────────┘
56/// ```
57///
58/// With a memory pool, we can count the memory usage by the shared buffer
59/// directly.
60pub trait MemoryPool: Debug + Send + Sync {
61 /// Reserves memory from the pool. Infallible.
62 ///
63 /// Returns a reservation of the requested size.
64 fn reserve(&self, size: usize) -> Box<dyn MemoryReservation>;
65
66 /// Returns the current available memory in the pool.
67 ///
68 /// The pool may be overfilled, so this method might return a negative value.
69 fn available(&self) -> isize;
70
71 /// Returns the current used memory from the pool.
72 fn used(&self) -> usize;
73
74 /// Returns the maximum memory that can be reserved from the pool.
75 fn capacity(&self) -> usize;
76}
77
78/// A simple [`MemoryPool`] that reports the total memory usage
79#[derive(Debug, Default)]
80pub struct TrackingMemoryPool(Arc<AtomicUsize>);
81
82impl TrackingMemoryPool {
83 /// Returns the total allocated size
84 pub fn allocated(&self) -> usize {
85 self.0.load(Ordering::Relaxed)
86 }
87}
88
89impl MemoryPool for TrackingMemoryPool {
90 fn reserve(&self, size: usize) -> Box<dyn MemoryReservation> {
91 self.0.fetch_add(size, Ordering::Relaxed);
92 Box::new(Tracker {
93 size,
94 shared: Arc::clone(&self.0),
95 })
96 }
97
98 fn available(&self) -> isize {
99 isize::MAX - self.used() as isize
100 }
101
102 fn used(&self) -> usize {
103 self.0.load(Ordering::Relaxed)
104 }
105
106 fn capacity(&self) -> usize {
107 usize::MAX
108 }
109}
110
111#[derive(Debug)]
112struct Tracker {
113 size: usize,
114 shared: Arc<AtomicUsize>,
115}
116
117impl Drop for Tracker {
118 fn drop(&mut self) {
119 self.shared.fetch_sub(self.size, Ordering::Relaxed);
120 }
121}
122
123impl MemoryReservation for Tracker {
124 fn size(&self) -> usize {
125 self.size
126 }
127
128 fn resize(&mut self, new: usize) {
129 match self.size < new {
130 true => self.shared.fetch_add(new - self.size, Ordering::Relaxed),
131 false => self.shared.fetch_sub(self.size - new, Ordering::Relaxed),
132 };
133 self.size = new;
134 }
135}
136
137/// Lock a memory reservation, recovering from a poisoned lock.
138///
139/// A poisoned lock only means that some other thread panicked. The reservation it
140/// guards is plain size accounting, so there is no broken invariant to protect, and
141/// recovering it is always preferable to panicking.
142pub(crate) fn lock_reservation(
143 reservation: &Mutex<Option<Box<dyn MemoryReservation>>>,
144) -> MutexGuard<'_, Option<Box<dyn MemoryReservation>>> {
145 reservation.lock().unwrap_or_else(PoisonError::into_inner)
146}
147
148/// This is a wrapper for the reservation so we can standardize on changing
149/// and avoid race conditions in memory accounting
150#[derive(Debug, Default)]
151pub(crate) struct TrackedReservation {
152 reservation: Mutex<Option<Box<dyn MemoryReservation>>>,
153}
154
155impl TrackedReservation {
156 /// Claim memory from a pool, replacing the current reservation (if exists).
157 pub fn claim(&self, pool: &dyn MemoryPool, capacity: usize) {
158 // get the existing reservation
159 let mut guard = lock_reservation(&self.reservation);
160
161 // drop it before we reserve the new one
162 drop(guard.take());
163
164 // reserve the new one
165 *guard = Some(pool.reserve(capacity))
166 }
167
168 /// Resize the memory reservation of this buffer
169 ///
170 /// This is a no-op if this buffer doesn't have a reservation.
171 pub fn resize(&self, new_size: usize) {
172 if let Some(reservation) = lock_reservation(&self.reservation).as_mut() {
173 // Resize the reservation
174 reservation.resize(new_size);
175 }
176 }
177
178 /// Takes ownership of the reservation and returns it in a new `TrackedReservation`
179 pub fn take(&self) -> Self {
180 let reservation = lock_reservation(&self.reservation).take();
181
182 Self {
183 reservation: Mutex::new(reservation),
184 }
185 }
186
187 /// Replaces the current tracked reservation with `other`, consuming it.
188 pub fn replace(&self, other: Self) {
189 // get the owned value out, preventing double lock
190 let reservation = other
191 .reservation
192 .into_inner()
193 .unwrap_or_else(PoisonError::into_inner);
194
195 let mut guard = lock_reservation(&self.reservation);
196
197 // drop the old reservation before installing the new one
198 drop(guard.take());
199 *guard = reservation;
200 }
201}
202
203#[cfg(test)]
204mod tests {
205 use super::*;
206
207 #[test]
208 fn test_tracking_memory_pool() {
209 let pool = TrackingMemoryPool::default();
210
211 // Reserve 512 bytes
212 let reservation = pool.reserve(512);
213 assert_eq!(reservation.size(), 512);
214 assert_eq!(pool.used(), 512);
215 assert_eq!(pool.available(), isize::MAX - 512);
216
217 // Reserve another 256 bytes
218 let reservation2 = pool.reserve(256);
219 assert_eq!(reservation2.size(), 256);
220 assert_eq!(pool.used(), 768);
221 assert_eq!(pool.available(), isize::MAX - 768);
222
223 // Test resize to increase
224 let mut reservation_mut = reservation;
225 reservation_mut.resize(600);
226 assert_eq!(reservation_mut.size(), 600);
227 assert_eq!(pool.used(), 856); // 600 + 256
228
229 // Test resize to decrease
230 reservation_mut.resize(400);
231 assert_eq!(reservation_mut.size(), 400);
232 assert_eq!(pool.used(), 656); // 400 + 256
233
234 // Drop the first reservation
235 drop(reservation_mut);
236 assert_eq!(pool.used(), 256);
237
238 // Drop the second reservation
239 drop(reservation2);
240 assert_eq!(pool.used(), 0);
241 }
242
243 /// A [`MemoryPool`] that records the peak usage observed at the instant
244 /// each reservation is taken, letting a single-threaded test witness the
245 /// transient double-count that [`TrackedReservation::claim`] must avoid.
246 #[derive(Debug, Default)]
247 struct PeakPool {
248 inner: TrackingMemoryPool,
249 peak: AtomicUsize,
250 }
251
252 impl MemoryPool for PeakPool {
253 fn reserve(&self, size: usize) -> Box<dyn MemoryReservation> {
254 let reservation = self.inner.reserve(size);
255 self.peak.fetch_max(self.inner.used(), Ordering::Relaxed);
256 reservation
257 }
258
259 fn available(&self) -> isize {
260 self.inner.available()
261 }
262
263 fn used(&self) -> usize {
264 self.inner.used()
265 }
266
267 fn capacity(&self) -> usize {
268 self.inner.capacity()
269 }
270 }
271
272 #[test]
273 fn test_claim_reclaims_before_reserving() {
274 let pool = PeakPool::default();
275 let reservation = TrackedReservation::default();
276
277 // Claim 512 bytes.
278 reservation.claim(&pool, 512);
279 assert_eq!(pool.used(), 512);
280
281 // Re-claim the same amount. The old reservation must be released
282 // before the new one is taken, so usage never transiently doubles
283 // (see #10139).
284 reservation.claim(&pool, 512);
285 assert_eq!(pool.used(), 512);
286 assert_eq!(
287 pool.peak.load(Ordering::Relaxed),
288 512,
289 "claim double-counted memory while reclaiming"
290 );
291 }
292}