code:
#
# \brief  Utilities for processing the output of Genode's 'parse_cxx'
# \author Norman Feske
# \date   2015-03-17
#

##
# Return last command-line argument, which is always the source token file
#
proc token_file {} {
	global argv
	return [lindex $argv end]
}

##
# Return path to source header file
#
proc header_file {} {
	regsub {.tokens$} [token_file] {} result
	return $result
}

##
# Return true if command-line switch was specified
#
proc get_cmd_switch { arg_name } {
	global argv
	return [expr [lsearch $argv $arg_name] >= 0]
}

##
# Return command-line argument value
#
# If a argument name is specified multiple times, return only the
# first match.
#
proc get_cmd_arg { arg_name default_value } {
	global argv

	set arg_idx [lsearch $argv $arg_name]

	if {$arg_idx == -1} { return $default_value }

	return [lindex $argv [expr $arg_idx + 1]]
}

##
# Return base URL for browsing the source code
#
# XXX evaluate command-line argument
#
proc code_url { } { return "https://github.com/genodelabs/genode/blob/22.05/" }

##
# Turn the first letter of a given string to upper case
#
# In contrast to Tcl's built-in 'string totitle' function, this function
# leaves the remaining characters untouched.
#
proc to_title {str} {
	return [string replace $str 0 0 [string toupper [string index $str 0]]]
}

##
# Read input file with token data
#
proc import_tokens {file_name} {
	global token_text

	# read token file
	set tokens [exec cat $file_name]

	# build dictionary of tokens
	foreach token $tokens {
		set name [lindex $token 0]
		set text [lindex $token 2]
		set token_text($name) "$text"
	}

	if {![info exists token_text(content0)]} {
		puts stderr "Error: input contains no root token 'content0'."
		exit -1
	}
}

##
# Return type of specified token
#
proc tok_type { token } {
	regexp {[a-z]+} $token type
	return $type
}

##
# Return text of specified token
#
proc tok_text { token } {
	global token_text
	return $token_text($token)
}

proc tok_valid { token } {
	return [string length $token]
}

##
# Execute functors 'plain_fn' and 'sub_token_fn' over a sequence of tokens
#
# The 'plain_fn' functor takes a plain-text snippet as argument.
# The 'sub_token_fn' functor takes a token as argument.
#
# \param plain_var      variable name of the 'plain_fn' argument
# \param sub_token_var  variable name of the 'sub_token_fn' argument
#
proc foreach_sub_token { sequence plain_var plain_fn sub_token_var sub_token_fn } {

	upvar $plain_var     plain
	upvar $sub_token_var sub_token

	while {$sequence != ""} {

		# consume plain text
		if {[regexp {^[^§]+} $sequence plain]} {
			uplevel 1 $plain_fn
			regsub {^[^§]+} $sequence "" sequence
		}

		# consume token
		if {[regexp {§(.+?)°} $sequence dummy sub_token]} {
			uplevel 1 $sub_token_fn
			regsub {§(.+?)°} $sequence "" sequence
		}
	}
}

##
# Turn tree of tokens into plain text
#
proc unfold_token {{token content0}} {

	set output ""

	if {![tok_valid $token]} { return "" }

	foreach_sub_token [tok_text $token] plain {

		# perform character substitutions for LaTeX compliance
		regsub -all {³} $plain "\\&" plain

		append output $plain
	} sub_token {
		append output [unfold_token $sub_token]
	}

	return $output
}

##
# Find and return a sub token of the specified type
#
proc sub_token {token token_type} {

	if {$token == ""} { return "" }
	if {[regexp "§($token_type\\d+)°" [tok_text $token] dummy sub_token]} {
		return $sub_token
	} else {
		return ""
	}
}

##
# Return class name of specified token
#
# The token may be of the types 'struct', 'class', 'tplstruct', or 'tplclass'.
#
proc class_name { token } {

	if {[tok_type $token] == "struct" || [tok_type $token] == "class"} {
		set name_token [sub_token $token identifier]
		set result [unfold_token $name_token]

		#
		# Strip template arguments from class name. This is needed for
		# classed defined within the scope of a class template, i.e.,
		# the 'Rpc_object::Capability_guard'.
		#
		regsub -all {<[^>]*>} $result "" result
		return $result
	}

	if {[tok_type $token] == "tplstruct"} {
		set struct_token [sub_token $token struct]
		return [class_name $struct_token]
	}

	if {[tok_type $token] == "tplclass"} {
		set class_token [sub_token $token class]
		return [class_name $class_token]
	}

	return ""
}

##
# Return true if token is a class template
#
proc is_class_template { token } {

	if {[tok_type $token] == "tplstruct" || [tok_type $token] == "tplclass"} {
		return 1 }

	return 0
}

##
# Return true if token is a function template
#
proc is_function_template { token } {

	if {[tok_type $token] == "tplfunc" || [tok_type $token] == "tplfuncdecl"} {
		return 1 }

	return 0
}

##
# Find class with specified name
#
proc find_class_by_name { token class_name } {

	set result ""
	foreach_sub_token [tok_text $token] plain { } token {

		if {[class_name $token] == "$class_name"} {
			set result $token;
		}
	}
	return $result
}

##
# Find function with specified name
#
proc find_func_by_name { token func_name } {

	set result ""
	foreach_sub_token [tok_text $token] plain { } token {

		if {[function_name $token] == "$func_name"} {
			set result $token;
		}
	}
	return $result
}

##
# Return list of the names of the public base classes of a class
#
proc public_base_classes { class_token } {

	if {[tok_type $class_token] == "tplclass"} {
		return [public_base_classes [sub_token $class_token class]] }

	if {[tok_type $class_token] == "tplstruct"} {
		return [public_base_classes [sub_token $class_token struct]] }

	set inherit_token [sub_token $class_token inherit]
	if {"$inherit_token" == ""} return ""

	set sequence [tok_text $inherit_token]

	set base_classes {}

	if {[tok_type $class_token] == "struct"} {

		# filter out private base classes from sequence
		regsub -all {§keyprivate\d+°\s*§identifier\d+°} $sequence {} sequence

		# append remaining identifiers
		foreach_sub_token $sequence plain { } token {
			if {[tok_type $token] == "identifier"} {
				lappend base_classes [unfold_token $token]
			}
		}
	}

	if {[tok_type $class_token] == "class"} {

		# match public base classes in sequence
		set pattern {§keypublic\d+°\s*§(identifier\d+)°}
		while {[regexp $pattern $sequence dummy identifier_token]} {

			lappend base_classes [unfold_token $identifier_token]

			# consume matched part of the sequence
			regsub $pattern $sequence {} sequence
		}
	}

	return $base_classes
}

##
# Return true if multi-line comment starts with "/**"
#
proc mlcomment_is_public { mlcomment } {

	return [regexp {^\s*/\*\*\n} $mlcomment]
}

