Sunday, October 23, 2011

Exceptional conditions: adding exceptions in standard C

An important aspect of programming is error handling. A program is running, all is well, and then ... oh no! All of a sudden a condition occurs that was not supposed to happen, or at least the programmer wished it would not happen. A program usually checks the most common errors and may retry, work around, or simply abort the operation depending on how hard to resolve this error is.

There are software error conditions and there are hardware errors. Hardware errors are represented by software error codes. There are different ways in which an error condition is given to an application when it comes to programming:
  • error return value from a function
  • library reports error: in standard C, check errno
  • UNIX signal received
  • an exception was thrown or raised
Easiest to understand and use is the first one; if the return value of a function has a certain value (error code), then it signifies an error and the application should act accordingly. The application programmer himself must choose what error codes to use for error conditions.

The second case describes how the standard C library reports errors; the library functions return zero on success and -1 on error. To get more information about what error occurred, examine the error code in errno. Note, errno is not a normal variable but a function that returns a thread-safe errno value. All errno values are predefined by the operating system. The errno values are (either translated or directly propagated) return codes from the operating system's system calls.

UNIX signals may be sent by the (UNIX) operating system to signify certain conditions. These conditions vary from SIGALRM (a timer expired) to hard errors like SIGSEGV (segment violation, which is illegal memory access) and SIGBUS (bus error). Signals are handled by the process itself, but the signal handler is run in a different context. This means that the normal program flow is interrupted and continues after the signal handler has finished executing. A signal can even interrupt a system call, after which the system call will report the errno value EINTR (system call was interrupted). Signal handlers may be hooked by the application, but an application can not define its own signal numbers. The signal numbers are predefined by the operating system.

Exceptions are exceptional conditions that may be thrown or raised. An application may catch an exception, in which it will resume operation at the point where it first tried to do the operation. Because it involves stack unwinding and jumping through code, exceptions generally require special language support. Moreover, exceptions generally have a specific syntax in the form of try { ... } catch(Exception) { ... } or try: ... except Exception: .... Exceptions are a key aspect of the Java and Python programming languages, in which it is common use to throw exceptions for error conditions. In C++ exceptions exist but it is more left to the programmer whether to use them extensively or stick with error codes. In Objective-C exceptions exist but they are not commonly used.

Exceptions do not exist in standard C, but I thought it would be fun to add them. How do you add a language feature that is completely absent from C? Well, you can emulate them. In fact, I stole this neat idea from Objective-C; in Objective-C the NSException is implemented using setjmp()/longjmp(). Without using any macros to define try and catch, I came up with the following:
if (!catchException(exception_number)) {
... try some code ...

throwException(exception_number, "descriptive message");

} else {
printf("caught exception! %s\n", caughtExceptionMsg());
}
endException();
In this code, catchException() really sets up a try block. What it does behind the screens is creating an Exception object containing a jmp_buf and pushing it onto an exception watching stack. The code that actually catches the Exception is really in throwException(), which examines the stack to see if we want to catch the thrown exception at all. When it finds the corresponding Exception object, it cleans up the stack and jumps back to the initial starting point of the try block. If the exception is not being caught, print a message about the uncaught exception and abort the program.
If the exception does not occur, you are left with an object on the exception watching stack, which is why you need to explicitly call endException() to clean up the stack. Other languages do this implicitly.

This way we have added exceptions to standard C. There is a huge caveat to using exceptions correctly: as your program is able to jump back and forth through large pieces of code, you have to be extra careful not to leak memory. You can't have everything, but if you have something like an AutoReleasePool then this may help a great deal.

Sunday, September 4, 2011

Bytecode interpreters, virtual machines, emulators

Lately I've been working on programming a utility that translates more or less natural text to more cryptic firewall statements. In the translation process, I use two passes: the first pass translates to bytecode, and the second pass translates from bytecode to the final output. A huge advantage of using the intermediate bytecode stage is that this makes it possible to easily support multiple kinds of firewalls while having only one syntax for the input. The code for the output generator is completely decoupled from the input parser code. Cross compilers work in the same way. Modern compilers like gcc also work in a different way; they support multiple frontends for compiling different programming languages.

