rust raw pointer not working without a println!() statement

Question

Today i try to use unsafe code to resolve a test, but encountered a weird problem, I found unrelated statement will affect the behavior of unsafe code. below is my code:

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

use rand;
use std::ptr::null;


struct Solution {
    list: Option<Box<ListNode>>,
    ptr: *const Option<Box<ListNode>>
}


impl Solution {
    fn new(head: Option<Box<ListNode>>) -> Self {
        let mut s = Self {
            list: head,
            ptr: null(),
        };
        s.ptr = &s.list as *const Option<Box<ListNode>>;
        s
    }
    
    fn get_random(&mut self) -> i32 {
        // generate random jumps
        let mut jumps: u8 = rand::random();
        unsafe {
            // if self.ptr is not point to the last node, update self.ptr to point next node
            // else point to head
            while jumps > 0 {
                if (*self.ptr).as_ref().unwrap().next.is_some() {
                    self.ptr = &(*self.ptr).as_ref().unwrap().next as *const Option<Box<ListNode>>;
                } else {
                    self.ptr = &self.list as *const Option<Box<ListNode>>;
                }
                jumps -= 1;
                // if comment below statement, the result will be like:
                // results: [573225736, 573225736, 573225736, 573225736]
                // if uncomment this statement, the result will be like:
                // results: [1, 2, 2, 1]
                // obviously the later one is correct
                println!("{}", jumps);
            }
            return (*self.ptr).as_ref().unwrap().val;
        }
    }
}


fn main() {
    let mut s = Solution::new(Some(Box::new(ListNode{
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode {
                val: 3,
                next: None,
            }))
        }))
    })));
    let mut res = Vec::new();
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    println!("results: {:?}", res);
}

Why is the result related to a println!() statement? It's so weird. Is there anyone can explain this for me?

That looks like undefined behavior. Not an answer per se, but it is ill advised to use `unsafe` in the early stages of learning, since as witnessed here, the outcome can be disastrous. Also, related, almost mandatory reading: https://rust-unofficial.github.io/too-many-lists/ And if you tried using a reference instead and that failed, see here: https://stackoverflow.com/questions/32300132/why-cant-i-store-a-value-and-a-reference-to-that-value-in-the-same-struct — E_net4, Aug 16 '21 at 12:57
Internal pointers like `s.ptr = &s.list as *const Option>;` are a recipe for disaster in rust, as structs regularly move around via memcpy, invalidating those pointers. — Colonel Thirty Two, Aug 16 '21 at 13:02
Probably your `ptr` should point to the inner `*const ListNode` not to the `Option<_>` itself. Since `ListNode` is behind a `Box` its address should be constant, that is not the case with the `Option`. — rodrigo, Aug 16 '21 at 14:06

Svetlin Zarev · Accepted Answer · 2021-08-16T16:43:35.880

You can use the MIRI tool to check for undefined behavior and other problems when using unsafe. I guess it won't catch all problems, yet it's still incredibly useful. Currently it's available only in nightly, but it's very easy to use via the rust playground:

error: Undefined Behavior: pointer to alloc1603 was dereferenced after this allocation got freed
  --> src/main.rs:45:20
   |
45 |                 if (*self.ptr).as_ref().unwrap().next.is_some() {
   |                    ^^^^^^^^^^^ pointer to alloc1603 was dereferenced after this allocation got freed
   |
   = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
   = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

As some comments have suggested you are storing the pointer to an Option (which can move) instead of the Box which cannot. If you change

    ptr: *const Option<Box<ListNode>>

to

    ptr: Option<*const ListNode>,

you will avoid the problem. This can be verified by MIRI, which no longer emits an error message:

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

use rand;
use std::ptr::null;

struct Solution {
    list: Option<Box<ListNode>>,
    ptr: Option<*const ListNode>,
}

impl Solution {
    fn new(head: Option<Box<ListNode>>) -> Self {
        let p = match &head {
            None => None,
            Some(h) => Some(&**h as *const ListNode),
        };

        let mut s = Self { list: head, ptr: p };
        s
    }

    fn get_random(&mut self) -> i32 {
        // generate random jumps
        let mut jumps: u8 = rand::random();
        unsafe {
            // if self.ptr is not point to the last node, update self.ptr to point next node
            // else point to head
            while jumps > 0 {
                if let Some(p) = self.ptr {
                    self.ptr = match &(*p).next {
                        None => Some(&**self.list.as_ref().unwrap() as *const ListNode),
                        Some(n) => Some(&**n as *const ListNode),
                    };
                }

                jumps -= 1;
                // if comment below statement, the result will be like:
                // results: [573225736, 573225736, 573225736, 573225736]
                // if uncomment this statement, the result will be like:
                // results: [1, 2, 2, 1]
                // obviously the later one is correct
                println!("{}", jumps);
            }
            return (*(self.ptr.unwrap())).val;
        }
    }
}

fn main() {
    let mut s = Solution::new(Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode { val: 3, next: None })),
        })),
    })));
    let mut res = Vec::new();
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    println!("results: {:?}", res);
}

PS: your code assumes that the list passed to new() will never be None and bad things can happen in that case :)

Instead of `&**h as *const ListNode` I like to do `Box::as_ref(h) as *const ListNode`, this way I let the auto dereference decide how many `*` to use. — rodrigo, Aug 16 '21 at 16:39
@Svetlin Zarev thanks so much, I think I got the difference between ```*const Option>``` and ```Option<*const ListNode>```, I have retried with ```*const ListNode```, it works very well, because the input of the function will never be ```None``` . But is this solution stable? Is there any situation in which the linked list will move to another location? — wangjun, Aug 17 '21 at 01:16

rust raw pointer not working without a println!() statement

1 Answers1