Re: Debbugs: The Next Generation

[tytso@mit.edu]

On Sat, Aug 18, 2001 at 01:52:56AM -0400, Matt Zimmerman wrote:
> On Tue, Aug 14, 2001 at 04:24:33PM +1000, Anthony Towns wrote:
> > That's not true: ext2 queries and directory lists are the problem here,
> > in that they're O(N) and O(N^2) rather than O(1)/O(N). Using reiser or
> > subdirectories would reduce those to O(lg(N)) and O(N lg(N)).
> 
> Why on earth are directory lists O(N^2)?  I don't know much about ext2
> internals, but that should be an O(N) operation in any sane filesystem.  

Doing a directory list is indeed O(N) for ext2.  

However, iterating through the directory using readdir() and then
stating or opening each file in readdir order is O(N**2).  There's a
very obvious optimization which makes this O(N), which I thought ext2
was using, but as it turns out, we weren't.

Thanks for bringing this to my attention; here's the very simple
kernel patch which should speed up a du or find of very large
directories significantly.

						- Ted

Patch generated: on Sat Aug 18 08:41:38 EDT 2001 by tytso@think
against Linux version 2.4.8
 
===================================================================
RCS file: fs/ext2/RCS/dir.c,v
retrieving revision 1.1
diff -u -r1.1 fs/ext2/dir.c
--- fs/ext2/dir.c	2001/08/18 11:11:30	1.1
+++ fs/ext2/dir.c	2001/08/18 12:41:10
@@ -303,7 +303,7 @@
 	const char *name = dentry->d_name.name;
 	int namelen = dentry->d_name.len;
 	unsigned reclen = EXT2_DIR_REC_LEN(namelen);
-	unsigned long n;
+	unsigned long start, n;
 	unsigned long npages = dir_pages(dir);
 	struct page *page = NULL;
 	ext2_dirent * de;
@@ -311,7 +311,11 @@
 	/* OFFSET_CACHE */
 	*res_page = NULL;
 
-	for (n = 0; n < npages; n++) {
+	start = dir->u.ext2_i.i_dir_start_lookup;
+	if (start >= npages)
+		start = 0;
+	n = start;
+	do {
 		char *kaddr;
 		page = ext2_get_page(dir, n);
 		if (IS_ERR(page))
@@ -324,11 +328,14 @@
 			if (ext2_match (namelen, name, de))
 				goto found;
 		ext2_put_page(page);
-	}
+		if (++n >= npages)
+			n = 0;
+	} while (n != start);
 	return NULL;
 
 found:
 	*res_page = page;
+	dir->u.ext2_i.i_dir_start_lookup = n;
 	return de;
 }
 
===================================================================
RCS file: include/linux/RCS/ext2_fs_i.h,v
retrieving revision 1.1
diff -u -r1.1 include/linux/ext2_fs_i.h
--- include/linux/ext2_fs_i.h	2001/08/18 11:10:48	1.1
+++ include/linux/ext2_fs_i.h	2001/08/18 11:11:18
@@ -34,6 +34,7 @@
 	__u32	i_next_alloc_goal;
 	__u32	i_prealloc_block;
 	__u32	i_prealloc_count;
+	__u32	i_dir_start_lookup;
 	int	i_new_inode:1;	/* Is a freshly allocated inode */
 };