rapx/analysis/safedrop/
safedrop.rs

1use crate::analysis::{
2    core::alias_analysis::mop::FnMap,
3    safedrop::SafeDropGraph
4};
5use crate::rap_error;
6use rustc_data_structures::fx::FxHashSet;
7use rustc_middle::{
8    ty::{TyCtxt, TyKind, TypingEnv},
9    mir::{
10        Place, TerminatorKind,
11        Operand::{self, Constant, Copy, Move}
12    }
13};
14use std::collections::{HashMap, HashSet};
15
16pub const VISIT_LIMIT: usize = 1000;
17
18impl<'tcx> SafeDropGraph<'tcx> {
19    // analyze the drop statement and update the liveness for nodes.
20    pub fn drop_check(&mut self, bb_index: usize, tcx: TyCtxt<'tcx>) {
21        let cur_block = self.blocks[bb_index].clone();
22        for drop in cur_block.drops {
23            match drop.kind {
24                TerminatorKind::Drop {
25                    ref place,
26                    target: _,
27                    unwind: _,
28                    replace: _,
29                    drop: _,
30                    async_fut: _,
31                } => {
32                    if !self.drop_heap_item_check(place, tcx) {
33                        continue;
34                    }
35                    let birth = self.scc_indices[bb_index];
36                    let drop_local = self.projection(tcx, false, place.clone());
37                    let info = drop.source_info.clone();
38                    self.dead_node(drop_local, birth, &info, false);
39                }
40                TerminatorKind::Call {
41                    func: _, ref args, ..
42                } => {
43                    if args.len() > 0 {
44                        let birth = self.scc_indices[bb_index];
45                        let place = match args[0].node {
46                            Operand::Copy(place) => place,
47                            Operand::Move(place) => place,
48                            _ => {
49                                rap_error!("Constant operand exists: {:?}", args[0]);
50                                return;
51                            }
52                        };
53                        let drop_local = self.projection(tcx, false, place.clone());
54                        let info = drop.source_info.clone();
55                        self.dead_node(drop_local, birth, &info, false);
56                    }
57                }
58                _ => {}
59            }
60        }
61    }
62
63    pub fn drop_heap_item_check(&self, place: &Place<'tcx>, tcx: TyCtxt<'tcx>) -> bool {
64        let place_ty = place.ty(&tcx.optimized_mir(self.def_id).local_decls, tcx);
65        match place_ty.ty.kind() {
66            TyKind::Adt(adtdef, ..) => match self.adt_owner.get(&adtdef.did()) {
67                None => true,
68                Some(owenr_unit) => {
69                    let idx = match place_ty.variant_index {
70                        Some(vdx) => vdx.index(),
71                        None => 0,
72                    };
73                    if owenr_unit[idx].0.is_owned() || owenr_unit[idx].1.contains(&true) {
74                        true
75                    } else {
76                        false
77                    }
78                }
79            },
80            _ => true,
81        }
82    }
83
84    pub fn split_check(&mut self, bb_index: usize, tcx: TyCtxt<'tcx>, fn_map: &FnMap) {
85        /* duplicate the status before visiting a path; */
86        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
87        let backup_constant = self.constant.clone();
88        let backup_alias_set = self.alias_set.clone();
89        let backup_dead = self.dead_record.clone();
90        self.check(bb_index, tcx, fn_map);
91        /* restore after visit */
92        self.values = backup_values;
93        self.constant = backup_constant;
94        self.alias_set = backup_alias_set;
95        self.dead_record = backup_dead;
96    }
97
98    pub fn split_check_with_cond(
99        &mut self,
100        bb_index: usize,
101        path_discr_id: usize,
102        path_discr_val: usize,
103        tcx: TyCtxt<'tcx>,
104        fn_map: &FnMap,
105    ) {
106        /* duplicate the status before visiting a path; */
107        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
108        let backup_constant = self.constant.clone();
109        let backup_alias_set = self.alias_set.clone();
110        let backup_dead = self.dead_record.clone();
111        /* add control-sensitive indicator to the path status */
112        self.constant.insert(path_discr_id, path_discr_val);
113        self.check(bb_index, tcx, fn_map);
114        /* restore after visit */
115        self.values = backup_values;
116        self.constant = backup_constant;
117        self.alias_set = backup_alias_set;
118        self.dead_record = backup_dead;
119    }
120
121    // the core function of the safedrop.
122    pub fn check(&mut self, bb_index: usize, tcx: TyCtxt<'tcx>, fn_map: &FnMap) {
123        self.visit_times += 1;
124        if self.visit_times > VISIT_LIMIT {
125            return;
126        }
127        let cur_block = self.blocks[self.scc_indices[bb_index]].clone();
128        self.alias_bb(self.scc_indices[bb_index], tcx);
129        self.alias_bbcall(self.scc_indices[bb_index], tcx, fn_map);
130        self.drop_check(self.scc_indices[bb_index], tcx);
131
132        if self.child_scc.get(&self.scc_indices[bb_index]).is_some() {
133            let init_index = self.scc_indices[bb_index];
134            let (init_block, cur_targets, scc_block_set) =
135                self.child_scc.get(&init_index).unwrap().clone();
136
137            for enum_index in cur_targets.all_targets() {
138                let backup_values = self.values.clone();
139                let backup_constant = self.constant.clone();
140
141                let mut block_node = if bb_index == init_index {
142                    init_block.clone()
143                } else {
144                    self.blocks[bb_index].clone()
145                };
146
147                if !block_node.switch_stmts.is_empty() {
148                    let TerminatorKind::SwitchInt { targets, .. } =
149                        block_node.switch_stmts[0].kind.clone()
150                    else {
151                        unreachable!();
152                    };
153                    if cur_targets == targets {
154                        block_node.next = FxHashSet::default();
155                        block_node.next.insert(enum_index.index());
156                    }
157                }
158
159                let mut work_list = Vec::new();
160                let mut work_set = FxHashSet::<usize>::default();
161                work_list.push(bb_index);
162                work_set.insert(bb_index);
163                while !work_list.is_empty() {
164                    let current_node = work_list.pop().unwrap();
165                    block_node.scc_sub_blocks.push(current_node);
166                    let real_node = if current_node != init_index {
167                        self.blocks[current_node].clone()
168                    } else {
169                        init_block.clone()
170                    };
171
172                    if real_node.switch_stmts.is_empty() {
173                        for next in &real_node.next {
174                            block_node.next.insert(*next);
175                        }
176                    } else {
177                        let TerminatorKind::SwitchInt { ref targets, .. } =
178                            real_node.switch_stmts[0].kind
179                        else {
180                            unreachable!();
181                        };
182
183                        if cur_targets == *targets {
184                            block_node.next.insert(enum_index.index());
185                        } else {
186                            for next in &real_node.next {
187                                block_node.next.insert(*next);
188                            }
189                        }
190                    }
191
192                    if real_node.switch_stmts.is_empty() {
193                        for next in &real_node.next {
194                            if scc_block_set.contains(next) && !work_set.contains(next) {
195                                work_set.insert(*next);
196                                work_list.push(*next);
197                            }
198                        }
199                    } else {
200                        let TerminatorKind::SwitchInt { ref targets, .. } =
201                            real_node.switch_stmts[0].kind
202                        else {
203                            unreachable!();
204                        };
205
206                        if cur_targets == *targets {
207                            let next_index = enum_index.index();
208                            if scc_block_set.contains(&next_index)
209                                && !work_set.contains(&next_index)
210                            {
211                                work_set.insert(next_index);
212                                work_list.push(next_index);
213                            }
214                        } else {
215                            for next in &real_node.next {
216                                if scc_block_set.contains(next) && !work_set.contains(next) {
217                                    work_set.insert(*next);
218                                    work_list.push(*next);
219                                }
220                            }
221                        }
222                    }
223                }
224
225                /* remove next nodes which are already in the current SCC */
226                let mut to_remove = Vec::new();
227                for i in block_node.next.iter() {
228                    if self.scc_indices[*i] == init_index {
229                        to_remove.push(*i);
230                    }
231                }
232                for i in to_remove {
233                    block_node.next.remove(&i);
234                }
235
236                for i in block_node.scc_sub_blocks.clone() {
237                    self.alias_bb(i, tcx);
238                    self.alias_bbcall(i, tcx, fn_map);
239                    self.drop_check(i, tcx);
240                }
241                /* Reach a leaf node, check bugs */
242                match block_node.next.len() {
243                    0 => {
244                        // check the bugs.
245                        if Self::should_check(self.def_id) {
246                            self.dp_check(&cur_block);
247                        }
248                        return;
249                    }
250                    _ => {
251                        /*
252                         * Equivalent to self.check(cur_block.next[0]..);
253                         * We cannot use [0] for FxHashSet.
254                         */
255                        for next in block_node.next {
256                            self.check(next, tcx, fn_map);
257                        }
258                    }
259                }
260
261                self.values = backup_values;
262                self.constant = backup_constant;
263            }
264
265            return;
266        }
267
268        let mut order = vec![];
269        order.push(vec![]);
270
271        /* Handle cases if the current block is a merged scc block with sub block */
272        if !cur_block.scc_sub_blocks.is_empty() {
273            match std::env::var_os("SAFEDROP") {
274                Some(val) if val == "0" => {
275                    order.push(cur_block.scc_sub_blocks.clone());
276                }
277                _ => {
278                    self.calculate_scc_order(
279                        &mut cur_block.scc_sub_blocks.clone(),
280                        &mut vec![],
281                        &mut order,
282                        &mut HashMap::new(),
283                        bb_index,
284                        bb_index,
285                        &mut HashSet::new(),
286                    );
287                }
288            }
289        }
290
291        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
292        let backup_constant = self.constant.clone();
293        let backup_alias_set = self.alias_set.clone();
294        for scc_each in order {
295            self.alias_set = backup_alias_set.clone();
296            self.values = backup_values.clone();
297            self.constant = backup_constant.clone();
298
299            if !scc_each.is_empty() {
300                for idx in scc_each {
301                    self.alias_bb(idx, tcx);
302                    self.alias_bbcall(idx, tcx, fn_map);
303                }
304            }
305
306            let cur_block = cur_block.clone();
307            /* Reach a leaf node, check bugs */
308            match cur_block.next.len() {
309                0 => {
310                    if Self::should_check(self.def_id) {
311                        self.dp_check(&cur_block);
312                    }
313                    return;
314                }
315                1 => {
316                    /*
317                     * Equivalent to self.check(cur_block.next[0]..);
318                     * We cannot use [0] for FxHashSet.
319                     */
320                    for next in cur_block.next {
321                        self.check(next, tcx, fn_map);
322                    }
323                    return;
324                }
325                _ => { // multiple blocks
326                }
327            }
328
329            /* Begin: handle the SwitchInt statement. */
330            let mut single_target = false;
331            let mut sw_val = 0;
332            let mut sw_target = 0; // Single target
333            let mut path_discr_id = 0; // To avoid analyzing paths that cannot be reached with one enum type.
334            let mut sw_targets = None; // Multiple targets of SwitchInt
335            if !cur_block.switch_stmts.is_empty() && cur_block.scc_sub_blocks.is_empty() {
336                if let TerminatorKind::SwitchInt {
337                    ref discr,
338                    ref targets,
339                } = cur_block.switch_stmts[0].clone().kind
340                {
341                    match discr {
342                        Copy(p) | Move(p) => {
343                            let place = self.projection(tcx, false, *p);
344                            if let Some(father) = self.disc_map.get(&self.values[place].local) {
345                                if let Some(constant) = self.constant.get(father) {
346                                    if *constant != usize::MAX {
347                                        single_target = true;
348                                        sw_val = *constant;
349                                    }
350                                }
351                                if self.values[place].local == place {
352                                    path_discr_id = *father;
353                                    sw_targets = Some(targets.clone());
354                                }
355                            }
356                        }
357                        Constant(c) => {
358                            single_target = true;
359                            let ty_env = TypingEnv::post_analysis(self.tcx, self.def_id);
360                            if let Some(val) = c.const_.try_eval_target_usize(self.tcx, ty_env) {
361                                sw_val = val as usize;
362                            }
363                        }
364                    }
365                    if single_target {
366                        /* Find the target based on the value;
367                         * Since sw_val is a const, only one target is reachable.
368                         * Filed 0 is the value; field 1 is the real target.
369                         */
370                        for iter in targets.iter() {
371                            if iter.0 as usize == sw_val {
372                                sw_target = iter.1.as_usize();
373                                break;
374                            }
375                        }
376                        /* No target found, choose the default target.
377                         * The default targets is not included within the iterator.
378                         * We can only obtain the default target based on the last item of all_targets().
379                         */
380                        if sw_target == 0 {
381                            let all_target = targets.all_targets();
382                            sw_target = all_target[all_target.len() - 1].as_usize();
383                        }
384                    }
385                }
386            }
387            /* End: finish handling SwitchInt */
388            // fixed path since a constant switchInt value
389            if single_target {
390                self.check(sw_target, tcx, fn_map);
391            } else {
392                // Other cases in switchInt terminators
393                if let Some(targets) = sw_targets {
394                    for iter in targets.iter() {
395                        if self.visit_times > VISIT_LIMIT {
396                            continue;
397                        }
398                        let next_index = iter.1.as_usize();
399                        let path_discr_val = iter.0 as usize;
400                        self.split_check_with_cond(
401                            next_index,
402                            path_discr_id,
403                            path_discr_val,
404                            tcx,
405                            fn_map,
406                        );
407                    }
408                    let all_targets = targets.all_targets();
409                    let next_index = all_targets[all_targets.len() - 1].as_usize();
410                    let path_discr_val = usize::MAX; // to indicate the default path;
411                    self.split_check_with_cond(
412                        next_index,
413                        path_discr_id,
414                        path_discr_val,
415                        tcx,
416                        fn_map,
417                    );
418                } else {
419                    for i in cur_block.next {
420                        if self.visit_times > VISIT_LIMIT {
421                            continue;
422                        }
423                        let next_index = i;
424                        self.split_check(next_index, tcx, fn_map);
425                    }
426                }
427            }
428        }
429    }
430
431    pub fn calculate_scc_order(
432        &mut self,
433        scc: &Vec<usize>,
434        path: &mut Vec<usize>,
435        ans: &mut Vec<Vec<usize>>,
436        disc_map: &mut HashMap<usize, usize>,
437        idx: usize,
438        root: usize,
439        visit: &mut HashSet<usize>,
440    ) {
441        if idx == root && !path.is_empty() {
442            ans.push(path.clone());
443            return;
444        }
445        visit.insert(idx);
446        let term = &self.terms[idx].clone();
447
448        match term {
449            TerminatorKind::SwitchInt {
450                ref discr,
451                ref targets,
452            } => match discr {
453                Copy(p) | Move(p) => {
454                    let place = self.projection(self.tcx, false, *p);
455                    if let Some(father) = self.disc_map.get(&self.values[place].local) {
456                        let father = *father;
457                        if let Some(constant) = disc_map.get(&father) {
458                            let constant = *constant;
459                            for t in targets.iter() {
460                                if t.0 as usize == constant {
461                                    let target = t.1.as_usize();
462                                    if path.contains(&target) {
463                                        continue;
464                                    }
465                                    path.push(target);
466                                    self.calculate_scc_order(
467                                        scc, path, ans, disc_map, target, root, visit,
468                                    );
469                                    path.pop();
470                                }
471                            }
472                        } else {
473                            for t in targets.iter() {
474                                let constant = t.0 as usize;
475                                let target = t.1.as_usize();
476                                if path.contains(&target) {
477                                    continue;
478                                }
479                                path.push(target);
480                                disc_map.insert(father, constant);
481                                self.calculate_scc_order(
482                                    scc, path, ans, disc_map, target, root, visit,
483                                );
484                                disc_map.remove(&father);
485                                path.pop();
486                            }
487                        }
488                    } else {
489                        if let Some(constant) = disc_map.get(&place) {
490                            let constant = *constant;
491                            for t in targets.iter() {
492                                if t.0 as usize == constant {
493                                    let target = t.1.as_usize();
494                                    if path.contains(&target) {
495                                        continue;
496                                    }
497                                    path.push(target);
498                                    self.calculate_scc_order(
499                                        scc, path, ans, disc_map, target, root, visit,
500                                    );
501                                    path.pop();
502                                }
503                            }
504                        } else {
505                            for t in targets.iter() {
506                                let constant = t.0 as usize;
507                                let target = t.1.as_usize();
508                                if path.contains(&target) {
509                                    continue;
510                                }
511                                path.push(target);
512                                disc_map.insert(place, constant);
513                                self.calculate_scc_order(
514                                    scc, path, ans, disc_map, target, root, visit,
515                                );
516                                disc_map.remove(&place);
517                                path.pop();
518                            }
519
520                            let constant = targets.iter().len();
521                            let target = targets.otherwise().as_usize();
522                            if !path.contains(&target) {
523                                path.push(target);
524                                disc_map.insert(place, constant);
525                                self.calculate_scc_order(
526                                    scc, path, ans, disc_map, target, root, visit,
527                                );
528                                disc_map.remove(&place);
529                                path.pop();
530                            }
531                        }
532                    }
533                }
534                _ => {}
535            },
536            _ => {
537                for bidx in self.blocks[idx].next.clone() {
538                    if !scc.contains(&bidx) && bidx != root {
539                        continue;
540                    }
541                    if bidx != root {
542                        path.push(bidx);
543                        self.calculate_scc_order(scc, path, ans, disc_map, bidx, root, visit);
544                        path.pop();
545                    } else {
546                        self.calculate_scc_order(scc, path, ans, disc_map, bidx, root, visit);
547                    }
548                }
549            }
550        }
551
552        visit.remove(&idx);
553    }
554}
rapx/analysis/safedrop/safedrop.rs

rapx/analysis/safedrop/
safedrop.rs
