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

[bugs at busybox.net]

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:                     assigned
====================================================================== 
Date Submitted:             12-18-2006 06:33 PST
Last Modified:              12-18-2006 17:10 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. 

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