1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486
/*
* Copyright (c) 2019 Erik Nordstrøm <erik@nordstroem.no>
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
//!
//! # persistence – mutable resizable arrays built on top of mmap
//!
//! This Rust library provides [`MmapedVec`](MmapedVec); a resizable, mutable array type
//! implemented on top of [`mmap()`](https://pubs.opengroup.org/onlinepubs/7908799/xsh/mmap.html),
//! providing a [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html)-like data structure
//! with persistence to disk built into it.
//!
//! [`MmapedVec`](MmapedVec) is aimed at developers who wish to write software utilizing
//! [data-oriented design](https://en.wikipedia.org/wiki/Data-oriented_design)
//! techniques in run-time environments where all of the following hold true:
//!
//! 1. You have determined that a `Vec`-like data structure is appropriate for some
//! or all of your data, and
//! 2. You require that the data in question be persisted to disk, and
//! 3. You require that the data in question be synced to disk at certain times
//! or intervals, after said data has been mutated (added to, deleted from, or altered),
//! such that abnormal termination of your program (e.g. program crash, loss of power, etc.)
//! incurs minimal loss of data, and
//! 4. You are confident that all processes which rely on the data on disk honor the
//! advisory locks that we apply to them, so that the integrity of the data is
//! ensured, and
//! 5. You desire, or at least are fine with, having the on-disk representation of your data
//! be the same as that which it has in memory, and understand that this means that the files
//! are tied to the CPU architecture of the host that they were saved to disk on. If you need
//! to migrate your data to another computer with a different CPU architecture in the future,
//! you convert it then, rather than serializing and deserializing your data between some
//! other format and the in-memory representation all of the time.
//!
//! ## Advisory locks
//!
//! This library makes use of BSD `flock()` advisory locks on Unix platforms (Linux, macOS,
//! FreeBSD, etc).
//!
//! Provided that your software runs in an environment where any process that attempts to open
//! the files you are persisting your data to honor the advisory locks, everything will be
//! fine and dandy :)
//!
//! ## Motivation
//!
//! Data persistence is achievable by many different means. No one solution fits all
//! (and this library is no exception from that).
//!
//! Some of the ways in which data persistence can be achieved include:
//!
//! - Relying on a relational database such as [PostgreSQL](https://www.postgresql.org).
//! - Making use of the [Serde](https://serde.rs) framework for serializing and deserializing
//! Rust data structures, and handle writing to and reading from disk yourself.
//!
//! But, in software architecture situations where you choose to apply the data-oriented design
//! paradigm to your problem, you may find that you end up with some big arrays of data where
//! you've ordered the elements of each array in such a way as to be optimized for
//! [CPU caches](https://en.wikipedia.org/wiki/CPU_cache) in terms of
//! [spatial locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference#Types_of_locality).
//!
//! **When that is the case** – when you have those kinds of arrays, and when you want to persist
//! the data in those arrays in the manner we talked about
//! [at the beginning of this document](#persistence--mutable-resizable-arrays-built-on-top-of-mmap),
//! `mmap()`'ing those arrays to files on disk begins to look *pretty* alluring,
//! doesn't it? And there you have it, that was the motivation for writing this library.
//!
//! ## What this library is, and what it is not
//!
//! This library helps you out when you have arrays of data that are being mutated at run-time,
//! and you need to sync the data to disk for persistence at certain points or intervals in time.
//! It does so by making use of `mmap()` (through [the `memmap` crate](https://crates.io/crates/memmap))
//! with a little bit of locking and data validation sprinkled on top.
//!
//! What this library is **not** is, *something that "gives you" data-oriented design*. Indeed,
//! there can be no such thing;
//!
//! <blockquote>
//! A big misunderstanding for many new to the data-oriented design paradigm, a concept brought
//! over from abstraction based development, is that we can design a static library or set of
//! templates to provide generic solutions to everything presented in this book as a
//! data-oriented solution. Much like with domain driven design, data-oriented design is product
//! and work-flow specific. You learn how to do data-oriented design, not how to add it to your
//! project. The fundamental truth is that data, though it can be generic by type,
//! is not generic in how it is used.
//!
//! <footer>
//! — <cite>
//! Richard Fabian,
//! <a href=http://www.dataorienteddesign.com/dodbook/node2.html#SECTION00240000000000000000>Data-Oriented Design. Chapter 1, sub-section "Data can change".</a>
//! </cite>
//! </footer>
//! </blockquote>
//!
//! ## Caveats or, some things to keep in mind
//!
//! TODO: Write about how to use the library correctly.
//!
//! ## READY? LET'S GO!
//!
//! Add [the persistence crate](https://crates.io/crates/persistence) to the `[dependencies]`
//! section of [your `Cargo.toml` manifest](https://doc.rust-lang.org/cargo/reference/manifest.html)
//! and start using this library in your projects.
//!
//! ## Star me on GitHub
//!
//! Don't forget to star [persistence on GitHub](https://github.com/ctsrc/persistence)
//! if you find this library interesting or useful.
//!
use std::marker::PhantomData;
use std::{io, slice};
use std::fs::{OpenOptions, File};
use std::path::Path;
use std::mem;
use std::io::{Read, Write};
use memmap::MmapMut;
use fs2::FileExt;
/// Bumped to match crate version when changes are made to format itself.
const PERSISTENCE_FORMAT_VERSION: [u8; 3] = [0, 0, 5];
#[repr(C, packed)]
struct FileHeader<T>
{
magic_bytes: [u8; 8],
endianness: u16,
persistence_format_version: [u8; 3],
data_contained_version: [u8; 3],
default_data: T,
number_of_padding_bytes_after_header: u16,
}
pub struct MmapedVec<T>
{
file: File,
mm: MmapMut,
_marker: PhantomData<T>,
}
impl<T: Sized + Default> MmapedVec<T>
{
pub fn try_new (path: &Path, magic_bytes: [u8; 8], data_contained_version: [u8; 3]) -> io::Result<Self>
{
// TODO: If the fs2 try_lock_exclusive simulated flock() on Solaris does not behave as it should,
// then a preflight check might be needed, or we might blacklist target_os = "solaris".
// It remains to be determined whether or not that is the case.
// If it does misbehave, and we decide to blacklist, then we must be vigilant about
// future changes in fs2, such as if the simulated flock() is enabled for more target OSes.
let mut file = OpenOptions::new().read(true).write(true).create(true).open(path)?;
// TODO: Require that file has permissions 0600. See comments on https://stackoverflow.com/a/34935188
/*
* NOTE: The fs2 library is cross-platform beyond just the platforms that we support.
* We use this library not because we want to try and support all of those,
* but because it covers what we want to do and saves us some typing and thinking.
* See the section about advisory locking the doc comments of this file.
*/
file.try_lock_exclusive()?;
let fhs = mem::size_of::<FileHeader<T>>();
let number_of_padding_bytes_after_header = match fhs % 4096
{
0 => 0,
_ => (4096 - fhs % 4096) as u16,
};
let fh = FileHeader
{
magic_bytes,
endianness: 0x1234,
persistence_format_version: PERSISTENCE_FORMAT_VERSION,
data_contained_version,
default_data: T::default(),
number_of_padding_bytes_after_header,
};
let flen = file.metadata().unwrap().len();
let len_fh_and_padding = fhs as u64 + number_of_padding_bytes_after_header as u64;
if flen == 0
{
let buf = unsafe
{
slice::from_raw_parts(
&fh as *const FileHeader<T> as *const u8,
mem::size_of::<FileHeader<T>>())
};
file.write(buf)?;
file.set_len(len_fh_and_padding)?;
}
else if flen < fhs as u64
{
return Err(io::Error::new(io::ErrorKind::InvalidData,
format!("File `{:?}` has non-zero size ({} bytes), but it is shorter than \
the expected header size ({} bytes).", path, flen, fhs)));
}
else
{
let mut fh_handle = file.try_clone()?.take(fhs as u64);
let mut fh_buf = vec![0u8; fhs];
fh_handle.read(fh_buf.as_mut_slice()).unwrap();
let fh_file = unsafe { std::ptr::read(fh_buf.as_ptr() as *const FileHeader<T>) };
if fh_file.magic_bytes != fh.magic_bytes
{
return Err(io::Error::new(io::ErrorKind::InvalidData,
format!("File `{:?}`: Magic bytes mismatch.", path)));
}
if fh_file.endianness != fh.endianness
{
if (fh_file.endianness << 8 | fh_file.endianness >> 8) != fh.endianness
{
return Err(io::Error::new(io::ErrorKind::InvalidData,
format!("File `{:?}`: Endianness-marker invalid.", path)));
}
else
{
return Err(io::Error::new(io::ErrorKind::InvalidData,
format!("File `{:?}`: Wrong endianness.", path)));
}
}
// TODO: Validate remaining fields
}
if flen > 0 && flen < len_fh_and_padding
{
// TODO: Error
}
if flen > len_fh_and_padding && ((flen - len_fh_and_padding) % mem::size_of::<T>() as u64 != 0)
{
return Err(io::Error::new(io::ErrorKind::InvalidData,
format!("File `{:?}` has non-zero size, but file size minus header size and padding \
bytes is not an integer multiple of the size of the data type that the file supposedly \
contains. This indicates that the file might be corrupt, incorrectly versioned or \
malformed.", path)));
}
let mut mm = unsafe { MmapMut::map_mut(&file)? };
Ok(Self
{
file,
mm,
_marker: PhantomData,
})
}
}
#[cfg(test)]
mod tests
{
use super::*;
use std::error::Error;
use std::path::PathBuf;
use std::process::{Command, ExitStatus, Stdio};
use std::io::{Seek, SeekFrom};
use tempfile::TempDir;
use memoffset::offset_of;
#[repr(C, packed)]
struct Example
{
hello: u8,
world: u8,
}
impl Default for Example
{
fn default () -> Self
{
Self
{
hello: 1,
world: 2,
}
}
}
const EXAMPLE_MAGIC_BYTES: [u8; 8] = [b'T', b'E', b'S', b'T', b'F', b'I', b'L', b'E'];
const EXAMPLE_CORRUPT_MAGIC_BYTES: [u8; 8] = [b'X', b'Y', b'Z', b'T', b'F', 0, 0, 0];
const EXAMPLE_DATA_CONTAINED_VERSION: [u8; 3] = [0, 1, 0];
// XXX: Type alias for use with offset_of!()
type ExampleFileHeader = FileHeader<Example>;
/// Helper function for tests.
fn tempdir_and_tempfile () -> io::Result<(TempDir, PathBuf)>
{
let dir = tempfile::tempdir()?;
let pathbuf = dir.path().join("file.bin");
Ok((dir, pathbuf))
}
/// Helper function for tests.
fn new_mmaped_vec_of_example_persisting_in_tempdir () -> io::Result<(TempDir, PathBuf, MmapedVec<Example>)>
{
let (dir, pathbuf) = tempdir_and_tempfile()?;
let mv = MmapedVec::try_new(pathbuf.as_path(),
EXAMPLE_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION)?;
Ok((dir, pathbuf, mv))
}
/// Helper function for tests.
fn python3_try_lock_exclusive (path: &Path) -> io::Result<ExitStatus>
{
// NOTE: Keep in mind that if the parent test fails, python3 might not be in your $PATH.
let mut child = Command::new("python3").arg("-").arg(path)
.stdin(Stdio::piped()).stdout(Stdio::inherit()).stderr(Stdio::inherit())
.spawn()?;
let child_stdin = child.stdin.as_mut().unwrap();
child_stdin.write_all(include_bytes!("../scripts/try_lock_exclusive.py"))?;
child.wait()
}
#[test]
pub fn test_create_mmaped_vec_onto_tempfile () -> Result<(), io::Error>
{
new_mmaped_vec_of_example_persisting_in_tempdir()?;
Ok(())
}
#[test]
pub fn test_file_is_locked_while_fd_is_held () -> Result<(), io::Error>
{
let (_dir, pathbuf, _mv) = new_mmaped_vec_of_example_persisting_in_tempdir()?;
assert_eq!(python3_try_lock_exclusive(pathbuf.as_path())?.code(), Some(35));
Ok(())
}
#[test]
pub fn test_existing_file_is_locked_while_fd_is_held () -> Result<(), io::Error>
{
// Create MmapedVec onto new tempfile. Header is written. Automatically close it by drop.
let (_dir, pathbuf, _) = new_mmaped_vec_of_example_persisting_in_tempdir()?;
// Create MmapedVec onto existing tempfile created above.
let _mv = MmapedVec::<Example>::try_new(pathbuf.as_path(),
EXAMPLE_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION)?;
assert_eq!(python3_try_lock_exclusive(pathbuf.as_path())?.code(), Some(35));
Ok(())
}
// TODO: Test opening multiple fds to the same file and unlocking one of them.
// TODO: Test locking and unlocking same file opened through real path and through
// symlink and see what happens.
#[test]
pub fn test_file_is_unlocked_after_drop () -> Result<(), io::Error>
{
let (_dir, pathbuf, _) = new_mmaped_vec_of_example_persisting_in_tempdir()?;
assert_eq!(python3_try_lock_exclusive(pathbuf.as_path())?.code(), Some(0));
Ok(())
}
#[test]
pub fn test_detect_header_corrupt_magic_bytes () -> Result<(), io::Error>
{
let (_dir, pathbuf) = tempdir_and_tempfile()?;
MmapedVec::<Example>::try_new(pathbuf.as_path(),
EXAMPLE_CORRUPT_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION)?;
let mv_err = MmapedVec::<Example>::try_new(pathbuf.as_path(),
EXAMPLE_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION).err().unwrap();
assert!(mv_err.description().ends_with("Magic bytes mismatch."));
Ok(())
}
#[test]
pub fn test_detect_file_corrupt_truncated_to_under_end_of_header () -> Result<(), io::Error>
{
let (_dir, pathbuf, _) = new_mmaped_vec_of_example_persisting_in_tempdir()?;
let file = OpenOptions::new().read(true).write(true).open(pathbuf.as_path())?;
let fhs = mem::size_of::<FileHeader<Example>>();
file.set_len((fhs - 1) as u64).unwrap();
let mv_err = MmapedVec::<Example>::try_new(pathbuf.as_path(),
EXAMPLE_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION).err().unwrap();
assert!(mv_err.description().contains("shorter than the expected header size"));
Ok(())
}
#[test]
pub fn test_detect_file_corrupt_body_not_integer_multiple_of_data_type () -> Result<(), io::Error>
{
let (_dir, pathbuf, _) = new_mmaped_vec_of_example_persisting_in_tempdir()?;
let file = OpenOptions::new().read(true).write(true).open(pathbuf.as_path())?;
let flen = file.metadata().unwrap().len();
file.set_len(flen + 1).unwrap();
let mv_err = MmapedVec::<Example>::try_new(pathbuf.as_path(),
EXAMPLE_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION).err().unwrap();
assert!(mv_err.description().contains("not an integer multiple of the size of the data type"));
Ok(())
}
#[test]
pub fn test_detect_endianness_marker_invalid () -> Result<(), io::Error>
{
let (_dir, pathbuf, _) = new_mmaped_vec_of_example_persisting_in_tempdir()?;
let mut file = OpenOptions::new().read(true).write(true).open(pathbuf.as_path())?;
let offs = SeekFrom::Start(offset_of!(ExampleFileHeader, endianness) as u64);
file.seek(offs).unwrap();
file.write(&[0u8, 0]).unwrap();
let mv_err = MmapedVec::<Example>::try_new(pathbuf.as_path(),
EXAMPLE_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION).err().unwrap();
assert!(mv_err.description().ends_with("Endianness-marker invalid."));
Ok(())
}
#[test]
pub fn test_detect_wrong_endianness () -> Result<(), io::Error>
{
let (_dir, pathbuf, _) = new_mmaped_vec_of_example_persisting_in_tempdir()?;
let mut file = OpenOptions::new().read(true).write(true).open(pathbuf.as_path())?;
let offs = SeekFrom::Start(offset_of!(ExampleFileHeader, endianness) as u64);
file.seek(offs).unwrap();
let mut buf = [0u8, 0];
file.read_exact(&mut buf).unwrap();
buf.reverse();
file.seek(offs).unwrap();
file.write(&buf).unwrap();
let mv_err = MmapedVec::<Example>::try_new(pathbuf.as_path(),
EXAMPLE_MAGIC_BYTES, EXAMPLE_DATA_CONTAINED_VERSION).err().unwrap();
assert!(mv_err.description().ends_with("Wrong endianness."));
Ok(())
}
}