A tale of two tiny bugs in Linux PAM's pam_access

Recently, a colleague of mine decided to introduce netgroups to our systems. NIS netgroups are a means of logically grouping users. So I reconfigured PAM to use netgroups: users had to be member of a certain netgroup to be granted access to the system. To my surprise, it didn't work on one system, while it did on another. Clearly we hit a bug, and one system was running a different version of the pam_access module. A little digging let to the excavation of an old bug. Interestingly enough, I discovered a second tiny mistake in the code.

First of all, I want it to be clear that I have great respect for all the developers that do the hard work for Linux. Zooming in on this little piece of code is for the love of code, and to illustrate the nature of the bug in detail for educational purposes.

Let us do a bit of NIS programming. You need the innetgr() function to tell whether a user is member of a group. Its signature is:

int innetgr(const char *netgroup, const char *host, const char *user, const char *domain);

The function innetgr() returns 1 for a successful match and 0 otherwise. The host and domain parameters may be NULL. The domain must be set though if a NIS domain has been configured. In order to find out what the NIS domain is, you can use either yp_get_default_domain() or getdomainname().

int yp_get_default_domain(char **domp);
int getdomainname(char *name, int namelen);

Both functions get the domain name, apparently there are systems where only one of these is available. If no domain name is configured, yp_get_default_domain() will set the pointer to NULL. The function getdomainname() may set the name to "\0" (empty string) or it may set it to "(none)".

The pam_access code looked like this:

/* netgroup_match - match group against machine or user */

static int
netgroup_match (pam_handle_t *pamh, const char *netgroup,
        const char *machine, const char *user, int debug)
{
  int retval;
  char *mydomain = NULL;

#ifdef HAVE_YP_GET_DEFAUTL_DOMAIN
  yp_get_default_domain(&mydomain);

#elif defined(HAVE_GETDOMAINNAME)
  char domainname_res[256];

  if (getdomainname (domainname_res, sizeof (domainname_res)) == 0)
    {
      if (strcmp (domainname_res, "(none)") == 0)
        {
  /* If domainname is not set, some systems will return "(none)" */
          domainname_res[0] = '\0';
        }
      mydomain = domainname_res;
    }
#endif

So, suppose you have a system that has no NIS domain name configured and it used getdomainname() to get the domain name. Consequently the name will be either an empty string or the string "(none)". If the domain is "(none)", it will be reset to an empty string. If you pass an empty string as domain to innetgr(), it will fail and report the user is not part of the netgroup. The reason is that the domain parameter of innetgr() must be NULL to indicate any domain name, an empty string will not do.

Note that this is an old version of the code. However, this code was still current for a debian linux system. Debian is known for running ‘stable’ code, as new software is likely to include new and buggy features. This particular bug was fixed over a year ago though.

The second problem with the code was still present, and it is right here:

#ifdef HAVE_YP_GET_DEFAUTL_DOMAIN

which is clearly a typo. When you make typos in code the compiler will usually catch them, but this is a preprocessor statement and it managed to go unnoticed for at least three years. This typo caused yp_get_default_domain() never to be used at all. This wasn't much of a problem since Linux systems typically provide both functions, but ironically, the block with getdomainname() contained a bug. Fixing the typo causes yp_get_default_domain() to be used and effectively discards the block with getdomainname().

Computers are very unforgiving to the mistakes that we humans make. The smallest of mistakes can be of great consequence (like users not being able to authenticate (!)). I was lucky to encounter and fix this problem, and I guess it shows the beauty of open source. Anyone can contribute to open source software, and anyone can help in making the whole a little bit better.

oolib gets notifications

Apple's Cocoa API has an interesting feature named the Notification Center. It enables UI components to communicate by posting messages to whomever is interested. I suppose it's a bit like Twitter in the insides of a computer program; objects may blurt out messages regardless of who is listening, and objects may show interest in receiving messages from other objects.

Notifications allow for loose coupling between objects. Suppose you have two classes A and B, and you want to make a state change in an instance of class A known to an instance of class B. The traditional way of doing that is to have A call a method in B. Now, A depends on B, and they are tightly coupled.
With notifications, the situation changes. A announces its state change to the world. B listens to state change messages, so it picks up the state change. There is no interdependency between the two, they are just handling messages. You can add a third class C that reacts to the message in another way, without touching class A.

This is particularly useful for GUI widgets; for example, a button announces it's been pressed, a scroll bar announces it's been moved, and a movie player announces it's finished playing.

For oolib, my personal C++ framework, I wanted to have this functionality too. It basically works like this: an object may register itself as an observer of certain messages. Whenever that message is sent, the observer will be notified.

class MyObserver : public Observer {
public:
    void notify(const char *event) {
        print("observer: %s", event);
    }
};

const char *Event1 = "This is event #1";
const char *Event2 = "This is event #2";

int main(int argc, char *argv[]) {
    MyObserver o;
    add_observer(o, Event1);
    add_observer(o, Event2);

    notify(Event1);
    notify(Event2);
    return 0;
}

The global notify() function will see to it that observer->notify() will be called for all registered observers.

There is one big difference between oolib's notify() and Cocoa's NSNotificationCenter: Cocoa works with Objective-C, and allows you to supply a selector—which is a function pointer, so it's essentially a callback mechanism.
With oolib, you are required to inherit from Observer and implement the virtual method notify(), which is more like ‘the C++ way’ of doing things.

Finally, I should mention the Qt framework. Qt has a feature called slots and signals, which allows you to connect a slot (class method) to a signal, which can be emitted by some object. It looks like Qt works by virtue of pointers to methods... which is peculiar because C++ does not deal well with pointers to methods. The Qt folks actually use a meta-compiler that generates the code needed to make it work.

This programming trick is also known as the observer pattern.

Starry, starry night

The holidays are nearing, and it always makes me ponder the universe. Maybe it's because the stars come out in the cold and clear dark winter evenings, or maybe it's because of the unusually bright star in the Christmas story. Anyway, it gave me the idea of creating something like a classic 3D star field. What if you used actual star positions for this star field, and would you see something like you do on Star Trek if you flew through it at warp speed?

I started out by searching for star catalogs. These are plain text databases with lots and lots of scientific data about the stars.
Star databases are a bit of an annoyance; each has its own format, and they all contain different fields. Some contain parallax data (which is needed for calculating the distance of stars), but most don't. Some contain the visible color of stars, others don't. But most annoying of all, they don't use the same unique identifiers; star Procyon A is named HIP-37279 in the Hipparcos catalog, HD 61421 in the Henry Draper catalog, Gliese 280 in the Gliese catalog, while it's Bayer Flamsteed designation is 10 Alpha Canis Minoris.
The Tycho-2 star catalog contains over 2.5 million stars, but unfortunately it is worthless for making a 3D model because it lacks parallax data. So I took the HYG database, which is a modified version of the Hipparcos database, and combined it with usable data from the SKY2000 star catalog, plus a short list of well-known brightest stars. This involved some awk and Python scripting to cross reference the databases and calculate the 3D positions.

Star positions are usually given in right ascension (RA) and declination (Dec). These are angles, like latitude and longitude, but are often described in hours, minutes, and seconds. Given the angles and the parallax, you can calculate an x,y,z position in space, and this is what we need for a 3D star field. These coordinates have the earth at its origin. You might want to use galactic coordinates instead, which puts the Sun at the origin.
Now, because all of this stuff is turning, turning in outer space, the positions of stars change (unlike what I was told as a child). Star databases contain the position at a point in time (referred to as the epoch) and you can adjust the position using the proper motion of stars. Frankly, I didn't bother, but if you want to know the correct position of a star as it is today, you are going to have to do some extra math.

The constellation Orion

At a distance of 4 kpc

So, I put all coordinates into OpenGL and the result is pretty neat. In the left image you can clearly see Orion. The red star in the top-left of Orion is Betelgeuse. All the way to the left from Betelgeuse is Procyon. The image on the right shows what you see from a distance of 4 kiloparsecs. It's like a bubble with a disc through the center. This is just what the data set looks like though; in reality, it probably does not have this shape as we are part of a much, much larger Milky Way.

This is what almost 220 thousand stars look like on a computer screen, and you can look around and point at stars in real-time.

Fun facts:

• The furthest bright star, just outside the bubble, is Deneb at 4754.8 light years.
• Most stars around us are red dwarfs. Hence the pinkish color of the bubble.
• When you travel to another star, the night sky looks different.
• OpenGL vertex buffer objects (VBO) kick ass.

I was amazed that my (now three years old) computer had no problems whatsoever in dealing with this data. Once again, I find that the modern PC is an amazingly powerful computer. Although I'm no scientist and no astronomer, it enabled me to put together a pretty realistic 3D model of our stellar neighborhood in my attic.

A Pool Allocator or The (un)importance of Code Optimization

In school I learned to use dynamic memory allocation, and to use linked lists to keep track of dynamically allocated objects. The idea was that arrays are static and fixed-size, while linked lists can virtually limitless continue to grow dynamically. The linked list also doesn't use memory that it doesn't need, and there are some nice performance characteristics when inserting and removing items from a linked list.

The malloc() library function takes memory from the heap, which is a region of memory. Whenever malloc() runs out of heap space, it will call sbrk() to grow the heap by asking the operating system kernel for extra memory pages. Modern operating systems actually use mmap() instead, which works by virtue of virtual memory and demand paging. It's all pretty sophisticated.

How different were things for classic arcade game machines, tiny computers with very small system memory. There was practically no operating system at all, it was just the game code itself running on the bare metal. Arcade games like Space Invaders and Galaga did not have the luxury of a malloc() library function. They were not even written in C, but in the machine's assembly language. The way to allocate monsters and bullets was to use an array in the bss segment—an area of system RAM memory sitting just outside where the program code was loaded, or rather, copied from eeprom to RAM when the machine was switched on.

Things were so much simpler then, but even today I like allocating monsters and bullets from a ‘free’ list backed by a statically allocated array. Such a pool allocator gives a very clear picture of what is going on and how things work.

Even though the pool allocator has a hard maximum on how many objects may be allocated, it will never deny you memory if you stay within that limit. No other task in a multitasking operating system can steal this memory away from you, making it a very robust memory allocator.
In terms of performance, the pool allocator always completes in a fixed time, which is important for games that need constant performance.

Discussions about memory usage and performance are becoming pointless in this day and age, when we have massive amounts of memory and CPU power at our disposal even on mobile devices. As computers before were frustratingly slow machines, you had to push the limits to get the most out of it. Writing efficient code was the challenge, and every time you managed to squeeze out a few cycles more it was an achievement well earned.

Nowadays this hardly applies anymore. Although I have to say, lately I had some scripting code for doing large data processing. I rewrote it in C++ with multi-threading, and boy, did that make a difference in run time.