07 Apr 08 Terrain rendering in Ada

A while ago I added another old project of mine to the projects page but I neglected to post about it.

The project is based on an old school project of mine from the university. It’s a terrain rendering engine written in Ada which was intended to be capable of handling very large terrains of very high detail, +/- 1 meter at the maximum zoom level if I recall correctly.

Since at the time the few OpenGL-bindings that existed for Ada were highly outdated and of varying quality I quickly decided I had to remedy the situation myself. It resulted in the AdaOpenGL project which to this very day, even though I haven’t updated it in over four years, still has a significant amount of downloads (according to SourceForge statistics). People have even tracked me down and called me personally about it, which was a first for me. For these very reasons I often have a guilty conscience for not bringing the project up to date. Two developers have offered to assist but neither of them every produced any releases.

After I had a viable OpenGL-binding I started on the terrain engine itself. As you might suspect I spent a lot of time on the binding and based on the little time I had left I decided to only implement a basic scene graph for the terrain engine. The idea was that someone else would pick up where I left off but as it turned out the company I did the project with never asked for my source code, which I found rather weird considering their initial enthusiasm.

I gave the project the name AdaTerrainEngine as I cannot recall what I initially named it. The data files belong to the company which I did the project with so I cannot release them. I don’t really remember how useful the source code is but at least it should provide a basic foundation for anyone who is doing OpenGL work in Ada.
The terrain engine is LGPL-licensed and AdaOpenGL is BSD-licensed.

P.S. I blatantly stole the design for the AdaOpenGL-site from an awesome CSS tutorial. After I finished the page I realized I forgot to credit the original author and I couldn’t find the site again. If you have any idea who did this please let me know! D.S.

14 Mar 08 Threadable C++ objects

I maintain a couple of objects at work which implement various behavior that requires a separate thread of execution. Since recently there were really only two of them but now they have multiplied beyond that so I realized that it would be appropriate to design a reusable framework in order to reduce unnecessary code duplication. The design I came up with is based around an interface which defines the API of any “threadable” object and an abstract implementation which provides the means to synchronize the threads. Threads in our systems tend to have a very long life span and we avoid any kind of resource allocation (including launching threads) which are soon thereafter released as that can lead to fragmentation.

Although I’m fairly satisfied with this implementation there is at least one flaw in it. I’ll leave it to my readers to find it.

The interface is fairly simple and provides three methods. kill() which is used to signal thread termination, running() which is used to query whether the thread is actually up and running and finally the actual thread function implemented as operator()().

class IThreadable {
public:
    virtual ~IThreadable() throw() { }

    virtual void kill() = 0;
    virtual bool running() const = 0;
    virtual void operator()() throw() = 0;
};

The AbstractThreadable object implements the kill() and running() methods which should look the same across all kinds of threadable objects. It also implements two protected methods which must be called in the threadable object to signal that it has enter or exited its thread function, these are known as signalThreadRunning() and signalThreadExit().

I’m using a tristate variable to keep track of the threads current state of execution. The reason behind this is that I want to differentiate between a thread that has not yet been started. If someone calls kill() and never actually launches the thread the kill() method will block on the semaphore unless we can detect this state.

enum ThreadState {
    ThreadState_NONE,
    ThreadState_RUNNING,
    ThreadState_KILLED,
};

class AbstractThreadable : public IThreadable {
public:
    AbstractThreadable() : m_state(ThreadState_NONE) { }

    virtual void kill() {
        scoped_lock stateLock(m_stateMutex);
        if (m_state != ThreadState_KILLED) {
            ThreadState prevState(m_state);
            m_state = ThreadState_KILLED;
            stateLock.unlock();
            if (prevState == ThreadState_RUNNING) {
                m_threadExitSemaphore.p();
            }
        }
    }

    virtual bool running() const {
        if (scoped_lock(m_stateMutex), m_state != ThreadState_KILLED) {
            return true;
        }
        return false;
    }

