[gparted] Switch to faster minfo and mdir to read FAT16/32 usage (#569921)

[Curtis Gedak <gedakc src gnome org>]

commit 5a52b44071d86bd556451e1e22f5fbc3a1ae9000
Author: Mike Fleetwood <mike fleetwood googlemail com>
Date:   Tue Jun 18 18:45:39 2019 +0100

    Switch to faster minfo and mdir to read FAT16/32 usage (#569921)
    
    A user reported that GParted was slow to refresh on FAT32 file systems:
    "can take very long, up to several minutes; can be reproduced by running
    dosfsck manually".  This is because the file system was large and almost
    full, and GParted performs a file system check just to to report the
    file system usage.
    
    Created a 4 GiB FAT32 file system and almost filled it with 4 KiB files,
    just over 970,000 files.
    
        # df -k /mnt/2
        Filesystem     1K-blocks     Used Available Used% Mounted on
        /dev/sdb2        4186108 39155384    270724   94% /mnt/2
        # df -i /mnt/2
        Filesystem     Inodes IUsed IFree IUse% Mounted on
        /dev/sdb2           0     0     0     - /mnt/2
        # find /mnt/2 -type f -print | wc -l
        971059
        # find /mnt/2 -type d -print | wc -l
        1949
    
    Testing performance of the current fsck.fat:
    
        # time fsck.fat -n -v /dev/sdb2 | \
        > egrep 'bytes per logical sector|bytes per cluster|sectors total|clusters$'
               512 bytes per logical sector
              4096 bytes per cluster
           8388608 sectors total
        /dev/sdb2: 973008 files, 978846/1046527 clusters
    
        real    0m11.552s
        user    0m2.183s
        sys     0m7.547s
    
    Free sectors in the file system according to fsck.fat:
        (1046527 - 978846) * 4096 / 512 = 541448 sectors
    
    Repeating this test while also using 'blktrace /dev/sdb2' and Ctrl-C
    around the test in a separate terminal, reports these numbers of I/Os
    being performed:
        Read requests   Read bytes
               15,563      165 MiB
    
    Prior to this commit [1] from 0.0.9, GParted used libparted's
    ped_file_system_get_resize_constraint() to report the minimum size to
    which a FAT* file system can be resized.  Use this test program [2] to
    performance test this method:
    
        # time ./fscons /dev/sdb2
        dev=/dev/sdb2
        sector_size=512
        min_size=7909522
        max_size=8388608
    
        real    0m2.673s
        user    0m0.070s
        sys     0m1.834s
    
    Free sectors in the file system according to libparted
    ped_file_system_get_resize_constraint():
        8388608 - 7909522 = 479086 sectors
    
    blktrace reports these numbers of I/Os being performed:
        Read requests   Read bytes
                7,821       71 MiB
    
    So using libparted resize constraint is a bit faster but is still
    reading too much data and is really too slow.  Also when testing GParted
    using this libparted method against a corrupted FAT32 file system, on
    every refresh, one popup dialog is displayed for each error libparted
    detects with the file system, each of which needs acknowledgement.
    Example popup:
    
                         Libparted Error
        \DIRNAME\FILENAME.EXT is 107724k, but is has 1920
        clusters (122880k).
    
                                     [ Cancel ][ Ignore ]
    
    There could be a huge number of such errors in a corrupted file system.
    Not really suitable for use by GParted.
    
    Test the performance of mtools' minfo command to report the file system
    figures:
    
        # time minfo -i /dev/sdb2 :: | \
        > egrep 'sector size:|cluster size:|small size:|big size:|free clusters='
        sector size: 512 bytes
        cluster size: 8 sectors
        small size: 0 sectors
        big size: 8388608 sectors
        free clusters=67681
    
        real    0m0.013s
        user    0m0.004s
        sys     0m0.019s
    
    Free sectors in the file system according to minfo:
        67681 * 8 = 541448 sectors
    
    blktrace reports these numbers of I/Os being performed by minfo:
        Read requests   Read bytes
                    1       16 KiB
    
    This matches with minfo just reading information from the BPB (BIOS
    Parameter Block) [3] from sector 0 and the FS Information Sector [4]
    usually in sector 1.  Note that the free cluster figure reported by
    minfo comes from the FS Information Sector because it only reports it
    for FAT32 file systems, not for FAT16 file systems.  Scanning the File
    Allocation Table (FAT) [5] to count free clusters is exactly what mdir,
    without the '-f' (fast) flag, does.  Test the performance of mdir:
    
        # export MTOOLS_SKIP_CHECK=1
        # time mdir -i /dev/sdb2 ::/ | fgrep 'bytes free'
                                277 221 376 bytes free
    
        real    0m0.023s
        user    0m0.011s
        sys     0m0.023s
    
    Free sectors in the file system according to mdir:
        277221376 / 512 = 541448 sectors
    
    blktrace reports these number of I/Os being performed by mdir:
        Read requests   Read bytes
                    5      448 KiB
    
    So minfo and mdir together provide the needed information and are 2 to 3
    orders of magnitude faster because they only read the needed BPB and FAT
    data from the drive.  Use these together to read the file system usage.
    
    [1] 61cd0ce77879e4af84280ddcf77959ae55885ba4
        lots of stuff and cleanups, including fixing getting used/unused
        space of hfs/hfs+/fat16/fat32
    
    [2] fscons.c
    /* FILE:     fscons.c
     * SYNOPSIS: Report libparted's FS resize limits.
     * BUILD:    gcc -o fscons fscons.c -lparted -lparted-fs-resize
     */
    
    int main(int argc, const char *argv[])
    {
        PedDevice* dev = NULL;
        PedDisk* tab = NULL;
        PedPartition* ptn = NULL;
        PedFileSystem* fs = NULL;
        PedConstraint* cons = NULL;
    
        if (argc != 2)
        {
            fprintf(stderr, "Usage: fscons BLOCKDEV\n");
            exit(1);
        }
    
        dev = ped_device_get(argv[1]);
        if (dev == NULL)
        {
            fprintf(stderr, "ped_device_get(\"%s\") failed\n", argv[1]);
            exit(1);
        }
        printf("dev=%s\n", dev->path);
        printf("sector_size=%ld\n", dev->sector_size);
    
        tab = ped_disk_new(dev);
        if (tab == NULL)
        {
            fprintf(stderr, "ped_disk_new(dev) failed\n");
            exit(1);
        }
    
        ptn = ped_disk_get_partition_by_sector(tab, 0);
        if (ptn == NULL)
        {
            fprintf(stderr, "ped_disk_get_partition(tab, 0) failed\n");
            exit(1);
        }
    
        fs = ped_file_system_open(&ptn->geom);
        if (fs == NULL)
        {
            fprintf(stderr, "ped_file_system_open(&ptn->geom) failed\n");
            exit(1);
        }
    
        cons = ped_file_system_get_resize_constraint(fs);
        if (cons == NULL)
        {
            fprintf(stderr, "ped_file_system_get_resize_constraint(fs) failed\n");
            exit(1);
        }
        printf("min_size=%ld\n", cons->min_size);
        printf("max_size=%ld\n", cons->max_size);
    
        ped_constraint_destroy(cons);
        ped_file_system_close(fs);
        ped_disk_destroy(tab);
        ped_device_destroy(dev);
    
        return 0;
    }
    
    [3] Design of the FAT file system, BIOS Parameter Block
        https://en.wikipedia.org/wiki/Design_of_the_FAT_file_system#BIOS_Parameter_Block
    
    [4] Design of the FAT file system, FS Information Sector
        https://en.wikipedia.org/wiki/Design_of_the_FAT_file_system#FS_Information_Sector
    
    [5] Design of the FAT file system, File Allocation Table
        https://en.wikipedia.org/wiki/Design_of_the_FAT_file_system#File_Allocation_Table
    
    Bug 569921 - dosfsck -n delays device scan

 include/fat16.h |   1 +
 src/fat16.cc    | 139 +++++++++++++++++++++++++++++++++++++-------------------
 2 files changed, 93 insertions(+), 47 deletions(-)
---
diff --git a/include/fat16.h b/include/fat16.h
index 4d1f3163..dc4ef4d3 100644
--- a/include/fat16.h
+++ b/include/fat16.h
@@ -44,6 +44,7 @@ public:
 
 private:
        const Glib::ustring sanitize_label( const Glib::ustring & label ) const;
+       static Glib::ustring remove_spaces(const Glib::ustring& str);
 };
 
 } //GParted
