OSCL ITC Framework Evolution
 Table of Contents

This article describes the evolution of the OSCL Inter Thread Communication framework.

Introduction

The OSCL ITC framework is designed to support client-server style communication between active objects within a single multi-threaded address space. The client-server active object model notation describes a way to view system designs using this concept. The diagram below illustrates the fundamental components of the active object client-server model.

clientserver.png

The communication mechanism between client and server is the subject of this article, presented as an evolution of concepts in an attempt to describe the design choices and structure of the OSCL ITC framework.

Messaging Tradition

Messages are objects used to convey information between concurrent processes and threads. Messaging services are as old as operating systems themselves and have taken many forms.

Most operating systems offer a form of messaging, known by many names and with several variations, that I will collectively call message queues. The implementation of message queues generally takes the form of an array that is treated as a fixed length queue. Messages are copied into the buffer in FIFO order by one process/thread, and removed by a receiving process/thread. Other names for mechanisms in this class include pipes, fifos, and sockets.

There are two interesting issues with these mechanisms.

When the queue to becomes full (the fixed length queue has no available slots,) the client must take exceptionsl action that may include: The method chosen is highly application dependent. Ideally, it would be nice if we could simply eliminate the queue full condition. By constraining the design to a single multi-threaded address space, the OSCL ITC framework makes use of linked list data structures rather than fixed length queues to allow for queueing without exceptions.

Of course there is no such thing as a free lunch and the result is that the problem changes slightly into a memory management issue rather than a queue full issue, but the OSCL ITC framework compensates for this by providing higher level mechanisms and policies for solving these issues in a more consistent way.

Another issue with message queues is that they require message data be copied into the queue during the send operation and out of the queue during the receive operation. While inefficient, this has the advantage of supporting the same messaging semantics across address spaces (e.g. TCP/IP sockets, UNIX fifos and pipes.)

However, by constraining the communication to threads within a single address space, the copying overhead can be reduced by only copying a pointer to the data into the message queue rather than the data itself. Of course, this requires that the sending thread not modify the pointed-to data while the receiver is operating on the data. As a result, a memory management and synchronization issue arises. The issue is how the sender can know when it can safely use/reuse the memory used for the message again.

This can be handled in a number of ways including:

Of these, we'll simply discount the flag polling as obviously inefficient in terms of processor utilization.

Semaphores can be used by having the sender block until the receiver signals the semaphore indicating that the receiver has finished with the message. However, this apparently simple solution is deceptive in that it requires careful system design to prevent deadlock. It also suffers from the problem that the sending thread is unable to perform any other activities while it is blocked waiting for the response.

Acknowledgement messages can work as long as there is assured delivery of the message without blocking. By using linked-list data structures for message queues, this requirement can be met, and acknowledgement messages can be effective, once the memory management issues associated with the messages are addressed.

The sender allocates - receiver releases style messaging is used in situations where the message source has no need of an acknowledgement. The sender allocates the message resources from a common pool and then sends the message. The receiver takes whatever action is necessary and then frees the message resource to the common pool.

The apparent simplicity of this technique belies the potential issues associated with such a technique. A brain-dead implementation might have the sender allocate message memory from the global heap (malloc/new) and the receiver release the message memory to the global heap (free/delete.) See the discussion on memory management in embedded systems to see why this is a bad idea.

While using global malloc/new free/delete is the wrong design decision for embedded systems, the sender allocates - receiver releases policy can be applied successfully with a dynamic memory policy specifically designed to prevent fragmentation. One important example is in the implementation of data communications protocol stacks, where it is typical for a driver to allocate buffers, and the upper protocol layers release the buffers. This technique works well with data-communications protocols which have re-transmission and flow control mechanisms which allow them to recover from temporary out-of-message-memory conditions. Such protocols, while useful and un-avoidable in distributed computing, require great care in their implementation and design, and are impractical for thread-to-thread messaging.

Linked List Message Queues

For the purposes of communications between threads within the same address space, message passing can be structured such that the act of sending a message never fails. This is done by using a linked list as the receiver's mailbox. Using such a mechanism, once the sender has acquired the memory needed to send a message, it can link it the message into the receiver's mailbox without exception.

