Sunday, May 24, 2009

pthreads and UNIX signals

A while ago, I wrote in this blog entry that when sending signals to a multi-threaded process, it is unclear which thread receives the signal. This little problem is actually easy to solve when you realize that you can create a seperate thread whose sole purpose it is to catch signals and respond to them.

You can mask out certain signals using sigprocmask() and its threaded nephew, pthread_sigmask(). These signals will be effectively disabled and will never be received in these contexts.
In the "signal processing" thread, enable the blocked signals. This will now be the only thread who receives the signals.

In almost finished C-code:
int main(int argc, char *argv[]) {
sigset_t set;

/* create signal processing thread */
pthread_create(&thread_id, NULL, signal_processor, NULL);

/*
in the main thread, set up the desired signal mask, common to most threads
any newly created threads will inherit this signal mask
*/
sigemptyset(&set);
sigaddset(&set, SIGHUP);
sigaddset(&set, SIGINT);
sigaddset(&set, SIGUSR1);
sigaddset(&set, SIGUSR2);
sigaddset(&set, SIGALRM);
/* sigaddset(&set, SIGWHATEVER); */

/* block out these signals */
sigprocmask(SIG_BLOCK, &set, NULL);

/* create other threads */
pthread_create(...);

/* ... */

/* pthread_join(...); */

/* ... */

return 0;
}

/*
implementation of the signal processing thread
*/
void *signal_processor(void *arg) {
/*
install signal handlers for interesting signals
I choose to install dummy handlers (see below for why)
*/
install_signal_handler(SIGHUP);
install_signal_handler(SIGINT);
install_signal_handler(SIGUSR1);
install_signal_handler(SIGUSR2);
install_signal_handler(SIGALRM);
/* install_signal_handler(SIGWHATEVER); */

for(;;) { /* forever */
/*
wait for any signal
*/
sigfillset(&set);
sigwait(&set, &sig);

/*
handle the signal here, rather than in a signal handler
*/
switch(sig) {
case SIGTERM:
exit(1);

case SIGHUP:
reload_config();
break;

default:
printf("caught signal %d\n", sig);
}
}
}

void dummy_signal_handler(int sig) {
/* nothing */
;
}

So, the code first creates a signal processing thread. This thread has the default signal mask and will therefore receive signals. The main thread then installs a signal mask that blocks most signals. Any threads created from the main thread will inherit this new signal mask.
The signal processing thread uses sigaction() (not shown here) to install signal handlers. These signal handlers are empty dummies. The reason for this is, by installing a signal handler you tell the operating system that you do not want the default signal action for these signals. Next, call sigwait(), so wait indefinately until any signal arrives. Then, handle the caught signal.
It is possible to install useful signal handlers instead of using the dummies, but I'd much rather use sigwait() and make signal handling synchronous as opposed to asynchronous. (The threads are still run asynchonously in respect to each other, though).

It is tempting to simply use sigfillset() and block all signals. While this is perfectly possible, it does have some implications. Any errors that generate signals like SIGSEGV, SIGBUS, SIGILL, will be blocked in the thread that generated the error, and caught in the signal processing thread. Be wary of this, as this is likely to produce debugging headaches.

There is a pthread_kill() function that you can use to send signals to threads. Do not use this mechanism to communicate between threads. Threads should synchronize and communicate using mutexes, barriers, and condition variables, and if you want to terminate a thread you should use pthread_cancel(), or communicate to it that it should exit, so that it can call pthread_exit() by itself.
The only use of pthread_kill() is to copy the signal to other threads that should also receive it, if you have a (weird) code where multiple threads can be signalled.

Wednesday, May 6, 2009

Multi-core games programming

I'm on sick leave, and although I've got some bad stomach problems and my head hurts, this is finally an opportunity to think over the problem of multi-core games programming. You see, modern computers are parallel machines, and it is a challenge to the programmer to take advantage of all this processing power.

Games are an interesting class of computer programs. Even the simplest of games draw our attention, because of the interaction between human and machine. On the inside, games are interesting as well. The code often contains things like an input handler, object allocators, sound file loaders, sprite or 3D object rendering code, etc, etc.
When switching from a single threaded game design to a multi-threaded one, you would probably think it would be smart to make a functional split:
  • a thread that handles sound
  • a thread that handles AI
  • a thread that handles rendering
  • a thread that handles input processing
