BUG in fs/ext3/dir.c

BUG in fs/ext3/dir.c

[Holger Kiehl]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2460 bytes --]

Hello

[Sorry if you get this twice. This was send to ext3-users@redhat.com and
 the authors of ext3, but got no responce.]

When using readdir() on a directory with many files or long file names
it can happen that it returns the same file name twice. Attached is
a program that demonstrates this. To produce the error start the program
as follows:

     ./a.out 200 20
     BUG: 00000000000000000061 appears twice!
     stat() error (testbugdir/input/00000000000000000061) : No such file or directory
     BUG: 00000000000000000061 appears twice!
     unlink() error (testbugdir/output/00000000000000000061) : No such file or directory

or:

     ./a.out 50 61
     BUG: 0000000000000000000000000000000000000000000000000000000000020 appears twice!
     stat() error (testbugdir/input/0000000000000000000000000000000000000000000000000000000000020) : No such file or directory
     unlink() error (testbugdir/output/0000000000000000000000000000000000000000000000000000000000020) : No such file or directory

First parameter is the number of files, second the file name length.

I have traced this problem back to linux-2.6.10-rc1-bk18 and all kernels
after this one are effected. linux-2.6.10-rc1-bk17 is okay. If I reverse
the following patch in linux-2.6.10-rc1-bk18, readdir() works again
correctly:

diff -Nru linux-2.6.10-rc1-bk17/fs/ext3/dir.c linux-2.6.10-rc1-bk18/fs/ext3/dir.c
--- linux-2.6.10-rc1-bk17/fs/ext3/dir.c	2004-10-18 23:54:30.000000000 +0200
+++ linux-2.6.10-rc1-bk18/fs/ext3/dir.c	2004-12-05 16:44:21.000000000 +0100
@@ -418,7 +418,7 @@
 				get_dtype(sb, fname->file_type));
 		if (error) {
 			filp->f_pos = curr_pos;
-			info->extra_fname = fname->next;
+			info->extra_fname = fname;
 			return error;
 		}
 		fname = fname->next;
@@ -457,9 +457,12 @@
 	 * If there are any leftover names on the hash collision
 	 * chain, return them first.
 	 */
-	if (info->extra_fname &&
-	    call_filldir(filp, dirent, filldir, info->extra_fname))
-		goto finished;
+	if (info->extra_fname) {
+		if(call_filldir(filp, dirent, filldir, info->extra_fname))
+			goto finished;
+		else
+			goto next_entry;
+	}
 
 	if (!info->curr_node)
 		info->curr_node = rb_first(&info->root);
@@ -492,7 +495,7 @@
 		info->curr_minor_hash = fname->minor_hash;
 		if (call_filldir(filp, dirent, filldir, fname))
 			break;