This is almost as efficient as the placement of pointers in traditional message queues, but without the need to wory about queue full conditions. For singly linked list message queue implementations, the difference is two pointer copies rather than one.

This linked-list method is used for message passing in the OSCL ITC framework. All messages in the OSCL ITC framework contain a link field so they can be linked into the mailbox of the receiving thread. This required link field provides an additional advantage in that messages can be placed in linked lists other than mailboxes when they are not currently threaded into a mailbox. For example, a receiver may defer the servicing of messages once they are received by storing them on an internal linked-list queue. More generally, in conjunction with the Oscl::Queue template class, the link field simplifies managing the message resources and memory.

The Oscl::Queue template class (defined in the file oscl/queue/queue.h ,) provides an easy to use and type-safe singly linked list queue implementation. It is used to implement the OSCL ITC framework mailboxes. The following diagram illustrates the most commonly used interface elements of the Oscl::Queue template class.

osclqueuequeue.png

Any element linked into an Oscl::Queue must have a public link field member with the following signature:

void* __qitemlink;
This field is usually supplied by inheriting the Oscl::QueueItem type defined in oscl/queue/queueitem.h header file.

The definition of the OSCL ITC framework mailbox (Oscl::Mt::Itc::Mailbox)is found in the oscl/mt/itc/mbox/mbox.h header, and implemented in the oscl/mt/itc/mbox/mbox.cpp file.

The most simple message might be an instance of Oscl::QueueItem. Of course such a message is not very useful, and indeed in reality cannot even be used with the Oscl::Mt::Itc::Mailbox since its linked list is not publicly accessible as it must be shared by multiple threads and access to the list must be protected by a mutual exclusion mechanism.

The pertinent mailboxinterface elements are illustrated in the following diagram.

osclmtitcmbox.png

The Oscl::Mt::Itc::Mailbox accepts messages which are of the type Oscl::Mt::Itc::Msg.

osclmtitcmboxmsg.png
This abstract class, defined in the file oscl/mt/itc/mbox/msg.h inherits the required queue link field from Oscl::QueueItem and defines a polymorphic operation (pure virtual) called process().

Message Discrimination and Dispatch

The receiver of a message must examine the message to determine its type, and ultimately decide what to do with the message. The type indicates to the receiver what the sender intends the receiver to do with the message, and the types of data that may optionally be a part of the message.

Traditionally, determining the message type has been done by defining an integer field common to all messages, that contains value mapped to the message type. The receiver examines the type using a switch statement, and takes the appropriate action with the remainder of the message, which might include casting data to an appropriate type.

Seeing the switch-on-type construct, the object oriented practioner can clearly see an oportunity for improvement. Thus the purpose of the Oscl::Mt::Itc::Msg::process() operation is to polymorphically dispatch the appropriate message handling based on its message type.

Client-Server Message Types

Before we consider how to apply the polymorphic process() operation, lets first consider the differing needs of clients and servers with respect to their handling of messages.

Interfaces define a set of requests that a server is expected to satisfy. Requests are ITC messages in the OSCL ITC active object framework.

It is usually the case in a client-server relationship that the client needs to know when the server has completed a particular request. This is required either to obtain the resulting data from the request or to simply know that the server is finished with the client resources used for the communication (e.g. the ITC message.)

There are many methods the server might use to indicate that it has completed the request. For example, the server might set a semaphore on which the client is blocked, or the server might send a reply message to the client.

To promote decoupling, and provide a flexible messaging system, it is desirable to leave the choice of acknowledgment mechanism to the client. Likewise, it is important to to hide the actual mechanism from the server.

The OSCL ITC framework realizes this by using another polymorphic operation called returnToSender() as illustrated by the Oscl::Mt::Itc::SrvMsg as defined in the file oscl/mt/itc/mbox/srvmsg.h.

osclmtitcmboxcsmsg.png
The returnToSender() operation is invoked by the server when it has finished the request associated with the message.

