hegel::stateful::ConcurrentStateMachine< Derived > Class Template Reference

Base class for a concurrent state machine. More...

#include <stateful.h>

Public Member Functions
std::vector< Invariant< Derived > >	invariants () const
	Returns the invariants of the machine.

Detailed Description

template<typename Derived>
class hegel::stateful::ConcurrentStateMachine< Derived >

Base class for a concurrent state machine.

Derive a machine from this class. Define a rules() member that returns the rules for the machine. Override invariants to add invariant checks.

This example tests a key-value store that has a lost-update bug. The increment operation reads a value and then writes the incremented value in a separate operation. Thus, two workers can overwrite an update. The invariant compares the stored total with the number of completed increments.

The operations group contains the register, increment, and read rules. These rules can run concurrently. The snapshot group does not overlap with the operations group.

class ConcurrentKVStore {
  public:
    std::optional<int64_t> get(int key) const {
        std::lock_guard<std::mutex> lock(mutex_);
        auto value = values_.find(key);
        if (value == values_.end()) {
            return std::nullopt;
        }
        return value->second;
    }
 
    void put(int key, int64_t value) {
        std::lock_guard<std::mutex> lock(mutex_);
        values_[key] = value;
    }
 
    bool put_if_absent(int key, int64_t value) {
        std::lock_guard<std::mutex> lock(mutex_);
        return values_.emplace(key, value).second;
    }
 
    void increment(int key) {
        int64_t value = get(key).value_or(0);
        std::this_thread::yield();
        put(key, value + 1);
    }
 
    std::map<int, int64_t> snapshot() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return values_;
    }
 
  private:
    mutable std::mutex mutex_;
    std::map<int, int64_t> values_;
};
 
struct ConcurrentKV
    : hegel::stateful::ConcurrentStateMachine<ConcurrentKV> {
    ConcurrentKVStore store;
    hegel::stateful::ConcurrentPool<int> keys;
    std::atomic<int64_t> increments{0};
 
    explicit ConcurrentKV(hegel::TestCase& tc) : keys(tc) {}
 
    std::vector<hegel::stateful::ConcurrentRule<ConcurrentKV>>
    rules() {
        return {
            {"register", "operations",
             [](hegel::TestCase& tc, ConcurrentKV& m) {
                 int key = tc.draw(hegel::generators::integers<int>(
                     {.min_value = 0, .max_value = 3}));
                 if (m.store.put_if_absent(key, 0)) {
                     m.keys.add(tc, key);
                 }
             }},
            {"increment", "operations",
             [](hegel::TestCase& tc, ConcurrentKV& m) {
                 int key = tc.draw(
                     hegel::stateful::values_reusable(m.keys));
                 m.store.increment(key);
                 m.increments.fetch_add(1);
             }},
            {"read", "operations",
             [](hegel::TestCase& tc, ConcurrentKV& m) {
                 int key = tc.draw(
                     hegel::stateful::values_reusable(m.keys));
                 int64_t value = m.store.get(key).value_or(0);
                 tc.note("read " + std::to_string(key) + " -> " +
                         std::to_string(value));
             }},
            {"snapshot", "snapshot",
             [](hegel::TestCase& tc, ConcurrentKV& m) {
                 tc.note("snapshot holds " +
                         std::to_string(m.store.snapshot().size()) +
                         " keys");
             }},
        };
    }
 
    std::vector<hegel::stateful::Invariant<ConcurrentKV>> invariants()
        const {
        return {{"no_lost_updates", [](const ConcurrentKV& m) {
                     int64_t stored = 0;
                     for (const auto& entry : m.store.snapshot()) {
                         stored += entry.second;
                     }
                     int64_t performed = m.increments.load();
                     if (stored != performed) {
                         throw std::runtime_error(
                             "the store lost an increment");
                     }
                 }}};
    }
};
 
HEGEL_TEST(concurrent_kv)(hegel::TestCase& tc) {
    ConcurrentKV machine(tc);
    hegel::stateful::run_concurrent(machine, tc, 1, 4);
}

Template Parameters

Derived

The deriving state-machine type

Member Function Documentation

invariants()

template<typename Derived>

std::vector< Invariant< Derived > > hegel::stateful::ConcurrentStateMachine< Derived >::invariants ( ) const

inline

Returns the invariants of the machine.

Override this member to add invariants. There are no invariants by default.

Returns

The invariants of the machine

---

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

• include/hegel/generators/stateful.h