##
# Parse multi-line comment
#
# The function returns a list of comment parts. A part may be a paragraph or a
# item that starts with "/".
#
proc parse_mlcomment { mlcomment } {

	# eliminate leading and trailing comment characters (/** and */)
	regsub {^/\*+\n} $mlcomment {} mlcomment
	regsub {\s*\*/$} $mlcomment {} mlcomment

	# list of parts
	set result {}

	# content of current part
	set part ""

	foreach line [split $mlcomment "\n"] {

		#
		# Remove leading whitespace and the '*' character. The '*' is normally
		# followed by a space, except when it is in front of an empty line.
		#
		regsub {^\s*\*} $line "" line
		regsub {^ }    $line "" line
		regsub {^\s+$} $line "" line

		# detect beginning of a new part
		if {$line == "" || [regexp {^\\} $line dummy]} {

			# append non-empty part to list
			if {$part != ""} {
				lappend result $part }

			# begin new part
			set part ""
		}

		#
		# Append current line to current part. Remove leading whitespace
		# that may be present if parameter descriptions span multiple lines.
		#
		regsub {^\s+} $line " " line

		if {$line != ""} {
			set part [concat $part " " $line] }
	}

	lappend result $part

	return $result
}

##
# Return the number of top-level classes in the header file
#
proc number_of_top_level_classes { } {

	set count 0
	foreach token_type { class struct classtpl structtpl } {
		incr count [regsub -all "§$token_type\\d+°" [tok_text content0] {} dummy]
	}
	return $count
}

##
# Return token for the multi-line comment in the file header
#
proc header_comment { } {

	set header_token [sub_token content0 mlcomment]

	if {[tok_valid $header_token]} {
		return [parse_mlcomment [tok_text $header_token]] }

	return ""
}

##
# Return brief comment in file header
#
proc header_brief_comment { } {

	foreach part [header_comment] {
		if {[regexp {^\\brief\s} $part]} {
			regsub {^\\brief\s+} $part "" part
			return $part
		}
	}
	return ""
}

##
# Return parsed multi-line comment for a function
#
proc function_comment { func_token } {

	set mlcomment_token [sub_token $func_token mlcomment]
	if {[tok_valid $mlcomment_token]} {
		return [parse_mlcomment [tok_text $mlcomment_token]] }

	return ""
}

##
# Return the brief description of a class
#
proc brief_class_description { class_token } {

	#
	# If the class is prepended with a multi-line comment, take the
	# brief description from there
	#
	set comment_token [sub_token $class_token mlcomment]
	if {[tok_valid $comment_token]} {

		set mlcomment [tok_text $comment_token]
		if {[mlcomment_is_public $mlcomment]} {

			set mlcomment_parts [parse_mlcomment $mlcomment]
			if {[llength $mlcomment_parts]} {
				return [lindex $mlcomment_parts 0]
			}
		}
	}

	#
	# Class lacks a valid multi-line comment. If the class is the only
	# class contained in the header, we use the header's brief description
	#
	if {[number_of_top_level_classes] == 1} {

		# search the mlcomment of the file header for a brief description
		return [header_brief_comment]
	}
	return ""
}

##
# Return true if class contains RPC annotations
#
proc class_is_rpc_interface { class_token } {

	set classblock_token [sub_token $class_token classblock]
	if {$classblock_token == ""} { return 0 }
	if {[sub_token $classblock_token genoderpc] != ""} { return 1 }
	return 0
}

##
# Return function token that is embedded in a template function token
#
proc tplfunc_function { tplfunc_token } {

	foreach token_type { funcdecl funcimpl constdecl constimpl destdecl destimpl } {
		set func_token [sub_token $tplfunc_token $token_type]
		if {$func_token != ""} {
			return $func_token }
	}
	return ""
}

proc function_is_operator { func_token } {

	set operatorfunction_token [sub_token $func_token operatorfunction]
	if {$operatorfunction_token != ""} { return 1 }
	return 0
}

##
# Return function name
#
proc function_name { func_token } {

	if {[is_function_template $func_token]} {
		set func_token [tplfunc_function $func_token] }

	if {[is_function $func_token]} {

		if {[function_is_operator $func_token]} {

			set operatorfunction_token [sub_token $func_token operatorfunction]
			set operator_name_token [sub_token $operatorfunction_token operator]
			set operator_name [concat [unfold_token $operator_name_token]]
			regsub {\s+} $operator_name " " operator_name
			return $operator_name

		} else {
			set funcsignature_token [sub_token $func_token          funcsignature]
			set name_token          [sub_token $funcsignature_token identifier]
			set tilde ""
			if {[sub_token $func_token tilde] != ""} { set tilde "~" }
			return "$tilde[unfold_token $name_token]"
		}
	}

	return ""
}

##
# Return the return type of a function
#
proc function_return_type { func_token } {

	if {[is_function_template $func_token]} {
		set func_token [tplfunc_function $func_token] }

	if {[is_function $func_token]} {
		set retval_token [sub_token $func_token retval]
		if {$retval_token != ""} {
			return [concat [unfold_token $retval_token]] }
	}

	return ""
}

##
# Return the multi-line comment of a compound token
#
proc mlcomment_parts { token } {

	set comment_token [sub_token $token mlcomment]
	if {[tok_valid $comment_token]} {

		set mlcomment [tok_text $comment_token]
		if {[mlcomment_is_public $mlcomment]} {

			return [parse_mlcomment $mlcomment]
		}
	}

	return {}
}

##
# Return the brief description of a function
#
proc function_brief_description { function_token } {

	set mlcomment_parts [mlcomment_parts $function_token]
	if {[llength $mlcomment_parts]} {

		set brief [concat [lindex $mlcomment_parts 0]]

		if {$brief == "Constructor" || $brief == "Destructor"} {
			return "" }

		#
		# Filter out brief descriptions starting with "Return" or "Returns".
		# This information is captured by 'function_return_value' instead.
		#
		if {[regexp {^Returns?\s+} $brief]} { return "" }

		return $brief
	}
	return ""
}

##
# Return list of paragraphs of the detailed description of a function
#
proc function_detailed_description { function_token } {

	set result {}
	set first 1
	foreach part [mlcomment_parts $function_token] {

		if {!$first && ![regexp {^\\} $part]} {
			lappend result $part }

		set first 0
	}
	return $result
}

##
# Return true if token is a function
#
proc is_function { token } {

	foreach token_type { funcdecl funcimpl constdecl constimpl destdecl destimpl tplfunc tplfuncdecl } {
		if {[tok_type $token] == "$token_type"} {
			if {![function_is_blacklisted $token]} {
				return 1 }
		}
	}

	return 0
}

##
# Return true if function is specified modifier
#
proc function_has_modifier { func_token modifier } {

	set modifier_token [sub_token $func_token modifier]
	if {$modifier_token != ""} {
		set modifiers [unfold_token $modifier_token]
		return [regexp $modifier $modifiers]
	}

	return 0
}

##
# Return true if is tagged with "\noapi" in its comment
#
proc function_is_blacklisted { func_token } {

	foreach part [mlcomment_parts $func_token] {
		if {[regexp {\\((noapi)|(deprecated))} $part]} { return 1 }
	}
	return 0;
}

proc function_is_static { func_token } {
	return [function_has_modifier $func_token static] }

proc function_is_virtual { func_token } {
	return [function_has_modifier $func_token virtual] }

proc function_is_pure_virtual { func_token } {
	return [expr {[sub_token $func_token virtassign] != ""}] }

proc function_is_const { func_token } {
	return [expr {[sub_token $func_token keyconst] != ""}] }

