linux-ext4 - Re: Problems with the max value for create directory

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20081223201247.GU23723@mit.edu>
Date:	Tue, 23 Dec 2008 15:12:47 -0500
From:	Theodore Tso <tytso@....EDU>
To:	Toshiyuki Okajima <toshi.okajima@...fujitsu.com>
Cc:	Zhang Xiliang <zhangxiliang@...fujitsu.com>,
	linux-ext4@...r.kernel.org
Subject: Re: Problems with the max value for create directory

On Tue, Dec 23, 2008 at 01:02:25PM +0900, Toshiyuki Okajima wrote:
>> I creat 65537 long directories and failed when the block size is 1024.
>>
>
> static int ext4_mkdir(struct inode *dir, struct dentry *dentry, int mode)
> {
>          handle_t *handle;
>          struct inode *inode;
>          struct buffer_head *dir_block;
>          struct ext4_dir_entry_2 *de;
>          int err, retries = 0;
>
>          if (EXT4_DIR_LINK_MAX(dir))
> 　　　　　^^^^^^^^^^^^^^^^^^^^^^^^^^^　　　　
>                  return -EMLINK;
>
> This limit is ext4's specification.

The definition of EXT4_DIR_LINK_MAX is here:

#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)

So that's not it.  The problem is that indexed diretories have a limit
that only allows the trees to be two levels deep.  The fanout is
normally big enough that this is effectively not a problem, but if you
use very long filenames, and a 1k blocksize, you will run into this
limit much more quickly.  So the problem is not the number of sub
directories, but the maximum depth of the htree allowed in Daniel
Phillips' relatively restricted implementation.  Note that with a 4k
block filesystem, the limits get expanded by a factor of 4 cubed, or
64.  And most of the time users aren't maximal length named directory
entries, which further pushes the limit out in the normal case.

It in theory would be possible to relax this restriction, using a more
advanced htree implementation and a feature flag to allow backwards
compatibility with older kernels that only support the maximal depth.
Andreas has a prototype kernel implementation which in theory could be
added to ext4.  It hasn't been high on my priority list to complete,
but if someone else really finds this limit to be annoying, it is a
project they might try to complete.

Were you writing this test program because this is a realistic
situation for your application, or just to explore the limits of ext4?

Regards,

						- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html