    virtual void operator()() throw() = 0;

protected:
    virtual void signalThreadEnter() {
        scoped_lock stateLock(m_stateMutex);
        m_state = ThreadState_RUNNING;
    }

    virtual void signalThreadExit() {
        m_threadExitSemaphore.v();
    }

private:
    ThreadState m_state
    mutable mutex m_stateMutex;
    semaphore m_threadExitSemaphore;
};

Finally I will present a simple object using the above implementation in order to implement a threadable object which just sleeps until someone signals it to terminate via kill(). Notice how signalThreadRunning() and signalThreadExit() are used in order to notify the AbstractThreadable implementation of the current thread state.
Note: Calling running() requires locking a mutex so if the thread loop is very tight it might be wise to unroll it.

class Sleeper : public AbstractThreadable {
public:
    void operator()() throw() {
        signalThreadEnter();
        while (running()) {
            sleep(1);
        }
        signalThreadExit();
    }
};

This is a simple example showing how to use the sleeper thread. I’m using Boost to create the thread. thread is a thread object and ref makes sure the sleeper object is passed by ref rather than being copied.

int main(int argc, char **argv)
{
    Sleeper sleeper;
    thread sleeperThread(ref(sleeper));
    ...
    sleeper.kill();
    return sleeperThread.join();
}

29 Feb 08 sed stupidity or ampersand magic?

We were reformatting some code at work the other day using find and sed and stumbled upon a very weird case when using the ampersand (&) character. We accidentally expanded all boolean and expressions in our C++-code (&&) to “& &” when applying a rule to modify “<type> & <variable>” to “<type>& <variable>”. In order to change them back we ran a “find . -type f | xargs sed -i -e ’s:& &:&&:g’” which resulted in all the expression becoming “& && &”?!

After some fiddling around it turns out the ampersands in the resulting string had to be escaped to reach the desired result. As far as I know ampersands are not part of the regular expression syntax and I’ve never before had to escape anything in the resulting string.

In the end the following syntax yielded the correct result.

echo " & & " | sed -e 's:& &:\&\&:g'

 &&

I don’t know if this is a bug or feature and if anyone else does please let me know.

21 Feb 08 “Kristian’s Model”

We’ve been confronted with the problem of working with a poorly documented API at work, again. The samples are overly complex and the simplest to the most advanced still link with and use functions from the same files making it very difficult to figure out what each individual part of it actually does and why it’s needed. I’ve had to deal with this issue before but this time around it’s definitely worse. In order to break down this API we have decided to apply a method known as “Kristian’s Model” which allows you to quickly gain an understanding to complex samples.

Kristian’s Model is a five step process which I will try to explain below. The original author has requested to remain anonymous.

1. Design comp.sh

If the existing build system is working against you quickly have it replaced by a simple build script that will compile exactly the application which you are trying to break down .. no more, no less. I like GNU Make as much as the next guy but when developers have too much spare time they have a tendency to abuse the more powerful features of GNU Make in order to concoct Makefiles which are almost more difficult to understand than the application itself. By running a make -n <target> you’ll quickly and painfully be able to extract the necessary commands to build your target. Put these commands into comp.sh and prune them when you need to.

2. Replace function calls with their actual code

Now that the build system is out of the way we can move on to the more interesting part, the actual code.

Breaking up large functions into smaller parts and putting these parts into functions with descriptive names is a very important quality to have in a programmer but sadly this seems to be somewhat of a lost art in the world of API-developers using C. It’s not at all uncommon to see functions spanning pages upon pages of unrelated code which would be a prime candidate for being broken up in any sane developers mind. An example from one of the simpler (!) samples I have to work with is a main function which spans a whopping 1150 lines. It’s bad enough to see this in a regular application but seeing it in a sample application which is meant to show how to use a moderately complex API makes me want to peel someone eyes out.

