Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

An Estelle-C compiler for automatic protocol implementation Chan, Robin Isaac Man-Hang 1987

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1987_A6_7 C39.pdf [ 3.64MB ]
Metadata
JSON: 831-1.0051896.json
JSON-LD: 831-1.0051896-ld.json
RDF/XML (Pretty): 831-1.0051896-rdf.xml
RDF/JSON: 831-1.0051896-rdf.json
Turtle: 831-1.0051896-turtle.txt
N-Triples: 831-1.0051896-rdf-ntriples.txt
Original Record: 831-1.0051896-source.json
Full Text
831-1.0051896-fulltext.txt
Citation
831-1.0051896.ris

Full Text

AN ESTELLE-C COMPILER FOR AUTOMATIC PROTOCOL IMPLEMENTATION  by  R O B I N I S A A C MAN-HANG  CHAN  B.Sc, The University of British Columbia, 1980 M.Sc, The University of British Columbia, 1983  A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F THE REQUIREMENTS FOR T H E DEGREE OF MASTER OF SCIENCE  in T H E F A C U L T Y OF G R A D U A T E STUDIES (DEPARTMENT OF C O M P U T E R SCIENCE)  We accept this thesis as conforming to the required standard  T H E U N I V E R S I T Y O F BRITISH C O L U M B I A October 1987 © Robin Isaac Man-Hang Chan, 1987  In  presenting  degree  at  this  the  thesis  in  University of  partial  fulfilment  of  British Columbia, I agree  freely available for reference and study. I further copying  of  department  this or  publication of  thesis for by  his  or  her  representatives.  that the  for  an advanced  Library shall make  it  It  is  granted  by the  understood  that  head of copying  my or  this thesis for financial gain shall not be allowed without my written  Computer Science  The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date  requirements  agree that permission for extensive  scholarly purposes may be  permission.  Department of  the  October 13, 1987  Abstract Over the past few years, much experience has been gained in semi-automatic protocol implementation using an existing Estelle-C compiler developed at the University of British Columbia. However, with the continual evolution of the Estelle language, that compiler is now obsolete. The present study found substantial syntactic and semantic differences between the Estelle language as implemented by the existing compiler and that specified in the latest ISO document to warrant the construction of a new Estelle-C compiler. The result is a new compiler which translates Estelle as defined in the second version of the ISO Draft Proposal 9074 into the programming language C. The new Estelle-C compiler addresses issues such as dynamic reconfiguration of modules and maintenance of priority relationships among nested modules. A run-time environment capable of supporting the new Estelle features is also presented. The implementation strategy used in the new Estelle-C compiler is illustrated by using the alternating bit protocol found in the ISO Draft Proposal 9074 document.  u  Contents Abstract  ii  Contents  iii  List of Figures  v  Acknowledgement  vi  1 Introduction 1.1 1.2  1  Motivations for a New Estelle Compiler Thesis Outline  2 Estelle Evolution 2.1  2.2  2.3  1 2  3  Module Hierarchy 2.1.1 Static Organization 2.1.2 Dynamic Organization Module Configuration 2.2.1 Dynamic Module Instantiation 2.2.2 Dynamic Module Interconnection Justification for a New Estelle-C Compiler 2.3.1 Syntactic Issues 2.3.2 Semantics Issues 2.3.3 User Issues  3 Estelle to C Translation  5 5 6 7 7 8 9 9 10 11  13  3.1  Global Declaration Blocks 3.1.1 Signal Parameter Block 3.1.2 Module Variable Block  14 14 16  3.2  Run-time Control Blocks 3.2.1 Signal Control Block  16 18  3.2.2 3.2.3  19 20  Channel Control Block Process Control Block  iii  3.3  3.4 3.5  3.2.4 Improvement over past Estelle Compilers Run-time Support Routines 3.3.1 Process Control Block Routines 3.3.2 Channel Control Block Routines 3.3.3 Signal Control Block Routines Module Translation 3.4.1 Initialization Routine 3.4.2 Transition Routine Transition Translation 3.5.1 Transition Clauses 3.5.2 Transition Blocks  22 23 24 24 25 26 26 29 29 31 36  4 Estelle Run-time Execution 4.1 Run-time Organization 4.1.1 Initialization Routines 4.1.2 Scheduler Routine 4.2 Transition Processing 4.2.1 Input Transitions 4.2.2 Spontaneous Transitions 4.2.3 Delayed Transitions 4.2.4 No Enabled Transitions  37 37 38 39 41 41 42 42 43  5 Conclusions 5.1 Thesis Summary  44 44  5.2  Future Work  46  Bibliography  48  A Alternating Bit Protocol — Estelle Specification  50  B Alternating Bit Protocol — Generated Codes  60  C Process Control Block Support Routines  76  D Channel Control Block Support Routines  79  E  89  Signal Control Block Support Routines  iv  List of Figures 3.1 3.2 3.3  Signal Parameter Block Structure Module Variable Block Structure Signal Control Block Structure  15 17 18  3.4 3.5  Channel Control Block Structure Process Control Block Structure  19 21  3.6 3.7  Initialization Routine Transition Routine  28 30  3.8 3.9 3.10 3.11 3.12  Codes Codes Codes Codes Codes  32 32 33 34 36  4.1 4.2  Main Driver Routine Run-time Scheduler Routine  generated generated generated generated generated  for a F R O M clause for a W H E N clause for a P R O V I D E D clause for a D E L A Y clause for an O U T P U T statement  37 40  v  Acknowledgement The author wishes to express his thanks to his supervisor, Dr. Son Vuong, for his guidance and to Dr. Samuel Chanson for his careful reading of the thesis. He also wishes to thank his wife, Silvian, for her many helpful suggestions in the preparation of this manuscript and for her patience and support throughout the course of this work.  vi  Chapter 1  Introduction Estelle is a formal description technique ( F D T ) developed to be used by ISO standards committees for the specification of communication protocols and services destined to become international standards. The use of formal methods for protocol specification reduces the risks of erroneous or incompatible implementations of these protocols. In addition, the availability of precise and unambiguous descriptions of protocols allows automatic tools to be built for generating protocol implementations directly from the formal specifications. In response to the challenge of realizing automatic implementation of protocols from Estelle specifications, the first Estelle compiler was developed at the University of Montreal [Gerb83]. This compiler accepts Estelle specifications and generates implementation codes in Pascal. Currently, several Estelle compilers, interpreters and simulators have already been developed [Ansa87,Cour86,Garg87].  1.1  Motivations for a New Estelle Compiler A t the University of British Columbia (UBC), an Estelle-C compiler was developed by  Daniel Ford in 1984 [Ford85]. T h e compiler accepts Estelle as defined by the 1984 Estelle working document [Este84] and generates target codes in the programming language C. The  1  CHAPTER  1.  INTRODUCTION  2  original compiler was found to be erroneous and was subsequently improved by Alan Lau in 1986 [Lau86]. The improved compiler was successfully used by Lau in a comparative study on semi-automatic versus manual implementation [Vuon87,Vuon88] of the ISO class 2 transport protocol [IS082a,IS082b]. However, the Estelle language has undergone two major changes since 1984 and is currently in the second draft proposal stage [Este85,Este86]. The U B C Estelle-C compiler is now obsolete due to the substantial differences between the current Estelle specification and the Estelle language as implemented by Ford. Therefore, it is necessary to build a new U B C Estelle-C compiler that will conform to the new standards [Este86] and, thus, allow further works in automatic protocol implementations.  1.2  Thesis Outline This thesis describes the implementation of a new Estelle-C compiler. Chapter 2 presents  the changes made to the Estelle language since 1984 and the justification for the reimplementation of a new compiler instead of the modification of the old compiler to conform to the new standards. Chapter 3 describes the translation scheme used in the new compiler and compares it with the scheme used in the old compiler. The implementation strategy used in the new Estelle-C compiler is illustrated by using the alternating bit protocol. Chapter 4 discusses the run-time environment used in the new compiler. Chapter 5 concludes the thesis with some insights gained from this project.  Chapter 2  Estelle Evolution Estelle is a hybrid formal protocol description technique which combines an underlying extended finite state machine model with the use of a programming language notation. Syntactically, Estelle is based on the programming language Pascal with additional features borrowed from Ada and Modula-2. An Estelle specification describes a complex protocol specification as a hierarchical structure of increasingly refined communicating finite state machines called modules. The syntax provides constructs necessary to specify state transitions within the modules as well as the means to interconnect the various specified modules. Semantically, these modules are allowed to be executed in parallel. The modules communicate with each other through abstract interfaces called interaction points. A bidirectional communication path between two interacting modules, called a channel, is formed when two interaction points, one from each module, are connected together. After a channel is established between two modules, the modules can interact by transmitting units of information, called interactions, through the channel. The dynamics of a channel is modeled abstractly as a pair offirst-in-first-outqueues located at the two linked interaction points. Each interaction signaled between two modules is routed  3  CHAPTER  2.  ESTELLE  EVOLUTION  4  from the interaction point at the sending module to the queue in the interaction point at the receiving module. Each channel is associated with a channel type. For each channel type, a set of parameterized interaction primitives can be specified for generating interaction instances which are to be transmitted through the channel. Because of the bidirectional nature of the channels, two interaction role identifiers must be specified for each channel in order to distinguish the directions. Each of the allowable interaction primitives may both of the defined roles. The  two  be associated with either one or  use of the role identifier allows each interaction primitive to  be specified as either unidirectional or bidirectional. The two corresponding interaction points for each channel must have opposite roles so that they can be used to send and to receive interactions of the opposite type. The abstraction provided by the Estelle channel can be used naturally for modeling the set of service primitives allowable at the boundaries between two adjacent protocol layers. When a protocol specification is refined into submodules, the same abstraction can also be used to specify interactions between any two submodules. Excellent descriptions of the Estelle features and facilities can be found in Linn [Linn86] and Courtiat et al. [Cour86], This chapter only describes the changes to the Estelle language from the 1984 working document [Este84] to its present 1986 draft proposal form [Este86] and concludes with a justification for building a new modifying the current U B C  Estelle-C compiler.  Estelle-C compiler from scratch instead of  CHAPTER  2. ESTELLE  EVOLUTION  5  Module Hierarchy  2.1  Some of the major differences between the Estelle language as defined in the original working document [Este84] and that defined in the resulting draft proposal documents [Este85,Este86] are the changes made to the hierarchical structuring of the modules. Since a module is the basic unit of protocol specification in Estelle, the changes have profound effects on the run-time environment that the new Estelle-C compiler must support.  2.1.1  Static Organization  A protocol specification is originally defined as a hierarchy of modules of two different types [Este84]. A t the bottom of the module hierarchy are processes. A process defines an atomic unit of protocol specification as an extended finite state machine which cannot be further subdivided. The behavior of a process is specified as a list of possible transitions. A l l processes are specified to be executed in parallel. The modules at the higher layers in the module hierarchy are called refinements. Refinements may be further divided into submodules, each of which may be either a process or another refinement. Refinements, however, may not contain any transition specification. The sole purpose of the refinement modules is to impose a structure on the set of defined processes during system initialization time; these modules are inactive during protocol execution. The implication of this modular organization is that a protocol specified in this manner has a static structure. Since only the bottom layer of the hierarchy contains active modules, the structure cannot be changed during run-time. Another consequence of this organization is that the structure is linear. The set of active modules can be linked together into a linear list. Simple round-robin scheduling over this list will suffice during run-time to simulate parallelism  CHAPTER  2. ESTELLE  EVOLUTION  6  [Ford85].  2.1.2  Dynamic Organization  In the first draft proposal for Estelle [Este85], transition execution is allowed in the higher level modules. In addition, provisions are made to allow modules to share common variables. In order to ensure mutual exclusion between the shared variables, two restrictions are imposed on the structuring principles of an Estelle protocol specification. First, two types of modules with different execution semantics are defined. An activity is a module which is considered to be atomic and cannot be substructured. A process is a module which may be substructured into either child processes or child activities. Processes at the same level may be run in parallel, but activities may be run only in an interleaved fashion. Second, a parent/child priority relation is imposed on the module hierarchy. If a transition of a parent module is enabled, no child may begin a transition. The first restriction will ensure mutual exclusion among modules at the same level in the module hierarchy if they are specified as activities. The second restriction will ensure mutual exclusion among modules at different levels in the module hierarchy. In the second draft proposal for Estelle [Este86], the major change to the Estelle language specification is to forbid the use of shared variables among modules at the same level in the module hierarchy. The inclusion of this restriction eliminates the concern of mutual exclusion among modules at the same level. Consequently, there is no further need to distinguish between processes and activities. However, the concepts of processes and activities are retained to distinguish the two possible forms of module execution semantics. The process abstraction represents a synchronous parallel execution while the activity abstraction represents a nondeterministic sequential execution. Because of these new semantics, activity modules may now  CHAPTER  2. ESTELLE  EVOLUTION  7  be further substructured into other activities. The new module synchronization semantics defined in the two Estelle draft proposals [Este85,Este86] imply a more complicated run-time environment than is necessary for Estelle as defined in the working document [Este84]. The new run-time scheduler must differentiate between modules at different levels in order to enforce the parent/child priority relationships. The scheduler used in the new Estelle-C compiler is discussed in Section 4.1.  Module Configuration  2.2  Module configuration is the process of instantiating and interconnecting the modules defined in an Estelle specification. Module configuration can only be performed by a parent module on its immediate child modules. In the original version of Estelle [Este84], module configuration can only be performed at system initialization time. Since all modules above the bottom level are inactive, the number and the types of modules will remain unchanged for the life-time of the specified system. In the later versions [Este85,Este86] where active modules are present in the higher levels, module configuration may be carried out any time. The potential result of this enhancement is a protocol specification with a dynamically varying module organization.  2.2.1  Dynamic Module Instantiation  The process of module instantiation includes the declaration of a module variable, the initialization of a module instance, and the binding of the initialized module instance to the module variable. In the working document version of Estelle [Este84], module instantiation is an implied operation associated with the declaration of a module variable. In the later versions [Este85,Este86], modules are explicitly created and initialized by using the INIT statement. Module termination  CHAPTER  2.  ESTELLE  EVOLUTION  8  is possible using the RELEASE statement. These two special Estelle statements may  be used  either at system initialization or within transition execution. The use of explicit statements to perform these two operations in an Estelle protocol specification provides the power to change the number and the type of modules within the specification dynamically. The need to support dynamic module creation and termination results in a run-time environment which must maintain the complete hierarchical module organization at all times. In contrast, under the old Estelle environment, this information may  be discarded after the system has been initialized  [Ford85].  2.2.2  D y n a m i c M o d u l e Interconnection  With the addition of dynamic module instantiation, it becomes necessary to provide explicit module interconnection statements. These operations are provided in Estelle by the special statements: CONNECT, DISCONNECT, ATTACH and DETACH. The CONNECT and DISCONNECT statements are used to alter the interconnections between modules at the same level; and the ATTACH and DETACH statements are used to alter the interconnections between modules at adjacent levels. With the added capabilities for dynamic reconfiguration, the immediate parent of a set of modules can be specified to act as a supervisory manager. However, these provisions for dynamic reconfiguration of the various entities in a protocol specification result in an Estelle run-time environment that is more complex than one which simply maintains a complete module hierarchy.  CHAPTER  2. ESTELLE  EVOLUTION  9  Justification for a New Estelle-C Compiler  2.3  With the basic ideas underlying the semi-automatic approach to protocol implementation well understood and demonstrated by the many existing Estelle compilers [Boch87a], the major motivation for developing a new compiler for Estelle is to upgrade the UBC Estelle-C compiler to support the latest Estelle language specification [Este86]. However, it is apparent that there are many issues which must be addressed in changing from a static run-time environment to a dynamic one. This section describes the justifications for a complete rewrite of the Estelle-C compiler instead of modifying the existing compiler.  2.3.1  Syntactic Issues  One of most important reasons for rewriting the new Estelle-C compiler is that the syntax of Estelle has changed so significantly that building a new parser is desirable. The old compiler was written with the aid of the UNIX utilities lex and yacc. A significant omission in the old compiler was the lack of syntax error recovery mechanisms. The building of a new parser offers an opportunity to incorporate this important compiler feature into the new compiler. With added error recovery as part of the design goal, the Estelle grammar is rewritten into a LL(1) form. Then, the parser for the new Estelle-C compiler is hand-coded in C using recursive descent techniques. Syntax error recovery is carried out using the panic mode technique with a dynamic stop symbol set. An unrelated advantage gained from rewriting the compiler without using lex and yacc is the possibility for further development of the new compiler in non-UNIX environments.  CHAPTER  2.3.2  2.  ESTELLE  EVOLUTION  10  Semantics Issues  Another important reason for rewriting the new compiler relates to semantics issues. Being a formal description technique for protocol specification, the Estelle language must have precise meaning; otherwise, protocols specified in Estelle will not have a sound foundation and may be opened to different interpretations. In order to satisfy this requirement, the second draft proposal for Estelle is published with a new section on formal semantics [Este86]. When the implementation of the old Estelle-C compiler is compared with the new formal semantics, several features are found to be incompatible. The major area of incompatibility has to do with the scoping rules for variables. The old Estelle compiler did not pay particular attention to the scoping of many variables. Variables local to individual transitions were not supported. Module parameters were not made available to the module transitions. Procedures and functions defined within a module were not allowed access to global variables declared within the same module. Furthermore, the old Estelle-C compiler is still erroneous despite the improvements made by Alan Lau [Lau86]. In particular, the old compiler lacks some important Estelle features, such as the data types S E T and multidimensional A R R A Y . Solutions to these and other problems are all part of the redesign of the new Estelle-C compiler. Other semantics issues deal with error checking. The old Estelle-C compiler has no provision for checking semantic errors besides Estelle specific semantic errors. Since the code generated by the Estelle compiler would have to be further compiled by the C compiler, the rationale was that the C compiler can be used for most of the semantic checks. However, by placing most of semantic checking burden on the C compiler, the error messages from the C compiler become cryptic. Users of the compiler without firm understanding of the organization of the  CHAPTER  2.  ESTELLE  EVOLUTION  11  generated C-codes frequently have trouble understanding errors detected during the subsequent C compilation. In order to build a more "user-friendly" Estelle compiler, more emphasis is placed on semantic checking in the new Estelle-C compiler. 2.3.3  U s e r Issues  Building extensive error checking facilities into the new Estelle-C compiler is not adequate to make the new compiler user-friendly. The old Estelle-C compiler produces a C program which is not readily compilable by the C compiler without extensive user modifications. Also, the old Estelle run-time support routines contain specification dependent details which must be modified for each Estelle specification. In order to generate an executable implementation from an Estelle specification, the user must recompile the run-time support routines using the C compiler along with the C-code generated by the Estelle-C compiler. In the new Estelle-C compiler, it is no longer necessary for the user to modify any of the generated codes. Besides improving and extending the run-time routines to support the new Estelle features, all specification dependent details have been extracted from these run-time support routines. The specification independent routines have been precompiled into a single object library.  After  the generated C-codes have been compiled by the C compiler, they can be easily linked to this object library to form the final executable program. In summary, the new Estelle-C compiler is written to incorporate the features in the latest version of the Estelle language and to improve the user-friendliness of the compiler. The userfriendliness aspect of the improvement includes the use of effective error diagnostics for the user and the freeing of the user from the need to know the details in the underlying run-time environment. The goal is to increase the degree of automation than that achieved in the previous semi-automatic implementations of protocols from formal specifications. W i t h regards to the  CHAPTER  2.  ESTELLE  EVOLUTION  shortcomings in the old Estelle-C compiler, a complete rewrite of the compiler is desirable well as necessary.  Chapter 3  Estelle to C Translation The translation of Estelle to C in the new Estelle-C compiler follows the implementation strategy used by Gerber [Gerb83], a strategy which was also adopted by Ford [Ford85]. Each Estelle module is translated into two separate C routines. One routine is used for transition execution while the other is used for module initialization. The t r a n s i t i o n r o u t i n e implements the finite state machine specified for the module. The i n i t i a l i z a t i o n r o u t i n e sets up the internal states of the module before it is ready for the subsequent transition execution. Besides generating executable codes to implement the modules, the Estelle-C compiler also generates two sets of global declaration structures. One structure, called the signal p a r a m e t e r  block  (FDTSVAR),  is used for storing the parameter information carried in the interactions  passed between modules. The other structure, called the m o d u l e v a r i a b l e  block  (FDTLVAR),  is used by each module for storing local variables. After these four sets of generated C codes are compiled and then linked together with a set of pre-compiled run-time support routines, an executable protocol implementation results. The Estelle run-time environment is constructed from three major control blocks representing the three major abstractions defined in the Estelle language. The interactions which are  13  CHAPTER  3.  ESTELLE  TO  C  TRANSLATION  14  signaled between modules are represented by signal c o n t r o l b l o c k s (FDTSCBs).  The chan-  nels through which the interactions are transmitted are represented by c h a n n e l c o n t r o l blocks (FDTCCBa).  Finally, the modules which send and receive the interactions are represented by  process c o n t r o l b l o c k s The  (FDTPCBs).  following sections present the Alternating Bit Protocol as an example in Estelle to  C translation. The complete Estelle specification for the Alternating Bit Protocol and the C program generated from it are included in Appendices A and B, respectively. The  sections  begin with the explanation on the generation of the two global declaration blocks followed by a description of the three control blocks and the ways in which they are combined with the generated declaration codes and with each other to form the run-time environment. Subsequently, the translation of an Estelle module into an initialization and a transition routine is discussed.  3.1  Global Declaration Blocks Two  global declaration blocks are generated to represent all of the specification dependent  variables needed during run-time. To facilitate the ease of understanding the generated code, the identifiers used in the generated C code retain their Estelle names. The elaborate variant structures described below is necessary to protect the Estelle names from identifier conflicts when used within a C program. 3.1.1  Signal Parameter Block The s i g n a l p a r a m e t e r b l o c k (FDTSVAR)  is a three-level variant record structure repre-  senting the combination of all specified parameters in all interaction primitives for all channel types within an Estelle specification. The FDTSVAR is shown in Figure 3.1.  generated for the alternating bit protocol  CHAPTER  3. ESTELLE  typedef union  TO C  TRANSLATION  i  /* CHANNEL U_access_point p r i m i t i v e s and t h e i r i d e n t i t y numbers */ union { struct { i n t udata ; } SEND.REQ ; i n t RECV.REQ ; struct { i n t udata ;  /* 1.  SEND.REQ (udata :: udata.type); */  /* 2.  RECV.REQ; */  /* 3.  RECV.RSP (udata :: udata_type); */  } RECV.RSP ; } U.access.point ; /* CHANNEL N.access.point p r i m i t i v e s and t h e i r i d e n t i f i e r s */ union {. struct { ndata.type ndata ; } DATA.REQ ; struct { ndata.type ndata ; > DATA.RSP ; } N.access.point ;  /* 1.  DATA.REQ (ndata : ndata.type); */  /* 2.  DATA.RSP (ndata : ndata.type); */  /* CHANNEL S.access.point p r i m i t i v e s and t h e i r i d e n t i f i e r s */ union { i n t TIMER.REQ ; i n t TIMER.RSP ; } S.access.point ;  /* 1. /* 2.  TIMER.REQ; */ TIMER.RSP; */  } FDTSVAR;  Figure 3.1: Signal Parameter Block Structure  15  CHAPTER  3.  ESTELLE  TO C  16  TRANSLATION  The first level variant structures identify the channel types while the second level variant structures identify the interaction primitives within the channels. For easy identification, the interaction primitives defined for each channel type are numbered. The identity numbers assigned by the Estelle-C compiler for the interaction primitives are shown in Figure 3.1. The innermost structures represent an enumeration of the parameters for the interaction primitives. These innermost structures are absent for interaction primitives without parameters.  3.1.2  Module Variable Block  The  module variable block (FDTLVAR)  is a two-level variant record structure that  contains the complete global state variables for all module bodies. The module variable block generated for the alternating bit protocol is presented in Figure 3.2. The outer level variant structures identify the module bodies in the Estelle specification. The inner structures store all major and minor state variables declared for the module bodies. The variables are collected from the various Estelle declaration sections. The first set of variables is extracted from the module parameter declaration and the exported variable declaration sections in the associated module header declarations. The rest of the variables are derived from the S T A T E , S T A T E S E T , VAR and M O D V A R declaration sections in the module bodies. The origins of the various variables in the FDTLVAR  are shown in Figure 3.2 as comments. Module bodies  without any variable declarations are not represented in the FDTLVAR  3.2  structure.  Run-time Control Blocks Three control blocks are used to represent all of the specification independent bookkeeping  information during run-time.  The following sections describe the three control blocks and  conclude with a discussion on the improvements made with respect to the old Estelle-C run-  CHAPTER  3. ESTELLE  TO C  TRANSLATION  typedef union { struct { i n t cep_id ; int flag ;  /* /* /* /*  i n t data ; } user_body; struct {  /* MODULE network_body */ /* V a r i a b l e */  i n t count ; } network_body; struct i i n t time ; int  FDT3 ;  i n t stop ; i n t stop_bis ; } timer_body; struct { i n t cep_id ; set.type EITHER ; i n t STATE ; ndata_type buf ; msg_type recv_msg msg_type send_msg buf_type recv.buf buf_type send_buf  MODULE user.body */ Parameter */ V a r i a b l e */ V a r i a b l e */  ; ; ; ;  i n t recv_seq ; i n t send_seq ; } datax_body; struct { i n t cep_id ; FDTPCB *timer_module ; FDTPCB *datax_module ; } abit_body; struct { FDTPCB *abit_module [ 2 ] ; FDTPCB *user_module [ 2 ]; FDTPCB *network_module ; > SPECIFICATION ; } FDTLVAR;  /* /* /* /* /*  MODULE timer.body */ Parameter */ Temporary */ V a r i a b l e */ V a r i a b l e */  /* /* /* /* /* /* /* /* /* /* /*  MODULE datax_body */ Parameter */ Stateset */ State */ Variable */ Variable */ Variable */  /* /* /* /*  MODULE abit.body */ Parameter */ Modvar */ Modvar */  /* /* /* /*  Modvar Modvar Modvar  Variable Variable Variable Variable  */ */ */ */  SPECIFICATION a b i t . s  Figure 3.2: Module Variable Block Structure  */ */ */  CHAPTER  3. ESTELLE  TO C  TRANSLATION  18  time control blocks.  3.2.1  Signal Control Block Each unit of interaction (or signal) sent through a channel is represented by a signal  c o n t r o l b l o c k (FDTSCB)  in conjunction with a s i g n a l p a r a m e t e r b l o c k (FDTSVAR).  described in Section 3.1.1, the FDTSVAR  As  is a specification dependent structure generated from  the channel type declaration sections in an Estelle specification. In contrast, the FDTSCB a specification independent run-time control block (Figure 3.3).  The  is  two blocks are linked  s t r u c t FDTSCB_struct { s t r u c t FDTSCB.struct int int int }; typedef  *next; cid; sid; *svar;  /* /* /* /*  Next s i g n a l Channel i d Primitive i d Parameters  */ */ */ */  s t r u c t FDTSCB_struct FDTSCB;  Figure 3.3: Signal Control Block Structure  together by the pointer svar located in the FDTSCB.  Since the FDTSVAR  contains only  interaction parameter fields (see Figure 3.1), additional information must be provided within the FDTSCB  for the identification of interaction primitives. With the FDTSVAR  implemented  as a three-level variant record structure, two identifiers are necessary to uniquely identify the interaction being conveyed. The first identifier, encoded in the field c i d , indicates the index number of the target interaction point within the target module. Since each interaction point is associated with only one channel type in Estelle, this number also identifies the channel type. The second identifier, stored in the field s i d , is used to specify the interaction primitive within  CHAPTER  3.  ESTELLE  TO C  TRANSLATION  19  the channel identified by cid. The next field is used for queue manipulation at the target interaction point.  3.2.2  Channel Control Block  Each interaction point associated with a channel is represented by a channel control block (FDTCCB).  The number of FDTCCBa  necessary to completely specify an Estelle channel at  run-time depends on the number of C O N N E C T and A T T A C H statements used to build the channel. Every C O N N E C T or A T T A C H operation involves two  FDTCCBa.  The bookkeeping for interaction point binding is maintained by three pairs of variables within each FDTCCB  (See Figure 3.4). The pair (targeta, channela) is used to specify the  struct FDTCCB_struct { struct FDTSCB.struct struct FDTPCB_struct int int  *head, * t a i l ; *targeta, *targetc, *targete; channela, channelc. channele; queue_kind;  >;  typedef struct FDTCCB.struct FDTCCB;  Figure 3.4: Channel Control Block Structure target interaction point of an A T T A C H operation when the target interaction point is located at a child module. The field targeta indicates the target module while the field channela specifies the index number of the target channel within the target module. Similarly, the pair (targetc, channelc) is used to represent the target interaction point of a C O N N E C T operation or the target interaction point of an A T T A C H operation when the target interaction point is located at a parent module. Because connected interaction points may be further attached to  CHAPTER  3. ESTELLE  TO C  TRANSLATION  20  other interaction points, in order to be efficient in determining the real target interaction point when interaction are sent between module, the pair (targete, channele) is used to specify the effective target interaction point directly. This tremendous amount of bookkeeping is necessary to keep track of the channel binding between modules so that channels may be DISCONNECTed and DETACHed afterwards. In contrast, under the old run-time environment for Estelle, where channels are prohibited from unbinding, only the effective target interaction point needs to be maintained in each FDTCCB  [Ford85].  The other fields with the FDTCCB  depicted in Figure 3.4 are used to implement the inter-  action queue. When an interaction, represented by a FDTSCB it will be queued at the opposite FDTCCB  is sent through one  FDTCCB,  indicated by the (targete, channele) pair. The  head and t a i l fields are pointers to the first and last FDTSCBs  in this queue, respectively.  In Estelle, interaction points may be specified with either COMMON or INDIVIDUAL queueing discipline. The queue_kind field is used to indicate this queueing discipline for the interaction point.  3.2.3  Process Control Block  Each module instance at run-time is represented by a process control block in conjunction with a module variable block (FDTLVAR).  While the FDTLVAR,  (FDTPCB) as described  in Section 3.1.2, is a specification dependent structure generated from the various variable declaration sections in an Estelle specification, the FDTPCB  is a specification independent  run-time control block (Figure 3.5). This control block is used to store bookkeeping information for each module instance for the duration of its existence at run-time. The fields parent, sib and ref are pointers used to maintain the static module hierarchical structure at run-time. They point to the parent module, the next sibling at the same hierarchical  CHAPTER  3.  ESTELLE  TO C  21  TRANSLATION  s t r u c t FDTPCB.struct struct struc t struct struct int int int int int int int int int int  FDTPCB..struct FDTPCB..struct FDTPCB..struct FDTCCB..struct  •parent; *sib; *ref; *chan; ipnum; ipnext; prio; sigcnt; delay; tO, t l ; spont; export; (*trans)(); *lvar;  typedef s t r u c t FDTPCB.struct  /* /* /* /* /* /* /* /* /* /* /* /* /* /*  */ */ F i r s t c h i l d FDTPCB */ FDTCCB a r r a y */ Size of FDTCCB a r r a y */ Next i p to search */ Hierarchical level */ Pending s i g n a l count */ Delay clause i d */ Delay time l i m i t s */ Spontaneous present? */ Export v a r i a b l e s ? */ Transition routine */ Module v a r i a b l e b l o c k */ Parent FDTPCB Next s i b l i n g FDTPCB  FDTPCB;  Figure 3.5: Process Control Block Structure  CHAPTER  3. ESTELLE  TO C  TRANSLATION  22  level and the head of the list of child modules at the next hierarchical level, respectively. The address of the transition routine which implements the extended finite state machine specified for the module is stored at the field trans. The field lvar is a pointer to the  FDTLVAR  block. Since the number of interaction points in a module can be statically determined, all channel control blocks FDTCCBa  needed for a module are placed into one common array. The field  chan is used to point to this FDTCCB  array while the field ipnum is used to store the size of  this array. Each interaction point is assigned an index number into this array starting at the index value '1'. The FDTCCB  with the index value of 0' is an extra channel control block (  reserved for the COMMON queue. Interactions destined for a target interaction point specified with COMMON queueing discipline are queued in this COMMON FDTCCB.  Interactions destined  for a target interaction point specified with INDIVIDUAL queueing discipline are queued in the specified target FDTCCB.  T h e field s i g c n t indicates the sum of all pending interactions in  the queues. The three fields delay, tO and t l are used to implement DELAYed transitions (See Section 4.2.3 for detail). The remaining fields identify the hierarchical level of the module (prio), the next interaction queue to examine for the pending interactions (ipnext), and whether or not the module has spontaneous transitions (spont) and export variables (export).  3.2.4  Improvement over past Estelle C o m p i l e r s  The run-time data structures used in the new Estelle-C compiler represent some of the major improvements made to the new compiler as compared to those used in the old compilers [Gerb83,Ford85]. In the past, the signal parameter block is placed within the signal control block; and the  CHAPTER  3. ESTELLE  TO C  TRANSLATION  23  module variable block is placed within the process control block. Since, these two combined control blocks contain specification dependent information, they are different for different Estelle specifications. Furthermore, since the run-time routines must have access to the control blocks, it is necessary for the old run-time routines to be recompiled for different specifications. With the arrangement used in the new Estelle-C compiler, the specification dependent details are isolated into the FDTSVAR  and FDTLVAR  structures while the control blocks remain the  same for all specifications. Consequently, the new run-time support routines are specification independent and they no longer require recompilation. A second improvement is made in the structuring of the FDTCCBa. compiler, the FDTCCB8  In the old Estelle  are linked together into a linear list. Therefore, every channel access  must involve a linear search along this list for the required FDTCCB.  The new Estelle-C  compiler takes advantage of the fact that the number of channel is fixed for each module and assigns a unique index number to each channel. Channel access in the new Estelle-C compiler is thus performed by array indexing rather than by linear searching.  3.3  Run-time Support Routines The control blocks described so far are constructed into a run-time data structure that  reflects the module organization defined in the Estelle specification. This structure is built using a set of pre-written support routines. The calls to these routines are made by codes incorporated within the two sets of generated module routines. The support routines can be divided into three groups, each of which manipulates one type of control blocks. The following sections describe these three groups of support routines.  CHAPTER  3.3.1  3.  ESTELLE  TO C  TRANSLATION  24  Process Control Block Routines There are two process control block routines used to create and destroy process control  blocks. The codes for these routines are depicted in Appendix C. The routine FDTPCBinitO creates and initializes an FDTPCB.  This routine is used to instantiate a new  Estelle module  and it implements all of the specification independent operations required for the INIT operation defined in Estelle. The first part of the initialization process results in the linking of the newly created FDTPCB  to the FDTPCB  of its parent module and to the FDTPCBs  modules. Afterwards, the appropriate number of FDTCCBs  of its other sibling  are created for the module being  instantiated. Finally, other bookkeeping variables are initialized. The specification dependent operations are individually implemented in the initialization routines generated for each defined Estelle module (See Section 3.4.1 for detail). The routine FDTPCBtermO destroys a specified module and all its child modules recursively. This routine implements the RELEASE operation defined in Estelle.  3.3.2  Channel Control Block Routines The channel control blocks are manipulated by a set of seven run-time routines shown in  Appendix D. These routines can be divided into two functional groups. One  group consists of the two routines, F D T C C B i n i t O and FDTCCBtermO, are used to  allocate and to release the appropriate number of channel control blocks for a module. These two routines are in turn used by the routines, F D T P C B i n i t O and FDTPCBtermO, respectively, when modules are created and  destroyed.  The other group is made up of five routines used to bind and unbind pairs of communicating channel control blocks. The routines FDTCCBconnectO and FDTCCBdisconnO are used  CHAPTER  3. ESTELLE  TO C  to bind and unbind FDTCCBs  TRANSLATION  25  of modules at the same level in the module hierarchy. The  routines FDTCCBattachO, FDTCCBdetachl () and FDTCCBdetach2() are used to bind and unbind FDTCCBa  of modules at adjacent levels in the hierarchy. Essentially, they implement the  Estelle operations CONNECT, DISCONNECT, ATTACH, and DETACH respectively.  3.3.3 Signal Control Block Routines Interactions queued at a FDTCCB  are manipulated by four pre-written library routines  shown in Appendix E. In this version of the Estelle-C run-time environment, the interaction queues are implemented as singly-linked circular queues. The routine FDTSCBsignalO is used to dispatch an interaction through a specified channel. A call to this routine is generated as the last step in the translation of an OUTPUT statement (See also Section 3.5.2). The newly dispatched interaction is placed in either the COMMON channel or the specified target channel of the target module depending on the queueing discipline of the target interaction point (See also Section 3.2.3). The routine FDTSCBspontO is used when it is necessary to generate a spontaneous signal. A call to this routine is issued, when appropriate, after a transition is completed. The routine FDTSCBdisposeQ is used after a transition has been completed in order to disposed of a received input interaction or a spontaneous interaction (See also Section 3.4.2 for details). Finally, the function FDTSCBpendingO is used by the global scheduler to search for a pending signal destined for a particular process.  CHAPTER  3. ESTELLE  TO C  TRANSLATION  26  Module Translation  3.4  The module abstraction in an Estelle specification represents the basic unit of protocol specification. A m o d u l e t y p e is declared as an abstract data type. The external visibility of the module is defined in a m o d u l e header while the internal behavior is specified in a m o d u l e b o d y . T h e Estelle language definition allows several different module bodies to be specified for each module header. As described in Section 3.1.2, the module head and the global declarations within the module body are used to generate declaration structures within the module variable block (FDTLVAR).  The two C routines that are generated from each module are translated from  the initialization parts and the transition parts within the module body. The convention used in the Estelle-C compiler is to name these routines after their corresponding module body. In order to distinguish the initialization routine from the transition routine, the prefix FDT is added to the name of the initialization routine. There is one exception to this naming convention. The two routines translated from the outermost SPECIFICATION module are always named F D T S P E C I F I C A T I O N O and S P E C I F I C A T I O N ) , respectively. The following sections describe the general structure of the two generated implementation routines. The discussion on the translation of the transitions themselves is deferred until Section 3.5.  3.4.1  Initialization Routine  The i n i t i a l i z a t i o n r o u t i n e for a module is generated from the initialization parts within a module body. This routine is used to set up the initial states of the extended finite state machine representing the module. The initialization routine for a module is executed whenever  CHAPTER  3.  ESTELLE  TO C  TRANSLATION  27  an INIT statement referencing the module is executed by its parent module. The general structure for an initialization routine is depicted in Figure 3.6. The first part of the routine allocates a control block for the module. Initialization begins by calling the run-time support routine FDTPCBinitO to create a FDTPCB. linked to the FDTPCB.  Afterwards, an FDTLVAR  is created and  The routine FDTPCBinitO implements the specification independent  aspects for the INIT statement (See Section 3.3.1 for detail). The rest of the initialization routine represents the specification dependent portion of the initialization process. After a FDTPCB  and a FDTLVAR  has been allocated for the module, the initialization  routine begins with module parameter initialization. All the module parameters declared in the module header section for the module are passed to the initialization routine. These parameters are copied into the FDTLVAR  by assignment statements.  The next section in the routine contains the code for the initialization transitions. These transitions are usually responsible for calling other initialization routines which, in turns, instantiate the underlying submodules and then interconnect these submodules to the module being initialized. Other activities performed by the initialization transitions includes initializing the various global variables and setting the module into the proper state before the subsequent transition execution. If the module contain spontaneous transitions, a spontaneous signal is generated in the next section. The last step in the initialization routine returns the address of the created  FDTPCB  to the parent module which calls this initialization routine. This pointer is stored within the FDTLVAR  of the parent module for subsequent references to this particular child module.  CHAPTER  3.  ESTELLE  TO C  TRANSLATION  s t r u c t FDTPCB *FDTbody (parent, a r g l , arg2,  ...)  FDTPCB *parent; ...  /* type d e c l a r a t i o n s l o r a r g l , arg2, ...  */  { FDTPCB *pcb; FDTLVAR * l v a r ; /* Creates c o n t r o l blocks */ pcb = FDTPCBinit  (parent, ipnum, SPDNTbody. XPORTbody. TRANSbody)  pcb->lvar = ( i n t *) ( l v a r = (FDTLVAR *)  malloc(sizeof(FDTLVAR)));  /* Copying arguments to module v a r i a b l e b l o c k */ 1var->body.argl = a r g l ;  lvar->body.arg2 = arg2;  /* I n i t i a l i z a t i o n t r a n s i t i o n s (See S e c t i o n 3.5)  */  /* Generates a spontaneous i n t e r a c t i o n i f p o s s i b l e */ trans_end : i f (pcb->spont) FDTSCBspont (pcb); r e t u r n (pcb);  Figure 3.6: Initialization Routine  CHAPTER  3.4.2  3.  ESTELLE  TO C  TRANSLATION  29  Transition Routine  The transition routine for a module is generated from the transition parts within a module body. This part of the Estelle specification is used to define the state transitions that constitute the extended finite state machine representing the module. The routine itself is called whenever the run-time scheduler selects the corresponding module for execution. The general structure of a transition routine is depicted in Figure 3.7.  Two parameters  are passed to each transition routine when the module is executed by the scheduler. parameter process supplies the routine with the correct FDTPCB  The  for the module while the  parameter signal indicates the interaction selected by the scheduler to be processed by the module. Within the routine, the local variables lvar and svar are used to facilitate access to the FDTLVAR  and FDTSVAR  control blocks, respectively.  The codes in the first part of the routine implements the module transitions. The details for these codes are described in Section 3.5. The final section in the routine contains the exit sequence for the module. The details for these codes are explained in Section 4.2.  3.5  Transition Translation In Estelle, the transitions for an extended finite state machine may be described in either an  initialization part or a transition part within the module bodies. There may be zero or more of these transition description sections within a module body. A module without any initialization part will be initialized with the creation of its FDTPCB  and FDTLVAR  of its module parameters, if any, into its FDTLVAR.  A module without any transition part  blocks and the copying  are inactive after its initialization. Inactive modules are generally used as structuring devices which impose an hierarchical organization to their underlying child modules.  CHAPTER  3. ESTELLE  TO C  30  TRANSLATION  body (process, s i g n a l ) FDTPCB *process; FDTSCB * s i g n a l ; { FDTLVAR * l v a r = process->lvar; FDTSVAR *svar = signal->svar; /* Code f o r t r a n s i t i o n s  (See S e c t i o n 3.5) */  /* E x i t code when no t r a n s i t i o n was t r i g g e r e d i f ( s i g n a l - > c i d == 0) FDTSCBdispose (process, s i g n a l ) ; return; /* E x i t code when a t r a n s i t i o n was t r i g g e r e d trans_end : FDTSCBdispose (process, s i g n a l ) ; i f (process->spont) FDTSCBspont (process); /* E x i t code f o r spontaneous t r a n s i t i o n */ spont_end : process->delay = 0;  Figure 3.7: Transition Routine  */  */  CHAPTER  3. ESTELLE  TO C  TRANSLATION  31  Each transition is specified in two parts. The actions to be performed by the transition are defined by a Pascal style statement block. This transition block is preceded by zero or more transition clauses. The transition clauses are used to specify the enabling conditions which must be satisfied before the transition block can be executed. This section describes the translation of the transition clauses followed by the translation of the transition blocks.  3.5.1  T r a n s i t i o n Clauses  In Estelle, transition clauses may be used to specify the enabling conditions of a transition in terms of the present state (FROM clause), the input signal (WHEN clause), an enabling predicate (PROVIDED clause) or a transition priority (PRIORITY clause). Other clauses may be used to specify actions such as going to a specified next state (TO clause) or delaying the action for a specified time (DELAY clause). Finally, there is also a clause that can be used as a shorthand notation for a sequence of transition (ANY clause). The translation scheme for generating codes for the enabling transition clauses is essentially one of substituting a corresponding boolean expression for the clause. The strategy for translating the action transition clauses is to place statements that perform the indicated action within the enclosing transition block. Compare Appendices A and B for illustrations. The translation of most of the transition clauses are straight forward. A FROM clause is translated into a boolean expression testing for the current state (Figure 3.8). As described in Section 3.2, the current state for a module is stored as the variable STATE in the module variable block (FDTLVAR) expression (Figure 3.9).  for the module. The WHEN clause is also translated into a boolean Two tests must be made. First the specified interaction point is  tested against the incoming signal (signal->cid). Then the incoming interaction primitive type (signal->sid) must match the primitive specified in the clause.  CHAPTER  3. ESTELLE  TO C  if  32  TRANSLATION  (lvar->body.STATE  == <FROM state>)  < ... /* Nested t r a n s i t i o n s */ }  Figure 3.8: Codes generated for a F R O M clause  if  ( ( s i g n a l - > c i d == <channel>) && ( s i g n a l - > s i d == <primitive>)) < ... /* Nested t r a n s i t i o n s */ }  Figure 3.9: Codes generated for a W H E N clause Although the natural translation for a PROVIDED clause is also a boolean expression, but because of the possible presence of an OTHERWISE condition, its translation is not straight forward (Figure  3.10). The strategy taken in this implementation is to declare and initialize a  boolean flag to TRUE before the execution of the boolean expressions. After every PROVIDED clause where a boolean expression is specified, a statement is added to set the flag to FALSE. If the boolean expression is evaluated to TRUE, then the flag will be set to FALSE, otherwise the flag will remain TRUE. If an OTHERWISE condition is specified in the final PROVIDED clause, a boolean expression is generated to test the boolean flag for the TRUE condition. In this way, the OTHERWISE transition is executed if and only if none of the previous boolean expressions are satisfied. The DELAY clause is the most complicated clause to translate (Figure variables (delay, to, tl) located in the FDTPCB  3.11). Three auxiliary  are used in order to implement this clause.  Each DELAY clause specified is assigned an unique number. The variable delay is always set to  CHAPTER  3. ESTELLE  TO C  TRANSLATION  i  i n t H a g = 1 /* TRUE */; if  (boolean expression 1)  /* PROVIDED clause 1  { f l a g = 0 /* FALSE */; i  ...  /* Nested t r a n s i t i o n s */  } > if  (boolean expression 2)  /* PROVIDED clause 2  { f l a g = 0 /* FALSE */; { ...  /* Nested t r a n s i t i o n s */  > }  if  ( f l a g == 1 /* TRUE */)  /* OTHERWISE clause *  { ... /* Nested t r a n s i t i o n s */ } }  Figure 3.10: Codes generated for a P R O V I D E D clause  CHAPTER  3.  ESTELLE  TO C TRANSLATION  34  process->tO = time(O); /* Set timer i f not a l r e a d y s e t */ if  (process->delay != <delay  id>)  { p r o c e s s - > t l «* process->tO + <delay time>; process->delay = <delay id>; > /* Tests f o r timer e x p i r a t i o n */ if  (process->tO >= process->tl) { ....  /* Perform a c t i o n */  }  else return; >  Figure 3.11: Codes generated for a D E L A Y clause  CHAPTER  3.  ESTELLE  TO C  TRANSLATION  35  the number assigned to the DELAY clause currently in effect. If none is in effect, the variable is set to the value '0'. The variable tO is used to store the current time while the variable t l is used to store the expiration time for the delay. See Section 4.2.3 for the run-time effect of this clause. The TO clause is translated into a statement in the enclosing transition block which changes the module state variable to the indicated state in the TO clause. If there are several transition block nested under a TO  clause, then the state change statement is replicated in all of the  enclosing transition blocks. The ANY  clause is translated into a simple f o r statement which steps through all values in  the specified scalar domain. If more than one domain is specified, a set of nested f o r statements are used. Within a transition routine, the transitions are layed out in the same sequence that they are defined in the Estelle specification. Therefore, the transition clauses will be evaluated in the order in which that they are specified. The transition that will be executed will be the first transition which enabling clauses are all satisfied. The use of this scheme implies that the order in which the transitions are specified is significant. Consequently, the PRIORITY clause is not implemented in the Estelle-C compiler. The user can always rearrange the transitions in the order of their priority. Although the scheme used is deterministic, the Estelle definition does allow the protocol implementer to make this choice [Este86]. If non-deterministic transition is to be supported, all of the transition clauses must be evaluated to determine the enabled set. From the enabled set of transitions, the ones with the highest priority and which also satisfy the delay criteria are selected. Finally, from this fireable set, a transition must be offered to be executed  non-  CHAPTER  3. ESTELLE  TO C  TRANSLATION  36  deterministically. This three step selection process will only make for an inefficient protocol implementation.  3.5.2  Transition Blocks  The translation of the Pascal style statements in a transition block into equivalent C style statements is generally done by straight substitution. The problems encountered are already noted by Ford and Lau [Ford85,Lau86]. Most of these difficulties have to do with Pascal constructs which have no equivalence in C. Most of the special statements provided in Estelle are translated into subroutine calls to the appropriate run-time support routines which implement the corresponding functions. These routines are described in Sections 3.3.1 and 3.3.2. The OUTPUT statement is translated into a C block containing a local pointer variable newsv a r (Figure 3.12). This local variable is used to allocate a signal parameter block  FDTSVAR  i  FDTSVAR *newsvar = (FDTSVAR *)  malloc(sizeof(FDTSVAR));  newsvar-><ch.annel>. <primitive>. <parameterl> = <valuel>; newsvar-><channel>.<primitive>.<parameter2> = <value2>;  FDTSCBsignal (process, <channel id>, <primitive id>, newsvar); >  Figure 3.12: Codes generated for an O U T P U T statement within the block. Then, the parameters supplied to the OUTPUT statement are copied into the FDTSVAR.  Finally, a signal control block (FDTSCB)  is constructed and appended to the des-  tination queue specified in the OUTPUT statement using the run-time routine FDTSCBsignal().  Chapter 4  Estelle Run-time Execution A n executable program generated from the Estelle specification described in Chapter 3 still only represents a static description of the Estelle specification. It is only when this C program is executed that a dynamic entity will result. This chapter describes the inner working of the generated program during execution.  4.1  Run-time Organization The execution of an Estelle specification is implemented as a two-stage process driven by  the main driver routine supplied in the Estelle run-time support package (Figure 4.1). First,  mainO { FDTPCB *root; r o o t = FDTSPECIFICATION(NULL); FDTSCHexec(root); }  Figure 4.1: Main Driver Routine the driver constructs a run-time structure to represent the initial module hierarchy for the  37  CHAPTER  4. ESTELLE  RUN-TIME  EXECUTION  38  specification by calling the initialization routine, FDTSPECIFICATIONO. Then, the driver calls the run-time scheduler routine, FDTSCHexec (), to take over the execution of the protocol. The following sections explain how two dependent run-time structures are generated from the same set of control blocks and how these structures are used by the run-time scheduler to execute an Estelle specification.  4.1.1  Initialization Routines  The initialization routines generated from the Estelle module body declarations are invoked in a sequence which reflects the nested module organization defined in the Estelle specification. As noted in Section 3.4, the initialization routine of the specification module is always named FDTSPECIFICATIONO. This routine is the only specification dependent routine that is directly invoked by the run-time support system. Consequently, the use of a fixed name for this routine is one of the reasons why the new Estelle run-time support system needs not be recompiled for every different Estelle specification. The function of an initialization routine for a module is to create the two control blocks, FDTPCB  and FDTLVAR,  which when taken together, represent an instance of the module, and  to execute the initialization routines of all its child modules. The result of each invocation of an initialization routine is the simultaneous construction of two tree structures which represent the initialized module and all its child modules in two different ways. In one system, each tree structure constructed by a child module is stored in a module variable located in the FDTLVAR  of the parent (See Figure 3.2).  After the initialization  process, a parent module can refer to any of its child modules by name through the use of these module variables in its FDTLVAR.  This system is used within the implementation routines  generated from the Estelle specification. The second system is generated automatically when  CHAPTER  4.  ESTELLE  RUN-TIME  EXECUTION  the initialization routines invoke FDTPCBinitO to create the FDTPCBs.  39  This system is used by  the run-time scheduler to refer to the modules anonymously and in a specification independent fashion.  4.1.2  Scheduler Routine  The function of the scheduler is to repeatedly select an interaction from the pool of pending interactions and to execute the appropriate module to process the selected interaction. The scheduling algorithm used is, in essence, a pre-order traversal of the module hierarchy tree in a round-robin manner. However, the scheduling algorithm is not straightly round-robin because of the parent/child priority relationship which exists in the module hierarchy. The scheduler routine is shown in Figure 4.2. The scheduler keeps track of a current module for each level in the hierarchy. A t any one time, the current module at one of these level is the current module in the system. The scheduler first checks if there are any pending interactions for the module. If a pending interaction exists, then the current module is selected to be executed. There is also the concept of a next level. If no pending interaction exists, the next level will be one level down. But, if a pending interaction exists and the execution of current module affects some of its ancestor modules, then the level of the ancestor module closest to the specification module will become the next level. Otherwise, the next level is still the current level. In any case, the next module to be selected at the current level will be the next sibling module of the current module. To summarize, the next level stays at the current level or goes up if a pending interaction exists for the current level. Otherwise, the next level becomes one level down. This scheduler algorithm ensured that when a module has the potential to execute transitions, none of its child modules can execute. The algorithm also ensures against module starvation because it  4.  CHAPTER  ESTELLE  RUN-TIME  EXECUTION  FDTSCHexec (root) FDTPCB *root; { C u r r L e v e l = (FDTSCH *) malloc(sizeof(FDTSCH)); CurrLevel->prev = C u r r L e v e l ; CurrLevel->next = NULL; CurrLevel->pcb = root; while (1) { CurrBlock = CurrLevel->pcb; C u r r S i g n a l = FDTSCBpending(CurrBlock); i i ( C u r r S i g n a l != NULL) { if  (CurrBlock->export) NextLevel = CurrLevel->prev; else NextLevel = C u r r L e v e l ; /* T r a n s i t i o n r o u t i n e may change NextLevel */ CurrBlock->trans (CurrBlock, C u r r S i g n a l ) ; }  e l s e i f (CurrBlock->ref != NULL) { i f (CurrLevel->next == NULL) { NextLevel = (FDTSCH *) malloc(sizeof(FDTSCH)) NextLevel->prev = C u r r L e v e l ; NextLevel->next = NULL; NextLevel->pcb = CurrBlock->ref; } else { NextLevel = CurrLevel->next; i f (NextLevel->pcb == NULL) NextLevel->pcb = CurrBlock->ref;  > }  CurrLevel->pcb = CurrBlock->sib; C u r r L e v e l = NextLevel; while (CurrLevel->pcb == NULL) C u r r L e v e l = CurrLevel->prev; > }  Figure 4.2: Run-time Scheduler Routine  CHAPTER  4. ESTELLE  RUN-TIME  EXECUTION  41  is not possible for a module to execute two transitions in a row even if it has several pending interactions enqueued at the same time.  4.2  Transition Processing After the scheduler executes the transition routine of the current module, the next step is  for the transition routine to search for the first transition within the module which satisfies all its enabling conditions. This transition is then executed to process the input interaction. The following sections elaborate on the procedures for processing transitions in various situations.  4.2.1  Input Transitions  When all the enabling condition of an input transition is satisfied, the actions specified in its transition block is executed. After the completion of the transition actions, the module performs an exit sequence which is common to all input transitions (See Figure 3.7). First, because the interaction which caused the transition has already been processed, it is disposed.  Second,  because the actions of the just completed transition may have enabled one of the spontaneous transitions in the module, actions must be taken to ensure that the scheduler will execute the module once more in order to check for this situation. If a pending interaction exists for the module, nothing needs to be done. However, if none exists then a spontaneous interaction is generated for the module by the use of the routine FDTSCBspont 0. Finally, because the just completed transition would have nullified any pending delayed transition, the variable delay in the FDTPCB  is cleared.  CHAPTER  4.2.2 The  4. ESTELLE  RUN-TIME  EXECUTION  42  Spontaneous Transitions exit sequence after the completion of a spontaneous transition is a lot simpler than  that for an input transition. There are two reasons for this difference. Firstly, if the interaction selected for the module is an input interaction, then it will not be processed by the spontaneous transition. Therefore, the interaction selected for the module by the scheduler should not be disposed. Secondly, if the interaction is a spontaneous interaction, then another spontaneous interaction must be needed to check for more enabled spontaneous transitions. Again, there is no need to dispose the interaction. The only action necessary after a spontaneous interaction is to nullify any pending delayed transition (See Figure 3.7).  4.2.3  Delayed Transitions  Delayed transitions are spontaneous transitions with additional timing constraints. However, unlike other transitions, delay transition also has a entry code sequence (See Figure 3.11). If the transition is newly enabled, then the delay parameters are saved by this entry sequence into the FDTPCB  of the module. A desirable side effect of this action is that it will also nullify  another pending delayed transition in the module. In the next step, the delay timer is checked. If the delay constraints are satisfied, the transition is executed. In this case, the exit sequence for it is identical to that for a regular spontaneous transition. Otherwise, control is immediately returned to the scheduler. This bypassing of the exit sequence will cause the selected interaction for the module to remain pending and to cause the scheduler to execute the module at a future time.  CHAPTER  4.2.4  4. ESTELLE  RUN-TIME  EXECUTION  43  No Enabled Transitions  The final situation which must be taken into account is the situation in which the interaction selected by the scheduler does not trigger any transitions. This situation can occur because the scheduler has no knowledge of the transitions within the transition routines. Therefore, the availability of a pending interaction does not guarantee its processing and disposal. This situation is most likely caused by a spontaneous interaction which is used only to check for enabled spontaneous transitions. The actions needed to handle this situation is to dispose the interaction if it is spontaneous, and to leave it pending in the queue if it is not. In order to help prevent deadlock, when the module is again selected for execution, the scheduler will search for pending interactions at other interaction points first.  Chapter 5  Conclusions The present study found substantial syntactic and semantic differences between the Estelle language as implemented by the existing U B C Estelle-C compiler and that specified in the latest ISO document [Este86] and cumulated in the construction of a new Estelle-C compiler. The new compiler supports a large subset of the latest Estelle language specification. The following sections summarize the present work and suggest possible future studies.  5.1  Thesis Summary As stated in Section 2.3, the major motivation for developing the new compiler is to upgrade  an existing U B C Estelle-C compiler to support the latest Estelle language specification. The new compiler fulfills this goal by supporting dynamic reconfiguration of the various entities in a protocol specification. However, there are several Estelle features not included in this new compiler. The P R I O R I T Y clause is not supported due to the reasons given in Section 3.5.1. Additional Estelle features missing are the A L L statement, the F O R O N E statement and the EXIST expression which are used for implicit access to module instances by types rather than by names. A general solution that implements these constructs would require a module directory service to associate module types with module names. The module directory would be further  44  CHAPTER  5.  CONCLUSIONS  45  complicated by the presence of indexed module names. In view of the fact that these constructs can usually be replaced by a mixture of iterative and conditional statements designed for specific situations, their general support would not be cost effective in terms of run-time overhead. Other issues resolved in the new Estelle-C compiler include problems cited by Lau in regards to the old compiler [Lau86]. The old compiler handles module parameter passing very clumsily. In the new compiler, module parameters are automatically accessible in the module initialization routines, the module transition routines and the subroutines nested within the Estelle module. Global variables are also supported as defined by the formal semantics in the new language specification. The Pascal multi-dimensional ARRAY type is now  Estelle  available for user  defined variables as well as MODULE and IP types. However, the data type SET is only partially supported in the form of STATESET. Other Pascal-to-C translation problems that remained are in the areas of SET expressions and nested procedures and functions. These limitations are certainly not unsolvable but their solutions are beyond the scope of protocol implementation. The new compiler is hand-coded in C without using the U N I X utilities lex and yacc. It consists of approximately 300 subroutines totaling to just under 11,000 lines of source code and just under 11K bytes of object code. The size of the new compiler compares favorably with that of the old compiler which contains over 14,000 lines of source code and just over 14K bytes of object code. The new Estelle run-time support routines are also implemented in C. There are 40 routines in the package with approximately 1,500 lines of source code and 7K bytes of object code. In contrast, there are only 17 routines in the old run-time support routines with 1,400 lines of source code and 2K bytes of object code. As part of the redesign of the Estelle-C compiler, the user operation of the compiler has been  CHAPTER  5.  46  CONCLUSIONS  greatly simplified. In the old compiler, the user is required to modify certain sections of the generated C code as well as the run-time support routines. Consequently, the old compiler was labeled with the term "semi-automatic."  The new compiler translates an Estelle specification  directly into a compilable C program. Modification of any of the generated C code is no longer necessary. In addition, the new run-time support routines have been rewritten to contain only specification independent details and they can be directly linked to the compiled C program without the need for recompilation. With these two user-friendly improvements, "automatic" implementation of protocols from formal protocol specifications is now realized.  5.2  Future Work Although an executable program can be generated automatically from a formal protocol  specification using the new  Estelle-C compiler, formal protocol specifications are usually in-  complete. It is the nature of formal specifications to be "completely independent of methods of implementation, so that the technique itself does not provide any undue constraints on implementers" [Este86]. Examples of implementation dependent properties that are almost always left unspecified are functions such as user data management routines, timer management routines and protocol data unit encoding and decoding routines. The user must provide customized versions of these functions manually for the actual implementations in different machine environments. However, it may  be possible to define generic interfaces for these functions to be  usable from within a formal Estelle specification. The user data management example in the Estelle language specification [Este86] presents one possibility. Another direction for research may be in the area of incorporating ASN.l [CCI86] into Estelle for the specification of protocol data unit encoding and decoding functions.  CHAPTER  5.  CONCLUSIONS  47  The usefulness of Estelle compilers has already been demonstrated for semi-automatic generation of communication protocols [Boch86,Lau86,Boch87b] and for automatic generation of test skeletons from protocol specifications [Favr87]. The possible enhancements of these Estelle compilers for the production of emulators for protocol testing and monitors for protocol performance evaluation would be invaluable. Therefore, the further development of novel applications using these compilers in other areas of protocol development should be encouraged.  Bibliography [Ansa87]  Ansart, J.P., Amer, P., Chari, V., Lenotre, J.F., Lumbroso, L., Mariani, E. and Mattera, E., "Software Tools for Estelle," Protocol Specification, Testing, and Verification, VI, (IFIP/WG6.1), B. Sarikaya and G.V. Bochmann, Eds., North Holland, pp. 55-61, 1987.  [Boch86]  Bochmann, G.v., "Semi-Automatic Implementation of Transport and Session Protocols," Computer Standards <fe Interfaces, 5:343-349, 1986.  [Boch87a] Bochmann, G.v., "Usage of Protocol Development Tools: The Results of a Survey," Protocol Specification, Testing, and Verification, VII, (IFIP/WG6.1), H. Rudin and C H . West, Eds., North Holland, 1987. [Boch87b] Bochmann, G.v., Gerber, G.W. and Serre, J.M., "Semiautomatic Implementation of Communication Protocols," IEEE Trans, on Software Engineering, SE-13:989-1000, 1987. [CCI86]  C C I T T , "Data Communication Networks — Message Handling Systems — Recommendations X.400-X.430," Red Book, Vol. VIII, Fascicle VIII.7, Ganeva, 1986.  [Cour86]  Courtiat, J.P., Pedroza, A. and Ayache, J.M., "A Simulation Environment for Protocol Specifications Described in Estelle," Protocol Specification, Testing, and Verification, V, (IFIP/WG6.1), M. Diaz, Ed., North Holland, pp. 297-312, 1986.  [Este84]  ISO/TC97/SC21/WGl/Subgroup B, "A Formal Description Technique Based on an Extended State Transition Model," Working Document, 1984.  [Este85]  ISO/TC97/SC21/WGl/Subgroup B, "Estelle — A Formal Description Technique Based on an Extended State Transition Model," D P 9074, 1985.  [Este86]  ISO/TC97/SC21/WGl/Subgroup B, "Estelle — A Formal Description Technique Based on an Extended State Transition Model," 2nd D P 9074, 1986.  [Favr87]  Favreau, J.P. and Linn, R. J., "Automatic Generation of Test Skeletons from Protocol Specification Written in Estelle," Protocol Specification, Testing and Verification, VI (IFIP/WG 6.1), B. Sarikaya and Bochmann, G.v., Eds., North Holland (1987).  48  [Ford85]  Ford, D.A., "Semi-Automatic Implementation of Network Protocols," Master Thesis, University of British Columbia, 1985.  [Garg87]  Garguilo, J., Fauneau, J.P., Hobbs, M. and Linn, R.J. "Automated Protocol Development Through Use of the NBS Prototype Estelle Compiler," ICST/APM-87-2, National Bureau of Standards, Guithersburg, 1987.  [Gerb83]  Gerber, G.W., "Une Methode D'Implantation Automatique de Systemes Specifies Formellement," Master Thesis, University of Montreal, 1983.  [IS082a] ISO/TC97/SC16, "Transport Protocol Specification," D P 8073, 1982. [IS082b] ISO/TC97/SC16, "Transport Service Definition," D P 8072, 1982. [Lau86]  Lau, A.C. "A Semi-Automatic Approach to Protocol Implementation — The ISO Class 2 Transport Protocol as an Example," Master Thesis, University of British Columbia, 1986.  [Linn86]  Linn, R.J., Jr., "The Features and Facilities of Estelle," Protocol Specification, Testing, and Verification, V, (IFIP/WG6.1), M. Diaz, Ed., North Holland, pp. 271-296, 1986.  [Vuon87]  Vuong, S.T. and Lau, A.C, "A Semi-Automatic Approach to Protocol Implementation — The ISO Class 2 Transport Protocol as an Example," I N F O C O M '87, San Francisco, 1987.  [Vuon88]  Vuong, S.T., Lau, A.C. and Chan, R.I., "Semi-Automatic Implementation of Protocols using an Estelle-C Compiler," IEEE Trans, on Software Engineering,, to be published, 1988.  49  Appendix A  Alternating Bit Protocol — Estelle Specification  50  APPENDIX  A. ALTERNATING  BIT PROTOCOL  SPECIFICATION abp_spec SYSTEMPROCESS; CONST LOV/.CEP HIGH_CEP TYPE cep_type seq_type pid_type udata_type ndata.type  1; 2;  — ESTELLE  SPECIFICATION  TIMESCALE seconds;  { Minimum cep subscript } { Maximum cep subscript }  LOVLCEP..HIGH_CEP; 0. .1;  (DATA. ACKM); INTEGER; RECORD pid : pid_type; cid : cep_type; seq : seq_type; dat : udata_type END;  Connection end point } Sequence number } } •C Packet type i  •c Type of message } Cep of sender } Sequence number } > i User data  { Channel between user and alternating bit protocol provider } CHANNEL U_access_point (user, provider); BY user : SEND.REQ. (udata : udata_type); RECV.REQ; BY provider : RECV.RSP (udata : udata_type); { Channel between alternating bit protocol provider and the network } CHANNEL N_access_point (user, provider); BY user : DATA_REQ (ndata : ndata.type); BY provider : DATA.RSP (ndata : ndata.type); MODULE user.type PROCESS (cep.id : cep.type); IP U : U_access_point(user) INDIVIDUAL QUEUE; END; { MODULE user.type > BODY user.body FOR user.type; VAR data : udata.type; flag : BOOLEAN;  APPENDIX  A. ALTERNATING  BIT  PROTOCOL —  ESTELLE  SPECIFICATION  INITIALIZE BEGIN data := 0 ;  flag := TRUE END; { INITIALIZE } TRANS WHEN U.RECV_RSP { Received data from peer and proceeds to send next data to peer } NAME userl : BEGIN data := data + 1; OUTPUT U.SEND_REQ (data); OUTPUT U.RECV_REq END; { userl > TRANS PROVIDED flag { Spontaneous transition to send i n i t i a l data } NAME uaer2 : BEGIN flag := FALSE; OUTPUT U.SENDJREQ (data); OUTPUT U.RECV_REq END;  END;  { user2 >  { BODY user_body }  MODULE network_type PROCESS; IP N : ARRAY [cep_type] OF N_access_point (provider) COMMON QUEUE; END; i MODULE network_type > BODY network_body FOR network_type; VAR count : INTEGER; TRANS ANY i : cep_type DO  APPENDIX  A. ALTERNATING  BIT  PROTOCOL — ESTELLE  WHEN N[i].DATA_REQ NAME networkl : BEGIN count := count + 1; IF count <> 4 THEN OUTPUT N[HIGH_CEP-i+l].DATA_RSP (ndata) END; { network! > END;  { BODY network_body >  MODULE abit_type PROCESS (cep_id : cep.type); IP U : U_access_point (provider) INDIVIDUAL QUEUE; N : N_access_point (user) INDIVIDUAL QUEUE; END; i MODULE abit.type } BODY abit_body FOR abit.type; CONST RETRAN_TIME =30; { Retransmission time } CHANNEL S_access_point (user, provider); BY user : TTMER.REQ; BY provider : TIMER_RSP; MODULE timer.type ACTIVITY (time : INTEGER); IP S : S_access_point (provider) INDIVIDUAL QUEUE; END; { MODULE timer_type > BODY timer_body FOR timer_type; VAR stop, stop.bis : BOOLEAN; INITIALIZE BEGIN stop := TRUE; stop_bis := TRUE END; i INITIALIZE } TRANS WHEN S.TIMER.REQ  SPECIFICATION  APPENDIX  A. ALTERNATING  BIT  PROTOCOL — ESTELLE  NAME timerl : BEGIN stop := TRUE; stop_bis := FALSE END; i timerl } TRANS PROVIDED NOT stop.bia NAME timer2 : BEGIN stop := FALSE; stop_bis := TRUE END; { timer2 > PROVIDED NOT stop DELAY (time, time) NAME timer3 : BEGIN stop := TRUE; OUTPUT S.TIMER.RSP END; { timer3 > END;  { BODY timer.body >  MODULE datax_type ACTIVITY (cep_id : cep_type); IP U : U_access_point (provider) INDIVIDUAL QUEUE; N : N.access.point (user) INDIVIDUAL QUEUE; S : S.access.point (user) INDIVIDUAL QUEUE; END; { MODULE datax.type > BODY datax_body FOR datax_type; TYPE mag_type = RECORD msgcid : cep.type; msgseq : seq.type; msgdat : udata.type END; buf.type RECORD empty : BOOLEAN; message : msg.type END; VAR send_seq : seq.type; recv.seq : seq.type;  { Send sequence number } •i Receive sequence number }  SPECIFICATION  APPENDIX  A. ALTERNATING  send_buf recv_buf send_msg recv.msg buf  : buf_type; : buf_type; : msg_type; : msg_type; : ndata_type;  BIT PROTOCOL  — ESTELLE  < ACKM pending flag { DATA pending flag { Message being sent { Message receive {. Network buffer  STATE ACK_MIT, ESTAB; STATESET EITHER = [ACK_WAIT, ESTAB]; PURE FUNCTION ack_ok (buf : ndata.type) : BOOLEAN; { Checks ACKM message i n the network buffer } BEGIN { ack_ok > ack_ok := (buf.pid = ACKM) AND (buf.seq = send_seq) END; { ack_ok > PROCEDURE format_data (msg : msg_type; VAR buf : ndata_type); { Formats a DATA message into the network buffer > BEGIN { format_data > buf.pid := DATA; buf.cid := cep_id; buf.seq := msg.msgseq; buf.dat := msg.msgdat END; { format_data > PROCEDURE format_ack (msg : msg_type; VAR buf : ndata_type); { Places an ACKM message into the network buffer } BEGIN { format.ack > buf.pid := ACKM; buf.cid := msg.msgcid; buf.seq := msg.msgseq; buf.dat := msg.msgdat END; { format_ack > PROCEDURE store (VAR buf : buf_type; msg : msg_type); { Stores message into the buffer } BEGIN  { store >  SPECIFICATION  APPENDIX  A. ALTERNATING  BIT  PROTOCOL — ESTELLE  buf.empty := FALSE; buf.message := msg; END; < store } PROCEDURE remove (VAR buf : buf_type; msg : msg_type); { Empties the buffer } BEGIN { remove > buf.empty := TRUE END; FUNCTION retrieve (buf : buf.type) : msg_type; { Retrieves the message from the buffer } BEGIN { retrieve > retrieve := buf.message END; { retrieve > FUNCTION buffer_empty (buf : buf.type) : BOOLEAN; { Checks for empty buffer > BEGIN { buffer_empty } buffer_empty := buf.empty END; { buffer_empty > PROCEDURE inc_send_seq; {. Increments the send sequence number } BEGIN < inc_send_seq > send_aeq := (send_seq + 1) MOD 2 END; •{ inc_send_seq > PROCEDURE inc_recv_seq; { Increments the receive sequence number } BEGIN { inc_recv_seq } recv_seq := (recv_seq + 1) MOD 2 END; { inc_recv_seq > INITIALIZE  { data.body >  SPECIFICATION  APPENDIX  A. ALTERNATING  BIT PROTOCOL  — ESTELLE  SPECIFICATION  TO ESTAB BEGIN send_seq := 0; recv.seq := 0; send.buf.empty := TRUE; recv_buf.empty := TRUE END; { INITIALIZE } TRANS FROM ESTAB TO ACK.WAIT WHEN U.SEND..REQ { Processes user send REQ } NAME dataxl : BEGIN send_msg.msgdat := udata; send_msg.msgseq := send.seq; store (send..buf, send_msg) ; format_data (send_msg, buf); OUTPUT N.DATA.REQ (buf); OUTPUT S.TIMER.REQ END; { dataxl > FROM EITHER TO SAME WHEN U.RECV.REQ PROVIDED NOT buffer_empty (recv_buf) { Retrieves received message for user i f one has been received } NAME datax2 : BEGIN recv_msg := retrieve (recv_buf); OUTPUT U.RECV.RSP (recv.msg.msgdat); remove (recv_buf, recv_msg) END; { datax2 } FROM ACK.V/AIT TO ACK.V/AIT WHEN S.TIMER.RSP { Resend user message after time out } NAME datax3 : BEGIN send_msg := retrieve (send_buf); format_data (send_msg, buf); OUTPUT N.DATA.REQ (buf); OUTPUT S.TIMER_REQ  APPENDIX  A. ALTERNATING  END;  BIT  PROTOCOL — ESTELLE  SPECIFICATION  { dataxS }  FROM ESTAB TO ESTAB WHEN S.TIMER.RSP { The message that caused this timer to be set has been acknowledged } NAME datax4 : BEGIN END; { datax4 > FROM ACK_WAIT TO ESTAB WHEN N.DATA_RSP PROVIDED ack_ok(ndata) { Acknowlegement f o r the l a s t message sent has been received } NAME dataxS : BEGIN send_msg := retrieve (send_buf); remove (send_buf, send.msg); inc_send_seq END; { dataxS > FROM EITHER TO SAME WHEN N.DATA_RSP PROVIDED ndata.pid = DATA { Processes message received from peer } NAME datax6 : BEGIN recv_msg.msgdat := ndata.dat; recv_msg.msgseq := ndata.seq; format_ack (recv_msg, buf); OUTPUT N.DATA_REQ (buf); IF ndata.seq = recv_seq THEN BEGIN Btore (recv_buf, recv_msg); inc_recv_seq END { IF > END; i datax6 > END;  i BODY datax_body >  MODVAR datax.module timer_module INITIALIZE BEGIN  : datax_type; : timer_type;  { abit.body >  APPENDIX  A. ALTERNATING  BIT  PROTOCOL — ESTELLE  INIT datax.module WITH datax_body (cep_id); INIT timer_module WITH timer.body (RETRAN_TIME); CONNECT datax_module.S TO timer_module.S; ATTACH U TO datax.module.U; ATTACH N TO datax_module.N; END; i INITIALIZE > END; { abit_body } MODVAR network_module : network_type; user_module : ARRAY [cep_type] OF user_type; abit_module : ARRAY [cep_type] OF abit_type; INITIALIZE  { abp.spec >  BEGIN INIT network_module WITH network_body; ALL cep : cep.type DO BEGIN INIT user.module[cep] WITH user_body(cep); INIT abit_module[cep] WITH abit_body(cep); CONNECT user_module[cep].U TO abit.module[cep].U; CONNECT abit_module[cep].N TO network_module.N[cep]; END; i ALL > END; i INITIALIZE > END. { abp_spec >  SPECIFICATION  Appendix B  Alternating Bit Protocol Generated Codes  60  APPENDIX  #include #include #include #include #include #include  B.  ALTERNATING  BIT  PROTOCOL — GENERATED  <8tdio.h> "fdtset.h" "fdtscb.h" "fdtccb.h" "fdtpcb.h" "fdtsch.h"  /* Type declarations */ typedef typedef typedef typedef typedef  i n t cep_type ; i n t seq_type ; i n t pid_type ; i n t udata_type ; struct { i n t dat ; i n t seq ; int c i d ; int pid ; > ndata.type ; typedef struct { i n t msgdat ; i n t msgseq ; i n t msgcid ; } msg_type ; typedef struct {. msg_type message ; i n t empty ; > buf_type ;  /* Signal parameter block declarations */ typedef union { union { struct { i n t udata ; > SEND.request ; i n t RECV.request ; struct { i n t udata ; } RECV.response ; y U_acce8s_point ; union { struct { ndata.type ndata ; > DATA_request ; struct {  CODES  APPENDIX  B.  ALTERNATING  BIT  PROTOCOL  ndata_type ndata ; }• DATA_response ; y N_access_point ; union i. int TIMER_requei3t ;  int TIMER_response ; y S_access_point ; > FDTSVAR;  /* Variable block declarations */ typedef union { struct { int cep_id ; int flag ; int data ; } user_body ; struct { int dummy ; >  struct { int time ; int FDT3 ; int stop ; int stop_bis ; > timer_body; struct { int cep_id ; set_type EITHER ; int STATE ; ndata_type buf ; msg_type recv_msg ; msg_type send_msg ; buf_type recv_buf ; buf_type send_buf ; int recv_seq ; int send_seq ; } datax_body; struct i. int cep_id ; struct FDTPCB *timer_module ; struct FDTPCB *datax_module ; y abit_body; struct { struct FDTPCB *abit_module [ 2 ] ; struct FDTPCB *user_module [ 2 ];  — GENERATED  CODES  APPENDIX  B.  ALTERNATING  BIT PROTOCOL  — GENERATED  struct FDTPCB *network_module ; } SPECIFICATION ; } FDTLVAR;  /* Miscellaneous declarations */ #define XPORTuser_body #define SPONTuser_body extern i n t user_body(); #define TRANSuser_body #define XPORTnetwork_body #define SPONTnetwork_body extern i n t network_body(); #define TRANSnetwork_body #define XPORTtimer_body #define SPONTtimer_body extern i n t timer_body(); #define TRANStimer_body #define XPORTdatax_body #define SPONTdatax_body extern i n t datax_body(); #define TRANSdatax_body #define XPORTabit.body #define SPONTabit.body #define TRANSabit_body #define XPORTSPECIFICATION #define SPONTSPECIFICATION #define TRANSSPECIFICATION  0 0 user.body 0 0 network_body 0 1 timer_body 0 0 datax_body 0 0 NULL 0 0 NULL  /* Procedure and function declarations */ int ack_ok ( buf ) ndata.type buf ; { FDTLVAR *lvar = CurrBlock->lvar; i n t FUNCTION; FUNCTION = ( buf .pid == 1 /* ACKM */) hk ( buf .seq == lvar->datax_body.send_seq return ( FUNCTION ) ; }  format_data ( msg , buf ) msg_type msg ;  ) ;  CODES  APPENDIX  B. ALTERNATING  BIT PROTOCOL  ndata.type *buf ; FDTLVAR *lvar = CurrBlock->lvar; (*buf (*buf (*buf (*buf  ) ) ) )  .pid = 0 /* DATA */; .cid = lvar->datax_body.cep_id ; .seq = msg .msgseq ; .dat = msg .msgdat ;  format_ack ( msg , buf ) msg_type msg ; ndata.type *buf ; i  FDTLVAR *lvar = CurrBlock->lvar; (*buf (*buf (*buf (*buf  ) ) ) )  .pid = 1 /* ACKM */; .cid = msg .msgcid ; .seq = msg .msgseq ; .dat = msg .msgdat ;  store ( buf , msg ) buf_type *buf ; msg_type msg ;  •C FDTLVAR *lvar = CurrBlock->lvar; (*buf ) .empty = 0 /* FALSE */; (*buf ) .message = msg ; >  remove ( buf , msg ) buf_type *buf ; msg_type msg ; { FDTLVAR *lvar = CurrBlock->lvar; (*buf ) .empty = 1  /* TRUE */;  > msg_type retrieve buf_type buf ;  ( buf )  —  GENERATED  CODES  APPENDIX B. ALTERNATING  BIT PROTOCOL  — GENERATED  CODES  65  FDTLVAR *lvar = CurrBlock->lvar; msg_type FUNCTION; FUNCTION = buf .message ; return ( FUNCTION ) ; }  int buffer_empty buf_type buf ;  ( buf )  {  FDTLVAR *lvar = CurrBlock->lvar; int FUNCTION;  >  FUNCTION = buf .empty ; return ( FUNCTION ) ;  inc_send_8eq ()  •C FDTLVAR *lvar = (FDTLVAR *) CurrBlock->lvar;  >  lvar->datax_body.send_seq  = ( lvar->datax_body.send_seq  + i ) % 2;  inc_recv_seq ()  •C FDTLVAR *lvar = (FDTLVAR *) CurrBlock->lvar; lvar->datax_body.recv_seq  = ( lvar->datax_body.recv_Beq  + 1 ) % 2 ;  >  /* Specification declarations */ FDTPCB *FDTuser_body ( parent , cep_id ) FDTPCB *parent; int cep_id ; < FDTPCB *pcb; FDTLVAR *lvar; pcb = FDTPCBinit ( parent , 1 , SPONTuser_body , XPORTuser_body , TRANSuser_body ); pcb->lvar = (int *) (lvar = (FDTLVAR *) malloc(sizeof(FDTLVAR)));  APPENDIX  B.  ALTERNATING  BIT  PROTOCOL  — GENERATED  CODES  lvar->user_body.cep_id = cep_id ; < lvar->user_body.data = 0 ; lvar->user_body.flag = 1 /* TRUE */; goto trans_end ; > trana_end : i f (pcb->spont) FDTSCBspont (pcb); return (pcb);  user.body ( process, signal ) FDTPCB ^process; FDTSCB *signal;  •C FDTLVAR *lvar = (FDTLVAR *) process->lvar; FDTSVAR *svar = (FDTSVAR *) signal->svar; {  i f ( ( signal->cid == 1 ) 44 ( signal->sid == 3 ) ) { /* userl */ lvar->user_body.data = lvar->user_body.data + 1 ;  •c FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR)); newsvar->U_access_point.SEND_REQ.udata = lvar->user_body.data FDTSCBsignal ( process, 1 , 1 , newsvar); }  < FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR)); FDTSCBsignal ( p r o c e s s , 1 , 2 , > goto trans.end ;  newsvar);  > >  •C int FDT1 if  = 1 ;  (lvar->user_body.flag )  •C FDT1 = 0; i /* user2 */ lvar->user_body.flag = 0  /* FALSE */;  ;  APPENDIX  B.  ALTERNATING  BIT PROTOCOL  — GENERATED  CODES  i  FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR)); newsvar->U_access_point.SEND_REQ.udata = lvar->uaer_body.data FDTSCBsignal ( p r o c e s s , 1 , 1 , newsvar); }  i  FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR));  }  >  >  FDTSCBsignal ( p r o c e s s , 1 , 2 , > goto spont.end ;  newsvar);  i f (signal->cid == 0) FDTSCBdispose (process, signal); return; trans_end : FDTSCBdispose (process, signal); i f (process->spont) FDTSCBspont (process); spont_end : process->delay = 0;  FDTPCB *FDTnetwork_body ( parent ) FDTPCB *parent; {  FDTPCB *pcb; FDTLVAR *lvar; ( parent , 2 , SPONTnetwork_body , XPORTnetwork_body , TRANSnetwork_body ) ; pcb->lvar = (int *) (lvar = (FDTLVAR *) malloc(sizeof(FDTLVAR))); pcb = FDTPCBinit  trans_end : i f (pcb->8pont) FDTSCBspont (pcb); return (pcb);  network_body ( process, signal ) FDTPCB ^process;  ;  APPENDIX  B. ALTERNATING  BIT  PROTOCOL — GENERATED  CODES  68  FDTSCB *signal; i  FDTLVAR *lvar = (FDTLVAR *) process->lvar; FDTSVAR *avar = (FDTSVAR *) signal->svar;  int i ; for ( i = 1  ; i <= 2  ; i++ )  •C i f ( ( signal-->cid = = l + i - l ) & & ( signal->sid == 1 ) ) { /* networkl */  •C  FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR));  >  >  >  newsvar->N_access_point.DATA_RSP.ndata = svar->N_access_point.DATA_REQ.ndata ; FDTSCBsignal ( process, 1 + 2 /* HIGH_CEP */- i + 1 - 1 , 2 , newsvar); > goto trans.end ;  i f (signal->cid === 0) FDTSCBdispose (process, signal); return; trans_end : FDTSCBdispose (process, signal); i f (process->spont) FDTSCBspont (process); spont.end : process->delay = 0;  FDTPCB *FDTtimer_body ( parent , time ) FDTPCB *parent; int time ;  •C FDTPCB *pcb; FDTLVAR *lvar; pcb = FDTPCBinit  ( parent , 1 , SPONTtimer_body , XPORTtimer.body , TRANStimer_body ); pcb->lvar = (int *) (lvar = (FDTLVAR *) malloc(Bizeof(FDTLVAR))); lvar->timer_body.time  = time ;  APPENDIX  >  B. ALTERNATING  BIT PROTOCOL  — GENERATED  lvar->timer_body.atop = 1 /* TRUE */; lvar->timer_body.Btop_bis = 1 /* TRUE */; goto trans_end ;  trans_end : i f (pcb->spont) FDTSCBspont (pcb); return (pcb);  timer_body ( process, signal ) FDTPCB *process; FDTSCB *signal;  •C  FDTLVAR *lvar = (FDTLVAR *) process->lvar; FDTSVAR *svar = (FDTSVAR *) signal->svar;  •C i f ( ( signal->cld == 1 ) && ( signal->sid == 1 ) ) < /* timerl */ lvar->timer_body.stop =1 /* TRUE */; lvar->timer_body.stop_bis = 0 /* FALSE */; goto trans_end ; }  >  •C  i n t FDT2  = 1;  i f (!lvar->timer_body.stop_bis  •C  )  FDT2 = 0; •C /* timer2 */ lvar->timer_body.stop = 0 /* FALSE */; lvar->timer_body.stop_bis = 1 /* TRUE */; goto spont_end ; }  if  >  (!lvar->timer_body.stop  )  •c FDT2  •C  = 0;  process->t0 = time(0); i f ( process->delay  •C  != 3 )  CODES  APPENDIX  B.  ALTERNATING  BIT  PROTOCOL  — GENERATED  CODES  procesB->tl = process->tO + ( lvar->timer_body.time ); process->delay = 3 ; > i f (process->t0 >= process->tl ) < /* timer3 */ lvar->timer_body.stop = 1 /* TRUE */; {  FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR)); FDTSCBsignal  ( process,1,2,  newsvar);  }  goto spont_end ; > else return; > > > i f (signal->cid === 0) FDTSCBdispose (process, signal); return; trans_end : FDTSCBdispose (process, signal); i f (process->spont) FDTSCBspont (process); spont.end : process->delay = 0;  FDTPCB *FDTdatax_body ( parent , cep_id ) FDTPCB *parent; i n t cep_id ;  •C FDTPCB *pcb; FDTLVAR *lvar; pcb = FDTPCBinit ( parent , 3 , SPONTdatax_body , XPORTdatax_body , TRANSdatax.body ); pcb->lvar = ( i n t *) (lvar = (FDTLVAR *) malloc(sizeof(FDTLVAR))); lvar->datax_body.cep_id = cep_id ; assign_set ( &(lvar->datax_body.EITHER) , 2 , 1 {  /* ESTAB */, 0  /* ACK_¥AIT * / ) ;  70  APPENDIX  B.  ALTERNATING  BIT  PROTOCOL  — GENERATED  CODES  lvar->datax_body.send_seq = 0 ; lvar->datax_body.recv_seq = 0 ; lvar->datax_body.Bend_buf .empty = i /* TRUE */; lvar->datax_body.recv_buf .empty = 1 /* TRUE */; lvar->datax_body.STATE = 1 /* ESTAB */ ; goto trans_end ; > trans_end : i f (pcb->spont) FDTSCBspont (pcb); return (pcb);  datax_body ( process, B i g n a l ) FDTPCB *process; FDTSCB *signal; { FDTLVAR *lvar = (FDTLVAR *) process->lvar; FDTSVAR *svar = (FDTSVAR *) signal->svar; < if  ( ( 1var->datax_body.STATE =  1  /* ESTAB */) )  i  i f ( ( signal->cid == 1 ) kb ( signal->sid == 1 ) ) •C /* dataxl */ lvar->datax_body.send_msg .msgdat - svar->U_access_point.SEND_REQ.udata lvar->datax_body.send_msg .msgseq = lvar->datax_body.send_seq ; store ( &( lvar->datax_body.send_buf ) , lvar->datax_body.send_msg ); format_data ( lvar->datax_body.send_msg , A( lvar->datax_body.buf ) );  ;  •C  FDTSVAR *newBvar = (FDTSVAR *) malloc(sizeof(FDTSVAR)); newsvar->N_access_point.DATA_REQ.ndata = lvar->datax_body.buf ; FDTSCBsignal ( p r o c e s s , 2 , 1 , newsvar); >  •C  FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR));  > if  •C  >  FDTSCBsignal ( p r o c e B B , 3 , 1 , newsvar); > lvar->datax_body.STATE = 0 /* ACK_WAIT */ ; goto trans_end ;  ( ( is_set_member  ( k(1var->datax_body.EITHER)  , lvar->datax_body.STATE  ) ) )  APPENDIX  B. ALTERNATING  BIT PROTOCOL  — GENERATED  CODES  i f ( ( signal->cid == 1 ) kk ( signal->sid == 2 ) ) i  int FDT4  = 1;  i f (!buffer_empty ( lvar->datax_body.recv_buf ) )  •C FDT4 = 0; i /* datax2 */ lvar->datax_body.recv_msg = retrieve ( lvar->datax_body.recv_buf ) { FDTSVAR *newBvar = (FDTSVAR *) malloc(Bizeof(FDTSVAR));  >  >  newsvar->U_access_point.RECV_RSP.udata = lvar->datax_body.recv_msg .msgdat ; FDTSCBsignal ( p r o c e s s , 1 , 3 , newsvar); > remove ( &( lvar->datax_body.recv_buf ) , lvar->datax_body.recv_msg goto trans_end ;  > }  i f ( ( lvar->datax_body.STATE =  0  /* ACK.WAIT */) )  •C i f ( ( signal->cid == 3 ) kk ( signal->sid == 2 ) ) i /* datax3 */ lvar->datax_body.send_msg = retrieve ( lvar->datax_body.send_buf ) ; format.data ( lvar->datax_body.send_msg , &( lvar->datax_body.buf ) );  •C FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR));  >  newsvar->N_access_point.DATA_REQ.ndata = lvar->datax_body.buf ; FDTSCBsignal ( process, 2 , 1 , newsvar);  •C FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR));  >  FDTSCBsignal ( p r o c e s s , 3 , 1 , newsvar); > lvar->datax..body.STATE = 0 /* ACK_WAIT */ ; goto trans.end ;  > i f ( ( 1var->datax_body.STATE == 1 /* ESTAB */) ) { i f ( ( signal->cid == 3 ) kk ( signal->sid == 2 ) ) < /* datax4 */  APPENDIX  B.  ALTERNATING  BIT  lvar->datax_body.STATE = 1 goto trans_end ;  PROTOCOL  — GENERATED  CODES  73  /* ESTAB */ ;  > }  i f ( ( lvar->datax_body. STATE =  0  /* ACK.VIAIT */) )  i  i f ( ( signal->cid == 2 ) kk ( signal->sid == 2 ) ) int FDT5  = 1 ;  i f (ack_ok ( svar->N_acceBB_point.DATA_RSP.ndata ) ) i  FDT5 = 0; { /* dataxS */ lvar->datax_body.send_m8g = retrieve ( lvar->datax_body.send_buf ) ; remove ( &( lvar->datax_body.send_buf ) , lvar->datax_body.send_mag ); inc_send_Beq ( ); lvar->datax_body.STATE = 1 /* ESTAB */ ; goto trans.end ; }  > > }  i f ( ( is_set_member  ( 4(lvar->datax_body.EITHER)  , lvar->datax_body.STATE ) ) )  i  i f ( ( aignal->cid == 2 ) hk ( signal->sid == 2 ) )  •C  i n t FDT6  = 1 ;  i f (svar->N_access_point.DATA_RSP.ndata .pid == 0 /* DATA */) < FDT6 = 0; { /* datax6 */ lvar->datax_body.recv_msg .msgdat = Bvar->N_access_point.DATA.RSP.ndata .dat ; lvar->datax_body.recv_msg .msgseq = 8var->N_access_point.DATA_RSP.ndata .seq ; format_ack ( lvar->datax_body.recv_msg , &( lvar->datax_body.buf ) );  •C  FDTSVAR *newsvar = (FDTSVAR *) malloc(sizeof(FDTSVAR)); newsvar->N_accesa_point.DATA_REQ.ndata = lvar->datax_body.buf ; FDTSCBsignal ( p r o c e s s , 2 , 1 , newsvar); > i f ( svar->N_access_point.DATA_RSP.ndata .seq == lvar->datax_body.recv_seq )  APPENDIX  B. ALTERNATING  BIT PROTOCOL  — GENERATED  CODES  store ( &( lvar->datax_body.recv_buf ) , lvar->datax_body.recv_msg inc_recv_seq ( );  )  > goto trana_end ; } }  > > > i f (signal->cid == 0) FDTSCBdispose (process, signal); return; trans_end : FDTSCBdispose (process, signal); i f (process->spont) FDTSCBspont (process); spont_end : process->delay = 0;  FDTPCB *FDTabit_body ( parent , cep_id ) FDTPCB *parent; int cep_id ;  •C FDTPCB *pcb; FDTLVAR *lvar; pcb = FDTPCBinit ( parent , 2 , SP0NTabit_body , XPORTabit.body , TRANSabit.body ); pcb->lvar = ( i n t *) (lvar = (FDTLVAR *) malloc(sizeof(FDTLVAR))); lvar->abit_body.cep_id = cep_id ; lvar->abit_body.datax_module = FDTdatax_body( pcb , lvar->abit_body.cep_id ); lvar->abit_body.timer_module = FDTtimer_body( pcb , 30 /* RETRAN_TIME * / ) ; FDTCCBconnect (lvar->abit_body.datax_module , 3 , 1 , lvar->abit_body.timer_module , 1 , 1 ) ; FDTCCBattach (pcb, 1 , 1 , lvar->abit_body.datax_module , 1 , 1 ) ; FDTCCBattach (pcb, 2 , 1 , Ivar->abit_body.datax_module ,2,1); goto trans_end ; }  trans_end : i f (pcb->spont)  APPENDIX  B. ALTERNATING  BIT PROTOCOL  — GENERATED  CODES  FDTSCBspont (pcb); return (pcb); >  FDTPCB *FDTSPECIFICATION ( parent ) FDTPCB *parent;  •C FDTPCB *pcb; FDTLVAR *lvar; pcb = FDTPCBinit ( parent , 0 , SPONTSPECIFICATION , XPORTSPECIFICATION , TRANSSPECIFICATION ); pcb->lvar = ( i n t *) (lvar = (FDTLVAR *) malloc(sizeof(FDTLVAR)));  •C lvar->SPECIFICATION.network_module  = FDTnetwork_body( pcb );  i  int cep ; for ( cep = 1  ; cep <= 2  ; cep++ )  i  lvar->SPECIFICATION.user_module [ cep - 1 ] = FDTuser_body( pcb , cep ); lvar->SPECIFICATION.abit_module [ cep - 1 ] = FDTabit_body( pcb , cep ); FDTCCBconnect (lvar->SPECIFICATION.user_module [ cep - 1 ] , 1 , 1 , lvar->SPECIFICATION.abit_module [ cep - 1 ] , 1 , 1 ); FDTCCBconnect (lvar->SPECIFICATION.abit_module [ cep - 1 ] , 2 , 1 , lvar->SPECIFICATION.network_module , 1 + cep - 1 , 0 ); > > goto trans.end ; }  trans_end : i f (pcb->spont) FDTSCBspont (pcb); return (pcb);  75  Appendix C  Process Control Block Support Routines  76  APPENDIX  C.  PROCESS  CONTROL  BLOCK  SUPPORT  ROUTINES  /* * * * * */  Creates and i n i t i a l i z e s a new process control block (PCB) Places the PCB at the head of the s i b l i n g l i s t I f process contains transitions, inserts PCB into the scheduler's l i s t s Returns the new PCB  FDTPCB *FDTPCBinit (parent, ipnum, spont, export, transition) FDTPCB *parent; int ipnum; int spont; int export; int (^transition)(); {  FDTPCB  *newpcb = (FDTPCB *) malloc(sizeof(FDTPCB));  /***+* Links new process control block to the module hierarchy *****/ newpcb->pid = Pid++; newpcb->parent = parent; i f (parent != NULL) < newpcb->sib = parent->ref; parent->ref = newpcb; newpcb->prio = parent->prio + 1; > else /* This i s the root module */ { newpcb->sib = newpcb; newpcb->prio = 1; > newpcb->ref = NULL; /***** Allocates enough interaction points f o r the module *****/ newpcb->ipnum = ipnum; i f (ipnum > 0) newpcb->chan = FDTCCBinit else newpcb->chan  (newpcb->ipnum);  = NULL;  /***** I n i t i a l i z e s other module state variables *****/ newpcb->ipnext newpcb->sigcnt newpcb->delay newpcb->spont  = 0; = 0; = 0; = spont;  !  APPENDIX  C. PROCESS  CONTROL  BLOCK  SUPPORT  ROUTINES  newpcb->export = export; newpcb->trans = transition; return (newpcb); >  /* * Releases the specified process control block and a l l i t s descendents */ FDTPCBterm (pcb) FDTPCB *pcb; { FDTPCB *p; i f (pcb == NULL) return; i f ((p = pcb->parent) == NULL) FDTLIBerror ("Root module attempting to k i l l  itself\n");  i f (p->ref == pcb) p->ref = pcb->sib; > else { p = p->ref; while ((p != NULL) && (p->sib != pcb)) p = p->sib; i f (p == NULL) FDTLIBerror ("Error i n l i n k to parent\n"); p->sib = pcb->sib; }  /***** Terminates a l l children recursively and then deallocates i t s e l f *****/ while (pcb->ref != NULL) FDTPCBterm (pcb->ref);  >  i f (pcb->chan != NULL) FDTCCBterm (pcb); free (pcb);  78  Appendix D  Channel Control Block Support Routines  79  APPENDIX  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  /*  *  Creates and i n i t i a l i z e s a new channel control block  */ FDTCCB *FDTCCBinit int size;  •C FDTCCB for  *i,  (size)  *ccb = (FDTCCB *) c a l l o c ( s i z e + 1 , sizeof(FDTCCB));  (i=ccb; i<ccb+size+l; i++)  •C i->head i->targeta i->channela i->qdispl  = = = =  i->tail = NULL; i->targetc = i->targete = NULL; i->channelc = i->channele = 0; COMMON;  > return (ccb); }  /* *  Removes a channel l i s t from a process control block  */ FDTCCB *FDTCCBterm (process) FDTPCB ^process; { FDTCCB *ccbl, *ccb2; int i ; for  ( i = l ; i<process->ipnum+l; i++)  •C ccbl = process->chan + i ; i f (ccbl->targetc != NULL)  •C ccb2 = ccbl->targetc->chan + ccbl->channelc; i f ((ccb2->targetc == process) kk (ccb2->channelc FDTCCBdisconn (process, i ) ; else FDTCCBdetach2 (process, i ) ; }  >  > free (procesB->chan);  == i ) )  APPENDIX  I* *  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  Implements the E s t e l l e connect statement  FDTCCBconnect (processl, channell, q d i s p l l , process2, channel2, qdispl2) FDTPCB *processl, *process2; int channell, channel2; queue.kind q d i s p l l , qdispl2; < FDTCCB *ccbl, *ccb2; /***** Locates channel control blocks *****/ ccbl - processl->chan + channell; ccb2 - process2->chan + channel2; ccbl->qdispl = q d i s p l l ; ccb2->qdispl = qdispl2; /***** Tests f o r prior connections *****/ i f ((ccbl->targetc != NULL) || (ccb2->targetc != NULL)) FDTLIBerror ("Channel i s already connected"); /***** Makes formal connections *****/ ccbl->targetc ccb2->targetc  - process2; = processl*,  ccbl->channelc = channel2; ccb2->channelc = channell;  /***** Finds actual target channel control blocks *****/ i f (ccbl->targeta != NULL) i  processl = ccbl->targete; channell = ccbl->channele; ccbl->targete = NULL; ccbl->channele = 0; ccbl = processl->chan + channell; > i f (ccb2->targeta != NULL) i  process2 = ccb2->targete; channel2 = ccb2->channele; ccb2->targete = NULL; ccb2->channele = 0; ccb2 = process2->chan + channel2;  APPENDIX  D. CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  > /***** Makes actual connec  m *****/  ccbl->targete ccb2->targete  ccbl->channele = channel2; ccb2->channele = channell;  = process2; = processl;  /* *  Implements the E s t e l l e ATTACH statement  */ FDTCCBattach FDTPCB int queue_kind  (processl, channell, q d i s p l l , process2, channel2, qdispl2) *processl, *process2; channell, channel2; q d i s p l l , qdispl2;  i  FDTCCB  *ccbl, *ccb2;  /***** Locates channel control blocks •****/ ccbl = processl->chan + channell; ccb2 = process2->chan + channel2; ccbl->qdispl = q d i s p l l ; ccb2->qdispl = qdispl2; /***** Tests f o r prior connections *****/ i f ((ccbl->targeta != NULL) || (ccb2->targetc != NULL)) FDTLIBerror ("Channel i s already attached"); /***** Makes formal attachments *****/ ccbl->targeta = process2; ccb2->targetc = processl;  ccbl->channela = channel2; ccb2->channelc = channell;  /***** Finds actual target channels •****/ if  (ccbl->targetc != NULL) { processl = ccbl->targete; channell = ccbl->channele; ccbl->targete = NULL; ccbl->channele = 0; ccbl = processl->chan + channell;  /* attach down */ /* connect up */  82  APPENDIX  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  > if  (ccb2->targeta != NULL) {. process2 = ccb2->targete; channel2 = ccb2->channele; ccb2->targete = NULL; ccb2->channele = 0; ccb2 = process2->chan + channel2; >  /***** Makes actual attachment *****/ ccbl->targete = process2; ccb2->targete = proceasl;  ccbl->channele = channel2; ccb2->channele = channell;  >  /* * Implements the E s t e l l e DISCONNECT statement */ FDTCCBdisconn ( p r o c e s B l c , channellc) FDTPCB *processlc; int channellc; { FDTCCB *ccblc, *ccb2c; FDTCCB *ccble, *ccb2e; FDTPCB *processle, *process2c, *process2e; int channelle, channel2c, channel2e; i f (channellc == 0) int  i ;  f o r (i=l; i<processic->ipnum; i++) FDTCCBdisconn (processlc, i ) ; }  elBe  •c /***** Locates actual channel control blocks *****/ ccblc = processlc->chan + channellc; process2c = ccblc->targetc; channel2c = ccblc->channelc; i f (process2c = NULL)  APPENDIX  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  FDTLIBerror ("Attempt to disconnect unbound channel"); ccb2c = process2c->chan + channel2c; /***** Tests f o r prior connections *****/ i f ((ccb2c->targetc != processlc) I I (ccb2c->channelc != channellc)) FDTLIBerror ("Attempt to disconnect attached channel"); /***** Locates effective channel control blocks *****/ ccble = ccblc; while (ccble->targete == NULL)  •C processle = ccble->targeta; channelle = ccble->channela; ccble = processle->chan + channelle;  ccb2e = ccb2c; while (ccb2e->targete == NULL) i  >  process2e = ccb2e->targeta; channel2e = ccb2e->channela; ccb2e = process2e->chan + channel2e;  /***** Disconnects actual channels *****/ ccblc->targetc = NULL; ccb2c->targetc = NULL;  ccblc->channelc = 0; ccb2c->channelc = 0;  /***** Rebinds effective channels, i f necessary *****/ i f (ccblc != ccble) < ccblc->targete = processle; ccble->targete = processlc; > else ccble->targete = NULL;  if  ccblc->channele = channelle; ccble->channele = channellc;  ccble->channele = 0;  (ccb2c != ccb2e) i  ccb2c->targete = process2e; ccb2e->targete = process2c;  ccb2c->channele = channel2e; ccb2e->channele = channel2c;  APPENDIX  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  > else  ccb2e->targete = NULL;  ccb2e->channele  = 0;  > }  >  /* * Implements the E s t e l l e DETACH statement f o r an external interaction point */ FDTCCBdetachl (processla, channella) FDTPCB *processla; int channella; i  FDTCCB FDTCCB FDTPCB int  *ccbla, *ccb2a; /* Formal attachments */ *ccble, *ccb2e; /* Actual attachments */ *proceasle, *process2a, *process2e; channelle, channel2a, channel2e;  /***** Locates channel control blocks f o r actual attachments if****/ ccbla = processla->chan + channella; process2a = ccbla->targeta; channel2a = ccbla->channela; i f (process2a = NULL) FDTLIBerror ("Attempt to detach unbound channel"); ccb2a = process2a->chan + channel2a; /***** Tests f o r prior attachments *****/ i f ((ccb2a->targete != processla) II (ccb2a->channelc != channella)) FDTLIBerror ("Attempt to detach improperly attached channel"); /***** Locates channel control blocks f o r effective attachments *****/ ccb2e = ccb2a; while (ccb2e->targete == NULL) { process2e = ccb2e->targeta; channel2e = ccb2e->channela; ccb2e = process2e->chan + channel2e; }  processle = ccb2e->targete;  APPENDIX  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  86  channelle = ccb2e->channele; ccble = processle->chan + channelle; /***** Dettaches actual channels **•**/ ccbla->targeta = NULL; ccb2a->targetc = NULL;  ccbla->channela = 0; ccb2a->channelc = 0;  /***** Rebinds effective channels, i f necessary *****/ i f (ccbla != ccble) ccbla->targete = processle; ccble->targete = processla;  ccbla->channele = channelle; ccbie->channele = channella;  else ccble->targete = NULL;  ccble->channele = 0;  i f (ccb2a != ccb2e) ccb2a->targete = process2e; ccb2e->targete = process2a;  ccb2a->channele ccb2e->channele  = channel2e; = channel2a;  else ccb2e->targete = NULL;  ccb2e->channele  = 0;  * Implements the E s t e l l e DETACH statement for a child's external interaction point */ FDTCCBdetach2 (process2a, channel2a) FDTPCB *proce8s2a; int channel2a;  •C FDTCCB FDTCCB FDTPCB int  *ccbla, *ccb2a; /* Formal attachments */ *ccble, *ccb2e; /* Actual attachments */ *processla, •processle, *process2e; channella, channelle, channel2e;  /***** Locates channel control blocks f o r actual attachments *****/  APPENDIX  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  ROUTINES  ccb2a = proceBs2a->chan + channel2a; processla = ccb2a->targeta; channella = ccb2a->channela; i f (processla == NULL) FDTLIBerror ("Attempt to detach unbound channel"); ccbla = processla->chan + channella; /***** Tests f o r prior attachments *****/ i f ((ccbla->targetc != process2a) I I (ccbla->channelc != channel2a)) FDTLIBerror ("Attempt to detach improperly attached channel"); /***** Locates channel control blocks f o r effective attachments **** ccb2e = ccb2a; while (ccb2e->targete == NULL) i  >  process2e = ccb2e->targeta; channel2e = ccb2e->channela; ccb2e = process2e->chan + channel2e;  processle = ccb2e->targete; channelle = ccb2e->channele; ccble = processle->chan + channelle; /if****  Dettaches actual channels *****/  ccbla->targeta = NULL; ccb2a->targetc = NULL;  ccbla->channela = 0; ccb2a->channelc = 0;  /***** Rebinds effective channels, i f necessary *****/ i f (ccbla != ccble)  •C ccbla->targete = processle; ccble->targete = processla;  ccbla->channele = channelle; ccble->channele = channella;  }  else < ccble->targete = NULL;  ccble->channele = 0;  i f (ccb2a != ccb2e)  •C ccb2a->targete = process2e; ccb2e->targete = process2a;  ccb2a->channele ccb2e->channele  = channel2e; = channel2a;  APPENDIX  D.  CHANNEL  CONTROL  BLOCK  SUPPORT  }  else i  ccb2e->targete = NULL; >  ccb2e->channele = 0;  ROUTINES  Appendix E  Signal Control Block Support Routines  89  APPENDIX  E. SIGNAL  CONTROL  BLOCK  SUPPORT  ROUTINES  /* * Creates a new signal control block on the target of the specified channel */ FDTSCBsignal (process, c i d , s i d , svar) FDTPCB ^process; int cid; int sid; int *svar; < FDTCCB *ccbl, *ccb2; FDTSCB *scb; FDTPCB *target; /***** Determines the location of the target channel *****/ ccbl = process->chan + c i d ; target = ccbl->targete; ccb2 = target->chan + ccbl->channele; i f (ccb2->qdispl == COMMON) ccb2 = target->chan; /***** Constructs an outgoing signal control block *****/ scb = (FDTSCB *) malloc(sizeof(FDTSCB)); scb->cid = ccbl->channele; scb->sid = s i d ; scb->svar = svar; /****« QueueB the Bignal control block to the t a i l of the target channel *****/ scb->next = NULL; i f (ccb2->tail == NULL) ccb2->head = scb; else ccb2->tail->next = scb; ccb2->tail = scb; /***** Increments the pending signal counter *****/ (target->sigcnt)++;  >  /* * Creates a spontaneous signal at the common channel f o r the process * i f there are no pending signals f o r the process */ FDTSCBspont (process) FDTPCB ^process;  90  APPENDIX  E.  SIGNAL  CONTROL  BLOCK  SUPPORT  ROUTINES  •C FDTCCB FDTSCB  *ccb; *scb;  /***** Exits i f there are pending signals *****/ i f (process->sigcnt > 0) return; /**•** Constructs a spontaneous signal control block *****/ scb = (FDTSCB *) malloc(sizeof(FDTSCB)); scb->cid = 0; scb->sid = 0; scb->svar = NULL; /***** queues the signal control block at the common channel *•***/ ccb = process->chan; scb->next = ccb->head; ccb->head = scb; i f (ccb->tail = NULL) ccb->tail = scb; /***** Increments the pending signal counter *****/ (proce8S->sigcnt)++;  >  /* * Removes a signal control block from a channel */ FDTSCBdispose (process, signal) FDTPCB *process; FDTSCB *signal; < FDTCCB *ccb; FDTSCB *scb; /***** Determines the location of the signal queue •****/ ccb = process->chan + signal->cid; i f (ccb->qdispl == COMMON) ccb = process->chan; /***** Removes the signal control block at the head of the queue *****/ scb = ccb->head; ccb->head = scb->next; i f (ccb->head = NULL) ccb->tail = NULL;  91  APPENDIX  E.  SIGNAL  CONTROL  BLOCK  SUPPORT  i f (scb->avar != NULL) free (scb->svar); free (scb); /***** Decrements the pending signal counter *****/ (process->sigcnt)—; }  /* *  Searches f o r a pending signal for the process  */ FDTSCB *FDTSCBpending (process) FDTPCB *process; FDTCCB if  *ccb;  (process->sigcnt == 0) return (NULL);  ccb = process->chan + process->ipnext; while (ccb <= process->chan + process->ipnum) i f (ccb->head != NULL)  •C process->ipnext = ccb - process->chan + 1; return (ccb->head); > else  •c ccb++; > ccb = process->chan; while (ccb < process->chan + process->ipnext) i f (ccb->head != NULL) < process->ipnext = ccb - process->chan + 1; return (ccb->head); > else ccb++; > return (NULL); }  ROUTINES  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051896/manifest

Comment

Related Items