rapx/analysis/safedrop/
alias.rs

1use rustc_middle::{
2    mir::{Operand, Place, ProjectionElem, TerminatorKind},
3    ty::{self},
4};
5
6use super::{drop::*, graph::*};
7use crate::analysis::core::alias_analysis::default::{
8    MopAliasPair, MopFnAliasMap, alias::is_no_alias_intrinsic, block::Term, types::*, value::*
9};
10use rustc_data_structures::fx::FxHashSet;
11
12impl<'tcx> SafeDropGraph<'tcx> {
13    /* alias analysis for a single block */
14    pub fn alias_bb(&mut self, bb_index: usize) {
15        for constant in self.mop_graph.blocks[bb_index].const_value.clone() {
16            self.mop_graph
17                .constants
18                .insert(constant.local, constant.value);
19        }
20        let cur_block = self.mop_graph.blocks[bb_index].clone();
21        for assign in cur_block.assignments {
22            let lv_idx = self.projection(assign.lv);
23            let rv_idx = self.projection(assign.rv);
24            // We should perform uaf check before alias analysis.
25            // Example: *1 = 4; when *1 is dangling.
26            // Perfoming alias analysis first would introduce false positives.
27            self.uaf_check(rv_idx, bb_index, assign.span, false);
28            self.assign_alias(lv_idx, rv_idx);
29            self.clear_drop_info(lv_idx);
30
31            rap_debug!("Alias sets: {:?}", self.mop_graph.alias_sets.clone());
32        }
33    }
34
35    /* Check the aliases introduced by the terminators (function call) of a scc block */
36    pub fn alias_bbcall(&mut self, bb_index: usize, fn_map: &MopFnAliasMap) {
37        let cur_block = self.mop_graph.blocks[bb_index].clone();
38        if let Term::Call(call) | Term::Drop(call) = cur_block.terminator {
39            if let TerminatorKind::Call {
40                func: Operand::Constant(ref constant),
41                ref args,
42                ref destination,
43                target: _,
44                unwind: _,
45                call_source: _,
46                fn_span: _,
47            } = call.kind
48            {
49                rap_debug!("alias_bbcall in {:?}: {:?}", bb_index, call);
50                let lv = self.projection(destination.clone());
51                let mut merge_vec = Vec::new();
52                merge_vec.push(lv);
53                let mut may_drop_flag = 0;
54                if self.mop_graph.values[lv].may_drop {
55                    may_drop_flag += 1;
56                }
57                for arg in args {
58                    match arg.node {
59                        Operand::Copy(ref p) | Operand::Move(ref p) => {
60                            let rv = self.projection(p.clone());
61                            self.uaf_check(rv, bb_index, call.source_info.span, true);
62                            merge_vec.push(rv);
63                            if self.mop_graph.values[rv].may_drop {
64                                may_drop_flag += 1;
65                            }
66                        }
67                        Operand::Constant(_) => {
68                            merge_vec.push(0);
69                        }
70                    }
71                }
72                if let ty::FnDef(target_id, _) = constant.const_.ty().kind() {
73                    if may_drop_flag > 1 {
74                        // This function does not introduce new aliases.
75                        if is_no_alias_intrinsic(*target_id) {
76                            return;
77                        }
78                        if self.mop_graph.tcx.is_mir_available(*target_id) {
79                            rap_debug!("fn_map: {:?}", fn_map);
80                            if fn_map.contains_key(&target_id) {
81                                let fn_aliases = fn_map.get(&target_id).unwrap();
82                                rap_debug!("aliases of the fn: {:?}", fn_aliases);
83                                if fn_aliases.aliases().is_empty() {
84                                    if let Some(l_set_idx) = self.mop_graph.find_alias_set(lv) {
85                                        self.mop_graph.alias_sets[l_set_idx].remove(&lv);
86                                    }
87                                }
88                                for alias in fn_aliases.aliases().iter() {
89                                    if !alias.valuable() {
90                                        continue;
91                                    }
92                                    self.handle_fn_alias(alias, &merge_vec);
93                                }
94                            }
95                        } else {
96                            if self.mop_graph.values[lv].may_drop {
97                                for rv in &merge_vec {
98                                    if self.mop_graph.values[*rv].may_drop
99                                        && lv != *rv
100                                        && self.mop_graph.values[lv].is_ptr()
101                                    {
102                                        self.mop_graph.merge_alias(lv, *rv);
103                                        self.clear_drop_info(lv);
104                                    }
105                                }
106                            }
107                        }
108                    }
109                }
110            }
111        }
112    }
113
114    pub fn assign_alias(&mut self, lv_idx: usize, rv_idx: usize) {
115        rap_debug!("assign_alias: lv = {:?}. rv = {:?}", lv_idx, rv_idx);
116        let r_set_idx = if let Some(idx) = self.mop_graph.find_alias_set(rv_idx) {
117            idx
118        } else {
119            self.mop_graph
120                .alias_sets
121                .push([rv_idx].into_iter().collect::<FxHashSet<usize>>());
122            self.mop_graph.alias_sets.len() - 1
123        };
124
125        if let Some(l_set_idx) = self.mop_graph.find_alias_set(lv_idx) {
126            if l_set_idx == r_set_idx {
127                return;
128            }
129            self.mop_graph.alias_sets[l_set_idx].remove(&lv_idx);
130        }
131        self.mop_graph.alias_sets[r_set_idx].insert(lv_idx);
132
133        if self.mop_graph.values[lv_idx].fields.len() > 0
134            || self.mop_graph.values[rv_idx].fields.len() > 0
135        {
136            self.sync_field_alias(lv_idx, rv_idx, 0, true);
137        }
138        if self.mop_graph.values[rv_idx].father != None {
139            self.sync_father_alias(lv_idx, rv_idx, r_set_idx);
140        }
141    }
142
143    // Update the aliases of fields.
144    // Case 1, lv = 1; rv = 2; field of rv: 1;
145    // Expected result: [1,2] [1.1,2.1];
146    // Case 2, lv = 0.0, rv = 7, field of rv: 0;
147    // Expected result: [0.0,7] [0.0.0,7.0]
148    pub fn sync_field_alias(&mut self, lv: usize, rv: usize, depth: usize, clear_left: bool) {
149        rap_debug!("sync field aliases for lv:{} rv:{}", lv, rv);
150
151        let max_field_depth = match std::env::var_os("MOP") {
152            Some(val) if val == "0" => 10,
153            Some(val) if val == "1" => 20,
154            Some(val) if val == "2" => 30,
155            Some(val) if val == "3" => 50,
156            _ => 15,
157        };
158
159        if depth > max_field_depth {
160            return;
161        }
162
163        // For the fields of lv; we should remove them from the alias sets;
164        if clear_left {
165            for lv_field in self.mop_graph.values[lv].fields.clone().into_iter() {
166                if let Some(alias_set_idx) = self.mop_graph.find_alias_set(lv_field.1) {
167                    self.mop_graph.alias_sets[alias_set_idx].remove(&lv_field.1);
168                }
169            }
170        }
171        for rv_field in self.mop_graph.values[rv].fields.clone().into_iter() {
172            rap_debug!("rv_field: {:?}", rv_field);
173            if !self.mop_graph.values[lv].fields.contains_key(&rv_field.0) {
174                let new_index = self.mop_graph.values.len();
175                let mut node = Value::new(
176                    new_index,
177                    self.mop_graph.values[lv].local,
178                    self.mop_graph.values[rv_field.1].need_drop,
179                    self.mop_graph.values[rv_field.1].may_drop,
180                );
181                node.kind = self.mop_graph.values[rv_field.1].kind;
182                node.father = Some(FatherInfo::new(lv, rv_field.0));
183                self.mop_graph.values[lv]
184                    .fields
185                    .insert(rv_field.0, node.index);
186                self.mop_graph.values.push(node);
187                self.drop_record
188                    .push(DropRecord::from(new_index, &self.drop_record[lv]));
189            }
190            let lv_field_value_idx = *(self.mop_graph.values[lv].fields.get(&rv_field.0).unwrap());
191
192            rap_debug!(
193                "alias_set_id of rv_field {:?}",
194                self.mop_graph.find_alias_set(rv_field.1)
195            );
196            if let Some(alias_set_idx) = self.mop_graph.find_alias_set(rv_field.1) {
197                self.mop_graph.alias_sets[alias_set_idx].insert(lv_field_value_idx);
198            }
199            rap_debug!("alias sets: {:?}", self.mop_graph.alias_sets);
200            self.sync_field_alias(lv_field_value_idx, rv_field.1, depth + 1, true);
201        }
202    }
203
204    // For example,
205    // Case 1: lv = 1; rv = 2.0; alias set [2, 3]
206    // Expected result: [1, 2.0, 3.0], [2, 3];
207    // Case 2: lv = 1.0; rv = 2; alias set [1, 3]
208    // Expected result: [1.0, 2], [1, 3]
209    pub fn sync_father_alias(&mut self, lv: usize, rv: usize, lv_alias_set_idx: usize) {
210        rap_debug!("sync father aliases for lv:{} rv:{}", lv, rv);
211        let mut father_id = rv;
212        let mut father = self.mop_graph.values[father_id].father.clone();
213        while let Some(father_info) = father {
214            father_id = father_info.father_value_id;
215            let field_id = father_info.field_id;
216            let father_value = self.mop_graph.values[father_id].clone();
217            if let Some(alias_set_idx) = self.mop_graph.find_alias_set(father_id) {
218                for value_idx in self.mop_graph.alias_sets[alias_set_idx].clone() {
219                    // create a new node if the node does not exist;
220                    let field_value_idx = if self.mop_graph.values[value_idx]
221                        .fields
222                        .contains_key(&field_id)
223                    {
224                        *self.mop_graph.values[value_idx]
225                            .fields
226                            .get(&field_id)
227                            .unwrap()
228                    } else {
229                        let new_index = self.mop_graph.values.len();
230                        let mut node = Value::new(
231                            new_index,
232                            self.mop_graph.values[value_idx].local,
233                            self.mop_graph.values[value_idx].need_drop,
234                            self.mop_graph.values[value_idx].may_drop,
235                        );
236                        node.kind = self.mop_graph.values[value_idx].kind;
237                        node.father = Some(FatherInfo::new(value_idx, field_id));
238                        self.mop_graph.values.push(node.clone());
239                        self.mop_graph.values[value_idx]
240                            .fields
241                            .insert(field_id, node.index);
242                        self.drop_record
243                            .push(DropRecord::from(new_index, &self.drop_record[lv]));
244                        node.index
245                    };
246                    // add the node to the alias_set of lv;
247                    self.mop_graph.alias_sets[lv_alias_set_idx].insert(field_value_idx);
248                }
249            }
250            father = father_value.father;
251        }
252    }
253
254    /*
255     * This is the function for field sensitivity.
256     * If the projection is a deref, we directly return its local;
257     * If the id is not a ref (e.g., 1.0), we project it to the value index.
258     *
259     */
260    pub fn projection(&mut self, place: Place<'tcx>) -> usize {
261        let local = place.local.as_usize();
262        let mut value_idx = local;
263        // Projections are leveled
264        // Case 1: (*6).1 involves two projections: a Deref and a Field.
265        // Case 2: (6.0).1 involves two field projections.
266        // We should recursively parse the projection.
267        for proj in place.projection {
268            let new_value_idx = self.mop_graph.values.len();
269            match proj {
270                ProjectionElem::Deref => {}
271                ProjectionElem::Field(field, ty) => {
272                    let field_idx = field.as_usize();
273                    if !self.mop_graph.values[value_idx]
274                        .fields
275                        .contains_key(&field_idx)
276                    {
277                        let ty_env =
278                            ty::TypingEnv::post_analysis(self.mop_graph.tcx, self.mop_graph.def_id);
279                        let need_drop = ty.needs_drop(self.mop_graph.tcx, ty_env);
280                        let may_drop = !is_not_drop(self.mop_graph.tcx, ty);
281                        let mut node =
282                            Value::new(new_value_idx, local, need_drop, need_drop || may_drop);
283                        node.kind = kind(ty);
284                        node.father = Some(FatherInfo::new(value_idx, field_idx));
285                        self.mop_graph.values[value_idx]
286                            .fields
287                            .insert(field_idx, node.index);
288                        self.mop_graph.values.push(node);
289                        // The drop status is the same as its father.
290                        self.drop_record.push(DropRecord::from(
291                            new_value_idx,
292                            &self.drop_record[value_idx],
293                        ));
294                    }
295                    value_idx = *self.mop_graph.values[value_idx]
296                        .fields
297                        .get(&field_idx)
298                        .unwrap();
299                }
300                _ => {}
301            }
302        }
303        value_idx
304    }
305
306    //inter-procedure instruction to merge alias.
307    pub fn handle_fn_alias(&mut self, fn_alias: &MopAliasPair, arg_vec: &Vec<usize>) {
308        rap_debug!("ret_alias: {:?}", fn_alias);
309        if fn_alias.left_local() >= arg_vec.len() || fn_alias.right_local() >= arg_vec.len() {
310            return;
311        }
312
313        let mut lv = arg_vec[fn_alias.left_local()];
314        self.clear_drop_info(lv);
315        let mut rv = arg_vec[fn_alias.right_local()];
316        let left_local = self.mop_graph.values[lv].local;
317        let right_local = self.mop_graph.values[rv].local;
318
319        for index in fn_alias.lhs_fields().iter() {
320            if !self.mop_graph.values[lv].fields.contains_key(&index) {
321                let new_index = self.mop_graph.values.len();
322                let need_drop = fn_alias.lhs_need_drop;
323                let may_drop = fn_alias.lhs_may_drop;
324                let mut node = Value::new(new_index, left_local, need_drop, may_drop);
325                node.kind = ValueKind::RawPtr;
326                node.father = Some(FatherInfo::new(lv, *index));
327                self.mop_graph.values[lv].fields.insert(*index, node.index);
328                self.drop_record
329                    .push(DropRecord::from(new_index, &self.drop_record[lv]));
330                self.mop_graph.values.push(node);
331            }
332            lv = *self.mop_graph.values[lv].fields.get(&index).unwrap();
333        }
334        for index in fn_alias.rhs_fields().iter() {
335            if !self.mop_graph.values[rv].fields.contains_key(&index) {
336                let new_index = self.mop_graph.values.len();
337                let need_drop = fn_alias.rhs_need_drop;
338                let may_drop = fn_alias.rhs_may_drop;
339                let mut node = Value::new(new_index, right_local, need_drop, may_drop);
340                node.kind = ValueKind::RawPtr;
341                node.father = Some(FatherInfo::new(rv, *index));
342                self.mop_graph.values[rv].fields.insert(*index, node.index);
343                self.drop_record
344                    .push(DropRecord::from(new_index, &self.drop_record[rv]));
345                self.mop_graph.values.push(node);
346            }
347            rv = *self.mop_graph.values[rv].fields.get(&index).unwrap();
348        }
349        self.merge_alias(lv, rv);
350    }
351
352    pub fn merge_alias(&mut self, e1: usize, e2: usize) {
353        rap_debug!("merge alias: {}, {}", e1, e2);
354        let mut s1 = self.mop_graph.find_alias_set(e1);
355        let mut s2 = self.mop_graph.find_alias_set(e2);
356
357        // Create set for e1 if needed
358        if s1.is_none() {
359            self.mop_graph
360                .alias_sets
361                .push([e1].into_iter().collect::<FxHashSet<usize>>());
362            s1 = Some(self.mop_graph.alias_sets.len() - 1);
363        }
364
365        // Create set for e2 if needed
366        if s2.is_none() {
367            self.mop_graph
368                .alias_sets
369                .push([e2].into_iter().collect::<FxHashSet<usize>>());
370            s2 = Some(self.mop_graph.alias_sets.len() - 1);
371        }
372
373        // After creation, fetch indices (unwrap OK)
374        let idx1 = s1.unwrap();
375        let idx2 = s2.unwrap();
376
377        if idx1 == idx2 {
378            return;
379        }
380
381        let set2 = self.mop_graph.alias_sets.remove(idx2);
382        // If idx2 < idx1, removing idx2 shifts idx1 down by one
383        let idx1 = if idx2 < idx1 { idx1 - 1 } else { idx1 };
384        self.mop_graph.alias_sets[idx1].extend(set2);
385
386        if self.mop_graph.values[e1].fields.len() > 0 {
387            self.sync_field_alias(e2, e1, 0, false);
388        }
389        if self.mop_graph.values[e2].fields.len() > 0 {
390            self.sync_field_alias(e1, e2, 0, false);
391        }
392        if self.mop_graph.values[e1].father != None {
393            self.sync_father_alias(e2, e1, idx1);
394        }
395        if self.mop_graph.values[e2].father != None {
396            self.sync_father_alias(e1, e2, idx1);
397        }
398    }
399}
rapx/analysis/safedrop/alias.rs

rapx/analysis/safedrop/
alias.rs
