[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