！！！注意，这篇文章中提到的性能优化方式基本仅适用于指针链扫描，不适用其它业务。
！！！这篇文章并不是接着上一篇文章写的，但有很多关联，不过很多代码，逻辑，已经发生变化。
反转数据储存方式
上一篇文章中，我们使用如下结构储存所有指针
其中 key=地址，value=地址所储存的引用地址
这导致了一些问题，首先整个 Map 会变得非常大，性能也会受到影响，并且由于其底层储存方式，占用的内存非常多。
但很容易解决这个问题，只需要 反转 它，使用如下方式储存
1
|
BTreeMap<usize, Vec<usize>>
|
key=地址所储存的引用地址，value=对应地址列表
我们从一对一的关系变成了一对多，这极大缩小了整个 Map
Rust 有一个非常方便的API可以帮我们处理这个
1
|
{BTreeMap<usize, Vec<usize>>}.entry(value).or_default().push(key)
|
做完这些，现实用例中，大多数情况，整体性能会提升高达 1000% 以上。
之所以会有如此大的提升是因为我们扫描的是指针链，必然会有多个地址储存了同一个引用。这为后续的扫描减少了无数次遍历 Map 的开销。
查找基址模块
计算出指针链的初始地址后，我们需要确定它位于哪个模块上，一般这被称为基址。
从前，我们遍历所有内存范围来确定基址，这很缓慢。
实际上我们可以使用 区间树/线段树 一类的数据结构来快速找到它。
不过多数现有的这类实现并不是很适合我们的需求，它会合并相关范围，例如储存 3..5 和 1..10，它会合并为单个 1..10
我们并不需要这种行为，这种多余的操作会影响一些性能，因为我们知道，内存区域中永远不会存在两个相交的范围。
我们可以自己实现一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#[derive(Default)]
struct RangeMap<K, V>(BTreeMap<RangeWrapper<K>, V>);
impl<K, V> RangeMap<K, V> {
fn iter(&self) -> impl Iterator<Item = (&Range<K>, &V)> {
self.0.iter().map(|(k, v)| (&k.0, v))
}
fn clear(&mut self) {
self.0.clear()
}
}
impl<K, V> RangeMap<K, V>
where
K: Ord + Copy,
{
fn get_key_value(&self, point: K) -> Option<(&Range<K>, &V)> {
let start = RangeWrapper(point..point);
self.0
.range((Bound::Unbounded, Bound::Included(start)))
.next_back()
.filter(|(range, _)| range.0.contains(&point))
.map(|(range, value)| (&range.0, value))
}
fn insert(&mut self, key: Range<K>, value: V) -> Option<V> {
assert!(key.start <= key.end);
self.0.insert(RangeWrapper(key), value)
}
}
|
其中 key=模块地址范围，value=模块信息
做完这些，现实用例中，大多数情况，整体性能会提升 10% （提升并不多，因为计算基址的时候才会执行这个，并不频繁）
缓慢的二分查找
从前我们使用二分查找来确定它是否已经接近基址模块，然后决定跳过一些扫描。
但是通常由于计算机cpu缓存以及分支预测的存在，对于少量数据，它可能不如线性搜索快速，我保守预计现代计算机中通常阀值在 64 左右，在实际 bench 中，它可能更高，不过对我们来说64已经足够。
分支预测器负责根据历史数据预测结果。分支被错误预测时CPU需要完成其所有工作并重组，这个过程很耗时。
我们实际需要查找的只是 BTreeMap<usize, Vec<usize>> 中 Vec<usize>> 的数据
由于整个Map是由 BTreeMap<usize, usize> 转换而来，可以保证 Vec<usize>> 是有序的
从前的实现
1
|
let idx = points.binary_search(&min).unwrap_or_else(|x| x);
|
添加线性搜索
1
|
let idx = points.iter().position(|x| min.le(x)).unwrap_or(points.len());
|
现在可以简单检测数据的密集程度，如果其中绝大部分value的长度小于64，则假设它是稀疏的，使用线性查找，否则假设它是密集的，使用二分查找。
1
2
3
4
5
|
let count = reverse.values().filter(|v| v.len() < 64).count();
let mode = match (reverse.len() - count).checked_mul(64) {
Some(n) if n < count => ScanMode::Sparse,
_ => ScanMode::Dense,
};
|
现实用例中，大部分时候它都应该是稀疏的，应该不会有什么程序中非常很多地址储存了同一个地址。
做完这些，现实用例中，大多数情况，相比纯粹使用二分查找，整体性能会提升 50% 左右。
巨大的偏移
影响指针扫描性能的最主要原因还是 深度/偏移 设定的过高，导致结果过多。
在一些特殊程序中，例如 IOS版植物大战僵尸的阳光指针链，它很短，大概只需要3级深度就够，但是，它的最后一级有一个高达接近三万的偏移。
事实上这类特殊例子并不多，目前只发现 战神 和 IOS版植物大战僵尸 会这样，（战神有一个最后一级高达十万的偏移）。
而除了最后一级，其它偏移都只有几百。
如果使用 深度3，偏移0-30000，这会导致输出非常多指针链，同时速度可能会很慢，因为它为每个深度都执行了大范围扫描。
实际上可以单独为最后一级偏移设定大范围扫描 （PS: 对于中间大的情况根本无需在意，可以当做不存在，只需要单独设定最后一级就够了）
1
2
3
4
5
|
let (min, max) = if curr != CURR {
(addr.saturating_sub(srange.1), addr.saturating_add(srange.0))
} else {
(addr.saturating_sub(lrange.1), addr.saturating_add(lrange.0))
};
|
这样可以使用参数 深度3，偏移0:2000, 尾部偏移 0:30000 执行扫描。这大大减少了指针链计算的次数，几乎一瞬间就可以扫描完成。这类特殊用例的性能会提升一个数量级。
垃圾区域
通常情况下，我们将全部区域都允许作为基址，然而实际上我们根本不需要关心这么多。
系统库，加载的媒体资源（视频，字体）等等，即便是模糊扫描也几乎根本不可能把它们作为基址。
我们可以在dump阶段就排除它
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#[inline]
fn check_region<Q: VirtualQuery + vmmap::macos::VirtualQueryExt>(page: &Q) -> bool {
use std::fs::File;
if !page.is_read() || page.is_reserve() {
return false;
}
let Some(name) = page.name() else {
return matches!(page.tag(), |1..=9| 11 | 30 | 33 | 60 | 61);
};
let path = Path::new(name);
if path.starts_with("/usr") {
return false;
}
let mut buf = [0; 8];
File::open(path)
.and_then(|mut f| f.read_exact(&mut buf))
.is_ok_and(|_| match buf[0..4] {
[width, 0xfa, 0xed, 0xfe] if width == 0xcf || width == 0xce => true,
[0xfe, 0xed, 0xfa, width] if width == 0xcf || width == 0xce => true,
[0xca, 0xfe, 0xba, 0xbe] => u32::from_be_bytes([buf[4], buf[5], buf[6], buf[7]]) < 45,
_ => false,
})
}
|
在扫描时，我们也几乎不可能把区域名字为空的模块作为地址，我们只需要有名字的。
使用 BTreeSet<usize> 储存所有相关地址。
然后扫描的时候我们可以通过指定一个模块来决定排除哪些垃圾。
1
2
3
4
5
6
|
let points = &self
.index
.iter()
.flat_map(|(Range { start, end }, _)| forward.range((Bound::Included(start), Bound::Included(end))))
.copied()
.collect::<Vec<_>>();
|
这部分的性能提升无法估计，取决于实际排除了多少垃圾区域，如果一个都没有，它会拖慢速度，但微乎其微。而一旦正确排除了垃圾区域，速度会得到非常大大提升。
指针链过滤
我们扫描到的指针链并不总是有效的，它可能只是一个 碰巧存在的幽灵指针链，进程重启后它可能就失效了，所以我们需要过滤出真正的指针链。
从前，对于例如长度为 7 的每一条指针链，它需要执行7个系统调用才能获取它的数据，以验证是否有效。
然而系统调用非常昂贵，对于大量数据它可能耗时非常久。
如果数量超过某个阀值，我们可以创建一个内存快照，以加速它的访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
pub struct Snap {
pub map: RangeMap<usize, Range<usize>>,
pub mmap: MmapMut,
}
impl Snap {
pub fn create_snapshot<'a, P, I, V>(proc: &P, iter: I) -> Result<Self>
where
P: VirtualMemoryRead,
V: VirtualQuery + 'a,
I: Iterator<Item = &'a V>,
{
let file = tempfile::Builder::new().append(true).tempfile_in(".")?.into_file();
let mut bufwriter = BufWriter::with_capacity(0x200000, &file);
let mut buf = vec![0; BUF_SIZE];
let mut map = RangeMap::new();
let mut e_seek = 0;
for vq in iter {
let mut i_seek = 0;
let (start, size) = (vq.start(), vq.size());
for off in (0..size).step_by(BUF_SIZE) {
let size = proc.read_at(&mut buf, start + off)?;
bufwriter.write_all(&buf[..size])?;
i_seek += size;
}
let (real_start, real_end) = (vq.start(), vq.end());
let (virt_start, virt_end) = (e_seek, e_seek + i_seek);
map.insert(real_start..real_end, virt_start..virt_end);
e_seek += i_seek;
}
let mmap = unsafe { MmapMut::map_mut(&file)? };
Ok(Self { map, mmap })
}
#[inline]
pub fn read_exact_at(&self, buf: &mut [u8], offset: usize) -> Option<()> {
let (k, v) = self.map.get_key_value(offset)?;
let offset = v.start + (offset - k.start);
let last = offset + buf.len();
if last > v.end {
None
} else {
let data = self.mmap.get(offset..last)?;
buf.copy_from_slice(data);
Some(())
}
}
}
|
我们基于 mmap 来实现这个，它可以极大减少内存占用。
在 Snap.map 中 key=真实地址范围, value=虚拟地址范围（相对于文件中的地址）
使用 read_exact_at 方法将真实地址转换为虚拟地址并读取它的内容。
然后我们可以并发调用它，这对于需要验证大量指针链，性能又提升了非常多，不过这并不是最好的实现方式，极小概率可能负提升（当地址转换的开销大于系统调用时）
总结
整个指针扫描流程有点类似于病毒溯源，我们先找到感染人群，然后将人群归类，找到他们分别去了哪里，最后确定病毒源头。
综合来说，相比以前的暴力扫描，我们在优化数据结构并改变扫描逻辑后，在不影响结果准确度的情况下，将整体性能提升了至少二十倍以上。
更改的扫描逻辑不在本文描述，放在这里: https://github.com/kekeimiku/PointerSearcher-X/blob/main/ptrsx/src/lib.rs