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 ...
[ message continues ]

[...]

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
[...]

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.
--

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,...
[ message continues ]

:::

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
--

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 <jblunck@suse.de>
--

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


Which makes the new filetype very much visible to the userspace but maybe that

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 <jblunck@suse.de>
--

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
--

Hello Nagabhushan,

	:::

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 <jblunck@suse.de>
--

seekdir support for union mounted directory.

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

Signed-off-by: Nagabhushan B S <bsn.0007@gmail.com>
---
 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(-)

--- a/sysdeps/unix/dirstream.h
+++ b/sysdeps/unix/dirstream.h
@@ -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*))));
--- a/sysdeps/unix/readdir.c
+++ b/sysdeps/unix/readdir.c
@@ -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...
[ message continues ]

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.

Signed-off-by: Nagabhushan B S <bsn.0007@gmail.com>
---
 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(-)

--- a/sysdeps/unix/closedir.c
+++ b/sysdeps/unix/closedir.c
@@ -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);
--- a/sysdeps/unix/dirstream.h
+++ b/sysdeps/unix/dirstream.h
@@ -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(d...
[ message continues ]

-----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-----
--

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.
--

[...]

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.
--

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

Erez.
--

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
--