While there is nothing wrong with this design, you are not getting the most out of the machine. What if we have a 8-core or 16-core or 100-core machine?

Imagine an old 8-bit 2D game where you walk around in a maze, picking up objects, and shooting bad guys. Do you have it visualized in your mind? Now, imagine a modern 3D shooter. What has changed? The amount of data, but also the amount of math. 3D worlds can be huge, with high-res textures, and realtime reflections and shadows. Great graphics hardware will take care of rendering objects to the screen, but the decision of what data of this vast 3D world is pushed to the GPU, is up to the programmer. All the culling has to be performed on the CPU, not the GPU.
What if the player bumps into a wall? Collision detection is a job done by the CPU. In our old 8-bit game, we could get away with checking the byte value (representing a wall) next to the player position in the two-dimensional array that represented the map. In a modern 3D game, we have to do a lot more than just that -- we have to compute the intersection between player and wall object with any of the walls that are near. In theory, we'd have to check every wall in the map, however, this is made more efficient by splitting the map into sections. Still, a section can be full of walls and other objects to bump in to. This takes a vast amount of computations.
Another subject is AI. While you'd probably think that good AI takes an enormous amount of CPU power, this is usually not the case. Yes, AI may utilize complex formulas, but this is generally totally unnecessary. Making a character behave or perform certain actions is accomplished by implementing a simple state machine. The state machine need not do much to get great results. It is the (vast) amount of intellectually behaving objects in the game world that results in AI taking up CPU time.
One last thing is animation. In the old 8-bit days, animations were done by drawing the next animation frame on every game tick. In the modern days of 3D graphics, there are still frames, but the 3D points can be interpolated in between frames, allowing for supersmooth animation. This requires every point to be interpolated on every game tick. In fact, nowadays we have multi-tasking operating systems, and a game tick is no longer a hard set value — one tick can last 10 ms, while the next one lasts 50 ms or more. This irregular behaviour of the game clock calls for interpolation too, in order to keep animations from stuttering.

As you may have realized by now, it is wise to parallelize by splitting on "data", or object handling. If we spawn as many threads as there are processor cores, we are fully utilizing the CPU. Maybe we even want to play nice and leave a core unallocated so that the operating system gets a chance to run its tasks while we are busy gaming.
We parallelize each big for-loop in the code:

PARALLEL DO
foreach obj in objects
do
animate(obj)
artificial_intelligence(obj)
collision_detect(obj)
culling(obj) # set flag whether object is visible
end
END PARALLEL DO

render:
foreach obj in objects
do
if obj.visible
then
draw_object(obj)
endif
end
flush_screen()

Note how the rendering loop is not parallel. Funnily enough, the GPU is addressed in serial. This is funny because the GPU in itself is a massively parallel processor.
I do not recommend putting the rendering loop in a thread by itself. The reason for this is that if you do, you will need to mutex-lock each object that is being rendered. This is less efficient than simply doing it in serial.

Enough talk and pseudo-code, it's time to sit down and implement this for real. But first, I need to get rid of my headache ...

Saturday, February 28, 2009

Dining Philosophers

A while ago, I wrote about threading. Last week, one of the students I'm guiding for their internship, mentioned he still had to complete a programming assignment. It was about implementing the dining philosophers problem in C, using pthreads. To a student, this can be quite a challenge.

The dining philosophers problem is a very fun programming problem concerning resource locking. The origins date all the way back to 1965, a time when computers were big clunky machines with green terminals, and the operators were computer scientists wearing lab coats.

An excellent description of the problem can be found in Wikipedia.

I remember my brother once explained it to me when I was young. He loves spaghetti, so I guess the idea of the philosophers having spaghetti kind of appealed to him. He noted that, in a real world situation, the problem is easily solved by adding a director, who tells the philosophers when to eat and when to think. So, a scheduling assistant can help in solving the problem. However, the problem can also easily balance itself by doing the right kind of locking, and be solved without the use of an explicit arbiter.