What makes things matters is that someone, probably management, realized that having single functions span more pages than your average datasheet was a bad idea and forced the inexperienced programmers to break up their functions. This had the unfortunate result that instead of having one humongous main function where at least execution flow was largely obvious the code was broken up into, still very large functions, with generic names such as initialize_options (which initializes maybe 100 variables stored in one enormous struct) and apply_options which used a way too small set of sub functions to apply this large number of options. When they ran out of generic function names they decided to use the next best thing, obscure names such as refresh_soft_cc and set_cp_bit (and no, they don’t make sense even if you know the context).

The second step goes against everything any good programmer should know. Replace all non-stdc calls in your main function with the actual code used in those functions. Iterate until you have nothing but stdc and API calls. You will end up with one very large main but at least code flow will now be painstakingly obvious. This step will aid you in your next venture, step 3.

3. Code reduction

Now that all code is nicely packed into one large bundle start removing anything that doesn’t affect the result of application execution in a negative way. My personal favorite is using #if 0 .. #endif since you can quickly enable/disable code to analyze its effect. I also use this method a lot in step 2 where I add an #else case with my replacement code until I can ascertain that it works like the original function call.

Once you have reduced the remaining code to a bare minimum of functionality you can finally start wrapping your brain around it.

4. Objectify

Not all people like object oriented development but to me it’s one of the most powerful tools I have as a programmer. It allows me to hide away functionality behind clearly understandable concepts such as somePath.parent() and FileUtils::isDirectory(..) which in effect means that you can break large complex problems into smaller and smaller objects. Sometimes I’ve even been known to design prototypes in high order object oriented languages only to make the actual implementation in regular C, without using fancy struct constructs.

It should be obvious by now but the fourth step is to divide your large lump of code into small understandable units of objects. This process will help you to gain a deeper understanding of what is actually going on behind the scenes while at the same time generating objects which you can use more or less unmodified in your applications.

5. Implement all possible features

The last and final step could be considered optional but it is helpful if you want to make sure that no stone is left unturned. By now you should also be close to the peak of total understanding of the system which you are breaking down and now is probably the best time to wrap as much as possible of the API in easy to understand objects. Try to implement features which will exercise all capabilities of the API even if you don’t need it now or any time soon.

Conclusion

By now you should have a pretty complete understanding of the system which you have to work with. Reading the remaining samples should be easier since you should be fairly familiar with domain specific concepts and terminology. Hopefully from hereon you will find it easier to read the remaining code samples as you know what most or maybe even all of the API calls do.

You’ve walked down a long and winding path but in your heart you know it had to be done. Try not to think of the long and tedious process when you start out and instead focus on the end results of your hard labor. I’ve tried having one or two highly interesting side projects to jump to whenever it feels like you are trapped in a dark pit but my experience is that it is better to grab the bull by the horns and just do it as distractions will only cause you to lose focus.

My kudos goes out to the guy who formalized this model which in turn made it much more quantifiable as a legitimate project task.

20 Jan 08 AmiScrobbler

I uploaded the latest source drop from my old CVS of AmiScrobbler to the projects page. I finally found it so now you can stop bugging me about making the latest source available.

The main difference between this version and the latest released version is that it fixed a bug with AmiNetRadio. Since I haven’t worked on this in a long time I don’t know if it will still work with the latest ANR release or even last.fm.

19 Jan 08 Projects page update

I have started going through the backups I recovered from my old server in order to publish some of the more interesting projects on this site. The first two source drops are CrabOS and Loader.

Check out my projects page for more information.

11 Dec 07 Why <insert year here> is not the year Linux takes over the desktop

Right now I’m feeling extremely pissed off and sad, both at the same time. I have been using Linux for more or less 10 years now. By “using” I mean that it has been my primary OS for every purpose you could possible use a computer for. Ok it’s not entirely true, I replaced Linux with FreeBSD for about a year back in 2000 or somewhere around that time. The reason I switched to Linux was simple and I think many of you will recognize it. The major operating system on home computers at the time, you know the one, was extremely bug ridden and unstable and had very little to offer in terms of functionality. Some will argue that it is still unstable and bug ridden but in my limited experience things are much better now than back in the older days in those terms.

