Documentation/trace/rv/deterministic_automata.rst

Source file repositories/reference/linux-study-clean/Documentation/trace/rv/deterministic_automata.rst

File Facts

System
Linux kernel
Corpus path
Documentation/trace/rv/deterministic_automata.rst
Extension
.rst
Size
6409 bytes
Lines
185
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

struct automaton {
	char *state_names[state_max];                   // X: the set of states
	char *event_names[event_max];                   // E: the finite set of events
	unsigned char function[state_max][event_max];   // f: transition function
	unsigned char initial_state;                    // x_0: the initial state
	bool final_states[state_max];                   // X_m: the set of marked states
  };

  struct automaton aut = {
	.state_names = {
		"preemptive",
		"non_preemptive"
	},
	.event_names = {
		"preempt_disable",
		"preempt_enable",
		"sched_waking"
	},
	.function = {
		{ non_preemptive,  INVALID_STATE,  INVALID_STATE },
		{  INVALID_STATE,     preemptive, non_preemptive },
	},
	.initial_state = preemptive,
	.final_states = { 1, 0 },
  };

The *transition function* is represented as a matrix of states (lines) and
events (columns), and so the function *f* : *X* x *E* -> *X* can be solved
in O(1). For example::

  next_state = automaton_wip.function[curr_state][event];

Graphviz .dot format
--------------------

The Graphviz open-source tool can produce the graphical representation
of an automaton using the (textual) DOT language as the source code.
The DOT format is widely used and can be converted to many other formats.

For example, this is the 'wip' model in DOT::

  digraph state_automaton {
        {node [shape = circle] "non_preemptive"};
        {node [shape = plaintext, style=invis, label=""] "__init_preemptive"};
        {node [shape = doublecircle] "preemptive"};
        {node [shape = circle] "preemptive"};
        "__init_preemptive" -> "preemptive";
        "non_preemptive" [label = "non_preemptive"];
        "non_preemptive" -> "non_preemptive" [ label = "sched_waking" ];
        "non_preemptive" -> "preemptive" [ label = "preempt_enable" ];
        "preemptive" [label = "preemptive"];
        "preemptive" -> "non_preemptive" [ label = "preempt_disable" ];
        { rank = min ;
                "__init_preemptive";
                "preemptive";
        }
  }

This DOT format can be transformed into a bitmap or vectorial image
using the dot utility, or into an ASCII art using graph-easy. For
instance::

  $ dot -Tsvg -o wip.svg wip.dot
  $ graph-easy wip.dot > wip.txt

dot2c
-----

dot2c is a utility that can parse a .dot file containing an automaton as
in the example above and automatically convert it to the C representation

Annotation

Implementation Notes