[EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Mingming Cao]

>From kalpak@clusterfs.com Thu May 17 17:21:08 2007
Hi,

I have rebased this patch to 2.6.22-rc1 so that it can be added to the
ext4 patch queue. It has been tested by creating more than 65000 subdirs
and then deleting them and checking the nlinks. The e2fsprogs part of
this patch was sent earlier by me to linux-ext4 and doesn't need any
changes, so not submitting it again.

----------------------------------------------------------------------
This patch adds support to ext4 for allowing more than 65000
subdirectories. Currently the maximum number of subdirectories is capped
at 32000.

If we exceed 65000 subdirectories in an htree directory it sets the
inode link count to 1 and no longer counts subdirectories.  The
directory link count is not actually used when determining if a
directory is empty, as that only counts subdirectories and not regular
files that might be in there. 

A EXT4_FEATURE_RO_COMPAT_DIR_NLINK flag has been added and it is set if
the subdir count for any directory crosses 65000.

Signed-off-by: Andreas Dilger <adilger@clusterfs.com>
Signed-off-by: Kalpak Shah <kalpak@clusterfs.com>


Index: linux-2.6.22-rc4/fs/ext4/namei.c
===================================================================
--- linux-2.6.22-rc4.orig/fs/ext4/namei.c	2007-06-14 17:30:47.000000000 -0700
+++ linux-2.6.22-rc4/fs/ext4/namei.c	2007-06-14 17:32:55.000000000 -0700
@@ -1619,6 +1619,27 @@ static int ext4_delete_entry (handle_t *
 	return -ENOENT;
 }
 