Very quickly I learned that Linux had a lot of powerful tools to offer which helped you in everyday matters if only you spent a little time getting to know them. Tools such as find, grep, sed, vi and so on are invaluable and I feel utterly lost without them. The other operating system has virtually no useful tools installed in the base install and even if you go out and waste (a lot of) money on their horrible development package you’ll find yourself with the definition of a bloated GUI where every power tool will be hidden under layers and layers of menus without offering console equivalents. It’s not like the GUI was usable in the first place. Why do focus follow mouse clicks and why on earth isn’t this configurable? Why is it that there are no system logs whatsoever? Why does the system hang for minutes upon minutes during boot if there is no DHCP reply leaving the user in limbo as to what is going on? Now all these issues are moot to me as I do not use this operating system and have no plans on doing so in the near future but to a lot of people this is very much the reality and to an unlucky bunch has been forced upon them. How fascist!

Where was I .. oh, yes .. In recent years Linux adoption by “regular” users has started to grow rapidly. I though this was a great thing at first and I even did my best to help these people ease into the transition. As time went by I started realizing that more and more people around me were Linux users and several of them had jumped on the bandwagon in the last year or so. “Great!”, I thought at the time but recently I have slowly started to come aware of the dark side of it all.

To me applications like Samba are a solution which makes it possible for people who choose to use lesser operating systems to interact with the rest of the world. Personally I like NFS and SSHFS (FUSE), depending on the purpose I think both these solutions do a very good job. If you want service discovery multicast DNS services such as Rendezvous, Avahi etc do an excellent job. You have a portable system which cannot be beaten, why on earth would I need a severely crippled system like SMB other than when interacting with someone on a crippled system?

Back to the issue at hand. Recently I’ve started hearing complaints from the recent Linux switchers. This is all good as no system is perfect and in the beginning I thought it would be refreshing to hear complaints from someone with a different background. Now I’m starting to realize the surmounting disaster that we are soon to face. These people want Linux to plug right into their legacy infrastructure built on top of SMB and other bad solutions. It doesn’t matter that they have replaced their systems with Linux which offers all these “new” shiny features, they still cling to the legacy crap. In the beginning I tried to reason with them but I soon learned that this was impossible. Stupid people don’t get smart just because they made one smart move in their life. With the growing presence of commercial interests I fear that we are going to see major Linux distributions move more and more towards being a bolt-on replacement to their original systems. Resources are going to be spent on making Linux compatible with legacy solutions rather than getting these companies to invest in upgrading their existing infrastructure. Others should be forced to adapt to modern, intelligent standards than forcing Linux to implement proprietary, badly designed, protocols. I fear that Linux is going to become the “new” OSX. All the power tools will be present on the system but most users will have no idea that they exist or how to use them.

The reason I’m pissed is that I am really really fed up with people trying to explain to me why I should be using SMB or why vi is so bad. Why KDE is so much better than GNOME and then having no clue about all the other options like Fluxbox (which I am using), Enlightenment and so on. Why some distribution is bad because it doesn’t automatically call WINE when double clicking an EXE-file, if they had just bothered to STFW they would have set that up in less than 2 minutes btw. If they don’t like the Unix philosophy then why on earth are they using Linux?
Maybe I’m a digital millenium racist but right now I feel that all the switchers should simply go back to their old operating system and leave the rest of us be. I don’t tell them that of course as it would be counter productive.

I’m seriously considering going back to FreeBSD. I loved FreeBSD and the only reason I went back to Linux was due to two drivers, one of which exists for FreeBSD today and the other I don’t need anymore. The BSDs are (luckily) further away from mainstream adoption and do not suffer from the mass of ignorant people infesting the Linux community.