Notice that clients have no need for a returnToSender() operation since they are the senders of the requests. Indeed, as we'll see later, clients receive responses and servers receive requests.

For reasons of symmetry, type-safety, and to emphasize the distinction between requests and responses the ITC framework defines Oscl::Mt::Itc::CliMsg as another message subclass.

The Return Handler

A return handler determines what happens when a server invokes the returnToSender operation on a server request message. There are two return handler implementations that correspond to the two primary acknowledgement mechanisms promoted by the OSCL ITC framework: These two types correspond to the mode in which clients may receive acknowledgements of completion to server request messages. The connection with the Oscl::Mt::Itc::SrvMsg is illustrated below.

csrethandler.png

It is possible to create other types of return handlers, for very specialized uses, but my experience to this point has proven that to be unnecessary. As a result, it is strongly recommended that any decision to create a new type of return handler be undertaken only after considering other alternatives.

An important property of the synchronous and asynchronous return handlers is that both methods notify the client when the server has completed processing the request. This promotes and simplifies the principle of the client being responsible for the memory used in the communications with other active objects.

The message memory is considered busy or in-use until the server invokes returnToSender() operation of the request message. At that point, the memory used for the message may be reclaimed and reused by the client.

The Big Picture

The discussion of the OSCL ITC framework has touched on the distinction between messages received by clients and those received by servers. In this section, we elaborate on the distinction between requests and responses.

The following analysis diagram includes the request, response, and mailbox concepts that have been discussed thus far, and shows them in relationship with some other OSCL ITC framework concepts.

The purpose of this model is to introduce new terminology while maintaining some coherency.

itcmodel.png

From the diagram, we can see that a Thread may exist independent of a Mailbox, but every Mailbox must be associated with exactly one thread.

Likewise, a Mailbox may exist independently of any Active Object, whereas an Active Object must be associated with exactly one Mailbox. Note the implication that any number of Active Objects may share the same Mailbox and Thread. This is true as long as all ITC transactions between Active Objects within the same Thread are done asynchronously. Othwerwise, deadlock will result.

Continuing, we see that an Active Object may be associated with more than one Service. However that a Service instance may be associated with only one Active Object. A Service is an ITC interface that receives ITC messages.

There are two types of Service determined by role. A ReqApi is implemented by a server that receives request messages. A RespApi is implemented by the client that receives response messages that result from a corresponding request to the server. A RespApi is always defined in terms of specific ReqApi.

A ReqApi defines a number of Request messages that it handles. Request messages are a part of only one ReqApi. Also, notice that each Request is uniquely associated with exactly one Payload type. The payload type distinguishes Request messages from one another within a ReqApi. The ReqApi, set of Request messages, and associated Payload types comprise a server interface. The parenthesized SrvRequest is the name of an OSCL ITC framework template class that is used to capture the common implementation aspects of defining Request messages.

A RespApi is a Service defined in terms of a corresponding ReqApi for use by clients that send Request messages to the server asynchronously and expect to receive corresponding Response messages. The parenthesized CliResponse is the name of an OSCL ITC framework template class that is used to capture the common implementation aspects of defining Response messages.

The SAP (Service Access Point) object provides an association between a mailbox and a ReqApi. There is a one-to-one relationship between a ReqApi and a SAP. A client needs to know the ReqApi and Mailbox to create and send a request to a server. A SAP is an object that keeps this critical information together.

Server Request Messages

Server Request messages (SrvRequest) are server messages (SrvMsg) defined as a part of a ReqApi interface. Such interfaces are to be implemented by an active object acting as a particular type of server (service provider.)

Like all descendants of SrvMsg, Request messages have a returnToSender() operation.

Request messages are defined in terms of the Oscl::Mt::Itc::SrvRequest template class as defined in the "oscl/mt/itc/mbox/srvreq.h" header file.

cssrvreq.png

Notice in the diagram the types ReqApi and Payload are template parameters. The ReqApi type must have a member operation that matches the signature:

void request(Oscl::Mt::Itc::SrvRequest<ReqApi,Payload>& msg) throw();

