Tolga Ceylan's Linux, C/C++ Blog

Parallax Ping))) has a simple protocol that requires only one connection for both request and response. The request is a pulse of 2-5 usecs, while the response pulse length is the distance measured.

On Linux, this is tricky.

First, in user space, it is difficult to get the scheduler predictability right. This might be minimized by running the application thread in one of the real time schedulers (SCHED_FIFO, SCHED_RR) and also augment this with rt-linux kernel patches or at least increasing the linux kernel preempt level. However, even in high spec machines these tricks do not guarantee latency below 10 usec. In other words, it's possible for the process to get swapped out in the middle of these measurements only to get scheduled back again after x usecs (or even msecs without rt-linux.)

Second, even in kernel space, the interrupt latency is too great to accurately measure these results. I think these issues could perhaps be overcome by approximations via multiple measurements, estimating interrupt latency, handling the interrupt in top-halves, or perhaps registering this interrupt at a higher priority then others. There are some opportunities to investigate and experiment in kernel space.

Beaglebone Black provides two PRU units at 200Mhz giving us 5 usec instructions. These processing units are specifically designed to provide predictable instruction latency. In other words, they are hard real time.

One important gotcha is the fact that Beaglebone Black digital pins use 3.3 volts while Parallax Ping)) operates higher at 5.0 volts. I've overcome this difficulty by using a cheap bi-directional level shifter. This is important since 5.0 volts can fry beaglebone black ports or if you are unlucky the beaglebone black itself. :-(

Also on Linux, it's not very quick to swap I/O mode (input to/from output) on GPIO. Especially on user-space, this requires expensive sysfs operations. On PRU, I have not investigated this. Instead, I've split the Ping)) I/O pin into two via resistor and used two I/O pins directly accessible from PRU.

As usual, first step is to get the device tree blob right. I've hacked one of the BB-BONE-PRU dts files and added my I/O pins there and enabled this on the cape manager.

For PRU coding, you have two basic options:

1) Use Texas Instruments IDE / compiler / tools and code it in C.

2) Use pruss compiler from TI, but code in Assembly.

Since my task at hand was simple, I chose Assembly. Also I did not want to use another IDE. I'm really happy with sublime text and if not, good old vi. The PRU instruction set is limited to about 40 instructions, so assembly coding was actually easier than I thought.

This whole process took some days to learn and experiment. But an incredibly rewarding experience. With its reasonable price tag, Beaglebone Black is hackers dream come true.

http://www.tutorialspoint.com/cplusplus/cpp_exceptions_handling.htm

In most production systems we end up with a slightly(!) more instrumented exception strategy. We see exception class hierarchies or error handling code that catches these exceptions just to add more instrumentation at various levels. 

These strategies start to break down in complex systems that need high and predictable performance while processing high number of tasks. Some examples of such processing are network proxies, web servers, graphics rendering, etc. 

We can conceptualize typical processing in these applications as:

pushing a vector of tasks to a pipeline to get results

For example, for a network proxy software we are looking at thousands of incoming/outgoing connections, DNS queries, file system accesses, etc. 

An example of a poorly designed typical object oriented software may look like this:

for(size_t idx = 0; idx < total_pending_IO; ++idx) { connection = pending[idx]; try { if (connection.isRead()) connection.onRead(); if (connection.isWrite()) connection.onWrite(); if (connection.isError()) connection.onError(); } catch (connectionException &exp) { connection.onException(exp); }

Notice how exceptions are starting to dictate I/O patterns here because they are essentially global objects. Spreading the calls into threads or asynchronous callbacks require extra care and we must make sure onException() handler itself must not throw. Perhaps it's a bit safer to save the exception and then call it outside of catch() block in this case (convert it into error code basically.) 

Notice above how an exception in onRead() will bypass onWrite() and onError(). Did we really intend to do this? Do we need multiple try/catch blocks?

Regardless, the style above is undesirable.

In a proxy example like this, it's not the responsibility of low level connection code to decide if a condition warrants an actual exception. Only higher levels of the software stack can make that call.

An alternative approach without exceptions is like this:

// partition/split pending I/O into read/write/error vectors splitIO(pending, r_vec, w_vec, e_vec); handleReads(r_vec, status_vec); handleWrites(w_vec, status_vec); handleErrors(e_vec, status_vec); // calls above store error conditions in status_vec handleExceptions(status_vec);

The service was a success. It was rock solid and we could brag about up-time of months. Maybe years...

For event handling, we used boost::asio. For cost effective I/O handling, asynchronous I/O using minimal number of threads is the way to go. If you are blocked and waiting on I/O, there's absolutely no reason to spawn threads to wait on it. Popular examples of such services are nginx, haproxy, nodejs, etc. All employing very similar principles.

The single threaded processing works until the system call and processing overhead on the CPU core starts to peak and saturate that core. In other words, you can only execute X number of system calls (and CPU bound calculations) per second on a single core. But a lot of times, it is possible (and simpler) to run another copy of your application on a different TCP/UDP port utilizing more CPU cores.

This effective strategy avoids multithreading as much as possible since synchronization overhead is very undesirable. Minimizing threads also keeps the code much simpler and robust. Another way to look at this is to accept the fact that the more locks you have, the less effective your I/O strategy is. True parallelism is only achieved when you actually don't have locks that stall your processing. 

A similar analogy is using shared pointers. You are probably (hopefully) using shared pointers not because they are very good and awesome, but because you have actually failed (or unable to because you are using boost::asio) to establish robust ownership policy across the code.

There are variety of libraries that offer asynchronous I/O. Besides boost::asio, there is also libevent, libev, libuv, etc. However looking back, now I would have not used any of these libraries at all.

This is because with Linux epoll and Linux timer file descriptors, you really have no reason to use these libraries. Rolling out your own poller with your custom code is trivial and it will out-perform them.

In fact, that is what I'm working on these days. Having tight control over the lower level details and the poller (event code) itself, I've also managed to ditch shared pointers. I cannot stress enough how liberating this is. Now I can establish strong ownership policies across my code and make sure the event handling code does not survive any of stored raw pointer life times. I was also able to minimize calls to malloc/free/new/delete and tightly pack my data in a more cache efficient manner. (Sure, you can also do this using allocators for shared pointers.)

Focusing on low level details, I also successfully avoided boost::function or std::function variants. This avoids behind the scenes memory allocations and copying. Basically old school function callbacks may not look syntactically the best at first, but they perform better than these heavy weight alternatives.

More importantly, I can now control these simple callback functions better. This is essentially same thing as deciding which virtual function is called at run time. Basically instead of using object hierarchy and inheritance, I'm using a small family of callbacks to handle each type. This keeps the code base small since I don't have to write a number of unnecessary classes and their implementation.

I cringe looking at this. A great example of object oriented (OO) programming overuse. But it also violates OO principles. Is Foo really a thread? Is this really an is-a relationship? Isn't this approach also likely to introduce multiple inheritance to the code base?

What if I simply want to spawn multiple threads in Foo to process a series of data? Even boost::thread and std::thread use a simpler approach and take a function as argument instead of this inheritance non-sense. And look, pthreads take a function argument too.. That's it... 

Why corner yourself into such a situation?

How did our industry really fell for all this?

From best seller design pattern (DP) books to basic recruiter questions about OO programming/design to job descriptions requiring OO programming skills in terms of number of years of experience... 

Did this happen because programmers failed to write good code and this OO/DP was a a response to control and contain the damage? I don't know...

Whatever it is, I think it's time to wake up and remember the basics:

What is your data? What are you processing here?

What is the type/frequency/probability of your data?

When memory allocation patterns are known in advance, rolling out your own memory pool/allocator may be a good solution. Recently, I needed a data structure as well as a memory pool for the following requirements:

Fast memory pool for fixed size objects

Access these objects with an integer index key

Given an object fetch its integer key

Walk a list of currently allocated objects

Typically I would have used a hash table and a memory pool where I'd include the key inside the object itself. But I wanted to investigate if I could provide all this functionality with a custom memory pool.

template<typename T> struct Pool { struct Item { T data; int flags; IListNode node; }; IList freeList; IList allocList; size_t poolSize; Item *items; bool initialize(int size); void shutdown(); T *allocate(); void deallocate(T *&obj); int getIndex(T *obj); T *getObj(int index); };

Pool provides initialize(), shutdown(), allocate(), deallocate(), getIndex(), getObj() methods for the requirements above, where IList is a simple intrusive list:

struct IListNode {

IListNode *prev; IListNode *next; }; struct IList { IListNode root; void prepend(IListNode *node) { link_ilist_node( node, &root, root.next); } void append(IListNode *node) { link_ilist_node( node, root.prev, &root); } void remove(IListNode *node) { unlink_ilist_node(node); } }; void unlink_ilist_node(IListNode *node) { node->next->prev = node->prev; node->prev->next = node->next; node->next = 0; node->prev = 0; } void link_ilist_node(IListNode *node, IListNode *prev, IListNode *next) { node->next = next; node->prev = prev; next->prev = node; prev->next = node; }

The implementation of Pool is also very simple. By decoupling free/allocated list (intrusive lists) from actual memory allocation / object construction, we can easily keep this code exception safe as well:

  bool initialize(int size) { assert(size>0); if (items) return false; // already-initialized items = static_cast<Item*>( malloc( sizeof(Item)*size) ); if (!items) return false; // out of mem poolSize = size; freeList.clear(); allocList.clear(); for (int idx = 0; idx < size; ++idx) { freeList.append( &(items[idx].node) ); items[idx].flags = FLAGS_FREE; } } T *allocate() { if (freeList.empty()) return false; // out of memory Item *item = fetch_base<Item,IListNode>(freeList.root.next, offsetof(Item,node); assert(item); assert(item->flags == FLAGS_FREE); T *obj = new(&(item->data)) T(); assert( obj == &(item->data)); item->flags = FLAGS_ALLOC; freeList.remove( &(item->node) ); allocList.append( &(item->node) ); return obj; } void deallocate(T *&obj) { Item *item = fetch_base<Item,T>(obj,offsetof(Item,data)); assert(item); assert(item->flags == FLAGS_ALLOC); obj->~T(); obj = 0; item->flags = FLAGS_FREE; allocList.remove( &(item->node)); freeList.prepend( &item->node)); }

This code not only catches double delete or invalid pointer delete, but it also has some basic buffer overrun checks using 'flags'. This could be expanded to include more stats/counters and more sophisticated canary values for stricter buffer overrun checks.

One important, but elusive trick is to 'prepend' to the freelist in deallocate(). This is important, because we'd like to put such cache hot items in front of our free list. The impact of this small change was visible in my performance tests.

Another variation to this pool is to add a boundary marker to keep track of how much of the pool is used. Using this, we can avoid the big for-loop in initialize() and instead gradually add more items to circulation.

After some time, I was able to achieve acceptable performance out of this framework. In one part of this code, I was using abort() as recommended by Bottle framework. In this case, this was to flag some backend failure such as a DB issue. Interestingly when I completely disabled most of the code and just issued an abort() things started to look grim. Mind you, this test code was merely an abort for all queries. It should have the best performance, since it does nothing.

Well, it turns out Bottle module raised python exceptions and did a ton of work under the hood for 'abort'. Instead of calling abort(), I switched to setting the error code inside the response object in Bottle.

Sure enough, after this change, we were back to good performance... 

Moral of this story is, when you can return an error value, please do so.. Most of the time, it is simpler and has predictable performance...

We must first understand that OpenSSL is used all over the internet and this includes connections that stream massive amounts of data. We all remember the days when SSL performance was too much for many web sites and it took internet a long time to embrace SSL. Most of the e-mail services did not have this turned on for a long time. Therefore performance is not something we can ignore for OpenSSL case. It differs in use cases compared to OpenSSH.

Having said this, a very common technique in low level network code is to use memory pools since dynamic memory allocation is a major drag on performance. Allocating fixed sized chunks, allocating a pool of such chunks, and/or caching in them in arrays, lists, etc. is extremely common.

OpenSSL followed a similar approach and cached previous allocations in a linked list. 

According to critics, this was wrong. The memory should have been released/allocated every time. Which would have unmasked the issue.

Although the issue would have been discovered on some platforms, I think OpenSSL caching scheme is completely sane (well except for the bugs in it.)

At one end of the spectrum, I've encountered high performance / embedded environments where performance has to be predictable and due to this exceptions and RTTI are disabled throughout the project. This results in not being able to use STL which is likely to be not important for such projects/teams. This also introduces additional states for constructors/destructors which were being managed by the compiler under the hood before. The end result is C++ code that resembles C. Not that this is a bad thing.

If you are in the industry, you'll most likely to encounter teams/projects that do not disable exceptions or RTTI. This means under the hood, the compiler is already handling exceptions and generating code for it. When I checked my own development environment, the compiler seemed to be using zero-cost approach. This means, at run time, there's "minimal" cost of exceptions as long as you do not throw them.

However, using exceptions did result in larger code base for a simple test case that I put together for this purpose. The compiler in my case was clever enough to detect the usage of exceptions and generated code when they were used. 

When I compared two code samples, the code that has explicit error handling in it performed actually slightly worse. This is not that interesting because any additional error handling code in such an environment is extra on top of existing exception handling by compiler. For example;

int process( int value, int &error );  // typical error handling

int process( int value); // may throw

If both of these functions never encounter an error or exception, the second function runs faster in an environment where exceptions are already enabled for both functions.

However, once you do throw an exception, this predictable performance goes through the roof. In a pathological test case, with 1,000,000 iterations and an exception / error at every iteration, my test code took 7 seconds versus 0.09 seconds. You don't have to guess which one was slower. :-)

This is fine if you rarely throw an exception. After all, "exception" is self explanatory. No one should be abusing this feature. If your developers are highly skilled and they do understand exception safety (or if this is a non-issue for the project) and if the project is mostly high level code and if performance is not that critical when exceptions occur, then by all means please use exceptions. 

Perhaps the only advantage of using exceptions is that the users of this code cannot ignore them. But other than this, cleaner / less code argument, in my experience is not true. If you are handling them properly, you do end up with a lot of try/catch clauses as well as a hierarchy of exception classes. (As well as error codes inside the exception classes.) Where and when these propagate through the software stack is also scary. After all, under the hood, we know what exceptions are... They are worse than gotos, they are in fact gofroms.

The discussion ends when you descend lower in the software stack. For example, low level network code. But before this, let's look at STL itself. Here we have std::map::insert;

pair<iterator,bool> insert( const value_type &value );

This returns a boolean (AKA error code) and does not throw an exception if the item is already in the map. This is a good design because it is not up to std::map to decide if this situation is error or not. std::map cannot make assumptions about upper layers of the software stack.

Similarly, low level network code should not throw exceptions... For example, a TCP connect timeout. Should this be an exception? If you are a careful good library designer, the answer is no. You return an error code. Period... You do not know if the upper level application is a high throughput proxy or a web browser... 

Personally, since most of my projects already have exceptions enabled, I do use them. But for non-recoverable failures such as bad configuration file, out of memory, installation issue, etc. I do not catch them if I can get away with it. It's much nicer to end up with a core file / stack trace that precisely shows a developer's logical mistake when using std::vector::at() as opposed to printing "out of range" in a log file.. If I have to catch them (hint: threads) then I only catch my own exceptions where the origin/reason of the exception is crystal clear. 

When and how to crash a server is also an art form. The choice boils down to choosing between running a corrupt server that "seems" to be functioning and an immediate restart with crash info. Obviously if you inherit a project, I do not recommend 'crash' approach. Of course, this decision depends on the team, operations, requirements, etc. In my experience, each team/environment is unique with unique requirements...