AFIO  v2.00 late alpha
afio_v2_xxx::algorithm::shared_fs_mutex::memory_map< Hasher, HashIndexSize, SpinlockType > Class Template Reference

Many entity memory mapped shared/exclusive file system based lock. More...

#include "memory_map.hpp"

Inheritance diagram for afio_v2_xxx::algorithm::shared_fs_mutex::memory_map< Hasher, HashIndexSize, SpinlockType >:
afio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex

Classes

struct  _entity_idx
 

Public Types

using entity_type = shared_fs_mutex::entity_type
 The type of an entity id.
 
using entities_type = shared_fs_mutex::entities_type
 The type of a sequence of entities.
 
using hasher_type = Hasher< entity_type::value_type >
 The type of the hasher being used.
 
using spinlock_type = SpinlockType
 The type of the spinlock being used.
 

Public Member Functions

 memory_map (const memory_map &)=delete
 No copy construction.
 
memory_mapoperator= (const memory_map &)=delete
 No copy assignment.
 
 memory_map (memory_map &&o) noexcept
 Move constructor.
 
memory_mapoperator= (memory_map &&o) noexcept
 Move assign.
 
const file_handlehandle () const noexcept
 Return the handle to file being used for this lock.
 
virtual void unlock (entities_type entities, unsigned long long) noexcept final
 Unlock a previously locked sequence of entities.
 
entity_type entity_from_buffer (const char *buffer, size_t bytes, bool exclusive=true) noexcept
 Generates an entity id from a sequence of bytes.
 
template<typename T >
entity_type entity_from_string (const std::basic_string< T > &str, bool exclusive=true) noexcept
 Generates an entity id from a string.
 
entity_type random_entity (bool exclusive=true) noexcept
 Generates a cryptographically random entity id.
 
void fill_random_entities (span< entity_type > seq, bool exclusive=true) noexcept
 Fills a sequence of entity ids with cryptographic randomness. Much faster than calling random_entity() individually.
 
result< entities_guardlock (entities_type entities, deadline d=deadline(), bool spin_not_sleep=false) noexcept
 Lock all of a sequence of entities for exclusive or shared access.
 
result< entities_guardlock (entity_type entity, deadline d=deadline(), bool spin_not_sleep=false) noexcept
 Lock a single entity for exclusive or shared access.
 
result< entities_guardtry_lock (entities_type entities) noexcept
 Try to lock all of a sequence of entities for exclusive or shared access.
 
result< entities_guardtry_lock (entity_type entity) noexcept
 Try to lock a single entity for exclusive or shared access.
 

Static Public Member Functions

static result< memory_mapfs_mutex_map (const path_handle &base, path_view lockfile) noexcept
 

Protected Member Functions

virtual result< void > _lock (entities_guard &out, deadline d, bool spin_not_sleep) noexcept final
 

Static Protected Member Functions

static span< _entity_idx_hash_entities (_entity_idx *entity_to_idx, entities_type &entities)
 

Detailed Description

template<template< class > class Hasher = QUICKCPPLIB_NAMESPACE::algorithm::hash::fnv1a_hash, size_t HashIndexSize = 4096, class SpinlockType = QUICKCPPLIB_NAMESPACE::configurable_spinlock::shared_spinlock<>>
class afio_v2_xxx::algorithm::shared_fs_mutex::memory_map< Hasher, HashIndexSize, SpinlockType >

Many entity memory mapped shared/exclusive file system based lock.

Template Parameters
HasherA STL compatible hash algorithm to use (defaults to fnv1a_hash)
HashIndexSizeThe size in bytes of the hash index to use (defaults to 4Kb)
SpinlockTypeThe type of spinlock to use (defaults to a SharedMutex concept spinlock)

This is the highest performing filing system mutex in AFIO, but it comes with a long list of potential gotchas. It works by creating a random temporary file somewhere on the system and placing its path in a file at the lock file location. The random temporary file is mapped into memory by all processes using the lock where an open addressed hash table is kept. Each entity is hashed into somewhere in the hash table and its individual spin lock is used to implement the exclusion. As with byte_ranges, each entity is locked individually in sequence but if a particular lock fails, all are unlocked and the list is randomised before trying again. Because this locking implementation is entirely implemented in userspace using shared memory without any kernel syscalls, performance is probably as fast as any many-arbitrary-entity shared locking system could be.

