llfio_v2_xxx::algorithm::shared_fs_mutex::lock_files Class Reference

Many entity exclusive compatibility file system based lock. More...

#include "lock_files.hpp"

Inheritance diagram for llfio_v2_xxx::algorithm::shared_fs_mutex::lock_files:

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
	lock_files (const lock_files &)=delete
	No copy construction.
lock_files &	operator= (const lock_files &)=delete
	No copy assignment.
	lock_files (lock_files &&o) noexcept
	Move constructor.
lock_files &	operator= (lock_files &&o) noexcept
	Move assign.
const path_handle &	path () const noexcept
	Return the path to the directory being used for this lock.
virtual void	unlock (entities_type, 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< lock_files >	fs_mutex_lock_files (const path_handle &lockdir) noexcept
	Initialises a shared filing system mutex using the directory at lockdir which MUST stay valid for the duration of this lock.

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

Detailed Description

Many entity exclusive compatibility file system based lock.

This is a very simple many entity shared mutex likely to work almost anywhere without surprises. It works by trying to exclusively create a file called the hex of the entity id. If it fails to exclusively create any file, it deletes all previously created files, randomises the order and tries locking them again until success. The only real reason to use this implementation is its excellent compatibility with almost everything, most users will want byte_ranges instead.

• Compatible with all networked file systems.
• Linear complexity to number of concurrent users.
• Exponential complexity to number of contended entities being concurrently locked.
• Requests for shared locks are treated as if for exclusive locks.

Caveats:

• No ability to sleep until a lock becomes free, so CPUs are spun at 100%.
• On POSIX only sudden process exit with locks held will deadlock all other users by leaving stale files around.
• Costs a file descriptor per entity locked.
• Sudden power loss during use will deadlock first user after reboot, again due to stale files.
• Currently this implementation does not permit more than one lock() per instance as the lock information is stored as member data. Creating multiple instances referring to the same path works fine. This could be fixed easily, but it would require a memory allocation per lock and user demand that this is actually a problem in practice.
• Leaves many 16 character long hexadecimal named files in the supplied directory which may confuse users. Tip: create a hidden lockfile directory.

Fixing the stale lock file problem could be quite trivial - simply byte range lock the first byte in the lock file to detect when a lock file is stale. However in this situation using the byte_ranges algorithm would be far superior, so implementing stale lock file clean up is left up to the user.

Constructor & Destructor Documentation

lock_files()

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

inlinenoexcept

Move constructor.

: _path(o._path), _hs(std::move(o._hs)) {}

Member Function Documentation

_lock()

virtual result< void > llfio_v2_xxx::algorithm::shared_fs_mutex::lock_files::_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();
          }
        }
        size_t n;
        // Create a set of paths to files to exclusively create
        std::vector<std::string> entity_paths(out.entities.size());
        for(n = 0; n < out.entities.size(); n++)
        {
          auto v = out.entities[n].value;
          entity_paths[n] = QUICKCPPLIB_NAMESPACE::algorithm::string::to_hex_string(span<char>(reinterpret_cast<char *>(&v), 8));
        }
        _hs.resize(out.entities.size());
        do
        {
          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--)
                {
                  (void) _hs[n].close();  // delete on close semantics deletes the file
                }
                (void) _hs[0].close();
              }
            });
            for(n = 0; n < out.entities.size(); n++)
            {
              auto ret = file_handle::file(_path, entity_paths[n], file_handle::mode::write, file_handle::creation::only_if_not_exist, file_handle::caching::temporary, file_handle::flag::unlink_on_first_close);
              if(ret.has_error())
              {
                const auto &ec = ret.error();
                if(ec != errc::resource_unavailable_try_again && ec != errc::file_exists)
                {
                  return std::move(ret).error();
                }
                // Collided with another locker
                was_contended = n;
                break;
              }
              _hs[n] = std::move(ret.value());
            }
            if(n == out.entities.size())
            {
              undo.release();
            }
          }
          if(n != out.entities.size())
          {
            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());
            // Sleep for a very short time
            if(!spin_not_sleep)
            {
              std::this_thread::yield();
            }
          }
        } while(n < out.entities.size());
        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_lock_files()

static result< lock_files > llfio_v2_xxx::algorithm::shared_fs_mutex::lock_files::fs_mutex_lock_files ( const path_handle &  lockdir )

inlinestaticnoexcept

Initialises a shared filing system mutex using the directory at lockdir which MUST stay valid for the duration of this lock.

      {
        LLFIO_LOG_FUNCTION_CALL(0);
        return lock_files(lockdir);
      }

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=()

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

inlinenoexcept

Move assign.

      {
        if(this == &o)
        {
          return *this;
        }
        this->~lock_files();
        new(this) lock_files(std::move(o));
        return *this;
      }

path()

const path_handle & llfio_v2_xxx::algorithm::shared_fs_mutex::lock_files::path ( ) const

inlinenoexcept

Return the path to the directory being used for this lock.

{ return _path; }

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::lock_files::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(auto &i : _hs)
        {
          (void) i.close();  // delete on close semantics deletes the file
        }
      }

---

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

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