A good idea with bad usage: /dev/urandom

Last week, I wrote two articles pointing out issues with unofficial porting efforts of LibreSSL. In these articles, I highlighted some issues that I currently see going on with some of these projects.

In the second article, I called attention to poor arc4random_buf() implementations being created, specifically saying: "Using poor sources of entropy like /dev/urandom on Linux, or worse, gettimeofday(), and using them to generate long-lived keys." Which seemed to irk some. Now for those that care to understand the quoted issue in its proper context should go look for the current LibreSSL porting projects they can find via Google, and review their source. However, most seem to be understanding this as some kind of argument about /dev/random versus /dev/urandom. It isn't. So without further ado:

Poorly seeding a cryptographically secure pseudorandom number generator (CSPRNG)

In order for many forms of cryptography to work properly, they depend on secrecy, unpredictability, and uniqueness. Therefore, we need a good way to use many unpredictable values.

Now randomness doesn't really exist. When we humans see something as random, it's only because we don't know or understand all the details. Therefore, any perceived randomness on your part is your inability to track all the variables.

Computers are very complex machines, where many different components are all working independently, and in ways that are hard to keep track of externally. Therefore, the operating system is able to collect variables from all the various hardware involved, their current operating conditions, how they handle certain tasks, how long they take, how much electricity they use, and so on. These variables can now be combined together using very confusing and ridiculous algorithms, which essentially throw all the data through a washing machine and the world's worst roller coaster. This result is what we call entropy.

Now entropy might not be that large, and can only provide a small amount of unique random values to play with. However, a small amount of random values can be enough to create trillions of pseudo-random values. To do so, one uses some of the aforementioned ridiculous algorithms to produce two values. One value is never seen outside the pseudo-random number generator, and is used as part of the calculations for the next time a random value is requested, and the other value is output as the pseudo-random value generated for a single request.

A construct of this nature can allow an unlimited amount of "random" values to be generated. As long as this technique never repeats and is unpredictable, then it is cryptographically secure. Of course since the algorithm is known, the entropy seeding it must be a secret, otherwise it is completely predictable.

Different algorithms have different properties. OpenBSD's arc4random set of functions are known to be able to create a very large amount of good random values from a very little amount of entropy. Of course the better entropy it is supplied with, the better it can perform, so you'll always want the best entropy possible. As with any random number generator, supply it with predictable values, and its entire security is negated.

arc4random and /dev/(u)random

So, how does one port the arc4random family to Linux? Linux is well known for inventing and supplying two default files, /dev/random and /dev/urandom (unlimited random). The former is pretty much raw entropy, while the latter is the output of a CSPRNG function like OpenBSD's arc4random family. The former can be seen as more random, and the latter as less random, but the differences are extremely hard to measure, which is why CSPRNGs work in the first place. Since the former is only entropy, it is limited as to how much it can output, and one needing a lot of random data can be stuck waiting a while for it to fill up the random buffer. Since the latter is a CSPRNG, it can keep outputting data indefinitely, without any significant waiting periods.

Now theoretically, one can make the arc4random_buf() function a wrapper around /dev/urandom, and be done with it. The only reason not to is because one may trust the arc4random set of algorithms more than /dev/urandom. In that case, would /dev/urandom be trusted enough to seed the arc4random algorithms, which is then in turn used for many other outputs, some of which end up in RSA keys, SSH keys, and so on? I'll leave that question to the cryptographic experts. But I'll show you how to use /dev/urandom poorly, how to attack the design, and corrective efforts.

First, take a look at how one project decided to handle the situation. It tries to use /dev/urandom, and in a worse case scenario uses gettimeofday() and other predictable data. Also, in a case where the read() function doesn't return as much as requested for some reason, but perhaps returned a decent chunk of it, the gettimeofday() and getpid() calls will overwrite what was returned.

This very much reminds me of why the OpenBSD team removed the OpenSSL techniques in the first place. You do not want to use a time function as your primary source of entropy, nor with range limited values, and other dumb things. If you're going to use time, at the very least use clock_gettime() which provides time resolution that is 1,000 times better than gettimeofday(), and can provide both current time, and monotonic time (time which cannot go backwards). Additionally, both gettimeofday() and clock_gettime() on 64-bit systems will return values where the top half of their data will be zeroed out, so you'll want to ensure you throw that away, and not just use their raw data verbatim. Further, how this one project uses /dev/urandom, like most other projects, is terrible.

Attacking /dev/(u)random usage

A naive approach to use /dev/urandom (and /dev/random) is as follows:

int fd = open("/dev/urandom", O_RDONLY);
if (fd != -1)
{
  uint8_t buffer[40];
  if (read(fd, buffer, sizeof(buffer)) == sizeof(buffer)))
  {
    //Do what needs to be done with the random data...
  }
  else
  {
    //Read error handling
  }
  close(fd);
}
else
{
  //Open error handling
}

This tries to open the file, ensures it was opened, tries to read 40 bytes of data, and continues what it needs to do in each scenario. Note, 40 bytes is the amount arc4random wants, which also happens to be 8 bytes more than the Linux manual page says you should be using at a time from its random device.

The first common mistake here is using read() like this. read() can be interrupted. Normally it can't be interrupted for regular files, but this device is not a regular file. Some random device implementations specifically document that read() can be interrupted upon them.

So now our second attempt:

//Like read(), but keep reading upon interuption, until everything possible is read
ssize_t insane_read(int fd, void *buf, size_t count)
{
  ssize_t amount_read = 0;
  while ((size_t)amount_read < count)
  {
    ssize_t r = read(fd, (char *)buf+amount_read, count-amount_read);
    if (r > 0) { amount_read += r; }
    else if (!r) { break; }
    else if (errno != EINTR)
    {
      amount_read = -1;
      break;
    }
  }
  return(amount_read);
}

int success = 0;
int fd = open("/dev/urandom", O_RDONLY);
if (fd != -1)
{
  uint8_t buffer[40];
  ssize_t amount = insane_read(fd, buffer, sizeof(buffer)); //Grab as much data as we possibly can
  close(fd);

  if (amount > 0)
  {
    if (amount < sizeof(buffer))
    {
      //Continue filling with other sources
    }
    //Do what needs to be done with random data...
    success = 1; //Yay!
  }
}

if (!success)
{
  //Error handling
}

With this improved approach, we know we're reading as much as possible, and if not, then we can try using lesser techniques to fill in the missing entropy required. So far so good, right?

Now, let me ask you, why would opening /dev/(u)random fail in the first place? First, it's possible the open was interrupted, as may happen on some implementations. So the open() call should probably be wrapped like read() is. In fact, you may consider switching to the C family fopen() and fread() calls which handle these kinds of problems for you. However, opening could be failing because the application has reached its file descriptor limit, which is even more prevalent with the C family of file functions. Another possibility is that the file doesn't even exist. Go ahead, try to delete the file as the superuser, nothing stops you. Also, you have to consider that applications may be running inside a chroot, and /dev/ entries don't exist.

I'll cover some alternative approaches for the above problems later. But if you managed to open and read all the data needed, everything is great, right? Wrong! How do you even know if /dev/(u)random is random in the first place? This may sound like a strange question, but it isn't. You can't just trust a file because of it's path. Consider an attacker ran the following:

void sparse_1gb_overwrite(const char *path)
{
  int fd;
  char byte = 0;
  //No error checking
  unlink(path);
  fd = open(path, O_CREAT | O_WRONLY | O_TRUNC, 0644);
  lseek(fd, 1073741822, SEEK_SET);
  write(fd, &byte, 1);
  close(fd);
}

sparse_1gb_create("/dev/random");
sparse_1gb_create("/dev/urandom");

Now both random devices are actually large sparse files with known data. This is worse than not having access to these files, in fact, the attacker is able to provide you with a seed of his own choosing! A strong cryptographic library should not just assume everything is in a proper state. In fact, if you're using a chroot, you're already admitting you don't trust what will happen on the file system, and you want to isolate some applications from the rest of the system.

So the next step is to ensure that the so called device you're opening is actually a device:

int success = 0;
int fd = insane_open("/dev/urandom", O_RDONLY);
if (fd != -1)
{
  struct stat stat_buffer;
  if (!fstat(fd, &stat_buffer) && S_ISCHR(stat_buffer.st_mode)) //Make sure we opened a character device!
  {
    uint8_t buffer[40];
    ssize_t amount = insane_read(fd, buffer, sizeof(buffer)); //Grab as much data as we possibly can

    if (amount > 0)
    {
      if (amount < sizeof(buffer))
      {
        //Continue filling with other sources
      }
      //Do what needs to be done with random data...
      success = 1; //Yay!
    }
  }
  close(fd);
}

if (!success)
{
  //Error handling
}

So now we're out of the woods, right? Unfortunately not yet. How do you know you opened the correct character device? Maybe /dev/urandom is symlinked to /dev/zero? You can run lstat() on /dev/urandom initially, but that has TOCTOU issues. We can add the FreeBSD/Linux extension O_NOFOLLOW to the open command, but then /dev/urandom can't be used when it's linked to /dev/random as it is on FreeBSD, or linked to some other location entirely as on Solaris. Furthermore, avoiding symlinks is not enough:

void dev_zero_overwrite(const char *path)
{
  unlink(path);
  mknod(path, S_IFCHR | 0644, makedev(1, 5));
}

dev_zero_overwrite("/dev/random");
dev_zero_overwrite("/dev/urandom");

If an attacker manages to run the above code on Linux, the random devices are now both in their very essence /dev/zero!

Here's a list of device numbers for the random devices on various Operating Systems:

	Linux	FreeBSD	DragonFlyBSD	NetBSD	OpenBSD	Solaris
/dev/random	1:8	0:10	8:3	46:0	45:0	0:0
/dev/urandom	1:9		8:4	46:1	45:2	0:1
/dev/srandom					45:1
/dev/arandom					45:3

If your application is running with Superuser privileges, you can actually create these random devices anywhere on the fly:

int result = mknod("/tmp/myurandom", S_IFCHR | 0400, makedev(1, 9)); //Create "/dev/urandom" on Linux

Of course, after opening, you want to ensure that you're using what you think you're using:

int success = 0;
int fd = insane_open("/dev/urandom", O_RDONLY);
if (fd != -1)
{
  struct stat stat_buffer;
  if (!fstat(fd, &stat_buffer) && S_ISCHR(stat_buffer.st_mode) &&
      ((stat_buffer.st_rdev == makedev(1, 8)) || (stat_buffer.st_rdev == makedev(1, 9)))) //Make sure we opened a random device
  {
    uint8_t buffer[40];
    ssize_t amount = insane_read(fd, buffer, sizeof(buffer)); //Grab as much data as we possibly can

    if (amount > 0)
    {
      if (amount < sizeof(buffer))
      {
        //Continue filling with other sources
      }
      //Do what needs to be done with random data...
      success = 1; //Yay!
    }
  }
  close(fd);
}

The Linux user manual page for the random devices explicitly informs the reader of these magic numbers, so hopefully they won't change. I have no official sources for the magic numbers on the other OSs. Now, you'll notice that I checked here that the file descriptor was open to either Linux random device. A system administrator may for some reason replace one with the other, so don't necessarily rely on a proper system using the expected device under the device name you're trying to use.

This brings us back to /dev/random versus /dev/urandom. Different OSs may implement these differently. On FreeBSD for example, there is only the former, and it is a CSPRNG. MirBSD offers five different random devices with all kinds of semantics, and who knows how a sysadmin may shuffle them around. On Linux and possibly others, /dev/urandom has a fatal flaw that in fact it may not be seeded properly, so blind usage of it isn't a good idea either. Thankfully Linux and NetBSD offer the following:

int data;
int result = ioctl(fd, RNDGETENTCNT, &data); //Upon success data now contains amount of entropy available in bits

This ioctl() call  will only work on a random device, so you can use this instead of the fstat() call on these OSs. You can then check data to ensure there's enough entropy to do what you need to:

int success = 0;
int fd = insane_open("/dev/urandom", O_RDONLY);
if (fd != -1)
{
  uint8_t buffer[40];
  int entropy;
  if (!ioctl(fd, RNDGETENTCNT, &entropy) && (entropy >= (sizeof(buffer) * 8))) //This ensures it's a random device, and there's enough entropy
  {
    ssize_t amount = insane_read(fd, buffer, sizeof(buffer)); //Grab as much data as we possibly can

    if (amount > 0)
    {
      if (amount < sizeof(buffer))
      {
        //Continue filling with other sources
      }
      //Do what needs to be done with random data...
      success = 1; //Yay!
    }
  }
  close(fd);
}

However, there may be a TOCTOU between the ioctl() and the read() call, I couldn't find any data on this, so take the above with a grain of salt. This also used to work on OpenBSD too, but they removed the ioctl() command RNDGETENTCNT a couple of versions back.

Linux has one other gem which may make you want to run away screaming. Look at the following from the manual for random device ioctl()s:

RNDZAPENTCNT, RNDCLEARPOOL
Zero the entropy count of all pools and add some system data (such as wall clock) to the pools.

If that last one does what I think it does, is any usage ever remotely safe?

/dev/(u)random conclusion

After all this, we now know the following:

• This is hardly an interface which is easy to use correctly (and securely).
• On some OSs there may not be any way to use it correctly (and securely).
• Applications not running with Superuser privileges may have no way to access the random device.
• An application at its file descriptor limit cannot use it.
• Many portability concerns.

For these reasons, OpenBSD created arc4random_buf() in the first place. It doesn't suffer from these above problems. The other BSDs also copied it, although they may be running on older less secure implementations.

Alternatives

In addition to a CSPRNG in userspace, the BSDs also allow for a way to get entropy directly from the kernel:

#define NUM_ELEMENTS(x) (sizeof(x)/sizeof((x)[0]))
uint8_t buffer[40];
size_t len = sizeof(buffer);
int mib[] = { CTL_KERN, KERN_RND };
int result = sysctl(mib, NUM_ELEMENTS(mib), buffer, &len, 0, 0);

KERN_RND may also be replaced with KERN_URND,  KERN_ARND, and others on the various BSDs. FreeBSD also has a similar interface to determine if the kernel's CSPRNG is properly seeded, see the FreeBSD user manual page for more details. DragonFlyBSD also provides read_random() and read_random_unlimited() as direct no-nonsense interfaces to the underlying devices for /dev/random and /dev/urandom.

Now Linux used to provide a similar interface as the BSDs:

#define NUM_ELEMENTS(x) (sizeof(x)/sizeof((x)[0]))
uint8_t buffer[40];
size_t len = sizeof(buffer);
int mib[] = { CTL_KERN, KERN_RANDOM, RANDOM_UUID };
int result = sysctl(mib, NUM_ELEMENTS(mib), buffer, &len, NULL, 0);

However, this interface was removed a couple of versions back. Kind of makes you wonder why there is no sane simple to use standardized API everywhere that doesn't depend on a house of cards. This is the kind of thing you would think would be standardized in POSIX.

Conclusion

There does not seem to be any good cross-platform techniques out there. Anything done with the current technology will probably require a ton of conditional compiles, annoying checks, and ridiculous workarounds. Although, there should be enough basis here to come up with something with a high confidence level. It'd be interesting to see what the LibreSSL team (or the OpenSSH team) comes up with when they get around to porting what's needed here. As I said before, until then, avoid the non-official ports out there, which use poor sources of entropy like an insecure use of /dev/urandom on Linux, which then falls back on gettimeofday(), and is used to generate long-lived keys.

Designing C++ functions to write/save to any storage mechanism

Problem

A common issue when dealing with a custom object or any kind of data is to create some sort of save functionality with it, perhaps writing some text or binary to a file. So what is the correct C++ method to allow an object to save its data anywhere?

An initial approach to allow some custom object to be able to save its data to a file is to create a member function like so:

void save(const char *filename);

While this is perfectly reasonable, what if I want something more advanced than that? Say I don't want the data to be saved as its own separate file, but would rather the data be written to some file that is already open, to a particular location within it? What if I'd rather save the data to a database? How about send the data over the network?

Naive Approach

When C++ programmers hear the initial set of requirements, they generally look to one of two solutions:

The first is to allow for a save function which can take an std::ostream, like so:

void save(std::ostream &stream);

C++ out of the box offers std::cout as an instance of an std::ostream which writes to the screen. C++ offers a derived class std::ofstream (std::fstream) which can save to files on disk. C++ also offers a derived class std::ostringstream which saves file to a C++ string.

With these options, you can display the data on the screen, save it to an actual file, or save it to a string, which you can then in turn save it wherever you want.

The next option programmers look to is to overload  std::basic_ostream::operator<< for the custom object. This way one can simply write:

mystream << myobject;

And then the object can be written to any C++ stream.

Either of these techniques pretty much work, but can be a bit annoying when you want a lot of flexibility and performance.

Say I wanted to save my object over the network, what do I do? I could save it to a string stream, grab the string, and then send that over the network, even though that seems a bit wasteful.

And for a similar case, say I have an already open file descriptor, and wish to save my object to it, do I also use a string stream as an intermediary?

Since C++ is extensible, one could actually create their own std::basic_streambuf derived class which works with file descriptors, and attach it to an std::ostream, which can then be used with anything that works with a stream for output. I'm not going to go into the details how to do that here, but The C++ Standard Library explains the general idea, and provides a working file descriptor streambuf example and shows how to use it with stream functions. You can also find some ready made implementations online with a bit of searching, and some compilers may even include a solution out of the box in their C++ extensions.

On UNIX systems, once you have a stream which works with file descriptors, you can now send data over the network, as sockets themselves are file descriptors. On Windows, you'll need a separate class which works with SOCKETs. Of course to turn a file descriptor streambuf into a SOCKET streambuf is trivial, and can probably be done with a few well crafted search and replace commands.

Now this may have solved the extra string overhead with file descriptors and networking, but what about if I want to save to a database? What about if I'm working with C's FILE *? Does one now have to implement a new wrapper for each of these (or pray the compiler offers an extension, or one can be found online)? The C++ stream library is actually a bit bloaty, and creating your own streambufs is somewhat annoying, especially if you want to do it right and allow for buffering. Many stream related library code you find online are also of poor quality. Surely there must be a better option, right?

Solution

If we look back at how C handles this problem, it uses function pointers, where the function doing the writing receives a callback to use for the actual writing, and the programmer using it can make the writing go anywhere. C++ of course includes this ability, and even takes it much further, in the form of function objects, and even further in C++ 2011.

Let's start with an example.

template<typename WriteFunction>
void world(WriteFunction func)
{
  //Do some stuff...
  //Do some more stuff...
  func("World", 5); //Write 5 characters via callback
  //Do some more stuff...
  unsigned char *data = ...;
  func(data, data_size); //Write some bytes
}

The template function above is expecting any function pointer which can be used to write data by passing it a pointer and a length. A proper signature would be something like the following:

void func(const void *data, size_t length);

Creating such a function is trivial. However, to be useful, writing needs to also include a destination of some sort, a device, a file, a database row, and so on, which makes function objects more powerful.

#include <cstdio>

class writer_file
{
  std::FILE *handle;
  public:
  writer_file(std::FILE *handle) : handle(handle) {}
  inline void operator()(const void *data, size_t length)
  {
    std::fwrite(data, 1, length, handle);
  }
};

Which can be used as follows:

world(writer_file(stdout));

Or perhaps:

std::FILE *fp = fopen("somefile.bin", "wb");
world(writer_file(fp));
std::close(fp);

As can be seen, our World function can write to any FILE *.

To allow any char-based stream to be written, the following function object will do the trick:

#include <ostream>

class writer_stream
{
  std::ostream *handle;
  public:
  writer_stream(std::ostream &handle) : handle(&handle) {}
  inline void operator()(const void *data, size_t length)
  {
    handle->write(reinterpret_cast<const char *>(data), length);
  }
};

You can call this with:

world(writer_stream(std::cout));

Or anything in the ostream family.

If for some reason we wanted to write to strings, it's easy to create a function object for them too, and we can use the string directly without involving a string stream.

#include <string>

class writer_string
{
  std::string *handle;
  public:
  writer_string(std::string &handle) : handle(&handle) {}
  inline void operator()(const void *data, size_t length)
  {
    handle->append(reinterpret_cast<const char *>(data), length);
  }
};

If you're worried about function objects being slow, then don't. Passing a function object like this to a template function has no overhead. The compiler is able to see a series of direct calls, and throws all the extraneous details away. It is as if the body of World is calling the write function to the handle passed to it directly. For more information, see Effective STL Item 46.

If you're wondering why developers forgo function pointers and function objects for situations like this, it is because C++ offers so much with its stream classes, which are also very extensible (and are often extended), they completely forget there are other options. The stream classes are also designed for formatting output, and working with all kinds of special objects. But if you just need raw writing or saving of data, the stream classes are overkill.

C++ 2011

Now C++ 2011 extends all this further in a multiple of ways.

std::bind()

First of all, C++ 2011 offers std::bind() which allows for creating function object adapters on the fly. std::bind() can take an unlimited amount of parameters. The first must be a function pointer of some sort, the next is optionally an object to work on in the case of a member function pointer, followed by the parameters to the function. These parameters can be hard coded by the caller, or bound via placeholders by the callee.

Here's how you would use std::bind() for using fwrite():

#include <functional>
world(std::bind(std::fwrite, std::placeholders::_1, 1, std::placeholders::_2, stdout));

Let us understand what is happening here. The function being called is std::fwrite(). It has 4 parameters. It's first parameter is the first parameter by the callee, denoted by std::placeholders::_1. The second parameter is being hard coded to 1 by the caller. The third parameter is the second parameter from the callee denoted by std::placeholders::_2. The fourth parameter is being hardcoded by the caller to stdout. It could be set to any FILE * as needed by the caller.

Now we'll see how this works with objects. To use with a stream, the basic approach is as follows:

world(std::bind(&std::ostream::write, &std::cout, std::placeholders::_1, std::placeholders::_2));

Note how we're turning a member function into a pointer, and we're also turning cout into a pointer so it can be passed as std::ostream::write's this pointer. The callee will pass its first and second parameters as the parameters to the stream write function. However, the above has a slight flaw, it will only work if writing is done with char * data. We can solve that with casting.

world(std::bind(reinterpret_cast<void (std::ostream::*)(const void *, size_t)>(&std::ostream::write), &std::cout, std::placeholders::_1, std::placeholders::_2));

Take a moment to notice that we're not just casting it to the needed function pointer, but as a member function pointer of std::ostream.

You might find doing this a bit more comfortable than using classical function objects. However, function objects still have their place, wherever functions do. Remember, functions are about re-usability, and some scenarios are complicated enough that you want to pull out a full blown function object.

For working with file descriptors, you might be tempted to do the following:

world(std::bind(::write, 1, std::placeholders::_1, std::placeholders::_2));

This here will have World write to file descriptor 1 - generally standard output. However this simple design is a mistake. Write can be interrupted by signals and needs to be resumed manually (by default, except on Solaris), among other issues, especially if the file descriptor is some kind of pipe or a socket. A proper write would be along the following lines:

#include <system_error>
#include <unistd.h>

class writer_fd
{
  int handle;
  public:
  writer_fd(int handle) : handle(handle) {}
  inline void operator()(const void *data, size_t length)
  {
    while (length)
    {
      ssize_t r = ::write(handle, data, length);
      if (r > 0) { data = static_cast<const char *>(data)+r; length -= r; }
      else if (!r) { break; }
      else if (errno != EINTR) { throw std::system_error(errno, std::system_category()); }
    }
  }
};

Lambda Functions

Now you might be wondering, why C++ 2011 stopped with std::bind(), what if the function body needs more than just a single function call that can be wrapped up in an adapter? That's where lambda functions come in.

world([&](const void *data, size_t length){ std::fwrite(data, 1, length, stdout); });
world([&](const void *data, size_t length){ std::cout.write(static_cast<const char *>(data), length); });

Note the ridiculous syntax. The [](){} combination signifies we are working with a lambda function. The [] receives a function scope, in this case &, which means that the function operates fully within its parent-scope, and has direct access to all its data. The rest you should already be well familiar with. You can change the stdout or the cout in the body of the lambda function to use your FILE * or ostream as necessary.

Let us look at an example of having our World function write directly to a buffer.

#include <cstring>

void *p = ...; //Point p at some buffer which has enough room to hold the contents needed to be written to it.
world([&](const void *data, size_t length){ std::memcpy(p, data, length); p = static_cast<char *>(p) + length; });

There's a very important point in this example. There is a pointer which is initialized to where writing should begin. Every time data is written, the pointer is incremented. This ensures that if World calls the passed write function multiple times, it will continue to work correctly. This was not needed for files above, as their write pointer increments automatically, or with std::string, where append always writes to the end, wherever it now is.

Be careful writing like this though, you must ensure in advance that your buffer is large enough, perhaps if your object has a way of reporting how much data the next call to its save or write function needs to generate. If it doesn't and you're winging it, something like the following is in order:

#include <stdexcept>

class writer_buffer
{
  void *handle, *limit;
  public:
  writer_buffer(void *handle, size_t limit) : handle(handle), limit(static_cast(handle)+limit) {}
  inline void operator()(const void *data, size_t length)
  {
    if ((static_cast<char *>(handle) + length) > limit) { throw std::out_of_range("writer_buffer"); }
    std::memcpy(handle, data, length);
    handle = static_cast<char *>(handle) + length;
  }
};

You can use it as follows:

#include <cstdlib>

size_t amount = 1024; //A nice number!
void *buffer = std::malloc(amount);
world(writer_buffer(buffer, amount));

Now an exception will be thrown if the callee tries to write more data than it should.

std::function

Lastly, C++ 2011 added the ability for more verbose type checking on function objects, and the ability to create the save/write function as a normal function as opposed to a template function. That ability is a general reusable function object facade, std::function.

To rewrite World to use it, we'd do as follows:

void world(std::function<void (const void *, size_t)> func)
{
  //Do some stuff...
  //Do some more stuff...
  func("World", 5); //Write 5 characters via callback
  //Do some more stuff...
  unsigned char *data = ...;
  func(data, data_size); //Write some bytes
}

With std::function, the type is now made explicit instead of being a template. It is anything which receives any kind of buffer and its length, and returns nothing. This can ensure that callers will always use a compatible function as intended by the library designer. For example, in our case, the caller only needs to ensure that data can be passed via a char * and an unsigned char *, based on how World uses the callback function. If World was now modified to also output an int *, less capable callers would now break. std::function can ensure that things are designed properly up front. With std::function, you can now also restructure your code to place various components in different compilation units if you so desire, although perhaps at a performance penalty.

Conclusion

To wrap up, you should now understand some features of C++ that are not as commonly used, or some new features of C++ 2011 that you may not be familiar with. You should now also have some ideas about generic code which should help you improve code you write.

Many examples above were given only with one methodology, although they can be implemented with some of the others. For practice, try doing this yourself. Also try applying these ideas to other kinds of storage mechanisms not covered here, doing so should now be rather trivial for you.

Remember, while this was done with a few standard examples and for writing, it can be extended to all handles Win32 offers, or for reading, or for anything else.

Optimizing your file dialog

Recently, someone asked me why is it that the custom file dialogs in some programs I wrote are able to load a file list so much faster than the so called "native file dialogs" on those operating systems. The answer is that I optimized many areas of loading a file list, and displaying it. Today we'll look at some optimizations that can be performed, instead of using the most obvious approaches to most of the process.

1. Know your system calls for reading directory entries

   
   
   You'll want to create some sort of library around the native directory functions in order to use the most efficient path on each operating system. Operating systems vary widely in what they they provide.
   
   Sometimes you have multiple APIs, or a single API with many options you can turn on and off. Unless the provided API is in itself doing everything as efficiently as possible (such as efficiently returning the file names in a sorted matter), you'll want to use the lowest level API, or turn off all options it provides.
   
   If bidirectional or scanning options are provided, turn them off, as you'll want forward only. The overhead for some of these features can significantly slow down the process of obtaining a file list. Same goes for anything else that adds overhead.
   
   Be aware of what information is provided other than file names. Some OSs will return a structure which may also contain file size or file permissions alongside each file. If you're filtering by any of these, use the information directly there, instead of using an additional call to stat() or similar.
   
   
   In addition to the above, if you need to filter by file size or file permissions, and the API does not provide that information directly, avoid the need for concatenating strings to get your information. A call to stat() would require concatenating a file name onto the directory name if it's not in the current directory. If your OS provides for it, use fstatat() or similar instead (see "OpenGroup Extended API Set Part 2").
   



2. Process file names in an optimized manner

   
   Once you start getting back file name(s), before anything, determine the length of a file name, as all other operations will need to know the length. Pretty much every operating system / file system limits the length of a file name to 255 bytes, the length of that can fit in a single byte. Compute the length (if need be) and keep reusing this cache.
   
   If you want to do extension filtering, now is the time to do so. Do not use strrchr(), or anything of the sort to find where the extension begins (searching for a period). Functions like strrchr() will first travel to the end then look back, effectively being O(2N). Since you already know the length of the string, use an O(N) function to look back from the end. Perhaps even using one which can scan multiple bytes (whole CPU words) at a time.
   
   For extension filtering, the most common method is generally one that breaks down to a series of compares. Put a little more thought into your algorithm usage! Either sort your list of extensions and binary search it for a match, or use perfect hashing. In either case, make sure the sorting or hashing phase is performed just once.
   
   For copying the files names you want elsewhere, use memcpy() instead of strcpy() and similar. Don't forget to pass around the length for other uses too.
   




3. Use efficient data structures efficiently

   
   The next question is how to keep track of your list of files. The most two common ideas are to use a vector and just keep adding to it, or use a linked list. Both those solutions are wrong.
   
   A vector while great in theory, has some performance and memory issues. When a vector can no longer contain what is being added to it, it doubles in size. The doubling in size can cause up to 99% more allocation than is actually needed during the growing process, which also comes with a lot of copying around. This may suit many workloads, but won't always suit the file list workload well.
   
   A linked list on the other hand is one of the worst possible data structures you can use. Every entry has 100-200% extra overhead for pointers, and often means many series of allocations. Many small allocations leads to performance issues, and a lot of memory fragmentation.
   
   The solution I would recommend is either a tweaked vector, or a combination of a vector plus linked list. Tweaking a vector starts off with reserving a set amount of space up front. Have your vector by default start with room for say 512 entries, and only then grow as needed. When you see your vector is full, instead of doubling in size, reserve another 512 entries. Smaller requests are more likely to be fulfilled for a realloc() in the same location, than a doubling in size. Very large directories beyond this point also becomes increasingly rarer at each new milestone. On top of all this, have your program remember how many files were in each of the past 10 or so directories it looked in (with filtering options of course). Then when loading a directory you recently loaded in the past, you can allocate an amount which is usually just what you need, or only needs one more chunk allocated onto it. Keep in mind that most users will keep using the same few directories over and over again with each application.
   
   The combination of the vector and linked list would instead build a structure out of the two ideas combined. Create your array of 512 entries, along with a fill pointer and and linked list pointers. When your array is full, allocate another block of this structure as the next chain in the linked list. This ensures no need to ever reallocate, or copy data around during the growing phase. Of course keep a global pointer to the current link being filled, instead of iterating to it each time you add a new entry.
   
   Which of these two options you use depends on how you want to sort and display your files. Each data structure has pros and cons for different use cases. Before we get into that, know how to store your file names themselves.
   
   The above description was for the pointers to the arrays holding the file names, the file names should NOT have a separate block of allocated memory for each. That's inefficient. Instead allocate large chunks of memory, say 16KB each. Store your file names in this memory pool. Forget the silly trailing null if you can, store the length before the name itself. The two data structures explained above for containing lists of files will point into these pools. If a pool can't contain another entry you're about to add, allocate another 16KB chunk, point to it from the previous one, and start allocating in this new one. If the need for a new one was for a rare overly large file, say 230 bytes, when 200 bytes were free, you can implement an algorithm to save some overhead by seeing if the next couple of files fit into the end of any previous pools. The pools in general will probably waste less than your OSs malloc() for small file names, and you'll certainly get better performance. Deallocation will also be a quick (backwards) traversal for large chunks instead of many small ones.
   



4. Sort efficiently

   
   The first part of sorting is comparison. strcmp()/strncmp() is not the function to use. You want something based on memcmp() as that works faster thanks to having the length of the file name already cached. Of course that's only if you want standard sorting.
   
   If you want case insensitive sorting, other methods will have to be used. If you're only dealing with ASCII file names, and you're not worried about file names containing control characters or some symbols end up being of equal value, you can compare 4 bytes at a time or'ing each with 0x20202020 (0x2020202020202020 for 8 bytes at a time). You're probably out of luck otherwise for case insensitive, unless someone knows of any good tricks to use.
   
   If you need "natural sorting", where numbers are compared to each other, so file1 precedes file15, and file2 follows file1 not file15, there's a few implementations floating around online and most are just copies of one another. Sadly, the most popular one I see, which is present in two operating systems, and the native implementation in a particular programming language, happens to incorrectly handle numbers past a certain magnitude (did anyone even test the implementations or just accept them at face value?), and has a worse case of O(3N). So beware of what you use or base your code off of.
   
   I'd recommend something along these lines:
   

   
   int strnatbase(const char *s1, const char *s2)
   {
     for (; *s1; ++s1, ++s2) //No need to check s2, as we compare it to s1, and it won't equal if it's null
     {
       if (isdigit(*s1) && isdigit(*s2)) //If they're both digits, use this special handling
       {
         while (*s1 == '0') { ++s1; } while (*s2 == '0') { ++s2; } //First skip leading zeros
   
         register bool d1 = isdigit(*s1), d2 = isdigit(*s2); //Are we still in a run of digits for both strings?
         if (d1 != d2) { return(d1-d2); } //If for only one of them, return that as the difference
   
         for (; d1 && (*s1 == *s2); ++s2) { d1 = isdigit(*++s1); } //Keep going while we have matching digits
   
         d2 = isdigit(*s2); //If we broke the above loop because a single string ran out of digits
         if (d1 != d2) { return(d1-d2); } //Return that as the difference
   
         for (const char *p1 = s1, *p2 = s2; d1; ) //Otherwise, difference in the digits themselves, clarify magnitude
         {
           d1 = isdigit(*++p1); d2 = isdigit(*++p2); //First string to run out of digits first
           if (d1 != d2) { return(d1-d2); } //Will lose right here
         } //If loop breaks, both strings are out of digits, the difference found above will be handled below
       }
      if (NOT_EQUAL(*s1, *s2)) { break; } //In all other cases, fall through with difference in current position - if any
     }
     return(*s1-*s2);
   }
   
   

   
   Modify as necessary for unicode, and replace NOT_EQUAL() with your function (or macro) of choice for comparing two letters (accounting for case differences if you want).
   
   As for the sort functions themselves, it will depend on which data structure you chose. You'll probably want Quicksort for the vector. Make sure your Quicksort sorts the pointers to the data and not the data itself! Same for any sorting algorithm sorting this. Swapping pointers is quick and easy. For the latter structure, you might want Merge sort, or perhaps Smoothsort. What you choose can depend on several factors.
   
   You may or may not want to utilize threading. Depending on how you filter, the OS may be giving you mostly sorted file names which can also play a role in the algorithm you choose. In the case of the linked lists of arrays, you might want to sort each array with one algorithm, then sort the whole. If you're utilizing threading, you can begin sorting the array(s) as you're still obtaining files from the operating system, as disk reads are slower than memory reads (when the current directory contents is not (yet) cached by the OS).
   



5. Display directly

   
   This point is rather simple. Have your file dialog display entries directly from whichever data structure you chose, without copying anything around. Know that most existing file dialog routines provided by various libraries will not be compatible with the data structures described above. So roll your own, or choose structures which can be passed directly to your library.
   
   Another possibility is to copy entries as they fit in the dialog window. The dialog is unable to show an infinite amount of entries at once, so convert from your structure to its structure just for the current files being viewed. Update as scrolling is performed.
   



6. Search efficiently

   
   Many file dialogs provide the option to type in some characters, and the file dialog jumps to the first file that begins with those characters. Since your file dialog is sorted, use binary search. Some people don't realize this, but binary search can find more than just an exact match, binary search can also be used to find the transition from entries "less than" to "first equal match" (in other words, binary search can also be used to find the transition between entries before the first match and the first match itself). Use this to find the first matching file in O(log(N)).
   

This basically wraps up this discussion on how to optimize file dialogs. I once was annoyed that loading up a directory with 20,000 files in it on a particular OS with a particular file browser took a good torturesome 20-30 seconds. Now using my own, I can load a directory with 100,000 files in 1-2 seconds on the same setup.

Thoughts, improvements, complaints, and every other kind of comment is welcome. Be sure to comment if you take of these ideas to optimize your library or application. I'd love to hear about it.

Directory safety when working with paths

As we discussed in our previous two articles, we run into issues of thread safety when we try changing the path during a running program. Therefor, in addition to bypassing PATH_MAX problems, working around buffer issues thanks to implementing with C++, we would also love to implement our functions without ever calling chdir() and changing the working directory. We'll now look into how we can make changes to our implementation to avoid a chdir() call, along with the pros and cons of techniques UNIX operating systems provide us, as well as what they're lacking.

If one looks back at how we implemented getcwd(), they'll notice that we call chdir("..") for each step in our loop. We need this to sanitize the location for these three calls:

opendir(".")
lstat(entry->d_name, &sb)
stat(".", &sb)

To remove the need of changing directories, we can place the ".." paths directly into our calls to opendir(), lstat(), and stat(). Thanks to C++ Strings being dynamic, it makes it easy for us to manipulate paths for these situations properly. We'll also see that being clever, we can even avoid string manipulation for some of these cases. And if our OSs supplied enough functionality, without any string manipulation at all!

Here's how we can implement getcwd() based off our previous implementation, but without calls to chdir(), with key details highlighted:

bool getcwd(std::string& path)
{
  typedef std::pair<dev_t, ino_t> file_id;

  bool success = false;
  struct stat sb;
  if (!stat(".", &sb))
  {
    file_id current_id(sb.st_dev, sb.st_ino);
    if (!stat("/", &sb)) //Get info for root directory, so we can determine when we hit it
    {
      std::vector<std::string> path_components;
      file_id root_id(sb.st_dev, sb.st_ino);
      std::string up_path("..");

      while (current_id != root_id) //If they're equal, we've obtained enough info to build the path
      {
        bool pushed = false;
        DIR *dir = opendir(up_path.c_str());
        if (dir)
        {
          dirent *entry;
          up_path += "/";
          std::string::size_type after_slash = up_path.size();
          while ((entry = readdir(dir))) //We loop through each entry trying to find where we came from
          {
            if (strcmp(entry->d_name, ".") && strcmp(entry->d_name, ".."))
            {
              up_path.replace(after_slash, std::string::npos, entry->d_name);
              if (!lstat(up_path.c_str(), &sb))
              {
                file_id child_id(sb.st_dev, sb.st_ino);
                if (child_id == current_id) //We found where we came from, add its name to the list
                {
                  path_components.push_back(entry->d_name);
                  pushed = true;
                  break;
                }
              }
            }
          }

          if (pushed && !fstat(dirfd(dir), &sb)) //If we have a reason to contiue, we update the current dir id
          {
            current_id = file_id(sb.st_dev, sb.st_ino);
            up_path.replace(after_slash, std::string::npos, ".."); //Keep recursing towards root each iteration
          }

          closedir(dir);
        }
        if (!pushed) { break; } //If we didn't obtain any info this pass, no reason to continue
      }

      if (current_id == root_id) //Unless they're equal, we failed above
      {
        //Built the path, will always end with a slash
        path = "/";
        for (std::vector<std::string>::reverse_iterator i = path_components.rbegin(); i != path_components.rend(); ++i)
        {
          path += *i+"/";
        }
        success = true;
      }
    }
  }

  return(success);
}

First of all, we removed all the code related to saving the current directory when we started, since we don't need that information anymore. Our first major change is that we created a new C++ String called up_path, we'll use this variable to keep track of the path, initializing it to "..". then for each step through the loop, make it "../..", "../../.." and so on, till we reach the root. We use this to replace our calls to opendir() to "." as we were doing before.
At this point, we'll add a slash to the path, and keep track of the spot with the variable after_slash. Now in our read directory loop, we can replace whatever is after the slash with the filename in the directory to pass to lstat(), again bypassing the need to be in the same directory as the file when making the function call.
Now for the stat() call on the directory itself, we got a little interesting. Instead of doing a path manipulation trick again, we call fstat() on the file descriptor returned from dirfd() on the already open directly handle. Notice how the call to close directory has been moved to after the block of code, so the directory is still open. And of course it's all wrapped up nicely with appending ".." after the slash.

Noticing how we eliminated path manipulation for the last part, it would be nice to eliminate more of it, especially if anyone wants to port this C++ code to C. The good news is that on Solaris and Linux we can, and as soon as the "at" functions get standardized, we can use them on the other UNIX OSs too. You can read more about them in one of our previous articles, File Descriptors and why we can't use them.

Here's how we can use the at functions to eliminate the path manipulation needed for calling lstat(), with the differences highlighted:

bool getcwd(std::string& path)
{
  typedef std::pair<dev_t, ino_t> file_id;

  bool success = false;
  struct stat sb;
  if (!stat(".", &sb))
  {
    file_id current_id(sb.st_dev, sb.st_ino);
    if (!stat("/", &sb)) //Get info for root directory, so we can determine when we hit it
    {
      std::vector<std::string> path_components;
      file_id root_id(sb.st_dev, sb.st_ino);
      std::string up_path("..");

      while (current_id != root_id) //If they're equal, we've obtained enough info to build the path
      {
        bool pushed = false;
        DIR *dir = opendir(up_path.c_str());
        if (dir)
        {
          int dir_fd = dirfd(dir);
          dirent *entry;
          while ((entry = readdir(dir))) //We loop through each entry trying to find where we came from
          {
            if (strcmp(entry->d_name, ".") && strcmp(entry->d_name, "..") && !fstatat(dir_fd, entry->d_name, &sb, AT_SYMLINK_NOFOLLOW))
            {
              file_id child_id(sb.st_dev, sb.st_ino);
              if (child_id == current_id) //We found where we came from, add its name to the list
              {
                path_components.push_back(entry->d_name);
                pushed = true;
                break;
              }
            }
          }

          if (pushed && !fstat(dir_fd, &sb)) //If we have a reason to contiue, we update the current dir id
          {
            current_id = file_id(sb.st_dev, sb.st_ino);
            up_path += "/.."; //Keep recursing towards root each iteration
          }

          closedir(dir);
        }
        if (!pushed) { break; } //If we didn't obtain any info this pass, no reason to continue
      }

      if (current_id == root_id) //Unless they're equal, we failed above
      {
        //Built the path, will always end with a slash
        path = "/";
        for (std::vector<std::string>::reverse_iterator i = path_components.rbegin(); i != path_components.rend(); ++i)
        {
          path += *i+"/";
        }
        success = true;
      }
    }
  }

  return(success);
}

As should be easily discernible, the string manipulation got easier, and mostly vanished. All the keeping track of a slash, and replaces has been replaced with only needing to append "/.." at the end of each loop.
Instead of manipulating a path string for our call to lstat(), we save the directory's file descriptor above (and subsequently use that instead of recalculating it lower down for fstat()), then use it to get the lstat() for each file in the directory, but now via fstatat().
fstatat() is the same as stat()/lstat(), but takes a directory descriptor as the first parameter to offset where the filename is relative to. The last parameter can be 0 or AT_SYMLINK_NOFOLLOW, which makes it act like stat() or lstat() respectively. fstatat() instead of a file descriptor can also take the special value AT_FDCWD to have it automatically work in the current directory.

This implementation should be much more elegant, but a bit less portable. If one would like to implement fstatat() themselves, it's not hard, here's how you can do it:

int fstatat(int dirfd, const char *pathname, struct stat *buf, int flags)
{
  int success = -1;

  if ((!flags || (flags == AT_SYMLINK_NOFOLLOW)))
  {
    int cwdfd = -1;
    if ((dirfd == AT_FDCWD) || (pathname && (*pathname == '/')) || (((cwdfd=open(".", O_RDONLY)) != -1) && !fchdir(dirfd)))
    {
      success = (!flags) ? stat(pathname, buf) : lstat(pathname, buf);
    }

    if (cwdfd != -1)
    {
      fchdir(cwdfd);
      close(cwdfd);
    }
  }
  else
  {
    errno = EINVAL;
  }

  return(success);
}

You'll also need the defines for AT_FDCWD and AT_SYMLINK_NOFOLLOW. You have to make sure that the value you choose for AT_FDCWD can't be a valid file descriptor or the normal failure return value. Therefor I chose -2 in my implementations, but choosing any negative value should be okay. AT_SYMLINK_NOFOLLOW shouldn't matter what it is, and a value of 1 or for all I care, 42, should be fine.
If your OS supports the at functions (currently Linux 2.6.16+ and recent versions of Solaris), it's better not to use a custom implementation, as this isn't thread safe, since it calls fchdir() internally, and for our example, runs counter to the whole point of using fstatat(). It would also be faster to use the original getcwd() implementation from a few days ago than using an emulated fstatat(), since there's less overhead from repeated fchdir() calls.
It's also interesting to note that glibc on Linux now, even for older than 2.6.16 implements fstatat() and the whole slew of at functions even when not supported in the Kernel. It's similar to ours, can be thread unsafe due to changing the working directory, and for some inexplicable reason, segfaulted in certain circumstances when I ran a large battery of tests on it and my implementation against the Kernel's to make sure that mine was working properly.

Anyways, with that out of the way, one can't hope but wonder if it would be possible to also eliminate the need of any path string manipulation for the call to opendir(). Mysteriously, neither Solaris nor Linux have an opendirat() call. If there was such, we could easily keep the previous directory open, till we obtained a new handle for its parent directory.
Baring having an opendirat() function, it'd be nice to implement such a thing. Some UNIX OSs I understand have a function perhaps named fopendir() or fdopendir() to promote a file descriptor to a directory handle. With such a function, we can simply write an opendirat() which calls openat(), then promotes it, but Linux doesn't have a method of promotion, although Solaris does (fdopendir()). Lets hope the people who are standardizing the new at functions for POSIX seriously consider what they're doing, otherwise we won't be able to use them.

Now that we've gotten getcwd() to be safe, we still need realpath() to be. In our realpath() implementation, the only unsafe parts was our function chdir_getcwd() which called chdir() internally as well as getcwd(). getcwd() is now taken care of, but we still need to rewrite the rest of chdir_getcwd() to not actually chdir().
To do such should now be easy, we simply do getcwd(), but with a new start path. We'd make a new function called getcwd_internal() which would take two parameters, one for the current directory, and another to initialize the up one, which we can wrap everything else around. Basically copy your favorite getcwd(), but make the modifications to the beginning like so:

bool getcwd_internal(std::string& path, const std::string& start_dir, std::string& up_path)
{
  typedef std::pair<dev_t, ino_t> file_id;

  bool success = false;
  struct stat sb;
  if (!stat(start_dir.c_str(), &sb))
  {
    file_id current_id(sb.st_dev, sb.st_ino);
    if (!stat("/", &sb)) //Get info for root directory, so we can determine when we hit it
    {
      std::vector<std::string> path_components;
      file_id root_id(sb.st_dev, sb.st_ino);

      while (current_id != root_id) //If they're equal, we've obtained enough info to build the path
--SNIP--

Now we'd turn getcwd() and chdir_getcwd() into wrappers like so:

bool getcwd(std::string& path)
{
  std::string up_path("..");
  return(getcwd_internal(path, ".", up_path));
}

bool chdir_getcwd(const std::string& dir, std::string& path)
{
  std::string up_path(dir+"/..");
  return(getcwd_internal(path, dir, up_path));
}

Note that the name of chdir_getcwd() is now misleading that it doesn't actually change directories anymore. For this reason, it's a good idea to not put any implementation details into a function name, as a user shouldn't have to know about them, and over time, it can become inaccurate.

And there you have it folks, getcwd() and realpath() implemented safely. Hopefully in the process all you loyal readers learned a couple other things too.

Other improvements over all we discussed, might be to run a smart pass over concatenated path names at key locations to remove extra slashes together "///", unneeded current directory "/./", and extra parent directories "path1/path2/.." -> "path1/", which is useful if certain functions like opendir() or the stat() family of calls have internal buffer issues. But doing such is a discussion for another time.

This wraps up our long discussion. All comments and suggestions are welcome.

Implementing realpath() in C++

Before reading this post, please read the background in the previous post PATH_MAX simply isn't, as it covers important background, and has some code we'll be building on over here.

Here's what realpath() is supposed to do:

realpath() expands all symbolic links and resolves references to ’/./’, ’/../’ and extra ’/’ characters in the null terminated string named by path and stores the canonicalized absolute pathname in the buffer of size PATH_MAX named by resolved_path. The resulting path will have no symbolic link, ’/./’ or ’/../’ components.

Instead of attacking implementing such a thing head on, we'll take a bottom up approach. One should consider that being able to break down a path between the path components prior to the last slash and after the last slash is essential to figuring out which directory the file actually lies.

The built in functions for this are called dirname() and basename(), but they modify their arguments, and they do some funny handling in special cases which we don't want.

So to implement our own for our purposes, we can write a function as follows:

void relative_dir_base_split(const std::string& path, std::string& dir, std::string& base)
{
  std::string::size_type slash_pos = path.rfind("/"); //Find the last slash
  if (slash_pos != std::string::npos) //If there is a slash
  {
    slash_pos++;
    dir = path.substr(0, slash_pos); //Directory is before slash
    base = path.substr(slash_pos); //And obviously, the file is after
  }
  else //Otherwise, there is no directory present
  {
    dir.clear(); 
    base = path;
  }
}

The function is simple enough, pass it a path, and two C++ strings for the return values, and have it split them up.

The next function which we'll use is one to get the realpath() of a directory. We can easily get such a thing by chdir()'ing to the directory, running our getcwd(), and then chdir() back.
This simple function is as follows:

bool chdir_getcwd(const std::string& dir, std::string& path)
{
  bool success = false;
  int start_fd = open(".", O_RDONLY); //Open current directory so we can save a handle to it
  if (start_fd != -1)
  {
    if (!chdir(dir.c_str())) //Change to directory
    {
      success = getcwd(path); //And get its path
      fchdir(start_fd); //And change back of course
    }
    close(start_fd);
  }
  return(success);
}

This simple function to resolve where a directory is located uses should be obvious, however, it's also a core function in figuring our where a file is, since a file is located at the realpath() of its parent directory, plus the base name for the file itself.

Now to get the realpath() of a file, we have this simple wrapper over the above functions:

static inline bool realpath_file(const std::string& path, std::string& resolved_path)
{
  bool success = false;
  std::string dir;
  std::string base;
  relative_dir_base_split(path, dir, base);

  //If there is a directory, get the realpath() for it, otherwise the current directory
  if (dir.size() ? chdir_getcwd(dir, resolved_path) : getcwd(resolved_path))
  {
    resolved_path += base;
    success = true;
  }
  return(success);
}

Now we have chdir_getcwd() which is basically a realpath() for a directory, and realpath_file() for files. Note however, that if you call realpath_file() directly, it won't actually ensure that the file exists, so probably a bad idea to call directly, unless you don't care if it exists or not. It also won't handle symlinks. To handle symlinks we need quite a bit more code.

First, let us write a wrapper in C++ for reading links:

bool readlink_internal(const std::string& path, std::string& buffer, ssize_t length)
{
  bool success = false;
  if (length > 0)
  {
    char *buf = new(nothrow) char[length+1]; //Room for Null
    if (buf)
    {
      ssize_t amount = ::readlink(path.c_str(), buf, length+1); //Give room for failure
      if ((amount > 0) && (amount <= length)) //If > length, it was modified mid check
      {
        buf[amount] = 0;
        buffer = buf;
        success = true;
      }
      delete[] buf;
    }
  }
  return(success);
}

This function simply wraps up the built in one, and uses C++ strings for dynamic allocation, so we don't have to worry about it directly in our function to resolve symlinks.

Before diving into the actual details in resolving a symlink, let me present one more helper function:

void build_path_base_swap(std::string &path, const std::string& newbase)
{
  string dir;
  string base;
  relative_dir_base_split(path, dir, base);

  if (dir.size())
  {
    path = dir + newbase;
  }
  else
  {
    path = newbase;
  }
}

This above function will take a path, and replace the base part of it, meaning if you pass it "path/cows.txt" and "feet.txt", path will become "path/feet.txt".

Now onto the symlink discussion.

Resolving symlinks in itself is hard though, since one symlink could lead to another, meaning we'll need a loop. We also need to defend ourselves against an infinite loop if one symlink links to itself, or a symlink earlier on in our resolve loop.

It is not safe enough to call a regular stat() to check for the final link existing (and not a loop), since during our resolve, an attacker can modify a link, so we have to detect that.
Unfortunately, most OSs/libraries have a define called MAXSYMLINKS which I've seen set anywhere from 8 to 30. They stop their loop once they've iterated MAXSYMLINKS times and return an errno of ELOOP. Unfortunately, doing such has two flaws, which I hope should be apparent. First of all, if a link links to itself immediately, it would take MAXSYMLINKS passes until the function finally realizes it (I'm looking at you OpenBSD). The other issue is that it's just wrong.
Hopefully any of us who has taken a data structures course would know that there are algorithms for detecting a loop in a linked list, and not have to resort to any dumb method which doesn't actually detect a loop. Also a number such as 8 is way too low which I've seen some do. I look at one of my Linux boxes, and I see some binaries are actually symlinked a dozen times. Like "upx" is symlinked to "upx-3.00", which is symlinked to "upx-3.00-nonfree", which is symlinked to, etc...

The optimal way to detect a loop in a linked list is explained here, see the last paragraph for the optimal O(N) solution. Unfortunately though, the optimal solution means we need to create a second iterator to check on symlinks, resolving links ahead of the main loop, two at a time. While great in memory, it can be a pain on a hard drive, where we have to deal with slow access, and the links can change during the check. Therefor I settled on a variation of the first solution, where we'll keep track of the file IDs (described in the previous post) of each symlink, and see if we ever hit a match. We'll store this data in an std::set, which is usually implemented as a Red & Black Tree which has O(log(N)) time for insertion and searching. Making our algorithm work at O(log(N))*2 (since we insert and find each time) * N, which reduces to O(N log(N)).

Here's the code:

bool symlink_resolve(const std::string& start, std::string& end)
{
  typedef std::pair<dev_t, ino_t> file_id;

  bool success = false;
  if (start.size())
  {
    std::string path = start; //Need a modifyable copy
    struct stat sb;
    std::set<file_id> seen_links;

    bool resolved_link;
    do //The symlink resolve loop
    {
      resolved_link = false;
      if (!lstat(path.c_str(), &sb))
      {
        file_id current_id(sb.st_dev, sb.st_ino);
        if (seen_links.find(current_id) == seen_links.end()) //Not a link we've seen
        {
          seen_links.insert(current_id); //Add to our set

          if (S_ISLNK(sb.st_mode)) //Another link
          {
            std::string newpath;
            if (readlink_internal(path, newpath, sb.st_size))
            {
              if (newpath[0] == '/') //Absolute
              {
                path = newpath;
              }
              else //We need to calculate the relative path in relation to the current
              {
                build_path_base_swap(path, newpath);
              }
              resolved_link = true;
            } //Else, Link can't be read, time to quit
          }
          else //Yay, it's not a link! got to the last part finally!
          {
            success = realpath_file(path, end);
          }
        } //Else, Nice try, someone linked a link back into a previous link during the scan to try to trick us into an infinite loop
      } //Else, Dangling link, can't resolve
    } while (resolved_link);
  }
  return(success);
}

And now with all those helper functions out of the way, we can finally write the actual realpath() function itself, and it's a heck of a lot simpler than other implementations you'll find out there.

Here it is:

bool realpath(const std::string& path, std::string& resolved_path, bool resolve_link = true)
{
  bool success = false;
  if (path.size())
  {
    struct stat sb;
    if (!stat(path.c_str(), &sb))
    {
      bool (*rp)(const std::string&, std::string&) = resolve_link ? symlink_resolve : realpath_file;
      success = S_ISDIR(sb.st_mode) ? chdir_getcwd(path, resolved_path) : rp(path, resolved_path);
    }
  }
  return(success);
}

It simply stat()s then runs chdir_getcwd() on directories and symlink_resolve() on files. I also offer an added feature. If you don't want the file name itself resolved, which is quite often what people want when a program saves a new file based off a name of another files passed to it, you can pass false as the third parameter, and it'll call realpath_file() instead of symlink_resolve(). With this wrapper, realpath_file() also has a stat() call before it, so the file is checked for existence like the built in realpath().

This implementation protects against the issues of PATH_MAX as described in our previous posts. It's also written in C++ to avoid buffer issues. Unlike built in ones, we generally have faster realpath() on directory, since it uses a getcwd() technique, while most other ones out there use a complicated set of steps on every component in the path until the last one is reached, which is especially slow if there are symlinks in the path. We also beat the built in ones regarding speed in cases of link to self, and have support for a deeper set of links. Some implementations also have some fixed sized buffer which can easily get full, and return failure, which is annoying, but our implementation won't run into. Lastly, we offer not resolving the links at all on the last component.

Drawbacks to our implementation is that it won't work on Windows as described in our last post. But you can #ifdef for that, and easily enough wrap around fullpath(). It also isn't thread safe due to the use of chdir() (which many built in implementations also do), see the previous post on how to work around that. Next time, we'll discuss methods to do all this without a chdir() at all, thus ensuring thread safety without any headaches.