marekgalovic / radixt

A fast, memory-efficient radix tree implementation in Rust

Radix Tree RS

A fast, memory-efficient radix tree implementation in Rust.

Examples

use radixt::RadixMap;

let mut map = RadixMap::new();

map.insert("bar", 1);
map.insert("baz", 2);
map.insert("foo", 2);

assert_eq!(map.len(), 3);

assert_eq!(map.get("bar"), Some(&1));
assert_eq!(map.get("baz"), Some(&2));
assert_eq!(map.get("foo"), Some(&3));

Benchmarks

	enwiki-latest-all-titles		googlebooks-eng-all-5gram
	Time (s)	Max RSS (MB)	Time (s)	Max RSS (MB)
RadixSet	5.74	558.65	3.31	283.25
HashSet	6.37	2062.06	3.62	1205.06
BTreeSet	6.05	1276.07	2.76	867.42

The results above were obtained using examples/insert_lines.rs with data downloaded using:

# enwiki-latest-all-titles
$ curl -s https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-all-titles-in-ns0.gz | gzip -d > enwiki-latest-all-titles-in-ns0
# googlebooks-eng-all-5gram
$ curl -s http://storage.googleapis.com/books/ngrams/books/googlebooks-eng-all-5gram-20120701-0.gz | gzip -d > googlebooks-eng-all-5gram-20120701-0

radixt's Issues

Unsound implementation leads to UB

The source of unsoundness

Hi, we found that there are several unsound implementation in the package. e.g., in safe function replace_value

radixt/src/node.rs

