rapx/analysis/safedrop/
alias.rs

1use crate::{
2    rap_error,
3    analysis::core::alias_analysis::mop::{FnMap, MopAAFact},
4};
5use super::{graph::*,types::*};
6use rustc_middle::{
7    ty::{self, TyCtxt, TypingEnv},
8    mir::{Operand, Place, ProjectionElem, TerminatorKind}
9};
10
11impl<'tcx> SafeDropGraph<'tcx> {
12    /* alias analysis for a single block */
13    pub fn alias_bb(&mut self, bb_index: usize, tcx: TyCtxt<'tcx>) {
14        for stmt in self.blocks[bb_index].const_value.clone() {
15            self.constant.insert(stmt.0, stmt.1);
16        }
17        let cur_block = self.blocks[bb_index].clone();
18        for assign in cur_block.assignments {
19            let mut lv_aliaset_idx = self.projection(tcx, false, assign.lv);
20            let rv_aliaset_idx = self.projection(tcx, true, assign.rv);
21            match assign.atype {
22                AssignType::Variant => {
23                    self.alias_set[lv_aliaset_idx] = rv_aliaset_idx;
24                    continue;
25                }
26                AssignType::InitBox => {
27                    lv_aliaset_idx = *self.values[lv_aliaset_idx].fields.get(&0).unwrap();
28                }
29                _ => {} // Copy or Move
30            }
31            self.uaf_check(
32                rv_aliaset_idx,
33                assign.span,
34                assign.rv.local.as_usize(),
35                false,
36            );
37            self.fill_birth(lv_aliaset_idx, self.scc_indices[bb_index] as isize);
38            if self.values[lv_aliaset_idx].local != self.values[rv_aliaset_idx].local {
39                self.merge_alias(lv_aliaset_idx, rv_aliaset_idx, 0);
40            }
41        }
42    }
43
44    /* Check the aliases introduced by the terminators (function call) of a scc block */
45    pub fn alias_bbcall(&mut self, bb_index: usize, tcx: TyCtxt<'tcx>, fn_map: &FnMap) {
46        let cur_block = self.blocks[bb_index].clone();
47        for call in cur_block.calls {
48            if let TerminatorKind::Call {
49                ref func,
50                ref args,
51                ref destination,
52                target: _,
53                unwind: _,
54                call_source: _,
55                fn_span: _,
56            } = call.kind
57            {
58                if let Operand::Constant(ref constant) = func {
59                    let lv = self.projection(tcx, false, destination.clone());
60                    self.values[lv].birth = self.scc_indices[bb_index] as isize;
61                    let mut merge_vec = Vec::new();
62                    merge_vec.push(lv);
63                    let mut may_drop_flag = 0;
64                    if self.values[lv].may_drop {
65                        may_drop_flag += 1;
66                    }
67                    for arg in args {
68                        match arg.node {
69                            Operand::Copy(ref p) => {
70                                let rv = self.projection(tcx, true, p.clone());
71                                self.uaf_check(rv, call.source_info.span, p.local.as_usize(), true);
72                                merge_vec.push(rv);
73                                if self.values[rv].may_drop {
74                                    may_drop_flag += 1;
75                                }
76                            }
77                            Operand::Move(ref p) => {
78                                let rv = self.projection(tcx, true, p.clone());
79                                self.uaf_check(rv, call.source_info.span, p.local.as_usize(), true);
80                                merge_vec.push(rv);
81                                if self.values[rv].may_drop {
82                                    may_drop_flag += 1;
83                                }
84                            }
85                            Operand::Constant(_) => {
86                                merge_vec.push(0);
87                            }
88                        }
89                    }
90                    if let ty::FnDef(ref target_id, _) = constant.const_.ty().kind() {
91                        if may_drop_flag > 1 {
92                            if tcx.is_mir_available(*target_id) {
93                                if fn_map.contains_key(&target_id) {
94                                    let assignments = fn_map.get(&target_id).unwrap();
95                                    for assign in assignments.aliases().iter() {
96                                        if !assign.valuable() {
97                                            continue;
98                                        }
99                                        self.merge(assign, &merge_vec);
100                                    }
101                                }
102                            } else {
103                                if self.values[lv].may_drop {
104                                    if self.corner_handle(lv, &merge_vec, *target_id) {
105                                        continue;
106                                    }
107                                    let mut right_set = Vec::new();
108                                    for rv in &merge_vec {
109                                        if self.values[*rv].may_drop
110                                            && lv != *rv
111                                            && self.values[lv].is_ptr()
112                                        {
113                                            right_set.push(*rv);
114                                        }
115                                    }
116                                    if right_set.len() == 1 {
117                                        self.merge_alias(lv, right_set[0], 0);
118                                    }
119                                }
120                            }
121                        }
122                    }
123                }
124            }
125        }
126    }
127
128    // assign to the variable _x, we will set the birth of _x and its child self.values a new birth.
129    pub fn fill_birth(&mut self, node: usize, birth: isize) {
130        self.values[node].birth = birth;
131        for i in 0..self.values.len() {
132            if self.union_is_same(i, node) && self.values[i].birth == -1 {
133                self.values[i].birth = birth;
134            }
135        }
136        for i in self.values[node].fields.clone().into_iter() {
137            self.fill_birth(i.1, birth); //i.1 corresponds to the local field.
138        }
139    }
140
141    /*
142     * This is the function for field sensitivity
143     * If the projection is a deref, we directly return its head alias or alias[0].
144     * If the id is not a ref, we further make the id and its first element an alias, i.e., level-insensitive
145     *
146     */
147    pub fn projection(&mut self, tcx: TyCtxt<'tcx>, is_right: bool, place: Place<'tcx>) -> usize {
148        let mut local = place.local.as_usize();
149        let mut proj_id = local;
150        for proj in place.projection {
151            let new_id = self.values.len();
152            match proj {
153                ProjectionElem::Deref => {
154                    //proj_id = self.values[proj_id].alias[0];
155                    proj_id = self.alias_set[proj_id];
156                }
157                /*
158                 * Objective: 2 = 1.0; 0 = 2.0; => 0 = 1.0.0
159                 */
160                ProjectionElem::Field(field, ty) => {
161                    if is_right && self.alias_set[proj_id] != proj_id {
162                        proj_id = self.alias_set[proj_id];
163                        local = self.values[proj_id].local;
164                    }
165                    let field_idx = field.as_usize();
166                    if !self.values[proj_id].fields.contains_key(&field_idx) {
167                        let ty_env = TypingEnv::post_analysis(tcx, self.def_id);
168                        let need_drop = ty.needs_drop(tcx, ty_env);
169                        let may_drop = !is_not_drop(tcx, ty);
170                        let mut node =
171                            ValueNode::new(new_id, local, need_drop, need_drop || may_drop);
172                        node.kind = kind(ty);
173                        node.birth = self.values[proj_id].birth;
174                        node.field_id = field_idx;
175                        self.values[proj_id].fields.insert(field_idx, node.index);
176                        self.alias_set.push(self.alias_set.len());
177                        self.dead_record.push(false);
178                        self.values.push(node);
179                    }
180                    proj_id = *self.values[proj_id].fields.get(&field_idx).unwrap();
181                }
182                _ => {}
183            }
184        }
185        return proj_id;
186    }
187
188    //instruction to assign alias for a variable.
189    pub fn merge_alias(&mut self, lv: usize, rv: usize, depth: usize) {
190        // if self.values[lv].alias.len() > 1 {
191        //     let mut alias_clone = self.values[rv].alias.clone();
192        //     self.values[lv].alias.append(&mut alias_clone);
193        // } else {
194        //     self.values[lv].alias = self.values[rv].alias.clone();
195        // }
196        if lv > self.values.len() || rv > self.values.len() {
197            return;
198        }
199        self.union_merge(lv, rv);
200
201        let max_field_depth = match std::env::var_os("SAFEDROP") {
202            Some(val) if val == "0" => 10,
203            Some(val) if val == "1" => 20,
204            Some(val) if val == "2" => 30,
205            Some(val) if val == "3" => 50,
206            _ => 15,
207        };
208
209        if depth > max_field_depth {
210            return;
211        }
212
213        for field in self.values[rv].fields.clone().into_iter() {
214            if !self.values[lv].fields.contains_key(&field.0) {
215                let mut node = ValueNode::new(
216                    self.values.len(),
217                    self.values[lv].local,
218                    self.values[field.1].need_drop,
219                    self.values[field.1].may_drop,
220                );
221                node.kind = self.values[field.1].kind;
222                node.birth = self.values[lv].birth;
223                node.field_id = field.0;
224                self.values[lv].fields.insert(field.0, node.index);
225                self.alias_set.push(self.alias_set.len());
226                self.dead_record.push(false);
227                self.values.push(node);
228            }
229            let lv_field = *(self.values[lv].fields.get(&field.0).unwrap());
230            self.merge_alias(lv_field, field.1, depth + 1);
231        }
232    }
233
234    //inter-procedure instruction to merge alias.
235    pub fn merge(&mut self, ret_alias: &MopAAFact, arg_vec: &Vec<usize>) {
236        if ret_alias.lhs_no() >= arg_vec.len() || ret_alias.rhs_no() >= arg_vec.len() {
237            rap_error!("Vector error!");
238            return;
239        }
240        let left_init = arg_vec[ret_alias.lhs_no()];
241        let mut right_init = arg_vec[ret_alias.rhs_no()];
242        let mut lv = left_init;
243        let mut rv = right_init;
244        for index in ret_alias.lhs_fields().iter() {
245            if self.values[lv].fields.contains_key(&index) == false {
246                let need_drop = ret_alias.lhs_need_drop;
247                let may_drop = ret_alias.lhs_may_drop;
248                let mut node = ValueNode::new(self.values.len(), left_init, need_drop, may_drop);
249                node.kind = TyKind::RawPtr;
250                node.birth = self.values[lv].birth;
251                node.field_id = *index;
252                self.values[lv].fields.insert(*index, node.index);
253                self.alias_set.push(self.alias_set.len());
254                self.dead_record.push(false);
255                self.values.push(node);
256            }
257            lv = *self.values[lv].fields.get(&index).unwrap();
258        }
259        for index in ret_alias.rhs_fields().iter() {
260            // if self.values[rv].alias[0] != rv {
261            if self.union_is_same(rv, self.alias_set[rv]) {
262                rv = self.values[rv].index;
263                right_init = self.values[rv].local;
264            }
265            if !self.values[rv].fields.contains_key(&index) {
266                let need_drop = ret_alias.rhs_need_drop;
267                let may_drop = ret_alias.rhs_may_drop;
268                let mut node =
269                    ValueNode::new(self.alias_set.len(), right_init, need_drop, may_drop);
270                node.kind = TyKind::RawPtr;
271                node.birth = self.values[rv].birth;
272                node.field_id = *index;
273                self.values[rv].fields.insert(*index, node.index);
274                self.alias_set.push(self.values.len());
275                self.dead_record.push(false);
276                self.values.push(node);
277            }
278            rv = *self.values[rv].fields.get(&index).unwrap();
279        }
280        self.merge_alias(lv, rv, 0);
281    }
282
283    #[inline(always)]
284    pub fn union_find(&mut self, e: usize) -> usize {
285        let mut r = e;
286        while self.alias_set[r] != r {
287            r = self.alias_set[r];
288        }
289        r
290    }
291
292    #[inline(always)]
293    pub fn union_merge(&mut self, e1: usize, e2: usize) {
294        let f1 = self.union_find(e1);
295        let f2 = self.union_find(e2);
296
297        if f1 < f2 {
298            self.alias_set[f2] = f1;
299        }
300        if f1 > f2 {
301            self.alias_set[f1] = f2;
302        }
303
304        for member in 0..self.alias_set.len() {
305            self.alias_set[member] = self.union_find(self.alias_set[member]);
306        }
307    }
308
309    #[inline(always)]
310    pub fn union_is_same(&mut self, e1: usize, e2: usize) -> bool {
311        let f1 = self.union_find(e1);
312        let f2 = self.union_find(e2);
313        f1 == f2
314    }
315
316    #[inline(always)]
317    pub fn union_has_alias(&mut self, e: usize) -> bool {
318        for i in 0..self.alias_set.len() {
319            if i == e {
320                continue;
321            }
322            if self.union_is_same(e, i) {
323                return true;
324            }
325        }
326        false
327    }
328}
rapx/analysis/safedrop/alias.rs

rapx/analysis/safedrop/
alias.rs