In pseudo code:
proc run_thread() {
while plate not empty {
lock(left_fork)
if not trylock(right_fork) {
unlock(left_fork)
continue
}
eat from plate

unlock(right_fork)
unlock(left_fork)
}
}
In order to avoid deadlock, trylock is used rather than a hard lock. trylock is an atomic operation like bit-test-and-set; it locks only if the lock was free, and does not wait until you actually own the lock.
When locking multiple resources at once, it is good practice to unlock in the reverse order of locking, also to avoid deadlock.
Note that there is no need to sleep anywhere in the loop; waiting for short periods of time is something that a human would do, but is totally unnecessary in a computer program. (Think of all the cycles needed to load/execute the instructions in between as waiting for short periods of time!)

Starvation
In the above code, it's possible that one philosopher finishes his plate, while the others haven't even started yet — they are literally starving. It would be good table manners if we instructed each philosopher not to eat faster than his neighbors. This would produce automatic balancing in the use of the resources.

In pseudo-code:
    if my_plate < left_neighbor_plate
or my_plate < right_neighbor_plate then
eat from plate
Making the wrong if-statement here results in nobody eating. You can also move this if-statement up, and refrain from trying to lock while the neighbors haven't eaten yet. This is giving your neighbors a chance to eat, and results in spinning before the lock, but also in a higher success rate for acquiring both locks.

What's fun is seeing how the outcome is different every time; you can actually gamble on which philosopher will finish first. Multi-threaded programs have a weird way of being undeterministic somehow.

As an exercise, and just for the fun of it, I coded up the dining philosophers problem with N philosophers in C with pthreads in less than an hour. I think that I would have had a much harder time at it when I was still a student, though.

Sunday, January 25, 2009

OpenAL - sounds good!

For getting sound to work on the iPhone, I needed to acquaint myself with the OpenAL sound system. OpenAL is also particularly interesting because it is a 3D sound system. You set the position of a sound source, and OpenAL will take care of getting the volume just right, as well as the "position" of the sound where you are perceiving it to be coming from, when you hear it played on your surround set. It can also do cool things like the doppler effect. While I do not need 3D sound and just have started using OpenAL, it would certainly be cool to get some simple stereo sound effects in my game. This is something that SDL_mixer can not do.

OpenAL tutorials and ALUT
There are some nice tutorials on the web, and they all use ALUT. It turns out that ALUT had some (simple to resolve!) bugs in it, and some guys decided to mark it as deprecated. When standard C code gets marked as deprecated, gcc won't compile it anymore. So, now all those nice online tutorials don't work anymore. ALUT had two functions that were really convenient: alutInit() and alutLoadWAVFile(). Writing my own WAV loader took some time, but I managed, and initializing OpenAL properly takes some magic sequence, but read below about how that works.

Ubuntu Linux suxxors
First a sidestep from writing code; getting your system to work, and be able to produce sound at all. My favorite development platform is still Linux. For some reason, Ubuntu decided to break sound in version 8.10 (Intrepid) and I've been hassling with it for days to get some audio output out of my programs. At it turns out, Ubuntu Intrepid mixes asound (ALSA), esnd, and PulseAudio, with an apparent preference for PulseAudio, except that it's not properly integrated or set up or whatever, it just doesn't work in all cases. That's right, one program seems to work, while others don't. The solution: I removed all PulseAudio packages from my system, and installed their ALSA counterparts. (In fact, I compiled the mpd music player daemon by hand, because Ubuntu's version tried to use PulseAudio anyway). After taking these drastic measures, my sound programs produced audio output, hurray!!

Initializing OpenAL
As said, we are going to have to do without ALUT. OpenAL needs to be initialized by creating a "context" and selecting the audio device, otherwise you will get nothing but errors. In some tutorials, I found that you may select "DirectSound3D" as a device, but that obviously only works on Windows. I have no clue what devices are available on Linux, MacOS X, or whatever other platform you may think of. Luckily, there is a way to get the default device.
I'll share The Code with you:
#include "al.h"
#include "alc.h"

