1ea906c41SOllivier Robert<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2ea906c41SOllivier Robert<html> 3ea906c41SOllivier Robert<head> 4ea906c41SOllivier Robert<meta http-equiv="content-type" content="text/html;charset=iso-8859-1"> 5ea906c41SOllivier Robert<meta name="generator" content="HTML Tidy, see www.w3.org"> 6ea906c41SOllivier Robert<title>Configuration File Definition (Advanced)</title> 7ea906c41SOllivier Robert<link href="scripts/style.css" type="text/css" rel="stylesheet"> 8ea906c41SOllivier Robert</head> 9ea906c41SOllivier Robert<body> 10ea906c41SOllivier Robert<h3>Configuration File Definition (Advanced)</h3> 11*2b15cb3dSCy Schubert<img src="pic/pogo7.gif" alt="gif" align="left"><a href="http://www.eecis.udel.edu/~mills/pictures.html">from <i>Pogo</i>, Walt Kelly</a> 12*2b15cb3dSCy Schubert<p>Racoon is shooting configuration bugs.</p> 13*2b15cb3dSCy Schubert<p>Last update: 14*2b15cb3dSCy Schubert <!-- #BeginDate format:En2m -->4-Oct-2010 05:13<!-- #EndDate --> 15*2b15cb3dSCy Schubert UTC</p> 16ea906c41SOllivier Robert<br clear="left"> 17ea906c41SOllivier Robert<h4>Table of Contents</h4> 18ea906c41SOllivier Robert<ul> 19*2b15cb3dSCy Schubert <li class="inline"><a href="#synopsis">Synopsis</a></li> 20*2b15cb3dSCy Schubert <li class="inline"><a href="#files">Files</a></li> 21*2b15cb3dSCy Schubert <li class="inline"><a href="#high-level">High-Level Description</a></li> 22*2b15cb3dSCy Schubert <li class="inline"><a href="#detailed">Detailed Description</a></li> 23*2b15cb3dSCy Schubert <li class="inline"><a href="#guidelines">Guidelines for Adding Configuration Commands </a></li> 24ea906c41SOllivier Robert</ul> 25*2b15cb3dSCy Schubert<hr> 26ea906c41SOllivier Robert<h4 id="synopsis">Synopsis</h4> 27ea906c41SOllivier Robert<p>The NTP configuration process is driven by a phrase-structure grammar which is used to specify the format of the configuration commands and the actions needed to build an abstract syntax tree (AST). The grammar is fed to a parser generator (Bison) which produces a parser for the configuration file.</p> 28ea906c41SOllivier Robert<p>The generated parser is used to parse an NTP configuration file and check it for syntax and semantic errors. The result of the parse is an AST, which contains a representation of the various commands and options. This AST is then traversed to set up the NTP daemon to the correct configuration.</p> 29ea906c41SOllivier Robert<p>This document is intended for developers who wish to modify the configuration code and/or add configuration commands and options. It contains a description of the files used in the configuration process as well as guidelines on how to construct them.</p> 30ea906c41SOllivier Robert<h4 id="files">Files</h4> 31ea906c41SOllivier Robert<p>A brief description of the files used by the configuration code is given below:</p> 32ea906c41SOllivier Robert<table border="1"> 33ea906c41SOllivier Robert <tbody> 34ea906c41SOllivier Robert <tr> 35ea906c41SOllivier Robert <th width="179">File</th> 36ea906c41SOllivier Robert <th width="537">Description</th> 37ea906c41SOllivier Robert </tr> 38ea906c41SOllivier Robert <tr> 39ea906c41SOllivier Robert <td valign="top"><b>ntp_config.y</b></td> 40ea906c41SOllivier Robert <td>This file is a Bison source file that contains the phrase-structure grammar and the actions that need to be performed to generate an AST.</td> 41ea906c41SOllivier Robert </tr> 42ea906c41SOllivier Robert <tr> 43ea906c41SOllivier Robert <td valign="top"><b>ntp_config.c</b></td> 44ea906c41SOllivier Robert <td>This file contains the major chunk of the configuration code. It contains all the functions that are called for building the AST as well as the functions that are needed for traversing the AST.</td> 45ea906c41SOllivier Robert </tr> 46ea906c41SOllivier Robert <tr> 47ea906c41SOllivier Robert <td valign="top"><b>ntp_config.h</b></td> 48ea906c41SOllivier Robert <td>This file is the header file for <b>ntp_config.c</b>. It mainly contains the structure definitions needed to build the AST. </td> 49ea906c41SOllivier Robert </tr> 50ea906c41SOllivier Robert <tr> 51ea906c41SOllivier Robert <td valign="top"><b>ntp_scanner.c</b></td> 52ea906c41SOllivier Robert <td>This file contains the code for a simple lexical analyzer. This file is directly included into the <b>ntp_config.c</b> file since this code is only used by the configuration code. The most important function in this file is <tt>yylex</tt>, which is called by the generated parser to get the next token on the input line.</td> 53ea906c41SOllivier Robert </tr> 54ea906c41SOllivier Robert <tr> 55ea906c41SOllivier Robert <td valign="top"><b>ntp_data_structures.c</b></td> 56ea906c41SOllivier Robert <td>This file contains a generic implementation of a priority queue and a simple queue. This code can be used to create a queue for any structure.</td> 57ea906c41SOllivier Robert </tr> 58ea906c41SOllivier Robert <tr> 59ea906c41SOllivier Robert <td valign="top"><b>ntp_data_structures.h</b></td> 60ea906c41SOllivier Robert <td>This header file contains the structure declarations and function prototypes needed to use the data structures defined in <b>ntp_data_structures.c</b>. This file forms the public interface of the data structures.</td> 61ea906c41SOllivier Robert </tr> 62ea906c41SOllivier Robert <tr> 63ea906c41SOllivier Robert <td valign="top"><b>ntp_config.tab.c</b></td> 64ea906c41SOllivier Robert <td>This file is generated by Bison from the <b>ntp_config.y</b> file. This file is also included directly into the configuration code.</td> 65ea906c41SOllivier Robert </tr> 66ea906c41SOllivier Robert </tbody> 67ea906c41SOllivier Robert</table> 68ea906c41SOllivier Robert<h4 id="high-level">High-Level Description</h4> 69ea906c41SOllivier Robert<p>A high-level description of the configuration process showing where all the files fit in is given below:</p> 70ea906c41SOllivier Robert<p><img src="pic/description.jpg" alt="JPEG" border="0"></p> 71ea906c41SOllivier Robert<p>The scanner reads in an NTP configuration file and converts it into tokens. The Bison generated parser reads these tokens and converts them into an AST. The AST traverser consists of a set of functions that configure parts of NTP on the basis of what is on the tree. A more detailed description of these parts and the files used is given below:</p> 72ea906c41SOllivier Robert<h4 id="detailed">Detailed Description</h4> 73ea906c41SOllivier Robert<dl> 74*2b15cb3dSCy Schubert <dt><b>ntp_scanner.c</b></dt> 75*2b15cb3dSCy Schubert <dd>This file contains the scanner. The scanner is a small program that converts an input NTP configuration file into a set of <b>tokens</b> that correspond to <b>lexemes</b> in the input. Lexemes are strings in the input, delimited by whitespace and/or special characters. Tokens are basically unique integers that represent these lexemes. A different token is generated for each reserved word and special character in the input. There are two main functions in the public interface of this file:</dd> 76*2b15cb3dSCy Schubert <dt><tt>int yylex</tt>()</dt> 77*2b15cb3dSCy Schubert <dd>This function is called <tt>yylex</tt> for historical reasons; <tt>lex</tt> is a program that takes a set of regular expressions and generates a scanner that returns tokens corresponding to those regular expressions. The name of the generated function is called <tt>yylex</tt>. We aren't using<b> </b><tt>lex</tt><b> </b>because it requires linking against an external library and we didn't want to increase the compile-time requirements of NTP.</dd> 78*2b15cb3dSCy Schubert <dd>History lessons aside, this function basically checks to see if the next input character is a special character as defined in the array <tt>char special_char[]</tt>. (The function <tt>int is_special(char ch)</tt>, can be used for this.) If yes, the special character is returned as the token. If not, a set of characters is read until the next whitespace or special character is encountered. This set of characters forms the lexeme; <tt>yylex</tt> then checks whether this lexeme is an integer, a double, an IP address or a reserved word. If yes, the corresponding token is returned. If not, a token for a string is returned as the default token.</dd> 79*2b15cb3dSCy Schubert <dt><tt>struct state *create_keyword_scanner(struct key_tok *<i>keyword_list</i>)</tt></dt> 80*2b15cb3dSCy Schubert <dd>This function takes a list of (<i>keyword, token</i>) pairs and converts them into a trie that can recognize the keywords (reserved words). Every time the scanner reads a lexeme, it compares it against the list of reserved words. If it finds a match, it returns the corresponding token for that keyword.</dd> 81*2b15cb3dSCy Schubert <dt><b>ntp_data_structures.c</b></dt> 82*2b15cb3dSCy Schubert <dd>This file contains an implementation of a generic priority queue and FIFO queue. By generic, we mean that these queues can hold element of any type (integers, user-defined structs, etc.), provided that these elements are allocated on the heap using the function <tt>void</tt> *<tt>get_node(size_t size)</tt>. Note that the prototype for this function is exactly the same as that of <tt>malloc</tt> and that it can be used in the exact same way. Behind the scenes, <tt>get_node</tt> calls <tt>malloc</tt> to allocate <i>size</i> plus some extra memory needed for bookkeeping. The allocated memory can be freed using the function <tt>void free_node (void *<i>my_node</i>)</tt>. In addition to these two functions, the public interface of this file contains the following functions:</dd> 83*2b15cb3dSCy Schubert <dt><tt>queue *create_priority_queue(int (*get_order)(void *, void*))</tt></dt> 84*2b15cb3dSCy Schubert <dd>This function creates a priority queue in which the order of the elements is determined by the <tt>get_order</tt><b> </b>function that is passed as input to the priority queue. The <tt>get_order</tt><b> </b>function should return positive if the priority of the first element is less than the priority of the second element.</dd> 85*2b15cb3dSCy Schubert <dt><tt>queue *create_queue(void)</tt></dt> 86*2b15cb3dSCy Schubert <dd>This function creates a FIFO queue. It basically calls the <tt>create_priority_queue</tt> function with the <tt>get_fifo_order</tt><b> </b>function as its argument.</dd> 87*2b15cb3dSCy Schubert <dt><tt>void destroy_queue(queue *<i>my_queue</i>)</tt></dt> 88*2b15cb3dSCy Schubert <dd>This function deletes <tt><i>my_queue</i></tt><b> </b>and frees up all the memory allocated to it an its elements.</dd> 89*2b15cb3dSCy Schubert <dt><tt>int empty(queue *</tt><i><tt>my_queue</tt></i><tt>)</tt></dt> 90*2b15cb3dSCy Schubert <dd>This function checks to see if <i><tt>my_queue</tt></i> is empty. Returns <tt>true</tt> if <tt><i>my_queue</i></tt> does not have any elements, else it returns false.</dd> 91*2b15cb3dSCy Schubert <dt><tt>queue *enqueue(queue *<i>my_queue</i>, void *<i>my_node</i>)</tt></dt> 92*2b15cb3dSCy Schubert <dd>This function adds an element, <i><tt>my_node</tt></i>, to a queue, <i><tt>my_queue</tt></i>. <i><tt>my_node</tt></i> must be allocated on the heap using the <tt>get_node</tt> function instead of <tt>malloc</tt>.</dd> 93*2b15cb3dSCy Schubert <dt><tt>void *dequeue(queue *<i>my_queue</i>)</tt></dt> 94*2b15cb3dSCy Schubert <dd>This function returns the element at the front of the queue. This element will be element with the highest priority.</dd> 95*2b15cb3dSCy Schubert <dt><tt>int get_no_of_elements(queue *<i>my_queue</i>)</tt></dt> 96*2b15cb3dSCy Schubert <dd>This function returns the number of elements in <tt><i>my_queue</i></tt>.</dd> 97*2b15cb3dSCy Schubert <dt><tt>void append_queue(queue *<i>q</i>1, queue *<i>q</i>2)</tt></dt> 98*2b15cb3dSCy Schubert <dd>This function adds all the elements of <tt><i>q</i>2</tt> to <tt><i>q</i>1</tt>. The queue <tt><i>q</i>2</tt> is destroyed in the process.</dd> 99*2b15cb3dSCy Schubert <dt><b>ntp_config.y</b></dt> 100*2b15cb3dSCy Schubert <dd>This file is structured as a standard Bison file and consists of three main parts, separated by <tt>%%</tt>:</dd> 101ea906c41SOllivier Robert</dl> 102ea906c41SOllivier Robert<ol> 103*2b15cb3dSCy Schubert <li>The prologue and bison declarations: This section contains a list of the terminal symbols, the non-terminal symbols and the types of these symbols.</li> 104*2b15cb3dSCy Schubert <li>The rules section: This section contains a description of the actual phrase-structure rules that are used to parse the configuration commands. Each rule consists of a left-hand side (LHS), a right-hand side (RHS) and an optional action. As is standard with phrase-structure grammars, the LHS consists of a single non-terminal symbol. The RHS can contain both terminal and non-terminal symbols, while the optional action can consist of any arbitrary C code.</li> 105*2b15cb3dSCy Schubert <li>The epilogue: This section is left empty on purpose. It is traditionally used to code the support functions needed to build the ASTs Since, we have moved all the support functions to <b>ntp_config.c</b>, this section is left empty.</li> 106ea906c41SOllivier Robert</ol> 107ea906c41SOllivier Robert<h4>Prologue and Bison Declarations</h4> 108ea906c41SOllivier Robert<p>All the terminal symbols (also known as tokens) have to be declared in the prologue section. Note that terminals and non-terminals may have values associated with them and these values have types. (More on this later). An unnamed union has to be declared with all the possible types at the start of the prologue section. For example, we declare the following union at the start of the <b>ntp_config.y</b> file:</p> 109ea906c41SOllivier Robert<p class="style1"><tt>%union {<br> 110ea906c41SOllivier Robert char *String;<br> 111ea906c41SOllivier Robert double Double;<br> 112ea906c41SOllivier Robert int Integer;<br> 113ea906c41SOllivier Robert void *VoidPtr;<br> 114ea906c41SOllivier Robert queue *Queue;<br> 115ea906c41SOllivier Robert struct attr_val *Attr_val;<br> 116ea906c41SOllivier Robert struct address_node *Address_node;<br> 117ea906c41SOllivier Robert struct setvar_node *Set_var;<br> 118ea906c41SOllivier Robert /* Simulation types */<br> 119ea906c41SOllivier Robert server_info *Sim_server;<br> 120ea906c41SOllivier Robert script_info *Sim_script;<br> 121ea906c41SOllivier Robert }</tt></p> 122ea906c41SOllivier Robert<p>Some tokens may not have any types. For example, tokens that correspond to reserved words do not usually have types as they simply indicate that a reserved word has been read in the input file. Such tokens have to be declared as follows:</p> 123ea906c41SOllivier Robert<p><tt>%token T_Discard<br> 124ea906c41SOllivier Robert %token T_Dispersion</tt></p> 125ea906c41SOllivier Robert<p>Other tokens do have types. For example, a <tt>T_Double</tt> token is returned by the scanner whenever it sees a floating-point double in the configuration file. The value associated with the token is the actual number that was read in the configuration file and its type (after conversion) is double. Hence, the token <tt>T_Double</tt> will have to be declared as follows in the prologue of <b>ntp_config.y</b> file:</p> 126ea906c41SOllivier Robert<p><tt>%token <Double> T_Double </tt></p> 127ea906c41SOllivier Robert<p>Note that the declaration given in the angled brackets is not <tt>double</tt> but <tt>Double</tt>, which is the name of the variable given in the <tt>%union {}</tt> declaration above.</p> 128ea906c41SOllivier Robert<p>Finally, non-terminal symbols may also have values associated with them, which have types. This is because Bison allows non-terminal symbols to have actions associated with them. Actions may be thought of as small functions which get executed whenever the RHS of a non-terminal is detected. The return values of these functions are the values associated with the non-terminals. The types of the non-terminals are specified with a <tt>%type</tt> declaration as shown below:</p> 129ea906c41SOllivier Robert<p><tt>%type <Queue> address_list<br> 130ea906c41SOllivier Robert %type <Integer> boolean</tt></p> 131ea906c41SOllivier Robert<p>The <tt>%type</tt> declaration may be omitted for non-terminals that do not return any value and do not have type information associated with them.</p> 132ea906c41SOllivier Robert<h4>The Rules Section </h4> 133ea906c41SOllivier Robert<p>The rule section only consists of phrase-structure grammar rules. Each rule typically has the following format:</p> 134ea906c41SOllivier Robert<p><tt>LHS : RHS [{ Actions }]<br> 135ea906c41SOllivier Robert ;</tt></p> 136ea906c41SOllivier Robert<p>where LHS consists of a single non-terminal symbol and the RHS consists of one or more terminal and non-terminal symbols. The <tt>Actions</tt> are optional and may consist of any number of arbitrary C statements. Note that Bison can only process LALR(1) grammars, which imposes additional restrictions on the kind of rules that can be specified. Examples of rules are shown below:</p> 137ea906c41SOllivier Robert<p><tt>orphan_mode_command<br> 138ea906c41SOllivier Robert : T_Tos tos_option_list<br> 139ea906c41SOllivier Robert { append_queue(my_config.orphan_cmds, $2); }<br> 140ea906c41SOllivier Robert ;</tt></p> 141ea906c41SOllivier Robert<p><tt>tos_option_list<br> 142ea906c41SOllivier Robert : tos_option_list tos_option { $$ = enqueue($1, $2); }<br> 143ea906c41SOllivier Robert | tos_option { $$ = enqueue_in_new_queue($1); }<br> 144ea906c41SOllivier Robert ;</tt></p> 145ea906c41SOllivier Robert<p>The <tt>$n</tt> notation, where <tt>n</tt> is an integer, is used to refer to the value of a terminal or non-terminal symbol. All terminals and non-terminal symbols within a particular rule are numbered (starting from 1) according to the order in which they appear within the RHS of a rule. <tt>$$</tt> is used to refer to the value of the LHS terminal symbol - it is used to return a value for the non-terminal symbol specified in the LHS of the rule.</p> 146ea906c41SOllivier Robert<h4>Invoking Bison </h4> 147ea906c41SOllivier Robert<p>Bison needs to be invoked in order to convert the <b>ntp_config.y</b> file into a C source file. To invoke Bison, simply enter the command:</p> 148ea906c41SOllivier Robert<p><tt>bison ntp_config.y</tt></p> 149ea906c41SOllivier Robert<p>at the command prompt. If no errors are detected, an <b>ntp_config.tab.c</b> file will be generated by default. This generated file can be directly included into the <b>ntp_config.c</b> file.</p> 150ea906c41SOllivier Robert<p>If Bison report shift-reduce errors or reduce-reduce errors, it means that the grammar specified using the rules in not LALR(1). To debug such a grammar, invoke Bison with a <tt>-v</tt> switch, as shown below. This will generate a <b>ntp_config.output</b> file, which will contain a description of the generated state machine, together with a list of states that have shift-reduce/reduce-reduce conflicts. You can then change the rules to remove such conflicts.</p> 151ea906c41SOllivier Robert<p><tt>bison -v ntp_config.y</tt></p> 152ea906c41SOllivier Robert<p>For more information, refer to the <a href="http://www.gnu.org/software/bison/manual/html_mono/bison.html">Bison manual</a>.</p> 153ea906c41SOllivier Robert<p><b>ntp_config.c</b></p> 154ea906c41SOllivier Robert<p>This file contains the major chunk of the configuration code including all the support functions needed for building and traversing the ASTs. As such, most of the functions in this file can be divided into two groups:</p> 155ea906c41SOllivier Robert<ol> 156*2b15cb3dSCy Schubert <li>Functions that have a <tt>create_</tt> prefix. These functions are used to build a node of the AST.</li> 157*2b15cb3dSCy Schubert <li>Functions that have a <tt>config_</tt> prefix. These functions are used to traverse the AST and configure NTP according to the nodes present on the tree.</li> 158ea906c41SOllivier Robert</ol> 159*2b15cb3dSCy Schubert<h4 id="guidelines">Guidelines for Adding Configuration Commands</h4> 160ea906c41SOllivier Robert<p>The following steps may be used to add a new configuration command to the NTP reference implementation:</p> 161ea906c41SOllivier Robert<ol> 162*2b15cb3dSCy Schubert <li>Write phrase-structure grammar rules for the syntax of the new command. Add these rules to the rules section of the <b>ntp_config.y</b> file. </li> 163*2b15cb3dSCy Schubert <li>Write the action to be performed on recognizing the rules. These actions will be used to build the AST.</li> 164*2b15cb3dSCy Schubert <li>If new reserved words are needed, add these to the <tt>struct key_tok keyword_list[]</tt>structure in the <b>ntp_config.c </b>file. This will allow the scanner to recognize these reserved words and generate the desired tokens on recognizing them.</li> 165*2b15cb3dSCy Schubert <li>Specify the types of all the terminals and non-terminal symbols in the prologue section of the <b>ntp_config.c</b> file.</li> 166*2b15cb3dSCy Schubert <li>Write a function with a <tt>config_</tt> prefix that will be executed for this new command. Make sure this function is called in the <tt>config_ntpd()</tt>function.</li> 167ea906c41SOllivier Robert</ol> 168ea906c41SOllivier Robert<hr> 169*2b15cb3dSCy Schubert<address> 170*2b15cb3dSCy Schubert<a href="mailto:skamboj@udel.edu">Sachin Kamboj</a> 171*2b15cb3dSCy Schubert</address> 172ea906c41SOllivier Robert<script type="text/javascript" language="javascript" src="scripts/footer.txt"></script> 173ea906c41SOllivier Robert</body> 174ea906c41SOllivier Robert</html> 175