##
# Return true if the method is an accessor (getter)
#
# An accessor is an argument-less const function with a return value.
#
proc function_is_accessor { func_token } {

	if {[function_is_static $func_token]}                { return 0; }
	if {![function_is_const $func_token]}                { return 0; }
	if {[llength [function_arguments $func_token]] != 0} { return 0; }
	if {[function_return_type $func_token] == "void"}    { return 0; }
	if {[function_return_type $func_token] == ""}        { return 0; }
	if {[llength [mlcomment_parts $func_token]] != 0}    { return 0; }

	return 1
}

##
# Return true if method should be described in detail
#
proc method_is_interesting { func_token } {

	#
	# Skip overrides with no prepending comment. Those are mere implementation
	# of an abstract interface defined somewhere else.
	#
	if {[sub_token $func_token keyoverride] != "" &&
		[sub_token $func_token mlcomment] == ""} {
		return 0
	}

	#
	# Accessors are listed only at the class description
	#
	if {[function_is_accessor $func_token]} { return 0; }

	#
	# A destructor or constructor without comments and arguments is not interesting
	#
	foreach func_type { constdecl constimpl destdecl destimpl } {
		if {[tok_type $func_token] == "$func_type"} {

			if {[llength [function_arguments $func_token]] > 0} { return 1 }

			set num_mlcomment_parts [llength [mlcomment_parts $func_token]]
			if {$num_mlcomment_parts == 0} { return 0 }

			# trivial comments do not make a constructor or destructor interesting
			if {$num_mlcomment_parts == 1 &&
			    [function_brief_description $func_token] == ""} { return 0 }
		}
	}

	return 1
}

##
# Return description of function argument as present in the mlcomment
#
proc function_argument_description { function_token arg_name } {

	foreach part [function_comment $function_token] {
		if {[regexp {^\\param\s+([^ ]+)\s+(.*)$} $part dummy name desc]} {
			if {$name == $arg_name} {
				return [to_title $desc]
			}
		}
	}
	return ""
}

proc argparenblk_arguments { compound_token argparenblk_token } {

	if {$argparenblk_token == ""} { return {} }

	set args {}
	foreach_sub_token [tok_text $argparenblk_token] plain { } token {

		if {[tok_type $token] == "argdecl"} {

			set arg_type [unfold_token [sub_token $token argtype]]

			#
			# Determine argument name
			#
			set arg_name ""
			if {[tok_type $token] == "argdecl"} {
				set arg_name [concat [unfold_token [sub_token $token argname]]]

				# try to infer the argument name from commented-out name
				if {$arg_name == ""} {
					set arg_lcomment [unfold_token [sub_token $token lcomment]]
					regexp {/\*\s*(.+)\s*\*/} $arg_lcomment dummy arg_name
				}
			}
			if {$arg_name == ""} { set arg_name "-" }

			#
			# Determine default value
			#
			set arg_default ""
			set arg_default [unfold_token [sub_token $token argdefault]]
			regsub {=\s*} $arg_default "" arg_default

			#
			# Determine argument description from the function's mlcomment
			#
			set arg_desc [function_argument_description $compound_token $arg_name]

			lappend args [list $arg_name $arg_type $arg_default $arg_desc]
		}

		if {[tok_type $token] == "varargs"} {

			lappend args [list "..." "..." "" ""]
		}
	}
	return $args
}

##
# Return list of function arguments
#
# Each list item is a list of name, type, default, and description.
#
proc function_arguments { func_token } {

	set orig_func_token $func_token

	if {[is_function_template $func_token]} {
		set func_token [tplfunc_function $func_token] }

	if {[function_is_operator $func_token]} {
		set operatorfunction_token [sub_token $func_token operatorfunction]
		set argparenblk_token [sub_token $operatorfunction_token argparenblk]
	} else {
		set funcsignature_token [sub_token $func_token funcsignature]
		set argparenblk_token [sub_token $funcsignature_token argparenblk]
	}

	return [argparenblk_arguments $orig_func_token $argparenblk_token]
}

##
# Return list of function template arguments
#
# Each list item is a list of name, type, default, and description.
#
proc function_template_arguments { func_template_token } {

	set tplargs_token [sub_token $func_template_token tplargs]

	return [argparenblk_arguments $func_template_token $tplargs_token]
}

##
# Return list of class template arguments
#
# Each list item is a list of name, type, default, and description.
#
proc class_template_arguments { class_template_token } {

	set tplargs_token [sub_token $class_template_token tplargs]

	return [argparenblk_arguments $class_template_token $tplargs_token]
}

##
# Return information about the function's return value
#
proc function_return_description { func_token } {

	set retval_token [sub_token $func_token retval]

	set ret_desc ""

	# look for \return annotation in the multi-line comment
	foreach part [function_comment $func_token] {
		if {[regexp {^\\return\s+(.*)$} $part dummy desc]} {
			set ret_desc [to_title $desc] } }

	#
	# If not \return annotation was found, look if the brief description
	# starts with "Return" or "Returns"
	#
	if {$ret_desc == ""} {
		set mlcomment_parts [mlcomment_parts $func_token]
		if {[llength $mlcomment_parts]} {

			set first_mlcomment_part [concat [lindex $mlcomment_parts 0]]

			if {[regexp {^Returns?\s+(.*)} $first_mlcomment_part dummy brief]} {
				set ret_desc [to_title $brief]
			}
		}
	}

	return [concat $ret_desc]
}

##
# Return list of function-exception infos
#
# Each list item is a list of the exception type and description.
#
proc function_exceptions { func_token } {

	set exc_list {}
	foreach part [mlcomment_parts $func_token] {

		if {[regexp {^\\throw\s+([^ ]+)\s*(.*)} $part dummy exc_type exc_desc]} {
			lappend exc_list [list $exc_type $exc_desc]
		}
	}
	return $exc_list
}

##
# Extract sequence of public and protected members from class or struct tokens
#
proc public_and_protected_class_members { class_token } {

	if {[tok_type $class_token] == "tplclass"} {
		set class_token [sub_token $class_token class] }

	if {[tok_type $class_token] == "tplstruct"} {
		set class_token [sub_token $class_token struct] }

	set classblock_token [sub_token $class_token classblock]

	set members_sequence {}

	foreach_sub_token [tok_text $classblock_token] plain { } prot_token {

		#
		# Capture members that appear directly in the 'struct' scope
		# where the default visibility is public
		#
		if {[tok_type $class_token] == "struct"} {
			if {[tok_type $prot_token]  == "declseq"} {
				append members_sequence [tok_text $prot_token] } }

		#
		# Capture members that appear in public and protected blocks
		#
		if {[tok_type $prot_token] == "public" ||
		    [tok_type $prot_token] == "protected"} {
			foreach_sub_token [tok_text $prot_token] plain { } token {
				if {[tok_type $token] == "declseq"} {
					append members_sequence [tok_text $token]
				}
			}
		}
	}
	return $members_sequence
}

##
# Return list of accessors for given class
#
proc accessor_functions { class_token } {

	set accessors {}
	set members_sequence [public_and_protected_class_members $class_token]
	foreach_sub_token $members_sequence plain { } token {
		if {[is_function $token] && [function_is_accessor $token]} {
			lappend accessors $token
		}
	}

	return $accessors
}

