include/rv/da_monitor.h - third_party/linux - Git at Google

 /* SPDX-License-Identifier: GPL-2.0 */
 /*
  * Copyright (C) 2019-2022 Red Hat, Inc. Daniel Bristot de Oliveira <bristot@kernel.org>
  *
  * Deterministic automata (DA) monitor functions, to be used together
  * with automata models in C generated by the rvgen tool.
  *
  * The rvgen tool is available at tools/verification/rvgen/
  *
  * For further information, see:
  *   Documentation/trace/rv/monitor_synthesis.rst
  */

 #ifndef _RV_DA_MONITOR_H
 #define _RV_DA_MONITOR_H

 #include <rv/automata.h>
 #include <linux/rv.h>
 #include <linux/stringify.h>
 #include <linux/bug.h>
 #include <linux/sched.h>
 #include <linux/slab.h>
 #include <linux/hashtable.h>

 /*
  * Per-cpu variables require a unique name although static in some
  * configurations (e.g. CONFIG_DEBUG_FORCE_WEAK_PER_CPU or alpha modules).
  */
 #define DA_MON_NAME CONCATENATE(da_mon_, MONITOR_NAME)

 static struct rv_monitor rv_this;

 /*
  * Hook to allow the implementation of hybrid automata: define it with a
  * function that takes curr_state, event and next_state and returns true if the
  * environment constraints (e.g. timing) are satisfied, false otherwise.
  */
 #ifndef da_monitor_event_hook
 #define da_monitor_event_hook(...) true
 #endif

 /*
  * Hook to allow the implementation of hybrid automata: define it with a
  * function that takes the da_monitor and performs further initialisation
  * (e.g. reset set up timers).
  */
 #ifndef da_monitor_init_hook
 #define da_monitor_init_hook(da_mon)
 #endif

 /*
  * Hook to allow the implementation of hybrid automata: define it with a
  * function that takes the da_monitor and performs further reset (e.g. reset
  * all clocks).
  */
 #ifndef da_monitor_reset_hook
 #define da_monitor_reset_hook(da_mon)
 #endif

 /*
  * Type for the target id, default to int but can be overridden.
  * A long type can work as hash table key (PER_OBJ) but will be downgraded to
  * int in the event tracepoint.
  * Unused for implicit monitors.
  */
 #ifndef da_id_type
 #define da_id_type int
 #endif

 static void react(enum states curr_state, enum events event)
 {
 	rv_react(&rv_this,
 		 "rv: monitor %s does not allow event %s on state %s\n",
 		 __stringify(MONITOR_NAME),
 		 model_get_event_name(event),
 		 model_get_state_name(curr_state));
 }

 /*
  * da_monitor_reset - reset a monitor and setting it to init state
  */
 static inline void da_monitor_reset(struct da_monitor *da_mon)
 {
 	da_monitor_reset_hook(da_mon);
 	da_mon->monitoring = 0;
 	da_mon->curr_state = model_get_initial_state();
 }

 /*
  * da_monitor_start - start monitoring
  *
  * The monitor will ignore all events until monitoring is set to true. This
  * function needs to be called to tell the monitor to start monitoring.
  */
 static inline void da_monitor_start(struct da_monitor *da_mon)
 {
 	da_mon->curr_state = model_get_initial_state();
 	da_mon->monitoring = 1;
 	da_monitor_init_hook(da_mon);
 }

 /*
  * da_monitoring - returns true if the monitor is processing events
  */
 static inline bool da_monitoring(struct da_monitor *da_mon)
 {
 	return da_mon->monitoring;
 }

 /*
  * da_monitor_enabled - checks if the monitor is enabled
  */
 static inline bool da_monitor_enabled(void)
 {
 	/* global switch */
 	if (unlikely(!rv_monitoring_on()))
 		return 0;

 	/* monitor enabled */
 	if (unlikely(!rv_this.enabled))
 		return 0;

 	return 1;
 }

 /*
  * da_monitor_handling_event - checks if the monitor is ready to handle events
  */
 static inline bool da_monitor_handling_event(struct da_monitor *da_mon)
 {
 	if (!da_monitor_enabled())
 		return 0;

 	/* monitor is actually monitoring */
 	if (unlikely(!da_monitoring(da_mon)))
 		return 0;

 	return 1;
 }

 #if RV_MON_TYPE == RV_MON_GLOBAL
 /*
  * Functions to define, init and get a global monitor.
  */

 /*
  * global monitor (a single variable)
  */
 static struct da_monitor DA_MON_NAME;

 /*
  * da_get_monitor - return the global monitor address
  */
 static struct da_monitor *da_get_monitor(void)
 {
 	return &DA_MON_NAME;
 }

 /*
  * da_monitor_reset_all - reset the single monitor
  */
 static void da_monitor_reset_all(void)
 {
 	da_monitor_reset(da_get_monitor());
 }

 /*
  * da_monitor_init - initialize a monitor
  */
 static inline int da_monitor_init(void)
 {
 	da_monitor_reset_all();
 	return 0;
 }

 /*
  * da_monitor_destroy - destroy the monitor
  */
 static inline void da_monitor_destroy(void)
 {
 	da_monitor_reset_all();
 }

 #elif RV_MON_TYPE == RV_MON_PER_CPU
 /*
  * Functions to define, init and get a per-cpu monitor.
  */

 /*
  * per-cpu monitor variables
  */
 static DEFINE_PER_CPU(struct da_monitor, DA_MON_NAME);

 /*
  * da_get_monitor - return current CPU monitor address
  */
 static struct da_monitor *da_get_monitor(void)
 {
 	return this_cpu_ptr(&DA_MON_NAME);
 }

 /*
  * da_monitor_reset_all - reset all CPUs' monitor
  */
 static void da_monitor_reset_all(void)
 {
 	struct da_monitor *da_mon;
 	int cpu;

 	for_each_cpu(cpu, cpu_online_mask) {
 		da_mon = per_cpu_ptr(&DA_MON_NAME, cpu);
 		da_monitor_reset(da_mon);
 	}
 }

 /*
  * da_monitor_init - initialize all CPUs' monitor
  */
 static inline int da_monitor_init(void)
 {
 	da_monitor_reset_all();
 	return 0;
 }

 /*
  * da_monitor_destroy - destroy the monitor
  */
 static inline void da_monitor_destroy(void)
 {
 	da_monitor_reset_all();
 }

 #elif RV_MON_TYPE == RV_MON_PER_TASK
 /*
  * Functions to define, init and get a per-task monitor.
  */

 /*
  * The per-task monitor is stored a vector in the task struct. This variable
  * stores the position on the vector reserved for this monitor.
  */
 static int task_mon_slot = RV_PER_TASK_MONITOR_INIT;

 /*
  * da_get_monitor - return the monitor in the allocated slot for tsk
  */
 static inline struct da_monitor *da_get_monitor(struct task_struct *tsk)
 {
 	return &tsk->rv[task_mon_slot].da_mon;
 }

 /*
  * da_get_target - return the task associated to the monitor
  */
 static inline struct task_struct *da_get_target(struct da_monitor *da_mon)
 {
 	return container_of(da_mon, struct task_struct, rv[task_mon_slot].da_mon);
 }

 /*
  * da_get_id - return the id associated to the monitor
  *
  * For per-task monitors, the id is the task's PID.
  */
 static inline da_id_type da_get_id(struct da_monitor *da_mon)
 {
 	return da_get_target(da_mon)->pid;
 }

 static void da_monitor_reset_all(void)
 {
 	struct task_struct *g, *p;
 	int cpu;

 	read_lock(&tasklist_lock);
 	for_each_process_thread(g, p)
 		da_monitor_reset(da_get_monitor(p));
 	for_each_present_cpu(cpu)
 		da_monitor_reset(da_get_monitor(idle_task(cpu)));
 	read_unlock(&tasklist_lock);
 }

 /*
  * da_monitor_init - initialize the per-task monitor
  *
  * Try to allocate a slot in the task's vector of monitors. If there
  * is an available slot, use it and reset all task's monitor.
  */
 static int da_monitor_init(void)
 {
 	int slot;

 	slot = rv_get_task_monitor_slot();
 	if (slot < 0 || slot >= RV_PER_TASK_MONITOR_INIT)
 		return slot;

 	task_mon_slot = slot;

 	da_monitor_reset_all();
 	return 0;
 }

 /*
  * da_monitor_destroy - return the allocated slot
  */
 static inline void da_monitor_destroy(void)
 {
 	if (task_mon_slot == RV_PER_TASK_MONITOR_INIT) {
 		WARN_ONCE(1, "Disabling a disabled monitor: " __stringify(MONITOR_NAME));
 		return;
 	}
 	rv_put_task_monitor_slot(task_mon_slot);
 	task_mon_slot = RV_PER_TASK_MONITOR_INIT;

 	da_monitor_reset_all();
 }

 #elif RV_MON_TYPE == RV_MON_PER_OBJ
 /*
  * Functions to define, init and get a per-object monitor.
  */

 struct da_monitor_storage {
 	da_id_type id;
 	monitor_target target;
 	union rv_task_monitor rv;
 	struct hlist_node node;
 	struct rcu_head rcu;
 };

 #ifndef DA_MONITOR_HT_BITS
 #define DA_MONITOR_HT_BITS 10
 #endif
 static DEFINE_HASHTABLE(da_monitor_ht, DA_MONITOR_HT_BITS);

 /*
  * da_create_empty_storage - pre-allocate an empty storage
  */
 static inline struct da_monitor_storage *da_create_empty_storage(da_id_type id)
 {
 	struct da_monitor_storage *mon_storage;

 	mon_storage = kmalloc_nolock(sizeof(struct da_monitor_storage),
 				     __GFP_ZERO, NUMA_NO_NODE);
 	if (!mon_storage)
 		return NULL;

 	hash_add_rcu(da_monitor_ht, &mon_storage->node, id);
 	mon_storage->id = id;
 	return mon_storage;
 }

 /*
  * da_create_storage - create the per-object storage
  *
  * The caller is responsible to synchronise writers, either with locks or
  * implicitly. For instance, if da_create_storage is only called from a single
  * event for target (e.g. sched_switch), it's safe to call this without locks.
  */
 static inline struct da_monitor *da_create_storage(da_id_type id,
 						   monitor_target target,
 						   struct da_monitor *da_mon)
 {
 	struct da_monitor_storage *mon_storage;

 	if (da_mon)
 		return da_mon;

 	mon_storage = da_create_empty_storage(id);
 	if (!mon_storage)
 		return NULL;

 	mon_storage->target = target;
 	return &mon_storage->rv.da_mon;
 }

 /*
  * __da_get_mon_storage - get the monitor storage from the hash table
  */
 static inline struct da_monitor_storage *__da_get_mon_storage(da_id_type id)
 {
 	struct da_monitor_storage *mon_storage;

 	lockdep_assert_in_rcu_read_lock();
 	hash_for_each_possible_rcu(da_monitor_ht, mon_storage, node, id) {
 		if (mon_storage->id == id)
 			return mon_storage;
 	}

 	return NULL;
 }

 /*
  * da_get_monitor - return the monitor for target
  */
 static struct da_monitor *da_get_monitor(da_id_type id, monitor_target target)
 {
 	struct da_monitor_storage *mon_storage;

 	mon_storage = __da_get_mon_storage(id);
 	return mon_storage ? &mon_storage->rv.da_mon : NULL;
 }

 /*
  * da_get_target - return the object associated to the monitor
  */
 static inline monitor_target da_get_target(struct da_monitor *da_mon)
 {
 	return container_of(da_mon, struct da_monitor_storage, rv.da_mon)->target;
 }

 /*
  * da_get_id - return the id associated to the monitor
  */
 static inline da_id_type da_get_id(struct da_monitor *da_mon)
 {
 	return container_of(da_mon, struct da_monitor_storage, rv.da_mon)->id;
 }

 /*
  * da_create_or_get - create the per-object storage if not already there
  *
  * This needs a lookup so should be guarded by RCU, the condition is checked
  * directly in da_create_storage()
  */
 static inline void da_create_or_get(da_id_type id, monitor_target target)
 {
 	guard(rcu)();
 	da_create_storage(id, target, da_get_monitor(id, target));
 }

 /*
  * da_fill_empty_storage - store the target in a pre-allocated storage
  *
  * Can be used as a substitute of da_create_storage when starting a monitor in
  * an environment where allocation is unsafe.
  */
 static inline struct da_monitor *da_fill_empty_storage(da_id_type id,
 						       monitor_target target,
 						       struct da_monitor *da_mon)
 {
 	if (unlikely(da_mon && !da_get_target(da_mon)))
 		container_of(da_mon, struct da_monitor_storage, rv.da_mon)->target = target;
 	return da_mon;
 }

 /*
  * da_get_target_by_id - return the object associated to the id
  */
 static inline monitor_target da_get_target_by_id(da_id_type id)
 {
 	struct da_monitor_storage *mon_storage;

 	guard(rcu)();
 	mon_storage = __da_get_mon_storage(id);

 	if (unlikely(!mon_storage))
 		return NULL;
 	return mon_storage->target;
 }

 /*
  * da_destroy_storage - destroy the per-object storage
  *
  * The caller is responsible to synchronise writers, either with locks or
  * implicitly. For instance, if da_destroy_storage is called at sched_exit and
  * da_create_storage can never occur after that, it's safe to call this without
  * locks.
  * This function includes an RCU read-side critical section to synchronise
  * against da_monitor_destroy().
  */
 static inline void da_destroy_storage(da_id_type id)
 {
 	struct da_monitor_storage *mon_storage;

 	guard(rcu)();
 	mon_storage = __da_get_mon_storage(id);

 	if (!mon_storage)
 		return;
 	da_monitor_reset_hook(&mon_storage->rv.da_mon);
 	hash_del_rcu(&mon_storage->node);
 	kfree_rcu(mon_storage, rcu);
 }

 static void da_monitor_reset_all(void)
 {
 	struct da_monitor_storage *mon_storage;
 	int bkt;

 	rcu_read_lock();
 	hash_for_each_rcu(da_monitor_ht, bkt, mon_storage, node)
 		da_monitor_reset(&mon_storage->rv.da_mon);
 	rcu_read_unlock();
 }

 static inline int da_monitor_init(void)
 {
 	hash_init(da_monitor_ht);
 	return 0;
 }

 static inline void da_monitor_destroy(void)
 {
 	struct da_monitor_storage *mon_storage;
 	struct hlist_node *tmp;
 	int bkt;

 	/*
 	 * This function is called after all probes are disabled, we need only
 	 * worry about concurrency against old events.
 	 */
 	synchronize_rcu();
 	hash_for_each_safe(da_monitor_ht, bkt, tmp, mon_storage, node) {
 		da_monitor_reset_hook(&mon_storage->rv.da_mon);
 		hash_del_rcu(&mon_storage->node);
 		kfree(mon_storage);
 	}
 }

 /*
  * Allow the per-object monitors to run allocation manually, necessary if the
  * start condition is in a context problematic for allocation (e.g. scheduling).
  * In such case, if the storage was pre-allocated without a target, set it now.
  */
 #ifdef DA_SKIP_AUTO_ALLOC
 #define da_prepare_storage da_fill_empty_storage
 #else
 #define da_prepare_storage da_create_storage
 #endif /* DA_SKIP_AUTO_ALLOC */

 #endif /* RV_MON_TYPE */

 #if RV_MON_TYPE == RV_MON_GLOBAL || RV_MON_TYPE == RV_MON_PER_CPU
 /*
  * Trace events for implicit monitors. Implicit monitor is the one which the
  * handler does not need to specify which da_monitor to manipulate. Examples
  * of implicit monitor are the per_cpu or the global ones.
  */

 static inline void da_trace_event(struct da_monitor *da_mon,
 				  char *curr_state, char *event,
 				  char *next_state, bool is_final,
 				  da_id_type id)
 {
 	CONCATENATE(trace_event_, MONITOR_NAME)(curr_state, event, next_state,
 						is_final);
 }

 static inline void da_trace_error(struct da_monitor *da_mon,
 				  char *curr_state, char *event,
 				  da_id_type id)
 {
 	CONCATENATE(trace_error_, MONITOR_NAME)(curr_state, event);
 }

 /*
  * da_get_id - unused for implicit monitors
  */
 static inline da_id_type da_get_id(struct da_monitor *da_mon)
 {
 	return 0;
 }

 #elif RV_MON_TYPE == RV_MON_PER_TASK || RV_MON_TYPE == RV_MON_PER_OBJ
 /*
  * Trace events for per_task/per_object monitors, report the target id.
  */

 static inline void da_trace_event(struct da_monitor *da_mon,
 				  char *curr_state, char *event,
 				  char *next_state, bool is_final,
 				  da_id_type id)
 {
 	CONCATENATE(trace_event_, MONITOR_NAME)(id, curr_state, event,
 						next_state, is_final);
 }

 static inline void da_trace_error(struct da_monitor *da_mon,
 				  char *curr_state, char *event,
 				  da_id_type id)
 {
 	CONCATENATE(trace_error_, MONITOR_NAME)(id, curr_state, event);
 }
 #endif /* RV_MON_TYPE */

 /*
  * da_event - handle an event for the da_mon
  *
  * This function is valid for both implicit and id monitors.
  * Retry in case there is a race between getting and setting the next state,
  * warn and reset the monitor if it runs out of retries. The monitor should be
  * able to handle various orders.
  */
 static inline bool da_event(struct da_monitor *da_mon, enum events event, da_id_type id)
 {
 	enum states curr_state, next_state;

 	curr_state = READ_ONCE(da_mon->curr_state);
 	for (int i = 0; i < MAX_DA_RETRY_RACING_EVENTS; i++) {
 		next_state = model_get_next_state(curr_state, event);
 		if (next_state == INVALID_STATE) {
 			react(curr_state, event);
 			da_trace_error(da_mon, model_get_state_name(curr_state),
 				       model_get_event_name(event), id);
 			return false;
 		}
 		if (likely(try_cmpxchg(&da_mon->curr_state, &curr_state, next_state))) {
 			if (!da_monitor_event_hook(da_mon, curr_state, event, next_state, id))
 				return false;
 			da_trace_event(da_mon, model_get_state_name(curr_state),
 				       model_get_event_name(event),
 				       model_get_state_name(next_state),
 				       model_is_final_state(next_state), id);
 			return true;
 		}
 	}

 	trace_rv_retries_error(__stringify(MONITOR_NAME), model_get_event_name(event));
 	pr_warn("rv: " __stringify(MAX_DA_RETRY_RACING_EVENTS)
 		" retries reached for event %s, resetting monitor %s",
 		model_get_event_name(event), __stringify(MONITOR_NAME));
 	return false;
 }

 static inline void __da_handle_event_common(struct da_monitor *da_mon,
 					    enum events event, da_id_type id)
 {
 	if (!da_event(da_mon, event, id))
 		da_monitor_reset(da_mon);
 }

 static inline void __da_handle_event(struct da_monitor *da_mon,
 				     enum events event, da_id_type id)
 {
 	if (da_monitor_handling_event(da_mon))
 		__da_handle_event_common(da_mon, event, id);
 }

 static inline bool __da_handle_start_event(struct da_monitor *da_mon,
 					   enum events event, da_id_type id)
 {
 	if (!da_monitor_enabled())
 		return 0;
 	if (unlikely(!da_monitoring(da_mon))) {
 		da_monitor_start(da_mon);
 		return 0;
 	}

 	__da_handle_event_common(da_mon, event, id);

 	return 1;
 }

 static inline bool __da_handle_start_run_event(struct da_monitor *da_mon,
 					       enum events event, da_id_type id)
 {
 	if (!da_monitor_enabled())
 		return 0;
 	if (unlikely(!da_monitoring(da_mon)))
 		da_monitor_start(da_mon);

 	__da_handle_event_common(da_mon, event, id);

 	return 1;
 }

 #if RV_MON_TYPE == RV_MON_GLOBAL || RV_MON_TYPE == RV_MON_PER_CPU
 /*
  * Handle event for implicit monitor: da_get_monitor() will figure out
  * the monitor.
  */

 /*
  * da_handle_event - handle an event
  */
 static inline void da_handle_event(enum events event)
 {
 	__da_handle_event(da_get_monitor(), event, 0);
 }

 /*
  * da_handle_start_event - start monitoring or handle event
  *
  * This function is used to notify the monitor that the system is returning
  * to the initial state, so the monitor can start monitoring in the next event.
  * Thus:
  *
  * If the monitor already started, handle the event.
  * If the monitor did not start yet, start the monitor but skip the event.
  */
 static inline bool da_handle_start_event(enum events event)
 {
 	return __da_handle_start_event(da_get_monitor(), event, 0);
 }

 /*
  * da_handle_start_run_event - start monitoring and handle event
  *
  * This function is used to notify the monitor that the system is in the
  * initial state, so the monitor can start monitoring and handling event.
  */
 static inline bool da_handle_start_run_event(enum events event)
 {
 	return __da_handle_start_run_event(da_get_monitor(), event, 0);
 }

 #elif RV_MON_TYPE == RV_MON_PER_TASK
 /*
  * Handle event for per task.
  */

 /*
  * da_handle_event - handle an event
  */
 static inline void da_handle_event(struct task_struct *tsk, enum events event)
 {
 	__da_handle_event(da_get_monitor(tsk), event, tsk->pid);
 }

 /*
  * da_handle_start_event - start monitoring or handle event
  *
  * This function is used to notify the monitor that the system is returning
  * to the initial state, so the monitor can start monitoring in the next event.
  * Thus:
  *
  * If the monitor already started, handle the event.
  * If the monitor did not start yet, start the monitor but skip the event.
  */
 static inline bool da_handle_start_event(struct task_struct *tsk,
 					 enum events event)
 {
 	return __da_handle_start_event(da_get_monitor(tsk), event, tsk->pid);
 }

 /*
  * da_handle_start_run_event - start monitoring and handle event
  *
  * This function is used to notify the monitor that the system is in the
  * initial state, so the monitor can start monitoring and handling event.
  */
 static inline bool da_handle_start_run_event(struct task_struct *tsk,
 					     enum events event)
 {
 	return __da_handle_start_run_event(da_get_monitor(tsk), event, tsk->pid);
 }

 #elif RV_MON_TYPE == RV_MON_PER_OBJ
 /*
  * Handle event for per object.
  */

 /*
  * da_handle_event - handle an event
  */
 static inline void da_handle_event(da_id_type id, monitor_target target, enum events event)
 {
 	struct da_monitor *da_mon;

 	guard(rcu)();
 	da_mon = da_get_monitor(id, target);
 	if (likely(da_mon))
 		__da_handle_event(da_mon, event, id);
 }

 /*
  * da_handle_start_event - start monitoring or handle event
  *
  * This function is used to notify the monitor that the system is returning
  * to the initial state, so the monitor can start monitoring in the next event.
  * Thus:
  *
  * If the monitor already started, handle the event.
  * If the monitor did not start yet, start the monitor but skip the event.
  */
 static inline bool da_handle_start_event(da_id_type id, monitor_target target,
 					 enum events event)
 {
 	struct da_monitor *da_mon;

 	guard(rcu)();
 	da_mon = da_get_monitor(id, target);
 	da_mon = da_prepare_storage(id, target, da_mon);
 	if (unlikely(!da_mon))
 		return 0;
 	return __da_handle_start_event(da_mon, event, id);
 }

 /*
  * da_handle_start_run_event - start monitoring and handle event
  *
  * This function is used to notify the monitor that the system is in the
  * initial state, so the monitor can start monitoring and handling event.
  */
 static inline bool da_handle_start_run_event(da_id_type id, monitor_target target,
 					     enum events event)
 {
 	struct da_monitor *da_mon;

 	guard(rcu)();
 	da_mon = da_get_monitor(id, target);
 	da_mon = da_prepare_storage(id, target, da_mon);
 	if (unlikely(!da_mon))
 		return 0;
 	return __da_handle_start_run_event(da_mon, event, id);
 }

 static inline void da_reset(da_id_type id, monitor_target target)
 {
 	struct da_monitor *da_mon;

 	guard(rcu)();
 	da_mon = da_get_monitor(id, target);
 	if (likely(da_mon))
 		da_monitor_reset(da_mon);
 }
 #endif /* RV_MON_TYPE */

 #endif
	/* SPDX-License-Identifier: GPL-2.0 */
	/*
	* Copyright (C) 2019-2022 Red Hat, Inc. Daniel Bristot de Oliveira <bristot@kernel.org>
	*
	* Deterministic automata (DA) monitor functions, to be used together
	* with automata models in C generated by the rvgen tool.
	*
	* The rvgen tool is available at tools/verification/rvgen/
	*
	* For further information, see:
	* Documentation/trace/rv/monitor_synthesis.rst
	*/

	#ifndef _RV_DA_MONITOR_H
	#define _RV_DA_MONITOR_H

	#include <rv/automata.h>
	#include <linux/rv.h>
	#include <linux/stringify.h>
	#include <linux/bug.h>
	#include <linux/sched.h>
	#include <linux/slab.h>
	#include <linux/hashtable.h>

	/*
	* Per-cpu variables require a unique name although static in some
	* configurations (e.g. CONFIG_DEBUG_FORCE_WEAK_PER_CPU or alpha modules).
	*/
	#define DA_MON_NAME CONCATENATE(da_mon_, MONITOR_NAME)

	static struct rv_monitor rv_this;

	/*
	* Hook to allow the implementation of hybrid automata: define it with a
	* function that takes curr_state, event and next_state and returns true if the
	* environment constraints (e.g. timing) are satisfied, false otherwise.
	*/
	#ifndef da_monitor_event_hook
	#define da_monitor_event_hook(...) true
	#endif

	/*
	* Hook to allow the implementation of hybrid automata: define it with a
	* function that takes the da_monitor and performs further initialisation
	* (e.g. reset set up timers).
	*/
	#ifndef da_monitor_init_hook
	#define da_monitor_init_hook(da_mon)
	#endif

	/*
	* Hook to allow the implementation of hybrid automata: define it with a
	* function that takes the da_monitor and performs further reset (e.g. reset
	* all clocks).
	*/
	#ifndef da_monitor_reset_hook
	#define da_monitor_reset_hook(da_mon)
	#endif

	/*
	* Type for the target id, default to int but can be overridden.
	* A long type can work as hash table key (PER_OBJ) but will be downgraded to
	* int in the event tracepoint.
	* Unused for implicit monitors.
	*/
	#ifndef da_id_type
	#define da_id_type int
	#endif

	static void react(enum states curr_state, enum events event)
	{
	rv_react(&rv_this,
	"rv: monitor %s does not allow event %s on state %s\n",
	__stringify(MONITOR_NAME),
	model_get_event_name(event),
	model_get_state_name(curr_state));
	}

	/*
	* da_monitor_reset - reset a monitor and setting it to init state
	*/
	static inline void da_monitor_reset(struct da_monitor *da_mon)
	{
	da_monitor_reset_hook(da_mon);
	da_mon->monitoring = 0;
	da_mon->curr_state = model_get_initial_state();
	}

	/*
	* da_monitor_start - start monitoring
	*
	* The monitor will ignore all events until monitoring is set to true. This
	* function needs to be called to tell the monitor to start monitoring.
	*/
	static inline void da_monitor_start(struct da_monitor *da_mon)
	{
	da_mon->curr_state = model_get_initial_state();
	da_mon->monitoring = 1;
	da_monitor_init_hook(da_mon);
	}

	/*
	* da_monitoring - returns true if the monitor is processing events
	*/
	static inline bool da_monitoring(struct da_monitor *da_mon)
	{
	return da_mon->monitoring;
	}

	/*
	* da_monitor_enabled - checks if the monitor is enabled
	*/
	static inline bool da_monitor_enabled(void)
	{
	/* global switch */
	if (unlikely(!rv_monitoring_on()))
	return 0;

	/* monitor enabled */
	if (unlikely(!rv_this.enabled))
	return 0;

	return 1;
	}

	/*
	* da_monitor_handling_event - checks if the monitor is ready to handle events
	*/
	static inline bool da_monitor_handling_event(struct da_monitor *da_mon)
	{
	if (!da_monitor_enabled())
	return 0;

	/* monitor is actually monitoring */
	if (unlikely(!da_monitoring(da_mon)))
	return 0;

	return 1;
	}

	#if RV_MON_TYPE == RV_MON_GLOBAL
	/*
	* Functions to define, init and get a global monitor.
	*/

	/*
	* global monitor (a single variable)
	*/
	static struct da_monitor DA_MON_NAME;

	/*
	* da_get_monitor - return the global monitor address
	*/
	static struct da_monitor *da_get_monitor(void)
	{
	return &DA_MON_NAME;
	}

	/*
	* da_monitor_reset_all - reset the single monitor
	*/
	static void da_monitor_reset_all(void)
	{
	da_monitor_reset(da_get_monitor());
	}

	/*
	* da_monitor_init - initialize a monitor
	*/
	static inline int da_monitor_init(void)
	{
	da_monitor_reset_all();
	return 0;
	}

	/*
	* da_monitor_destroy - destroy the monitor
	*/
	static inline void da_monitor_destroy(void)
	{
	da_monitor_reset_all();
	}

	#elif RV_MON_TYPE == RV_MON_PER_CPU
	/*
	* Functions to define, init and get a per-cpu monitor.
	*/

	/*
	* per-cpu monitor variables
	*/
	static DEFINE_PER_CPU(struct da_monitor, DA_MON_NAME);

	/*
	* da_get_monitor - return current CPU monitor address
	*/
	static struct da_monitor *da_get_monitor(void)
	{
	return this_cpu_ptr(&DA_MON_NAME);
	}

	/*
	* da_monitor_reset_all - reset all CPUs' monitor
	*/
	static void da_monitor_reset_all(void)
	{
	struct da_monitor *da_mon;
	int cpu;

	for_each_cpu(cpu, cpu_online_mask) {
	da_mon = per_cpu_ptr(&DA_MON_NAME, cpu);
	da_monitor_reset(da_mon);
	}
	}

	/*
	* da_monitor_init - initialize all CPUs' monitor
	*/
	static inline int da_monitor_init(void)
	{
	da_monitor_reset_all();
	return 0;
	}

	/*
	* da_monitor_destroy - destroy the monitor
	*/
	static inline void da_monitor_destroy(void)
	{
	da_monitor_reset_all();
	}

	#elif RV_MON_TYPE == RV_MON_PER_TASK
	/*
	* Functions to define, init and get a per-task monitor.
	*/

	/*
	* The per-task monitor is stored a vector in the task struct. This variable
	* stores the position on the vector reserved for this monitor.
	*/
	static int task_mon_slot = RV_PER_TASK_MONITOR_INIT;

	/*
	* da_get_monitor - return the monitor in the allocated slot for tsk
	*/
	static inline struct da_monitor da_get_monitor(struct task_struct tsk)
	{
	return &tsk->rv[task_mon_slot].da_mon;
	}

	/*
	* da_get_target - return the task associated to the monitor
	*/
	static inline struct task_struct da_get_target(struct da_monitor da_mon)
	{
	return container_of(da_mon, struct task_struct, rv[task_mon_slot].da_mon);
	}

	/*
	* da_get_id - return the id associated to the monitor
	*
	* For per-task monitors, the id is the task's PID.
	*/
	static inline da_id_type da_get_id(struct da_monitor *da_mon)
	{
	return da_get_target(da_mon)->pid;
	}

	static void da_monitor_reset_all(void)
	{
	struct task_struct g, p;
	int cpu;

	read_lock(&tasklist_lock);
	for_each_process_thread(g, p)
	da_monitor_reset(da_get_monitor(p));
	for_each_present_cpu(cpu)
	da_monitor_reset(da_get_monitor(idle_task(cpu)));
	read_unlock(&tasklist_lock);
	}

	/*
	* da_monitor_init - initialize the per-task monitor
	*
	* Try to allocate a slot in the task's vector of monitors. If there
	* is an available slot, use it and reset all task's monitor.
	*/
	static int da_monitor_init(void)
	{
	int slot;

	slot = rv_get_task_monitor_slot();
	if (slot < 0 \|\| slot >= RV_PER_TASK_MONITOR_INIT)
	return slot;

	task_mon_slot = slot;

	da_monitor_reset_all();
	return 0;
	}

	/*
	* da_monitor_destroy - return the allocated slot
	*/
	static inline void da_monitor_destroy(void)
	{
	if (task_mon_slot == RV_PER_TASK_MONITOR_INIT) {
	WARN_ONCE(1, "Disabling a disabled monitor: " __stringify(MONITOR_NAME));
	return;
	}
	rv_put_task_monitor_slot(task_mon_slot);
	task_mon_slot = RV_PER_TASK_MONITOR_INIT;

	da_monitor_reset_all();
	}

	#elif RV_MON_TYPE == RV_MON_PER_OBJ
	/*
	* Functions to define, init and get a per-object monitor.
	*/

	struct da_monitor_storage {
	da_id_type id;
	monitor_target target;
	union rv_task_monitor rv;
	struct hlist_node node;
	struct rcu_head rcu;
	};

	#ifndef DA_MONITOR_HT_BITS
	#define DA_MONITOR_HT_BITS 10
	#endif
	static DEFINE_HASHTABLE(da_monitor_ht, DA_MONITOR_HT_BITS);

	/*
	* da_create_empty_storage - pre-allocate an empty storage
	*/
	static inline struct da_monitor_storage *da_create_empty_storage(da_id_type id)
	{
	struct da_monitor_storage *mon_storage;

	mon_storage = kmalloc_nolock(sizeof(struct da_monitor_storage),
	__GFP_ZERO, NUMA_NO_NODE);
	if (!mon_storage)
	return NULL;

	hash_add_rcu(da_monitor_ht, &mon_storage->node, id);
	mon_storage->id = id;
	return mon_storage;
	}

	/*
	* da_create_storage - create the per-object storage
	*
	* The caller is responsible to synchronise writers, either with locks or
	* implicitly. For instance, if da_create_storage is only called from a single
	* event for target (e.g. sched_switch), it's safe to call this without locks.
	*/
	static inline struct da_monitor *da_create_storage(da_id_type id,
	monitor_target target,
	struct da_monitor *da_mon)
	{
	struct da_monitor_storage *mon_storage;

	if (da_mon)
	return da_mon;

	mon_storage = da_create_empty_storage(id);
	if (!mon_storage)
	return NULL;

	mon_storage->target = target;
	return &mon_storage->rv.da_mon;
	}

	/*
	* __da_get_mon_storage - get the monitor storage from the hash table
	*/
	static inline struct da_monitor_storage *__da_get_mon_storage(da_id_type id)
	{
	struct da_monitor_storage *mon_storage;

	lockdep_assert_in_rcu_read_lock();
	hash_for_each_possible_rcu(da_monitor_ht, mon_storage, node, id) {
	if (mon_storage->id == id)
	return mon_storage;
	}

	return NULL;
	}

	/*
	* da_get_monitor - return the monitor for target
	*/
	static struct da_monitor *da_get_monitor(da_id_type id, monitor_target target)
	{
	struct da_monitor_storage *mon_storage;

	mon_storage = __da_get_mon_storage(id);
	return mon_storage ? &mon_storage->rv.da_mon : NULL;
	}

	/*
	* da_get_target - return the object associated to the monitor
	*/
	static inline monitor_target da_get_target(struct da_monitor *da_mon)
	{
	return container_of(da_mon, struct da_monitor_storage, rv.da_mon)->target;
	}

	/*
	* da_get_id - return the id associated to the monitor
	*/
	static inline da_id_type da_get_id(struct da_monitor *da_mon)
	{
	return container_of(da_mon, struct da_monitor_storage, rv.da_mon)->id;
	}

	/*
	* da_create_or_get - create the per-object storage if not already there
	*
	* This needs a lookup so should be guarded by RCU, the condition is checked
	* directly in da_create_storage()
	*/
	static inline void da_create_or_get(da_id_type id, monitor_target target)
	{
	guard(rcu)();
	da_create_storage(id, target, da_get_monitor(id, target));
	}

	/*
	* da_fill_empty_storage - store the target in a pre-allocated storage
	*
	* Can be used as a substitute of da_create_storage when starting a monitor in
	* an environment where allocation is unsafe.
	*/
	static inline struct da_monitor *da_fill_empty_storage(da_id_type id,
	monitor_target target,
	struct da_monitor *da_mon)
	{
	if (unlikely(da_mon && !da_get_target(da_mon)))
	container_of(da_mon, struct da_monitor_storage, rv.da_mon)->target = target;
	return da_mon;
	}

	/*
	* da_get_target_by_id - return the object associated to the id
	*/
	static inline monitor_target da_get_target_by_id(da_id_type id)
	{
	struct da_monitor_storage *mon_storage;

	guard(rcu)();
	mon_storage = __da_get_mon_storage(id);

	if (unlikely(!mon_storage))
	return NULL;
	return mon_storage->target;
	}

	/*
	* da_destroy_storage - destroy the per-object storage
	*
	* The caller is responsible to synchronise writers, either with locks or
	* implicitly. For instance, if da_destroy_storage is called at sched_exit and
	* da_create_storage can never occur after that, it's safe to call this without
	* locks.
	* This function includes an RCU read-side critical section to synchronise
	* against da_monitor_destroy().
	*/
	static inline void da_destroy_storage(da_id_type id)
	{
	struct da_monitor_storage *mon_storage;

	guard(rcu)();
	mon_storage = __da_get_mon_storage(id);

	if (!mon_storage)
	return;
	da_monitor_reset_hook(&mon_storage->rv.da_mon);
	hash_del_rcu(&mon_storage->node);
	kfree_rcu(mon_storage, rcu);
	}

	static void da_monitor_reset_all(void)
	{
	struct da_monitor_storage *mon_storage;
	int bkt;

	rcu_read_lock();
	hash_for_each_rcu(da_monitor_ht, bkt, mon_storage, node)
	da_monitor_reset(&mon_storage->rv.da_mon);
	rcu_read_unlock();
	}

	static inline int da_monitor_init(void)
	{
	hash_init(da_monitor_ht);
	return 0;
	}

	static inline void da_monitor_destroy(void)
	{
	struct da_monitor_storage *mon_storage;
	struct hlist_node *tmp;
	int bkt;

	/*
	* This function is called after all probes are disabled, we need only
	* worry about concurrency against old events.
	*/
	synchronize_rcu();
	hash_for_each_safe(da_monitor_ht, bkt, tmp, mon_storage, node) {
	da_monitor_reset_hook(&mon_storage->rv.da_mon);
	hash_del_rcu(&mon_storage->node);
	kfree(mon_storage);
	}
	}

	/*
	* Allow the per-object monitors to run allocation manually, necessary if the
	* start condition is in a context problematic for allocation (e.g. scheduling).
	* In such case, if the storage was pre-allocated without a target, set it now.
	*/
	#ifdef DA_SKIP_AUTO_ALLOC
	#define da_prepare_storage da_fill_empty_storage
	#else
	#define da_prepare_storage da_create_storage
	#endif /* DA_SKIP_AUTO_ALLOC */

	#endif /* RV_MON_TYPE */

	#if RV_MON_TYPE == RV_MON_GLOBAL \|\| RV_MON_TYPE == RV_MON_PER_CPU
	/*
	* Trace events for implicit monitors. Implicit monitor is the one which the
	* handler does not need to specify which da_monitor to manipulate. Examples
	* of implicit monitor are the per_cpu or the global ones.
	*/

	static inline void da_trace_event(struct da_monitor *da_mon,
	char curr_state, char event,
	char *next_state, bool is_final,
	da_id_type id)
	{
	CONCATENATE(trace_event_, MONITOR_NAME)(curr_state, event, next_state,
	is_final);
	}

	static inline void da_trace_error(struct da_monitor *da_mon,
	char curr_state, char event,
	da_id_type id)
	{
	CONCATENATE(trace_error_, MONITOR_NAME)(curr_state, event);
	}

	/*
	* da_get_id - unused for implicit monitors
	*/
	static inline da_id_type da_get_id(struct da_monitor *da_mon)
	{
	return 0;
	}

	#elif RV_MON_TYPE == RV_MON_PER_TASK \|\| RV_MON_TYPE == RV_MON_PER_OBJ
	/*
	* Trace events for per_task/per_object monitors, report the target id.
	*/

	static inline void da_trace_event(struct da_monitor *da_mon,
	char curr_state, char event,
	char *next_state, bool is_final,
	da_id_type id)
	{
	CONCATENATE(trace_event_, MONITOR_NAME)(id, curr_state, event,
	next_state, is_final);
	}

	static inline void da_trace_error(struct da_monitor *da_mon,
	char curr_state, char event,
	da_id_type id)
	{
	CONCATENATE(trace_error_, MONITOR_NAME)(id, curr_state, event);
	}
	#endif /* RV_MON_TYPE */

	/*
	* da_event - handle an event for the da_mon
	*
	* This function is valid for both implicit and id monitors.
	* Retry in case there is a race between getting and setting the next state,
	* warn and reset the monitor if it runs out of retries. The monitor should be
	* able to handle various orders.
	*/
	static inline bool da_event(struct da_monitor *da_mon, enum events event, da_id_type id)
	{
	enum states curr_state, next_state;

	curr_state = READ_ONCE(da_mon->curr_state);
	for (int i = 0; i < MAX_DA_RETRY_RACING_EVENTS; i++) {
	next_state = model_get_next_state(curr_state, event);
	if (next_state == INVALID_STATE) {
	react(curr_state, event);
	da_trace_error(da_mon, model_get_state_name(curr_state),
	model_get_event_name(event), id);
	return false;
	}
	if (likely(try_cmpxchg(&da_mon->curr_state, &curr_state, next_state))) {
	if (!da_monitor_event_hook(da_mon, curr_state, event, next_state, id))
	return false;
	da_trace_event(da_mon, model_get_state_name(curr_state),
	model_get_event_name(event),
	model_get_state_name(next_state),
	model_is_final_state(next_state), id);
	return true;
	}
	}

	trace_rv_retries_error(__stringify(MONITOR_NAME), model_get_event_name(event));
	pr_warn("rv: " __stringify(MAX_DA_RETRY_RACING_EVENTS)
	" retries reached for event %s, resetting monitor %s",
	model_get_event_name(event), __stringify(MONITOR_NAME));
	return false;
	}

	static inline void __da_handle_event_common(struct da_monitor *da_mon,
	enum events event, da_id_type id)
	{
	if (!da_event(da_mon, event, id))
	da_monitor_reset(da_mon);
	}

	static inline void __da_handle_event(struct da_monitor *da_mon,
	enum events event, da_id_type id)
	{
	if (da_monitor_handling_event(da_mon))
	__da_handle_event_common(da_mon, event, id);
	}

	static inline bool __da_handle_start_event(struct da_monitor *da_mon,
	enum events event, da_id_type id)
	{
	if (!da_monitor_enabled())
	return 0;
	if (unlikely(!da_monitoring(da_mon))) {
	da_monitor_start(da_mon);
	return 0;
	}

	__da_handle_event_common(da_mon, event, id);

	return 1;
	}

	static inline bool __da_handle_start_run_event(struct da_monitor *da_mon,
	enum events event, da_id_type id)
	{
	if (!da_monitor_enabled())
	return 0;
	if (unlikely(!da_monitoring(da_mon)))
	da_monitor_start(da_mon);

	__da_handle_event_common(da_mon, event, id);

	return 1;
	}

	#if RV_MON_TYPE == RV_MON_GLOBAL \|\| RV_MON_TYPE == RV_MON_PER_CPU
	/*
	* Handle event for implicit monitor: da_get_monitor() will figure out
	* the monitor.
	*/

	/*
	* da_handle_event - handle an event
	*/
	static inline void da_handle_event(enum events event)
	{
	__da_handle_event(da_get_monitor(), event, 0);
	}

	/*
	* da_handle_start_event - start monitoring or handle event
	*
	* This function is used to notify the monitor that the system is returning
	* to the initial state, so the monitor can start monitoring in the next event.
	* Thus:
	*
	* If the monitor already started, handle the event.
	* If the monitor did not start yet, start the monitor but skip the event.
	*/
	static inline bool da_handle_start_event(enum events event)
	{
	return __da_handle_start_event(da_get_monitor(), event, 0);
	}

	/*
	* da_handle_start_run_event - start monitoring and handle event
	*
	* This function is used to notify the monitor that the system is in the
	* initial state, so the monitor can start monitoring and handling event.
	*/
	static inline bool da_handle_start_run_event(enum events event)
	{
	return __da_handle_start_run_event(da_get_monitor(), event, 0);
	}

	#elif RV_MON_TYPE == RV_MON_PER_TASK
	/*
	* Handle event for per task.
	*/

	/*
	* da_handle_event - handle an event
	*/
	static inline void da_handle_event(struct task_struct *tsk, enum events event)
	{
	__da_handle_event(da_get_monitor(tsk), event, tsk->pid);
	}

	/*
	* da_handle_start_event - start monitoring or handle event
	*
	* This function is used to notify the monitor that the system is returning
	* to the initial state, so the monitor can start monitoring in the next event.
	* Thus:
	*
	* If the monitor already started, handle the event.
	* If the monitor did not start yet, start the monitor but skip the event.
	*/
	static inline bool da_handle_start_event(struct task_struct *tsk,
	enum events event)
	{
	return __da_handle_start_event(da_get_monitor(tsk), event, tsk->pid);
	}

	/*
	* da_handle_start_run_event - start monitoring and handle event
	*
	* This function is used to notify the monitor that the system is in the
	* initial state, so the monitor can start monitoring and handling event.
	*/
	static inline bool da_handle_start_run_event(struct task_struct *tsk,
	enum events event)
	{
	return __da_handle_start_run_event(da_get_monitor(tsk), event, tsk->pid);
	}

	#elif RV_MON_TYPE == RV_MON_PER_OBJ
	/*
	* Handle event for per object.
	*/

	/*
	* da_handle_event - handle an event
	*/
	static inline void da_handle_event(da_id_type id, monitor_target target, enum events event)
	{
	struct da_monitor *da_mon;

	guard(rcu)();
	da_mon = da_get_monitor(id, target);
	if (likely(da_mon))
	__da_handle_event(da_mon, event, id);
	}

	/*
	* da_handle_start_event - start monitoring or handle event
	*
	* This function is used to notify the monitor that the system is returning
	* to the initial state, so the monitor can start monitoring in the next event.
	* Thus:
	*
	* If the monitor already started, handle the event.
	* If the monitor did not start yet, start the monitor but skip the event.
	*/
	static inline bool da_handle_start_event(da_id_type id, monitor_target target,
	enum events event)
	{
	struct da_monitor *da_mon;

	guard(rcu)();
	da_mon = da_get_monitor(id, target);
	da_mon = da_prepare_storage(id, target, da_mon);
	if (unlikely(!da_mon))
	return 0;
	return __da_handle_start_event(da_mon, event, id);
	}

	/*
	* da_handle_start_run_event - start monitoring and handle event
	*
	* This function is used to notify the monitor that the system is in the
	* initial state, so the monitor can start monitoring and handling event.
	*/
	static inline bool da_handle_start_run_event(da_id_type id, monitor_target target,
	enum events event)
	{
	struct da_monitor *da_mon;

	guard(rcu)();
	da_mon = da_get_monitor(id, target);
	da_mon = da_prepare_storage(id, target, da_mon);
	if (unlikely(!da_mon))
	return 0;
	return __da_handle_start_run_event(da_mon, event, id);
	}

	static inline void da_reset(da_id_type id, monitor_target target)
	{
	struct da_monitor *da_mon;

	guard(rcu)();
	da_mon = da_get_monitor(id, target);
	if (likely(da_mon))
	da_monitor_reset(da_mon);
	}
	#endif /* RV_MON_TYPE */

	#endif