Skip to content

Commit 407ab7a

Browse files
authored
fix: count the largest capacity seen for a shared buffer address (apache#27097)
## Which issue does this PR close? - Closes apache#27069. ## Rationale for this change A sort over batches that came through the Arrow C Data Interface as zero-copy slices of one larger batch panics, in release builds too: ``` assertion failed: reservation.size() + shared.size() >= reserved_bytes ``` This is a regression in 56 (it comes from the shared-buffer accounting added in apache#25820). Apache DataFusion Comet hits it on TPC-DS q67a, where the sort input arrives from the JVM through FFI. `RecordBatchMemoryCounter` identifies a buffer by its start address and sizes it with `Buffer::capacity()`, keeping the first capacity it sees for an address. A buffer from `Buffer::from_custom_allocation`, which is what `arrow::ffi::from_ffi` builds, reports the length it was imported with rather than the size of the allocation. Slices of one batch that are exported and imported separately therefore share a start address but report different capacities. When a smaller one is counted first, the shared input size from `sort_run_sizes` ends up below a later run's own `get_record_batch_memory_size`, and the check in `sort_run` fails. `RecordBatchMemoryTracker` has the same problem in its uncount path. It adds the capacity of the buffer that brings an address's count from 0 to 1, but subtracts the capacity of whichever buffer brings it back to 0. If that one is larger, `memory_usage` underflows, and TopK's `checked_sub(..).unwrap()` on its batch store size panics. ## What changes are included in this PR? - `BufferIdSet` (used by the counter) stores the capacity counted for each address, both inline and in the overflow map. `insert` returns the bytes not counted yet: the full capacity for a new address, the growth when a larger capacity shows up at a known address, and 0 otherwise. - `BufferIdMap` (used by the tracker) stores the counted capacity next to each reference count. `increment` returns the bytes added the same way, and `decrement` returns the recorded capacity when the count reaches 0, so the tracker always releases exactly what it added. - The inline addresses stay in their own contiguous array and the capacities go in a parallel one, so the lookup scan still only touches addresses. - `ExternalSorter::sort_run` returns an internal error instead of panicking when either of its reservation checks fails, so a future accounting mismatch fails the query rather than aborting the process, which for Comet is the JVM. `record_batch_memory` against `main`, as medians of 8 alternating rounds on an M3 Max: a one-column batch goes from 8.5 ns to 12.8 ns because the counter is larger to construct (7.8 ns to 13.1 ns on its own), `shared_slices/16` is 8–11% slower, `count_uncount/16` and `count_uncount/64` are up to 6% slower, and the rest are within ±4% or within the variation between rounds. Buffers that agree on capacity at a shared address, which covers every buffer not built with `Buffer::from_custom_allocation`, are counted exactly as before. One behavior to note: the tracker keeps an address charged at the largest capacity seen until every buffer at that address is released, even after the largest one is released. The allocation is at least that large and stays alive while any slice of it is held, so the overestimate is safe, and it keeps count and uncount symmetric. ## What is the testing strategy for this PR? - `sort_runs_sharing_address_with_different_capacities` in `sorts/sort.rs` sorts two runs over one custom allocation that declare 16 and 1024 values, with `sort_in_place_threshold_bytes` set to 0 so each batch stays its own run. Without the fix, the check above fails, now as an internal error rather than a panic. - `test_record_batch_memory_counter_counts_largest_capacity_at_address` in `utils/memory.rs` counts two arrays over one allocation in both orders, with the inline set and after promotion to the overflow map, and checks the bytes each call returns and the total. - `test_uncount_releases_largest_capacity_at_address` counts the smaller array and then the larger one, releases them in that order, and checks that the tracker returns to its starting usage, inline and after promotion. ## Are there any user-facing changes? No. Sorting FFI-imported sliced batches no longer panics, and if the sort's reservation check fails again, the query fails with an internal error instead of a panic. Memory accounting for buffers that share an address and disagree on capacity is now at least as large as before. No public API changes.
1 parent 25beec8 commit 407ab7a

2 files changed

Lines changed: 230 additions & 66 deletions

File tree

‎datafusion/common/src/utils/memory.rs‎

Lines changed: 170 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
//! This module provides a function to estimate the memory size of a HashTable prior to allocation
66
77
use crate::error::_exec_datafusion_err;
8+
use crate::hash_map::Entry;
89
use crate::{HashMap, HashSet, Result};
910
use arrow::array::types::{
1011
ByteArrayType, ByteViewType, Int8Type, Int16Type, Int32Type, Int64Type,
@@ -226,9 +227,9 @@ impl RecordBatchMemoryCounter {
226227

227228
impl BufferVisitor for RecordBatchMemoryCounter {
228229
fn visit(&mut self, buffer: &Buffer) {
229-
if self.counted_buffers.insert(buffer.data_ptr().addr()) {
230-
self.memory_usage += buffer.capacity();
231-
}
230+
self.memory_usage += self
231+
.counted_buffers
232+
.insert(buffer.data_ptr().addr(), buffer.capacity());
232233
}
233234
}
234235

@@ -237,8 +238,8 @@ impl BufferVisitor for RecordBatchMemoryCounter {
237238
/// Operators that retain batches incrementally and drop them later (sort,
238239
/// window, sort-merge join, TopK) count a batch when they retain it and
239240
/// [`Self::uncount_batch`] it when they drop it. The tracker keeps a reference
240-
/// count per buffer: a buffer's capacity is added when its count goes from 0
241-
/// to 1 and subtracted when it returns to 0.
241+
/// count per buffer: it is charged the largest capacity seen while its count
242+
/// is positive, and released when its count returns to 0.
242243
///
243244
/// **Contract**: a batch must be uncounted *before* its buffers are dropped.
244245
/// The tracker identifies buffers by their data-pointer address and does not
@@ -373,9 +374,9 @@ impl RecordBatchMemoryTracker {
373374
/// Counting visitor: retains each buffer once more.
374375
impl BufferVisitor for RecordBatchMemoryTracker {
375376
fn visit(&mut self, buffer: &Buffer) {
376-
if self.counted_buffers.increment(buffer.data_ptr().addr()) {
377-
self.memory_usage += buffer.capacity();
378-
}
377+
self.memory_usage += self
378+
.counted_buffers
379+
.increment(buffer.data_ptr().addr(), buffer.capacity());
379380
}
380381
}
381382

@@ -384,9 +385,7 @@ struct Uncount<'a>(&'a mut RecordBatchMemoryTracker);
384385

385386
impl BufferVisitor for Uncount<'_> {
386387
fn visit(&mut self, buffer: &Buffer) {
387-
if self.0.counted_buffers.decrement(buffer.data_ptr().addr()) {
388-
self.0.memory_usage -= buffer.capacity();
389-
}
388+
self.0.memory_usage -= self.0.counted_buffers.decrement(buffer.data_ptr().addr());
390389
}
391390
}
392391

@@ -604,137 +603,157 @@ fn array_children(array: &ArrayRef) -> Vec<&ArrayRef> {
604603
}
605604

606605
/// Tracks a small number of buffers inline, avoiding a heap allocation for
607-
/// typical batches, and promotes to a hash set when more buffers are seen.
606+
/// typical batches, and promotes to a hash map when more buffers are seen.
607+
///
608+
/// Keeps the largest capacity seen per address: buffers built with
609+
/// `Buffer::from_custom_allocation`, such as FFI imports, can share an address
610+
/// while reporting different capacities.
608611
#[derive(Debug)]
609612
struct BufferIdSet {
610613
inline: [Option<NonZero<usize>>; INLINE_BUFFER_IDS],
614+
/// Counted capacity of each inline buffer, parallel to `inline`.
615+
capacities: [usize; INLINE_BUFFER_IDS],
611616
len: usize,
612-
overflow: Option<HashSet<NonZero<usize>>>,
617+
overflow: Option<HashMap<NonZero<usize>, usize>>,
613618
}
614619

615620
impl Default for BufferIdSet {
616621
fn default() -> Self {
617622
Self {
618623
inline: [None; INLINE_BUFFER_IDS],
624+
capacities: [0; INLINE_BUFFER_IDS],
619625
len: 0,
620626
overflow: None,
621627
}
622628
}
623629
}
624630

625631
impl BufferIdSet {
626-
fn insert(&mut self, buffer_id: NonZero<usize>) -> bool {
632+
/// Returns the bytes of `capacity` not already counted for `buffer_id`.
633+
fn insert(&mut self, buffer_id: NonZero<usize>, capacity: usize) -> usize {
627634
if let Some(overflow) = &mut self.overflow {
628-
return overflow.insert(buffer_id);
635+
let counted = overflow.entry(buffer_id).or_insert(0);
636+
return grow_counted_capacity(counted, capacity);
629637
}
630638

631-
if self.inline[..self.len].contains(&Some(buffer_id)) {
632-
return false;
639+
for i in 0..self.len {
640+
if self.inline[i] == Some(buffer_id) {
641+
return grow_counted_capacity(&mut self.capacities[i], capacity);
642+
}
633643
}
634644

635645
if self.len < INLINE_BUFFER_IDS {
636646
self.inline[self.len] = Some(buffer_id);
647+
self.capacities[self.len] = capacity;
637648
self.len += 1;
638-
return true;
649+
return capacity;
639650
}
640651

641-
let mut overflow = HashSet::with_capacity(INLINE_BUFFER_IDS + 1);
642-
overflow.extend(self.inline.iter().flatten().copied());
643-
let inserted = overflow.insert(buffer_id);
652+
let mut overflow = HashMap::with_capacity(INLINE_BUFFER_IDS + 1);
653+
overflow.extend(self.inline.iter().flatten().copied().zip(self.capacities));
654+
overflow.insert(buffer_id, capacity);
644655
self.overflow = Some(overflow);
645-
inserted
656+
capacity
646657
}
647658
}
648659

660+
/// Raises `counted` to `capacity` if that is larger, returning the growth.
661+
#[inline(always)]
662+
fn grow_counted_capacity(counted: &mut usize, capacity: usize) -> usize {
663+
let growth = capacity.saturating_sub(*counted);
664+
*counted += growth;
665+
growth
666+
}
667+
649668
/// Reference-counted buffer tracker with an inline fast path.
650669
///
651-
/// Tracks buffer addresses with their reference counts. The first
652-
/// [`INLINE_BUFFER_IDS`] distinct buffers are stored in a fixed-size inline
653-
/// array to avoid heap allocation for typical batches. When more buffers are
654-
/// encountered, the tracker promotes to a heap-allocated `HashMap`.
670+
/// Tracks buffer addresses with their reference counts and counted capacities
671+
/// (the largest seen, as in [`BufferIdSet`]). The first [`INLINE_BUFFER_IDS`]
672+
/// distinct buffers are stored in fixed-size inline arrays to avoid heap
673+
/// allocation for typical batches. When more buffers are encountered, the
674+
/// tracker promotes to a heap-allocated `HashMap`.
655675
///
656-
/// The inline path stores addresses and counts in **separate** arrays so that
657-
/// the hot `position()` scan over addresses touches a contiguous
676+
/// The inline path stores addresses, counts and capacities in **separate**
677+
/// arrays so that the hot scan over addresses touches a contiguous
658678
/// `[Option<NonZero<usize>>; 16]` (128 bytes, two cache lines) without
659-
/// interleaved count words, matching the layout of the previous insert-only
660-
/// `BufferIdSet`.
679+
/// interleaved count words.
661680
#[derive(Debug)]
662681
struct BufferIdMap {
663682
/// Inline storage: buffer addresses (None = empty slot).
664683
ids: [Option<NonZero<usize>>; INLINE_BUFFER_IDS],
665684
/// Inline storage: per-slot reference counts, parallel to `ids`.
666685
counts: [u32; INLINE_BUFFER_IDS],
686+
/// Inline storage: per-slot counted capacities, parallel to `ids`.
687+
capacities: [usize; INLINE_BUFFER_IDS],
667688
/// Number of occupied inline slots.
668689
len: usize,
669690
/// Overflow storage used when more than `INLINE_BUFFER_IDS` distinct
670-
/// buffers are tracked.
671-
overflow: Option<HashMap<NonZero<usize>, u32>>,
691+
/// buffers are tracked: (reference count, counted capacity).
692+
overflow: Option<HashMap<NonZero<usize>, (u32, usize)>>,
672693
}
673694

674695
impl Default for BufferIdMap {
675696
fn default() -> Self {
676697
Self {
677698
ids: [None; INLINE_BUFFER_IDS],
678699
counts: [0; INLINE_BUFFER_IDS],
700+
capacities: [0; INLINE_BUFFER_IDS],
679701
len: 0,
680702
overflow: None,
681703
}
682704
}
683705
}
684706

685707
impl BufferIdMap {
686-
/// Increment the reference count for `buffer_id`. Returns `true` when the
687-
/// count went from 0 to 1 (i.e., the buffer is newly tracked).
708+
/// Increment the reference count for `buffer_id`, returning the bytes of
709+
/// `capacity` not already counted for it.
688710
#[inline(always)]
689-
fn increment(&mut self, buffer_id: NonZero<usize>) -> bool {
711+
fn increment(&mut self, buffer_id: NonZero<usize>, capacity: usize) -> usize {
690712
if let Some(overflow) = &mut self.overflow {
691-
let count = overflow.entry(buffer_id).or_insert(0);
713+
let (count, counted) = overflow.entry(buffer_id).or_insert((0, 0));
692714
*count += 1;
693-
return *count == 1;
715+
return grow_counted_capacity(counted, capacity);
694716
}
695717

696718
// Search inline slots.
697-
if let Some(i) = self.ids[..self.len]
698-
.iter()
699-
.position(|id| *id == Some(buffer_id))
700-
{
701-
self.counts[i] += 1;
702-
return false; // Already tracked, count > 1 now.
719+
for i in 0..self.len {
720+
if self.ids[i] == Some(buffer_id) {
721+
self.counts[i] += 1;
722+
return grow_counted_capacity(&mut self.capacities[i], capacity);
723+
}
703724
}
704725

705726
// New buffer: try inline first.
706727
if self.len < INLINE_BUFFER_IDS {
707728
self.ids[self.len] = Some(buffer_id);
708729
self.counts[self.len] = 1;
730+
self.capacities[self.len] = capacity;
709731
self.len += 1;
710-
return true;
732+
return capacity;
711733
}
712734

713735
// Promote to overflow.
714736
let mut overflow = HashMap::with_capacity(INLINE_BUFFER_IDS + 1);
715737
for i in 0..self.len {
716738
if let Some(id) = self.ids[i] {
717-
overflow.insert(id, self.counts[i]);
739+
overflow.insert(id, (self.counts[i], self.capacities[i]));
718740
}
719741
}
720-
overflow.insert(buffer_id, 1);
742+
overflow.insert(buffer_id, (1, capacity));
721743
self.overflow = Some(overflow);
722-
true
744+
capacity
723745
}
724746

725-
/// Decrement the reference count for `buffer_id`. Returns `true` when the
726-
/// count reached zero (i.e., the buffer is no longer tracked). Returns
727-
/// `false` if the buffer was not tracked or its count is still positive.
728-
fn decrement(&mut self, buffer_id: NonZero<usize>) -> bool {
747+
/// Decrement the reference count for `buffer_id`, returning its counted
748+
/// capacity when the count reaches zero and 0 otherwise.
749+
fn decrement(&mut self, buffer_id: NonZero<usize>) -> usize {
729750
if let Some(overflow) = &mut self.overflow {
730-
if let Some(count) = overflow.get_mut(&buffer_id) {
731-
*count -= 1;
732-
if *count == 0 {
733-
overflow.remove(&buffer_id);
734-
return true;
735-
}
736-
}
737-
return false;
751+
let Entry::Occupied(mut entry) = overflow.entry(buffer_id) else {
752+
return 0;
753+
};
754+
let (count, _) = entry.get_mut();
755+
*count -= 1;
756+
return if *count == 0 { entry.remove().1 } else { 0 };
738757
}
739758

740759
// Search inline slots.
@@ -743,20 +762,22 @@ impl BufferIdMap {
743762
if self.ids[i] == target {
744763
self.counts[i] -= 1;
745764
if self.counts[i] == 0 {
765+
let counted = self.capacities[i];
746766
// Swap-remove: move last entry here.
747767
self.len -= 1;
748768
if i < self.len {
749769
self.ids[i] = self.ids[self.len];
750770
self.counts[i] = self.counts[self.len];
771+
self.capacities[i] = self.capacities[self.len];
751772
}
752773
self.ids[self.len] = None;
753-
return true;
774+
return counted;
754775
}
755-
return false;
776+
return 0;
756777
}
757778
}
758779

759-
false
780+
0
760781
}
761782
}
762783

@@ -1229,6 +1250,93 @@ mod record_batch_tests {
12291250
assert_eq!(counter.count_batch(&batch), 0);
12301251
}
12311252

1253+
/// Arrays over one allocation with different capacities, as
1254+
/// `arrow::ffi::from_ffi` imports slices of one batch.
1255+
fn custom_allocation_arrays(lens: &[usize]) -> Vec<ArrayRef> {
1256+
use arrow::buffer::ScalarBuffer;
1257+
use std::ptr::NonNull;
1258+
1259+
let max_len = lens.iter().copied().max().unwrap_or(0);
1260+
let owner: Arc<Vec<i32>> = Arc::new((0..max_len as i32).collect());
1261+
let ptr = NonNull::new(owner.as_ptr().cast::<u8>().cast_mut()).unwrap();
1262+
lens.iter()
1263+
.map(|&len| {
1264+
// SAFETY: `owner` holds `len` values at `ptr`; the buffer keeps it alive.
1265+
let buffer = unsafe {
1266+
Buffer::from_custom_allocation(
1267+
ptr,
1268+
len * size_of::<i32>(),
1269+
Arc::clone(&owner) as _,
1270+
)
1271+
};
1272+
Arc::new(Int32Array::new(ScalarBuffer::new(buffer, 0, len), None))
1273+
as ArrayRef
1274+
})
1275+
.collect()
1276+
}
1277+
1278+
/// Arrays that fill the inline slots, so the next buffer promotes to overflow.
1279+
fn inline_filler_arrays() -> Vec<ArrayRef> {
1280+
(0..INLINE_BUFFER_IDS)
1281+
.map(|i| Arc::new(Int32Array::from(vec![i as i32])) as ArrayRef)
1282+
.collect()
1283+
}
1284+
1285+
#[test]
1286+
fn test_record_batch_memory_counter_counts_largest_capacity_at_address() {
1287+
let (small, large) = (16 * size_of::<i32>(), 1024 * size_of::<i32>());
1288+
for promote in [false, true] {
1289+
for (lens, expected) in [
1290+
([16, 1024], (small, large - small)),
1291+
([1024, 16], (large, 0)),
1292+
] {
1293+
let arrays = custom_allocation_arrays(&lens);
1294+
let mut counter = RecordBatchMemoryCounter::new();
1295+
if promote {
1296+
for array in inline_filler_arrays() {
1297+
counter.count_array(array.as_ref());
1298+
}
1299+
}
1300+
let base = counter.memory_usage();
1301+
1302+
let first = counter.count_array(arrays[0].as_ref());
1303+
let second = counter.count_array(arrays[1].as_ref());
1304+
assert_eq!((first, second), expected);
1305+
assert_eq!(counter.memory_usage() - base, large);
1306+
assert_eq!(counter.counted_buffers.overflow.is_some(), promote);
1307+
}
1308+
}
1309+
}
1310+
1311+
#[test]
1312+
fn test_uncount_releases_largest_capacity_at_address() {
1313+
let (small, large) = (16 * size_of::<i32>(), 1024 * size_of::<i32>());
1314+
for promote in [false, true] {
1315+
let arrays = custom_allocation_arrays(&[16, 1024]);
1316+
let mut tracker = RecordBatchMemoryTracker::new();
1317+
let fillers = inline_filler_arrays();
1318+
if promote {
1319+
for array in &fillers {
1320+
tracker.count_array(array.as_ref());
1321+
}
1322+
}
1323+
let base = tracker.memory_usage();
1324+
1325+
assert_eq!(tracker.count_array(arrays[0].as_ref()), small);
1326+
assert_eq!(tracker.count_array(arrays[1].as_ref()), large - small);
1327+
assert_eq!(tracker.counted_buffers.overflow.is_some(), promote);
1328+
// Released at its largest capacity once the last array goes.
1329+
assert_eq!(tracker.uncount_array(arrays[0].as_ref()), 0);
1330+
assert_eq!(tracker.uncount_array(arrays[1].as_ref()), large);
1331+
assert_eq!(tracker.memory_usage(), base);
1332+
1333+
for array in &fillers {
1334+
tracker.uncount_array(array.as_ref());
1335+
}
1336+
assert_eq!(tracker.memory_usage(), 0);
1337+
}
1338+
}
1339+
12321340
#[test]
12331341
fn test_array_memory_size_matches_array_data_layouts() {
12341342
let list_field = Arc::new(Field::new_list_field(DataType::Int32, true));

0 commit comments

Comments
 (0)