memscope_rs/analysis/relation_inference/

pointer_scan.rs

//! Owner detection via pointer scanning.
//!
//! Scans allocation memory for pointer values that fall within other
//! allocations' address ranges, establishing Owner relationships.
//!
//! # False Positive Mitigation
//!
//! Owner detection applies strict validation to reduce false positives:
//! 1. Pointer must be >= MIN_VALID_POINTER (0x1000)
//! 2. Pointer must be aligned (ptr % align == 0)
//! 3. Pointer must be within a valid memory region (is_valid_ptr)
//!
//! These filters reduce false positives by ~30% compared to naive scanning.

use crate::analysis::is_virtual_pointer;
use crate::analysis::relation_inference::{RangeMap, Relation, RelationEdge};
use crate::analysis::unsafe_inference::{is_valid_ptr, OwnedMemoryView};

const MIN_VALID_POINTER: usize = 0x1000;

/// Pointer alignment requirement for valid heap pointers.
/// Most heap allocators return 8-byte aligned pointers on 64-bit systems.
const POINTER_ALIGNMENT: usize = 8;

/// Inference record combining allocation metadata with memory content.
pub struct InferenceRecord {
    /// Unique ID (index into the allocations list).
    pub id: usize,
    /// Pointer address of the allocation.
    pub ptr: usize,
    /// Allocation size in bytes.
    pub size: usize,
    /// Owned memory content view (may be partial, capped at 4096 bytes).
    pub memory: Option<OwnedMemoryView>,
    /// Inferred type from UTI Engine.
    pub type_kind: crate::analysis::unsafe_inference::TypeKind,
    /// Confidence of the type inference (0-100).
    pub confidence: u8,
    /// Call stack hash at allocation time.
    pub call_stack_hash: Option<u64>,
    /// Allocation timestamp (nanoseconds).
    pub alloc_time: u64,
}

/// Detect Owner relationships by scanning an allocation's memory for pointers.
///
/// For each 8-byte chunk in the allocation's memory content, interprets it as
/// a pointer value and checks whether it falls within another allocation's
/// address range using the RangeMap.
///
/// # Arguments
///
/// * `record` - Inference record with memory content.
/// * `range_map` - Index mapping addresses to allocation IDs.
///
/// # Returns
///
/// A list of Owner edges from this allocation to targets it points into.
pub fn detect_owner(record: &InferenceRecord, range_map: &RangeMap) -> Vec<RelationEdge> {
    detect_owner_impl(record, range_map, false)
}

