[PATCH] Rewrite find_root_device_from_mountinfo to cope with move-mounts

[Colin Watson]

https://bugs.launchpad.net/ubuntu/+source/grub2/+bug/738345 turns out to
be a fiddly bug in our /proc/self/mountinfo parsing.  In this
environment, /proc/self/mountinfo looks like this:

  19 20 8:2 / /host rw,nosuid,nodev,relatime - fuseblk /dev/sda2 
rw,user_id=0,group_id=0,allow_other,blksize=4096
  20 1 7:0 / / rw,relatime - ext4 /dev/loop0 
rw,errors=remount-ro,barrier=1,data=ordered

find_root_device_from_mountinfo's assumption (which was my fault) that
mountinfo is always in mount order is more or less correct, but
unhelpful: moving a mount does not change its position in mountinfo,
even though it might change the manner in which mounts occlude other
mounts.

To fix this, we need to use the first two fields in mountinfo, which
allow us to construct a DAG of visible mounts: the first field is a
unique mount ID, and the second field is the parent mount ID.  The
semantics of this are that the parent directory of a given mountpoint is
in the mount identified by that mountpoint's parent mount ID.  Using
this, we can construct a list of visible mounts leading up to the
requested path.

I know this is a non-trivial patch, but I'd rather like to get it into
1.99 to correct the false assumption I introduced after 1.98.  It's more
of an issue in the context of the butter branch which causes this
function to be used much more broadly than just for btrfs, but a twisty
combination of btrfs mounts would be entirely capable of triggering this
bug with trunk as well.

I've tested this both with the Wubi example excerpted above and with
some constructed examples of bind-mounts occluding parts of the
filesystem.  It seems to be working fine in the examples I've been able
to construct.

2011-03-23  Colin Watson  <address@hidden>

        Rewrite /proc/self/mountinfo handling to cope with bind-mounts and
        move-mounts appearing out of order.  Fixes Ubuntu bug #738345.

        * grub-core/kern/emu/getroot.c (find_root_device_from_mountinfo):
        Build a list of relevant visible mounts using the mnt_id and
        parent_mnt_id fields, and then scan that list at the end.

=== modified file 'grub-core/kern/emu/getroot.c'
--- grub-core/kern/emu/getroot.c        2011-01-22 14:37:05 +0000
+++ grub-core/kern/emu/getroot.c        2011-03-23 14:55:54 +0000
@@ -98,6 +98,14 @@ xgetcwd (void)
 
 #ifdef __linux__
 
+struct mountinfo_entry
+{
+  int id;
+  int major, minor;
+  char enc_root[PATH_MAX], enc_path[PATH_MAX];
+  char fstype[PATH_MAX], device[PATH_MAX];
+};
+
 /* Statting something on a btrfs filesystem always returns a virtual device
    major/minor pair rather than the real underlying device, because btrfs
    can span multiple underlying devices (and even if it's currently only
@@ -112,68 +120,117 @@ find_root_device_from_mountinfo (const c
   char *buf = NULL;
   size_t len = 0;
   char *ret = NULL;
+  int entry_len = 0, entry_max = 4;
+  struct mountinfo_entry *entries;
+  struct mountinfo_entry parent_entry = { 0, 0, 0, "", "", "", "" };
+  int i;
 
   fp = fopen ("/proc/self/mountinfo", "r");
   if (! fp)
     return NULL; /* fall through to other methods */
 
+  entries = xmalloc (entry_max * sizeof (*entries));
+
+  /* First, build a list of relevant visible mounts.  */
   while (getline (&buf, &len, fp) > 0)
     {
-      int mnt_id, parent_mnt_id;
-      unsigned int major, minor;
-      char enc_root[PATH_MAX], enc_path[PATH_MAX];
+      struct mountinfo_entry entry;
       int count;
       size_t enc_path_len;
       const char *sep;
-      char fstype[PATH_MAX], device[PATH_MAX];
-      struct stat st;
 
       if (sscanf (buf, "%d %d %u:%u %s %s%n",
-                 &mnt_id, &parent_mnt_id, &major, &minor, enc_root, enc_path,
-                 &count) < 6)
+                 &entry.id, &parent_entry.id, &entry.major, &entry.minor,
+                 entry.enc_root, entry.enc_path, &count) < 6)
        continue;
 
