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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

/// Keeps track of mapped libraries in an address space. Stores a value
/// for each mapping, and allows efficient lookup of that value based on
/// an address.
#[derive(Debug, Clone)]
pub struct LibMappings<T> {
    sorted_mappings: Vec<Mapping<T>>,
}

impl<T> Default for LibMappings<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> LibMappings<T> {
    /// Creates a new empty instance.
    pub fn new() -> Self {
        Self {
            sorted_mappings: Vec::new(),
        }
    }

    /// Add a mapping to this address space. Any existing mappings which overlap with the
    /// new mapping are removed.
    ///
    /// `start_avma` and `end_avma` describe the address range that this mapping
    /// occupies.
    ///
    /// AVMA = "actual virtual memory address"
    ///
    /// `relative_address_at_start` is the "relative address" which corresponds
    /// to `start_avma`, in the library that is mapped in this mapping. This is zero if
    /// `start_avm` is the base address of the library.
    ///
    /// A relative address is a `u32` value which is relative to the library base address.
    /// So you will usually set `relative_address_at_start` to `start_avma - base_avma`.
    ///
    /// For ELF binaries, the base address is the AVMA of the first segment, i.e. the
    /// start_avma of the mapping created by the first ELF `LOAD` command.
    ///
    /// For mach-O binaries, the base address is the vmaddr of the `__TEXT` segment.
    ///
    /// For Windows binaries, the base address is the image load address.
    pub fn add_mapping(
        &mut self,
        start_avma: u64,
        end_avma: u64,
        relative_address_at_start: u32,
        value: T,
    ) {
        let remove_range_begin = match self
            .sorted_mappings
            .binary_search_by_key(&start_avma, |r| r.start_avma)
        {
            Ok(i) => i,
            Err(0) => 0,
            Err(i) => {
                // start_avma falls between the start_avmas of `i - 1` and `i`.
                if start_avma < self.sorted_mappings[i - 1].end_avma {
                    i - 1
                } else {
                    i
                }
            }
        };

        let mut remove_range_end = remove_range_begin;
        for mapping in &self.sorted_mappings[remove_range_begin..] {
            if mapping.start_avma < end_avma {
                remove_range_end += 1;
            } else {
                break;
            }
        }

        self.sorted_mappings.splice(
            remove_range_begin..remove_range_end,
            [Mapping {
                start_avma,
                end_avma,
                relative_address_at_start,
                value,
            }],
        );
    }

    /// Remove a mapping which starts at the given address. If found, this returns
    /// the `relative_address_at_start` and the associated value of the mapping.
    pub fn remove_mapping(&mut self, start_avma: u64) -> Option<(u32, T)> {
        self.sorted_mappings
            .binary_search_by_key(&start_avma, |m| m.start_avma)
            .ok()
            .map(|i| self.sorted_mappings.remove(i))
            .map(|m| (m.relative_address_at_start, m.value))
    }

    /// Clear all mappings.
    pub fn clear(&mut self) {
        self.sorted_mappings.clear();
        self.sorted_mappings.shrink_to_fit();
    }

    /// Look up the mapping which covers the given address.
    fn lookup(&self, avma: u64) -> Option<&Mapping<T>> {
        let mappings = &self.sorted_mappings[..];
        let index = match mappings.binary_search_by_key(&avma, |r| r.start_avma) {
            Err(0) => return None,
            Ok(exact_match) => exact_match,
            Err(insertion_index) => {
                let mapping_index = insertion_index - 1;
                if avma < mappings[mapping_index].end_avma {
                    mapping_index
                } else {
                    return None;
                }
            }
        };
        Some(&mappings[index])
    }

    /// Converts an absolute address (AVMA, actual virtual memory address) into
    /// a relative address and the mapping's associated value.
    pub fn convert_address(&self, avma: u64) -> Option<(u32, &T)> {
        let mapping = match self.lookup(avma) {
            Some(mapping) => mapping,
            None => return None,
        };
        let offset_from_mapping_start = (avma - mapping.start_avma) as u32;
        let relative_address = mapping.relative_address_at_start + offset_from_mapping_start;
        Some((relative_address, &mapping.value))
    }
}

#[derive(Debug, Clone, PartialEq, PartialOrd, Ord, Eq)]
struct Mapping<T> {
    start_avma: u64,
    end_avma: u64,
    relative_address_at_start: u32,
    value: T,
}