Skip to contentSkip to conversation

ext3_dx_add_entry: Directory index full!

DISCUSSION Bernie Innocenti 6 participants 10 messages May 18, 2008 – May 19, 2008

lore
Share & tools
lore
#0 lore raw

On 2.6.24.4-64.fc8, I createed and mounted a filesystem like this:

mke2fs -m0 -b 1024 -R stride=64 -I 128 -i 2048 -j -L mail -O dir_index,sparse_super -v /dev/sdc1 mount -t ext3 -o noatime,data=writeback,nosuid,usrquota /dev/sdc1 /mail

Then I copied a directory with 200K small files into it:

cp -a home/simone/Maildir/YouHaveJunkSir /mail/
[...]
cp: cannot create regular file `/mnt/YouHaveJunkSir/1174170042.20731_2.trinity.develer.com:2,b': No space left on device
cp: cannot create regular file `/mnt/YouHaveJunkSir/1186341042.8337_2.trinity.develer.com:2,': No space left on device
cp: cannot create regular file `/mnt/YouHaveJunkSir/1209101786.3888_2.trinity.develer.com:2,': No space left on device

The kernel logs are also scary:

EXT3-fs warning (device sdc1): ext3_dx_add_entry: Directory index full! EXT3-fs warning (device sdc1): ext3_dx_add_entry: Directory index full! [...]

The failing check looks like this:

       if (levels && (dx_get_count(frames->entries) ==
                  dx_get_limit(frames->entries))) {
           ext3_warning(sb, __FUNCTION__,
                    "Directory index full!");
           err = -ENOSPC;
           goto cleanup;
       }

The limit is set in make_indexed_dir():

dx_set_limit (entries, dx_root_limit(dir, sizeof(root->info)));

with this helper function:

static inline unsigned dx_root_limit (struct inode *dir, unsigned infosize)

 {
     unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(1) -
         EXT3_DIR_REC_LEN(2) - infosize;
     return 0? 20: entry_space / sizeof(struct dx_entry);

}

Am I reading the above code correctly? Why does it always return 20 no matter what?

Some background: I'm moving users' Maildirs to a separate filesystem tuned for small files to increase performance. One of our users intentionally collected spam for 5 years in one folder and likes it this way. We could easily work it around, but first I'd like to understand whether the particular parameters we used trigger a bug in ext3 or if we're just hitting a (possibly undocumented) limit.

Signature · 3 lines
  \___/
 _| X |  Bernie Innocenti - http://www.codewiz.org/
 \|_O_|  "It's an education project, not a laptop project!"
#1 lore raw
Quoted 9 lines · Bernie Innocenti

static inline unsigned dx_root_limit (struct inode *dir, unsigned
infosize)

  {
      unsigned entry_space = dir->i_sb->s_blocksize -
EXT3_DIR_REC_LEN(1) -
          EXT3_DIR_REC_LEN(2) - infosize;
      return 0? 20: entry_space / sizeof(struct dx_entry);
Quoted 4 lines

}

Am I reading the above code correctly? Why does it always return 20 no matter what?

It doesn't. "condition?A:B" will return A if the condition is _true_, which it isn't.

Signature · 1 line
dwmw2
#2 lore raw
Quoted 11 lines · David Woodhouse
Quoted 10 lines · Bernie Innocenti

static inline unsigned dx_root_limit (struct inode *dir, unsigned
infosize)

  {
      unsigned entry_space = dir->i_sb->s_blocksize -
EXT3_DIR_REC_LEN(1) -
          EXT3_DIR_REC_LEN(2) - infosize;
      return 0? 20: entry_space / sizeof(struct dx_entry);

}

Quoted 5 lines
Quoted 2 lines

Am I reading the above code correctly? Why does it always return 20 no matter what?

It doesn't. "condition?A:B" will return A if the condition is _true_, which it isn't.

Oh... I feel stupid.

Signature · 3 lines
  \___/
 _| X |  Bernie Innocenti - http://www.codewiz.org/
 \|_O_|  "It's an education project, not a laptop project!"
#3 lore raw
In reply to Bernie Innocenti
Quoted 3 lines · Bernie Innocenti

On 2.6.24.4-64.fc8, I createed and mounted a filesystem like this:

mke2fs -m0 -b 1024 -R stride=64 -I 128 -i 2048 -j -L mail -O dir_index,sparse_super -v /dev/sdc1

I cannot reproduce it any more if I reformat omitting "-b 1024". Maybe it would reappear with 200K * 4 = 800K files?

Signature · 3 lines
  \___/
 _| X |  Bernie Innocenti - http://www.codewiz.org/
 \|_O_|  "It's an education project, not a laptop project!"
#4 lore raw
Quoted 8 lines · Bernie Innocenti
Quoted 4 lines · Bernie Innocenti

On 2.6.24.4-64.fc8, I createed and mounted a filesystem like this:

mke2fs -m0 -b 1024 -R stride=64 -I 128 -i 2048 -j -L mail -O dir_index,sparse_super -v /dev/sdc1

I cannot reproduce it any more if I reformat omitting "-b 1024". Maybe it would reappear with 200K * 4 = 800K files?

In that case you might want to switch the filesystems.

#5 lore raw
In reply to Bernie Innocenti
Quoted 7 lines · Bernie Innocenti
Quoted 3 lines · Bernie Innocenti

On 2.6.24.4-64.fc8, I createed and mounted a filesystem like this:
mke2fs -m0 -b 1024 -R stride=64 -I 128 -i 2048 -j -L mail -O
dir_index,sparse_super -v /dev/sdc1

I cannot reproduce it any more if I reformat omitting "-b 1024". Maybe it would reappear with 200K * 4 = 800K files?

Using a filesystem with 4k blocks, and assuming the filenames are of the same average length, you should be able to get approximately 200k
* (4**3) = 12.8 million files in a single directory. If you use a 2k block filesystem, the limit will be approximately 200k * (2**3) = 1.6 million files in a single directory.

Regards,

- Ted

P.S. Past a certain point, you really don't want to have that many files in a Maildir directory; if the user is never going to be deleting his SPAM, then you should seriously think about using a Unix mbox style storage scheme. Even with a 1k block filesystem, at 12 million files you'll be wasting 6 gigabytes of disk space of slack space that is totally being wasted since the whole point of using Maildir is to make it easy to delete or replace individual mail messages. If you want to archive all of your SPAM, why use a Maildir format mbox at all?

#6 lore raw
Quoted 8 lines · Theodore Tso

P.S. Past a certain point, you really don't want to have that many files in a Maildir directory; if the user is never going to be deleting his SPAM, then you should seriously think about using a Unix mbox style storage scheme. Even with a 1k block filesystem, at 12 million files you'll be wasting 6 gigabytes of disk space of slack space that is totally being wasted since the whole point of using Maildir is to make it easy to delete or replace individual mail messages.

Yes. I'm proposing my users a cron job that will prune everything but the most recent 2000 messages in their spamtraps.

This particular user likes to do "spam forensics" with sophisticated Perl scripts and shell one liners, and publish pretty cool results like this one:

simone@haring:~/Maildir$ grep -rhIos "Be [^.]*\." .Junk .junk/ | sort | uniq
Be a bunch of bastards.
Be a fool for five minutes.
Be a good person than a famous person.
Be an attraction by showing off our white gold with diamond brim.
Be attention grabbing with this watch.
Be attractive with genuine replica timepiece.
Be a very positive thing.
Be a vogue magician.
Be aware of an inherent conflict of interest resulting from such compensation.
Be aware of an inherent conflict of interest resulting from such compensation due to the fact that this is a paid advertisement and is not without bias.
Be aware of an inherent conflict of interest resulting from such holdings due to our intent to profit from the liquidation of these shares.
Be bold.
Be chic with our reasonably priced watch.
Be civil to all; sociable to many; familiar with few.
Be confidence with set of diamonds on pure gold masterpiece.
Be fashionable with our low priced watch.
Be free to choose, and not to be chosen for, is an inalienable.
Be gentle with yourself, learn to lvoe yourself, to forgive.
Be having it.
Be lying.
Be made dependent on myth nor tied to any authority lest doubt about.
Be silent, and be thought a fool, than to speak and remove all doubt.
Be Used for Any Commercial Purposes of Any Kind.

What bastard operator would deny an innocent user such an irresistible pleasure for a few GBs of disk? :-)

Quoted 2 lines

If you want to archive all of your SPAM, why use a Maildir format mbox at all?

You're right, but we'd have to teach all the tools that mess into the Maildir about both formats. I find it incredibly easier to process email if it's in one simple format. As in my cleanup script:

for i in /mail/*/.Junk.Both/cur /mail/*/.Junk.Both/new; do

     ls -t $i | tail -n +2000 | xargs rm;

done

Easy as pie ;-)

For a while, we considered reiser3 for mail storage, but seeing it's being marginally maintained and phased out by all distributors, we've opted for wasting some cheap disk space instead.

Signature · 3 lines
  \___/
 _| X |  Bernie Innocenti - http://www.codewiz.org/
 \|_O_|  "It's an education project, not a laptop project!"
#7 lore raw
In reply to Bernie Innocenti
Quoted 7 lines · Bernie Innocenti

Some background: I'm moving users' Maildirs to a separate filesystem tuned for small files to increase performance. One of our users intentionally collected spam for 5 years in one folder and likes it this way. We could easily work it around, but first I'd like to understand whether the particular parameters we used trigger a bug in ext3 or if we're just hitting a (possibly undocumented) limit.

No, not a bug, but a limit. Ext3's hash directores are limited to a depth of 3 blocks, which normally isn't a problem if you are using a 4k blocksize, since each internal node is small; only 8 bytes. So you have a fanout of 508 for each internal node, and two internal nodes gets you to over 250,000 4k directory blocks. But with a 1k blocksize, the internal node fanout is only 124, so that only gets you a bit more than 15,000 1k directory blocks.

We could remove this limit at some point; the problem is that Daniel Phillip's original code had this as a limitation, and fixing it would mean replacing the tree implementation. We actually have some code from Lustre that we could use for this purpose, but to date we've been focused on some other higher priority items for ext4.

- Ted

#8 lore raw
Quoted 7 lines · Theodore Tso

No, not a bug, but a limit. Ext3's hash directores are limited to a depth of 3 blocks, which normally isn't a problem if you are using a 4k blocksize, since each internal node is small; only 8 bytes. So you have a fanout of 508 for each internal node, and two internal nodes gets you to over 250,000 4k directory blocks. But with a 1k blocksize, the internal node fanout is only 124, so that only gets you a bit more than 15,000 1k directory blocks.

So, if I understand correctly, with a 1024 bytes blocksize, dir_index, and inode size of 128 byte, the maximum number of files in a directory is 123008. With 4k blocks this limit rises to 8,258,048 files?

#9 lore raw
Quoted 4 lines · Stefano Fedrigo

So, if I understand correctly, with a 1024 bytes blocksize, dir_index, and inode size of 128 byte, the maximum number of files in a directory is 123008. With 4k blocks this limit rises to 8,258,048 files?

It depends on the length of the directory entries, and how full the various directory blocks end up getting (which is a function of the directory names used and the per-filesystem hash seed). But in general, the maximum limit goes up as the cube of the blocksize. So a 4k filesystem can store roughly 64 times as many files ; a filesystem using 16k blocks (say, on a Power or IA64 architecture) will be able to store roughly 4,096 as many files in a single directory. (So around 819 million files in a single directory, using the original maildir example).

Seriously, though, past a certain point, if you really want to store that many small datums, you should really consider a database....

- Ted