[BusyBox 0001123]: Tab completion with large numbers of files takes forever.

bugs at busybox.net bugs at busybox.net
Tue Dec 19 19:31:50 UTC 2006


A NOTE has been added to this issue. 
====================================================================== 
http://busybox.net/bugs/view.php?id=1123 
====================================================================== 
Reported By:                Marty
Assigned To:                BusyBox
====================================================================== 
Project:                    BusyBox
Issue ID:                   1123
Category:                   Other
Reproducibility:            always
Severity:                   crash
Priority:                   normal
Status:                     feedback
====================================================================== 
Date Submitted:             12-18-2006 06:33 PST
Last Modified:              12-19-2006 11:31 PST
====================================================================== 
Summary:                    Tab completion with large numbers of files takes
forever.
Description: 
If you create a large number of files in a directory, say 100,000 or so and
use tab completion, the shell 'locks up' as it is attempting to do 10
billion string comparisons, which will take quite some time to complete. 

I noticed this in the 1.1.0 version of busybox and confirmed that it still
exists in 1.3.0. To reproduce, run a script similar to this one:

 #! /usr/bin/perl

use strict;

sub main ()
{
    my $sPrefix = "interface-default";
    for ( my $i = 0; $i < 100000; ++$i )
    {
        my $sFilename = $sPrefix . "-" . $i;
        system ( "touch $sFilename" );
    }
}
main(); 

Then start a busybox shell, cd to the directory with the 100,000+ files
type 'inter' then press tab. 

To fix this, apply the following patch (also attached to bug):
diff -Naru busybox-1.3.0-orig/shell/cmdedit.c
busybox-1.3.0/shell/cmdedit.c
--- busybox-1.3.0-orig/shell/cmdedit.c  2006-12-13 00:09:53.000000000
+0000
+++ busybox-1.3.0/shell/cmdedit.c       2006-12-18 13:59:07.000000000
+0000
@@ -1022,6 +1022,10 @@
        }
 }

