llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges Class Reference

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

#include "byte_ranges.hpp"

Inheritance diagram for llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges:

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.

Public Member Functions
	byte_ranges (const byte_ranges &)=delete
	No copy construction.
byte_ranges &	operator= (const byte_ranges &)=delete
	No copy assignment.
	byte_ranges (byte_ranges &&o) noexcept
	Move constructor.
byte_ranges &	operator= (byte_ranges &&o) noexcept
	Move assign.
const file_handle &	handle () 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_guard >	lock (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_guard >	lock (entity_type entity, deadline d=deadline(), bool spin_not_sleep=false) noexcept
	Lock a single entity for exclusive or shared access.
result< entities_guard >	try_lock (entities_type entities) noexcept
	Try to lock all of a sequence of entities for exclusive or shared access.
result< entities_guard >	try_lock (entity_type entity) noexcept
	Try to lock a single entity for exclusive or shared access.

Static Public Member Functions
static result< byte_ranges >	fs_mutex_byte_ranges (const path_handle &base, path_view lockfile) noexcept
	Initialises a shared filing system mutex using the file at lockfile.

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

Detailed Description

Many entity shared/exclusive file system based lock.

This is a simple many entity shared mutex. It works by locking in the same file the byte at the offset of the entity id. If it fails to lock a byte, it backs out all preceding locks, randomises the order and tries locking them again until success. Needless to say this algorithm puts a lot of strain on your byte range locking implementation, some NFS implementations have been known to fail to cope.

Note

Most users will want to use safe_byte_ranges instead of this class directly.

• Compatible with networked file systems, though be cautious with older NFS.
• Linear complexity to number of concurrent users.
• Exponential complexity to number of entities being concurrently locked, though some OSs provide linear complexity so long as total concurrent waiting processes is CPU core count or less.
• Does a reasonable job of trying to sleep the thread if any of the entities are locked.
• Sudden process exit with lock held is recovered from.
• Sudden power loss during use is recovered from.
• Safe for multithreaded usage of the same instance.

Caveats:

• When entities being locked is more than one, the algorithm places the contending lock at the front of the list during the randomisation after lock failure so we can sleep the thread until it becomes free. However, under heavy churn the thread will generally spin, consuming 100% CPU.
• Byte range locks need to work properly on your system. Misconfiguring NFS or Samba to cause byte range locks to not work right will produce bad outcomes.
• 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. Use lock_files or share a single instance of this class per lock file in this case.
• If you are on POSIX and the same process relocks an entity a second time, it will release everything on the first unlock. On Windows, the first unlock releases the exclusive lock and the second unlock will release the shared lock.

Constructor & Destructor Documentation

byte_ranges()

llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges::byte_ranges ( byte_ranges &&  o )

inlinenoexcept

Move constructor.

: _h(std::move(o._h)) {}

Member Function Documentation

_lock()

virtual result< void > llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges::_lock ( entities_guard &  out, deadline  d, bool  spin_not_sleep  )

inlinefinalprotectedvirtualnoexcept

Implements llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex.

      {
        LLFIO_LOG_FUNCTION_CALL(this);
        std::chrono::steady_clock::time_point began_steady;
        std::chrono::system_clock::time_point end_utc;
        if(d)
        {
          if((d).steady)
          {
            began_steady = std::chrono::steady_clock::now();
          }
          else
          {
            end_utc = (d).to_time_point();
          }
        }
        // Fire this if an error occurs
        auto disableunlock = make_scope_exit([&]() noexcept { out.release(); });
        size_t n;
        for(;;)
        {
          auto was_contended = static_cast<size_t>(-1);
          {
            auto undo = make_scope_exit([&]() noexcept {
              // 0 to (n-1) need to be closed
              if(n > 0)
              {
                --n;
                // Now 0 to n needs to be closed
                for(; n > 0; n--)
                {
                  _h.unlock_file_range(out.entities[n].value, 1);
                }
                _h.unlock_file_range(out.entities[0].value, 1);
              }
            });
            for(n = 0; n < out.entities.size(); n++)
            {
              deadline nd;
              // Only for very first entity will we sleep until its lock becomes available
              if(n != 0u)
              {
                nd = deadline(std::chrono::seconds(0));
              }
              else
              {
                nd = deadline();
                if(d)
                {
                  if((d).steady)
                  {
                    std::chrono::nanoseconds ns = std::chrono::duration_cast<std::chrono::nanoseconds>((began_steady + std::chrono::nanoseconds((d).nsecs)) - std::chrono::steady_clock::now());
                    if(ns.count() < 0)
                    {
                      (nd).nsecs = 0;
                    }
                    else
                    {
                      (nd).nsecs = ns.count();
                    }
                  }
                  else
                  {
                    (nd) = (d);
                  }
                }
              }
              auto outcome = _h.lock_file_range(out.entities[n].value, 1, (out.entities[n].exclusive != 0u) ? lock_kind::exclusive : lock_kind::shared, nd);
              if(!outcome)
              {
                was_contended = n;
                goto failed;
              }
              outcome.value().release();
            }
            // Everything is locked, exit
            undo.release();
            disableunlock.release();
            return success();
          }
        failed:
          if(d)
          {
            if((d).steady)
            {
              if(std::chrono::steady_clock::now() >= (began_steady + std::chrono::nanoseconds((d).nsecs)))
              {
                return errc::timed_out;
              }
            }
            else
            {
              if(std::chrono::system_clock::now() >= end_utc)
              {
                return errc::timed_out;
              }
            }
          }
          // Move was_contended to front and randomise rest of out.entities
          std::swap(out.entities[was_contended], out.entities[0]);
          auto front = out.entities.begin();
          ++front;
          QUICKCPPLIB_NAMESPACE::algorithm::small_prng::random_shuffle(front, out.entities.end());
          if(!spin_not_sleep)
          {
            std::this_thread::yield();
          }
        }
        // return success();
      }

entity_from_buffer()

entity_type llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::entity_from_buffer ( const char *  buffer, size_t  bytes, bool  exclusive = true  )

inlinenoexceptinherited

Generates an entity id from a sequence of bytes.

      {
        uint128 hash = QUICKCPPLIB_NAMESPACE::algorithm::hash::fast_hash::hash(buffer, bytes);
        return {hash.as_longlongs[0] ^ hash.as_longlongs[1], exclusive};
      }

entity_from_string()

template<typename T >

entity_type llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::entity_from_string ( const std::basic_string< T > &  str, bool  exclusive = true  )

inlinenoexceptinherited

Generates an entity id from a string.

      {
        uint128 hash = QUICKCPPLIB_NAMESPACE::algorithm::hash::fast_hash::hash(str);
        return {hash.as_longlongs[0] ^ hash.as_longlongs[1], exclusive};
      }

fill_random_entities()

void llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::fill_random_entities ( span< entity_type >  seq, bool  exclusive = true  )

inlinenoexceptinherited

Fills a sequence of entity ids with cryptographic randomness. Much faster than calling random_entity() individually.

      {
        utils::random_fill(reinterpret_cast<char *>(seq.data()), seq.size() * sizeof(entity_type));
        for(auto &i : seq)
        {
          i.exclusive = exclusive;  // NOLINT
        }
      }

fs_mutex_byte_ranges()

static result< byte_ranges > llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges::fs_mutex_byte_ranges ( const path_handle &  base, path_view  lockfile  )

inlinestaticnoexcept

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

      {
        LLFIO_LOG_FUNCTION_CALL(0);
        OUTCOME_TRY(auto &&ret, file_handle::file(base, lockfile, file_handle::mode::write, file_handle::creation::if_needed, file_handle::caching::temporary));
        return byte_ranges(std::move(ret));
      }

handle()

const file_handle & llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges::handle ( ) const

inlinenoexcept

Return the handle to file being used for this lock.

{ return _h; }

lock() [1/2]

result< entities_guard > llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::lock ( entities_type  entities, deadline  d = deadline(), bool  spin_not_sleep = false  )

inlinenoexceptinherited

Lock all of a sequence of entities for exclusive or shared access.

      {
        entities_guard ret(this, entities);
        OUTCOME_TRYV(_lock(ret, d, spin_not_sleep));
        return {std::move(ret)};
      }

lock() [2/2]

result< entities_guard > llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::lock ( entity_type  entity, deadline  d = deadline(), bool  spin_not_sleep = false  )

inlinenoexceptinherited

Lock a single entity for exclusive or shared access.

      {
        entities_guard ret(this, entity);
        OUTCOME_TRYV(_lock(ret, d, spin_not_sleep));
        return {std::move(ret)};
      }

operator=()

byte_ranges & llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges::operator= ( byte_ranges &&  o )

inlinenoexcept

Move assign.

      {
        if(this == &o)
        {
          return *this;
        }
        _h = std::move(o._h);
        return *this;
      }

random_entity()

entity_type llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::random_entity ( bool  exclusive = true )

inlinenoexceptinherited

Generates a cryptographically random entity id.

      {
        entity_type::value_type v;
        utils::random_fill(reinterpret_cast<char *>(&v), sizeof(v));
        return {v, exclusive};
      }

try_lock() [1/2]

result< entities_guard > llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::try_lock ( entities_type  entities )

inlinenoexceptinherited

Try to lock all of a sequence of entities for exclusive or shared access.

{ return lock(entities, deadline(std::chrono::seconds(0))); }

try_lock() [2/2]

result< entities_guard > llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex::try_lock ( entity_type  entity )

inlinenoexceptinherited

Try to lock a single entity for exclusive or shared access.

{ return lock(entity, deadline(std::chrono::seconds(0))); }

unlock()

virtual void llfio_v2_xxx::algorithm::shared_fs_mutex::byte_ranges::unlock ( entities_type  entities, unsigned long long  hint  )

inlinefinalvirtualnoexcept

Unlock a previously locked sequence of entities.

Implements llfio_v2_xxx::algorithm::shared_fs_mutex::shared_fs_mutex.

      {
        LLFIO_LOG_FUNCTION_CALL(this);
        for(const auto &i : entities)
        {
          _h.unlock_file_range(i.value, 1);
        }
      }

---

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

• include/llfio/v2.0/algorithm/shared_fs_mutex/byte_ranges.hpp