From 8b09d046fedf84ed869204bbe0779a0439bbf9eb Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Thu, 18 Apr 2019 11:41:28 +0200 Subject: [PATCH] fix LinkedList invalidating mutable references --- src/liballoc/collections/linked_list.rs | 48 +++++++++++++++++++------ 1 file changed, 37 insertions(+), 11 deletions(-) diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs index d6d84a4f083..bc1a024e989 100644 --- a/src/liballoc/collections/linked_list.rs +++ b/src/liballoc/collections/linked_list.rs @@ -86,6 +86,9 @@ fn clone(&self) -> Self { /// [`LinkedList`]: struct.LinkedList.html #[stable(feature = "rust1", since = "1.0.0")] pub struct IterMut<'a, T: 'a> { + // We do *not* exclusively own the entire list here, references to node's `element` + // have been handed out by the iterator! So be careful when using this; the methods + // called must be aware that there can be aliasing pointers to `element`. list: &'a mut LinkedList, head: Option>>, tail: Option>>, @@ -143,6 +146,8 @@ impl LinkedList { /// Adds the given node to the front of the list. #[inline] fn push_front_node(&mut self, mut node: Box>) { + // This method takes care not to create mutable references to whole nodes, + // to maintain validity of aliasing pointers into `element`. unsafe { node.next = self.head; node.prev = None; @@ -150,7 +155,8 @@ fn push_front_node(&mut self, mut node: Box>) { match self.head { None => self.tail = node, - Some(mut head) => head.as_mut().prev = node, + // Not creating new mutable (unique!) references overlapping `element`. + Some(head) => (*head.as_ptr()).prev = node, } self.head = node; @@ -161,13 +167,16 @@ fn push_front_node(&mut self, mut node: Box>) { /// Removes and returns the node at the front of the list. #[inline] fn pop_front_node(&mut self) -> Option>> { + // This method takes care not to create mutable references to whole nodes, + // to maintain validity of aliasing pointers into `element`. self.head.map(|node| unsafe { let node = Box::from_raw(node.as_ptr()); self.head = node.next; match self.head { None => self.tail = None, - Some(mut head) => head.as_mut().prev = None, + // Not creating new mutable (unique!) references overlapping `element`. + Some(head) => (*head.as_ptr()).prev = None, } self.len -= 1; @@ -178,6 +187,8 @@ fn pop_front_node(&mut self) -> Option>> { /// Adds the given node to the back of the list. #[inline] fn push_back_node(&mut self, mut node: Box>) { + // This method takes care not to create mutable references to whole nodes, + // to maintain validity of aliasing pointers into `element`. unsafe { node.next = None; node.prev = self.tail; @@ -185,7 +196,8 @@ fn push_back_node(&mut self, mut node: Box>) { match self.tail { None => self.head = node, - Some(mut tail) => tail.as_mut().next = node, + // Not creating new mutable (unique!) references overlapping `element`. + Some(tail) => (*tail.as_ptr()).next = node, } self.tail = node; @@ -196,13 +208,16 @@ fn push_back_node(&mut self, mut node: Box>) { /// Removes and returns the node at the back of the list. #[inline] fn pop_back_node(&mut self) -> Option>> { + // This method takes care not to create mutable references to whole nodes, + // to maintain validity of aliasing pointers into `element`. self.tail.map(|node| unsafe { let node = Box::from_raw(node.as_ptr()); self.tail = node.prev; match self.tail { None => self.head = None, - Some(mut tail) => tail.as_mut().next = None, + // Not creating new mutable (unique!) references overlapping `element`. + Some(tail) => (*tail.as_ptr()).next = None, } self.len -= 1; @@ -213,18 +228,22 @@ fn pop_back_node(&mut self) -> Option>> { /// Unlinks the specified node from the current list. /// /// Warning: this will not check that the provided node belongs to the current list. + /// + /// This method takes care not to create mutable references to `element`, to + /// maintain validity of aliasing pointers. #[inline] unsafe fn unlink_node(&mut self, mut node: NonNull>) { - let node = node.as_mut(); + let node = node.as_mut(); // this one is ours now, we can create an &mut. + // Not creating new mutable (unique!) references overlapping `element`. match node.prev { - Some(mut prev) => prev.as_mut().next = node.next.clone(), + Some(prev) => (*prev.as_ptr()).next = node.next.clone(), // this node is the head node None => self.head = node.next.clone(), }; match node.next { - Some(mut next) => next.as_mut().prev = node.prev.clone(), + Some(next) => (*next.as_ptr()).prev = node.prev.clone(), // this node is the tail node None => self.tail = node.prev.clone(), }; @@ -297,6 +316,8 @@ pub fn append(&mut self, other: &mut Self) { match self.tail { None => mem::swap(self, other), Some(mut tail) => { + // `as_mut` is okay here because we have exclusive access to the entirety + // of both lists. if let Some(mut other_head) = other.head.take() { unsafe { tail.as_mut().next = Some(other_head); @@ -916,9 +937,11 @@ impl IterMut<'_, T> { issue = "27794")] pub fn insert_next(&mut self, element: T) { match self.head { + // `push_back` is okay with aliasing `element` references None => self.list.push_back(element), - Some(mut head) => unsafe { - let mut prev = match head.as_ref().prev { + Some(head) => unsafe { + let prev = match head.as_ref().prev { + // `push_front` is okay with aliasing nodes None => return self.list.push_front(element), Some(prev) => prev, }; @@ -929,8 +952,10 @@ pub fn insert_next(&mut self, element: T) { element, })); - prev.as_mut().next = node; - head.as_mut().prev = node; + // Not creating references to entire nodes to not invalidate the + // reference to `element` we handed to the user. + (*prev.as_ptr()).next = node; + (*head.as_ptr()).prev = node; self.list.len += 1; }, @@ -994,6 +1019,7 @@ fn next(&mut self) -> Option { self.idx += 1; if (self.pred)(&mut node.as_mut().element) { + // `unlink_node` is okay with aliasing `element` references. self.list.unlink_node(node); return Some(Box::from_raw(node.as_ptr()).element); } -- 2.44.0