+static int match_compare(const void *a, const void *b)
+{
+       return strcmp(*(char **) a, *(char **) b);
+}

 static void input_tab(int *lastWasTab)
 {
@@ -1070,30 +1074,20 @@
                        exe_n_cwd_tab_completion(matchBuf, find_type);
                /* Remove duplicate found and sort */
                if(matches) {
-                       int i, j, n, srt;
-                       /* bubble */
-                       n = num_matches;
-                       for(i=0; i<(n-1); i++) {
-                               for(j=i+1; j<n; j++) {
-                                       if(matches[i]!=NULL &&
matches[j]!=NULL) {
-                                               srt = strcmp(matches[i],
matches[j]);
-                                               if(srt == 0) {
-                                                       free(matches[j]);
-                                                       matches[j]=0;
-                                               } else if(srt > 0) {
-                                                       tmp1 =
matches[i];
-                                                       matches[i] =
matches[j];
-                                                       matches[j] =
tmp1;
-                                                       srt =
add_char_to_match[i];
-                                                      
add_char_to_match[i] = add_char_to_match[j];
-                                                      
add_char_to_match[j] = srt;
-                                               }
-                                       }
-                               }
-                       }
-                       j = n;
+                       int i, n;
+            qsort(matches, num_matches, sizeof(char *), match_compare);
+
+                       for(i=0; i<num_matches-1; i++)
+            {
+                if( matches[i]!=NULL && matches[i+1]!=NULL &&
+                    strcmp ( matches[i], matches[i+1] ) == 0 )
+                {
+                    free ( matches[i+1] );
+                    matches[i+1] = 0;
+                }
+            }
                        n = 0;
-                       for(i=0; i<j; i++)
+                       for(i=0; i<num_matches; i++)
                                if(matches[i]) {
                                        matches[n]=matches[i];
                                       
add_char_to_match[n]=add_char_to_match[i];


====================================================================== 

---------------------------------------------------------------------- 
 vda - 12-18-06 17:10  
---------------------------------------------------------------------- 
The patch is buggy. It won't free() and NULL identical matches if you have
more than 2 of them in a row. [Patch is also severely whitespace-damaged
and doesn't match bbox style.]

But still, thanks... better than nothing. 

---------------------------------------------------------------------- 
 vda - 12-18-06 17:11  
---------------------------------------------------------------------- 
Fixed in rev 17003. 

---------------------------------------------------------------------- 
 Marty - 12-19-06 04:07  
---------------------------------------------------------------------- 
Hi Denis,

Thank you for catching the oversight in my patch. I am not hugely
concerned about whitespace or style, but at getting the algorithm correct
and fast.

Your patch contains one very important bug, in that, on my system at
least, qsort doesn't actually sort the array. I have modified my patch to
fix this problem, and also to collapse all three loops in this area of
code into a single loop. I also modified 'showfiles' to reduce the amount
of IO.

New patch is:

Index: shell/cmdedit.c
===================================================================
--- shell/cmdedit.c     (revision 17004)
+++ shell/cmdedit.c     (working copy)
@@ -989,18 +989,16 @@
                for(nc = 1; nc < ncols && n+nrows < nfiles; n += nrows,
nc++) {
                        str_add_chr[0] = add_char_to_match[n];
                        acol = str_add_chr[0] ? column_width - 1 :
column_width;
-                       printf("%s%s", matches[n], str_add_chr);
-                       l = strlen(matches[n]);
-                       while (l < acol) {
-                               putchar(' ');
-                               l++;
-                       }
+                       printf("%-*s", acol, matches[n] );
                }
                str_add_chr[0] = add_char_to_match[n];
                printf("%s%s\n", matches[n], str_add_chr);
        }
 }
-
+static int match_compare(const void *a, const void *b)
+{
+    return strcmp(*(char **) a, *(char **) b);
+}
 static void input_tab(int *lastWasTab)
 {
        /* Do TAB completion */
@@ -1045,35 +1043,26 @@
 #endif
                /* Try to match any executable in our path and everything
                 * in the current working directory that matches.  */
-                       exe_n_cwd_tab_completion(matchBuf, find_type);
-               /* Remove duplicate found and sort */
+               exe_n_cwd_tab_completion(matchBuf, find_type);
+               /* Sort, then remove any duplicates found */
                if (matches) {
-                       int i, n;
-                       /* strcmp is int(*f)(const char*, const char*) */
-                       /* qsort wants int(*f)(const void*, const void*)
*/
-                       /* We cheat here :) */
-                       qsort(matches, num_matches, sizeof(char*),
(void*)strcmp);
-                       i = 0;
-                       while (i < num_matches - 1) {
-                               n = i + 1;
-                               if (matches[i] && matches[n]) {
-                                       while (n < num_matches
-                                        && !strcmp(matches[i],
matches[n])) {
-                                               free(matches[n]);
-                                               matches[n] = 0;
-                                               n++;
-                                       }
-                               }
-                               i = n;
-                       }
-                       n = 0;
-                       for(i = 0; i < num_matches; i++)
-                               if (matches[i]) {
-                                       matches[n] = matches[i];
-                                       add_char_to_match[n] =
add_char_to_match[i];
-                                       n++;
-                               }
-                       num_matches = n;
+                       int i, n = 0;
+                       qsort(matches, num_matches, sizeof(char*),
match_compare);
+            for ( i = 0 ; i < num_matches -1 ; ++i ) {
+                if ( matches[i] != NULL && matches[i+1] != NULL ) {
+                    if ( 0 == strcmp ( matches[i], matches[i+1] ) ) {
+                        free ( matches[i] );
+                        matches[i] = 0;
+                    }
+                    else {
+                        add_char_to_match[n] = add_char_to_match[i];
+                        matches[n++] = matches[i];
+                    }
+                }
+            }
+            add_char_to_match[n] = add_char_to_match[num_matches-1];
+            matches[n++] = matches[num_matches-1];
+            num_matches = n;
                }
                /* Did we find exactly one match? */
                if (!matches || num_matches > 1) { 

---------------------------------------------------------------------- 
 Marty - 12-19-06 04:16  
---------------------------------------------------------------------- 
Hi Denis,

Sorry, realised when reading the patch after uploading that my change to
'showfiles' didn't output the 'str_add_chr'. The latest and greatest patch
is aptly named 'latest.busybox.patch'.

Thanks,

Martin 

---------------------------------------------------------------------- 
 vda - 12-19-06 11:30  
---------------------------------------------------------------------- 
Applied to svn. Try attached cmdedit.c file... 

---------------------------------------------------------------------- 
 vda - 12-19-06 11:31  
---------------------------------------------------------------------- 
And, btw, thanks for pointing out my bug! 

Issue History 
Date Modified   Username       Field                    Change               
====================================================================== 
12-18-06 06:33  Marty          New Issue                                    
12-18-06 06:33  Marty          Status                   new => assigned     
12-18-06 06:33  Marty          Assigned To               => BusyBox         
12-18-06 06:33  Marty          File Added: busybox.patch                    
12-18-06 17:10  vda            Note Added: 0001880                          
12-18-06 17:11  vda            Status                   assigned => closed  
12-18-06 17:11  vda            Note Added: 0001881                          
12-18-06 17:11  vda            Resolution               open => fixed       
12-19-06 04:07  Marty          Status                   closed => feedback  
12-19-06 04:07  Marty          Resolution               fixed => reopened   
12-19-06 04:07  Marty          Note Added: 0001882                          
12-19-06 04:08  Marty          File Added: updated.busybox.patch                
   
12-19-06 04:15  Marty          File Added: latest.busybox.patch                 
  
12-19-06 04:16  Marty          Note Added: 0001883                          
12-19-06 11:30  vda            Note Added: 0001884                          
12-19-06 11:31  vda            File Added: cmdedit.c                        
12-19-06 11:31  vda            Note Added: 0001885                          
======================================================================




More information about the busybox-cvs mailing list