##
# Return true if class has members
#
proc class_has_members { class_token } {

	set members_sequence [public_and_protected_class_members $class_token]
	set has_members 0
	foreach_sub_token $members_sequence plain { } token {
		if {[is_function $token]} {
			set has_members 1 } }

	return $has_members
}

##
# Return list of paragraphs of the detailed description of a class
#
proc class_detailed_description { class_token } {

	# the implementation happens to be identical for classes and functions
	return [function_detailed_description $class_token]
}

##
# Return name of namespace
#
proc namespace_name { namespace_token } {

	set namespace_name_token [sub_token $namespace_token identifier]
	set namespace_name       [tok_text $namespace_name_token]

	return $namespace_name
}

##
# Return true if token is a namespace
#
proc is_namespace { token } {

	if {[tok_type $token] == "namespace"} {
		return 1 }

	return 0
}

##
# Return list of namespace present in the header
#
proc namespaces_in_header { } {

	set result {}

	foreach_sub_token [tok_text content0] plain { } token {
		if {[is_namespace $token]} {
			lappend result [namespace_name $token]
		}
	}

	return [lsort -unique $result]
}

##
# Return sequence of namespace content for the specified namespace name
#
proc namespace_sequence { name } {

	set sequence ""
	foreach_sub_token [tok_text content0] plain { } token {
		if {[is_namespace $token] && [namespace_name $token] == $name} {
			append sequence [tok_text [sub_token $token namespaceblock]]
		}
	}

	return $sequence
}

##
# Return true if token is a type definition
#
proc is_typedef { token } {

	if {[tok_type $token] == "typedef"} { return 1 }
	return 0
}

##
# Return true if token is a typed enum
#
proc is_enum_typedef { token } {

	if {[tok_type $token] == "enum"} {

		set enum_type [sub_token $token identifier]
		if {$enum_type != ""} { return 1 }
	}
	return 0
}

##
# Return type name of typed enumeration
#
proc enum_type_name { enum_token } {

	return [unfold_token [sub_token $enum_token identifier]]
}

##
# Return true if struct or class is a mere subtype
#
# A subtype is a class definition that interits from a base class and has
# nothing else than constructors.
#
proc class_is_subtype { class_token } {

	# a subtype class must have exactly one public base class
	set base_classes [public_base_classes $class_token]
	if {[llength $base_classes] != 1} { return 0 }

	# a subtype class can have constructors but no other members
	set has_more_members_than_constructor 0
	set members_sequence [public_and_protected_class_members $class_token]
	foreach_sub_token $members_sequence plain { } token {
		if {[tok_type $token] != "constimpl"} {
			set has_more_members_than_constructor 1 }
	}
	if {$has_more_members_than_constructor} {
		return 0 }

	return 1;
}

##
# Return token of sub-type definition if token is a sub type
#
proc sub_typedef { namespace_name token } {

	#
	# Handle case where the subtype is declared in the namespace but defined in
	# the global scope (as usual).
	#
	if {[tok_type $token] == "classdecl" || [tok_type $token] == "structdecl"} {

		set class_name [unfold_token [sub_token $token "identifier"]]
		set full_name "$namespace_name\::$class_name"

		# find class definition in the global scope
		set class_token [find_class_by_name content0 $full_name]
		if {$class_token == ""} { return "" }

		if {[class_is_subtype $class_token]} {
			return $class_token }
	}

	#
	# Handle the case where the subtype is directly defined within the
	# namespace.
	#
	if {[tok_type $token] == "class" || [tok_type $token] == "struct"} {

		if {[class_is_subtype $token]} {
			return $token }
	}

	return ""
}

##
# Return list of type definitions defined in the specified token sequence
#
# Each list element has is a list of type (typedef, subtype, or enum), type
# name, type definition, and a description.
#
proc collect_types_from_sequence { namespace_name sequence } {

	set result { }
	foreach_sub_token $sequence plain { } token {

		if {[is_typedef $token]} {
			set name [unfold_token [sub_token $token typename]]
			set def  [unfold_token [sub_token $token identifier]]
			set desc [mlcomment_parts $token]
			lappend result [list "typedef" $name $def $desc]
		} elseif {[is_enum_typedef $token]} {
			set name [enum_type_name $token]
			set desc [mlcomment_parts $token]
			lappend result [list "enum" $name "" $desc]
		} else {
			set sub_typedef_token [sub_typedef $namespace_name $token]
			if {$sub_typedef_token != ""} {
				set name [class_name $sub_typedef_token]

				if {$namespace_name != "" || ![regexp {::} $name]} {
					regsub "^$namespace_name\::" $name "" name
					set def  [lindex [public_base_classes $sub_typedef_token] 0]
					set desc [mlcomment_parts $sub_typedef_token]
					lappend result [list "subtype" $name $def $desc]
				}
			}
		}
	}
	return $result
}

##
# Return token of function declaration or implementation where it is
# commented
#
proc function_specification { namespace_name token } {

	#
	# Handle case where the function template is declared in the namespace
	# but defined in the global scope (as usual).
	#
	if {[tok_type $token] == "tplfuncdecl"} {

		set func_name [function_name $token]
		set full_name "$namespace_name\::$func_name"

		# find implementation in the global scope
		set funcimpl_token [find_func_by_name content0 $full_name]

		if {$funcimpl_token != ""} {
			return $funcimpl_token }
	}

	return $token
}

##
# Return list of function tokens referred to by the specified token sequence
#
proc collect_functions_from_sequence { namespace_name sequence } {

	set result { }
	foreach_sub_token $sequence plain { } token {

		if {[is_function $token]} {
			lappend result [function_specification $namespace_name $token]
		}
	}
	return $result
}

proc namespace_types { namespace_name } {

	return [collect_types_from_sequence $namespace_name [namespace_sequence $namespace_name]]
}

proc namespace_functions { namespace_name } {

	return [collect_functions_from_sequence $namespace_name [namespace_sequence $namespace_name]]
}

proc global_types { } {

	return [collect_types_from_sequence "" [tok_text content0]]
}


code:
System configuration
####################

There are manifold principal approaches to configure different aspects of
an operating system and the applications running on top.
At the lowest level, there exists the opportunity to pass configuration
information to the boot loader. This information may be evaluated
directly by the boot loader or passed to the booted system. As an
example for the former, some boot loaders allow for setting up a
graphics mode depending on its configuration. Hence, the graphics mode
to be used by the OS could be defined right at this early stage
of booting. More prominently, however, is the mere passing of configuration
information to the booted OS, e.g., in the form of a kernel command line or as
command-line arguments to boot modules. The OS interprets
boot-loader-provided data structures (i.e., multiboot info structures) to
obtain such information. Most kernels interpret certain configuration
arguments passed via this mechanism.
At the OS-initialization level, before any drivers are functioning,
the OS behavior is typically governed by configuration information
provided along with the kernel image, i.e., an initial file-system
image (initrd). On Linux-based systems, this information comes in the
form of configuration files and init scripts located at well-known
locations within the initial file-system image.
Higher up the software stack, configuration becomes an even more diverse
topic. I.e., the runtime behavior of a GNU/Linux-based system is
defined by a conglomerate of configuration files, daemons and their
respective command-line arguments, environment variables, collections
of symlinks, and plenty of heuristics.

