Bertrand's Design Study

Latest revision as of 11:00, 5 October 2009

Last year, I was involved in a project which consisted in building an autonomous robot to compete in the French Robotic Cup. My main task was to handle all the data transmissions in the robot. This mean I had to work a lot with networks, especially the CAN network (widely used in cars).

This one is not like TCP/IP, there is no sources nor destinations. All frames have IDs (11 or 29 bits), and each nodes connected to the network needs to determine if the frame is relevant or not by filtering IDs.
The main problem is for managing the whole network, which mean handling IDs:

• nodes are mostly µc like PIC, ARM, ... and are running home-made firmwares, usually written in C, and are not running any OS
• the data part of a frame can be up to 8 bytes long, the format is determined by the developer

Managing the network "by hand" would be a really painful task: determining IDs, format, writing them in the code, ... can lead to an infinite amount of errors and wasted time. In order to do that, I developed a tool called CanXml in C++ which takes an XML-based configuration file describing the network (nodes, frames, format), and exporting it as a C header with all the networks IDs defined in here using #define with convenient names.

This tool was really helpful but when designing it, I was thinking in building a library that feature tools to manage the network, but also that can be used to debug the network.

This goal was not reached and the design I realized then is far from perfect, that's why I think it can be a great subject for my design study.

Requirements

The library must feature:

• network management abilities (IDs generation, XML import and C-header export)
• a way to process existing frames
• be memory efficient (in order to be used on Linux embedded devices)

And it also need to be clean, since I want to release it under an open source license.

First implementation

In my first attempt, I was mainly trying to make things work and I did not much think about what the design should be to be a good OO design.

Here is the first UML (I didn't represent most getter and setters, they are everywhere though):

My naming convention appeared as a bad choice when I started implementing a way to process existing frames, there is a conflict between "abstract frames" (the "family") and "concrete frames" (transfered frames), which gets really confusing when processing the code.

The way it determines IDs is too static, the policy is static while it should be more ... well, dynamic. Network/Nodes/Frames is some kind of tree, and each frame generate his ID using a simple algorithm based on the node it belongs to, the priority, ...

There is another problem for XML import and C export which is closely related. The XML file is processed recursively by objects in order to build the tree. A similar pattern is used for C export. The whole library heavily depend on one XML library (ticpp).

Another thing about the way it export things is that even if both exportViz and exportC seems similar, they are not implemented in the same way.

The pattern I used for storing the format is too complex and inefficient. Since I was looking for a memory-efficient way to handle formats of different type, bit sizes, endianness while being able to process existing frames, I produced something that is heavy and not clean. It is a merge between the factory and flyweight pattern, mixing elements that are initiated when the factory is first used with more complex elements like Enum. Another funny thing is that the Format is a factory buildings elements of the same type ... This is done in a dirty way using lots of static variables (static is the new global :o), rather than having a factory singleton class which would have been a lot cleaner. I broke the law in so many ways here I can't believe I'm not in Guantanamo Bay.

Another error I made was to start writing the concept using french words for attributes, class names, etc ... When I realized I would probably like to release it, I switched to english, but it was too late for that ...

Actual implementation

I released my work in OpenSource, the library is called CanArch (CanOE at first but this name was already taken).

UML diagram for CanArch:

(Most getters/setters are not represented)

I started from scratch in order to build something clean from the beginning. A principle maxim is this design was to Model the real world and to keep concerns separated.

Architecture exploration

The overall network architecture is quite similar to the past one, except that all classes inherit from the TreeObject, which is an entrance door for the Visitor pattern and is also holding the Observer collection. All import and export behavior have been ejected from the network tree. On the input part, a class handle the XML import process and keep all XML related parts in one class, which allow the design to be loss couple with the XML library. On the output part, the Visitor is heavily used to explore the network and do the related work. This abstract class offer multiple handlers which have default no-op implementations except for the handleBegin(Network) method. That allow inheriting classes to behave pretty much how they want without heavy implementation.

Concerning the Enum handling, each network has an EnumCollection, which is holding EnumReferences, which are holding a map associating values with strings. An Enum mostly bind the required Type methods to the ones in EnumReference.

The Network is holding a map between IDs and FrameTypes in order to handle easily existing Frames. This map is actualized when the ID of a FrameType is changed using the Observer pattern implementation. Indeed, each time a change occur in the Tree the Network node gets notified.

Pattern used

• Visitor: Exporters / IdGenerators are visitors that use the TreeObject door to navigate through a Network architecture
• Iterator: EnumCollection and EnumReference are using iterators to allow a const access to their collection. The Iterator itself is inherited from the STL. EnumCollection's begin() and end() are just passing through the results of the begin and end standard operators of their list while the EnumReference has a nested class that inherit the standard map const iterator and implement two other methods to allow an easier access to data.
• Observer: An implementation of NetworkObserver can register to any element of the network tree and be notified when it changed. By default the constructor of a LeafObject register his parent, allowing a parent node to be notified when a child changed. In the case of a LeafObject, the handleChange simply call notifyChanged.
• Strategy: A Network object has an object which class inherit IdGenerator::BasePolicy that handle the ID generation process.
• Factory Method: An EnumReference has a newEnum method that make Enum objects.
• Adapter: The Enum version of Type is an Adapter that allow an EnumReference to behave has a type. The reason why an EnumReference does not inherit from Type is that it can be shared by multiple instances of Enum.

All Singletons have been removed from the past implementation since the library was written in order to be able to handle multiple networks without conflicts. The weird implementation of the Flyweight pattern was also removed in order for the user to register to Type objects for example.

Improvements

The whole existing frame handling is not implemented yet, but it would simply be a factory in the Network class that would take a RawFrame and return a Frame linked to an instance of FrameType. However another thing would be to put a triggered(TreeObject) in the NetworkObserver in order to handle events that would be generated when a FrameType is received.

I'm already thinking about few refactoring work for the architecture though.

I think that the XmlImporters knows to much. It is really tight coupled to the network architecture. In the first implementation, the library was heavily coupled with the XML library, which is not the case any more, since only one class handle the xml import process. However, now any change in the network architecture would imply a whole new XmlImporter. I think that the XmlImporter should only create the Network object with the right configuration, then convert the network definition (the "tree" part) to a basic and really abstract internal storage (that would be based on the Composite pattern), and in the end the importer would simple tell the Network object to parse the this internal definition (this would realize the Interpreter pattern. It would have multiple advantages, new importers from other file types could be created quite easily as long as they create an internal definition in a similar way that the xml one does, and another thing is that another network implantations can be done without having to change heavily the way that importers work. Another thing is that there is lot of setters for now, which is not that great. Such internal language would allow an heavy encapsulation since the objects would modify themself when parsing the language. It would also be a great support for the Command pattern a modification could be kept using such thing.

The current version of the library support really low-level networks, while higher level protocols (DeviceNet, ...) are available and widely used. Another thing is that in more complex architecture, other kind of networks are used (LIN, ...). I already though about few ideas to support them. Most of the existent work would be kept and it would mostly consist in few inheritance of Network parts in order to change few beaviours.

Links

• libcanoe @ SourceForge (project page for CanOE, which will be replaced in a few days)
• Article on my blog