When I was still a student, I once wrote an assembler/disassembler for a nonexistent architecture. While a nonexistent architecture may seem an odd choice, I was inspired by the Java bytecode that executes in a virtual machine rather than on a real CPU. The professor did not give me a straight A only because I had not actually written the virtual machine that would run the code. The instruction set was rather extensive and implementing the full virtual machine would have been too much work for the limited time of the assignment. The feeling of what if always stuck with me however.

An emulated CPU has the following properties:
  • a bunch of general purpose registers
  • a program counter (this is just an address; the instruction pointer)
  • a stack pointer
  • a flags register (with a zero, sign, carry, overflow flag)
  • optionally: interrupt flag or current interrupt level
  • optionally: supervisor mode flag or current privilege level
Emulated interrupts enable you to let the system interact with I/O devices much like it happens in real computers. Whenever an I/O device is ready, it will interrupt the CPU, which will then automatically jump to the Interrupt Service Routine (ISR). The address of the ISR is read from an interrupt vector table that typically resides at a low memory address.
The supervisor mode or privilege levels offer the possibilities of implementing a sturdy “operating system” in the virtual machine, adding a hypervisor, and ultimately having virtual machines running in virtual machines.

The instruction set needs to have load, store, arithmetic operations like add, subtract, multiply and divide, logical operations like and, or, exclusive or, and bitwise operations like bit shifting and possibly bit rotation. Furthermore you need a jump (goto) instruction and a set of instructions for conditional branching, and push/pop to work with the stack. Lastly you could add some privileged instructions like loading the flags register or resetting the machine. At the bare minimum, there are about 25 instructions to be implemented. By comparison, the 8086 CPU has about 75 different instructions.

For a memory model, 64K ought to be enough for anybody ... Or you could give the system very little real memory and implement paging and swapping. Implementation wise, the virtual memory management could take place in either the guest or the host ... (when implemented in the host, the guest OS would never know its memory was being swapped in and out!)
A related issue is protected memory: can the current process write to a given address or not? Early micro-computers did not have support for paging, but they did have read-only memory in the form of ROM. You probably want to have memory mapped I/O, an interrupt vector table and some display memory representing the screen.

One of the problems I've always had with this model is that programming for such an emulated system is hell as you would need to write everything in its assembly language. To overcome this problem, you would really need to make a high level compiler generate the code. Nowadays we have gcc and if you're handy it should be possible to have it generate code for platform X.

Now let us take a step back and get back to bytecode interpreters. Java, Perl, PHP, Python, various kinds of BASIC and even some MUD codes all use a stack machine at the heart of their bytecode interpreters. The stack machine is the simplest kind of processor: it has no registers and its instructions only manipulate a stack. The lack of registers make both compilation and execution (or emulation) easy. Interpreted languages benefit from bytecode because interpreting bytecode is faster than having to go through the language parsing procedures all the time.

A bytecode interpreter for a scripting language is quite different from a full blown system emulator. For a bytecode interpreter, you can make up your own opcodes for any common operation you like. There is no need for an opcode to perform only low level operations; they can be high level operations just the same. For example, Python has opcodes for slicing strings. Until Python 3, print was a statement with an opcode equivalent rather than being a function. It's not cheating, it increases performance.

It's good fun designing your own bytecode interpreting virtual machine. There are a lot design of choices to be made beforehand. Do you want to fully emulate a CPU or not? Maybe you want to emulate any other hardware components? Will you write anything like a system BIOS in bytecode? Are you going to develop a self-hosting system? How far are you willing to take it?

Wednesday, August 3, 2011

Lion: Yet Another Review