diff --git a/src/fat16.cc b/src/fat16.cc
index 0517b1e2..8cda7f16 100644
--- a/src/fat16.cc
+++ b/src/fat16.cc
@@ -60,6 +60,13 @@ FS fat16::get_filesystem_support()
 
        fs .busy = FS::GPARTED ;
 
+       if (! Glib::find_program_in_path("mdir").empty())
+       {
+               fs.read_uuid = FS::EXTERNAL;
+               if (! Glib::find_program_in_path("minfo").empty())
+                       fs.read = FS::EXTERNAL;
+       }
+
        //find out if we can create fat file systems
        if ( ! Glib::find_program_in_path( "mkfs.fat" ) .empty() )
        {
@@ -77,19 +84,14 @@ FS fat16::get_filesystem_support()
        if ( ! Glib::find_program_in_path( "fsck.fat" ) .empty() )
        {
                fs.check = FS::EXTERNAL;
-               fs.read = FS::EXTERNAL;
                check_cmd = "fsck.fat" ;
        }
        else if ( ! Glib::find_program_in_path( "dosfsck" ) .empty() )
        {
                fs.check = FS::EXTERNAL;
-               fs.read = FS::EXTERNAL;
                check_cmd = "dosfsck" ;
        }
 
-       if ( ! Glib::find_program_in_path( "mdir" ) .empty() )
-               fs .read_uuid = FS::EXTERNAL ;
-
        if ( ! Glib::find_program_in_path( "mlabel" ) .empty() ) {
                fs .read_label = FS::EXTERNAL ;
                fs .write_label = FS::EXTERNAL ;
@@ -125,54 +127,82 @@ FS fat16::get_filesystem_support()
 
 void fat16::set_used_sectors( Partition & partition ) 
 {
-       exit_status = Utils::execute_command( check_cmd + " -n -v " + Glib::shell_quote( partition.get_path() 
),
-                                             output, error, true );
-       if ( exit_status == 0 || exit_status == 1 )
+       // Use mdir's scanning of the FAT to get the free space.
+       // https://en.wikipedia.org/wiki/Design_of_the_FAT_file_system#File_Allocation_Table
+       exit_status = Utils::execute_command("mdir -i " + Glib::shell_quote(partition.get_path()) + " ::/",
+                                            output, error, true);
+       if (exit_status != 0)
        {
-               //total file system size in logical sectors
-               Glib::ustring::size_type index = output.rfind( "\n", output.find( "sectors total" ) ) + 1;
-               if ( index >= output.length() || sscanf( output.substr( index ).c_str(), "%lld", &T ) != 1 )
-                       T = -1 ;
-
-               //bytes per logical sector
-               index = output .rfind( "\n", output .find( "bytes per logical sector" ) ) +1 ;
-               if ( index >= output.length() || sscanf( output.substr( index ).c_str(), "%lld", &S ) != 1 )
-                       S = -1 ;
-
-               if ( T > -1 && S > -1 )
-                       T = Utils::round( T * ( S / double(partition .sector_size) ) ) ;
-
-               //free clusters
-               index = output .find( ",", output .find( partition .get_path() ) + partition .get_path() 
.length() ) +1 ;
-               if ( index < output.length() && sscanf( output.substr( index ).c_str(), "%lld/%lld", &S, &N ) 
== 2 )
-                       N -= S ;
-               else
-                       N = -1 ;
-
-               //bytes per cluster
-               index = output .rfind( "\n", output .find( "bytes per cluster" ) ) +1 ;
-               if ( index >= output.length() || sscanf( output.substr( index ).c_str(), "%lld", &S ) != 1 )
-                       S = -1 ;
-       
-               if ( N > -1 && S > -1 )
-               {
-                       N = Utils::round( N * ( S / double(partition .sector_size) ) ) ;
-                       partition.fs_block_size = S;
-               }
-
-               if ( T > -1 && N > -1 )
-                       partition .set_sector_usage( T, N ) ;
+               if (! output.empty())
+                       partition.push_back_message(output);
+               if (! error.empty())
+                       partition.push_back_message(error);
+               return;
        }
-       else
+
+       // Bytes free.  Parse the value from the bottom of the directory listing by mdir.
+       // Example line "                        277 221 376 bytes free".
+       Glib::ustring spaced_number_str = Utils::regexp_label(output, "^ *([0-9 ]*) bytes free$");
+       Glib::ustring number_str = remove_spaces(spaced_number_str);
+       long long bytes_free = -1;
+       if (number_str.size() > 0)
+               bytes_free = atoll(number_str.c_str());
+
+       // Use minfo's reporting of the BPB (BIOS Parameter Block) to get the file system
+       // size and FS block (cluster) size.
+       // https://en.wikipedia.org/wiki/Design_of_the_FAT_file_system#BIOS_Parameter_Block
+       exit_status = Utils::execute_command("minfo -i " + Glib::shell_quote(partition.get_path()) + " ::",
+                                            output, error, true);
+       if (exit_status != 0)
        {
-               if ( ! output .empty() )
-                       partition.push_back_message( output );
-               
-               if ( ! error .empty() )
-                       partition.push_back_message( error );
+               if (! output.empty())
+                       partition.push_back_message(output);
+               if (! error.empty())
+                       partition.push_back_message(error);
+               return;
+       }
+
+       // FS logical sector size in bytes
+       long long logical_sector_size = -1;
+       Glib::ustring::size_type index = output.find("sector size:");
+       if (index < output.length())
+               sscanf(output.substr(index).c_str(), "sector size: %lld bytes", &logical_sector_size);
+
+       // Cluster size in FS logical sectors
+       long long cluster_size = -1;
+       index = output.find("cluster size:");
+       if (index < output.length())
+               sscanf(output.substr(index).c_str(), "cluster size: %lld sectors", &cluster_size);
+
+       // FS size in logical sectors if <= 65535, or 0 otherwise
+       long long small_size = -1;
+       index = output.find("small size:");
+       if (index < output.length())
+               sscanf(output.substr(index).c_str(), "small size: %lld sectors", &small_size);
+
+       // FS size in logical sectors if > 65535, or 0 otherwise
+       long long big_size = -1;
+       index = output.find("big size:");
+       if (index < output.length())
+               sscanf(output.substr(index).c_str(), "big size: %lld sectors", &big_size);
+
+       // FS size in logical sectors
+       long long logical_sectors = -1;
+       if (small_size > 0)
+               logical_sectors = small_size;
+       else if (big_size > 0)
+               logical_sectors = big_size;
+
+       if (bytes_free > -1 && logical_sector_size > -1 && cluster_size > -1 && logical_sectors > -1)
+       {
+               Sector fs_free = bytes_free / partition.sector_size;
+               Sector fs_size = logical_sectors * logical_sector_size / partition.sector_size;
+               partition.set_sector_usage(fs_size, fs_free);
+               partition.fs_block_size = logical_sector_size * cluster_size;
        }
 }
 
+
 void fat16::read_label( Partition & partition )
 {
        if ( ! Utils::execute_command( "mlabel -s :: -i " + Glib::shell_quote( partition.get_path() ),
@@ -279,4 +309,19 @@ const Glib::ustring fat16::sanitize_label( const Glib::ustring &label ) const
        return new_label ;
 }
 
+
+Glib::ustring fat16::remove_spaces(const Glib::ustring& str)
+{
+       Glib::ustring result;
+
+       for (unsigned int i = 0; i < str.size(); i++)
+       {
+               if (str[i] != ' ')
+                       result += str[i];
+       }
+
+       return result;
+}
+
+
 } //GParted