I’ve never been a fan of blurting out RTFM or STFW but I’m seriously considering starting now.

10 Dec 07 Redundant Array of Indestructible Disks

I was investigating the possibility of making the Sun a bit more silent this weekend. In an act of unimaginable stupidity I accidentally pulled the wrong drive out of the RAID. Since I was running RAID5 I kind of assumed I would spend the day waiting for a parity check to finish before my system would be back online again but I was so terribly wrong. I’m using software RAID in OpenBSD, as my SCSI-controller apparently does not come with RAID support, and this is a feature which is not enabled in the supported kernel meaning I only have myself to blame.

Since I don’t own a VGA monitor I drove to work on Saturday evening in order to borrow a monitor so that I could investigate why the system didn’t come up. Instead of recalculating the parity the system refused to boot and waited for me to manually run fsck_ffs on the partitions residing on the RAID. I manually executed a parity recalculation and then ran fsck which found a ton of errors on both the partitions. To top it all off this was the day before my weekly tape backup was to be run. When I finally was able to boot the system it turned out it had killed so many files on /var that it was pretty much useless. I decided to recover the entire tape from last week as I had no idea how far the problems had spread. The posts from last week were recreated by copy pasting from planets where I’m aggregated but I lost the comments, drafts and a couple of other things.

My plan now is to switch to the concatenated disk driver and solely rely on tape for backups. ccd is officially supported by OpenBSD so I assume it doesn’t have as many hidden problems.

The lesson I’ve learned this weekend is to always run the tape backup before messing with the drives. Stupid me!

03 Dec 07 High availability network solutions

A while back I was tasked with prototyping a system for transferring large amounts of data across the Internet to a wide array of nodes without making any assumptions about how they were connected. This took some research on my part as I hadn’t really designed anything network-wise which was to hold up under extreme load or service a huge amount of simultaneous connections. During the investigative period I found a couple of links which I found to be particularly well written which I would now like to share with you.

The first one is “High-Performance Server Architecture” by Jeff Darcy. This is a good introduction into the subject and mainly covers how to manage resources. It will help you avoid the most common mistakes.

After that we have “The C10K problem” by Dan Kegel. This article digs a little deeper and offers many recommendations on how to manage the problem of handling tens of thousands of requests by leveraging existing solutions present in many of the largest *NIX operating systems. This is a typical don’t reinvent the wheel scenario where the OS already has several solutions canned and ready for you as long as you know where to look.

Finally I consulted CiteSeer and found a couple of really good articles on a bit more scientific level which handed me the last pieces of the puzzle. As I can’t divulge too much about our system in particular I’m going to leave the more specific articles out of this blog post.

To top it all off I want to share this excellent but unrelated link to “Capturing that Special Moment“.

28 Nov 07 OpenBSD woes

Based on the encouragement I received to my previous post I installed OpenBSD on the 250 again and this time I compiled a multi processor enabled kernel from current and it worked! So now I’m back on OpenBSD again and it feels great.

I also found that the AR5212 WiFi chipset is one of the supported chipsets in OpenBSD and as it happens I bought a D-Link DWL-G520 a couple of years ago that hasn’t been doing any good ever so I decided to install it in the 250. A huge Sun machine with a small WiFi antenna on the back looks kind of cool in my opinion. Sadly the ath is not as stable as I had hoped so it will have to be left disabled for the time being. So no replacing the Linksys just yet.
There is of course also the possibility that it is caused by a problem in -current, I’ll just have to wait and see.

MySQL seems to require a significant amount of processing power as it is a constant bottleneck when servicing pages from Wordpress. There is a very noticable latency whenever I load anything dynamic that requires data from the db whereas other pages come up instantly. I guess I’ll have to dig through the MySQL documentation on how to optimize it. Especially considering that at the time being it is very memory conservative, much more than it need be.