Cheerios, finally a new blog post after a long while. Haven't I been programming a lot lately? Well, yes and no. I've been working real hard on synctool, which is a sysadmin tool written in Python for doing software configuration management on clusters of computers. In github the development branch is now something like 180 commits ahead of the stable branch. After which I got the flu and after that I was on a well deserved long vacation. Just when I got back home, Apple released Mac OS X Lion so I had some interesting upgrading to do. In the past, I sometimes blogged about Ubuntu (Linux) upgrades, nowadays “I'm a mac” (sorry — btw, still doing lots of things with Linux at work) so I'll write about my experiences with the Lion.

Surprise surprise
Upgrading to Lion is a breeze. Just buy it from the App Store, download the program and off you go. After an hour or so you are now running Mac OS X Lion. It's as easy as that. But wait, as a sysadmin, there are a few things here that are making me feel uneasy.

I got Lion from the App Store, so I have no CD-ROM to install the system from if my system ever breaks. Apple solved this partially by including a system restore partition on your hard drive. Eww. Uhm. Well ... OK. I guess..?

Apparently there is a way to create a Lion install CD-ROM but Apple does not tell you how. It is (apparently) reserved to “power users” (or should I say “hackers”?). Doing so is not easy especially because the Lion installer magically disappears from your hard drive after the upgrade is done. After downloading the 4 gig or so installer I had to download it again to upgrade my laptop. This is not such a nice thing for Apple to do.

Upgrading my laptop took a bit more work. It's an older model white macbook with only 1 gig of memory. Lion only works on systems with 2 gigs of memory or more, so I had to do a small hardware upgrade first. I can't really explain, but Lion uses a ton of memory even though the running apps do not show big memory footprints in Activity Monitor.

Gimme gimme new features
Lion offers a number of new things. There isn't an awful lot, but then again, it was only 29 dollars or something. Some of those things were good, and some of those were bad. I love my Mac enough to blog about it and I do like Lion but grrrrrowls ... I'll give you the bad first.

Ironically most of Lion's biggest selling points were pretty useless to me. Honestly, it's mostly marketing hype. Here's why: my main system is a 27 inch iMac. Gimmicks like Launchpad and fullscreen Mail are nice on a laptop, but they are not useful (just plain awful) on a 27 inch screen. Lion's features are mostly ideal for laptops but not for desktop Macs.
  • new UI. Really? Yeah, but you have to look super hard to notice. And then when you do notice, it annoys the crap out of you because it does not look better than Leopard. Except for the squared buttons, which looks more like Microsoft Windows?
  • full screen apps. Great feature, but on large displays it is not useful. You just drown in this amazingly large screen. Which is kind of fun actually, because a regular PC never does that to me.
  • 3 column layout for Mail. Oh wow. I hate it. It's a cheap Outlook imitation if you ask me. And it's ugly.
  • Launchpad. A big screen full of icons. Great. Sigh. I will never use it.
  • new trackpad gestures. Yeah, I do have a trackpad with my iMac. I'm just not comfortable with four and five finger gestures, rotating your hand, etc. For photo editing, I use a mouse (!)
  • Mission Control. Where did Expose go??
  • Dashboard is awful on a large display. It was nice in Leopard, the screen would fade out to darkness and your widgets would appear. You would click next to a widget in the void and the whole thing would zoom out and you would return to your desktop. In Lion, the whole desktop slides offscreen to the right (a dazzling animation that gives you a headache) and you are presented with a million (really, a million!) tiny knobs that are some kind of Lego base plate, and you can't even change that annoying background without hacking into your system library folder (!!!)
  • AirDrop. Maybe Lion's coolest feature, but it doesn't work with my old macbook. I don't even blame Apple for this because it is an older model and the WiFi chip in this macbook does not have the needed functionality, but as said, AirDrop is unfortunately useless to me.
  • FileVault now has whole disk encryption. To a lot of people, this feature came like five years too late. On the other hand, this feature is arguably useless to everyone. It enables you to encrypt even your system files, files that are identical on any Lion installation. Moreover, even though Apple denies it, FileVault makes your system noticeably slower.