-
+next_entry:
 		info->curr_node = rb_next(info->curr_node);
 		if (!info->curr_node) {
 			if (info->next_hash == ~0) {

Regards,
Holger
-- 

[-- Attachment #2: Type: TEXT/PLAIN, Size: 3676 bytes --]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <fcntl.h>
#include <errno.h>

int
main(int argc, char *argv[])
{
   int           fd, filename_length, i, j, no_of_files;
   char          pathname[256], *ptr,
                 prevname[256],
                 to_pathname[256], *to_ptr;
   DIR           *dp;
   struct dirent *p_dir;
   struct stat   stat_buf;

   if (argc != 3)
   {
      fprintf(stderr, "Usage: %s <no. of files> <filename length>\n", argv[0]);
      exit(1);
   }
   else
   {
      no_of_files = atoi(argv[1]);
      filename_length = atoi(argv[2]);
   }

   /* Create necessary dirs. */
   (void)mkdir("testbugdir", S_IRUSR|S_IWUSR|S_IXUSR);
   (void)mkdir("testbugdir/input", S_IRUSR|S_IWUSR|S_IXUSR);
   (void)mkdir("testbugdir/output", S_IRUSR|S_IWUSR|S_IXUSR);

   /* Create input files. */
   strcpy(pathname, "testbugdir/input/");
   ptr = pathname + strlen(pathname);
   for (i = 0; i < no_of_files; i++)
   {
      sprintf(ptr, "%0*d", filename_length, i);
      if ((fd = open(pathname, O_RDWR|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR)) == -1)
      {
         fprintf(stderr, "open() error %s : %s\n", pathname, strerror(errno));
         exit(1);
      }
      close(fd);
   }

   /* Move input files to output. */
   strcpy(to_pathname, "testbugdir/output/");
   to_ptr = to_pathname + strlen(to_pathname);
   *ptr = '\0';
   if ((dp = opendir(pathname)) == NULL)
   {
      fprintf(stderr, "opendir() error (%s) : %s\n",
              pathname, strerror(errno));
      exit(1);
   }
   prevname[0] = '\0';
   while ((p_dir = readdir(dp)) != NULL)
   {
      if (p_dir->d_name[0] == '.')
      {
         continue;
      }
      if (strcmp(prevname, p_dir->d_name) == 0)
      {
         fprintf(stderr, "BUG: %s appears twice!\n", p_dir->d_name);
      }
      strcpy(prevname, p_dir->d_name);
      strcpy(ptr, p_dir->d_name);
      if (stat(pathname, &stat_buf) < 0)
      {
         fprintf(stderr, "stat() error (%s) : %s\n",
                 pathname, strerror(errno));
         continue;
      }
      strcpy(to_ptr, p_dir->d_name);
      if (rename(pathname, to_pathname) == -1)
      {
         fprintf(stderr, "rename() error (file %d) : %s\n",
                 pathname, strerror(errno));
      }
   }
   (void)closedir(dp);

   /* Remove everyting. */
   *to_ptr = '\0';
   if ((dp = opendir(to_pathname)) == NULL)
   {
      fprintf(stderr, "opendir() error (%s) : %s\n",
              to_pathname, strerror(errno));
      exit(1);
   }
   prevname[0] = '\0';
   while ((p_dir = readdir(dp)) != NULL)
   {
      if (p_dir->d_name[0] == '.')
      {
         continue;
      }
      if (strcmp(prevname, p_dir->d_name) == 0)
      {
         fprintf(stderr, "BUG: %s appears twice!\n", p_dir->d_name);
      }
      strcpy(prevname, p_dir->d_name);
      strcpy(to_ptr, p_dir->d_name);
      if (unlink(to_pathname) == -1)
      {
         fprintf(stderr, "unlink() error (%s) : %s\n",
                 to_pathname, strerror(errno));
         continue;
      }
   }
   (void)closedir(dp);
   if (rmdir("testbugdir/input") == -1)
   {
      fprintf(stderr, "rmdir() error (testbugdir/input) : %s\n",
              strerror(errno));
   }
   if (rmdir("testbugdir/output") == -1)
   {
      fprintf(stderr, "rmdir() error (testbugdir/output) : %s\n",
              strerror(errno));
   }
   if (rmdir("testbugdir") == -1)
   {
      fprintf(stderr, "rmdir() error (testbugdir) : %s\n", strerror(errno));
   }

   exit(0);
}

Re: BUG in fs/ext3/dir.c

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 7528 bytes --]

On Dec 07, 2004  09:56 +0000, Holger Kiehl wrote:
> When using readdir() on a directory with many files or long file names
> it can happen that it returns the same file name twice. Attached is
> a program that demonstrates this. To produce the error start the program
> as follows:
> 
>      ./a.out 200 20
>      BUG: 00000000000000000061 appears twice!
>      stat() error (testbugdir/input/00000000000000000061) : No such file or directory
>      BUG: 00000000000000000061 appears twice!
>      unlink() error (testbugdir/output/00000000000000000061) : No such file or directory
> 
> or:
> 
>      ./a.out 50 61
>      BUG: 0000000000000000000000000000000000000000000000000000000000020 appears twice!
>      stat() error (testbugdir/input/0000000000000000000000000000000000000000000000000000000000020) : No such file or directory
>      unlink() error (testbugdir/output/0000000000000000000000000000000000000000000000000000000000020) : No such file or directory
> 
> First parameter is the number of files, second the file name length.
> 
> I have traced this problem back to linux-2.6.10-rc1-bk18 and all kernels
> after this one are effected. linux-2.6.10-rc1-bk17 is okay. If I reverse
> the following patch in linux-2.6.10-rc1-bk18, readdir() works again
> correctly:

This patch was added by Ted & Andrew because of some other problem when
handling duplicate hash values.  It looks like the relevant thread is at:

http://marc.theaimsgroup.com/?t=110062880800001&r=1&w=4

#       When there are more than one entry in fname linked list, the current
#       implementation of ext3_dx_readdir() can not traverse all entries
#       correctly in the case that call_filldir() fails.
#   
#       If we use system call readdir() to read entries in a directory which
#       happens that "." and ".." in the same fname linked list.  Each time we
#       call readdir(), it will return the "." entry and never returns 0 which
#       indicates that all entries are read.
#   
#       Although chances that more than one entry are in one fname linked list
#       are very slim, it does exist.

> diff -Nru linux-2.6.10-rc1-bk17/fs/ext3/dir.c linux-2.6.10-rc1-bk18/fs/ext3/dir.c
> --- linux-2.6.10-rc1-bk17/fs/ext3/dir.c	2004-10-18 23:54:30.000000000 +0200
> +++ linux-2.6.10-rc1-bk18/fs/ext3/dir.c	2004-12-05 16:44:21.000000000 +0100
> @@ -418,7 +418,7 @@
>  				get_dtype(sb, fname->file_type));
>  		if (error) {
>  			filp->f_pos = curr_pos;
> -			info->extra_fname = fname->next;
> +			info->extra_fname = fname;
>  			return error;
>  		}
>  		fname = fname->next;
> @@ -457,9 +457,12 @@
>  	 * If there are any leftover names on the hash collision
>  	 * chain, return them first.
>  	 */
> -	if (info->extra_fname &&
> -	    call_filldir(filp, dirent, filldir, info->extra_fname))
> -		goto finished;
> +	if (info->extra_fname) {
> +		if(call_filldir(filp, dirent, filldir, info->extra_fname))
> +			goto finished;
> +		else
> +			goto next_entry;
> +	}
>  
>  	if (!info->curr_node)
>  		info->curr_node = rb_first(&info->root);
> @@ -492,7 +495,7 @@
>  		info->curr_minor_hash = fname->minor_hash;
>  		if (call_filldir(filp, dirent, filldir, fname))
>  			break;
> -
> +next_entry:
>  		info->curr_node = rb_next(info->curr_node);
>  		if (!info->curr_node) {
>  			if (info->next_hash == ~0) {
> 
> Regards,
> Holger
> -- 
> #include <stdio.h>
> #include <string.h>
> #include <stdlib.h>
> #include <sys/types.h>
> #include <sys/stat.h>
> #include <dirent.h>
> #include <fcntl.h>
> #include <errno.h>
> 
> int
> main(int argc, char *argv[])
> {
>    int           fd, filename_length, i, j, no_of_files;
>    char          pathname[256], *ptr,
>                  prevname[256],
>                  to_pathname[256], *to_ptr;
>    DIR           *dp;
>    struct dirent *p_dir;
>    struct stat   stat_buf;
> 
>    if (argc != 3)
>    {
>       fprintf(stderr, "Usage: %s <no. of files> <filename length>\n", argv[0]);
>       exit(1);
>    }
>    else
>    {
>       no_of_files = atoi(argv[1]);
>       filename_length = atoi(argv[2]);
>    }
> 
>    /* Create necessary dirs. */
>    (void)mkdir("testbugdir", S_IRUSR|S_IWUSR|S_IXUSR);
>    (void)mkdir("testbugdir/input", S_IRUSR|S_IWUSR|S_IXUSR);
>    (void)mkdir("testbugdir/output", S_IRUSR|S_IWUSR|S_IXUSR);
> 
>    /* Create input files. */
>    strcpy(pathname, "testbugdir/input/");
>    ptr = pathname + strlen(pathname);
>    for (i = 0; i < no_of_files; i++)
>    {
>       sprintf(ptr, "%0*d", filename_length, i);
>       if ((fd = open(pathname, O_RDWR|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR)) == -1)
>       {
>          fprintf(stderr, "open() error %s : %s\n", pathname, strerror(errno));
>          exit(1);
>       }
>       close(fd);
>    }
> 
>    /* Move input files to output. */
>    strcpy(to_pathname, "testbugdir/output/");
>    to_ptr = to_pathname + strlen(to_pathname);
>    *ptr = '\0';
>    if ((dp = opendir(pathname)) == NULL)
>    {
>       fprintf(stderr, "opendir() error (%s) : %s\n",
>               pathname, strerror(errno));
>       exit(1);
>    }
>    prevname[0] = '\0';
>    while ((p_dir = readdir(dp)) != NULL)
>    {
>       if (p_dir->d_name[0] == '.')
>       {
>          continue;
>       }
>       if (strcmp(prevname, p_dir->d_name) == 0)
>       {
>          fprintf(stderr, "BUG: %s appears twice!\n", p_dir->d_name);
>       }
>       strcpy(prevname, p_dir->d_name);
>       strcpy(ptr, p_dir->d_name);
>       if (stat(pathname, &stat_buf) < 0)
>       {
>          fprintf(stderr, "stat() error (%s) : %s\n",
>                  pathname, strerror(errno));
>          continue;
>       }
>       strcpy(to_ptr, p_dir->d_name);
>       if (rename(pathname, to_pathname) == -1)
>       {
>          fprintf(stderr, "rename() error (file %d) : %s\n",
>                  pathname, strerror(errno));
>       }
>    }
>    (void)closedir(dp);
> 
>    /* Remove everyting. */
>    *to_ptr = '\0';
>    if ((dp = opendir(to_pathname)) == NULL)
>    {
>       fprintf(stderr, "opendir() error (%s) : %s\n",
>               to_pathname, strerror(errno));
>       exit(1);
>    }
>    prevname[0] = '\0';
>    while ((p_dir = readdir(dp)) != NULL)
>    {
>       if (p_dir->d_name[0] == '.')
>       {
>          continue;
>       }
>       if (strcmp(prevname, p_dir->d_name) == 0)
>       {
>          fprintf(stderr, "BUG: %s appears twice!\n", p_dir->d_name);
>       }
>       strcpy(prevname, p_dir->d_name);
>       strcpy(to_ptr, p_dir->d_name);
>       if (unlink(to_pathname) == -1)
>       {
>          fprintf(stderr, "unlink() error (%s) : %s\n",
>                  to_pathname, strerror(errno));
>          continue;
>       }
>    }
>    (void)closedir(dp);
>    if (rmdir("testbugdir/input") == -1)
>    {
>       fprintf(stderr, "rmdir() error (testbugdir/input) : %s\n",
>               strerror(errno));
>    }
>    if (rmdir("testbugdir/output") == -1)
>    {
>       fprintf(stderr, "rmdir() error (testbugdir/output) : %s\n",
>               strerror(errno));
>    }
>    if (rmdir("testbugdir") == -1)
>    {
>       fprintf(stderr, "rmdir() error (testbugdir) : %s\n", strerror(errno));
>    }
> 
>    exit(0);
> }


Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://members.shaw.ca/adilger/             http://members.shaw.ca/golinux/


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: BUG in fs/ext3/dir.c

[Theodore Ts'o]

On Tue, Dec 07, 2004 at 09:56:26AM +0000, Holger Kiehl wrote:
> [Sorry if you get this twice. This was send to ext3-users@redhat.com and
>  the authors of ext3, but got no responce.]

I'm on ext3-users, but I didn't get the e-mail.....  so this is the
first time I've seen this.

> When using readdir() on a directory with many files or long file names
> it can happen that it returns the same file name twice. Attached is
> a program that demonstrates this. 

Thanks for the test case, I'm currently looking at the problem....

						- Ted

Re: BUG in fs/ext3/dir.c

[Holger Kiehl]

On Tue, 7 Dec 2004, Theodore Ts'o wrote:

> On Tue, Dec 07, 2004 at 09:56:26AM +0000, Holger Kiehl wrote:
> > [Sorry if you get this twice. This was send to ext3-users@redhat.com and
> >  the authors of ext3, but got no responce.]
> 
> I'm on ext3-users, but I didn't get the e-mail.....  so this is the
> first time I've seen this.
> 
> > When using readdir() on a directory with many files or long file names
> > it can happen that it returns the same file name twice. Attached is
> > a program that demonstrates this. 
> 
> Thanks for the test case, I'm currently looking at the problem....
> 
I see that Andrew Morton took out the relevant patch and that
Kris Karas reported some filesytem corruption. In my case it did NOT
corrupt the filesystem. I just checked it after some millions of files
went through the system for some days.

Holger