Skip to main content

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}