Skip to content

Commit e678b41

Browse files
committed
fix: widen the collect_set arena's byte offsets past 4 GiB
The arena holds encoded values for every group, so its byte addresses are not bounded by any group's own result or by the combined List<i32> element count, which counts elements rather than bytes. A 32-bit start/len pair wrapped once the arena crossed 4 GiB: 0xFFFF_FFFB + 8 came back as 3, and probing, entry_bytes and compaction then sliced an invalid range. start is now 64-bit and the range is computed with checked arithmetic in entry_range. Field order keeps SetEntry at three machine words, so no distinct value pays for the wider offset, and a test pins that. len stays 32-bit with a checked narrowing that errors instead of truncating.
1 parent bf13b3c commit e678b41

1 file changed

Lines changed: 116 additions & 16 deletions

File tree

‎native/spark-expr/src/agg_funcs/collect.rs‎

Lines changed: 116 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -30,13 +30,16 @@ use arrow::buffer::{NullBuffer, OffsetBuffer};
3030
use arrow::compute::{cast, concat, interleave, take};
3131
use arrow::datatypes::{DataType, Field, FieldRef};
3232
use arrow::row::{RowConverter, SortField};
33-
use datafusion::common::{internal_datafusion_err, internal_err, Result as DFResult, ScalarValue};
33+
use datafusion::common::{
34+
internal_datafusion_err, internal_err, DataFusionError, Result as DFResult, ScalarValue,
35+
};
3436
use datafusion::logical_expr::function::{AccumulatorArgs, StateFieldsArgs};
3537
use datafusion::logical_expr::{
3638
Accumulator, AggregateUDFImpl, EmitTo, GroupsAccumulator, Signature,
3739
};
3840
use datafusion_spark::function::aggregate::collect::{SparkCollectList, SparkCollectSet};
3941
use std::mem::{size_of, take as take_field};
42+
use std::ops::Range;
4043
use std::sync::Arc;
4144
use twox_hash::XxHash64;
4245