The diversity and complexity of configuration mechanisms, however, is
problematic for high-assurance computing. To attain a high level of
assurance, Genode's architecture must be complemented by a low-complexity
yet scalable configuration concept.
The design of this concept takes the following considerations into account:

:Uniformity across platforms:
  To be applicable across a variety of kernels and hardware platforms, the
  configuration mechanism must not rely on a particular kernel or boot loader.
  Even though boot loaders for x86-based machines usually support the
  multiboot specification and thereby the ability to supplement boot modules
  with additional command lines, boot loaders on ARM-based platforms
  generally lack this ability. Furthermore, even if a multiboot compliant
  boot loader is used, the kernel - once started - must provide a way to
  reflect the boot information to the system on top, which is not the case
  for most microkernels.

:Low complexity:
  The configuration mechanism is an intrinsic part of each component. Hence,
  it affects the trusted computing base of every Genode-based system.
  For this reason, the mechanism must be easy to understand and implementable
  without the need for complex underlying OS infrastructure. As a negative
  example, the provision of configuration files via a file system would
  require each Genode-based system to support the notion of a file system
  and to define the naming of configuration files.

:Expressiveness:
  Passing configuration information as command-line arguments to components
  at their creation time seems like a natural way to avoid the complexity
  of a file-based configuration mechanism.
  However, whereas command-line arguments are the tried and tested way for
  supplying program arguments in a concise way, the expressiveness
  of the approach is limited. In particular, it is ill-suited for expressing
  structured information as often found in configurations.
  Being a component-based system, Genode requires a way to
  express relationships between components, which lends itself to the
  use of a structural representation.

:Common syntax:
  The requirement of a low-complexity mechanism mandates a common syntax
  across components. Otherwise, each component would need to  come with a
  custom parser. Each of those parsers would eventually inflate the
  complexity of the trusted computing base. In contrast, a common syntax
  that is both expressive and simple to parse helps to avoid such
  redundancies by using a single parser implementation across all components.

:Least privilege:
  Being the guiding motive behind Genode's architecture, the principle of
  least privilege needs to be applied to the access of configuration
  information. Each component needs to be able to access its own configuration
  but must not observe configuration information concerning unrelated components.
  A system-global registry of configurations or even a global namespace of
  keys for such a database would violate this principle.

:Accommodation of dynamic workloads:
  Supplying configuration information at the construction time of a component
  is not sufficient for long-living components, whose behavior might need to
  be adapted at runtime.
  For example, the assignment of resources to the clients of a resource
  multiplexer might change over the lifetime of the resource multiplexer.
  Hence, the configuration concept should provide a means to update
  the configuration information of a component after it has been constructed.

; XXX best practices
; free from side effects and magic, configuration should be all-encompassing
; reference to [Component configuration]
; offline validation, runtime diagnosis less important

Nested configuration concept
============================

Genode's configuration concept is based on the ROM session interface described
in Section [Read-only memory (ROM)]. In contrast to a file-system interface,
the ROM session interface is extremely simple. The client of a ROM service
specifies the requested ROM module by its name as known by the client.
There is neither a way to query a list of available ROM modules, nor are ROM
modules organized in a hierarchic name space.

[tikz img/nested_config]
  Nested system configuration

The ROM session interface is implemented by core's ROM service to make boot
modules available to other components. Those boot modules comprise the
executable binaries of the init component as well as those of the components
created by init. Furthermore, a ROM module called "config" contains the
configuration of the init process in XML format. To obtain its
configuration, init requests a ROM session for the ROM module "config" from
its parent, which is core. Figure [img/nested_config] shows an example of
such a config ROM module.

[tikz img/config_virtualization]
  Successive interception of "config" ROM requests

The config ROM module uses XML as syntax, which supports the expression of
arbitrary structural data while being simple to parse. I.e., Genode's XML
parser comes in the form of a single header file with less than 600 lines of
code. Init's configuration is contained within a single '<config>' node.

Each component started by init obtains its configuration by requesting
a ROM module named "config" from its parent. Init responds to
this request by handing out a locally-provided ROM session. Instead of
handing out the "config" ROM module as obtained from core, it creates a new
dataspace that solely contains the portion of init's config ROM module that
refers to the respective child. Analogously to init's configuration,
each child's configuration has the form of a single '<config>' node.
This works recursively. From each component's perspective, including the init
component, the mechanism for obtaining its configuration is identical -- it
obtains a ROM session for a ROM module named "config" from its parent.
The parent interposes the ROM session request as described in
Section [Interposing individual services]. Figure [img/config_virtualization]
shows the successive interposing of "config" ROM requests according to the
example configuration given in Figure [img/nested_config].
At each level, the information structure within the '<config>' node can
be different. Besides following the convention that a configuration has the
form of a single '<config>' node, each component can introduce arbitrary
custom tags and attributes.

Besides being simple, the use of the ROM session interface for supplying
configuration information has the benefit of supporting dynamic configuration
updates over the lifetime of the config ROM session. Section
[Read-only memory (ROM)] describes the update protocol between client
and server of a ROM session. This way, the configuration of long-living
components can be dynamically changed.

The init component
==================

The init component plays a special role within Genode's component tree. It
gets started directly by core, gets assigned all physical resources, and
controls the execution of all subsequent component nodes, which can be further
instances of init. Init's policy is driven by an XML-based configuration,
which declares a number of children, their relationships, and resource
assignments. The XML schema definition for init's configuration is provided
at _repos/os/src/init/config.xsd_.

Session routing
~~~~~~~~~~~~~~~

At the parent-child interface, there are two operations that are subject to
policy decisions of the parent: the child announcing a service and the
child requesting a service. If a child announces a service, it is up to the parent
to decide if and how to make this service accessible to its other children.
When a child requests a service, the parent may deny the session request,
delegate the request to its own parent, implement the requested service
locally, or open a session at one of its other children. This decision may
depend on the service requested or the session-construction arguments provided
by the child. Apart from assigning resources to children, the central
element of the policy implemented in the parent is a set of rules to
route session requests. Therefore, init's configuration concept is laid out
around child components and the routing of session requests originating from
those components. The mechanism is best illustrated by an example:

! <config>
!   <parent-provides>
!     <service name="PD"/>
!     <service name="ROM"/>
!     <service name="CPU"/>
!     <service name="LOG"/>
!   </parent-provides>
!   <start name="timer" caps="100">
!     <resource name="RAM" quantum="1M"/>
!     <provides> <service name="Timer"/> </provides>
!     <route>
!       <service name="PD">  <parent/> </service>
!       <service name="ROM"> <parent/> </service>
!       <service name="CPU"> <parent/> </service>
!       <service name="LOG"> <parent/> </service>
!     </route>
!   </start>
!   <start name="test-timer" caps="200">
!     <resource name="RAM" quantum="1M"/>
!     <route>
!       <service name="Timer">  <child name="timer"/> </service>
!       <service name="PD">     <parent/>             </service>
!       <service name="ROM">    <parent/>             </service>
!       <service name="CPU">    <parent/>             </service>
!       <service name="LOG">    <parent/>             </service>
!     </route>
!   </start>
! </config>

