include src/mc/transition/TransitionRandom.hpp
include src/mc/transition/TransitionSynchro.cpp
include src/mc/transition/TransitionSynchro.hpp
-include src/mc/udpor_global.cpp
-include src/mc/udpor_global.hpp
+include src/mc/explo/udpor/Configuration.hpp
+include src/mc/explo/udpor/Configuration.cpp
+include src/mc/explo/udpor/EventSet.cpp
+include src/mc/explo/udpor/EventSet.hpp
+include src/mc/explo/udpor/StateManager.cpp
+include src/mc/explo/udpor/StateManager.hpp
+include src/mc/explo/udpor/UnfoldingEvent.cpp
+include src/mc/explo/udpor/UnfoldingEvent.hpp
include src/plugins/ProducerConsumer.cpp
include src/plugins/chaos_monkey.cpp
include src/plugins/file_system/s4u_FileSystem.cpp
#include <xbt/asserts.h>
#include <xbt/log.h>
-XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_udpor, mc, "Logging specific to MC safety verification ");
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_udpor, mc, "Logging specific to verification using UDPOR");
namespace simgrid::mc::udpor {
#define SIMGRID_MC_UDPOR_CHECKER_HPP
#include "src/mc/explo/Exploration.hpp"
+#include "src/mc/explo/udpor/Configuration.hpp"
+#include "src/mc/explo/udpor/EventSet.hpp"
+#include "src/mc/explo/udpor/StateManager.hpp"
+#include "src/mc/explo/udpor/UnfoldingEvent.hpp"
#include "src/mc/mc_record.hpp"
-#include "src/mc/udpor_global.hpp"
#include <optional>
+/* Copyright (c) 2008-2023. The SimGrid Team. All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+#include "src/mc/explo/udpor/Configuration.hpp"
+
+namespace simgrid::mc::udpor {
+
+void Configuration::add_event(UnfoldingEvent* e)
+{
+ this->events_.insert(e);
+ this->newest_event = e;
+
+ // TODO: Re-compute the maxmimal events
+}
+
+} // namespace simgrid::mc::udpor
namespace simgrid::mc::udpor {
-using StateHandle = uint64_t;
-
class Configuration {
public:
Configuration() = default;
void recompute_maxmimal_events(UnfoldingEvent* new_event);
};
-class UnfoldingEvent {
-public:
- UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes,
- StateHandle sid);
- UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes);
- UnfoldingEvent(const UnfoldingEvent&) = default;
- UnfoldingEvent& operator=(UnfoldingEvent const&) = default;
- UnfoldingEvent(UnfoldingEvent&&) = default;
-
- EventSet get_history() const;
- bool in_history(const UnfoldingEvent* otherEvent) const;
-
- bool conflicts_with(const UnfoldingEvent* otherEvent) const;
- bool conflicts_with(const Configuration& config) const;
- bool immediately_conflicts_with(const UnfoldingEvent* otherEvt) const;
-
- bool operator==(const UnfoldingEvent&) const { return false; };
-
- inline StateHandle get_state_id() const { return state_id; }
- inline void set_state_id(StateHandle sid) { state_id = sid; }
-
-private:
- int id = -1;
-
- /**
- * @brief The "immediate" causes of this event.
- *
- * An event `e` is an immediate cause of an event `e'` if
- *
- * 1. e < e'
- * 2. There is no event `e''` in E such that
- * `e < e''` and `e'' < e'`
- *
- * Intuitively, an immediate cause "happened right before"
- * this event was executed. It is sufficient to store
- * only the immediate causes of any event `e`, as any indirect
- * causes of that event would either be an indirect cause
- * or an immediate cause of the immediate causes of `e`, and
- * so on.
- */
- EventSet immediate_causes;
- StateHandle state_id = 0ul;
-};
-
-class StateManager {
-private:
- using Handle = StateHandle;
-
- Handle current_handle_ = 1ul;
- std::unordered_map<Handle, std::unique_ptr<State>> state_map_;
-
-public:
- Handle record_state(std::unique_ptr<State>);
- std::optional<std::reference_wrapper<State>> get_state(Handle);
-};
-
} // namespace simgrid::mc::udpor
#endif
#include <algorithm>
#include <iterator>
-#include <set>
namespace simgrid::mc::udpor {
#ifndef SIMGRID_MC_UDPOR_EVENT_SET_HPP
#define SIMGRID_MC_UDPOR_EVENT_SET_HPP
-#include "src/mc/explo/udpor/UnfoldingEvent.hpp"
#include "src/mc/explo/udpor/udpor_forward.hpp"
+#include <cstddef>
+#include <set>
+
namespace simgrid::mc::udpor {
class EventSet {
#include "src/mc/api/State.hpp"
#include "src/mc/explo/udpor/udpor_forward.hpp"
+#include <optional>
+
namespace simgrid::mc::udpor {
class StateManager {
#include "src/mc/explo/udpor/EventSet.hpp"
#include "src/mc/explo/udpor/udpor_forward.hpp"
+#include <string>
+
namespace simgrid::mc::udpor {
class UnfoldingEvent {
class UnfoldingEvent;
class Configuration;
class StateManager;
+using StateHandle = unsigned long long;
} // namespace simgrid::mc::udpor
+++ /dev/null
-/* Copyright (c) 2008-2023. The SimGrid Team. All rights reserved. */
-
-/* This program is free software; you can redistribute it and/or modify it
- * under the terms of the license (GNU LGPL) which comes with this package. */
-
-#include "udpor_global.hpp"
-#include "xbt/log.h"
-
-#include <algorithm>
-#include <iterator>
-
-XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_udpor_global, mc, "udpor_global");
-
-namespace simgrid::mc::udpor {
-
-void EventSet::remove(UnfoldingEvent* e)
-{
- this->events_.erase(e);
-}
-
-void EventSet::subtract(const EventSet& other)
-{
- this->events_ = std::move(subtracting(other).events_);
-}
-
-// void EventSet::subtract(const Configuration& other);
-
-EventSet EventSet::subtracting(const EventSet& other) const
-{
- std::set<UnfoldingEvent*> result;
- std::set_difference(this->events_.begin(), this->events_.end(), other.events_.begin(), other.events_.end(),
- std::inserter(result, result.end()));
- return EventSet(std::move(result));
-}
-
-EventSet EventSet::subtracting(UnfoldingEvent* e) const
-{
- auto result = this->events_;
- result.erase(e);
- return EventSet(std::move(result));
-}
-// EventSet EventSet::subtracting(const Configuration* e) const;
-
-void EventSet::insert(UnfoldingEvent* e)
-{
- // TODO: Potentially react if the event is already inserted
- this->events_.insert(e);
-}
-
-void EventSet::form_union(const EventSet& other)
-{
- this->events_ = std::move(make_union(other).events_);
-}
-
-// void EventSet::form_union(const Configuration&);
-EventSet EventSet::make_union(UnfoldingEvent* e) const
-{
- auto result = this->events_;
- result.insert(e);
- return EventSet(std::move(result));
-}
-
-EventSet EventSet::make_union(const EventSet& other) const
-{
- std::set<UnfoldingEvent*> result;
- std::set_union(this->events_.begin(), this->events_.end(), other.events_.begin(), other.events_.end(),
- std::inserter(result, result.end()));
- return EventSet(std::move(result));
-}
-
-// EventSet EventSet::make_union(const Configuration& e) const;
-
-size_t EventSet::size() const
-{
- return this->events_.size();
-}
-
-bool EventSet::empty() const
-{
- return this->events_.empty();
-}
-
-bool EventSet::contains(UnfoldingEvent* e) const
-{
- return this->events_.find(e) != this->events_.end();
-}
-
-bool EventSet::is_subset_of(const EventSet& other) const
-{
- // If there is some element not contained in `other`, then
- // the set difference will contain that element and the
- // result won't be empty
- return subtracting(other).empty();
-}
-
-void Configuration::add_event(UnfoldingEvent* e)
-{
- this->events_.insert(e);
- this->newest_event = e;
-
- // TODO: Re-compute the maxmimal events
-}
-
-UnfoldingEvent::UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes)
- : UnfoldingEvent(nb_events, trans_tag, immediate_causes, 0)
-{
- // TODO: Implement this correctly
-}
-
-UnfoldingEvent::UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes,
- StateHandle sid)
-{
- // TODO: Implement this
-}
-
-StateManager::Handle StateManager::record_state(std::unique_ptr<State> state)
-{
- if (state.get() == nullptr) {
- throw std::invalid_argument("Expected a newly-allocated State but got NULL instead");
- }
-
- const auto integer_handle = this->current_handle_;
- this->state_map_.insert({integer_handle, std::move(state)});
-
- // TODO: Check for state handle overflow!
- this->current_handle_++;
- return integer_handle;
-}
-
-std::optional<std::reference_wrapper<State>> StateManager::get_state(StateManager::Handle handle)
-{
- auto state = this->state_map_.find(handle);
- if (state == this->state_map_.end()) {
- return std::nullopt;
- }
- auto& state_ref = *state->second.get();
- return std::optional<std::reference_wrapper<State>>{state_ref};
-}
-
-} // namespace simgrid::mc::udpor
+++ /dev/null
-/* Copyright (c) 2007-2023. The SimGrid Team. All rights reserved. */
-
-/* This program is free software; you can redistribute it and/or modify it
- * under the terms of the license (GNU LGPL) which comes with this package. */
-
-#ifndef SIMGRID_MC_UDPOR_GLOBAL_HPP
-#define SIMGRID_MC_UDPOR_GLOBAL_HPP
-
-#include "src/mc/api/State.hpp"
-
-#include <iostream>
-#include <optional>
-#include <queue>
-#include <set>
-#include <string_view>
-
-/* TODO: many method declared in this module are not implemented */
-
-namespace simgrid::mc::udpor {
-
-class UnfoldingEvent;
-class Configuration;
-using StateHandle = uint64_t;
-
-class EventSet {
-private:
- std::set<UnfoldingEvent*> events_;
- explicit EventSet(std::set<UnfoldingEvent*>&& raw_events) : events_(raw_events) {}
-
-public:
- EventSet() = default;
- EventSet(const EventSet&) = default;
- EventSet& operator=(const EventSet&) = default;
- EventSet& operator=(EventSet&&) = default;
- EventSet(EventSet&&) = default;
-
- inline auto begin() const { return this->events_.begin(); }
- inline auto end() const { return this->events_.end(); }
-
- void remove(UnfoldingEvent* e);
- void subtract(const EventSet& other);
- void subtract(const Configuration& other);
- EventSet subtracting(UnfoldingEvent* e) const;
- EventSet subtracting(const EventSet& e) const;
- EventSet subtracting(const Configuration* e) const;
-
- void insert(UnfoldingEvent* e);
- void form_union(const EventSet&);
- void form_union(const Configuration&);
- EventSet make_union(UnfoldingEvent* e) const;
- EventSet make_union(const EventSet&) const;
- EventSet make_union(const Configuration& e) const;
-
- size_t size() const;
- bool empty() const;
- bool contains(UnfoldingEvent* e) const;
- bool is_subset_of(const EventSet& other) const;
-};
-
-struct s_evset_in_t {
- EventSet causuality_events;
- EventSet cause;
- EventSet ancestorSet;
-};
-
-class Configuration {
-public:
- Configuration() = default;
- Configuration(const Configuration&) = default;
- Configuration& operator=(Configuration const&) = default;
- Configuration(Configuration&&) = default;
-
- inline auto begin() const { return this->events_.begin(); }
- inline auto end() const { return this->events_.end(); }
- inline const EventSet& get_events() const { return this->events_; }
- inline const EventSet& get_maximal_events() const { return this->max_events_; }
-
- void add_event(UnfoldingEvent*);
- UnfoldingEvent* get_latest_event() const;
-
-private:
- /**
- * @brief The most recent event added to the configuration
- */
- UnfoldingEvent* newest_event = nullptr;
- EventSet events_;
-
- /**
- * The <-maxmimal events of the configuration. These are
- * dynamically adjusted as events are added to the configuration
- *
- * @invariant: Each event that is part of this set is
- *
- * 1. a <-maxmimal event of the configuration, in the sense that
- * there is no event in the configuration that is "greater" than it.
- * In UDPOR terminology, each event does not "cause" another event
- *
- * 2. contained in the set of events `events_` which comprise
- * the configuration
- */
- EventSet max_events_;
-
-private:
- void recompute_maxmimal_events(UnfoldingEvent* new_event);
-};
-
-class UnfoldingEvent {
-public:
- UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes,
- StateHandle sid);
- UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes);
- UnfoldingEvent(const UnfoldingEvent&) = default;
- UnfoldingEvent& operator=(UnfoldingEvent const&) = default;
- UnfoldingEvent(UnfoldingEvent&&) = default;
-
- EventSet get_history() const;
- bool in_history(const UnfoldingEvent* otherEvent) const;
-
- bool conflicts_with(const UnfoldingEvent* otherEvent) const;
- bool conflicts_with(const Configuration& config) const;
- bool immediately_conflicts_with(const UnfoldingEvent* otherEvt) const;
-
- bool operator==(const UnfoldingEvent&) const { return false; };
-
- inline StateHandle get_state_id() const { return state_id; }
- inline void set_state_id(StateHandle sid) { state_id = sid; }
-
-private:
- int id = -1;
-
- /**
- * @brief The "immediate" causes of this event.
- *
- * An event `e` is an immediate cause of an event `e'` if
- *
- * 1. e < e'
- * 2. There is no event `e''` in E such that
- * `e < e''` and `e'' < e'`
- *
- * Intuitively, an immediate cause "happened right before"
- * this event was executed. It is sufficient to store
- * only the immediate causes of any event `e`, as any indirect
- * causes of that event would either be an indirect cause
- * or an immediate cause of the immediate causes of `e`, and
- * so on.
- */
- EventSet immediate_causes;
- StateHandle state_id = 0ul;
-};
-
-class StateManager {
-private:
- using Handle = StateHandle;
-
- Handle current_handle_ = 1ul;
- std::unordered_map<Handle, std::unique_ptr<State>> state_map_;
-
-public:
- Handle record_state(std::unique_ptr<State>);
- std::optional<std::reference_wrapper<State>> get_state(Handle);
-};
-
-} // namespace simgrid::mc::udpor
-#endif
src/mc/explo/UdporChecker.cpp
src/mc/explo/UdporChecker.hpp
+ src/mc/explo/udpor/Configuration.hpp
+ src/mc/explo/udpor/Configuration.cpp
+ src/mc/explo/udpor/EventSet.cpp
+ src/mc/explo/udpor/EventSet.hpp
+ src/mc/explo/udpor/StateManager.cpp
+ src/mc/explo/udpor/StateManager.hpp
+ src/mc/explo/udpor/UnfoldingEvent.cpp
+ src/mc/explo/udpor/UnfoldingEvent.hpp
+
src/mc/inspect/DwarfExpression.cpp
src/mc/inspect/DwarfExpression.hpp
src/mc/inspect/Frame.cpp
src/mc/mc_forward.hpp
src/mc/mc_private.hpp
src/mc/mc_record.cpp
- src/mc/udpor_global.cpp
- src/mc/udpor_global.hpp
src/xbt/mmalloc/mm_interface.c
)