@@ -503,12 +506,46 @@ fn single_row_lists(
503506
/// One distinct `(group, value)` pair. `start` and `len` address the value's row-encoded bytes
504507
/// in [`CollectSetGroupsAccumulator::arena`], and `hash` is of those bytes alone, so it survives
505508
/// the group renumbering [`CollectSetGroupsAccumulator::compact`] does.
509+
///
510+
/// `start` is 64-bit because the arena holds every group's bytes: a large execution-memory
511+
/// budget can push it past 4 GiB while every group's own result, and the combined `List<i32>`
512+
/// element count, stay valid, since that limit counts elements rather than encoded bytes. `len`
513+
/// stays 32-bit and is range-checked on insert, which keeps the struct at three machine words.
514+
/// Field order is chosen so the wider `start` costs nothing: `size_of::<SetEntry>()` is pinned
515+
/// by [`tests::set_entry_stays_three_words`].
506516
#[derive(Debug, Clone, Copy)]
507517
struct SetEntry {
518+
hash: u64,
519+
start: u64,
508520
group: u32,
509-
start: u32,
510521
len: u32,
511-
hash: u64,
522+
}
523+
524+
/// Largest row-encoded value a [`SetEntry`] can address. A single Spark value cannot approach
525+
/// this, but the conversion is checked rather than truncating.
526+
const MAX_ENTRY_LEN: usize = u32::MAX as usize;
527+
528+
/// Narrows an encoded value's length to the 32 bits a [`SetEntry`] stores, erroring rather than
529+
/// truncating a length whose low bits would address a shorter, wrong slice.
530+
fn checked_entry_len(len: usize) -> DFResult<u32> {
531+
u32::try_from(len).map_err(|_| {
532+
DataFusionError::Execution(format!(
533+
"collect_set value of {len} encoded bytes exceeds the {MAX_ENTRY_LEN} byte limit"
534+
))
535+
})
536+
}
537+
538+
/// Byte range of `entry` within the arena, computed in 64-bit and widened once.
539+
///
540+
/// Split out from [`CollectSetGroupsAccumulator::entry_bytes`] so the arithmetic can be tested at
541+
/// the 4 GiB boundary without allocating an arena that large.
542+
#[inline]
543+
fn entry_range(start: u64, len: u32) -> Range<usize> {
544+
let start = usize::try_from(start).expect("arena offset exceeds the address space");
545+
let end = start
546+
.checked_add(len as usize)
547+
.expect("arena entry end exceeds the address space");
548+
start..end
512549
}
513550

514551
/// `GroupsAccumulator` for Spark's `collect_set`.
@@ -545,7 +582,8 @@ impl CollectSetGroupsAccumulator {
545582

546583
/// Records `(group, encoded)` unless the group already holds that value. `hash` is of
547584
/// `encoded` alone, so a caller that already has it (`compact`) need not recompute it.
548-
fn insert(&mut self, group: u32, hash: u64, encoded: &[u8]) {
585+
fn insert(&mut self, group: u32, hash: u64, encoded: &[u8]) -> DFResult<()> {
586+
let len = checked_entry_len(encoded.len())?;
549587
let Self {
550588
arena,
551589
entries,
@@ -557,30 +595,31 @@ impl CollectSetGroupsAccumulator {
557595
let entry = &entries[entry_idx as usize];
558596
entry.group == group
559597
&& entry.hash == hash
560-
&& &arena[entry.start as usize..(entry.start + entry.len) as usize] == encoded
598+
&& &arena[entry_range(entry.start, entry.len)] == encoded
561599
}) else {
562-
return;
600+
return Ok(());
563601
};
564602
let entry_idx = entries.len() as u32;
565603
entries.push(SetEntry {
566-
group,
567-
start: arena.len() as u32,
568-
len: encoded.len() as u32,
569604
hash,
605+
start: arena.len() as u64,
606+
group,
607+
len,
570608
});
571609
arena.extend_from_slice(encoded);
572610
index.fill(slot, entry_idx);
573611
if index.is_full(entries.len()) {
574612
index.grow(entries.iter().map(|e| key_hash(e.group, e.hash)));
575613
}
614+
Ok(())
576615
}
577616

578617
fn entry_bytes(&self, entry: &SetEntry) -> &[u8] {
579-
&self.arena[entry.start as usize..(entry.start + entry.len) as usize]
618+
&self.arena[entry_range(entry.start, entry.len)]
580619
}
581620

582621
/// Drops the entries of groups `0..emit_groups` and renumbers what is left to start at 0.
583-
fn compact(&mut self, emit_groups: u32) {
622+
fn compact(&mut self, emit_groups: u32) -> DFResult<()> {
584623
let old_entries = take_field(&mut self.entries);
585624
let old_arena = take_field(&mut self.arena);
586625
self.index = RowIndex::default();
@@ -589,9 +628,10 @@ impl CollectSetGroupsAccumulator {
589628
if entry.group < emit_groups {
590629
continue;
591630
}
592-
let bytes = &old_arena[entry.start as usize..(entry.start + entry.len) as usize];
593-
self.insert(entry.group - emit_groups, entry.hash, bytes);
631+
let bytes = &old_arena[entry_range(entry.start, entry.len)];
632+
self.insert(entry.group - emit_groups, entry.hash, bytes)?;
594633
}
634+
Ok(())
595635
}
596636

597637
fn clear(&mut self) {
@@ -626,7 +666,7 @@ impl GroupsAccumulator for CollectSetGroupsAccumulator {
626666
continue;
627667
}
628668
let row = rows.row(row_idx);
629-
self.insert(group_idx as u32, value_hash(row.as_ref()), row.as_ref());
669+
self.insert(group_idx as u32, value_hash(row.as_ref()), row.as_ref())?;
630670
}
631671
Ok(())
632672
}
@@ -653,7 +693,7 @@ impl GroupsAccumulator for CollectSetGroupsAccumulator {
653693
}
654694
for pos in offsets[row_idx] as usize..offsets[row_idx + 1] as usize {
655695
let row = rows.row(pos);
656-
self.insert(group_idx as u32, value_hash(row.as_ref()), row.as_ref());
696+
self.insert(group_idx as u32, value_hash(row.as_ref()), row.as_ref())?;
657697
}
658698
}
659699
Ok(())
@@ -705,7 +745,7 @@ impl GroupsAccumulator for CollectSetGroupsAccumulator {
705745

706746
match emit_to {
707747
EmitTo::All => self.clear(),
708-
EmitTo::First(n) => self.compact(n as u32),
748+
EmitTo::First(n) => self.compact(n as u32)?,
709749
}
710750

711751
Ok(Arc::new(ListArray::new(
@@ -1138,6 +1178,66 @@ mod tests {
11381178

11391179
/// The two UDFs forward the rest of `AggregateUDFImpl` to `datafusion_spark`, and the
11401180
/// planner and the `GroupsAccumulator` both depend on what those forwards report.
1181+
/// The arena addresses every group's bytes at once, so its offsets have to stay valid past
1182+
/// 4 GiB. The old 32-bit `start`/`len` pair wrapped there: `0xFFFF_FFFB + 8` came back as 3,
1183+
/// and the resulting slice either panicked or read another entry's bytes. Nothing about a
1184+
/// group's own result or the combined `List<i32>` element count bounds the arena, because that
1185+
/// limit counts elements rather than encoded bytes.
1186+
///
1187+
/// Checked here on the range arithmetic rather than through a real accumulator, so the
1188+
/// boundary is covered without allocating a 4 GiB arena.
1189+
#[test]
1190+
fn entry_range_stays_valid_past_four_gibibytes() {
1191+
const FOUR_GIB: u64 = u32::MAX as u64 + 1;
1192+
1193+
// Straddling the boundary: the wrapping version produced 3..3 for this pair.
1194+
assert_eq!(
1195+
entry_range(u32::MAX as u64 - 4, 8),
1196+
4_294_967_291..4_294_967_299
1197+
);
1198+
// Wholly above it.
1199+
assert_eq!(entry_range(FOUR_GIB, 8), 4_294_967_296..4_294_967_304);
1200+
// A later start is no longer truncated back into the first 4 GiB.
1201+
assert_eq!(entry_range(FOUR_GIB + 16, 0).start, 4_294_967_312);
1202+
// Ordinary offsets are unaffected.
1203+
assert_eq!(entry_range(0, 0), 0..0);
1204+
assert_eq!(entry_range(24, 8), 24..32);
1205+
}
1206+
1207+
/// Widening `start` to 64 bits is only free because of the field order. If someone reorders
1208+
/// `SetEntry`, padding appears and every distinct value in the aggregate pays 8 more bytes,
1209+
/// which `size()` reports to the memory pool.
1210+
#[test]
1211+
fn set_entry_stays_three_words() {
1212+
assert_eq!(size_of::<SetEntry>(), 3 * size_of::<u64>());
1213+
}
1214+
1215+
/// `len` stays 32-bit, so it is the one narrowing conversion left. Reaching it through the
1216+
/// accumulator would need a single row-encoded value over 4 GiB, so the conversion is checked
1217+
/// on its own: it must error rather than truncate a length into a shorter slice that would
1218+
/// silently return part of a value.
1219+
#[test]
1220+
fn oversized_entry_len_is_rejected_rather_than_truncated() {
1221+
assert_eq!(checked_entry_len(0).unwrap(), 0);
1222+
assert_eq!(checked_entry_len(24).unwrap(), 24);
1223+
assert_eq!(checked_entry_len(MAX_ENTRY_LEN).unwrap(), u32::MAX);
1224+
let err = checked_entry_len(MAX_ENTRY_LEN + 1).unwrap_err();
1225+
assert!(err.to_string().contains("exceeds"), "{err}");
1226+
}
1227+
1228+
/// The ordinary path still round-trips through the widened representation.
1229+
#[test]
1230+
fn entry_bytes_round_trip_through_the_arena() {
1231+
let mut acc = CollectSetGroupsAccumulator::try_new(DataType::Int32).unwrap();
1232+
acc.insert(0, 1, &[1, 2, 3]).unwrap();
1233+
acc.insert(1, 2, &[4, 5]).unwrap();
1234+
acc.insert(0, 1, &[1, 2, 3]).unwrap(); // duplicate, not stored again
1235+
assert_eq!(acc.entries.len(), 2);
1236+
assert_eq!(acc.entry_bytes(&acc.entries[0]), &[1, 2, 3]);
1237+
assert_eq!(acc.entry_bytes(&acc.entries[1]), &[4, 5]);
1238+
assert_eq!(acc.entries[1].start, 3);
1239+
}
1240+
11411241
#[test]
11421242
fn collect_functions_forward_their_shape_to_datafusion_spark() {
11431243
for udf in [

0 commit comments

Comments
 (0)