Skip to contentSkip to conversation

Maximum files per Directory

DISCUSSION Andreas Rogge 10 participants 14 messages May 1, 2001 – May 5, 2001

lore
Share & tools
lore
#0 lore raw

While trying to create 100.000 (in words: one hundred thousand) Mailboxes with cyrus-imapd i ran into problems.
At about 2^15 files the filesystem gave up, telling me that there cannot be more files in a directory.

Is this a vfs-Issue or an ext2-issue?

Andreas Rogge <[email protected]>
Available on IRCnet:#linux.de as Dyson

#1 lore raw
Followup to:  <272800000.988750082@hades>
By author:    Andreas Rogge <[email protected]>
In newsgroup: linux.dev.kernel
Quoted 9 lines

While trying to create 100.000 (in words: one hundred thousand) Mailboxes with
cyrus-imapd i ran into problems.
At about 2^15 files the filesystem gave up, telling me that there cannot be more files in a directory.

Is this a vfs-Issue or an ext2-issue?

Not correct, there can't be more than 2^15 *directories* in a single directory. I belive this is an ext2 limitation.

-hpa

Signature · 3 lines
<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt
#8 lore raw
In reply to Andreas Rogge
Quoted 5 lines

cyrus-imapd i ran into problems.
At about 2^15 files the filesystem gave up, telling me that there cannot be more files in a directory.

Is this a vfs-Issue or an ext2-issue?

Bit of both. You exceeded the max link count, and your performance would have been abominable too. cyrus should be using heirarchies of directories for very large amounts of stuff.

#10 lore raw
In reply to Andreas Rogge
Followup to:  <[email protected]>
By author:    Alan Cox <[email protected]>
In newsgroup: linux.dev.kernel
Quoted 11 lines
Quoted 6 lines

cyrus-imapd i ran into problems.
At about 2^15 files the filesystem gave up, telling me that there cannot be more files in a directory.

Is this a vfs-Issue or an ext2-issue?

Bit of both. You exceeded the max link count, and your performance would have been abominable too. cyrus should be using heirarchies of directories for very large amounts of stuff.

But also showing, once again, that this particular scalability problem really is a headache for some people.

-hpa

Signature · 3 lines
<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt
#2 lore raw
In reply to H. Peter Anvin
Quoted 2 lines · H. Peter Anvin

Not correct, there can't be more than 2^15 *directories* in a single directory. I belive this is an ext2 limitation.

This is imposed by a number of issues:
- EXT2_LINK_MAX=32000 is checked for new subdirectories
- ext2 bg_used_dirs_count is a __u16
- inode->i_nlink (__kernel_nlink_t) is an unsigned short for some platforms

For stat (old interface) the st_nlinks count is also an unsigned short, so we _should_ be able to increase EXT2_LINK_MAX to 65500 or so safely. The VFS will have problems if you increase the max link count over 65535 because __kernel_nlink_t is __u16.

I see that reiserfs plays some tricks with the directory i_nlink count. If you exceed 64536 links in a directory, it reverts to "1" and no longer tracks the link count.

You will have problems with performance for directories this large on stock ext2, unless you use Daniel Phillips' indexed directory patch. I have tested 100k+ _files_ in a single directory without problems (Daniel has tested 1M _files_ without problems). I would NOT reccommend doing this on your production mail server at this time, but it may be worth testing at least... It does not (yet) address the issue of lots of subdirectories, but that is something that can be worked on at least.

http://kernelnewbies.org/~phillips/htree/

Cheers, Andreas

Signature · 3 lines
Andreas Dilger                               Turbolinux filesystem development
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/
#11 lore raw
In reply to Andreas Rogge
Quoted 5 lines · Andreas Rogge

While trying to create 100.000 (in words: one hundred thousand) Mailboxes with
cyrus-imapd i ran into problems.
At about 2^15 files the filesystem gave up, telling me that there cannot be more files in a directory.

Ugh. Went into this on a NetApp Filer some years ago, too.

Easy solution: Use multiple partitions with cyrus.

I also have a hashing patch for cyrus somewhere.

Does ReiserFS help here?

Regards
Henning

Signature · 5 lines
Dipl.-Inf. (Univ.) Henning P. Schmiedehausen       -- Geschaeftsfuehrer
INTERMETA - Gesellschaft fuer Mehrwertdienste mbH     [email protected]

Am Schwabachgrund 22  Fon.: 09131 / 50654-0   [email protected]
D-91054 Buckenhof     Fax.: 09131 / 50654-20   
#12 lore raw
In reply to Andreas Rogge
Quoted 4 lines · H. Peter Anvin
Quoted 4 lines

Bit of both. You exceeded the max link count, and your performance would have been abominable too. cyrus should be using heirarchies of directories for very large amounts of stuff.

Right.

Quoted 2 lines

But also showing, once again, that this particular scalability problem really is a headache for some people.

If you do ls on that directory as an admin, you'll see, what the REAL cause of this headache is:

The application doing such stupid thing!

People (writing applications) building up such large directories should be forced to read every entry of it aloud.

Then they'll learn[1] and the problem is solved.

Regards

Ingo Oeser

[1] If not, let them repeat until they do.

Signature · 2 lines
10.+11.03.2001 - 3. Chemnitzer LinuxTag <http://www.tu-chemnitz.de/linux/tag>
         <<<<<<<<<<<<     been there and had much fun   >>>>>>>>>>>>
#9 lore raw
In reply to Alan Cox
Quoted 9 lines · Alan Cox
Quoted 5 lines

cyrus-imapd i ran into problems.
At about 2^15 files the filesystem gave up, telling me that there cannot be more files in a directory.

Is this a vfs-Issue or an ext2-issue?