Apps that broke:
  • PowerPC apps simply don't work anymore. Apple removed the brilliant Rosetta software. I say brilliant because it allowed me to play WarCraft 3 (for PowerMac) on my intel Leopard system flawlessly.
  • TrueCrypt / MacFUSE. I found a website that offered up-to-date MacFUSE software that fixed the problem. But it was not on the official MacFUSE website. Odd. Very odd. But it really does work now.
  • Some folks say that Spaces is broken in Lion because Apple changed it. I don't use Spaces but looking at Mission Control, I believe them.
  • Printing from Google Chrome crashes the app. Of course, it's all Google's fault and you should use Safari. But I'm pretty sure that I could print from the Chrome browser before.
  • Lion removed my compilers and did so even without asking. gcc, clang, make, all gone. Insane! Apple decided that thou shalt use Xcode 4 on a Lion system. It's free, and thou shalt download the 4 gig Xcode 4 installer from the App Store and you are not given any option to install only the command-line tools. So I spent some additional hours to get my programming environment back in order again.

The Good Stuff
So, is Lion all useless? No, here's what I do like about it:
  • More system programs are 64-bits binaries.
  • The OS kernel runs in 64-bits mode now, which is faster than 32-bits mode on modern CPUs.
  • ASLR has now been implemented properly or so they say. Address randomization is important for security; it helps prevent system crackers to gain root access by smashing the stack. I find this to be a very important feature because I do online banking with my system, and who doesn't, nowadays.
  • The price is fair, even for a guy like me who has been spoiled rotten for years with Linux and GNU where software is typically free (as in beer — yes, RMS says you can make money from it but everyone is getting it for free anyway. But wait, isn't that exactly the same in the Windows world? Hmmm).
  • The arrows on the scroll bars are gone. I'm not too crazy about the new scroll bars, but you have to admit that no one was seriously clicking those arrows anymore and removing them is a bold move. No doubt Ubuntu and other Linuxes will follow this example, as will Microsoft.

I Still Love You
Despite my criticism on Lion I have to say that I'm still very much in love with the Mac OS. It just works. I can't put it any other way. I love working with it. I love programming for it. I love its strangely brilliant Objective-C. I love digging in the docs of its Objective-C API. I love its brilliant BSD UNIX that is its core. I love that you can sit down and get some work done rather than having to click away popup after popup as your system is begging for attention because it needs you to be a sysadmin night after night. I love that OS upgrades do not totally break your system and that you do not have to spend a full weekend on hacking away in it in a futile attempt to fix it. I love how you can copy gigabyte files around and the whole desktop remains responsive. I love how my old white macbook runs the latest Mac OS X smoothly and without feeling sluggish at all. I love the finger scroll with inertia on the Magic Mouse that seems to ‘just know’ where you want to scroll to. I love the beautiful screen fonts. They are not ugly like on other platforms. And I love how the Dashboard worked in Leopard. No other OS in the world implemented widgets in this way and it was done exactly right. And I love Spotlight. Spotlight has to be the only desktop search tool that does not grind on your hard drive as it is rebuilding an index every single day from a daily cron job.

I could go on and on. There are few things in Mac OS that I do not like. The Finder does not behave like Windows Explorer — but then again, it is not a Windows application. The default settings for PageUp and PageDown in the Terminal and Xcode editor appear broken as they do not react intuitively. Launchpad is rubbish. They messed with my favorite app, the Dashboard.
Other than that, the Mac is still insanely great.

Update: In System Preferences|Mission Control, uncheck “Show Dashboard as a space” to get the old Dashboard behavior back.

Sunday, May 8, 2011

Quaternion versus Matrix performance

When doing 3D graphics programming, you will be dealing with vertices, vectors, translations and rotations. OpenGL will happily do the translations and rotations for you, but in some cases you will want to do the math by yourself anyway. For example, I like keeping the orientation of an object around so I can rotate it whenever I like (like in an animation or game loop or heartbeat routine). At that point, OpenGL is not involved. Later, a drawing routine is invoked that calls OpenGL to do the necessary rendering to display.

OpenGL uses matrices to represent 3D space in memory, so it makes sense to store the orientation of the object in a matrix as well. The 3D space is actually represented in a 4x4 matrix, which is generally written as an array of 16 floats. Now, there are some gotchas like the column major format to layout the matrix in memory and the right-handedness rule, but once you got that right, all the drawing routine really has to do call glMultMatrix() on your 'matrix' array of float values, and the object will (hopefully, if you got everything else right as well) appear under the desired angles. That's easy.
Multiplying matrices together to make combined rotations is not an easy task and takes 4x16 = 64 floating point multiply operations! There are 4x12 = 48 add/subtract operations as well, but I assume that the multiplications have the worst impact on performance. If you want to do a rotate in a glRotate-style you will have to setup the matrix first, which adds another 24 multiply operations in the worst case, without counting the multiplications and the sqrt() call needed to normalize the vector.

There is another way of storing orientation, and it's the quaternion. This is something like a vector in complex 4D space and consists of "something like" a <x,y,z> vector and an additional w component. What, only 4 values? Yup, that's all. The memory footprint of a quaternion is really small compared to that of a matrix. (By the way, this is a non-issue to me because modern computers have plenty of memory — even the mobile devices do. But maybe you have some whack project in which you want keep tons of different orientations and memory becomes a problem). Because there are only 4 values, initializing a quaternion is dirt cheap in terms of CPU usage. Multiplying quaternions is also relatively cheap with only 16 floating point multiply operations. There are 12 add/subtract operations as well, but I assume that the multiplications have the worst impact on performance. Again, not counting the operations needed to normalize the rotation vector.
So, are quaternions the golden egg? Well, yes and no. Yes, they are great, but the main drawback is that OpenGL works with matrices. Converting the quaternion back to a matrix costs 27 multiplies.

In my book (I keep a little black book to pen down these kinds of numbers) 16+27 = 43 is still less than the 88 that matrices cost. However, there is a special case where matrices will still be faster. The trick is that when working with matrices, initially, you will have the identity matrix. Since multiplying the identity matrix with another matrix equals that other matrix (check this yourself, it's fun ...), you can greatly optimize the first matrix rotation, as it requires no multiply at all. This requires that you keep a flag on the matrix saying that it is identity. Or you can make a separate routine that simply initializes the matrix in its first rotated state. It makes for an embarrassingly fast rotate call, especially if you were going to do just one rotation of the object.
Of course, this is cheating. You can cheat in a similar way with quaternions, saving an extracted copy of its corresponding matrix and flagging it as dirty whenever it needs to be updated. Just keep in mind that if you rotate the object all the time, you will have to extract the matrix for use with OpenGL all the time.

I want to end this post with a couple of remarks:
  1. Quaternions are apparently terrific for combined rotations. If you hardly do combined rotations, matrices will be faster. If you do combined rotations all the time (like for animating skeletons and such) then you probably already knew that quaternions are the way to go.
  2. Quaternions produce less floating point drift than matrices, because they do less multiply operations than when multiplying matrices. They do drift however, and don't let anybody tell you that they don't.
  3. In my post I made a remark about modern computers having enough memory ("640K ought be enough for anybody ..."). The same goes for CPU power, really. However, on mobile devices it probably does pay off to investigate app performance not only because of the less powerful CPU, but also because of battery power consumption.
  4. I got to writing this blog entry because I spent a day wondering why my matrix rotation around an arbitrary axis gave weird results. The quaternion code did work, until I passed in a vector that was not normalized and it displayed the exact same weird result! That was an eye-opener. After normalizing said vector, the matrix code gave just as good results.
  5. Over a year ago, when I wrote in my blog about quaternions for the first time, I made a remark that NeHe's code has a sign wrong somehow. To my surprise, my model was rotating clockwise using my own quaternion code. I fixed it to have it rotate anti-clockwise. Either I got the matrix column major layout wrong before, or my other project was working with different axis. Anyway, NeHe's quaternion code is probably alright after all. I didn't use it. By the way, I saw wikipedia too now shows code examples for quaternions.