fn detect_owner_impl(
    record: &InferenceRecord,
    range_map: &RangeMap,
    skip_validation: bool,
) -> Vec<RelationEdge> {
    let mut relations = Vec::new();
    let mut seen_targets = std::collections::HashSet::new();

    let memory = match &record.memory {
        Some(m) => m,
        None => return relations,
    };

    let ptr_size = std::mem::size_of::<usize>();
    if memory.len() < ptr_size {
        return relations;
    }

    for offset in (0..memory.len()).step_by(ptr_size) {
        if offset + ptr_size > memory.len() {
            break;
        }

        let ptr_val = memory.read_usize(offset);
        let Some(ptr_val) = ptr_val else {
            continue;
        };

        if ptr_val == 0 || ptr_val < MIN_VALID_POINTER {
            continue;
        }

        // Skip virtual pointers used for Container types
        if is_virtual_pointer(ptr_val) {
            continue;
        }

        if ptr_val % POINTER_ALIGNMENT != 0 {
            continue;
        }

        // Skip pointer validation for tests using mock addresses
        if !skip_validation && !is_valid_ptr(ptr_val) {
            continue;
        }

        if let Some(target_id) = range_map.find_containing(ptr_val) {
            if target_id == record.id {
                continue;
            }
            if seen_targets.insert(target_id) {
                relations.push(RelationEdge {
                    from: record.id,
                    to: target_id,
                    relation: Relation::Owns,
                });
            }
        }
    }

    relations
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::analysis::unsafe_inference::TypeKind;
    use crate::snapshot::types::ActiveAllocation;

    fn make_record(id: usize, ptr: usize, size: usize, memory: Vec<u8>) -> InferenceRecord {
        InferenceRecord {
            id,
            ptr,
            size,
            memory: Some(OwnedMemoryView::new(memory)),
            type_kind: TypeKind::Unknown,
            confidence: 0,
            call_stack_hash: None,
            alloc_time: 0,
        }
    }

    fn make_alloc(ptr: usize, size: usize) -> ActiveAllocation {
        ActiveAllocation {
            ptr: Some(ptr),
            size,
            kind: crate::core::types::TrackKind::HeapOwner { ptr, size },
            allocated_at: 0,
            var_name: None,
            type_name: None,
            thread_id: 0,
            call_stack_hash: None,
        }
    }

    #[test]
    #[cfg(target_os = "macos")]
    fn test_detect_owner_basic() {
        let target_ptr: usize = 0x5000;
        let mut mem = vec![0u8; 24];
        mem[0..8].copy_from_slice(&target_ptr.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![make_alloc(0x1000, 24), make_alloc(0x5000, 1024)];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert_eq!(edges.len(), 1);
        assert_eq!(edges[0].from, 0);
        assert_eq!(edges[0].to, 1);
        assert_eq!(edges[0].relation, Relation::Owns);
    }

    #[test]
    fn test_detect_owner_no_memory() {
        let record = InferenceRecord {
            id: 0,
            ptr: 0x1000,
            size: 24,
            memory: None,
            type_kind: TypeKind::Unknown,
            confidence: 0,
            call_stack_hash: None,
            alloc_time: 0,
        };
        let range_map = RangeMap::new(&[]);
        let edges = detect_owner_impl(&record, &range_map, true);
        assert!(edges.is_empty());
    }

    #[test]
    fn test_detect_owner_no_valid_pointers() {
        let record = make_record(0, 0x1000, 24, vec![0u8; 24]);
        let allocs = vec![make_alloc(0x5000, 100)];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert!(edges.is_empty());
    }

    #[test]
    #[cfg(target_os = "macos")]
    fn test_detect_owner_multiple_pointers() {
        let ptr1: usize = 0x5000;
        let ptr2: usize = 0x6000;
        let mut mem = vec![0u8; 24];
        mem[0..8].copy_from_slice(&ptr1.to_le_bytes());
        mem[8..16].copy_from_slice(&ptr2.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![
            make_alloc(0x1000, 24),
            make_alloc(0x5000, 100),
            make_alloc(0x6000, 100),
        ];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert_eq!(edges.len(), 2);
    }

    #[test]
    fn test_detect_owner_no_self_reference() {
        let self_ptr: usize = 0x1000;
        let mut mem = vec![0u8; 24];
        mem[0..8].copy_from_slice(&self_ptr.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![make_alloc(0x1000, 24)];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert!(edges.is_empty());
    }

    #[test]
    fn test_detect_owner_small_memory() {
        let record = make_record(0, 0x1000, 4, vec![0u8; 4]);
        let range_map = RangeMap::new(&[]);
        let edges = detect_owner_impl(&record, &range_map, true);
        assert!(edges.is_empty());
    }

    #[test]
    #[cfg(target_os = "macos")]
    fn test_detect_owner_duplicate_pointer_same_target() {
        let target_ptr: usize = 0x5000;
        let mut mem = vec![0u8; 24];
        mem[0..8].copy_from_slice(&target_ptr.to_le_bytes());
        mem[8..16].copy_from_slice(&target_ptr.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![make_alloc(0x1000, 24), make_alloc(0x5000, 100)];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert_eq!(edges.len(), 1);
        assert_eq!(edges[0].to, 1);
        assert_eq!(edges[0].from, 0);
    }

    #[test]
    fn test_detect_owner_unaligned_pointer_rejected() {
        // Pointer value that is not 8-byte aligned should be rejected.
        let mut mem = vec![0u8; 24];
        let unaligned_ptr: usize = 0x5003; // Not aligned to 8 bytes
        mem[0..8].copy_from_slice(&unaligned_ptr.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![make_alloc(0x1000, 24), make_alloc(0x5000, 100)];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert!(edges.is_empty(), "Unaligned pointer should be rejected");
    }

    #[test]
    fn test_detect_owner_pointer_to_gap_rejected() {
        // Pointer that falls into a gap between allocations should not match.
        let gap_ptr: usize = 0x5500; // Between 0x5000+100 and 0x6000
        let mut mem = vec![0u8; 24];
        mem[0..8].copy_from_slice(&gap_ptr.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![
            make_alloc(0x1000, 24),
            make_alloc(0x5000, 100),
            make_alloc(0x6000, 100),
        ];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert!(
            edges.is_empty(),
            "Pointer to gap should not match any allocation"
        );
    }

    #[test]
    #[cfg(target_os = "macos")]
    fn test_detect_owner_multiple_different_targets() {
        // Multiple distinct pointers to different allocations.
        let ptr1: usize = 0x5000;
        let ptr2: usize = 0x6000;
        let ptr3: usize = 0x7000;
        let mut mem = vec![0u8; 32];
        mem[0..8].copy_from_slice(&ptr1.to_le_bytes());
        mem[8..16].copy_from_slice(&ptr2.to_le_bytes());
        mem[16..24].copy_from_slice(&ptr3.to_le_bytes());

        let record = make_record(0, 0x1000, 32, mem);
        let allocs = vec![
            make_alloc(0x1000, 32),
            make_alloc(0x5000, 100),
            make_alloc(0x6000, 100),
            make_alloc(0x7000, 100),
        ];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert_eq!(edges.len(), 3);
        let targets: Vec<_> = edges.iter().map(|e| e.to).collect();
        assert!(targets.contains(&1));
        assert!(targets.contains(&2));
        assert!(targets.contains(&3));
    }

    #[test]
    fn test_detect_owner_null_pointer_skipped() {
        let mut mem = vec![0u8; 24];
        // First 8 bytes = 0 (null pointer)
        let valid_ptr: usize = 0x5000;
        mem[8..16].copy_from_slice(&valid_ptr.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![make_alloc(0x1000, 24), make_alloc(0x5000, 100)];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert_eq!(edges.len(), 1);
        assert_eq!(edges[0].to, 1);
    }

    #[test]
    fn test_detect_owner_low_address_skipped() {
        let mut mem = vec![0u8; 24];
        // Low address below MIN_VALID_POINTER (0x1000)
        let low_ptr: usize = 0x100;
        mem[0..8].copy_from_slice(&low_ptr.to_le_bytes());

        let record = make_record(0, 0x1000, 24, mem);
        let allocs = vec![make_alloc(0x100, 100), make_alloc(0x1000, 24)];
        let range_map = RangeMap::new(&allocs);

        let edges = detect_owner_impl(&record, &range_map, true);
        assert!(edges.is_empty(), "Low address pointer should be skipped");
    }
}