Bit of both. You exceeded the max link count, and your performance would have been abominable too. cyrus should be using heirarchies of directories for very large amounts of stuff.

That's not always best, is it? I've been testing a bit with reiserfs, and with LOTS of files, I lose performance with a lot of directories compared to putting all the files in one directory.

Of course, that is only read-performance. Write performance is enhanced (at least when creating new files) by splitting this into some more directories. So how you want to split this up depends whether your data is write-many-read-once or write-once-read-many or something in between. That is my experience with reiserfs, anyway.

Ketil

#13 lore raw
In reply to Andreas Rogge
Quoted 14 lines · Ingo Oeser
Quoted 4 lines · H. Peter Anvin
Quoted 4 lines

Bit of both. You exceeded the max link count, and your performance would have been abominable too. cyrus should be using heirarchies of directories for very large amounts of stuff.

Right.

Quoted 2 lines

But also showing, once again, that this particular scalability problem really is a headache for some people.

If you do ls on that directory as an admin, you'll see, what the REAL cause of this headache is:

Quoted 7 lines

The application doing such stupid thing!

People (writing applications) building up such large directories should be forced to read every entry of it aloud.

Then they'll learn[1] and the problem is solved.

"Violence is the last refuge of the incompetent."

Seriously, I don't buy this "the application is doing something stupid." The application is using the VFS the way it is advertised to work. If you think doing ls on an extrememly large directory is painful, you have never seen the droppings of an application which tries to do load-balancing between directories by doing real hashing. THAT is painful! At least in the first case you can use grep.

The only ones we fool by repeating the mantra "stupid admin, stupid application" is ourselves.

-hpa

Signature · 3 lines
<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt
#3 lore raw
In reply to Andreas Dilger
Quoted 8 lines · On Tuesday, May 01, 2001 04:57:02 PM -0600 Andreas Dilger…
Quoted 2 lines · H. Peter Anvin

Not correct, there can't be more than 2^15 *directories* in a single directory. I belive this is an ext2 limitation.

I see that reiserfs plays some tricks with the directory i_nlink count. If you exceed 64536 links in a directory, it reverts to "1" and no longer tracks the link count.

Correct. The link count isn't used at all when deciding if the directory is empty (we use the size instead), so we can just lie to VFS if someone tries to make tons of subdirs.

-chris

#4 lore raw
Quoted 9 lines · Chris
Quoted 3 lines · On Tuesday, May 01, 2001 04:57:02 PM -0600 Andreas Dilger…

I see that reiserfs plays some tricks with the directory i_nlink count. If you exceed 64536 links in a directory, it reverts to "1" and no longer tracks the link count.

Correct. The link count isn't used at all when deciding if the directory is empty (we use the size instead), so we can just lie to VFS if someone tries to make tons of subdirs.

For that matter, ext2 doesn't use the link count on directories to determine if they are empty either, so it shouldn't be too hard to do the same with the ext2 indexed-directory code. Is there a reason that reiserfs chose to have "large number of directories" represented by "1" and not "LINK_MAX+1"?

Cheers, Andreas

Signature · 3 lines
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert
#5 lore raw
Quoted 11 lines · On Friday, May 04, 2001 01:15:22 PM -0600 Andreas Dilger…
Quoted 9 lines · Chris
Quoted 3 lines · On Tuesday, May 01, 2001 04:57:02 PM -0600 Andreas Dilger…

I see that reiserfs plays some tricks with the directory i_nlink count. If you exceed 64536 links in a directory, it reverts to "1" and no longer tracks the link count.

Correct. The link count isn't used at all when deciding if the directory is empty (we use the size instead), so we can just lie to VFS if someone tries to make tons of subdirs.

Quoted 6 lines

For that matter, ext2 doesn't use the link count on directories to determine if they are empty either, so it shouldn't be too hard to do the same with the ext2 indexed-directory code. Is there a reason that reiserfs chose to have "large number of directories" represented by "1" and not "LINK_MAX+1"?

find and a few others consider a link count of 1 to mean there is no link count tracking being done.

-chris

#6 lore raw
In reply to Andreas Dilger
Quoted 6 lines · Chris Mason
Quoted 3 lines

Is there a reason that
reiserfs chose to have "large number of directories" represented by "1" and not "LINK_MAX+1"?

find and a few others consider a link count of 1 to mean there is no link count tracking being done.

Indeed, and thank you for getting this right!

Btw, is it possible to add dirent->d_type information to reiserfs, and would there be any performance gain in doing so?

I have code to add d_type for every other filesystem that can support it without additional disk reads, but I couldn't figure out whether reiserfs can do it or whether stat() following readdir() is cheap anyway.

-- Jamie (who has written a find-like program)

#7 lore raw
Quoted 5 lines · On Saturday, May 05, 2001 03:49:20 PM +0200 Jamie Lokier…
Quoted 4 lines · Chris Mason
Quoted 3 lines

Is there a reason that
reiserfs chose to have "large number of directories" represented by "1" and not "LINK_MAX+1"?

Quoted 7 lines
Quoted 2 lines

find and a few others consider a link count of 1 to mean there is no link count tracking being done.

Indeed, and thank you for getting this right!

Btw, is it possible to add dirent->d_type information to reiserfs, and would there be any performance gain in doing so?

reiserfs doesn't store that information in its directory items right now, but there are plenty of free bits to do so. It wouldn't be hard to add the feature, and yes there should be a performance gain.

Quoted 4 lines

I have code to add d_type for every other filesystem that can support it without additional disk reads, but I couldn't figure out whether reiserfs can do it or whether stat() following readdir() is cheap anyway.

stat is actually a little more expensive than ext2, since we have to search for the inode data in the tree. It is a fast search, but...

-chris