+static inline void ext4_inc_count(handle_t *handle, struct inode *inode)
+{
+	inc_nlink(inode);
+	if (is_dx(inode) && inode->i_nlink > 1) {
+		/* limit is 16-bit i_links_count */
+		if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
+			inode->i_nlink = 1;
+			EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
+					      EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
+		}
+	}
+}
+
+static inline void ext4_dec_count(handle_t *handle, struct inode *inode)
+{
+	drop_nlink(inode);
+	if (S_ISDIR(inode->i_mode) && inode->i_nlink == 0)
+		inc_nlink(inode);
+}
+
+
 static int ext4_add_nondir(handle_t *handle,
 		struct dentry *dentry, struct inode *inode)
 {
@@ -1715,7 +1736,7 @@ static int ext4_mkdir(struct inode * dir
 	struct ext4_dir_entry_2 * de;
 	int err, retries = 0;
 
-	if (dir->i_nlink >= EXT4_LINK_MAX)
+	if (EXT4_DIR_LINK_MAX(dir))
 		return -EMLINK;
 
 retry:
@@ -1738,7 +1759,7 @@ retry:
 	inode->i_size = EXT4_I(inode)->i_disksize = inode->i_sb->s_blocksize;
 	dir_block = ext4_bread (handle, inode, 0, 1, &err);
 	if (!dir_block) {
-		drop_nlink(inode); /* is this nlink == 0? */
+		ext4_dec_count(handle, inode); /* is this nlink == 0? */
 		ext4_mark_inode_dirty(handle, inode);
 		iput (inode);
 		goto out_stop;
@@ -1770,7 +1791,7 @@ retry:
 		iput (inode);
 		goto out_stop;
 	}
-	inc_nlink(dir);
+	ext4_inc_count(handle, dir);
 	ext4_update_dx_flag(dir);
 	ext4_mark_inode_dirty(handle, dir);
 	d_instantiate(dentry, inode);
@@ -2035,10 +2056,10 @@ static int ext4_rmdir (struct inode * di
 	retval = ext4_delete_entry(handle, dir, de, bh);
 	if (retval)
 		goto end_rmdir;
-	if (inode->i_nlink != 2)
-		ext4_warning (inode->i_sb, "ext4_rmdir",
-			      "empty directory has nlink!=2 (%d)",
-			      inode->i_nlink);
+	if (!EXT4_DIR_LINK_EMPTY(inode))
+		ext4_warning(inode->i_sb, "ext4_rmdir",
+			     "empty directory has too many links (%d)",
+			     inode->i_nlink);
 	inode->i_version++;
 	clear_nlink(inode);
 	/* There's no need to set i_disksize: the fact that i_nlink is
@@ -2048,7 +2069,7 @@ static int ext4_rmdir (struct inode * di
 	ext4_orphan_add(handle, inode);
 	inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
 	ext4_mark_inode_dirty(handle, inode);
-	drop_nlink(dir);
+	ext4_dec_count(handle, dir);
 	ext4_update_dx_flag(dir);
 	ext4_mark_inode_dirty(handle, dir);
 
@@ -2099,7 +2120,7 @@ static int ext4_unlink(struct inode * di
 	dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
 	ext4_update_dx_flag(dir);
 	ext4_mark_inode_dirty(handle, dir);
-	drop_nlink(inode);
+	ext4_dec_count(handle, inode);
 	if (!inode->i_nlink)
 		ext4_orphan_add(handle, inode);
 	inode->i_ctime = ext4_current_time(inode);
@@ -2149,7 +2170,7 @@ retry:
 		err = __page_symlink(inode, symname, l,
 				mapping_gfp_mask(inode->i_mapping) & ~__GFP_FS);
 		if (err) {
-			drop_nlink(inode);
+			ext4_dec_count(handle, inode);
 			ext4_mark_inode_dirty(handle, inode);
 			iput (inode);
 			goto out_stop;
@@ -2175,8 +2196,9 @@ static int ext4_link (struct dentry * ol
 	struct inode *inode = old_dentry->d_inode;
 	int err, retries = 0;
 
-	if (inode->i_nlink >= EXT4_LINK_MAX)
+	if (EXT4_DIR_LINK_MAX(inode))
 		return -EMLINK;
+
 	/*
 	 * Return -ENOENT if we've raced with unlink and i_nlink is 0.  Doing
 	 * otherwise has the potential to corrupt the orphan inode list.
@@ -2194,7 +2216,7 @@ retry:
 		handle->h_sync = 1;
 
 	inode->i_ctime = ext4_current_time(inode);
-	inc_nlink(inode);
+	ext4_inc_count(handle, inode);
 	atomic_inc(&inode->i_count);
 
 	err = ext4_add_nondir(handle, dentry, inode);
@@ -2327,7 +2349,7 @@ static int ext4_rename (struct inode * o
 	}
 
 	if (new_inode) {
-		drop_nlink(new_inode);
+		ext4_dec_count(handle, new_inode);
 		new_inode->i_ctime = ext4_current_time(new_inode);
 	}
 	old_dir->i_ctime = old_dir->i_mtime = ext4_current_time(old_dir);
@@ -2338,11 +2360,13 @@ static int ext4_rename (struct inode * o
 		PARENT_INO(dir_bh->b_data) = cpu_to_le32(new_dir->i_ino);
 		BUFFER_TRACE(dir_bh, "call ext4_journal_dirty_metadata");
 		ext4_journal_dirty_metadata(handle, dir_bh);
-		drop_nlink(old_dir);
+		ext4_dec_count(handle, old_dir);
 		if (new_inode) {
-			drop_nlink(new_inode);
+			/* checked empty_dir above, can't have another parent,
+			 * ext3_dec_count() won't work for many-linked dirs */
+			new_inode->i_nlink = 0;
 		} else {
-			inc_nlink(new_dir);
+			ext4_inc_count(handle, new_dir);
 			ext4_update_dx_flag(new_dir);
 			ext4_mark_inode_dirty(handle, new_dir);
 		}
Index: linux-2.6.22-rc4/include/linux/ext4_fs.h
===================================================================
--- linux-2.6.22-rc4.orig/include/linux/ext4_fs.h	2007-06-14 17:32:41.000000000 -0700
+++ linux-2.6.22-rc4/include/linux/ext4_fs.h	2007-06-14 17:32:55.000000000 -0700
@@ -71,7 +71,7 @@
 /*
  * Maximal count of links to a file
  */
-#define EXT4_LINK_MAX		32000
+#define EXT4_LINK_MAX		65000
 
 /*
  * Macro-instructions used to manage several block sizes
@@ -685,6 +685,7 @@ static inline int ext4_valid_inum(struct
 #define EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER	0x0001
 #define EXT4_FEATURE_RO_COMPAT_LARGE_FILE	0x0002
 #define EXT4_FEATURE_RO_COMPAT_BTREE_DIR	0x0004
+#define EXT4_FEATURE_RO_COMPAT_DIR_NLINK	0x0020
 #define EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE	0x0040
 
 #define EXT4_FEATURE_INCOMPAT_COMPRESSION	0x0001
@@ -703,6 +704,7 @@ static inline int ext4_valid_inum(struct
 					 EXT4_FEATURE_INCOMPAT_64BIT)
 #define EXT4_FEATURE_RO_COMPAT_SUPP	(EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER| \
 					 EXT4_FEATURE_RO_COMPAT_LARGE_FILE| \
+					 EXT4_FEATURE_RO_COMPAT_DIR_NLINK | \
 					 EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE | \
 					 EXT4_FEATURE_RO_COMPAT_BTREE_DIR)
 

Re: [EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Andrew Morton]

On Sun, 01 Jul 2007 03:38:18 -0400 Mingming Cao <cmm@us.ibm.com> wrote:

> >From kalpak@clusterfs.com Thu May 17 17:21:08 2007
> Hi,
> 
> I have rebased this patch to 2.6.22-rc1 so that it can be added to the
> ext4 patch queue. It has been tested by creating more than 65000 subdirs
> and then deleting them and checking the nlinks. The e2fsprogs part of
> this patch was sent earlier by me to linux-ext4 and doesn't need any
> changes, so not submitting it again.
> 
> ----------------------------------------------------------------------
> This patch adds support to ext4 for allowing more than 65000
> subdirectories. Currently the maximum number of subdirectories is capped
> at 32000.
> 
> If we exceed 65000 subdirectories in an htree directory it sets the
> inode link count to 1 and no longer counts subdirectories.  The
> directory link count is not actually used when determining if a
> directory is empty, as that only counts subdirectories and not regular
> files that might be in there. 
> 
> A EXT4_FEATURE_RO_COMPAT_DIR_NLINK flag has been added and it is set if
> the subdir count for any directory crosses 65000.
> 

Would I be correct in assuming that a later fsck will clear
EXT4_FEATURE_RO_COMPAT_DIR_NLINK if there are no longer any >65000 subdir
directories?

If so, that is worth a mention in the changelog, perhaps?

Please remind us what is the behaviour of an RO_COMPAT flag?  It means that
old ext4, ext3 and ext2 can only mount this fs read-only, yes?

> 
> Index: linux-2.6.22-rc4/fs/ext4/namei.c
> ===================================================================
> --- linux-2.6.22-rc4.orig/fs/ext4/namei.c	2007-06-14 17:30:47.000000000 -0700
> +++ linux-2.6.22-rc4/fs/ext4/namei.c	2007-06-14 17:32:55.000000000 -0700
> @@ -1619,6 +1619,27 @@ static int ext4_delete_entry (handle_t *
>  	return -ENOENT;
>  }
>  
> +static inline void ext4_inc_count(handle_t *handle, struct inode *inode)
> +{
> +	inc_nlink(inode);
> +	if (is_dx(inode) && inode->i_nlink > 1) {
> +		/* limit is 16-bit i_links_count */
> +		if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
> +			inode->i_nlink = 1;
> +			EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
> +					      EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
> +		}
> +	}
> +}