where SrvRequest is the same type as this particular server request message.

The Payload type may be a class or struct, which may optionally have no members.

To help some of this jargon crystalize, consisder the following TickeReqApi a typical server interface interface definition in C++. 


#include "oscl/mt/itc/mbox/srvreq.h"

class TickleReqApi {
    public:
        class StartPayload { };
        class StopPayload { };
    public:
        typedef Oscl::Mt::Itc::SrvRequest<TickleReqApi,OpenPayload>  StartReq;
        typedef Oscl::Mt::Itc::SrvRequest<TickleReqApi,StopPayload>  StopReq;
    public:
        virtual void    request(StartReq& msg) throw()=0;
        virtual void    request(StopReq& msg) throw()=0;
    };

Notice that the TickleReqApi::request() operations are pure virtual functions. The server implementation is responsible for implementing these functions to handle the reception of each particular message type. These operations are invoked as the result of the Oscl::Mt::Itc::Msg::process() operation, which is implemented as a part of the Oscl::Mt::Itc::SrvRequest template implementation.

Each Thread with a Mailbox does message processing in a loop that looks something like this: 


void run() {
    for(;;){
        Mt::Itc::Msg*   msg;
        msg = mailbox.waitNext();
        if(msg){
            msg->process();
            }
        }
    }
The mailbox.waitNext() operation blocks until the Mailbox becomes not empty. When it returns with a valid message pointer, the process() operation of the message is invoked. If the msg is a Oscl::Mt::Itc::SrvRequest the process() implementation invokes the appropriate request() operation as follows from oscl/mt/itc/mbox/srvreq.h: 

template <class ReqApi,class Payload>
void SrvRequest<ReqApi,Payload>::process() throw(){
    _reqApi.request(*this);
    }
Look mom, no switch statement "event"/message dispatching! A concrete implementation of the TickleReqApi named TickleServer is presented graphically below.

ticklesrv.png

Asynchronous Response Messages

When clients communicate asynchronously with a server, the notification that the server has completed the requested operation is accomplished by the sending of a Response message from the server to the client as the result of the server invoking the returnToSender operation of the associated Request message.

Client Response messages (CliResponse) and their corresponding/owning RespApi are similar in structure to the server Request messages and the ReqApi with which the Request messages are associated. The difference is the direction of the messages across the client-server interface. Response messages are received by clients and the RespApi is implemented by clients that receive Response messages.

Each client Response message (a specialization of Oscl::Mt::Itc::CliResponse) is defined in terms of a specific server Request message (a specialization of Oscl::Mt::Itc::SrvResponse.) In fact, the Oscl::Mt::Itc::CliResponse template class is defined such that it actually contains (is composed of) the corresponding Request message.

The Oscl::Mt::Itc::CliResponse template captures the common behavior of response messages . The template is defined in the "oscl/mt/itc/mbox/clirsp.h" header file.

csclirsp.png

It is important to note that servers know absolutely nothing about the existence of a client response message.

Response messages are sent from the server as a result of the execution of the server invoking the returnToSender() operation of the corresponding (contained) Request message (_msg).

The following code is an example of a client RespApi interface declaration. Notice that the StartResp and StopResp messages are defined in terms of the elements defined in the TickleReqApi example described previously. 


#include "oscl/mt/itc/mbox/clirsp.h"

class TickleRespApi {
    public:
        typedef Oscl::Mt::Itc::CliResponse< TickleReqApi,
                                            TickleRespApi,
                                            TickleReqApi::StartPayload
                                            >   StartResp;
        typedef Oscl::Mt::Itc::CliResponse< TickleReqApi,
                                            TickleRespApi,
                                            TickleReqApi::StopPayload
                                            >   StopResp;
    public:
        virtual void    response(StartResp& msg) throw()=0;
        virtual void    response(StopResp& msg) throw()=0;
    };