Lines 460 to 463 in 301640f

	if self.flags().contains(Flags::VALUE_INITIALIZED) {
	// Replace old value
	Some(unsafe { std::mem::replace::<T>(&mut *self.value_ptr(), value) })
	} else {

At line 462, the code called the unsafe function self.value_ptr which could create a misaligned raw pointer.

radixt/src/node.rs

Lines 365 to 368 in 301640f

	unsafe fn value_ptr(&self) -> *mut T {
	assert!(self.flags().contains(Flags::VALUE_ALLOCATED));
	self.data.as_ptr().add(2 + self.key_len()) as *mut T
	}

In line 367, self.data was aligned to 8 bits, and could be casted to arbitrary aligned type. It was returned to line 462 in replace_value, followed by a dereference. Even though value_ptr() was declared as unsafe method, it was called by several safe function, and the undefined behavior led by misaligned pointer dereference should not happen in safe function.
The affected functions include value

radixt/src/node.rs

Lines 83 to 88 in 301640f

	pub(crate) fn value(&self) -> Option<&T> {
	if self.flags().contains(Flags::VALUE_INITIALIZED) {
	return unsafe { Some(&*self.value_ptr()) };
	}
	None
	}

and value_mut

radixt/src/node.rs

Lines 91 to 96 in 301640f

	pub(crate) fn value_mut(&mut self) -> Option<&mut T> {
	if self.flags().contains(Flags::VALUE_INITIALIZED) {
	return unsafe { Some(&mut *self.value_ptr()) };
	}
	None
	}

and next

radixt/src/iter.rs

Lines 103 to 124 in 301640f

	fn next(&mut self) -> Option<Self::Item> {
	match self.stack.pop() {
	Some((prefix_len, node)) => {
	// Update prefix
	self.prefix.truncate(prefix_len);
	self.prefix.extend(node.key());
	let value = node.value_mut().map(|v| v as *mut T);
	// Push node's children to stack
	for child in node.children_mut().iter_mut().rev() {
	self.stack.push((self.prefix.len(), child));
	}
	// Return value
	match value {
	Some(v) => Some(M::map(&self.prefix, unsafe {
	// SAFETY
	// We are giving out mutable references to node's value
	// while holding a mutable reference to the node itself
	// so this is OK.
	&mut *v

To reproduce the bug

Simply running cargo test could trigger the undefined behavior in replace_value

running 52 tests
test map::tests::test_into_iter_unfinished ... ok
test map::tests::test_into_iter_drops_internal_values ... ok
test map::tests::test_into_iter ... ok
test node::tests::test_children_add ... ok
test node::tests::test_children_remove ... ok
test node::tests::test_children_remove_last_item ... ok
test node::tests::test_children_push_full ... ok
test node::tests::test_new ... ok
test node::tests::test_take_children ... ok
test node::tests::test_take_children_front_back ... ok
test node::tests::test_take_children_rev ... ok
test node::tests::test_take_children_rev_unfinished ... ok
test node::tests::test_take_children_with_no_children ... ok
test node::tests::test_take_children_unfinished ... ok
test set::tests::test_difference_empty ... ok
test set::tests::test_difference ... ok
test set::tests::test_from ... ok
test set::tests::test_from_iterator ... ok
test set::tests::test_insert_and_get ... ok
test set::tests::test_intersection_empty ... ok
test set::tests::test_intersection_full ... ok
test set::tests::test_intersection_partial ... ok
test set::tests::test_iter ... ok
test set::tests::test_prefix_iter ... ok
test set::tests::test_remove ... ok
test set::tests::test_union_full_overlap ... ok
test set::tests::test_union_interleaved ... ok
test set::tests::test_union_no_overlap ... ok
test set::tests::test_union_partial_overlap ... ok
test tests::test_longest_common_prefix ... ok
test set::tests::test_with_long_keys ... ok
thread 'map::tests::test_from_iterator' panicked at 'misaligned pointer dereference: address must be a multiple of 0x8 but is 0x7f9e08000da5', src/node.rs:462:50
stack backtrace:
   0: begin_panic_handler
             at /rustc/a97c36dd2e6f711949fc9b790476e93bd9e6d1f4/library/std/src/panicking.rs:593:5
   1: panic_fmt
             at /rustc/a97c36dd2e6f711949fc9b790476e93bd9e6d1f4/library/core/src/panicking.rs:67:14
   2: panic_misaligned_pointer_dereference
             at /rustc/a97c36dd2e6f711949fc9b790476e93bd9e6d1f4/library/core/src/panicking.rs:174:5
   3: radixt::node::Node<T>::replace_value
             at ./src/node.rs:462:50
   4: radixt::node::Node<T>::insert
             at ./src/node.rs:136:20
   5: radixt::node::Node<T>::insert
             at ./src/node.rs:157:20
   6: radixt::map::RadixMap<T>::insert
             at ./src/map.rs:49:19
   7: <radixt::map::RadixMap<T> as core::iter::traits::collect::FromIterator<(K,T)>>::from_iter
             at ./src/map.rs:228:13
   8: core::iter::traits::iterator::Iterator::collect
             at /rustc/a97c36dd2e6f711949fc9b790476e93bd9e6d1f4/library/core/src/iter/traits/iterator.rs:1895:9
   9: radixt::map::tests::test_from_iterator
             at ./src/map.rs:660:34
  10: radixt::map::tests::test_from_iterator::{{closure}}
             at ./src/map.rs:659:29
  11: core::ops::function::FnOnce::call_once
             at /rustc/a97c36dd2e6f711949fc9b790476e93bd9e6d1f4/library/core/src/ops/function.rs:250:5
  12: call_once<fn() -> core::result::Result<(), alloc::string::String>, ()>
             at /rustc/a97c36dd2e6f711949fc9b790476e93bd9e6d1f4/library/core/src/ops/function.rs:250:5

Conclusion

The misaligned pointer was created in value_ptr(), but the method itself was unsafe. Therefore, the safe function who called the unsafe method should take care of the unaligned pointer. For example, you could use std::ptr::read_unaligned¹ instead.

Footnotes

1. https://doc.rust-lang.org/stable/std/ptr/fn.read_unaligned.html ↩