Coder Social home page Coder Social logo

id-map's People

Contributors

andrewhickman avatar

Stargazers

 avatar  avatar  avatar

Watchers

 avatar  avatar  avatar

id-map's Issues

Id type other than usize

Would it be possible to have a type parameter for IdMap that determines the Id type? I would like to use u16 instead of usize.

Multiple panic safety issues

Hi there, we (Rust group @sslab-gatech) are scanning crates on crates.io for potential soundness bugs. We noticed a few panic safety issues in this library.


clone_from double-frees if T::clone panics

id-map/src/lib.rs

Lines 370 to 380 in a2fa8d4

unsafe { self.drop_values() };
self.ids.clone_from(&other.ids);
let cap = other.values.capacity();
self.values.reserve(cap);
unsafe {
for id in &self.ids {
ptr::write(self.values.get_unchecked_mut(id),
other.values.get_unchecked(id).clone());
}
}

The current values in the map are dropped and the ids are updated up front. This means that if other.values.get_unchecked(id).clone() panics, it can cause the previously dropped values to drop again.


get_or_insert double frees if insertion function f panics

id-map/src/lib.rs

Lines 169 to 180 in a2fa8d4

// val was not previously in the map.
if id == self.space {
self.find_space();
}
if self.values.capacity() < id + 1 {
self.values.reserve(id + 1);
}
unsafe {
let space = self.values.get_unchecked_mut(id);
ptr::write(space, f());
space
}

Since this reserves space for the value before calling ptr::write(space, f());, if f panics here, it can drop an already freed value.


remove_set double frees if drop panics

id-map/src/lib.rs

Lines 192 to 203 in a2fa8d4

if let Some(first) = iter.next() {
// Set iterators are increasing so we only need to change start once.
self.space = cmp::min(self.space, first);
unsafe {
ptr::drop_in_place(self.values.get_unchecked_mut(first))
}
for id in iter {
unsafe {
ptr::drop_in_place(self.values.get_unchecked_mut(id))
}
}
}

This code goes over to the ids to remove and calls drop_in_place on them. However if the drop function for the type panics, the element gets dropped again when the IdMap is dropped.


Code to recrate these problems is here:

#![forbid(unsafe_code)]

use id_map::IdMap;
use id_set::IdSet;

struct DropDetector(u32);

impl Drop for DropDetector {
    fn drop(&mut self) {
        println!("Dropping {}", self.0);
    }
}
impl Clone for DropDetector {
    fn clone(&self) -> Self { panic!("Panic on clone!"); }
}

fn main() {
    //clone_from_panic_will_drop_invalid_memory();
    //get_or_insert_with_leaves_state_inconsistent();
    remove_set_leaves_state_inconsistent_if_drop_panics();
}

fn clone_from_panic_will_drop_invalid_memory() {
    let mut map = IdMap::new();
    map.insert(DropDetector(1));

    let mut map_2 = IdMap::new();
    map_2.insert(DropDetector(2));
    map_2.clone_from(&map);
}

fn get_or_insert_with_leaves_state_inconsistent() {
    let mut map : IdMap<DropDetector> = IdMap::with_capacity(0);
    map.get_or_insert_with(0, || panic!("Panic in insertion function!"));
}

struct PanicsOnDrop(u32, bool);

impl Drop for PanicsOnDrop {
    fn drop(&mut self) {
        println!("Dropping {}", self.0);

        if (self.1) {
            self.1 = false;
            panic!("Panicking on drop");
        }
    }
}

fn remove_set_leaves_state_inconsistent_if_drop_panics() {
    let mut map = IdMap::new();
    map.insert(PanicsOnDrop(1, true));

    map.remove_set(&IdSet::new_filled(1));
}

retain and similar methods do not properly update the next_id

Example code showing the difference in behavior:

extern crate id_map;

use id_map::IdMap;

fn main() {
    // test 1
    let mut map1 = IdMap::new();
    for _ in 0..10 {
        map1.insert("foo");
    }
    // remove all odd ids
    for i in 0..5 {
        map1.remove(i*2+1);
    }
    // prints {0, 2, 4, 6, 8}
    println!("{:?}", map1.as_set());
    // prints 1
    println!("{}", map1.next_id());

    // test2
    let mut map2 = IdMap::new();
    for _ in 0..10 {
        map2.insert("foo");
    }
    // remove all odd ids
    map2.retain(|id, _| id%2 == 0);
    // prints {0, 2, 4, 6, 8}
    println!("{:?}", map2.as_set());
    // prints 10
    println!("{}", map2.next_id());
}

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.