First, there is the declaration of services provided by the parent of the
configured init instance. In this case, we declare that the parent provides a
a LOG service.
For each child to start, there is a '<start>' node describing the assigned RAM
and capability budget, declaring services provided by the child,
and holding a routing table for session requests originating from the child.
The first child is called "timer" and implements the "Timer" service.
The second component called "test-timer" is a client of the timer service. In
its routing table, we see that requests for "Timer" sessions are routed to the
"timer" child whereas requests for core's services are routed to
init's parent. Per-child service routing rules provide a flexible way to
express arbitrary client-server relationships. For example, service requests
may be transparently mediated through special policy components acting upon
session-construction arguments. There might be multiple children implementing
the same service, each targeted by different routing tables. If there exists no
valid route to a requested service, the service is denied. In the example
above, the routing tables act effectively as a white list of services the child
is allowed to use.

Routing based on session labels
-------------------------------

Access-control policies in Genode systems are based on session labels. When a
server receives a new session request, the session label is passed along with
the request.

A session label is a string that is assembled by the components that are
involved with routing the session request from the client along the branches
of the component tree to the server. The client may specify the least
significant part of the label by itself. This part gives the parent a hint
for routing the request. For example, a client may create two file-system
sessions, one labeled with "home" and one labeled with "bin". The parent may
take this information into account and route the individual requests to
different file-system servers. The label is successively superseded (prefixed)
by additional parts along the chain of components on the route of the session
request. The first part of the label is the most significant part as it is
imposed by the component in the intermediate proximity of the server. The last
part is the least trusted part of the label because it originated from the
client. Once the session request arrives at the server, the server takes the
session label as the key to select a server-side policy as described in
Section [Server-side policy selection].

In most cases, routing decisions are simply based on the type of the requested
sessions. However, by equipping '<service>' nodes with the following
attributes, it is possible to take session labels as a criterion for the
routing of session requests into account.

:'label="<string>"': The session label must perfectly match the specified
  string.

:'label_prefix="<string>"': The first part of the label must match the
  specified string.

:'label_suffix="<string>"': The end of the label must match the
  specified string.

:'unscoped_label="<string>"': The session label including the child's name
  prefix must perfectly match the specified string. In contrast to the
  'label' attribute, which refers to the child-defined label, the 'unscoped_label'
  can refer to the child's environment sessions, which have no client-defined
  label because they are initiated by init itself.

:'label_last="<string>"': The part after the last "->" delimiter must match the
  specified string. This part usually refers to a requested resource such as
  the name of a ROM module. If no delimiter is present, the label must be an
  exact match.

If no attributes are present, the route matches. The attributes can be
combined. If any of the specified attributes mismatch, the route is
neglected.
If multiple '<service>' nodes match in init's routing configuration, the first
matching rule is taken. So the order of the nodes is important.

Wildcards
---------

In practice, usage scenarios become more complex than the basic example,
increasing the size of routing tables. Furthermore, in many practical cases,
multiple children may use the same set of services and require duplicated
routing tables within the configuration. In particular during development, the
elaborative specification of routing tables tend to become an inconvenience.
To alleviate this problem, there are two mechanisms, namely wildcards and a
default route.
Instead of specifying a list of individual service routes targeting the same
destination, the wildcard '<any-service>' becomes handy. For example, instead
of specifying
! <route>
!   <service name="ROM"> <parent/> </service>
!   <service name="LOG"> <parent/> </service>
!   <service name="PD">  <parent/> </service>
!   <service name="CPU"> <parent/> </service>
! </route>
the following shortform can be used:
! <route>
!   <any-service> <parent/> </any-service>
! </route>
The latter version is not as strict as the first one because it permits the
child to create sessions at the parent, which were not white listed in the
elaborative version. Therefore, the use of wildcards is discouraged for
configuring untrusted components. Wildcards and explicit routes may be combined
as illustrated by the following example:
! <route>
!   <service name="LOG"> <child name="nitlog"/> </service>
!   <any-service>        <parent/>              </any-service>
! </route>
The routing table is processed starting with the first entry. If the route
matches the service request, it is taken, otherwise the remaining
routing-table entries are visited. This way, the explicit service route of
"LOG" sessions to the "nitlog" child shadows the LOG service provided by the
parent.

To allow a child to use services provided by arbitrary other children, there
is a further wildcard called '<any-child>'. Using this wildcard, such a policy
can be expressed as follows:
! <route>
!   <any-service> <parent/>    </any-service>
!   <any-service> <any-child/> </any-service>
! </route>
This rule would delegate all session requests referring to one of the parent's
services to the parent. If no parent service matches the session request, the
request is routed to any child providing the service. The rule can be further
abbreviated to:
! <route>
!   <any-service> <parent/> <any-child/> </any-service>
! </route>
Init detects potential ambiguities caused by multiple children providing the
same service. In this case, the ambiguity must be resolved using an explicit
route preceding the wildcards.

Default routing
---------------

To reduce the need to specify the same routing table for many children
in one configuration, there is a '<default-route>' mechanism. The default
route is declared within the '<config>' node and used for each '<start>'
entry with no '<route>' node. In particular during development, the default
route becomes handy to keep the configuration tidy and neat.

The combination of explicit routes and wildcards is designed to scale well from
being convenient to use during development towards being highly secure at
deployment time. If only explicit rules are present in the configuration, the
permitted relationships between all processes are explicitly defined and can be
easily verified.

Using aliases for component names
---------------------------------

In complex scenarios, it is sometimes useful to distinguish the name of a
component from its role as a service provider for other components.
For example, file-system server may be called "ahci-1.ext2.fs" to express that
the component works with an EXT2 file system on partition 1 of an AHCI block
device. Such an encoding is useful to clearly tell multiple file-system
servers apart. But for configuring the routes of multiple file-system clients,
the repetition of this level of detail becomes a burden. This situation calls
for an indirection:

! <alias name="wwwdata_fs" child="ahci-1.ext2.fs"/>

An '<alias>' node introduces a new name that can be used as session-routing
target alternatively to the name of the referred-to '<start>' node. With
the alias in place, a client's session route can now be written such that the
purpose of the targeted server becomes clear at first glance.

! ...
! <service name="File_system" label="wwwdata">
!   <child name="wwwdata_fs"/> </service>
! ...

The alias not only eases the human interpretation of routing rules during a
security assessment. It also anticipates a flexible adaptation of the scenario
for the use of another file system, which would involve only the change of the
single alias while keeping all client-side session routes unaffected.

Resource assignment
~~~~~~~~~~~~~~~~~~~

Physical memory budget
----------------------

Each '<start>' node must be equipped with a declaration of the amount of
RAM assigned to the child via a '<resource>' sub node.

! <resource name="RAM" quantum="1M"/>

If the specified amount exceeds the available resources,
the available resources are assigned almost completely to the child.
This makes it possible to assign all remaining resources to the last child by
simply specifying an overly large quantum.
Note that this special case should only be used for static configurations.
In dynamic scenarios, components can temporarily disappear during the
reconfiguration, which temporary frees their resources. Once released,
however, those temporarily slack resources would end up in the unsaturated
subsystem, preventing the subsequent (re-)spawning of other subsystems.

Init retains only a small amount of quota for itself, which is used to cover
indirect costs such as a few capabilities created on behalf of the children,
or memory used for buffering configuration data. The preserved amount
can be configured as follows:

! <config>
!   ...
!   <resource name="RAM" preserve="1M"/>
!   ...
! </config>

Capability budget
-----------------

Each component requires a certain amount of capabilities to live. At startup,
several capabilities are created along with the component's environment
sessions, in particular its PD session. At lifetime, the component consumes
capabilities when creating signal handlers or RPC objects. Since the
system-global amount of capabilities is a bounded resource, which depends on
the used kernel and the kernel configuration, Genode subjects the allocation
of capabilities to the same rigid regime as for physical memory. First, the
creation of capabilities is restricted by resource quotas explicitly assigned
to components. Second, capability budgets can be traded between clients and
servers such that servers are able to account capability allocations to their
clients.

Each '<start>' node can be equipped with a 'caps' attribute with
the amount of capabilities assigned to the component. As a rule of
thumb, the setup costs of a component are 35 capabilities. Hence, for
typical components, an amount of 100 is a practical value.
To alleviate the need to equip each '<start>' node with the same default
value, the init configuration accepts a default declaration as follows:
! <default caps="100"/>
Unless a '<start>' node is equipped with a custom 'caps' attribute, the
default value is used.

If a component runs out of capabilities, core's PD service prints a warning to
the log. To observe the consumption of capabilities per component in detail,
core's PD service is equipped with a diagnostic mode, which can be enabled via
the 'diag' attribute in the target node of init's routing rules. E.g., the
following route enables the diagnostic mode for the PD session:

! <route>
!   <service name="PD"> <parent diag="yes"/> </service>
!   ...
! </route>

With the 'diag' attribute enabled, core prints a log message each time the
PD consumes, frees, or transfers its capability budget.

Multiple instantiation of a single ELF binary
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Each '<start>' node requires a unique 'name' attribute. By default, the
value of this attribute is used as ROM module name for obtaining the ELF
binary from the parent. If multiple instances of a component with the same
ELF binary are needed, the binary name can be explicitly specified
using a '<binary>' sub node of the '<start>' node:
! <binary name="filename"/>
This way, a unique child name can be defined independently from the
binary name.

Session-label rewriting
~~~~~~~~~~~~~~~~~~~~~~~

As explained in section [Session routing], init routes session requests by
taking the requested service type and the
session label into account. The latter may be used by the server as a key for
selecting a policy at the server side. To simplify server-side policies, init
supports the rewriting of session labels in the target node
of a matching session route. For example, an interactive shell ("shell") may
have the following session route for the "home" file system:

!<route>
!  <service name="File_system" label="home">
!    <child name="vfs"/>
!  </service>
!  ...
!</route>

At the "vfs" file-system server, the label of the file-system session will
appear as "shell -> home". This information may be evaluated by the vfs's
server-side policy. However, when renaming the shell instance, we'd need to
update this server-side policy.

With the label-rewriting mechanism, the client's identity can be hidden from
the server. The label can instead represent the role of the client, or a name
of a physical resource. For example, the route could be changed to this:

!<route>
!  <service name="File_system" label="home">
!    <child name="vfs" label="primary_user"/>
!  </service>
!  ...
!</route>

Whenever the vfs receives the session request, it is presented with the label
"primary_user". The fact that the client is "shell" is not taken into account
for the server-side policy selection.

Nested configuration
~~~~~~~~~~~~~~~~~~~~

; XXX Figure showing an illustration of the nested scenario

Each '<start>' node can host a '<config>' sub node.
As described in Section [Nested configuration concept], the content of this
sub node is provided to the child when a ROM session for the module name
"config" is requested.
Thereby, arbitrary configuration parameters can be passed to the
child. For example, the following configuration starts the 'timer-test' within an
init instance within another init instance. To show the flexibility of init's
service routing facility, the "Timer" session of the second-level 'timer-test'
child is routed to the timer service started at the first-level init instance.
! <config>
!   <parent-provides>
!     <service name="LOG"/>
!     <service name="ROM"/>
!     <service name="CPU"/>
!     <service name="PD"/>
!   </parent-provides>
!   <start name="timer" caps="100">
!     <resource name="RAM" quantum="1M"/>
!     <provides><service name="Timer"/></provides>
!     <route>
!       <any-service> <parent/> </any-service>
!     </route>
!   </start>
!   <start name="init" caps="1000">
!     <resource name="RAM" quantum="10M"/>
!     <config>
!       <parent-provides>
!         <service name="Timer"/>
!         <service name="LOG"/>
!         <service name="ROM"/>
!         <service name="CPU"/>
!         <service name="PD"/>
!       </parent-provides>
!       <start name="test-timer" caps="200">
!         <resource name="RAM" quantum="1M"/>
!         <route>
!           <any-service> <parent/> </any-service>
!         </route>
!       </start>
!     </config>
!     <route>
!       <service name="Timer"> <child name="timer"/> </service>
!       <any-service>          <parent/>             </any-service>
!     </route>
!   </start>
! </config>
The services ROM, LOG, CPU, and PD are required by the second-level
init instance to create the timer-test component.
As illustrated by this example, the use of nested configurations
enables the construction of arbitrarily complex component trees via a single
configuration.

Configuring components from distinct ROM modules
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

As an alternative to specifying the component configurations of all '<start>'
nodes via '<config>' sub nodes, component configurations may be placed in
separate ROM modules by facilitating the session-label rewriting mechanism
described in Section [Session-label rewriting]:

! <start name="nitpicker">
!   <resource name="RAM" quantum="1M"/>
!   <route>
!     <service name="ROM" label="config">
!       <parent label="nitpicker.config"/>
!     </service>
!     ...
!   </route>
!   ...
! </start>

With this routing rule in place, a ROM session request for the module "config"
is routed to the parent and appears at the parent's ROM service under the
label "nitpicker.config".

Assigning subsystems to CPUs
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Most multi-processor (MP) systems have topologies that can be represented on a
two-dimensional coordinate system. CPU nodes
close to each other are expected to have closer relationship than distant
nodes. In a large MP system, it is natural to assign clusters of closely
related nodes to a given workload. As described in Section
[Recursive system structure], Genode's architecture is based on a strictly
hierarchic organizational structure. Thereby, it lends itself to the idea of
applying this successive virtualization of resources to the problem of clustering
CPU nodes.

[tikz img/affinity_spaces]
  Successive virtualization of CPU affinity spaces by nested instances
  of init

Each component within the component tree has a component-local view on a
so-called _affinity space_, which is a two-dimensional coordinate space. If the
component creates a new subsystem, it can assign a portion of its own affinity
space to the new subsystem by imposing a rectangular affinity location to the
subsystem's CPU session. Figure [img/affinity_spaces] illustrates the idea.

Following from the expression of affinities as a rectangular location within a
component-local affinity space, the assignment of subsystems to CPU nodes
consists of two parts: the definition of the affinity space dimensions as used
for the init instance, and the association of subsystems with affinity locations
relative to the affinity space.
The affinity space is configured as a sub node of the '<config>' node. For
example, the following declaration describes an affinity space of 4x2:

! <config>
!   ...
!   <affinity-space width="4" height="2" />
!   ...
! </config>

Subsystems can be constrained to parts of the affinity space using the
'<affinity>' sub node of a '<start>' entry:

! <config>
!   ...
!   <start name="loader">
!     <affinity xpos="0" ypos="1" width="2" height="1" />
!     ...
!   </start>
!   ...
! </config>

As illustrated by this example, the numbers used in the declarations for this
instance of init are not directly related to physical CPUs.
If the machine has merely two cores, init's affinity space would be mapped to
the range 0,1 of physical CPUs. However, in a machine with 16x16 CPUs, the
loader would obtain 8x8 CPUs with the upper-left CPU at position (0,8).

Priority support
~~~~~~~~~~~~~~~~

The number of CPU priorities to be distinguished by init can be specified with
the 'prio_levels' attribute of the '<config>' node. The value must be a power of
two. By default, no priorities are used. To assign a priority to a child
process, a priority value can be specified as 'priority' attribute of the
corresponding '<start>' node. Valid priority values lie in the range of
-prio_levels + 1 (maximum priority degradation) to 0 (no priority degradation).

Propagation of exit events
~~~~~~~~~~~~~~~~~~~~~~~~~~

A component can notify its parent about its graceful exit via the exit RPC
function of the parent interface. By default, init responds to such a
notification from one of its children by merely printing a log message but
ignores it otherwise. However, there are scenarios where the exit of a
particular child should result in the exit of the entire init component. To
propagate the exit of a child to the parent of init, start nodes can host the
optional sub node '<exit>' with the attribute 'propagate' set to "yes".

! <config>
!   <start name="shell">
!     <exit propagate="yes"/>
!     ...
!   </start>
! </config>

The exit value specified by the exiting child is forwarded to init's parent.

State reporting
~~~~~~~~~~~~~~~

When used in a nested fashion, init can be configured to report its internal
state in the form of a "state" report by placing a '<report>' node into init's
configuration. The report node accepts the following arguments (with their
default values shown):

:'delay_ms="100"': specifies the number of milliseconds to wait before
  producing a new report. This way, many consecutive state changes -
  like they occur during startup - do not result in an overly
  large number of reports but are merged into one final report.

:'buffer="4K"': the maximum size of the report in bytes. The attribute
  accepts the use of K/M/G as units.

:'init_ram="no"': if enabled, the report will contain a '<ram>' node
  with the memory statistics of init.

:'init_caps="no"': if enabled, the report will contain a '<caps>' node
  with the capability-allocation statistics of init.

:'ids="no"': supplement the children in the report with unique IDs, which
  may be used to infer the lifetime of children across configuration
  updates in the future.

:'requested="no"': if enabled, the report will contain information about
  all session requests initiated by the children.

:'provided="no"': if enabled, the report will contain information about
  all sessions provided by all servers.

:'session_args="no"': level of detail of the session information
  generated via 'requested' or 'provided'.

:'child_ram="no"': if enabled, the report will contain a '<ram>' node
  for each child based on the information obtained from the child's PD
  session.

:'child_caps="no"': if enabled, the report will contain a '<caps>' node
  for each child based on the information obtained from the child's PD
  session.

Note that the state reporting feature cannot be used for the initial
instance of init started by core. It depends on the "Timer" and "Report"
services, which are provided by higher-level components only.

Init verbosity
~~~~~~~~~~~~~~

To ease debugging, init can be instructed to print diverse status
information as LOG output. To enable the verbose mode, assign the value "yes"
to the 'verbose' attribute of the '<config>' node.

Service forwarding
~~~~~~~~~~~~~~~~~~

In nested scenarios, init is able to act as a server that forwards
session requests to its children. Session requests can be routed
depending on the requested service type and the session label
originating from init's parent.

The feature is configured by one or multiple '<service>' nodes hosted in
init's '<config>' node. The routing policy is selected via the regular
server-side policy-selection mechanism, for example:

! <config>
!   ...
!   <service name="LOG">
!     <policy label="shell">
!       <child name="terminal_log" label="important"/>
!     </policy>
!     <default-policy> <child name="nitlog"/> </default-policy>
!   </service>
!   ...
! </config>

Each policy node must have a '<child>' sub node, which denotes the name of the
server with the 'name' attribute. The optional 'label' attribute defines
the session label presented to the server, analogous to how the
rewriting of session labels works in session routes. If not specified,
the client-provided label is presented to the server as is.

Component health monitoring
~~~~~~~~~~~~~~~~~~~~~~~~~~~

Scenarios where components are known to sometimes fail call for a mechanism
that continuously checks the health of components and reports anomalies. To
accommodate such use cases, Genode provides a built-in health-monitoring
mechanism. Each component registers a heartbeat signal handler during its
initialization at its parent. This happens under the hood and is thereby
transparent to application code. Each time the signal is triggered by the
parent, the default heartbeat handler invokes the 'heartbeat_response'
function at the parent interface and thereby confirms that the component is
still able to respond to external events.

[tikz img/heartbeat]
  Init queries the responsiveness of its children

Thanks to this low-level mechanism, the init component is able to
monitor its child components as depicted in Figure [img/heartbeat].
A global (for this init instance) heartbeat rate can be configured via
a '<heartbeat rate_ms="1000"/>' node at the top level of init's configuration.
The heartbeat rate can be specified in milliseconds. If configured, init uses
a dedicated timer session for performing health checks periodically. Each
component that hosts a '<heartbeat>' node inside its '<start>' node is
monitored. In each period, init requests heartbeat responses from all
monitored children and maintains a count of outstanding heartbeats for each
component. The counter is incremented in each period and reset whenever the
child responds to init's heartbeat request. Whenever the number of outstanding
heartbeats of a child becomes higher than 1, the child may be in trouble.
Init reports this information in its state report via the new attribute
'skipped_heartbeats="N"' where N denotes the number of periods since the child
became unresponsive.

Of course, the mechanism won't deliver 100% accuracy. There may be situations
like long-running calculations where long times of unresponsiveness are
expected from a healthy component. Vice versa, in a multi-threaded
application, the crash of a secondary thread may go undetected if the primary
(checked) thread stays responsive. However, in the majority of cases where a
component crashes (page fault, stack overflow), gets stuck in a busy loop,
produces a deadlock, or throws an unhandled exception (abort), the mechanism
nicely reflects the troublesome situation to the outside.

Unlabeled of LOG messages
~~~~~~~~~~~~~~~~~~~~~~~~~

By default, each line printed by core's LOG service is prefixed with the label
of the originating component. In situations where a Genode system is remotely
controlled and monitored, it is useful to allow a special component to produce
log output with no label applied. This way, such a component can produce log
data in a format that is immediately suitable for a controller. This feature
can be enabled for a component by rewriting the label of the component's LOG
session to "unlabeled".

! <route>
!   <service name="LOG"> <parent label="unlabeled"/> </service>
!   ...
! </route>

repo_name: Fhiss/genode


code:
                    =================================
                    Genode Operating System Framework
                               Foundations
                    =================================

                              Norman Feske

: \vfill \epsfig{file=img/by-sa,angle=0,width=0.2\textwidth} \hspace{0.3cm}
: \begin{minipage}[b]{0.8\textwidth} \raggedright \small
: This work is licensed under the Creative Commons Attribution + ShareAlike
: License (CC-BY-SA). To view a copy of the license, visit
: http://creativecommons.org/licenses/by-sa/4.0/legalcode
: \end{minipage}