Union Mount: Directory listing in glibc

Hi,

I went through Bharata's RFC post on glibc based Union Mount readdir solution
(http://lkml.org/lkml/2008/3/11/34) and have come up with patches against glibc to implement the same.

The RFC discussed about the information glibc readdir needs to get about union mounted directories and I have assumed the following information to be available from the kernel for this implementation.

- Kernel would return all the dirents (including duplicates and whiteouts) starting from the topmost directory of the union.

- Indication that this directory is a union mounted directory
I have assumed that kernel would return a "." whiteout as the first
directory entry of the union. This would tell glibc readdir(3) that it is working with a union mounted directory and it needs to do duplicate elimination and whiteout suppression. It starts building a dirent cache for this purpose.

Ulrich had suggested that we could use the fstat call to recognize union mounts. But looking at the stat structure from stat(2), it was not obvious as to which field in there could be used for this purpose. Hence for this prototype implementation, I decided to go with what Al Viro suggested, which is about using a "." whiteout.

- Indication that kernel is done with returning entries from the topmost directory.
I have assumed that kernel would return a "." whiteout at the beginning
of each directory of the union. So when glibc gets a 2nd "." whiteout, it will start performing duplicate elimination.

- Whiteout indication

	glibc will depend on dirent->d_type to be set to DT_WHT on a whiteout

file.

With this post, I am sending two patches:

Patch 1. readdir support for union mounted directories.
I am caching the dirent names in a list to aid duplicate elimination.
And this cache is stored in DIRP. For duplicate elimination I am using strcmp(). I am not sure if this works universally with different types of filesystems. Any suggestions here would be welcome.

Patch 2. seekdir support.
The seekdir works on the cache maintained by readdir. Since after a
seekdir, it might become necessary for readdir to return dirents from cache (as against getting them from readdir(2)/getdents(2)), I had to cache the entire dirent structure in readdir. I understand that this is expensive, but not sure if this is avoidable if we have to support seekdir.

To support seekdir on a union mounted directory, the seek is applied to the cache of dirents. The offsets (dirent->d_off) returned by readdir(3) has been modified to return linearly increasing offsets like 0,1,2,... rather than returning filesystem-returned offsets. This helps us to have a uniform seek across all the directories of the union.

With seekdir modified, I had to modify telldir also not to return filesystem-returned offsets for union mounted directories.

With seekdir support, it becomes necessary in readdir to check if we need to return dirents from cache. And this adds a bit of overhead to readdir as we have to do this check for every directory.

Compatibility issues
--------------------
There are many versions of dirent structure in glibc and I have tried my best to take care of compatibility issues. But I have not really tested readdir64 or old_readdir64. Also atleast one version of dirent structure doesn't have d_type field and my whiteout suppression logic depends on it and uses it in the generic __READDIR routine which gets used by various version of readdir and I think this would break that readdir version which uses dirent structure w/o d_type. I will be taking care of such compatibility issues more cleanly/thoroughly in subsequent posts.

Testing
-------
I have done very minimal testing of these patches on a Intel machine which uses 32 bit readdir. There might be some corner cases in readdir, seekdir and telldir which I might not have taken care of and would be happy to fix them if pointed to. I have tested these patches together with Union Mount patches for 2.6.24-rc2-mm1. These patches are for glibc-2.7.

I request you to reveiw the patches. Any comments and suggestions are greatly welcome.

Regards
Nagabhushan

Enhance readdir to support union mounted directories.

readdir now caches the dirents obtained from readdir(2)/getdents(2) to support duplicate elimination and whiteout suppression for union mounted directories.

---
 sysdeps/unix/closedir.c  |   14 +++++++++
 sysdeps/unix/dirstream.h |   27 ++++++++++++++++++
 sysdeps/unix/opendir.c   |    4 ++
 sysdeps/unix/readdir.c   |   69 +++++++++++++++++++++++++++++++++++++++++++++--
 4 files changed, 112 insertions(+), 2 deletions(-)

@@ -32,6 +32,7 @@ int
 __closedir (DIR *dirp)
 {
   int fd;
+  struct union_dir_cache *temp = NULL;
 
   if (dirp == NULL)
     {

@@ -49,6 +50,19 @@ __closedir (DIR *dirp)
   __libc_lock_fini (dirp->lock);
 #endif
 
+  if (dirp->head != NULL)
+    {
+      while (dirp->head->next != NULL)
+        {
+	  temp = dirp->head->next;
+	  free (dirp->head);
+          dirp->head = temp;
+        }
+      free (dirp->head);
+      dirp->head = NULL;
+      dirp->current = NULL;
+    }
+
   free ((void *) dirp);
 
   return close_not_cancel (fd);

@@ -16,6 +16,20 @@
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
+#ifndef _UNION_DIR_CACHE
+#define _UNION_DIR_CACHE    1
+
+#include <limits.h>
+
+struct union_dir_cache
+{
+  char fname[NAME_MAX];
+  struct union_dir_cache *next;
+  struct union_dir_cache *prev;
+};
+
+#endif
+
 #ifndef	_DIRSTREAM_H
 #define	_DIRSTREAM_H	1
 

@@ -23,6 +37,14 @@
 
 #include <bits/libc-lock.h>
 
+#define DIR_FIRST_DIRENT	1
+#define DIR_UNION_MOUNTED	2
+#define DIR_DUP_ELIM_START	4
+
+#define IS_FIRST_DIRENT(dirp) (dirp->union_dir_status & DIR_FIRST_DIRENT)
+#define IS_DIR_UNION_MOUNTED(dirp) (dirp->union_dir_status & DIR_UNION_MOUNTED)
+#define IS_DUP_ELIM_STARTED(dirp) (dirp->union_dir_status & DIR_DUP_ELIM_START)
+
 /* Directory stream type.
 
    The miscellaneous Unix `readdir' implementations read directory data

@@ -40,6 +62,11 @@ struct __dirstream
 
     off_t filepos;		/* Position of next entry to read.  */
 
+    /* Cache of dirents to be used with union mounted directories */
+    struct union_dir_cache *head;
+    struct union_dir_cache *current;
+    unsigned char union_dir_status;
+
     /* Directory block.  */
     char data[0] __attribute__ ((aligned (__alignof__ (void*))));
   };

@@ -202,6 +202,10 @@ __alloc_dir (int fd, bool close_fd, cons
   dirp->size = 0;
   dirp->offset = 0;
   dirp->filepos = 0;
+  dirp->head = NULL;
+  dirp->current = NULL;
+  dirp->union_dir_status = 1;
+  dirp->union_dir_pos = 0;
 
   return dirp;
 }

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Before anything further is discussed I need to know how you expect to handle NFS? I don't see how, with a userlevel readdir implementation, you can support NFS.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖ -----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iEYEARECAAYFAkgZXmkACgkQ2ijCOnn/RHSFfwCgj/8c4C267owRAcKw//OF7z5E kgkAn0chMraZqjmzFcWsQVgN4l4ZrD/X
=VXir
-----END PGP SIGNATURE-----
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

At the client side, I don't see a problem with unioning NFS with other FS. Kernel would still return all dirents of the union including those from NFS and glibc readdir would be able to handle them appropriately. Or am I missing something ?

At the server side, I can't see how NFS server could export a union. I don't see how this could be sanely done with Union Mount. Erez, how does Unionfs handle this ?

Is dis-allowing NFS-exporting of unions an option ?

Regards,
Bharata.

Bharata B Rao:

As a note, there were many requests for aufs to support NFS-exporting. And it was already implemented. The encode/decode_fh functions in aufs behave like sub-nfsd.

Junjiro Okajima

Is it that simple? What about a union further in an NFS export? What about union-mounting after the tree has been NFS-exported? If the kernel won't fully merge unions then FS servers have to do whatever it is that's being proposed for glibc.

Ok I am realizing that it is not simple. I am actually reading up NFS code to understand how it supports crossing of mountpoints. I see that one can mount a filesystem within a NFS export and NFS server would be able to cross over to that filesystem and provide those contents to the client. Acutally Union Mount maintains union stack very similar to the mount stack, but here we walk the union stack down. So I am checking if something similar to mountpoint crossing would be able to solve the problem of fetching all the contents of the NFS-exported union.

Answering my question to Erez that I raised in another thread, I see that Unionfs doesn't set the export_operations in it's superblock and hence I believe unions created by Unionfs aren't NFS-exportable as of know. Erez, correct me if I got it wrong.

Regards,
Bharata.

Yes, the unionfs in -mm isn't nfs exportable safely, b/c it doesn't have persistent inode numbers. Our unionfs-odf version has persistent inode numbers and is exportable (see http://unionfs.filesystems.org/).

Erez.

[...]

The ODF version of unionfs stores, among other things, persistent inode numbers in a small/special /odf partition. If the inums aren't persistent, they could get flushed out of memory, making it very difficult to reconstruct the inode w/ the same inum later on.

Erez.

seekdir support for union mounted directory.

seekdir, telldir and rewinddir now work on the dirent cache maintained by readdir.

---
 sysdeps/unix/dirstream.h                 |    9 +++++++--
 sysdeps/unix/readdir.c                   |   21 ++++++++++++++++++---
 sysdeps/unix/rewinddir.c                 |   16 ++++++++++++----
 sysdeps/unix/seekdir.c                   |   26 ++++++++++++++++++++++----
 sysdeps/unix/sysv/linux/i386/readdir64.c |    2 ++
 sysdeps/unix/telldir.c                   |    5 ++++-
 6 files changed, 65 insertions(+), 14 deletions(-)

@@ -19,11 +19,15 @@
 #ifndef _UNION_DIR_CACHE
 #define _UNION_DIR_CACHE    1
 
-#include <limits.h>
+#include <dirent.h>
+
+#ifndef CACHE_DIRENT_TYPE
+#define CACHE_DIRENT_TYPE struct dirent
+#endif
 
 struct union_dir_cache
 {
-  char fname[NAME_MAX];
+  CACHE_DIRENT_TYPE dp;
   struct union_dir_cache *next;
   struct union_dir_cache *prev;
 };

@@ -66,6 +70,7 @@ struct __dirstream
     struct union_dir_cache *head;
     struct union_dir_cache *current;
     unsigned char union_dir_status;
+    off_t union_dir_pos;
 
     /* Directory block.  */
     char data[0] __attribute__ ((aligned (__alignof__ (void*))));

@@ -48,6 +48,21 @@ __READDIR (DIR *dirp)
   __libc_lock_lock (dirp->lock);
 #endif
 
+  /* If union mounted directory, check if we can return dirent from cache */
+  if (dirp->head && dirp->current->next)
+    {
+      dirp->current = dirp->current->next;
+      while (dirp->current && dirp->current->dp.d_type == DT_WHT)
+        dirp->current = dirp->current->next;
+
+      if (dirp->current) {
+        dirp->union_dir_pos = dirp->current->dp.d_off;
+#ifndef NOT_IN_libc
+        __libc_lock_unlock (dirp->lock);
+#endif
+        return &dirp->current->dp;
+      }
+    }
   do
     {
       size_t reclen;

@@ -135,7 +150,7 @@ __READDIR (DIR *dirp)
               temp = dirp->head;
               while (temp)
                 {
-                  if (!strcmp (temp->fname, dp->d_name))
+                  if (!strcmp (temp->dp.d_name, dp->d_name))
                     {
                       isdup = 1;
                       break;

@@ -168,8 +183,8 @@ __READDIR (DIR *dirp)
               dirp->current = dirp->current->next;
             }
 
-          strcpy(dirp->current->fname, dp->d_name);
-
+          memcpy(&dirp->current->dp, dp, sizeof(DIRENT_TYPE));
+          dirp->current->dp.d_off = ++dirp->union_dir_pos;
         }
 	dirp->union_dir_status &= ~DIR_FIRST_DIRENT;
 

@@ -29,9 +29,17 @@ rewinddir (dirp)
      DIR *dirp;
 {
   __libc_lock_lock (dirp->lock);
-  (void) __lseek (dirp->fd, (off_t) 0, SEEK_SET);
-  dirp->filepos = 0;
-  dirp->offset = 0;
-  dirp->size = 0;
+  if (dirp->head)
+    {
+      dirp->current = dirp->head;
+      dirp->union_dir_pos = dirp->current->dp.d_off;
+    }
+  else
+    {
+      (void) __lseek (dirp->fd, (off_t) 0, SEEK_SET);
+      dirp->filepos = 0;
+      dirp->offset = 0;
+      dirp->size = 0;
+    }
   __libc_lock_unlock (dirp->lock);
 }

@@ -30,9 +30,27 @@ seekdir (dirp, pos)
      long int pos;
 {
   __libc_lock_lock (dirp->lock);
-  (void) __lseek (dirp->fd, pos, SEEK_SET);
-  dirp->size = 0;
-  dirp->offset = 0;
-  dirp->filepos = pos;
+  if (dirp->head) /* union mounted directory */
+    {
+      if (pos == 0)
+        dirp->current = dirp->head;
+      else
+        {
+          dirp->current = dirp->head;
+          while (dirp->current->next && pos != 1)
+            {
+              dirp->current = dirp->current->next;
+              pos--;
+            }
+        }
+      dirp->union_dir_pos = dirp->current->dp.d_off;
+    }
+  else
+    {
+      (void) __lseek (dirp->fd, pos, SEEK_SET);
+      dirp->size = 0;
+      dirp->offset = 0;
+      dirp->filepos = pos;
+    }
   __libc_lock_unlock (dirp->lock);
 }

@@ -16,6 +16,7 @@
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
+#define CACHE_DIRENT_TYPE struct dirent64
 #define __READDIR __readdir64
 #define __GETDENTS __getdents64
 #define DIRENT_TYPE struct dirent64

@@ -34,6 +35,7 @@ versioned_symbol (libc, __readdir64, rea
 
 #include <sysdeps/unix/sysv/linux/i386/olddirent.h>
 
+#define CACHE_DIRENT_TYPE struct __old_dirent64
 #define __READDIR attribute_compat_text_section __old_readdir64
 #define __GETDENTS __old_getdents64
 #define DIRENT_TYPE struct __old_dirent64

@@ -24,5 +24,8 @@
 long int
 telldir (DIR *dirp)
 {
-  return dirp->filepos;
+  if (dirp->head)          /* union mounted directory  */
+    return dirp->union_dir_pos;
+  else
+    return dirp->filepos;
 }

Hello Nagabhushan,

[email protected]:

	:::

While I don't have objection against the implementation in userspace, what will UnionMount handle about rmdir or rename dir?
Those systemcalls need to test whether the dir is *logically* empty or not in kernel space, don't they?
And I am afraid that UnionMount has to implement the similar thing, but it never mean to modify glibc is a bad idea.

Junjiro Okajima

For rmdir it is simple: the filesystem that supports whiteouts must know how to get rid of them again. Since it knows how the whiteouts are implemented it can do that in an optimized fashion.

The rename story is somehow different. A union directory consists of multiple directories on different filesystem. Since rename syscall is only working on one filesystem the rename is crossing devices. Therefore I return -EXDEV. Not very efficient but really simple. At least this is how my patches implement it.

Regards,
Jan

Jan Blunck <[email protected]>

IIRC the intention was to emit a "." whiteout when "changing" from one directory to the next. That means when the first directory is completely read the whiteout is emitted. After that glibc knows to start duplicate removal.

See above

Which makes the new filetype very much visible to the userspace but maybe that is the price we have to pay.

We don't support union mounts on older kernels. Newer kernels return d_type. So I think we don't have a problem.

Regards,
Jan

Jan Blunck <[email protected]>

Yes the intention was to get a "." whiteout when changing from one directory to next and thats essentially what i have assumed, for starting duplicate elimination.
Along with that i have also assumed to get a "." whiteout as the first directory entry of the union, so as to indicate to glibc that the directory is a union mounted directory.

Regards
Nagabhushan

[...]

The last set of discussions on glibc support ended, as I understood it, with the glibc people objecting to such "special-purpose" code in glibc. See
<http://lkml.org/lkml/2008/3/11/66>. So has anything changed behind the scenes, or is this idea unlikely to be merged into glibc any time soon, if ever. (Personally I'd love to rip out the readdir-related code from unionfs if glibc supported the same.)

[...]

You might consider using a hash table instead of a list; it'll be faster in case where there are a lot of whiteouts/duplicates to process.

Also, I'll reiterate my previous concern that I think you may need to also handle "opaque directories". See the discussion in section 5.1 "Creation and deletion of whiteouts", in the original union mounts paper:

<http://www.usenix.org/publications/library/proceedings/neworl/full_papers/mckusick.a>

Cheers,
Erez.

Hmm, if kernel is traversing to the next layer in an union and it finds it to be opaque the kernel knows that this is the "end" of the union. So after reading that directory it is done.

Regards,
Jan

Jan Blunck <[email protected]>

Yes, hash table was one of the things i had considered to use as a cache. But i am not completely sure how this would support seekdir. Any suggestions are greatly welcome.

Regards Nagabhushan

[...]

Here's one idea:

1. Your main data structure is a linear array of struct dirents. You perform seekdir/readdir on this linear structure, which should be trivial. Each time you find a dirent which definitely needs to go into this structure, you append to it. If you're about to run out of space in it, you can realloc it 2x its previous size (a common technique). This structure remains cached in memory for as long as the directory is open.

Optimization 1: you can keep it cached past close(fd), b/c recursive programs like /bin/find may close and reopen a directory several times. But you'll need to determine if the directory's mtime had changed and if so, purge the cached content and reconstruct it.

Optimization 2: if you can do a stat(2) on each directory in the union, and sum their total size, that'll provide you with an upper bound on the size of your dirent cache. In that case, you can forego the realloc I mentioned, and just malloc one large array at once. This could be more efficient than realloc'ing for two reasons: (a) realloc may have to memcpy data, which you can avoid; and (b) the rest of the malloc'ed array, near its end, may be unused, but as long as you don't touch it, it'll be one large-ish extent of virtual memory for which physical page frames won't be actually needed. Even better, you can realloc() that large malloc'ed area to cut back on its size to exactly what you need.

2. During the construction of the dirent array above, you keep two hash tables:

2a. HT1 is used for duplicate elimination. It contains POINTERS ONLY (or
offsets) into the dirent cache buffer. You add entries into it each time you append a name to the dirent cache array. This HT1 allows you to quickly find out if a string name had been seen before. When you're done constructing the dirent cache, free(HT1).

2b. HT2 is used for whiteouts. It contains the actual strings of whited-out
entries you've seen, which you add each time you find a whiteout. You look this HT2 each time you need to determine if an entry you're about to add to the dirent cache had been whited-out or not. When you're done constructing the dirent cache, free(HT2).

Hope you can use this as a starting point.

Cheers,
Erez.

Erez Zadok:

	:::

All these points are very similar to the actual implementation in AUFS, except 'Optimization 2: decide memory size by stat().'
- the size may not be enough for storing every dirent, it depends upon the filesystem's implementation.
- the size may be a block size which can be larger than page size even if it is a empty dir, also it depends upon the filesystem.

Junjiro Okajima