linux-ext4 - Re: [RFC] dynamic inodes

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: <20080925232951.GQ10950@webber.adilger.int>
Date:	Thu, 25 Sep 2008 17:29:51 -0600
From:	Andreas Dilger <adilger@....com>
To:	Alex Tomas <bzzz@....com>
Cc:	ext4 development <linux-ext4@...r.kernel.org>
Subject: Re: [RFC] dynamic inodes

On Sep 26, 2008  03:00 +0400, Alex Tomas wrote:
> Andreas Dilger wrote:
>> Storing B:0 for an in-use block seems very dangerous to me.  This also
>> doesn't really address the need to be able to quickly locate free inodes,
>> because it means "I:1" _might_ mean the inode is free or it might not,
>> so EVERY "in-use" inode would need to be checked to see if it is free.
>
> just combine I and B into single bitmap:
> 1) when you look for free block it's any 0 bit in bitmap made by (I & B)
> 2) when you look for free inode (in current inode blocks) it's any 1 bit
>    in bitmap made again by (I & B), then you read corresponded block and
>    find free slot there (for example, it can be null i_mode)
>
> looks very simple and doable?

It _sounds_ simple, but I think the implementation will not be what
is expected.  Either you need to keep a 3rd bitmap for each group
which is (I&B) used for finding either inodes or blocks first (with
respectively find_first_bit() or find_first_zero_bit()), then check the
"normal" inode and block bitmaps, keeping this in sync with mballoc, and
confusion/danger on disk/e2fsck because in-use itable blocks are marked
"0" in the block bitmap.  There will be races between updating these
bitmaps, unless the group is locked for both block or inode allocations
on any update because setting any bit completely changes the meaning.

Alternately, if there are only I and B bitmaps, then find_first_bit()
and find_first_zero_bit() are not useful.  Searching for free blocks
means looking for "B:0" and finding potentially many "B:0 I:1" blocks
that are full of inodes.  Searching for free inodes means looking for
"I:1" (strangely) but finding potentially many "I:1 B:0" blocks.

I much prefer the dynamic itable idea from José (which I embellished in
my other email), which is very simple for both the kernel and e2fsck,
robust, and avoids the 64-bit inode problem for userspace to the maximum
amount (i.e. a full 4B inodes must be in use before we ever need to
use 64-bit inodes).  The lack of complexity in itable allocation also
translates directly into increased robustness in the face of corruption.

It doesn't provide dynamic-sized inodes (which hasn't traditionally
been a problem), nor is it perfect in terms of being able to fully
populate a filesystem with inodes in all use cases but it could work
in all but completely pathalogical fragmentation cases (at which point
one wonders if it isn't better to just return -ENOSPC than to flog a
nearly dead filesystem).  It can definitely do a good job in most likely
uses, and also provides a big win over what is done today.

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 majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html