Looks too big to be inlined.

Why do we set EXT4_FEATURE_RO_COMPAT_DIR_NLINK if i_nlink==2?

> +static inline void ext4_dec_count(handle_t *handle, struct inode *inode)
> +{
> +	drop_nlink(inode);
> +	if (S_ISDIR(inode->i_mode) && inode->i_nlink == 0)
> +		inc_nlink(inode);
> +}

Probably too big to inline.

> +
>  static int ext4_add_nondir(handle_t *handle,
>  		struct dentry *dentry, struct inode *inode)
>  {
> @@ -1715,7 +1736,7 @@ static int ext4_mkdir(struct inode * dir
>  	struct ext4_dir_entry_2 * de;
>  	int err, retries = 0;
>  
> -	if (dir->i_nlink >= EXT4_LINK_MAX)
> +	if (EXT4_DIR_LINK_MAX(dir))
>  		return -EMLINK;
>  
>  retry:
> @@ -1738,7 +1759,7 @@ retry:
>  	inode->i_size = EXT4_I(inode)->i_disksize = inode->i_sb->s_blocksize;
>  	dir_block = ext4_bread (handle, inode, 0, 1, &err);
>  	if (!dir_block) {
> -		drop_nlink(inode); /* is this nlink == 0? */
> +		ext4_dec_count(handle, inode); /* is this nlink == 0? */
>  		ext4_mark_inode_dirty(handle, inode);
>  		iput (inode);
>  		goto out_stop;
> @@ -1770,7 +1791,7 @@ retry:
>  		iput (inode);
>  		goto out_stop;
>  	}
> -	inc_nlink(dir);
> +	ext4_inc_count(handle, dir);
>  	ext4_update_dx_flag(dir);
>  	ext4_mark_inode_dirty(handle, dir);
>  	d_instantiate(dentry, inode);
> @@ -2035,10 +2056,10 @@ static int ext4_rmdir (struct inode * di
>  	retval = ext4_delete_entry(handle, dir, de, bh);
>  	if (retval)
>  		goto end_rmdir;
> -	if (inode->i_nlink != 2)
> -		ext4_warning (inode->i_sb, "ext4_rmdir",
> -			      "empty directory has nlink!=2 (%d)",
> -			      inode->i_nlink);
> +	if (!EXT4_DIR_LINK_EMPTY(inode))
> +		ext4_warning(inode->i_sb, "ext4_rmdir",
> +			     "empty directory has too many links (%d)",
> +			     inode->i_nlink);
>  	inode->i_version++;
>  	clear_nlink(inode);
>  	/* There's no need to set i_disksize: the fact that i_nlink is
> @@ -2048,7 +2069,7 @@ static int ext4_rmdir (struct inode * di
>  	ext4_orphan_add(handle, inode);
>  	inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
>  	ext4_mark_inode_dirty(handle, inode);
> -	drop_nlink(dir);
> +	ext4_dec_count(handle, dir);
>  	ext4_update_dx_flag(dir);
>  	ext4_mark_inode_dirty(handle, dir);
>  
> @@ -2099,7 +2120,7 @@ static int ext4_unlink(struct inode * di
>  	dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
>  	ext4_update_dx_flag(dir);
>  	ext4_mark_inode_dirty(handle, dir);
> -	drop_nlink(inode);
> +	ext4_dec_count(handle, inode);
>  	if (!inode->i_nlink)
>  		ext4_orphan_add(handle, inode);
>  	inode->i_ctime = ext4_current_time(inode);
> @@ -2149,7 +2170,7 @@ retry:
>  		err = __page_symlink(inode, symname, l,
>  				mapping_gfp_mask(inode->i_mapping) & ~__GFP_FS);
>  		if (err) {
> -			drop_nlink(inode);
> +			ext4_dec_count(handle, inode);
>  			ext4_mark_inode_dirty(handle, inode);
>  			iput (inode);
>  			goto out_stop;
> @@ -2175,8 +2196,9 @@ static int ext4_link (struct dentry * ol
>  	struct inode *inode = old_dentry->d_inode;
>  	int err, retries = 0;
>  
> -	if (inode->i_nlink >= EXT4_LINK_MAX)
> +	if (EXT4_DIR_LINK_MAX(inode))
>  		return -EMLINK;

argh.  WHY_IS_EXT4_FULL_OF_UPPER_CASE_MACROS_WHICH_COULD_BE_IMPLEMENTED
as_lower_case_inlines?  Sigh.  It's all the old-timers, I guess.

EXT4_DIR_LINK_MAX() is buggy: it evaluates its arg twice.

>  	/*
>  	 * Return -ENOENT if we've raced with unlink and i_nlink is 0.  Doing
>  	 * otherwise has the potential to corrupt the orphan inode list.
> @@ -2194,7 +2216,7 @@ retry:
>  		handle->h_sync = 1;
>  
>  	inode->i_ctime = ext4_current_time(inode);
> -	inc_nlink(inode);
> +	ext4_inc_count(handle, inode);
>  	atomic_inc(&inode->i_count);
>  
>  	err = ext4_add_nondir(handle, dentry, inode);
> @@ -2327,7 +2349,7 @@ static int ext4_rename (struct inode * o
>  	}
>  
>  	if (new_inode) {
> -		drop_nlink(new_inode);
> +		ext4_dec_count(handle, new_inode);
>  		new_inode->i_ctime = ext4_current_time(new_inode);
>  	}
>  	old_dir->i_ctime = old_dir->i_mtime = ext4_current_time(old_dir);
> @@ -2338,11 +2360,13 @@ static int ext4_rename (struct inode * o
>  		PARENT_INO(dir_bh->b_data) = cpu_to_le32(new_dir->i_ino);
>  		BUFFER_TRACE(dir_bh, "call ext4_journal_dirty_metadata");
>  		ext4_journal_dirty_metadata(handle, dir_bh);
> -		drop_nlink(old_dir);
> +		ext4_dec_count(handle, old_dir);
>  		if (new_inode) {
> -			drop_nlink(new_inode);
> +			/* checked empty_dir above, can't have another parent,
> +			 * ext3_dec_count() won't work for many-linked dirs */
> +			new_inode->i_nlink = 0;
>  		} else {
> -			inc_nlink(new_dir);
> +			ext4_inc_count(handle, new_dir);
>  			ext4_update_dx_flag(new_dir);
>  			ext4_mark_inode_dirty(handle, new_dir);
>  		}

Re: [EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Andreas Dilger]

On Jul 10, 2007  22:40 -0700, Andrew Morton wrote:
> On Sun, 01 Jul 2007 03:38:18 -0400 Mingming Cao <cmm@us.ibm.com> wrote:
> > A EXT4_FEATURE_RO_COMPAT_DIR_NLINK flag has been added and it is set if
> > the subdir count for any directory crosses 65000.
> 
> Would I be correct in assuming that a later fsck will clear
> EXT4_FEATURE_RO_COMPAT_DIR_NLINK if there are no longer any >65000 subdir
> directories?

Correct.

> If so, that is worth a mention in the changelog, perhaps?
> 
> Please remind us what is the behaviour of an RO_COMPAT flag?  It means that
> old ext4, ext3 and ext2 can only mount this fs read-only, yes?

Also correct.  The COMPAT flag behaviour is described in detail in
Documentation/filesystems/ext[234].txt

> > +static inline void ext4_inc_count(handle_t *handle, struct inode *inode)
> > +{
> > +	inc_nlink(inode);
> > +	if (is_dx(inode) && inode->i_nlink > 1) {
> > +		/* limit is 16-bit i_links_count */
> > +		if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
> > +			inode->i_nlink = 1;
> > +			EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
> > +					      EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
> > +		}
> > +	}
> > +}
> 
> Why do we set EXT4_FEATURE_RO_COMPAT_DIR_NLINK if i_nlink==2?

Because that means it was previously 1 (inc_nlink() was already called).

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

Re: [EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Kalpak Shah]

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

The updated patch is attached. comments inline...

On Tue, 2007-07-10 at 22:40 -0700, Andrew Morton wrote:
> > If we exceed 65000 subdirectories in an htree directory it sets the
> > inode link count to 1 and no longer counts subdirectories.  The
> > directory link count is not actually used when determining if a
> > directory is empty, as that only counts subdirectories and not regular
> > files that might be in there. 
> > 
> > A EXT4_FEATURE_RO_COMPAT_DIR_NLINK flag has been added and it is set if
> > the subdir count for any directory crosses 65000.
> > 
> 
> Would I be correct in assuming that a later fsck will clear
> EXT4_FEATURE_RO_COMPAT_DIR_NLINK if there are no longer any >65000 subdir
> directories?
> 
> If so, that is worth a mention in the changelog, perhaps?

The changelog has been updated to include this.

> >  
> > +static inline void ext4_inc_count(handle_t *handle, struct inode *inode)
> > +{
> > +	inc_nlink(inode);
> > +	if (is_dx(inode) && inode->i_nlink > 1) {
> > +		/* limit is 16-bit i_links_count */
> > +		if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
> > +			inode->i_nlink = 1;
> > +			EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
> > +					      EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
> > +		}
> > +	}
> > +}
> 
> Looks too big to be inlined.
> 
> Why do we set EXT4_FEATURE_RO_COMPAT_DIR_NLINK if i_nlink==2?

