Problems with the max value for create directory
Hi,
I creat 65537 long directories and failed when the block size is 1024.
# mkfs.ext4dev -b 1024 -I 256 /dev/hda3 # tune2fs -E test_fs -O extents /dev/hda3 # mount -t ext4dev /dev/hda3 /mnt # ./create_long_dirs 65537 /mnt
The code of create_long_dirs.c:
#define _ATFILE_SOURCE
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <sys/types.h>
//#define __USE_ATFILE
#include <sys/stat.h>
#define NAME_LEN 255
#define NCHARS 62
#define MAX_LEN1 62
#define MAX_LEN2 (62 * 62)
#define MAX_LEN3 (62 * 62 * 62)
/* valid characters for the directory name */
char chars[NCHARS + 1] =
"0123456789qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM";
/* to store the generated directory name */
char name[NAME_LEN + 1];
int names;
int parent_fd;
void init_name(void)
{
int i;
srand(time(NULL));
for (i = 0; i < NAME_LEN; i++)
name[i] = chars[rand() % 62];
}void create_dir(void)
{
if (mkdirat(parent_fd, name, S_IRWXU)) {
perror("mkdir");
exit(1);
}
}/*
* create_dirs - create @names directory names
* @n: how many names to be created
*
* if n <= 62, we need to modify 1 char of the name
* if n <= 62*62, we need to modify 2 chars
* if n <= 62*62*62, we need to modify 3 chars
*/
void create_dirs(int n)
{
int i, j, k;
int depth;
if (n <= MAX_LEN1)
depth = 1;
else if (n <= MAX_LEN2)
depth = 2;
else
depth = 3;
for (i = 0; i < NCHARS; i++) {
name[0] = chars[i];
if (depth == 1) {
create_dir();
if (--n == 0)
return;
continue;
}
for (j = 0; j < NCHARS; j++) {
name[1] = chars[j];
if (depth == 2) {
create_dir();
if (--n == 0)
return;
continue;
}
for (k = 0; k < NCHARS; k++) {
name[2] = chars[k];
create_dir();
if (--n == 0)
return;
}
}
}
}void usage()
{
fprintf(stderr, "Usage: create_long_dirs nr_dirs parent_dir\n");
}int main(int argc, char *argv[])
{
if (argc != 3) {
usage();
return 1;
}
names = atoi(argv[1]);
if (names > MAX_LEN3 || names <= 0) {
usage();
return 1;
}
parent_fd = open(argv[2], O_RDONLY);
if (parent_fd == -1) {
perror("open parent dir failed");
return 1;
}
init_name();
create_dirs(names);
return 0;
}Signature · 2 lines
Regards Zhang Xiliang
Hi,
Quoted 10 lines · Zhang Xiliang
Hi,
I creat 65537 long directories and failed when the block size is 1024.
# mkfs.ext4dev -b 1024 -I 256 /dev/hda3 # tune2fs -E test_fs -O extents /dev/hda3 # mount -t ext4dev /dev/hda3 /mnt # ./create_long_dirs 65537 /mntThe code of
create_long_dirs.c:
ext4 filesystem cannot make over 65000 links toward a file. (ext3 filesystem cannot make over 32000 links toward a file.) This test makes over 65000 links toward /mnt-directory. (Creating 65000 sub-directories makes 65000 links toward /mnt-directory.)
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.
Regards,
Toshiyuki Okajima
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 10 lines · Toshiyuki Okajima
Quoted 9 lines · Zhang Xiliang
Hi,
I creat 65537 long directories and failed when the block size is 1024.
# mkfs.ext4dev -b 1024 -I 256 /dev/hda3 # tune2fs -E test_fs -O extents /dev/hda3 # mount -t ext4dev /dev/hda3 /mnt # ./create_long_dirs 65537 /mnt
Quoted 6 lines
Quoted 1 line
The code of
create_long_dirs.c:ext4 filesystem cannot make over 65000 links toward a file. (ext3 filesystem cannot make over 32000 links toward a file.) This test makes over 65000 links toward /mnt-directory. (Creating 65000 sub-directories makes 65000 links toward /mnt-directory.)
Note that there is a specific reason why it was implemented this way:
- a directory with > 65000 subdirectories can be checked if empty even if the link count is wrong (in fact link count was ignored even in ext3)
- a file needs to keep accurate link counts or it is impossible to know when the file needs to be deleted.
We thought about adding a "i_links_count_hi" but it wasn't thought that many (any) real applications would create so many hard links on the same file.
Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.
Quoted 15 lines · Toshiyuki Okajima
Quoted 2 lines
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;
Quoted 1 line
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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 20 lines · Theodore Tso
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.
Quoted 3 lines
Were you writing this test program because this is a realistic situation for your application, or just to explore the limits of ext4?
Thanks for explanation.
I see the limit of ext4 subdirectory. The test program originally tests it. But I fail and find the limit of the htree.
I think it may be annoying. Somebody may be puzzled for the two limits. The limit of the htree should be greater than the limit of ext4 subdirectory.
Signature · 7 lines
Regards Zhang Xiliang -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 5 lines · Zhang Xiliang
Thanks for explanation.
I see the limit of ext4 subdirectory. The test program originally tests it. But I fail and find the limit of the htree.
But if that was your goal, why did you use the largest possible filename length for the subdirectories? And why did you use a 1k block filesystem? Both of these are totally unnecessary if the goal is to test the limit of the number of ext4 subdirectories, and are *ideal* if you are trying to detect the htree limit.
Quoted 2 lines
I think it may be annoying. Somebody may be puzzled for the two limits. The limit of the htree should be greater than the limit of ext4 subdirectory.
Well, are you annoyed enough to help to try to solve the problem? In actual practice very few people have run across the htree limit as far as I know.
- Ted
Hi, guys
I got a question about this.
Since htree is a potential limitation for subdirectories. Is there a reason why EXT4_LINK_MAX is applied when fs hasn't dir_index but ignored when fs has dir_index(by the following code)?
#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)
Quoted 44 lines · Zhang Xiliang
Quoted 20 lines · Theodore Tso
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.
Quoted 3 lines
Were you writing this test program because this is a realistic situation for your application, or just to explore the limits of ext4?
Thanks for explanation.
I see the limit of ext4 subdirectory. The test program originally tests it. But I fail and find the limit of the htree.
I think it may be annoying. Somebody may be puzzled for the two limits. The limit of the htree should be greater than the limit of ext4 subdirectory.
--
Regards
Zhang Xiliang--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Signature · 7 lines
Cheers, Bergwolf ................ Rodney Dangerfield - "The way my luck is running, if I was a politician I would be honest."
Quoted 9 lines · Peng tao
I got a question about this.
Since htree is a potential limitation for subdirectories. Is there a reason whyEXT4_LINK_MAXis applied when fs hasn'tdir_indexbut ignored when fs hasdir_index(by the following code)?#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)
Because without the dir_index feature the largest usable directory size is only about 10k-20k files before the O(n^2) insertion performance is so bad that the directory is useless.
Quoted 41 lines
Quoted 39 lines · Zhang Xiliang
Quoted 20 lines · Theodore Tso
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.
Quoted 3 lines
Were you writing this test program because this is a realistic situation for your application, or just to explore the limits of ext4?
Thanks for explanation.
I see the limit of ext4 subdirectory. The test program originally tests it. But I fail and find the limit of the htree.
I think it may be annoying. Somebody may be puzzled for the two limits. The limit of the htree should be greater than the limit of ext4 subdirectory.
--
Regards
Zhang Xiliang
Quoted 17 lines
Quoted 5 lines
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.htmlSignature · 8 lines
Cheers, Bergwolf ................ Rodney Dangerfield - "The way my luck is running, if I was a politician I would be honest." N?????r??y????b?X??ǧv?^?){.n?+????{?{x?{ay?ʇڙ?,j??f???h???z??w??????j:+v???w?j?m????????zZ+?????ݢj"??!
Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html