This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1327

radix204: add a mmap-based vector type
AbandonedPublic

Authored by quark on Nov 7 2017, 12:40 PM.
Tags
None
Subscribers
None

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

This allows us to replace Vec used in radix.rs to the mmap-based version,
which is more efficient if the index or key buffer is large.

Test Plan

cargo test --lib. Also make sure kcov reports 100% coverage of
mmapvec.rs.

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Nov 7 2017, 12:40 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 7 2017, 12:40 PM
quark abandoned this revision.Nov 11 2017, 1:34 AM

This is not related to the main library. Therefore moved to another place.

Revision Contents
Changeset List

Diff 3312

rust/radix204/Cargo.toml

[package] [package]
name = "radix204" name = "radix204"
version = "0.1.0" version = "0.1.0"
[dependencies] [dependencies]
error-chain = "0.11" error-chain = "0.11"
libc = "0.2"
memmap = "0.6"
[dev-dependencies] [dev-dependencies]
quickcheck = "0.4" quickcheck = "0.4"
rand = "0.3" rand = "0.3"
rand_derive = "0.3" rand_derive = "0.3"
rustc-test = "0.2" rustc-test = "0.2"
tempdir = "0.3"

rust/radix204/src/errors.rs

// Copyright 2017 Facebook, Inc. // Copyright 2017 Facebook, Inc.
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
use types::KeyId; use types::KeyId;
error_chain! { error_chain! {
foreign_links { foreign_links {
BorrowMut(::std::cell::BorrowMutError); BorrowMut(::std::cell::BorrowMutError);
Io(::std::io::Error);
} }
errors { errors {
OffsetOverflow(offset: usize) { OffsetOverflow(offset: usize) {
description("offset overflow") description("offset overflow")
display("offset {} is out of range", offset) display("offset {} is out of range", offset)
} }
KeyConflict { KeyConflict {

rust/radix204/src/lib.rs

// Copyright 2017 Facebook, Inc. // Copyright 2017 Facebook, Inc.
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
#[cfg(test)] #[cfg(test)]
extern crate test; extern crate test;
#[macro_use] #[macro_use]
extern crate error_chain; extern crate error_chain;
extern crate memmap;
#[cfg(test)] #[cfg(test)]
#[macro_use] #[macro_use]
extern crate quickcheck; extern crate quickcheck;
#[cfg(test)] #[cfg(test)]
extern crate rand; extern crate rand;
#[cfg(test)] #[cfg(test)]
#[macro_use] #[macro_use]
extern crate rand_derive; extern crate rand_derive;
#[cfg(test)]
extern crate tempdir;
pub mod types; pub mod types;
pub mod errors; pub mod errors;
pub mod base16; pub mod base16;
pub mod radix; pub mod radix;
pub mod mmapvec;
pub type RadixBuffer = radix::RadixBuffer; pub type RadixBuffer = radix::RadixBuffer;

rust/radix204/src/mmapvec.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
//! Simple vector based on mmap
use errors::Result;
use std::borrow::Borrow;
use std::fs::{File, OpenOptions};
use std::io::{Seek, SeekFrom};
use std::marker::PhantomData;
use std::mem::size_of;
use std::ops::{Deref, DerefMut, Drop, Index, IndexMut, Range, RangeFrom, RangeTo, RangeFull};
use std::path::PathBuf;
use std::ptr;
use std::slice;
use memmap::{MmapMut, MmapOptions};
/// A subset of Vec<T> features based on a mmap-ed file. Application should take care of
/// locking so `MVec`s backed by a same file would either have multiple readers, or have
/// a unique reader.
pub struct MmapVec<T> {
mmap: MmapMut,
file: File,
len: usize,
cap: usize,
_t: PhantomData<T>,
}
impl<T: Copy> MmapVec<T> {
pub fn from_file(mut file: File) -> Result<Self> {
let min_size: usize = size_of::<T>().max(4096);
// Make sure the file is not empty and has a size of multiples of size_of::<T>()
file.seek(SeekFrom::Start(0))?;
let mut size = file.seek(SeekFrom::End(0))? as usize;
let len = size / size_of::<T>();
if size < min_size {
file.set_len(min_size as u64)?;
size = min_size;
}
let cap = size / size_of::<T>();
size = cap * size_of::<T>();
// mmap the file
let mmap = unsafe { MmapOptions::new().len(size).map_mut(&file) }?;
Ok(Self {
mmap,
file,
len,
cap,
_t: PhantomData,
})
}
pub fn from_path<P: Borrow<PathBuf>>(path: P) -> Result<Self> {
let file = OpenOptions::new()
.read(true)
.write(true)
.create(true)
.open(path.borrow())?;
Self::from_file(file)
}
#[inline]
pub fn len(&self) -> usize { self.len }
#[inline]
pub fn cap(&self) -> usize { self.cap }
pub fn extend_from_slice(&mut self, other: &[T]) {
let len = self.len();
let slice_len = other.len();
self.reserve(slice_len);
self.len += slice_len;
self[len..(len + slice_len)].copy_from_slice(other);
}
pub fn resize(&mut self, new_len: usize, value: T) {
let len = self.len;
if new_len > len {
let n = new_len - len;
self.reserve(n);
unsafe {
let mut ptr = self.mmap.as_mut_ptr() as *mut T;
ptr = ptr.offset(self.len as isize);
for _ in 0..n {
ptr::write(ptr, value);
ptr = ptr.offset(1);
}
}
}
self.len = new_len;
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
let required_cap = self.len + additional;
if required_cap > self.cap {
// Preallocate more space to reduce disk fragments. Neither too big nor too small.
let new_cap = ((required_cap + 0x40_0000) & !0x3f_ffff)
.min(self.cap * 4)
.max(required_cap);
// Always align to 4KB
let new_cap = (new_cap + 0x1000) & !0xfff;
let size = new_cap * size_of::<T>();
self.file.set_len(size as u64).expect("disk full");
self.mmap = unsafe { MmapOptions::new().len(size).map_mut(&self.file) }.expect("mmap");
self.cap = new_cap;
}
}
pub fn sync(&self) -> Result<()> { Ok(self.mmap.flush()?) }
}
impl<T> Deref for MmapVec<T> {
type Target = [T];
#[inline]
fn deref(&self) -> &[T] {
unsafe { slice::from_raw_parts(self.mmap.as_ptr() as *const T, self.len) }
}
}
impl<T> DerefMut for MmapVec<T> {
#[inline]
fn deref_mut(&mut self) -> &mut [T] {
unsafe { slice::from_raw_parts_mut(self.mmap.as_mut_ptr() as *mut T, self.len) }
}
}
impl<T> Drop for MmapVec<T> {
fn drop(&mut self) {
if self.cap != self.len {
// Truncate the file to actual size
let size = self.len * size_of::<T>();
self.file.set_len(size as u64).expect("truncate failed");
}
}
}
// Mark MmapVec as supporting Index/IndexMut interface
macro_rules! impl_index {
($I: ty, $T: tt, $O: tt) => {
impl<$T: Copy> Index<$I> for MmapVec<T> {
type Output = $O;
#[inline]
fn index(&self, index: $I) -> &$O { self.deref().index(index) }
}
impl<$T: Copy> IndexMut<$I> for MmapVec<T> {
#[inline]
fn index_mut(&mut self, index: $I) -> &mut $O { self.deref_mut().index_mut(index) }
}
}
}
impl_index!(usize, T, T);
impl_index!(Range<usize>, T, [T]);
impl_index!(RangeFrom<usize>, T, [T]);
impl_index!(RangeTo<usize>, T, [T]);
impl_index!(RangeFull, T, [T]);
#[cfg(test)]
mod tests {
use super::*;
use std::fmt::Debug;
use tempdir::TempDir;
fn check_with_vec<T: Copy + Eq + Default + Debug>(v: &Vec<T>) -> Result<()> {
let tempdir = TempDir::new("mvec")?;
let path = tempdir.path().join("mvec");
{
let mut m: MmapVec<T> = MmapVec::from_path(&path)?;
assert_eq!(m.len(), 0);
assert_ne!(m.cap(), 0);
m.extend_from_slice(&v[..]);
assert_eq!(m.len(), v.len());
assert!(m.cap() >= v.len());
assert_eq!(m[..], v[..]);
}
{
// Reload the file
let m: MmapVec<T> = MmapVec::<T>::from_path(&path)?;
assert_eq!(m[..], v[..]);
}
Ok(())
}
#[test]
fn check_large_buffer() {
assert!(check_with_vec(&vec![0x12345678abcdef01u64; 10000]).is_ok());
}
#[test]
fn check_resize() {
let tempdir = TempDir::new("mvec").unwrap();
let path = tempdir.path().join("resize");
let mut v = Vec::<u64>::new(); // reference
{
let mut m: MmapVec<u64> = MmapVec::from_path(path).unwrap();
for &(size, default) in [(10, 101), (100, 201), (1000, 301), (500, 401)].iter() {
m.resize(size, default);
v.resize(size, default);
assert_eq!(m[..], v[..]);
}
}
assert!(check_with_vec(&vec![0x12345678abcdef01u64; 10000]).is_ok());
}
quickcheck! {
fn test_compare_with_vec_i8(v: Vec<i8>) -> bool {
check_with_vec(&v).is_ok()
}
fn test_compare_with_vec_u32(v: Vec<u32>) -> bool {
check_with_vec(&v).is_ok()
}
fn test_compare_with_vec_i64(v: Vec<i64>) -> bool {
check_with_vec(&v).is_ok()
}
}
}