I have added a comment for this. (since it indicates that nlinks==1
previously).

> 
> > +static inline void ext4_dec_count(handle_t *handle, struct inode *inode)
> > +{
> > +	drop_nlink(inode);
> > +	if (S_ISDIR(inode->i_mode) && inode->i_nlink == 0)
> > +		inc_nlink(inode);
> > +}
> 
> Probably too big to inline.

Removed the inline.

> >  
> > -	if (inode->i_nlink >= EXT4_LINK_MAX)
> > +	if (EXT4_DIR_LINK_MAX(inode))
> >  		return -EMLINK;
> 
> argh.  WHY_IS_EXT4_FULL_OF_UPPER_CASE_MACROS_WHICH_COULD_BE_IMPLEMENTED
> as_lower_case_inlines?  Sigh.  It's all the old-timers, I guess.
> 
> EXT4_DIR_LINK_MAX() is buggy: it evaluates its arg twice.

#define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX)

This just checks if directory has hash indexing in which case we need not worry about EXT4_LINK_MAX subdir limit. If directory is not hash indexed then we will need to enforce a max subdir limit. 

Sorry, I didn't understand what is the problem with this macro?

Thanks,
Kalpak.

[-- Attachment #2: ext4_remove_subdirs_limit.patch --]
[-- Type: text/x-patch, Size: 6969 bytes --]

This patch adds support to ext4 for allowing more than 65000
subdirectories. Currently the maximum number of subdirectories is capped
at 32000.

If we exceed 65000 subdirectories in an htree directory it sets the
inode link count to 1 and no longer counts subdirectories.  The
directory link count is not actually used when determining if a
directory is empty, as that only counts subdirectories and not regular
files that might be in there. 

A EXT4_FEATURE_RO_COMPAT_DIR_NLINK flag has been added and it is set if
the subdir count for any directory crosses 65000. A later fsck will clear
EXT4_FEATURE_RO_COMPAT_DIR_NLINK if there are no longer any directory
with >65000 subdirs.

Signed-off-by: Andreas Dilger <adilger@clusterfs.com>
Signed-off-by: Kalpak Shah <kalpak@clusterfs.com>


---
 fs/ext4/namei.c         |   52 +++++++++++++++++++++++++++++++++++-------------
 include/linux/ext4_fs.h |    4 ++-
 2 files changed, 41 insertions(+), 15 deletions(-)

Index: linux-2.6.22/fs/ext4/namei.c
===================================================================
--- linux-2.6.22.orig/fs/ext4/namei.c
+++ linux-2.6.22/fs/ext4/namei.c
@@ -1617,6 +1617,35 @@ static int ext4_delete_entry (handle_t *
 	return -ENOENT;
 }
 
+/*
+ * DIR_NLINK feature is set if 1) nlinks > EXT4_LINK_MAX or 2) nlinks == 2,
+ * since this indicates that nlinks count was previously 1.
+ */
+static void ext4_inc_count(handle_t *handle, struct inode *inode)
+{
+	inc_nlink(inode);
+	if (is_dx(inode) && inode->i_nlink > 1) {
+		/* limit is 16-bit i_links_count */
+		if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
+			inode->i_nlink = 1;
+			EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
+					      EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
+		}
+	}
+}
+
+/*
+ * If a directory had nlink == 1, then we should let it be 1. This indicates
+ * directory has >EXT4_LINK_MAX subdirs.
+ */
+static void ext4_dec_count(handle_t *handle, struct inode *inode)
+{
+	drop_nlink(inode);
+	if (S_ISDIR(inode->i_mode) && inode->i_nlink == 0)
+		inc_nlink(inode);
+}
+
+
 static int ext4_add_nondir(handle_t *handle,
 		struct dentry *dentry, struct inode *inode)
 {
@@ -1713,7 +1742,7 @@ static int ext4_mkdir(struct inode * dir
 	struct ext4_dir_entry_2 * de;
 	int err, retries = 0;
 
-	if (dir->i_nlink >= EXT4_LINK_MAX)
+	if (EXT4_DIR_LINK_MAX(dir))
 		return -EMLINK;
 
 retry:
@@ -1736,7 +1765,7 @@ retry:
 	inode->i_size = EXT4_I(inode)->i_disksize = inode->i_sb->s_blocksize;
 	dir_block = ext4_bread (handle, inode, 0, 1, &err);
 	if (!dir_block) {
-		drop_nlink(inode); /* is this nlink == 0? */
+		ext4_dec_count(handle, inode); /* is this nlink == 0? */
 		ext4_mark_inode_dirty(handle, inode);
 		iput (inode);
 		goto out_stop;
@@ -1768,7 +1797,7 @@ retry:
 		iput (inode);
 		goto out_stop;
 	}
-	inc_nlink(dir);
+	ext4_inc_count(handle, dir);
 	ext4_update_dx_flag(dir);
 	ext4_mark_inode_dirty(handle, dir);
 	d_instantiate(dentry, inode);
@@ -2033,9 +2062,9 @@ static int ext4_rmdir (struct inode * di
 	retval = ext4_delete_entry(handle, dir, de, bh);
 	if (retval)
 		goto end_rmdir;
-	if (inode->i_nlink != 2)
+	if (!EXT4_DIR_LINK_EMPTY(inode))
 		ext4_warning (inode->i_sb, "ext4_rmdir",
-			      "empty directory has nlink!=2 (%d)",
+			      "empty directory has too many links (%d)",
 			      inode->i_nlink);
 	clear_nlink(inode);
 	/* There's no need to set i_disksize: the fact that i_nlink is
@@ -2045,7 +2074,7 @@ static int ext4_rmdir (struct inode * di
 	ext4_orphan_add(handle, inode);
 	inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
 	ext4_mark_inode_dirty(handle, inode);
-	drop_nlink(dir);
+	ext4_dec_count(handle, dir);
 	ext4_update_dx_flag(dir);
 	ext4_mark_inode_dirty(handle, dir);
 
@@ -2096,7 +2125,7 @@ static int ext4_unlink(struct inode * di
 	dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
 	ext4_update_dx_flag(dir);
 	ext4_mark_inode_dirty(handle, dir);
-	drop_nlink(inode);
+	ext4_dec_count(handle, inode);
 	if (!inode->i_nlink)
 		ext4_orphan_add(handle, inode);
 	inode->i_ctime = ext4_current_time(inode);
@@ -2146,7 +2175,7 @@ retry:
 		err = __page_symlink(inode, symname, l,
 				mapping_gfp_mask(inode->i_mapping) & ~__GFP_FS);
 		if (err) {
-			drop_nlink(inode);
+			ext4_dec_count(handle, inode);
 			ext4_mark_inode_dirty(handle, inode);
 			iput (inode);
 			goto out_stop;
@@ -2172,8 +2201,9 @@ static int ext4_link (struct dentry * ol
 	struct inode *inode = old_dentry->d_inode;
 	int err, retries = 0;
 
-	if (inode->i_nlink >= EXT4_LINK_MAX)
+	if (EXT4_DIR_LINK_MAX(inode))
 		return -EMLINK;
+
 	/*
 	 * Return -ENOENT if we've raced with unlink and i_nlink is 0.  Doing
 	 * otherwise has the potential to corrupt the orphan inode list.
@@ -2191,7 +2221,7 @@ retry:
 		handle->h_sync = 1;
 
 	inode->i_ctime = ext4_current_time(inode);
-	inc_nlink(inode);
+	ext4_inc_count(handle, inode);
 	atomic_inc(&inode->i_count);
 
 	err = ext4_add_nondir(handle, dentry, inode);
@@ -2323,7 +2353,7 @@ static int ext4_rename (struct inode * o
 	}
 
 	if (new_inode) {
-		drop_nlink(new_inode);
+		ext4_dec_count(handle, new_inode);
 		new_inode->i_ctime = ext4_current_time(new_inode);
 	}
 	old_dir->i_ctime = old_dir->i_mtime = ext4_current_time(old_dir);
@@ -2334,11 +2364,13 @@ static int ext4_rename (struct inode * o
 		PARENT_INO(dir_bh->b_data) = cpu_to_le32(new_dir->i_ino);
 		BUFFER_TRACE(dir_bh, "call ext4_journal_dirty_metadata");
 		ext4_journal_dirty_metadata(handle, dir_bh);
-		drop_nlink(old_dir);
+		ext4_dec_count(handle, old_dir);
 		if (new_inode) {
-			drop_nlink(new_inode);
+			/* checked empty_dir above, can't have another parent,
+			 * ext3_dec_count() won't work for many-linked dirs */
+			new_inode->i_nlink = 0;
 		} else {
-			inc_nlink(new_dir);
+			ext4_inc_count(handle, new_dir);
 			ext4_update_dx_flag(new_dir);
 			ext4_mark_inode_dirty(handle, new_dir);
 		}
Index: linux-2.6.22/include/linux/ext4_fs.h
===================================================================
--- linux-2.6.22.orig/include/linux/ext4_fs.h
+++ linux-2.6.22/include/linux/ext4_fs.h
@@ -71,7 +71,7 @@
 /*
  * Maximal count of links to a file
  */
-#define EXT4_LINK_MAX		32000
+#define EXT4_LINK_MAX		65000
 
 /*
  * Macro-instructions used to manage several block sizes
@@ -694,6 +694,7 @@ static inline int ext4_valid_inum(struct
 #define EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER	0x0001
 #define EXT4_FEATURE_RO_COMPAT_LARGE_FILE	0x0002
 #define EXT4_FEATURE_RO_COMPAT_BTREE_DIR	0x0004
+#define EXT4_FEATURE_RO_COMPAT_DIR_NLINK	0x0020
 #define EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE	0x0040
 
 #define EXT4_FEATURE_INCOMPAT_COMPRESSION	0x0001
@@ -712,6 +713,7 @@ static inline int ext4_valid_inum(struct
 					 EXT4_FEATURE_INCOMPAT_64BIT)
 #define EXT4_FEATURE_RO_COMPAT_SUPP	(EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER| \
 					 EXT4_FEATURE_RO_COMPAT_LARGE_FILE| \
+					 EXT4_FEATURE_RO_COMPAT_DIR_NLINK | \
 					 EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE | \
 					 EXT4_FEATURE_RO_COMPAT_BTREE_DIR)
 

Re: [EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Pekka Enberg]

On 7/13/07, Kalpak Shah <kalpak@clusterfs.com> wrote:
> > EXT4_DIR_LINK_MAX() is buggy: it evaluates its arg twice.
>
> #define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX)

[snip]

> Sorry, I didn't understand what is the problem with this macro?

The expression represented by 'dir' is evaluated twice (think dir++
here). It's safer to make it a static inline function.

                                       Pekka

Re: [EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Andrew Morton]

On Fri, 13 Jul 2007 16:00:48 +0530 Kalpak Shah <kalpak@clusterfs.com> wrote:

> > >  
> > > -	if (inode->i_nlink >= EXT4_LINK_MAX)
> > > +	if (EXT4_DIR_LINK_MAX(inode))
> > >  		return -EMLINK;
> > 
> > argh.  WHY_IS_EXT4_FULL_OF_UPPER_CASE_MACROS_WHICH_COULD_BE_IMPLEMENTED
> > as_lower_case_inlines?  Sigh.  It's all the old-timers, I guess.
> > 
> > EXT4_DIR_LINK_MAX() is buggy: it evaluates its arg twice.
> 
> #define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX)
> 
> This just checks if directory has hash indexing in which case we need not worry about EXT4_LINK_MAX subdir limit. If directory is not hash indexed then we will need to enforce a max subdir limit. 
> 
> Sorry, I didn't understand what is the problem with this macro?

Macros should never evaluate their argument more than once, because if they
do they will misbehave when someone passes them an
expression-with-side-effects:

	struct inode *p = q;

	EXT4_DIR_LINK_MAX(p++);

one expects `p' to have the value q+1 here.  But it might be q+2.

and

	EXT4_DIR_LINK_MAX(some_function());

might cause some_function() to be called twice.


This is one of the many problems which gets fixed when we write code in C
rather than in cpp.

Re: [EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Kalpak Shah]

On Fri, 2007-07-13 at 09:53 -0700, Andrew Morton wrote:
> On Fri, 13 Jul 2007 16:00:48 +0530 Kalpak Shah <kalpak@clusterfs.com> wrote:
> 
> > > >  
> > > > -	if (inode->i_nlink >= EXT4_LINK_MAX)
> > > > +	if (EXT4_DIR_LINK_MAX(inode))
> > > >  		return -EMLINK;
> > > 
> > > argh.  WHY_IS_EXT4_FULL_OF_UPPER_CASE_MACROS_WHICH_COULD_BE_IMPLEMENTED
> > > as_lower_case_inlines?  Sigh.  It's all the old-timers, I guess.
> > > 
> > > EXT4_DIR_LINK_MAX() is buggy: it evaluates its arg twice.
> > 
> > #define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX)
> > 
> > This just checks if directory has hash indexing in which case we need not worry about EXT4_LINK_MAX subdir limit. If directory is not hash indexed then we will need to enforce a max subdir limit. 
> > 
> > Sorry, I didn't understand what is the problem with this macro?
> 
> Macros should never evaluate their argument more than once, because if they
> do they will misbehave when someone passes them an
> expression-with-side-effects:
> 
> 	struct inode *p = q;
> 
> 	EXT4_DIR_LINK_MAX(p++);
> 
> one expects `p' to have the value q+1 here.  But it might be q+2.
> 
> and
> 
> 	EXT4_DIR_LINK_MAX(some_function());
> 
> might cause some_function() to be called twice.
> 
> 
> This is one of the many problems which gets fixed when we write code in C
> rather than in cpp.

Thanks. Here is the fix converting these macros into inlined functions.


----
The EXT4_DIR_LINK_MAX(dir) and EXT4_DIR_LINK_EMPTY(dir) macros were
evaluating their argument twice so convert them into inlined functions.

Signed-off-by: Kalpak Shah <kalpak@clusterfs.com>

Index: linux-2.6.22/fs/ext4/namei.c
===================================================================
--- linux-2.6.22.orig/fs/ext4/namei.c
+++ linux-2.6.22/fs/ext4/namei.c
@@ -1742,7 +1742,7 @@ static int ext4_mkdir(struct inode * dir
        struct ext4_dir_entry_2 * de;
        int err, retries = 0;

-       if (EXT4_DIR_LINK_MAX(dir))
+       if (ext4_dir_link_max(dir))
                return -EMLINK;

 retry:
@@ -2062,7 +2062,7 @@ static int ext4_rmdir (struct inode * di
        retval = ext4_delete_entry(handle, dir, de, bh);
        if (retval)
                goto end_rmdir;
-       if (!EXT4_DIR_LINK_EMPTY(inode))
+       if (!ext4_dir_link_empty(inode))
                ext4_warning (inode->i_sb, "ext4_rmdir",
                              "empty directory has too many links (%d)",
                              inode->i_nlink);
@@ -2201,7 +2201,7 @@ static int ext4_link (struct dentry * ol
        struct inode *inode = old_dentry->d_inode;
        int err, retries = 0;

-       if (EXT4_DIR_LINK_MAX(inode))
+       if (ext4_dir_link_max(inode))
                return -EMLINK;

        /*
Index: linux-2.6.22/include/linux/ext4_fs.h
===================================================================
--- linux-2.6.22.orig/include/linux/ext4_fs.h
+++ linux-2.6.22/include/linux/ext4_fs.h
@@ -797,12 +797,18 @@ struct ext4_dir_entry_2 {
   #define is_dx(dir) (EXT4_HAS_COMPAT_FEATURE(dir->i_sb, \
                                              EXT4_FEATURE_COMPAT_DIR_INDEX) && \
                      (EXT4_I(dir)->i_flags & EXT4_INDEX_FL))
-#define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX)
-#define EXT4_DIR_LINK_EMPTY(dir) ((dir)->i_nlink == 2 || (dir)->i_nlink == 1)
+static inline int ext4_dir_link_max(struct inode *dir)
+{
+       return (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX);
+}
+static inline int ext4_dir_link_empty(struct inode *dir)
+{
+       return ((dir)->i_nlink == 2 || (dir)->i_nlink == 1);
+}
 #else
   #define is_dx(dir) 0
-#define EXT4_DIR_LINK_MAX(dir) ((dir)->i_nlink >= EXT4_LINK_MAX)
-#define EXT4_DIR_LINK_EMPTY(dir) ((dir)->i_nlink == 2)
+#define ext4_dir_link_max(dir) ((dir)->i_nlink >= EXT4_LINK_MAX)
+#define ext4_dir_link_empty(dir) ((dir)->i_nlink == 2)
 #endif

 /* Legal values for the dx_root hash_version field: */

Re: [EXT4 set 7][PATCH 1/1]Remove 32000 subdirs limit.

[Ingo Oeser]

On Tuesday 17 July 2007, Kalpak Shah wrote:
> Index: linux-2.6.22/include/linux/ext4_fs.h
> ===================================================================
> --- linux-2.6.22.orig/include/linux/ext4_fs.h
> +++ linux-2.6.22/include/linux/ext4_fs.h
> @@ -797,12 +797,18 @@ struct ext4_dir_entry_2 {
>    #define is_dx(dir) (EXT4_HAS_COMPAT_FEATURE(dir->i_sb, \
>                                               EXT4_FEATURE_COMPAT_DIR_INDEX) && \
>                       (EXT4_I(dir)->i_flags & EXT4_INDEX_FL))
> -#define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX)
> -#define EXT4_DIR_LINK_EMPTY(dir) ((dir)->i_nlink == 2 || (dir)->i_nlink == 1)
> +static inline int ext4_dir_link_max(struct inode *dir)
> +{
> +       return (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX);
> +}
> +static inline int ext4_dir_link_empty(struct inode *dir)
> +{
> +       return ((dir)->i_nlink == 2 || (dir)->i_nlink == 1);
> +}

even better:

static inline bool ext4_is_dx(const struct inode *dir)
{
#ifdef FOOBAR
	return EXT4_HAS_COMPAT_FEATURE(dir->i_sb,   EXT4_FEATURE_COMPAT_DIR_INDEX) 
                   && (EXT4_I(dir)->i_flags & EXT4_INDEX_FL));
#else
	return false;
#endif
}

static inline bool ext4_dir_link_max(const struct inode *dir)
{
	return !ext4_is_dx(dir) && (dir->i_nlink >= EXT4_LINK_MAX);
}

static inline bool ext4_dir_link_empty(const struct inode *dir)
{
#ifdef FOOBAR
	return dir->i_nlink == 2 || dir->i_nlink == 1;
#else
	return dir->i_nlink == 2;
#endif
}


FOOBAR is the define, which enables ext4_is_dx(). 
That is not in the patch, so left as an exercise to the reader :-)

Best Regards

Ingo Oeser