-      if (strcmp (enc_root, "/") != 0)
+      if (strcmp (entry.enc_root, "/") != 0)
        continue; /* only a subtree is mounted */
 
-      enc_path_len = strlen (enc_path);
+      enc_path_len = strlen (entry.enc_path);
       /* Check that enc_path is a prefix of dir.  The prefix must either be
          the entire string, or end with a slash, or be immediately followed
          by a slash.  */
-      if (strncmp (dir, enc_path, enc_path_len) != 0 ||
+      if (strncmp (dir, entry.enc_path, enc_path_len) != 0 ||
          (enc_path_len && dir[enc_path_len - 1] != '/' &&
           dir[enc_path_len] && dir[enc_path_len] != '/'))
        continue;
 
-      /* This is a parent of the requested directory.  /proc/self/mountinfo
-        is in mount order, so it must be the closest parent we've
-        encountered so far.  If it's virtual, return its device node;
-        otherwise, carry on to try to find something closer.  */
-
-      free (ret);
-      ret = NULL;
-
-      if (major != 0)
-       continue; /* not a virtual device */
-
       sep = strstr (buf + count, " - ");
       if (!sep)
        continue;
 
       sep += sizeof (" - ") - 1;
-      if (sscanf (sep, "%s %s", fstype, device) != 2)
+      if (sscanf (sep, "%s %s", entry.fstype, entry.device) != 2)
        continue;
 
-      if (stat (device, &st) < 0)
+      /* Using the mount IDs, find out where this fits in the list of
+        visible mount entries we've seen so far.  There are three
+        interesting cases.  Firstly, it may be inserted at the end: this is
+        the usual case of /foo/bar being mounted after /foo.  Secondly, it
+        may be inserted at the start: for example, this can happen for
+        filesystems that are mounted before / and later moved under it.
+        Thirdly, it may occlude part or all of the existing filesystem
+        tree, in which case the end of the list needs to be pruned and this
+        new entry will be inserted at the end.  */
+      if (entry_len >= entry_max)
+       {
+         entry_max <<= 1;
+         entries = xrealloc (entries, entry_max * sizeof (*entries));
+       }
+
+      if (!entry_len)
+       {
+         /* Initialise list.  */
+         entry_len = 2;
+         entries[0] = parent_entry;
+         entries[1] = entry;
+       }
+      else
+       {
+         for (i = entry_len - 1; i >= 0; i--)
+           {
+             if (entries[i].id == parent_entry.id)
+               {
+                 /* Insert at end, pruning anything previously above this.  */
+                 entry_len = i + 2;
+                 entries[i + 1] = entry;
+                 break;
+               }
+             else if (i == 0 && entries[i].id == entry.id)
+               {
+                 /* Insert at start.  */
+                 entry_len++;
+                 memmove (entries + 1, entries,
+                          (entry_len - 1) * sizeof (*entries));
+                 entries[0] = parent_entry;
+                 entries[1] = entry;
+                 break;
+               }
+           }
+       }
+    }
+
+  /* Now scan visible mounts for the ones we're interested in.  */
+  for (i = entry_len - 1; i >= 0; i--)
+    {
+      struct stat st;
+
+      if (entries[i].major != 0)
+       continue; /* not a virtual device */
+
+      if (!*entries[i].device || stat (entries[i].device, &st) < 0)
        continue;
 
       if (!S_ISBLK (st.st_mode))
        continue; /* not a block device */
 
-      ret = strdup (device);
+      ret = strdup (entries[i].device);
+      break;
     }
 
   free (buf);
+  free (entries);
   fclose (fp);
   return ret;
 }

Thanks,

-- 
Colin Watson                                       address@hidden