/* Copyright 2018-2019 Mozilla Foundation
*
* Licensed under the Apache License (Version 2.0), or the MIT license,
* (the "Licenses") at your option. You may not use this file except in
* compliance with one of the Licenses. You may obtain copies of the
* Licenses at:
*
*
http://www.apache.org/licenses/LICENSE-2.0
*
http://opensource.org/licenses/MIT
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the Licenses is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the Licenses for the specific language governing permissions and
* limitations under the Licenses. */
//! This module provides a [`Handle`] type, which you can think of something
//! like a dynamically checked, type erased reference/pointer type. Depending on
//! the usage pattern a handle can behave as either a borrowed reference, or an
//! owned pointer.
//!
//! They can be losslessly converted [to](Handle::into_u64) and
//! [from](Handle::from_u64) a 64 bit integer, for ease of passing over the FFI
//! (and they implement [`IntoFfi`] using these primitives for this purpose).
//!
//! The benefit is primarially that they can detect common misuse patterns that
//! would otherwise be silent bugs, such as use-after-free, double-free, passing
//! a wrongly-typed pointer to a function, etc.
//!
//! Handles are provided when inserting an item into either a [`HandleMap`] or a
//! [`ConcurrentHandleMap`].
//!
//! # Comparison to types from other crates
//!
//! [`HandleMap`] is similar to types offered by other crates, such as
//! `slotmap`, or `slab`. However, it has a number of key differences which make
//! it better for our purposes as compared to the types in those crates:
//!
//! 1. Unlike `slab` (but like `slotmap`), we implement versioning, detecting
//! ABA problems, which allows us to detect use after free.
//! 2. Unlike `slotmap`, we don't have the `T: Copy` restriction.
//! 3. Unlike either, we can detect when you use a Key in a map that did not
//! allocate the key. This is true even when the map is from a `.so` file
//! compiled separately.
//! 3. Our implementation of doesn't use any `unsafe` (at the time of this
//! writing).
//!
//! However, it comes with the following drawbacks:
//!
//! 1. `slotmap` holds its version information in a `u32`, and so it takes
//! 2<sup>31</sup> colliding insertions and deletions before it could
//! potentially fail to detect an ABA issue, wheras we use a `u16`, and are
//! limited to 2<sup>15</sup>.
//! 2. Similarly, we can only hold 2<sup>16</sup> items at once, unlike
//! `slotmap`'s 2<sup>32</sup>. (Considering these items are typically things
//! like database handles, this is probably plenty).
//! 3. Our implementation is slower, and uses slightly more memory than
//! `slotmap` (which is in part due to the lack of `unsafe` mentioned above)
//!
//! The first two issues seem exceptionally unlikely, even for extremely
//! long-lived `HandleMap`, and we're still memory safe even if they occur (we
//! just might fail to notice a bug). The third issue also seems unimportant for
//! our use case.
use crate::error::{ErrorCode, ExternError};
use crate::into_ffi::IntoFfi;
use std::error::Error as StdError;
use std::fmt;
use std::ops;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::{Mutex, RwLock};
/// `HandleMap` is a collection type which can hold any type of value, and
/// offers a stable handle which can be used to retrieve it on insertion. These
/// handles offer methods for converting [to](Handle::into_u64) and
/// [from](Handle::from_u64) 64 bit integers, meaning they're very easy to pass
/// over the FFI (they also implement [`IntoFfi`] for the same purpose).
///
/// See the [module level docs](index.html) for more information.
///
/// Note: In FFI code, most usage of `HandleMap` will be done through the
/// [`ConcurrentHandleMap`] type, which is a thin wrapper around a
/// `RwLock<HandleMap<Mutex<T>>>`.
#[derive(Debug, Clone)]
pub struct HandleMap<T> {
// The value of `map_id` in each `Handle`.
id: u16,
// Index to the start of the free list. Always points to a free item --
// we never allow our free list to become empty.
first_free: u16,
// The number of entries with `data.is_some()`. This is never equal to
// `entries.len()`, we always grow before that point to ensure we always have
// a valid `first_free` index to add entries onto. This is our `len`.
num_entries: usize,
// The actual data. Note: entries.len() is our 'capacity'.
entries: Vec<Entry<T>>,
}
#[derive(Debug, Clone)]
struct Entry<T> {
// initially 1, incremented on insertion and removal. Thus,
// if version is even, state should always be EntryState::Active.
version: u16,
state: EntryState<T>,
}
#[derive(Debug, Clone)]
enum EntryState<T> {
// Not part of the free list
Active(T),
// The u16 is the next index in the free list.
InFreeList(u16),
// Part of the free list, but the sentinel.
EndOfFreeList,
}
impl<T> EntryState<T> {
#[cfg(any(debug_assertions, test))]
fn is_end_of_list(&self) -> bool {
match self {
EntryState::EndOfFreeList => true,
_ => false,
}
}
#[inline]
fn is_occupied(&self) -> bool {
self.get_item().is_some()
}
#[inline]
fn get_item(&self) -> Option<&T> {
match self {
EntryState::Active(v) => Some(v),
_ => None,
}
}
#[inline]
fn get_item_mut(&mut self) -> Option<&mut T> {
match self {
EntryState::Active(v) => Some(v),
_ => None,
}
}
}
// Small helper to check our casts.
#[inline]
fn to_u16(v: usize) -> u16 {
use std::u16::MAX as U16_MAX;
// Shouldn't ever happen.
assert!(v <= (U16_MAX as usize), "Bug: Doesn't fit in u16: {}", v);
v as u16
}
/// The maximum capacity of a [`HandleMap`]. Attempting to instantiate one with
/// a larger capacity will cause a panic.
///
/// Note: This could go as high as `(1 << 16) - 2`, but doing is seems more
/// error prone. For the sake of paranoia, we limit it to this size, which is
/// already quite a bit larger than it seems like we're likely to ever need.
pub const MAX_CAPACITY: usize = (1 << 15) - 1;
// Never having to worry about capacity == 0 simplifies the code at the cost of
// worse memory usage. It doesn't seem like there's any reason to make this
// public.
const MIN_CAPACITY: usize = 4;
/// An error representing the ways a `Handle` may be invalid.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub enum HandleError {
/// Identical to invalid handle, but has a slightly more helpful
/// message for the most common case 0.
NullHandle,
/// Returned from [`Handle::from_u64`] if [`Handle::is_valid`] fails.
InvalidHandle,
/// Returned from get/get_mut/delete if the handle is stale (this indicates
/// something equivalent to a use-after-free / double-free, etc).
StaleVersion,
/// Returned if the handle index references an index past the end of the
/// HandleMap.
IndexPastEnd,
/// The handle has a map_id for a different map than the one it was
/// attempted to be used with.
WrongMap,
}
impl StdError for HandleError {}
impl fmt::Display for HandleError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
use HandleError::*;
match self {
NullHandle => {
f.write_str("Tried to use a null handle (this object has probably been closed)")
}
InvalidHandle => f.write_str("u64 could not encode a valid Handle"),
StaleVersion => f.write_str("Handle has stale version number"),
IndexPastEnd => f.write_str("Handle references a index past the end of this HandleMap"),
WrongMap => f.write_str("Handle is from a different map"),
}
}
}
impl From<HandleError> for ExternError {
fn from(e: HandleError) -> Self {
ExternError::new_error(ErrorCode::INVALID_HANDLE, e.to_string())
}
}
impl<T> HandleMap<T> {
/// Create a new `HandleMap` with the default capacity.
pub fn new() -> Self {
Self::new_with_capacity(MIN_CAPACITY)
}
/// Allocate a new `HandleMap`. Note that the actual capacity may be larger
/// than the requested value.
///
/// Panics if `request` is greater than [`handle_map::MAX_CAPACITY`](MAX_CAPACITY)
pub fn new_with_capacity(request: usize) -> Self {
assert!(
request <= MAX_CAPACITY,
"HandleMap capacity is limited to {} (request was {})",
MAX_CAPACITY,
request
);
let capacity = request.max(MIN_CAPACITY);
let id = next_handle_map_id();
let mut entries = Vec::with_capacity(capacity);
// Initialize each entry with version 1, and as a member of the free list
for i in 0..(capacity - 1) {
entries.push(Entry {
version: 1,
state: EntryState::InFreeList(to_u16(i + 1)),
});
}
// And the final entry is at the end of the free list
// (but still has version 1).
entries.push(Entry {
version: 1,
state: EntryState::EndOfFreeList,
});
Self {
id,
first_free: 0,
num_entries: 0,
entries,
}
}
/// Get the number of entries in the `HandleMap`.
#[inline]
pub fn len(&self) -> usize {
self.num_entries
}
/// Returns true if the HandleMap is empty.
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Returns the number of slots allocated in the handle map.
#[inline]
pub fn capacity(&self) -> usize {
// It's not a bug that this isn't entries.capacity() -- We're returning
// how many slots exist, not something about the backing memory allocation
self.entries.len()
}
fn ensure_capacity(&mut self, cap_at_least: usize) {
assert_ne!(self.len(), self.capacity(), "Bug: should have grown by now");
assert!(cap_at_least <= MAX_CAPACITY, "HandleMap overfilled");
if self.capacity() > cap_at_least {
return;
}
let mut next_cap = self.capacity();
while next_cap <= cap_at_least {
next_cap *= 2;
}
next_cap = next_cap.min(MAX_CAPACITY);
let need_extra = next_cap.saturating_sub(self.entries.capacity());
self.entries.reserve(need_extra);
assert!(
!self.entries[self.first_free as usize].state.is_occupied(),
"Bug: HandleMap.first_free points at occupied index"
);
// Insert new entries at the front of our list.
while self.entries.len() < next_cap - 1 {
// This is a little wasteful but whatever. Add each new entry to the
// front of the free list one at a time.
self.entries.push(Entry {
version: 1,
state: EntryState::InFreeList(self.first_free),
});
self.first_free = to_u16(self.entries.len() - 1);
}
self.debug_check_valid();
}
#[inline]
fn debug_check_valid(&self) {
// Run the expensive validity check in tests and in debug builds.
#[cfg(any(debug_assertions, test))]
{
self.assert_valid();
}
}
#[cfg(any(debug_assertions, test))]
fn assert_valid(&self) {
assert_ne!(self.len(), self.capacity());
assert!(self.capacity() <= MAX_CAPACITY, "Entries too large");
// Validate that our free list is correct.
let number_of_ends = self
.entries
.iter()
.filter(|e| e.state.is_end_of_list())
.count();
assert_eq!(
number_of_ends, 1,
"More than one entry think's it's the end of the list, or no entries do"
);
// Check that the free list hits every unoccupied item.
// The tuple is: `(should_be_in_free_list, is_in_free_list)`.
let mut free_indices = vec![(false, false); self.capacity()];
for (i, e) in self.entries.iter().enumerate() {
if !e.state.is_occupied() {
free_indices[i].0 = true;
}
}
let mut next = self.first_free;
loop {
let ni = next as usize;
assert!(
ni <= free_indices.len(),
"Free list contains out of bounds index!"
);
assert!(
free_indices[ni].0,
"Free list has an index that shouldn't be free! {}",
ni
);
assert!(
!free_indices[ni].1,
"Free list hit an index ({}) more than once! Cycle detected!",
ni
);
free_indices[ni].1 = true;
match &self.entries[ni].state {
EntryState::InFreeList(next_index) => next = *next_index,
EntryState::EndOfFreeList => break,
// Hitting `Active` here is probably not possible because of the checks above, but who knows.
EntryState::Active(..) => unreachable!("Bug: Active item in free list at {}", next),
}
}
let mut occupied_count = 0;
for (i, &(should_be_free, is_free)) in free_indices.iter().enumerate() {
assert_eq!(
should_be_free, is_free,
"Free list missed item, or contains an item it shouldn't: {}",
i
);
if !should_be_free {
occupied_count += 1;
}
}
assert_eq!(
self.num_entries, occupied_count,
"num_entries doesn't reflect the actual number of entries"
);
}
/// Insert an item into the map, and return a handle to it.
pub fn insert(&mut self, v: T) -> Handle {
let need_cap = self.len() + 1;
self.ensure_capacity(need_cap);
let index = self.first_free;
let result = {
// Scoped mutable borrow of entry.
let entry = &mut self.entries[index as usize];
let new_first_free = match entry.state {
EntryState::InFreeList(i) => i,
_ => panic!("Bug: next_index pointed at non-free list entry (or end of list)"),
};
entry.version += 1;
if entry.version == 0 {
entry.version += 2;
}
entry.state = EntryState::Active(v);
self.first_free = new_first_free;
self.num_entries += 1;
Handle {
map_id: self.id,
version: entry.version,
index,
}
};
self.debug_check_valid();
result
}
// Helper to contain the handle validation boilerplate. Returns `h.index as usize`.
fn check_handle(&self, h: Handle) -> Result<usize, HandleError> {
if h.map_id != self.id {
log::info!(
"HandleMap access with handle having wrong map id: {:?} (our map id is {})",
h,
self.id
);
return Err(HandleError::WrongMap);
}
let index = h.index as usize;
if index >= self.entries.len() {
log::info!("HandleMap accessed with handle past end of map: {:?}", h);
return Err(HandleError::IndexPastEnd);
}
if self.entries[index].version != h.version {
log::info!(
"HandleMap accessed with handle with wrong version {:?} (entry version is {})",
h,
self.entries[index].version
);
return Err(HandleError::StaleVersion);
}
// At this point, we know the handle version matches the entry version,
// but if someone created a specially invalid handle, they could have
// its version match the version they expect an unoccupied index to
// have.
//
// We don't use any unsafe, so the worse thing that can happen here is
// that we get confused and panic, but still that's not great, so we
// check for this explicitly.
//
// Note that `active` versions are always even, as they start at 1, and
// are incremented on both insertion and deletion.
//
// Anyway, this is just for sanity checking, we already check this in
// practice when we convert `u64`s into `Handle`s, which is the only
// way we ever use these in the real world.
if (h.version % 2) != 0 {
log::info!(
"HandleMap given handle with matching but illegal version: {:?}",
h,
);
return Err(HandleError::StaleVersion);
}
Ok(index)
}
/// Delete an item from the HandleMap.
pub fn delete(&mut self, h: Handle) -> Result<(), HandleError> {
self.remove(h).map(drop)
}
/// Remove an item from the HandleMap, returning the old value.
pub fn remove(&mut self, h: Handle) -> Result<T, HandleError> {
let index = self.check_handle(h)?;
let prev = {
// Scoped mutable borrow of entry.
let entry = &mut self.entries[index];
entry.version += 1;
let index = h.index;
let last_state =
std::mem::replace(&mut entry.state, EntryState::InFreeList(self.first_free));
self.num_entries -= 1;
self.first_free = index;
if let EntryState::Active(value) = last_state {
value
} else {
// This indicates either a bug in HandleMap or memory
// corruption. Abandon all hope.
unreachable!(
"Handle {:?} passed validation but references unoccupied entry",
h
);
}
};
self.debug_check_valid();
Ok(prev)
}
/// Get a reference to the item referenced by the handle, or return a
/// [`HandleError`] describing the problem.
pub fn get(&self, h: Handle) -> Result<&T, HandleError> {
let idx = self.check_handle(h)?;
let entry = &self.entries[idx];
// This should be caught by check_handle above, but we avoid panicking
// because we'd rather not poison any locks we don't have to poison
let item = entry
.state
.get_item()
.ok_or_else(|| HandleError::InvalidHandle)?;
Ok(item)
}
/// Get a mut reference to the item referenced by the handle, or return a
/// [`HandleError`] describing the problem.
pub fn get_mut(&mut self, h: Handle) -> Result<&mut T, HandleError> {
let idx = self.check_handle(h)?;
let entry = &mut self.entries[idx];
// This should be caught by check_handle above, but we avoid panicking
// because we'd rather not poison any locks we don't have to poison
let item = entry
.state
.get_item_mut()
.ok_or_else(|| HandleError::InvalidHandle)?;
Ok(item)
}
}
impl<T> Default for HandleMap<T> {
#[inline]
fn default() -> Self {
HandleMap::new()
}
}
impl<T> ops::Index<Handle> for HandleMap<T> {
type Output = T;
#[inline]
fn index(&self, h: Handle) -> &T {
self.get(h)
.expect("Indexed into HandleMap with invalid handle!")
}
}
// We don't implement IndexMut intentionally (implementing ops::Index is
// dubious enough)
/// A Handle we allow to be returned over the FFI by implementing [`IntoFfi`].
/// This type is intentionally not `#[repr(C)]`, and getting the data out of the
/// FFI is done using `Handle::from_u64`, or it's implemetation of `From<u64>`.
///
/// It consists of, at a minimum:
///
/// - A "map id" (used to ensure you're using it with the correct map)
/// - a "version" (incremented when the value in the index changes, used to
/// detect multiple frees, use after free, and ABA and ABA)
/// - and a field indicating which index it goes into.
///
/// In practice, it may also contain extra information to help detect other
/// errors (currently it stores a "magic value" used to detect invalid
/// [`Handle`]s).
///
/// These fields may change but the following guarantees are made about the
/// internal representation:
///
/// - This will always be representable in 64 bits.
/// - The bits, when interpreted as a signed 64 bit integer, will be positive
/// (that is to say, it will *actually* be representable in 63 bits, since
/// this makes the most significant bit unavailable for the purposes of
/// encoding). This guarantee makes things slightly less dubious when passing
/// things to Java, gives us some extra validation ability, etc.
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Handle {
map_id: u16,
version: u16,
index: u16,
}
// We stuff this into the top 16 bits of the handle when u16 encoded to detect
// various sorts of weirdness. It's the letters 'A' and 'S' as ASCII, but the
// only important thing about it is that the most significant bit be unset.
const HANDLE_MAGIC: u16 = 0x4153_u16;
impl Handle {
/// Convert a `Handle` to a `u64`. You can also use `Into::into` directly.
/// Most uses of this will be automatic due to our [`IntoFfi`] implementation.
#[inline]
pub fn into_u64(self) -> u64 {
let map_id = u64::from(self.map_id);
let version = u64::from(self.version);
let index = u64::from(self.index);
// SOMEDAY: we could also use this as a sort of CRC if we were really paranoid.
// e.g. `magic = combine_to_u16(map_id, version, index)`.
let magic = u64::from(HANDLE_MAGIC);
(magic << 48) | (map_id << 32) | (index << 16) | version
}
/// Convert a `u64` to a `Handle`. Inverse of `into_u64`. We also implement
/// `From::from` (which will panic instead of returning Err).
///
/// Returns [`HandleError::InvalidHandle`](HandleError) if the bits cannot
/// possibly represent a valid handle.
pub fn from_u64(v: u64) -> Result<Self, HandleError> {
if !Handle::is_valid(v) {
log::warn!("Illegal handle! {:x}", v);
if v == 0 {
Err(HandleError::NullHandle)
} else {
Err(HandleError::InvalidHandle)
}
} else {
let map_id = (v >> 32) as u16;
let index = (v >> 16) as u16;
let version = v as u16;
Ok(Self {
map_id,
version,
index,
})
}
}
/// Returns whether or not `v` makes a bit pattern that could represent an
/// encoded [`Handle`].
#[inline]
pub fn is_valid(v: u64) -> bool {
(v >> 48) == u64::from(HANDLE_MAGIC) &&
// The "bottom" field is the version. We increment it both when
// inserting and removing, and they're all initially 1. So, all valid
// handles that we returned should have an even version.
((v & 1) == 0)
}
}
impl From<u64> for Handle {
fn from(u: u64) -> Self {
Handle::from_u64(u).expect("Illegal handle!")
}
}
impl From<Handle> for u64 {
#[inline]
fn from(h: Handle) -> u64 {
h.into_u64()
}
}
unsafe impl IntoFfi for Handle {
type Value = u64;
// Note: intentionally does not encode a valid handle for any map.
#[inline]
fn ffi_default() -> u64 {
0u64
}
#[inline]
fn into_ffi_value(self) -> u64 {
self.into_u64()
}
}
/// `ConcurrentHandleMap` is a relatively thin wrapper around
/// `RwLock<HandleMap<Mutex<T>>>`. Due to the nested locking, it's not possible
/// to implement the same API as [`HandleMap`], however it does implement an API
/// that offers equivalent functionality, as well as several functions that
/// greatly simplify FFI usage (see example below).
///
/// See the [module level documentation](index.html) for more info.
///
/// # Example
///
/// ```rust,no_run
/// # #[macro_use] extern crate lazy_static;
/// # extern crate ffi_support;
/// # use ffi_support::*;
/// # use std::sync::*;
///
/// // Somewhere...
/// struct Thing { value: f64 }
///
/// lazy_static! {
/// static ref ITEMS: ConcurrentHandleMap<Thing> = ConcurrentHandleMap::new();
/// }
///
/// #[no_mangle]
/// pub extern "C" fn mylib_new_thing(value: f64, err: &mut ExternError) -> u64 {
/// // Most uses will be `ITEMS.insert_with_result`. Note that this already
/// // calls `call_with_output` (or `call_with_result` if this were
/// // `insert_with_result`) for you.
/// ITEMS.insert_with_output(err, || Thing { value })
/// }
///
/// #[no_mangle]
/// pub extern "C" fn mylib_thing_value(h: u64, err: &mut ExternError) -> f64 {
/// // Or `ITEMS.call_with_result` for the fallible functions.
/// ITEMS.call_with_output(err, h, |thing| thing.value)
/// }
///
/// #[no_mangle]
/// pub extern "C" fn mylib_thing_set_value(h: u64, new_value: f64, err: &mut ExternError)
{
/// ITEMS.call_with_output_mut(err, h, |thing| {
/// thing.value = new_value;
/// })
/// }
///
/// // Note: defines the following function:
/// // pub extern "C" fn mylib_destroy_thing(h: u64, err: &mut ExternError)
/// define_handle_map_deleter!(ITEMS, mylib_destroy_thing);
/// ```
pub struct ConcurrentHandleMap<T> {
/// The underlying map. Public so that more advanced use-cases
/// may use it as they please.
pub map: RwLock<HandleMap<Mutex<T>>>,
}
impl<T> ConcurrentHandleMap<T> {
/// Construct a new `ConcurrentHandleMap`.
pub fn new() -> Self {
Self {
map: RwLock::new(HandleMap::new()),
}
}
/// Get the number of entries in the `ConcurrentHandleMap`.
///
/// This takes the map's `read` lock.
#[inline]
pub fn len(&self) -> usize {
let map = self.map.read().unwrap();
map.len()
}
/// Returns true if the `ConcurrentHandleMap` is empty.
///
/// This takes the map's `read` lock.
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Insert an item into the map, returning the newly allocated handle to the
/// item.
///
/// # Locking
///
/// Note that this requires taking the map's write lock, and so it will
/// block until all other threads have finished any read/write operations.
pub fn insert(&self, v: T) -> Handle {
// Fails if the lock is poisoned. Not clear what we should do here... We
// could always insert anyway (by matching on LockResult), but that
// seems... really quite dubious.
let mut map = self.map.write().unwrap();
map.insert(Mutex::new(v))
}
/// Remove an item from the map.
///
/// # Locking
///
/// Note that this requires taking the map's write lock, and so it will
/// block until all other threads have finished any read/write operations.
pub fn delete(&self, h: Handle) -> Result<(), HandleError> {
// We use `remove` and not delete (and use the inner block) to ensure
// that if `v`'s destructor panics, we aren't holding the write lock
// when it happens, so that the map itself doesn't get poisoned.
let v = {
let mut map = self.map.write().unwrap();
map.remove(h)
};
v.map(drop)
}
/// Convenient wrapper for `delete` which takes a `u64` that it will
/// convert to a handle.
///
/// The main benefit (besides convenience) of this over the version
/// that takes a [`Handle`] is that it allows handling handle-related errors
/// in one place.
pub fn delete_u64(&self, h: u64) -> Result<(), HandleError> {
self.delete(Handle::from_u64(h)?)
}
/// Remove an item from the map, returning either the item,
/// or None if its guard mutex got poisoned at some point.
///
/// # Locking
///
/// Note that this requires taking the map's write lock, and so it will
/// block until all other threads have finished any read/write operations.
pub fn remove(&self, h: Handle) -> Result<Option<T>, HandleError> {
let mut map = self.map.write().unwrap();
let mutex = map.remove(h)?;
Ok(mutex.into_inner().ok())
}
/// Convenient wrapper for `remove` which takes a `u64` that it will
/// convert to a handle.
///
/// The main benefit (besides convenience) of this over the version
/// that takes a [`Handle`] is that it allows handling handle-related errors
/// in one place.
pub fn remove_u64(&self, h: u64) -> Result<Option<T>, HandleError> {
self.remove(Handle::from_u64(h)?)
}
/// Call `callback` with a non-mutable reference to the item from the map,
/// after acquiring the necessary locks.
///
/// # Locking
///
/// Note that this requires taking both:
///
/// - The map's read lock, and so it will block until all other threads have
/// finished any write operations.
/// - The mutex on the slot the handle is mapped to.
///
/// And so it will block if there are ongoing write operations, or if
/// another thread is reading from the same handle.
///
/// # Panics
///
/// This will panic if a previous `get()` or `get_mut()` call has panicked
/// inside it's callback. The solution to this
///
/// (It may also panic if the handle map detects internal state corruption,
/// however this should not happen except for bugs in the handle map code).
pub fn get<F, E, R>(&self, h: Handle, callback: F) -> Result<R, E>
where
F: FnOnce(&T) -> Result<R, E>,
E: From<HandleError>,
{
self.get_mut(h, |v| callback(v))
}
/// Call `callback` with a mutable reference to the item from the map, after
/// acquiring the necessary locks.
///
/// # Locking
///
/// Note that this requires taking both:
///
/// - The map's read lock, and so it will block until all other threads have
/// finished any write operations.
/// - The mutex on the slot the handle is mapped to.
///
/// And so it will block if there are ongoing write operations, or if
/// another thread is reading from the same handle.
///
/// # Panics
///
/// This will panic if a previous `get()` or `get_mut()` call has panicked
/// inside it's callback. The only solution to this is to remove and reinsert
/// said item.
///
/// (It may also panic if the handle map detects internal state corruption,
/// however this should not happen except for bugs in the handle map code).
pub fn get_mut<F, E, R>(&self, h: Handle, callback: F) -> Result<R, E>
where
F: FnOnce(&mut T) -> Result<R, E>,
E: From<HandleError>,
{
// XXX figure out how to handle poison...
let map = self.map.read().unwrap();
let mtx = map.get(h)?;
let mut hm = mtx.lock().unwrap();
callback(&mut *hm)
}
/// Convenient wrapper for `get` which takes a `u64` that it will convert to
/// a handle.
///
/// The other benefit (besides convenience) of this over the version
/// that takes a [`Handle`] is that it allows handling handle-related errors
/// in one place.
///
/// # Locking
///
/// Note that this requires taking both:
///
/// - The map's read lock, and so it will block until all other threads have
/// finished any write operations.
/// - The mutex on the slot the handle is mapped to.
///
/// And so it will block if there are ongoing write operations, or if
/// another thread is reading from the same handle.
pub fn get_u64<F, E, R>(&self, u: u64, callback: F) -> Result<R, E>
where
F: FnOnce(&T) -> Result<R, E>,
E: From<HandleError>,
{
self.get(Handle::from_u64(u)?, callback)
}
/// Convenient wrapper for [`Self::get_mut`] which takes a `u64` that it will
/// convert to a handle.
///
/// The main benefit (besides convenience) of this over the version
/// that takes a [`Handle`] is that it allows handling handle-related errors
/// in one place.
///
/// # Locking
///
/// Note that this requires taking both:
///
/// - The map's read lock, and so it will block until all other threads have
/// finished any write operations.
/// - The mutex on the slot the handle is mapped to.
///
/// And so it will block if there are ongoing write operations, or if
/// another thread is reading from the same handle.
pub fn get_mut_u64<F, E, R>(&self, u: u64, callback: F) -> Result<R, E>
where
F: FnOnce(&mut T) -> Result<R, E>,
E: From<HandleError>,
{
self.get_mut(Handle::from_u64(u)?, callback)
}
/// Helper that performs both a
/// [`call_with_result`][crate::call_with_result] and
/// [`get`](ConcurrentHandleMap::get_mut).
pub fn call_with_result_mut<R, E, F>(
&self,
out_error: &mut ExternError,
h: u64,
callback: F,
) -> R::Value
where
F: std::panic::UnwindSafe + FnOnce(&mut T) -> Result<R, E>,
ExternError: From<E>,
R: IntoFfi,
{
use crate::call_with_result;
call_with_result(out_error, || -> Result<_, ExternError> {
// We can't reuse get_mut here because it would require E:
// From<HandleError>, which is inconvenient...
let h = Handle::from_u64(h)?;
let map = self.map.read().unwrap();
let mtx = map.get(h)?;
let mut hm = mtx.lock().unwrap();
Ok(callback(&mut *hm)?)
})
}
/// Helper that performs both a
/// [`call_with_result`][crate::call_with_result] and
/// [`get`](ConcurrentHandleMap::get).
pub fn call_with_result<R, E, F>(
&self,
out_error: &mut ExternError,
h: u64,
callback: F,
) -> R::Value
where
F: std::panic::UnwindSafe + FnOnce(&T) -> Result<R, E>,
ExternError: From<E>,
R: IntoFfi,
{
self.call_with_result_mut(out_error, h, |r| callback(r))
}
/// Helper that performs both a
/// [`call_with_output`][crate::call_with_output] and
/// [`get`](ConcurrentHandleMap::get).
pub fn call_with_output<R, F>(
&self,
out_error: &mut ExternError,
h: u64,
callback: F,
) -> R::Value
where
F: std::panic::UnwindSafe + FnOnce(&T) -> R,
R: IntoFfi,
{
self.call_with_result(out_error, h, |r| -> Result<_, HandleError> {
Ok(callback(r))
})
}
/// Helper that performs both a
/// [`call_with_output`][crate::call_with_output] and
/// [`get_mut`](ConcurrentHandleMap::get).
pub fn call_with_output_mut<R, F>(
&self,
out_error: &mut ExternError,
h: u64,
callback: F,
) -> R::Value
where
F: std::panic::UnwindSafe + FnOnce(&mut T) -> R,
R: IntoFfi,
{
self.call_with_result_mut(out_error, h, |r| -> Result<_, HandleError> {
Ok(callback(r))
})
}
/// Use `constructor` to create and insert a `T`, while inside a
/// [`call_with_result`][crate::call_with_result] call (to handle panics and
/// map errors onto an [`ExternError`][crate::ExternError]).
pub fn insert_with_result<E, F>(&self, out_error: &mut ExternError, constructor: F) -> u64
where
F: std::panic::UnwindSafe + FnOnce() -> Result<T, E>,
ExternError: From<E>,
{
use crate::call_with_result;
call_with_result(out_error, || -> Result<_, ExternError> {
// Note: it's important that we don't call the constructor while
// we're holding the write lock, because we don't want to poison
// the entire map if it panics!
let to_insert = constructor()?;
Ok(self.insert(to_insert))
})
}
/// Equivalent to
/// [`insert_with_result`](ConcurrentHandleMap::insert_with_result) for the
/// case where the constructor cannot produce an error.
///
/// The name is somewhat dubious, since there's no `output`, but it's
/// intended to make it clear that it contains a
/// [`call_with_output`][crate::call_with_output] internally.
pub fn insert_with_output<F>(&self, out_error: &mut ExternError, constructor: F) -> u64
where
F: std::panic::UnwindSafe + FnOnce() -> T,
{
// The Err type isn't important here beyond being convertable to ExternError
self.insert_with_result(out_error, || -> Result<_, HandleError> {
Ok(constructor())
})
}
}
impl<T> Default for ConcurrentHandleMap<T> {
#[inline]
fn default() -> Self {
Self::new()
}
}
// Returns the next map_id.
fn next_handle_map_id() -> u16 {
let id = HANDLE_MAP_ID_COUNTER
.fetch_add(1, Ordering::SeqCst)
.wrapping_add(1);
id as u16
}
// Note: These IDs are only used to detect using a key against the wrong HandleMap.
// We ensure they're randomly initialized, to prevent using them across separately
// compiled .so files.
lazy_static::lazy_static! {
// This should be `AtomicU16`, but those aren't stablilized yet.
// Instead, we just cast to u16 on read.
static ref HANDLE_MAP_ID_COUNTER: AtomicUsize = {
// Abuse HashMap's RandomState to get a strong RNG without bringing in
// the `rand` crate (OTOH maybe we should just bring in the rand crate?)
use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hasher};
let init = RandomState::new().build_hasher().finish() as usize;
AtomicUsize::new(init)
};
}
#[cfg(test)]
mod test {
use super::*;
#[derive(PartialEq, Debug)]
pub(super) struct Foobar(usize);
#[test]
fn test_invalid_handle() {
assert_eq!(Handle::from_u64(0), Err(HandleError::NullHandle));
// Valid except `version` is odd
assert_eq!(
Handle::from_u64((u64::from(HANDLE_MAGIC) << 48) | 0x1234_0012_0001),
Err(HandleError::InvalidHandle)
);
assert_eq!(
Handle::from_u64((u64::from(HANDLE_MAGIC) << 48) | 0x1234_0012_0002),
Ok(Handle {
version: 0x0002,
index: 0x0012,
map_id: 0x1234,
})
);
}
#[test]
fn test_correct_value_single() {
let mut map = HandleMap::new();
let handle = map.insert(Foobar(1234));
assert_eq!(map.get(handle).unwrap(), &Foobar(1234));
map.delete(handle).unwrap();
assert_eq!(map.get(handle), Err(HandleError::StaleVersion));
}
#[test]
fn test_correct_value_multiple() {
let mut map = HandleMap::new();
let handle1 = map.insert(Foobar(1234));
let handle2 = map.insert(Foobar(4321));
assert_eq!(map.get(handle1).unwrap(), &Foobar(1234));
assert_eq!(map.get(handle2).unwrap(), &Foobar(4321));
map.delete(handle1).unwrap();
assert_eq!(map.get(handle1), Err(HandleError::StaleVersion));
assert_eq!(map.get(handle2).unwrap(), &Foobar(4321));
}
#[test]
fn test_wrong_map() {
let mut map1 = HandleMap::new();
let mut map2 = HandleMap::new();
let handle1 = map1.insert(Foobar(1234));
let handle2 = map2.insert(Foobar(1234));
assert_eq!(map1.get(handle1).unwrap(), &Foobar(1234));
assert_eq!(map2.get(handle2).unwrap(), &Foobar(1234));
assert_eq!(map1.get(handle2), Err(HandleError::WrongMap));
assert_eq!(map2.get(handle1), Err(HandleError::WrongMap));
}
#[test]
fn test_bad_index() {
let map: HandleMap<Foobar> = HandleMap::new();
assert_eq!(
map.get(Handle {
map_id: map.id,
version: 2,
index: 100
}),
Err(HandleError::IndexPastEnd)
);
}
#[test]
fn test_resizing() {
let mut map = HandleMap::new();
let mut handles = vec![];
for i in 0..1000 {
handles.push(map.insert(Foobar(i)))
}
for (i, &h) in handles.iter().enumerate() {
assert_eq!(map.get(h).unwrap(), &Foobar(i));
assert_eq!(map.remove(h).unwrap(), Foobar(i));
}
let mut handles2 = vec![];
for i in 1000..2000 {
// Not really related to this test, but it's convenient to check this here.
let h = map.insert(Foobar(i));
let hu = h.into_u64();
assert_eq!(Handle::from_u64(hu).unwrap(), h);
handles2.push(hu);
}
for (i, (&h0, h1u)) in handles.iter().zip(handles2).enumerate() {
// It's still a stale version, even though the slot is occupied again.
assert_eq!(map.get(h0), Err(HandleError::StaleVersion));
let h1 = Handle::from_u64(h1u).unwrap();
assert_eq!(map.get(h1).unwrap(), &Foobar(i + 1000));
}
}
/// Tests that check our behavior when panicing.
///
/// Naturally these require panic=unwind, which means we can't run them when
/// generating coverage (well, `-Zprofile`-based coverage can't -- although
/// ptrace-based coverage like tarpaulin can), and so we turn them off.
///
/// (For clarity, `cfg(coverage)` is not a standard thing. We add it in
/// `automation/emit_coverage_info.sh`, and you can force it by adding
/// "--cfg coverage" to your RUSTFLAGS manually if you need to do so).
#[cfg(not(coverage))]
mod panic_tests {
use super::*;
struct PanicOnDrop(());
impl Drop for PanicOnDrop {
fn drop(&mut self) {
panic!("intentional panic (drop)");
}
}
#[test]
fn test_panicking_drop() {
let map = ConcurrentHandleMap::new();
let h = map.insert(PanicOnDrop(())).into_u64();
let mut e = ExternError::success();
crate::call_with_result(&mut e, || map.delete_u64(h));
assert_eq!(e.get_code(), crate::ErrorCode::PANIC);
let _ = unsafe { e.get_and_consume_message() };
assert!(!map.map.is_poisoned());
let inner = map.map.read().unwrap();
inner.assert_valid();
assert_eq!(inner.len(), 0);
}
#[test]
fn test_panicking_call_with() {
let map = ConcurrentHandleMap::new();
let h = map.insert(Foobar(0)).into_u64();
let mut e = ExternError::success();
map.call_with_output(&mut e, h, |_thing| {
panic!("intentional panic (call_with_output)");
});
assert_eq!(e.get_code(), crate::ErrorCode::PANIC);
let _ = unsafe { e.get_and_consume_message() };
{
assert!(!map.map.is_poisoned());
let inner = map.map.read().unwrap();
inner.assert_valid();
assert_eq!(inner.len(), 1);
let mut seen = false;
for e in &inner.entries {
if let EntryState::Active(v) = &e.state {
assert!(!seen);
assert!(v.is_poisoned());
seen = true;
}
}
}
assert!(map.delete_u64(h).is_ok());
assert!(!map.map.is_poisoned());
let inner = map.map.read().unwrap();
inner.assert_valid();
assert_eq!(inner.len(), 0);
}
#[test]
fn test_panicking_insert_with() {
let map = ConcurrentHandleMap::new();
let mut e = ExternError::success();
let res = map.insert_with_output(&mut e, || {
panic!("intentional panic (insert_with_output)");
});
assert_eq!(e.get_code(), crate::ErrorCode::PANIC);
let _ = unsafe { e.get_and_consume_message() };
assert_eq!(res, 0);
assert!(!map.map.is_poisoned());
let inner = map.map.read().unwrap();
inner.assert_valid();
assert_eq!(inner.len(), 0);
}
}
}