As it uses shared memory, this implementation of shared_fs_mutex cannot work over a networked drive. If you attempt to open this lock on a network drive and the first user of the lock is not on this local machine, errc::no_lock_available will be returned from the constructor.

  • Linear complexity to number of concurrent users up until hash table starts to get full or hashed entries collide.
  • Sudden power loss during use is recovered from.
  • Safe for multithreaded usage of the same instance.
  • In the lightly contended case, an order of magnitude faster than any other shared_fs_mutex algorithm.

Caveats:

  • No ability to sleep until a lock becomes free, so CPUs are spun at 100%.
  • Sudden process exit with locks held will deadlock all other users.
  • Exponential complexity to number of entities being concurrently locked.
  • Exponential complexity to concurrency if entities hash to the same cache line. Most SMP and especially NUMA systems have a finite bandwidth for atomic compare and swap operations, and every attempt to lock or unlock an entity under this implementation is several of those operations. Under heavy contention, whole system performance very noticeably nose dives from excessive atomic operations, things like audio and the mouse pointer will stutter.
  • Sometimes different entities hash to the same offset and collide with one another, causing very poor performance.
  • Memory mapped files need to be cache unified with normal i/o in your OS kernel. Known OSs which don't use a unified cache for memory mapped and normal i/o are QNX, OpenBSD. Furthermore, doing normal i/o and memory mapped i/o to the same file needs to not corrupt the file. In the past, there have been editions of the Linux kernel and the OS X kernel which did this.
  • If your OS doesn't have sane byte range locks (OS X, BSD, older Linuxes) and multiple objects in your process use the same lock file, misoperation will occur.
  • Requires handle::current_path() to be working.
Todo:
memory_map::_hash_entities needs to hash x16, x8 and x4 at a time to encourage auto vectorisation

Member Function Documentation

◆ fs_mutex_map()

template<template< class > class Hasher = QUICKCPPLIB_NAMESPACE::algorithm::hash::fnv1a_hash, size_t HashIndexSize = 4096, class SpinlockType = QUICKCPPLIB_NAMESPACE::configurable_spinlock::shared_spinlock<>>
static result<memory_map> afio_v2_xxx::algorithm::shared_fs_mutex::memory_map< Hasher, HashIndexSize, SpinlockType >::fs_mutex_map ( const path_handle base,
path_view  lockfile 
)
inlinestaticnoexcept

Initialises a shared filing system mutex using the file at lockfile.

