Chapter 5.5. Owned Heap Analysis

The purpose of owned heap analysis is to determine whether a type holds a piece of memory on the heap.

OwnedHeapAnalysis Trait

#![allow(unused)]
fn main() {
pub trait OwnedHeapAnalysis: Analysis {
    fn get_all_items(&mut self) -> OHAResult;
    fn is_heapowner<'tcx>(hares: OHAResult, ty: Ty<'tcx>) -> Result<bool, &'static str>;
    fn maybe_heapowner<'tcx>(hares: OHAResult, ty: Ty<'tcx>) -> Result<bool, &'static str>;
}
}

We represent the result as a hashmap named OHAResult, where the key is DefId and the value contains the information of whether the type owns data on heap. Since a type could be a enumerate type, the value is represented as a Vec, indicating the heap information of each variant. Also, because it may contain type parameters or generic types, the heap information is a tuple containing the information of each type parameter.

#![allow(unused)]
fn main() {
pub type OHAResult = HashMap<DefId, Vec<(OwnedHeap, Vec<bool>)>>;
pub enum OwnedHeap {
    False = 0,
    True = 1,
    Unknown = 2,
}
}

Default Implementation

There are two general methods: either by examining the implementation of the Drop trait for the type, for the type or by checking the presence of a PhantomData marker. The analysis approach implemented in RAPx is based on [PhantomData].

We define a data structure as a heap unit if it contains a raw pointer to T and a PhantomData<T> field. It is the most fundamental unit that owns a piece of memory on the heap. Other data structures may internally contain heap units, referred to as heap owners or heap items.

For example, the following code employs the String data structure, which is based on Vec.

#![allow(unused)]
fn main() {
let _buf = String::from("hello, heap item");
}

When running RAPx with the -heap option, you will see the following result. The main result for String is (1, []), where 1 indicates that it is a heap item, and [] represents attributes for type parameters. Since the String data structure has no type parameters, [] is empty. The output also includes information about other types that String depends on.

Usage Guide

When running rapx with the -ownedheap option, you will see the following result. The main result for String is (1, []), where 1 indicates that it is a heap item, and [] represents the ownership of type parameters. Since the data structure has no type parameters, [] is empty. The output also includes information about other types that String depends on.

cargo rapx -ownedheap
    Checking heap_string...
21:20:05|RAP|INFO|: Start analysis with RAP.
21:20:05|RAP|INFO|: std::string::String (1, [])
21:20:05|RAP|INFO|: alloc::raw_vec::Cap (0, [])
21:20:05|RAP|INFO|: alloc::raw_vec::RawVec<T/#0, A/#1> (1, [0,1])
21:20:05|RAP|INFO|: std::ptr::Unique<T/#0> (1, [0])
21:20:05|RAP|INFO|: alloc::raw_vec::RawVecInner<A/#0> (1, [1])
21:20:05|RAP|INFO|: std::alloc::Global (0, [])
21:20:05|RAP|INFO|: std::ptr::NonNull<T/#0> (0, [0])
21:20:05|RAP|INFO|: std::vec::Vec<T/#0, A/#1> (1, [0,1])
21:20:05|RAP|INFO|: std::marker::PhantomData<T/#0> (0, [0])

RAPx provides a default implementation via the DefaultOwnedHeapAnalysis struct, developers can use the feature in their own analysis code as follows.

#![allow(unused)]
fn main() {
let mut analysis = DefaultOwnedHeapAnalysis::new(tcx);
analysis.run();
analysis.output();
let result = heap.get_all_items();
}

Analysis Method

There are two steps:

Type Parameter Analysis: If a data structure contains type parameters, the type parameter can be monomorphized into either a heap owner or a non-owner. If there are heap owners, whether the data structure ultimately owns heap memory depends on how the type parameter is used, i.e., as an owned value, a reference, or a raw pointer. Only ownership leads to an owned object. Therefore, we perform type parameter analysis to determine whether the data structure owns the type. This result is then used to assess whether a monomorphic type is a heap owner, significantly reducing the overhead of handling generic types.
Ownership Analysis: If a data structure contains a heap unit, it owns heap memory. Otherwise, if the data structure is not a direct heap owner, and it contains type parameters, we use the results from type parameter analysis and type assignment to determine whether its monomorphic version is a heap owner.

Next, we empoy the follow example to demonstrate the mechanism.

#![allow(unused)]
fn main() {
struct Proxy1<T> {
    _p: *mut T,
}
struct Proxy2<T> {
    _p: *mut T,
    _marker: PhantomData<T>,
}
struct Proxy3<'a, T> {
    _p: *mut T,
    _marker: PhantomData<&'a T>,
}
struct Proxy4<T> {
    _x: T,
}
struct Proxy5<T> {
    _x: Proxy2<T>,
}
}

This example contains five data structures:

Proxy1 is not a heap unit because it does not contain PhantomData<T>.
Proxy2 is a heap unit.
Proxy3 is not a heap unit because its PhantomData marker holds a reference rather than an owned value.
Proxy4 is not a direct heap owner, but it contains type parameters. Since it ownes T, we have to emply [1] to indicate the possibility of it being a heap owner, i.e., when T itself is a heap owner.
Proxy5 is a heap owner because Proxy2<T> is a heap unit. This type also contains the type parameter T, which is used in Proxy2<T>. However, it does not own T because Proxy2<T> does not own T.

The analysis result is displayed as follows.

cargo rapx -heap
    Checking heap_proxy ...
11:42:05|RAP|INFO|: Proxy5<T/#0> (1, [0])
11:42:05|RAP|INFO|: Proxy4<T/#0> (0, [1])
11:42:05|RAP|INFO|: Proxy3<'a/#0, T/#1> (0, [0,0])
11:42:05|RAP|INFO|: Proxy2<T/#0> (1, [0])
11:42:05|RAP|INFO|: Proxy1<T/#0> (0, [0])
...

Rust Analysis Platform

Chapter 5.5. Owned Heap Analysis

OwnedHeapAnalysis Trait

Default Implementation

Usage Guide

Analysis Method