Saturday, November 3, 2007


PATH_MAX simply isn't



Many C/C++ programmers at some point may run into a limit known as PATH_MAX. Basically, if you have to keep track of paths to files/directories, how big does your buffer have to be?
Most Operating Systems/File Systems I've seen, limit a filename or any particular path component to 255 bytes or so. But a full path is a different matter.

Many programmers will immediately tell you that if your buffer is PATH_MAX, or PATH_MAX+1 bytes, it's long enough. A good C++ programmer of course would use C++ strings (std::string or similar with a particular API) to avoid any buffer length issues. But even when having dynamic strings in your program taking care of the nitty gritty issue of how long your buffers need to be, they only solve half the problem.

Even a C++ programmer may at some point want to call the getcwd() or realpath() (fullpath() on Windows) functions, which take a pointer to a writable buffer, and not a C++ string, and according to the standard, they don't do their own allocation. Even ones that do their own allocation very often just allocate PATH_MAX bytes.

getcwd() is a function to return what the current working directory is. realpath() can take a relative or absolute path to any filename, containing .. or levels of /././. or extra slashes, and symlinks and the like, and return a full absolute path without any extra garbage. These functions have a flaw though.

The flaw is that PATH_MAX simply isn't. Each system can define PATH_MAX to whatever size it likes. On my Linux system, I see it's 4096, on my OpenBSD system, I see it's 1024, on Windows, it's 260.

Now performing a test on my Linux system, I noticed that it limits a path component to 255 characters on ext3, but it doesn't stop me from making as many nested ones as I like. I successfully created a path 6000 characters long. Linux does absolutely nothing to stop me from creating such a large path, nor from mounting one large path on another. Running getcwd() in such a large path, even with a huge buffer, fails, since it doesn't work with anything past PATH_MAX.

Even a commercial OS like Mac OS X defines it as 1024, but tests show you can create a path several thousand characters long. Interestingly enough, OSX's getcwd() will properly identify a path which is larger than its PATH_MAX if you pass it a large enough buffer with enough room to hold all the data. This is possible, because the prototype for getcwd() is:
char *getcwd(char *buf, size_t size);


So a smart getcwd() can work if there's enough room. But unfortunately, there is no way to determine how much space you actually need, so you can't allocate it in advance. You'd have to keep allocating larger and larger buffers hoping one of them will finally work, which is quite retarded.

Since a path can be longer than PATH_MAX, the define is useless, writing code based off of it is wrong, and the functions that require it are broken.

An exception to this is Windows. It doesn't allow any paths to be created larger than 260 characters. If the path was created on a partition from a different OS, Windows won't allow anything to access it. It sounds strange that such a small limit was chosen, considering that FAT has no such limit imposed, and NTFS allows paths to be 32768 characters long. I can easily imagine someone with a sizable audio collection having a 300+ character path like so:
"C:\Documents and Settings\Jonathan Ezekiel Cornflour\My Documents\My Music\My Personal Rips\2007\Technological\Operating System Symphony Orchestra\The GNOME Musical Men\I Married Her For Her File System\You Don't Appreciate Marriage Until You've Noticed Tax Pro's Wizard For Married Couples.Track 01.MP5"


Before we forget, here's the prototype for realpath:
char *realpath(const char *file_name, char *resolved_name);


Now looking at that prototype, you should immediately say to yourself, but where's the size value for resolved_name? We don't want a buffer overflow! Which is why OSs will implement it based on the PATH_MAX define.
The resolved_name argument must refer to a buffer capable of storing at least PATH_MAX characters.

Which basically means, it can never work on a large path, and no clever OS can implement around it, unless it actually checks how much RAM is allocated on that pointer using an OS specific method - if available.

For these reasons, I've decided to implement getcwd() and realpath() myself. We'll discuss the exact specifics of realpath() next time, for now however, we will focus on how one can make their own getcwd().

The idea is to walk up the tree from the working directory, till we reach the root, along the way noting which path component we just went across.
Every modern OS has a stat() function which can take a path component and return information about it, such as when it was created, which device it is located on, and the like. All these OSs except for Windows return the fields st_dev and st_ino which together can uniquely identify any file or directory. If those two fields match the data retrieved in some other way on the same system, you can be sure they're the same file/directory.
To start, we'd determine the unique ID for . and /, once we have those, we can construct our loop. At each step, when the current doesn't equal the root, we can change directory to .., then scan the directory (using opendir()+readdir()+closedir()) for a component with the same ID. Once a matching ID is found, we can denote that as the correct name for the current level, and move up one.

Code demonstrating this in C++ is as follows:


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

bool success = false;
int start_fd = open(".", O_RDONLY); //Keep track of start directory, so can jump back to it later
if (start_fd != -1)
{
struct stat sb;
if (!fstat(start_fd, &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
{
bool pushed = false;

if (!chdir("..")) //Keep recursing towards root each iteration
{
DIR *dir = opendir(".");
if (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, "..") && !lstat(entry->d_name, &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;
}
}
}
closedir(dir);

if (pushed && !stat(".", &sb)) //If we have a reason to contiue, we update the current dir id
{
current_id = file_id(sb.st_dev, sb.st_ino);
}
}//Else, Uh oh, can't read information at this level
}
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;
}
fchdir(start_fd);
}
}
close(start_fd);
}

return(success);
}


Before we accept that as the defacto method to use in your application, let us discuss the flaws.

As mentioned above, it doesn't work on Windows, but a simple #ifdef for Windows can just make it a wrapper around the built in getcwd() with a local buffer of size PATH_MAX, which is fine for Windows, and pretty much no other OS.

This function uses the name getcwd() which can conflict with the built in C based one which is a problem for certain compilers. The fix is to rename it, or put it in its own namespace.

Next, the built in getcwd() implementations I checked only have a trailing slash on the root directory. I personally like having the slash appended, since I'm usually concatenating a filename onto it, but note that if you're not using it for concatenation, but to pass to functions like access(), stat(), opendir(), chdir(), and the like, an OS may not like doing the call with a trailing slash. I've only noticed that being an issue with DJGPP and a few functions. So if it matters to you, the loop near the end of the function can easily be modified to not have the trailing slash, except in the case that the root directory is the entire path.

This function also changes the directory in the process, so it's not thread safe. But then again, many built in implementations aren't thread safe either. If you use threads, calculate all the paths you need prior to creating the threads. Which is probably a good idea, and keep using path names based off of your absolute directories in your program, instead of changing directories during the main execution elsewhere in the program. Otherwise, you'll have to use a mutex around the call, which is also a valid option.

There could also be the issue that some level of the path isn't readable. Which can happen on UNIX, where to enter a directory, one only needs execute permission, and not read permission. I'm not sure what one can do in that case, except maybe fall back on the built in one hoping it does some magical Kernel call to get around it. If anyone has any advice on this one, please post about it in the comments.

Lastly, this function is written in C++, which is annoying for C users. The std::vector can be replaced with a linked list keeping track of the components, and at the end, allocate the buffer size needed, and return the allocated buffer. This requires the user to free the buffer on the outside, but there really isn't any other safe way of doing this.
Alternatively, instead of a linked list, a buffer which is constantly reallocated can be used while building the path, constantly memmove()'ing the built components over to the higher part of the buffer.

During the course of the rest of the program, all path manipulation should be using safe allocation managing strings such as std::string, or should be based off of the above described auto allocating getcwd() and similar functions, and constantly handling the memory management, growing as needed. Be careful when you need to get any path information from elsewhere, as you can never be sure how large it will be.

I hope developers realize that when not on Windows, using the incorrect define PATH_MAX is just wrong, and fix their applications. Next time, we'll discuss how one can implement their own realpath().

5 comments:

Dan said...

Hey, good to see you're finally back from your extended vacation. Bet the kids loved it, I know I always loved Disney World as a kid (hope they didn't make you go on "It's a Small World" too many times, that gets annoying after a while). Anyway, what you said about windows reminds me of a trick I used in high school to hide files on the school's network. I'd basically create a path as long as it would allow, put my games or whatever other forbidden files in there, and move the entire path once more into a new directory. Then when they tried to see what was in there, all they'd get is a recurrence of "New Folder/New Folder/New Folder/"etc. until they couldn't open it. It also wouldn't delete IIRC, and they weren't smart enough to realize to move it one level up, which is, of course, the method by which I would access my files there.

As for your wife's filesystem, what's she running? ReiserFS V5? Ext7? FAT4096? It's gotta be something cool if you're ripping mp5s.

The problem with PATH_MAX though, is that it's like a great sports play. You can't just rush into the score zone, you'd get a buffer overflow! But rather than implementing it sanely in a manner that you pass a buffer and a size, they decided to make their own number that has no relation whatsoever to the actual max path length. Sure, you could say something like "no one could possibly need a path longer than X", but we saw how well that worked when Gates Almighty stated that "640K ought to be enough for anybody". You just never know how much of anything will be enough for someone, and therein lies the flaw in many aspects of computing today.

In closing, stupid people suck.

L3thal said...

great topic , great explanation :)

fantastico said...

Windows allows approx 32k Unicode chars for the whole concatenated path, so long as:
1. You call the Unicode ('W') APIs rather than the OEM ('A') ones, eg CreateFileW; AND
2. You prepend the magic string '\\?\' to your path; AND
3. Your path is absolute or UNC, rather than relative.

I know this is wierd and sounds unlikely, but I've personally written a test program to exercise this bizarre feature.

MS documentation here:
http://msdn.microsoft.com/en-us/library/aa365247%28VS.85%29.aspx#maxpath

For extra kicks, you can also do:
\\?\UNC\myhostname\mysharename\my\big\long\sequence\of\subdirs

fantastico said...

Dan: the problem with PATH_MAX is not stupidity of the designers. It's the history of UNIX. Please don't accuse the designers of stupidity without doing some research first.

Modern *NIXes support multiple filesystem types simultaneously, each one with its own values for its own limits of various kinds.

Worse, most modern *NIXes support something like loadable kernel filesystem modules. So now entire types of filesystem can come and go at the whim of the sysadmin.

Given this, the idea of a single, static max-length number is wrong, regardless of its value. But that does not mean that those who came up with the idea were stupid.

Back in the day, UNIX had none of these features. In those days, the PATH_MAX concept was:
a) sufficient for then purposes;
b) simple for people to code to (compare modern sysconf);
b. Could be implemented efficiently on a PDP-11.

These were the times when malloc() performance sucked, so it was to be avoided at almost any cost - including static buffers with no bounds checking.

In closing, judgemental ignorant people suck, and they make themselves look silly when they spout off on other peoples' blogs.

Lisa Nek said...

Impressive one. I will like to share a thing about this that my problem of copying and moving of ling path file solved by suing long path tool. I Suggest everyone to try this.