Why doesn't readdir () system call work the way it should (unexpected output)?

Question

I am writing a C program like,

void printdir (char*);

int main () {
    printf ("Directory scan of /home: \n");
    printdir ("/home/fahad/");
    exit (0);
}

void printdir (char *dir) {
    struct dirent *entry;
    DIR *dp = opendir (dir);

    if (dp == NULL) {
        fprintf (stderr, "Cannot open dir:%s\n", dir);
        return;
    }

    chdir (dir);
    while ((entry = readdir(dp)) != NULL)
        printf ("%s\n",entry -> d_name);
    closedir (dp);
}

Interestingly, it shows output in an unexpected way. Considering the fact that whenever a directory is created in UNIX. First two entries are created inside this directory one is . and other is ... So basically their inode numbers should be less than the directory entries created through mkdir () or open () (for directory and file respectively).

My question is, in what order readdir () system call reads the directory entries? Because I don't get first who entries . and ... Why is that so?

Answer 1

readdir() doesn't return entries in any particular order. As others mentioned, the order will depend on the particular file system in question.

For example, the Berkeley UFS file system uses an unsorted linked-list. See the description of the direct structure on page 744 of http://ptgmedia.pearsoncmg.com/images/0131482092/samplechapter/mcdougall_ch15.pdf. The binary content of a directory consists of a stream of variable-length records, each of which contains the inode number, record length, string length (of the filename) and the string data itself. readdir() works by walking the linked list (using the record length to know where each record begins relative to the previous record) and returning whatever it finds.

The list of records is not typically optimized, so filenames appear on the list (more or less) in the order the files were created. But not quite, because holes (resulting from deleted files) will be filled with new filenames if they are small enough to fit.

Now, not all file systems represent directories the way UFS does. A file system that keeps directory data in a binary tree may choose to implement readdir() as an in-order traversal of that tree, which would present files sorted by whatever attributes it uses as key for the tree. Or it might use a pre-order traversal, which would not return the records in a sorted order.

Because applications can not know the nature of the file system's implementation (and that each mounted volume can potentially use a different file system), applications should never assume anything about the order of entries that readdir() returns. If they require the entries to be sorted, they must read the entire directory into memory and do their own sorting.

This is why, for example, the ls command can take a long time to display output when run against a large directory. It needs to sort the entire list of names (and determine the longest name, in order to compute the column width) before it can display any output. This is also why ls -1U (disable sorting and display in one column) will produce output immediately on such directories.

Answer 2

Try skipping the "." and ".." entries, as follows:

DIR* dirp;
struct dirent  *dp=NULL;
char* fname;
if( !(dirp=opendir(dname)) ) {
    int ec=errno;
    printf("completed:-1:cannot opendir %s (%d)\n",dname,ec);
    return(-1);
}
while ((dp = readdir(dirp)) != NULL) {
    if( strcmp(dp->d_name,".")==0 ) continue;
    if( strcmp(dp->d_name,"..")==0 ) continue;
    fname=dp->d_name;
    sprintf(pathname,"%s/%s",dname,fname);
}

See this answer which notes that since the order is not stated as predictable, one should not assume any order. The above code will gives a sample of how to handle (avoid) these entries (in the typical use-case of traversing a directory hierarchy). The order is probably based upon the order of the files appearing in the directory inodes.

Answer 3

First two entries are created inside this directory one is . and other is ... So basically their inode numbers should be less than the directory entries created through mkdir () or open ()(for directory and file respectively).

Yes, your understanding about the inode numbers is correct. To validate this we can write simple c++ program to store the inode/name in map.

 std::map<ino_t, std::string>  entries;
 std::pair<ino_t, std::string> en;
 while ((entry = readdir(dp)) != NULL) {
          en.first = entry->d_ino;
          en.second = entry->d_name;
          entries.insert(en);
        printf ("%s\n",entry -> d_name);
  }


  "entries in GDB"
  ================
  [5114862] = "..",
  [5114987] = ".",
  [5115243] = "taop",
  [5115623] = "c++11_study",
  [5115651] = "volume-3",
  [5115884] = "gtkmm",
  [5116513] = "basic",
  [5116733] = "program",
  [5116794] = "bakwas",
  [5116813] = "a.out",
  [5116818] = "foo",

This way we can validate about the order of inode number and "." & ".." are the less than other directory & file entry.

My question is, in what order readdir () system call reads the directory entries? Because I don't get first who entries . and ... Why is that so?

From The Book "Advanced Programming in the UNIX® Environment by W. Richard Stevens", we can get the following:

The opendir function initializes things so that the first readdir reads the first entry in the directory. The ordering of entries within the directory is implementation dependent and is usually not alphabetical. So their order are not defined and for the above program, readdir() gave in the following order.

Output from readdir()
=====================
c++11_study
taop
volume-3
basic
.
gtkmm
foo
program
a.out
..
bakwas