Skip to content

Commit 7ff7278

Browse files
authored
fix: Reject out-of-range ArrayMap probe keys on 32-bit targets (#22911)
## Which issue does this PR close? - Closes #22910 ## Rationale for this change `ArrayMap` bucket lookups computed `key.wrapping_sub(offset) as usize`, and then bounds-checked the result after the cast. On 64-bit hosts, that is fine, but on 32-bit hosts, the cast will truncate the computed bucket offset to its low 32 bits. Given a large probe key whose low 32 bits are a valid bucket array index, this can produce incorrect results. ## What changes are included in this PR? * Introduce `key_to_index` and `get_value` helpers, to consolidate bucket lookup logic into one place * Fix bucket lookup logic for 32-bit hosts * Tweak null logic to optimize hot path slightly * Other minor refactorings / comment fixes * Add unit test ## Are these changes tested? Yes; new test added. ## Are there any user-facing changes? No.
1 parent 66fdcb0 commit 7ff7278

1 file changed

Lines changed: 78 additions & 24 deletions

File tree

‎datafusion/physical-plan/src/joins/array_map.rs‎

Lines changed: 78 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -89,7 +89,7 @@ macro_rules! downcast_supported_integer {
8989
/// ```
9090
/// The resulting `range` (10) correctly represents the size of the interval `[-5, 5]`.
9191
///
92-
/// **2. Index Lookup (in `get_matched_indices`)**
92+
/// **2. Index Lookup (in `get_matched_indices_with_limit_offset`)**
9393
///
9494
/// For a probe value of `0` (which is stored as `0u64`):
9595
/// ```text
@@ -157,13 +157,23 @@ impl ArrayMap {
157157
max_val.wrapping_sub(min_val)
158158
}
159159

160+
#[inline]
161+
fn key_to_index(key: u64, offset: u64, data_len: usize) -> Option<usize> {
162+
let idx = key.wrapping_sub(offset);
163+
if idx < data_len as u64 {
164+
Some(idx as usize)
165+
} else {
166+
None
167+
}
168+
}
169+
160170
/// Creates a new [`ArrayMap`] from the given array of join keys.
161171
///
162172
/// Note: This function processes only the non-null values in the input `array`,
163173
/// ignoring any rows where the key is `NULL`.
164174
///
165175
pub(crate) fn try_new(array: &ArrayRef, min_val: u64, max_val: u64) -> Result<Self> {
166-
let range = max_val.wrapping_sub(min_val);
176+
let range = Self::calculate_range(min_val, max_val);
167177
if range >= usize::MAX as u64 {
168178
return internal_err!("ArrayMap key range is too large to be allocated.");
169179
}
@@ -207,10 +217,9 @@ impl ArrayMap {
207217
for (i, val) in arr.iter().enumerate().rev() {
208218
if let Some(val) = val {
209219
let key: u64 = val.as_();
210-
let idx = key.wrapping_sub(offset_val) as usize;
211-
if idx >= data.len() {
220+
let Some(idx) = Self::key_to_index(key, offset_val, data.len()) else {
212221
return internal_err!("failed build Array idx >= data.len()");
213-
}
222+
};
214223

215224
if data[idx] != 0 {
216225
if next.is_empty() {
@@ -264,6 +273,16 @@ impl ArrayMap {
264273
)
265274
}
266275

276+
/// Looks up `key` (a raw probe value cast to `u64`) in the build side,
277+
/// returning the 1-based build-side slot if the key maps to a non-empty
278+
/// bucket, or `None` otherwise.
279+
#[inline]
280+
fn get_value(&self, key: u64) -> Option<u32> {
281+
let idx = Self::key_to_index(key, self.offset, self.data.len())?;
282+
let value = self.data[idx];
283+
(value != 0).then_some(value)
284+
}
285+
267286
fn lookup_and_get_indices<T: ArrowNumericType>(
268287
&self,
269288
array: &ArrayRef,
@@ -294,14 +313,10 @@ impl ArrayMap {
294313
}
295314
// SAFETY: prob_idx is guaranteed to be within bounds by the loop range.
296315
let prob_val: u64 = unsafe { arr.value_unchecked(prob_idx) }.as_();
297-
let idx_in_build_side = prob_val.wrapping_sub(self.offset) as usize;
298-
299-
if idx_in_build_side >= self.data.len()
300-
|| self.data[idx_in_build_side] == 0
301-
{
316+
let Some(build_value) = self.get_value(prob_val) else {
302317
continue;
303-
}
304-
build_indices.push((self.data[idx_in_build_side] - 1) as u64);
318+
};
319+
build_indices.push((build_value - 1) as u64);
305320
probe_indices.push(prob_idx as u32);
306321
}
307322
Ok(None)
@@ -337,22 +352,17 @@ impl ArrayMap {
337352
return Ok(Some((prob_side_idx, None)));
338353
}
339354

340-
if arr.is_null(prob_side_idx) {
355+
if have_null && arr.is_null(prob_side_idx) {
341356
continue;
342357
}
343358

344359
let is_last = prob_side_idx == arr.len() - 1;
345360

346361
// SAFETY: prob_idx is guaranteed to be within bounds by the loop range.
347362
let prob_val: u64 = unsafe { arr.value_unchecked(prob_side_idx) }.as_();
348-
let idx_in_build_side = prob_val.wrapping_sub(self.offset) as usize;
349-
if idx_in_build_side >= self.data.len()
350-
|| self.data[idx_in_build_side] == 0
351-
{
363+
let Some(build_idx) = self.get_value(prob_val) else {
352364
continue;
353-
}
354-
355-
let build_idx = self.data[idx_in_build_side];
365+
};
356366

357367
if let Some(offset) = traverse_chain(
358368
&self.next,
@@ -381,14 +391,14 @@ impl ArrayMap {
381391

382392
downcast_supported_integer!(
383393
array.data_type() => (
384-
contain_hashes_helper,
394+
contain_keys_helper,
385395
self,
386396
array
387397
)
388398
)
389399
}
390400

391-
fn contain_hashes_helper<T: ArrowNumericType>(
401+
fn contain_keys_helper<T: ArrowNumericType>(
392402
&self,
393403
array: &ArrayRef,
394404
) -> Result<BooleanArray>
@@ -402,8 +412,7 @@ impl ArrayMap {
402412
}
403413
// SAFETY: i is within bounds [0, arr.len())
404414
let key: u64 = unsafe { arr.value_unchecked(i) }.as_();
405-
let idx = key.wrapping_sub(self.offset) as usize;
406-
idx < self.data.len() && self.data[idx] != 0
415+
self.get_value(key).is_some()
407416
});
408417
Ok(BooleanArray::new(buffer, None))
409418
}
@@ -414,6 +423,7 @@ mod tests {
414423
use super::*;
415424
use arrow::array::Int32Array;
416425
use arrow::array::Int64Array;
426+
use arrow::array::UInt64Array;
417427
use std::sync::Arc;
418428

419429
#[test]
@@ -506,6 +516,50 @@ mod tests {
506516
Ok(())
507517
}
508518

519+
#[test]
520+
fn test_array_map_rejects_large_out_of_range_probe_key() -> Result<()> {
521+
let build: ArrayRef =
522+
Arc::new(UInt64Array::from(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]));
523+
let map = ArrayMap::try_new(&build, 0, 10)?;
524+
525+
assert_eq!(ArrayMap::key_to_index(3, 0, 11), Some(3));
526+
527+
// Pick a key for which the computed bucket offset is larger than
528+
// u32::MAX but has low 32 bits equal to 3. It must be bounds-checked
529+
// before casting to usize, otherwise 32-bit targets can truncate it
530+
// into range.
531+
let out_of_range_key = (1_u64 << 32) + 3;
532+
assert_eq!(ArrayMap::key_to_index(out_of_range_key, 0, 11), None);
533+
534+
let probe = [Arc::new(UInt64Array::from(vec![
535+
Some(3),
536+
Some(out_of_range_key),
537+
Some(11),
538+
None,
539+
])) as ArrayRef];
540+
541+
let mut matched_probe_indices = vec![];
542+
let mut matched_build_indices = vec![];
543+
let next = map.get_matched_indices_with_limit_offset(
544+
&probe,
545+
10,
546+
(0, None),
547+
&mut matched_probe_indices,
548+
&mut matched_build_indices,
549+
)?;
550+
assert_eq!(matched_probe_indices, vec![0]);
551+
assert_eq!(matched_build_indices, vec![3]);
552+
assert!(next.is_none());
553+
554+
let contains = map.contain_keys(&probe)?;
555+
assert!(contains.value(0));
556+
assert!(!contains.value(1));
557+
assert!(!contains.value(2));
558+
assert!(!contains.value(3));
559+
560+
Ok(())
561+
}
562+
509563
#[test]
510564
fn test_array_map_i64_with_negative_and_positive_numbers() -> Result<()> {
511565
// Build array with a mix of negative and positive i64 values, no duplicates

0 commit comments

Comments
 (0)