Errors returnable
Awaiting the clang result<> AST parser which auto generates all the error codes which could occur, but a particularly important one is errc::no_lock_available which will be returned if the lock is in use by another computer on a network.
214  {
215  AFIO_LOG_FUNCTION_CALL(0);
216  try
217  {
218  OUTCOME_TRY(ret, file_handle::file(base, lockfile, file_handle::mode::write, file_handle::creation::if_needed, file_handle::caching::reads));
219  file_handle temph;
220  // Am I the first person to this file? Lock everything exclusively
221  auto lockinuse = ret.try_lock(_initialisingoffset, 2, true);
222  if(lockinuse.has_error())
223  {
224  if(lockinuse.error() != errc::timed_out)
225  {
226  return lockinuse.error();
227  }
228  // Somebody else is also using this file, so try to read the hash index file I ought to use
229  lockinuse = ret.lock(_lockinuseoffset, 1, false); // inuse shared access, blocking
230  if(!lockinuse)
231  {
232  return lockinuse.error();
233  }
234  byte buffer[65536];
235  memset(buffer, 0, sizeof(buffer));
236  OUTCOME_TRYV(ret.read(0, {{buffer, 65535}}));
237  path_view temphpath(reinterpret_cast<filesystem::path::value_type *>(buffer));
238  result<file_handle> _temph(in_place_type<file_handle>);
239  _temph = file_handle::file({}, temphpath, file_handle::mode::write, file_handle::creation::open_existing, file_handle::caching::temporary);
240  // If temp file doesn't exist, I am on a different machine
241  if(!_temph)
242  {
243  // Release the exclusive lock and tell caller that this lock is not available
244  return errc::no_lock_available;
245  }
246  temph = std::move(_temph.value());
247  // Map the hash index file into memory for read/write access
248  OUTCOME_TRY(temphsection, section_handle::section(temph, HashIndexSize));
249  OUTCOME_TRY(temphmap, map_handle::map(temphsection, HashIndexSize));
250  // Map the path file into memory with its maximum possible size, read only
251  OUTCOME_TRY(hsection, section_handle::section(ret, 65536, section_handle::flag::read));
252  OUTCOME_TRY(hmap, map_handle::map(hsection, 0, 0, section_handle::flag::read));
253  return memory_map(std::move(ret), std::move(temph), std::move(lockinuse.value()), std::move(hmap), std::move(temphmap));
254  }
255 
256  // I am the first person to be using this (stale?) file, so create a new hash index file in /tmp
258  OUTCOME_TRY(_temph, file_handle::random_file(tempdirh));
259  temph = std::move(_temph);
260  // Truncate it out to the hash index size, and map it into memory for read/write access
261  OUTCOME_TRYV(temph.truncate(HashIndexSize));
262  OUTCOME_TRY(temphsection, section_handle::section(temph, HashIndexSize));
263  OUTCOME_TRY(temphmap, map_handle::map(temphsection, HashIndexSize));
264  // Write the path of my new hash index file, padding zeros to the nearest page size
265  // multiple to work around a race condition in the Linux kernel
266  OUTCOME_TRY(temppath, temph.current_path());
267  char buffer[4096];
268  memset(buffer, 0, sizeof(buffer));
269  size_t bytes = temppath.native().size() * sizeof(*temppath.c_str());
270  file_handle::const_buffer_type buffers[] = {{reinterpret_cast<const byte *>(temppath.c_str()), bytes}, {reinterpret_cast<const byte *>(buffer), 4096 - (bytes % 4096)}};
271  OUTCOME_TRYV(ret.truncate(65536));
272  OUTCOME_TRYV(ret.write({buffers, 0}));
273  // Map for read the maximum possible path file size, again to avoid race problems
274  OUTCOME_TRY(hsection, section_handle::section(ret, 65536, section_handle::flag::read));
275  OUTCOME_TRY(hmap, map_handle::map(hsection, 0, 0, section_handle::flag::read));
276  /* Take shared locks on inuse. Even if this implementation doesn't implement
277  atomic downgrade of exclusive range to shared range, we're fully prepared for other users
278  now. The _initialisingoffset remains exclusive to prevent double entry into this init routine.
279  */
280  OUTCOME_TRY(lockinuse2, ret.lock(_lockinuseoffset, 1, false));
281  lockinuse = std::move(lockinuse2); // releases exclusive lock on all three offsets
282  return memory_map(std::move(ret), std::move(temph), std::move(lockinuse.value()), std::move(hmap), std::move(temphmap));
283  }
284  catch(...)
285  {
286  return error_from_exception();
287  }
288  }
Cache reads only. Writes of data and metadata do not complete until reaching storage (O_SYNC)...
io_handle::io_result< io_handle::buffers_type > read(io_handle &self, io_handle::io_request< io_handle::buffers_type > reqs, deadline d=deadline()) noexcept
Read data from the open handle.
Definition: io_handle.hpp:483
const path_handle & storage_backed_temporary_files_directory() noexcept
Returns a reference to an open handle to a verified temporary directory where files created are store...
const path_handle & memory_backed_temporary_files_directory() noexcept
Returns a reference to an open handle to a verified temporary directory where files created are store...
static result< file_handle > file(const path_handle &base, path_view_type path, mode _mode=mode::read, creation _creation=creation::open_existing, caching _caching=caching::all, flag flags=flag::none) noexcept
static result< map_handle > map(size_type bytes, section_handle::flag _flag=section_handle::flag::readwrite) noexcept
bool is_valid() const noexcept
True if the handle is valid (and usually open)
Definition: handle.hpp:264
Ability to read and write (READ_CONTROL|FILE_READ_DATA|FILE_READ_ATTRIBUTES|FILE_READ_EA|FILE_WRITE_D...
static result< file_handle > random_file(const path_handle &dirpath, mode _mode=mode::write, caching _caching=caching::temporary, flag flags=flag::none) noexcept
Definition: file_handle.hpp:135
Cache reads and writes of data and metadata so they complete immediately, only sending any updates to...
static result< section_handle > section(file_handle &backing, extent_type maximum_size, flag _flag) noexcept
Create a memory section backed by a file.

The documentation for this class was generated from the following file: