Friday, September 13, 2013

Maintainable Software, Adventure 2

This adventure in maintainable software is included because some very stringent requirements and a couple of significant requirements which came in late in the project lead to a highly maintainable architecture/design.  This was a firmware project for what was called a BootROM in an embedded system.  One aspect of this type of application is that unless you count the system code which is loaded, there is no application data but some configuration data.  

The restrictions and requirements were roughly as follows:
o   The system buss was VME which is/was the standard for large embedded systems
o   The RAM available for firmware use was very limited.  There was enough for roughly 3 stack frames as generated by the C compiler which limited the calling depth
o   There was no practical limit on ROM address space
o   There was a good amount of flash memory for configuration data
o   It required using three languages (assembler, C and Fourth)
o   It must support simultaneously an arbitrary number (0 to n) of Human Interface devices (keyboards, displays, and RS-232 ports.  Late in the project was added remote console (LAN) interfaces.  All of these interfaces were to remain active even while the OS/user system was being loaded
o   It must be capable of finding an arbitrary number of bootable systems on each of an arbitrary number of bootable devices (disks and remote (LAN) servers)
o   It must be capable of accepting input from keyboards configured for any of dozens of human languages and displaying messages in those languages.
o   It must be capable of running diagnostics for any user supplied device which appeared on the VME bus.
o   Late in the project a requirement was given to support what was known as hard real time.  What this mostly meant was that the system as a whole must be capable of going from power on to user code running under Linux in under 30 seconds. What this required of the firmware was to ignore HI devices and to disable all diagnostic code except for devices directly involved in the boot process
o   Oh! And if possible allow users to modify the code

The requirement for Forth came about because at the time there was a push for a way to allow device interfaces to contain their own driver code.  This was to be the way in which interface testing and boot support was to be supplied so that firmware did not have to be constantly updated for new or changed devices.  A group of manufactures and suppliers including, Hewlett-Packard and Apple had come to an agreement that Forth would be the language used to implement this capability.  Also at this time a IEEE standard for Forth was accepted. 

The problem of supporting keyboards for any language was solved by using a pure menu based human interface system where menu items were selected by keying a number.  This worked because all keyboards have the same key position for the numbers (excluding number pads).

A breakthrough solution for the stack depth problem came when I realized that if code was broken up into small functions that a state-machine could be used to represent calling sequences and the stack depth could then be limited to a single level.  A refinement of this design was to limit the number of function arguments to three because the C compiler always put the first three arguments into registers rather than on the calling stack thus further reducing the stack frame size.  The state machine description could be stored in ROM. 

The rough process used to create such a representation was to translate each subroutine into a state machine representation by refactoring each straight line code segment (code between routine calls) into a function and replacing each subroutine/function call with the state machine representation of that routine.  This was rather laborious but fortunately most routines were small and straight line.
The following is a simple abstract example of this flattening and state machine representation:

‘Normal version’ for simplicity it is assumed that only sub2 calls another routine.
subroutine A(arg1)
    code seg1
    v1 = func1(arg1)
    if (v1=1) call sub2(arg1) else call sub3(v1)
    code seg2
    call sub4(v2)
end sub A
subroutine sub2(argx)
     code seg3
     call sub5
end sub2

‘State machine version’
Code segments 1, 2, 3 etc. are refactored as functions.   Most often the return value is a 0 or 1 indicating success or failure.
Rv is the return value while Arg1 and V1 are a ‘global’ variables
StateA1
     Rv=seg1();  stateA2
StateA2
     Rv=func1(Arg1) ;  1,stateS2.0; 0,stateA3
StateA3
     Rv=Sub3(V1); 1,stateA4
StateA4
     Rv=seg2(); 1,stateA4
StateA5
     Rv=Sub5(); 0
The 0 or here indicates completion for the machine
State S2.0 // this implements sub2
     Rv=seg3(); state S2.1
State S2.1
     Rv=Sub4(); stateA4 // this is the return from sub2

Another innovation was in the state-machine representation and its ‘interpreter’.  In conventional state-machines, the ‘interpreter’ operates by calling a routine which returns an value (often a character from an input source) this value along with the number of the current state is used to index into a two dimensional array to fetch the number of the next current state, this number is also used to select and call a routine which is the action associated with the state.  This process is repeated until some final state is reached. 

The main problem with this design is that as the number of states increases the number of empty or can’t get there values in the state table increases along with the difficulty in understanding what the machine is doing.  Documentation can help but must be changed every time the state machine is changed.  The solution I came up with was to represent the state-machine as a table of constants in assembler language and use addresses instead of index numbers.  Each state has a name and contains the address of the function to call, its arguments and a list of value-next state pairs.  The following examples and explanations may be a bit tedious for some people but they form the basis for my solution to the multiple HI devices problem as well as solving the stack size problem.

In this example the dc stands for Define Constant and the -* causes a self-relative address to be produced, this will be explained later
stateX1     dc ‘op1 ‘ //arg1
            dc 1      //arg2
dc 0      //arg3  not used
            dc myfunc-*
            dc value1,stateX1-*  // repeat stateX1
            dc value2,stateX2-*
            dc 0,0 // end of list

The calling a routine for an input value was eliminated and the ‘interpreter’ ran by using the current state address to select the function to call but then used the return value from that call to select the next state from a list tailored to that functions return values.  This minimizes the amount of space to represent the state machine and makes it somewhat easier to follow a sequence of transitions.

The requirement to support simultaneous use of multiple HI devices even while the OS/system is being loaded provided a significant challenge because there was not enough available RAM as well as other issues which prevented using an interrupt based mechanism like the Operating Systems do.  Firmware had to use a polling mechanism which meant that the user ‘lost control’ while the OS was being loaded as well as at other times.  The requirement to support a LAN based console was over the top because driver code in general had never been implemented or even designed to be used for two different purposes at the same time.

The multiple simultaneous HI device ‘problem’ was solved primarily by changing the state machine to support a cooperative multi-threading mechanism and then creating a thread for each input device and a separate thread for the selected boot device.  Each input device thread was a two state state-machine which called the driver requesting a character.  If one was not found, the next state is the same as the current state and when one was read, the next state called a function which invoked the menu system then transitioned to the first state.

This worked because the state-machine interpreter was modified to work with a list of state machine records.  I do not remember the details of how it was implemented but even now I can think of at least three ways it could have been done.  The essence is that the interpreter would pop the next state address off a list and execute the state selected.  After executing the state, new next state address was put on the end of the list and the cycle would be repeated. The effect of this was to switch threads on state boundaries and therefore after each function call.  The LAN driver was converted to state-machine format and refactored to have both boot protocol and console protocol components thus allowing the console and boot operations to work simultaneously.

At the time of this design, there was great interest in using ‘building blocks’ as a way to construct easy to build and maintain systems.  No one had as yet actually tried or even come up with a concrete proposal.  Because we anticipated a huge maintenance work load after the first system release I decided to try to come up with something for this project.




                  The resulting architecture initially consisted of a ‘core’ block an English language block, a set of               driver blocks and an end block. 

                                                
The Core block contained normal BootROM stuff, including basic initialization, the Forth Interpreter and various general utility routines which could be used by all blocks.  The End block was nothing more than a set of null pointers to terminate all the lists.  There were in fact several more linked lists than are shown in the above diagram.  All of these links were self-relative pointers and were paired with a bit pattern which indicated if there was anything of interest at that address for example text for English or code for a human input device.  Each block relied on the assumption that there would be a set of pointers immediately following its own code.   Each block was compiler/assembled independent of one another. The ‘ROM’ was constructed by extracting the code from compiled files and literally concatenating them between the Core block and the End block.  This architecture required code and addresses such as the ones in the state-machine tables and the lists running thru the blocks to be self-relocating.  The compiler generated self-relocating code.  The self-relocating requirement for addresses was met by making them self-relative (add the value at an address to its address to produce the required needed address. The null pointer was detected by checking for zero before the addition step.

The ‘multiple human languages’ requirement was met in part by the HI input device mechanism described above and in part by using a pure menu system and in part by the following mechanism.

All of the text for all human visible messages was placed in a table and referred to by a number.  This text consisted of phrases and single words which could be combined as needed. Messages as stored in the table could be either text or a string of message numbers.  When a message needed to be displayed, a call would be made to a print routine in the Core block and giving it the message number.  This routine would find the language table for the currently configured language,  construct the text version of the message then find all the console output devices and have them display the message.
These messages and message fragments were developed by Human Factors specialists.  I developed a simple emulator (in Perl) which would behave like the ROM in terms of how the menu system worked and how it would react to error conditions.  These specialists then had complete control over the message text.  This allowed parallel development of code and user manuals.  When the time came to deliver the ROM,  I used a Perl script to extract the messages and generate the English language block.  The same or very similar process was used to generate the French language block.
The last requirement (“Oh! And if possible allow users to modify the code”) was put in place by creating a developer’s kit which consisted of a lot of documentation, the ready to concatenate files used in the ‘standard’ ROM and the scripts used to create them.
Historical notes:
o   Shortly after the first release of this ROM, Apple came out with the first device which was to support the Forth language concept.  Instead of Forth, their ROM contained machine code.  Their comment was ‘we never intended to support Forth’.  That killed the initiative.
o   The system this ROM was part of was designed to work in hostile/demanding environments primarily for data collection/management purposes.  As I recall, it was used in monitoring tracks for the Japanese bullet trains, doing something in the latest French tanks, monitoring and controlling sewage treatment plants, collecting and displaying data for an Air Traffic control system and collecting and displaying data in the US Navy Aegis weapon systems.
o   I did train engineers for one company to allow them to build their own ROMs.
o   About a year after releasing this project, the division was disbanded but maintenance was transferred to another division.  About five years after this I talked with an engineer who had been assigned to maintaining the ROM and he said that he had been maintaining it by himself for a few years and had released new modules and had easily made several releases per year by himself.

Summary of things done and learned:
o   Used Assembler, Forth and C in the same application.
o   Designed and implemented what may be the only true ‘building block’ system.
o   Learned that separating control logic from computational logic helps maintainability.
o   State-machines are a viable way to keep control and computational logic separate and make the control logic very visible.
o   Simple emulators can be used to see what an application will look and behave like before and while the application is being built.  They can be cost effective because the allow scenario testing before the code becomes too rigid.
o   Learned a lot about multi-threaded systems work in a very controlled environment
o   The building block architecture proved to be a very good way to improve maintainability



No comments:

Post a Comment