ext3_dx_add_entry: Directory index full!

ext3_dx_add_entry: Directory index full!

[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
  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.

-- 
   \___/
  _| X |  Bernie Innocenti - http://www.codewiz.org/
  \|_O_|  "It's an education project, not a laptop project!"

Re: ext3_dx_add_entry: Directory index full!

[Bernie Innocenti]

Bernie Innocenti wrote:
> 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?

-- 
   \___/
  _| X |  Bernie Innocenti - http://www.codewiz.org/
  \|_O_|  "It's an education project, not a laptop project!"

Re: ext3_dx_add_entry: Directory index full!

[Jan Engelhardt]

On Sunday 2008-05-18 17:38, Bernie Innocenti wrote:
> Bernie Innocenti wrote:
>> 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.

Re: ext3_dx_add_entry: Directory index full!

[Theodore Tso]

On Sun, May 18, 2008 at 05:38:58PM +0200, Bernie Innocenti wrote:
> Bernie Innocenti wrote:
>> 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?

Re: ext3_dx_add_entry: Directory index full!

[Bernie Innocenti]

Theodore Tso wrote:

> 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? :-)


> 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.

-- 
   \___/
  _| X |  Bernie Innocenti - http://www.codewiz.org/
  \|_O_|  "It's an education project, not a laptop project!"

Re: ext3_dx_add_entry: Directory index full!

[David Woodhouse]

On Sun, 2008-05-18 at 17:36 +0200, Bernie Innocenti wrote:
> 
> 
>   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?

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

-- 
dwmw2

Re: ext3_dx_add_entry: Directory index full!

[Bernie Innocenti]

David Woodhouse wrote:

> On Sun, 2008-05-18 at 17:36 +0200, Bernie Innocenti wrote:
>>
>>   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?
> 
> It doesn't. "condition?A:B" will return A if the condition is _true_,
> which it isn't.

Oh... I feel stupid.

-- 
   \___/
  _| X |  Bernie Innocenti - http://www.codewiz.org/
  \|_O_|  "It's an education project, not a laptop project!"

Re: ext3_dx_add_entry: Directory index full!

[Theodore Tso]

On Sun, May 18, 2008 at 05:36:02PM +0200, Bernie Innocenti wrote:
>
> 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

Re: ext3_dx_add_entry: Directory index full!

[Stefano Fedrigo]

On May 18, 2008, at 6:24 PM, Theodore Tso wrote:

> 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?

Re: ext3_dx_add_entry: Directory index full!

[Theodore Tso]

On Mon, May 19, 2008 at 01:01:57AM +0200, Stefano Fedrigo wrote:
>
> 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