Again, notice that there is one pure virtual response() operation for each Response message. The server is responsible for implementing these functions and take appropriate action based on the message type. These response() operations are invoked as the result of the Oscl::Mt::Itc::Msg::process() operation, which through the magic of polymorphism invokes the implementation of Oscl::Mt::Itc::CliResponse::process(), which in turn invokes the appropriate RespApi response() operation.

The implementation of Oscl::Mt::Itc::CliResponse::process() is shown below: 


template <class ReqApi,class RespApi,class Payload>
void        CliResponse<ReqApi,RespApi,Payload>::process() throw(){
    _cli.response(*this);
    }

The following diagram illustrates the relationship between a concrete client implemenation (TickleClient) and the RespApi for our TickleRespApi example.

ticklecli.png

Synchronous Messaging

When a client sends a Request message to a server synchronously, there is no need for client Response messages. In fact, the server Request message and payload are typically allocated on the client Thread's stack during a synchronous post. This is illustrated in the following code: 

void    MyClass::sendStartSynchronously() throw(){
    TickleReqApi::StartPayload         payload;
    Oscl::Mt::Itc::SyncReturnHandler   srh;
    TickleReqApi::StartReq             msg(  _sap.getReqApi(),
                                              payload,
                                             srh
                                             );
    _sap.postSync(msg);
    }
The Thread blocks on a semaphore inside the _sap.postSync(msg) until the semaphore is signaled by the server's invocation of the returnToSender() operation.

If the Request Payload contains data sent to the server, that data would be passed as arguments to the function and as arguments to the Payload constructor.

If the Request Payload carries any response data or result codes, that information would be extracted from the Payload after the _sap.postSync(msg); and returned from the function as required.

The Oscl::Mt::Itc::SyncReturnHandler implementation of the rts() operation simply signals the client Thread semaphore releasing the client from its blocked condition. 


void    Mt::Itc::SyncReturnHandler::rts() throw(){
    _sema.signal();
    }
From the client point-of-view, sending a Request synchronously is semantically indistinguishable from a simple function call.

Service Access Point (SAP)

A SAP (Service Access Point) is an important ITC framework element that is required by clients to target a Request message at a specific server. The SAP binds a Mailbox with a ReqApi.

A SrvRequest needs to know which ReqApi to use when invoking a request() operation during the execution of it's process() operation. This is done by having the SrvRequest contain a reference to the ReqApi. The ReqApi reference is passed in as a parameter to the SrvRequest constructor. Thus, the client must have a reference to the server's ReqApi.

srvreq.png

Since a CliResponse contains the corresponding SrvRequest, it too requires a reference to the server's ReqApi as an argument to its constructor so that it can satisfy its SrvRequest constructor.

clirsp.png

After a client has constructed the Request message , it must subsequently send the message to the appropriate server's Mailbox. This may be done using either the post() operation to send the message asynchronously, or the postSync() operation to send the message synchronously.

The relationship of a SAP to Mailbox and ReqApi is detailed in the following illustration.

sap.png

Of particular interest is the common abstract interface shared by the Mailbox and the SAP. The common Oscl::Mt::Itc::PostMsgApi interface means that clients can post messages to a SAP in the same way that it can post a message to a Mailbox. In fact, as can be seen in the implementation of the Oscl::Mt::Itc::ConcreteSAP and the note demonstrating its implementation, the sap simply redirects the message posting to another Oscl::Mt::Itc::PostMsgApi.

In most implementations, the PostMsgApi reference contained within the ConcreteSAP is a reference directly to the server's Mailbox.

The usual creational process is that the entity that creates the client and server, knows both intimately. This knowledge includes the knowledge of association between the server and its Mailbox. Thus this creational entity instantiates a ConcreteSAP effectively gluing together the server's ReqApi and its Mailbox. A reference to this SAP is then passed as a parameter to the constructor of the client.

Later, as the client sees fit, it creates the appropriate Request message, and then sends it to the server using its reference to the server's SAP.

So why not simply pass the ReqApi and PostMsgApi individually instead of using a SAP? The answer is that while a ReqApi is type-safe with respect to the messages it will accept, a Mailbox will accept any kind of Oscl::Mt::Itc::Msg including those intended for a ReqApi not associated with a particular Mailbox (wrong Thread.) The result of such a programming error could cause errors that are subtle and difficult to find.

