Bug 1962515

Thank you for the thorough analysis!  You are right about the cause of the different output of df on RHEL-8 onwards.  My only concern is about the performance penalty of the duplicated insertion into the hash table.  It could yield worse performance in some cases, thus invalidate the original motivation for introducing the hash table.  Comparing device names in the hash table could also decrease the performance because it runs quite frequently (and comparing strings is more expensive than comparing integers).

I wonder if we could fix it like this to achieve the same behavior with lower performance penalty?

--- a/src/df.c
+++ b/src/df.c
@@ -51,12 +51,13 @@

 struct devlist
 {
   dev_t dev_num;
   struct mount_entry *me;
   struct devlist *next;
+  struct devlist *seen_last; /* valid for hashed devlist entries only */
 };

 /* Filled with device numbers of examined file systems to avoid
    duplicates in output.  */
 static Hash_table *devlist_table;

@@ -678,13 +679,19 @@ static struct devlist *
 devlist_for_dev (dev_t dev)
 {
   if (devlist_table == NULL)
     return NULL;
   struct devlist dev_entry;
   dev_entry.dev_num = dev;
-  return hash_lookup (devlist_table, &dev_entry);
+
+  struct devlist *found = hash_lookup (devlist_table, &dev_entry);
+  if (found == NULL)
+    return NULL;
+
+  /* Return the last devlist entry we have seen with this dev_num */
+  return found->seen_last;
 }

 static void
 devlist_free (void *p)
 {
   free (p);
@@ -796,14 +803,18 @@ filter_mount_list (bool devices_only)
           /* Add the device number to the device_table.  */
           struct devlist *devlist = xmalloc (sizeof *devlist);
           devlist->me = me;
           devlist->dev_num = buf.st_dev;
           devlist->next = device_list;
           device_list = devlist;
-          if (hash_insert (devlist_table, devlist) == NULL)
+
+          struct devlist *inserted = hash_insert (devlist_table, devlist);
+          if (inserted == NULL)
             xalloc_die ();
+          /* Remember the last devlist entry we have seen with this dev_num */
+          inserted->seen_last = devlist;

           me = me->me_next;
         }
     }

   /* Finally rebuild the mount_list from the devlist.  */

hi Kamil !

  (In reply to Kamil Dudka from comment #1)
> Thank you for the thorough analysis!  You are right about the cause of the
> different output of df on RHEL-8 onwards.  My only concern is about the
> performance penalty of the duplicated insertion into the hash table.  It
> could yield worse performance in some cases, thus invalidate the original
> motivation for introducing the hash table.  Comparing device names in the
> hash table could also decrease the performance because it runs quite
> frequently (and comparing strings is more expensive than comparing integers).
> 
> I wonder if we could fix it like this to achieve the same behavior with
> lower performance penalty?

Yes, my fix indeed incurr on a perfomance penalty for same dev case, i guess more potentially possible
for network filesystems, for the rest of cases we still have the benefit of hash table


> 
> --- a/src/df.c
> +++ b/src/df.c
> @@ -51,12 +51,13 @@
> 
>  struct devlist
>  {
>    dev_t dev_num;
>    struct mount_entry *me;
>    struct devlist *next;
> +  struct devlist *seen_last; /* valid for hashed devlist entries only */
>  };
> 
>  /* Filled with device numbers of examined file systems to avoid
>     duplicates in output.  */
>  static Hash_table *devlist_table;
> 
> @@ -678,13 +679,19 @@ static struct devlist *
>  devlist_for_dev (dev_t dev)
>  {
>    if (devlist_table == NULL)
>      return NULL;
>    struct devlist dev_entry;
>    dev_entry.dev_num = dev;
> -  return hash_lookup (devlist_table, &dev_entry);
> +
> +  struct devlist *found = hash_lookup (devlist_table, &dev_entry);
> +  if (found == NULL)
> +    return NULL;
> +
> +  /* Return the last devlist entry we have seen with this dev_num */
> +  return found->seen_last;
>  }
> 
>  static void
>  devlist_free (void *p)
>  {
>    free (p);
> @@ -796,14 +803,18 @@ filter_mount_list (bool devices_only)
>            /* Add the device number to the device_table.  */
>            struct devlist *devlist = xmalloc (sizeof *devlist);
>            devlist->me = me;
>            devlist->dev_num = buf.st_dev;
>            devlist->next = device_list;
>            device_list = devlist;
> -          if (hash_insert (devlist_table, devlist) == NULL)
> +
> +          struct devlist *inserted = hash_insert (devlist_table, devlist);
> +          if (inserted == NULL)
>              xalloc_die ();
> +          /* Remember the last devlist entry we have seen with this dev_num
> */
> +          inserted->seen_last = devlist;
> 
>            me = me->me_next;
>          }
>      }
> 
>    /* Finally rebuild the mount_list from the devlist.  */

Nice! i'll take a look and try it tomorrow. Thanks for taking a look !

rgds
roberto

(In reply to Roberto Bergantinos from comment #2)
> Yes, my fix indeed incurr on a perfomance penalty for same dev case, i guess
> more potentially possible
> for network filesystems, for the rest of cases we still have the benefit of
> hash table

I totally agree.  The performance penalty could only be observable in some special cases.  On the other hand, the hash table is there to cover special cases.  For 99% of common use cases, the linked list would be sufficient.

> Nice! i'll take a look and try it tomorrow. Thanks for taking a look !

Thanks!  And sorry that it took me so long to have a closer look at this.

Hi Kamil

  Sorry for delay this fell off my radar.

  Your patch works in my testing, i build from upstream version :

[root@rhel8 coreutils]# src/df -t nfs4
Filesystem      1K-blocks    Used Available Use% Mounted on
rhel73:/share     8374272 6010880   2363392  72% /testdir/share1
rhel73:/workvol   8374272 6010880   2363392  72% /testdir/share2
[root@rhel8 coreutils]# df -t nfs4
Filesystem      1K-blocks    Used Available Use% Mounted on
rhel73:/share     8374272 6010880   2363392  72% /testdir/share1
rhel73:/workvol   8374272 6010880   2363392  72% /testdir/share2
rhel73:/workvol   8374272 6010880   2363392  72% /mnt/testdir/share2

  had some warnings building but possibly my build machine is not the best.

  thanks !

rgds
roberto

Thank you for testing it!  I will propose the change upstream.

patch proposed upstream: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=49298

upstream commit: https://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=commitdiff;h=v8.32-169-gd6125af095c

Since the problem described in this bug report should be
resolved in a recent advisory, it has been closed with a
resolution of ERRATA.

For information on the advisory (coreutils bug fix and enhancement update), and where to find the updated
files, follow the link below.

If the solution does not work for you, open a new bug report.

https://access.redhat.com/errata/RHBA-2021:4418