int init_openal(void) {
ALCcontext *context;
ALCdevice *device;
const ALCchar *default_device;

default_device = alcGetString(NULL,
ALC_DEFAULT_DEVICE_SPECIFIER);

printf("using default device: %s\n", default_device);

if ((device = alcOpenDevice(default_device)) == NULL) {
fprintf(stderr, "failed to open sound device\n");
return -1;
}
context = alcCreateContext(device, NULL);
alcMakeCurrentContext(context);
alcProcessContext(context);

/* you may use alcGetError() at this point to see if everything is still OK */

atexit(atexit_openal);

/* allocate buffers and sources here using alGenBuffers() and alGenSources() */
/* ... */

alGetError(); /* clear any AL errors beforehand */
return 0;
}
First a remark about the includes. Including the files "al.h" and "alc.h" is much more portable than using <AL/al.h> and <AL/alc.h>, and it saves you from resorting to "#ifdef PLATFORM_SO_AND_SO" constructs.
Using the default device may not always be the best choice. There should be an option in the program to let the user decide on what device to use.
Note the atexit() call; OpenAL will complain loudly when you exit the program without having cleaned up properly. It has a right to complain too; you've allocated some valuable hardware resources and it may be well possible that the operating system is not exactly babysitting this hardware, meaning that when you exit the program without releasing the allocated hardware buffers, they will remain as marked 'in use' until the computer is rebooted (!).
A good atexit() handler frees the allocated resources and closes the sound device.
#include "al.h"
#include "alc.h"

int init_openal(void) {
ALCcontext *context;
ALCdevice *device;
const ALCchar *default_device;

default_device = alcGetString(NULL,
ALC_DEFAULT_DEVICE_SPECIFIER);

printf("using default device: %s\n", default_device);

if ((device = alcOpenDevice(default_device)) == NULL) {
fprintf(stderr, "failed to open sound device\n");
return -1;
}
context = alcCreateContext(device, NULL);
alcMakeCurrentContext(context);
alcProcessContext(context);

/* you may use alcGetError() at this point to see if everything is still OK */

atexit(atexit_openal);

/* allocate buffers and sources here using alGenBuffers() and alGenSources() */
/* ... */

alGetError(); /* clear any AL errors beforehand */
return 0;
}
Mind the order in which to call OpenAL in the atexit handler, always first stop the sound, delete the sound sources, and then delete the buffers. Then move on to the context, and finally close the device. If you don't do it in this order, the sound system will not be properly de-initialized.

Loading .WAV files
Loading WAV sound files is easy, although there is one big gotcha to it: it is a binary format, stored in little endian format. The intel x86 line of processors are all little endian, so no problem there. However, I like to write portable code, so this is a bit of fun. I have the pleasure of having access to a big endian machine, so I could test my WAVE loader code there, too. I came up with a very simple test too see if a machine is big or little endian:
#include <stdint.h>

int is_big_endian(void) {
unsigned char test[4] = { 0x12, 0x34, 0x56, 0x78 };

return *((uint32_t *)test) == 0x12345678;
}
The is_little_endian() function is left as an exercise to the reader.

Back to the WAVE loader, what I do is simply read the whole file into
memory and then map a struct that represents the WAV header over it. Then I do the integer fixups (read as little endian values), and then perform some basic checks on whether this really was a good WAV file. For a music player, you should do these checks before loading the music data, but for my game code, I was happy with simply loading the file all at once.

You can find good information about the structure of a WAV file header on the web. Note how a WAVE loader is really a RIFF loader, and in my case, also a PCM sound loader.
There is a gotcha when blindly pouring the WAV header information into a struct, which is alignment. The compiler may mess around with the size of your struct ... use pragma pack to
instruct the compiler to refrain from doing that:
#pragma pack(1)
typedef struct {
uint32_t Chunk_ID;
uint32_t ChunkSize;
...
uint16_t AudioFormat;
...
} WAV_header_t;
#pragma pack()
I've noticed that there are quite a few WAV files out there that have little mistakes in the
headers, in particular the final field data_size (or subchunk2_size), which represents the length of the music data, is often wrong. The correct value is file size minus header size, and note that you can now 'repair' the WAV file.
Now that we've succeeded in loading the .WAV file, feed this data into alBufferData() and we're ready to make some noise.

Closing remarks
In this blog entry I've shown how you can survive without ALUT. Although SDL_mixer happily handles .mp3s, and many other formats, it doesn't give you the stereo and 3D sound that OpenAL does. For OpenAL, you will need to write your own sample loader. Painful as it seems, it is really just a good exercise in handling data formats.
In the devmaster OpenAL tutorials they show how to stream Ogg Vorbis files through OpenAL. Be sure to read all their tutorials, they're pretty straightforward once you've gotten through lesson 1. Also note how they rely on ALUT ... forget about ALUT. Use OpenAL, it sounds good.