Thus, the risk of dispatching a Request message to the wrong Mailbox is substantially reduced by keeping them bound together in a SAP. It is also easier to pass a single SAP reference across an interface instead of the two (ReqApi and Mailbox references.)

Because a SAP is so useful and important, it is standard operating procedure to declare the appropriate SAP specialization as a part of the ReqApi. 


#include "oscl/mt/itc/mbox/srvreq.h"
#include "oscl/mt/itc/mbox/sap.h"

class TickleReqApi {
    public:
        typedef Oscl::Mt::Itc::SAP<TickleReqApi>         SAP;
        typedef Oscl::Mt::Itc::ConcreteSAP<TickleReqApi> ConcreteSAP;
    public:
        class StartPayload { };
        class StopPayload { };
    public:
        typedef Oscl::Mt::Itc::SrvRequest<TickleReqApi,OpenPayload>  StartReq;
        typedef Oscl::Mt::Itc::SrvRequest<TickleReqApi,StopPayload>  StopReq;
    public:
        virtual void    request(StartReq& msg) throw()=0;
        virtual void    request(StopReq& msg) throw()=0;
    };

Interface Conventions

A client-server interface is independent of both the client and server implementations that use its facilities. Using object-oriented UML notation, the relationship between the client, server, and the basic interface components is illustrated below.

csidetail.png

This model can be further simplified in terms of dependencies as shown in the following illustration.

csi.png

The implication of this model is that the client and server implementations can vary independently of the interface. Indeed, it is possible to have many servers that provide the same interface within the same system. For example, assume that the interface defines the facilities of a serial port, and there are three different types of serial port hardware in a system. It is also the case that an interface might be implemented differently on different target platforms, but the source code for the interface is shared.

As a result, it is desirable to locate the source code for the interface in a directory other than the client and server implementation directories.

Which brings us to the topic of complete interfaces. A complete interface implementation should contain the following elements:

The example files listed are taken from the OSCL USB Host stack. Notice the file naming conventions closely follow the terminology used in this article.

BTW, you may have noticed that I am a little over-zealous in my use of namespaces, but I have found that using namespaces this way helps me consider carefully how my code is organized, and helps guide me in design decisions. "Friends" have called this "namespace-hell". You won't need to worry about my macros conflicting with yours! Get over it. ;-)
Most of these elements should be obvious to you after reading this article (yeah right), with the exception of the RespMem, which I will discuss here.

The OSCL ITC Framework is designed to support active-object development for embedded systems. In case you haven't guessed, I am a bit of a fanatic about the use of general purpose dynamic memory allocation and freeing in the context of embedded systems. In the context of active-object development for embedded systems, this means that memory resources by active-objects must be managed explicitly.

This point-of-view is not as difficult to implement as it may sound with the right frame-of-mind and support toolset in hand. The OSCL ITC Framework is that kind of toolset, but you're on your own with the frame-of-mind.

Having said all of that, it is typical for an active object to preallocate asynchronous Response messages and accompanying Payload resources. Since these items a usually instantiated together, the RespMem element listed above declares memory blocks of the appropriate size for this purpose. This is done as a convenience for asynchronous clients of the interface, just as the SyncApi and concrete implementation of the SyncApi eliminate the need for individual clients to implement their own versions.

The RespMem header files make use of Oscl::Memory::AlignedBlock template to reserve memory in struct constructs. This template is defined in the file oscl/memory/block.h. The OsclCacheAlignMacroPre() and OsclCacheAlignMacroPost() macros (yuk) are a lame attempt to encapsulate compiler specific details for aligning data structures on a processor specific cache-line size. While this may seem wasteful or superfluous, it is quite useful for systems programming where cache alignment not only improves performance, but is also critical when cache coherency must be enforced by the system software. Ultimately, I would like to see alignment adressed by the C++ standards commitee. I would also like to refactor the Oscl::Memory::AlignedBlock functionality, but for now this will do.

Contents