From: Eric Biggers <ebiggers@kernel.org>
To: "Theodore Y. Ts'o" <tytso@mit.edu>
Cc: Andreas Dilger <adilger@dilger.ca>,
linux-ext4@vger.kernel.org, linux-fscrypt@vger.kernel.org
Subject: Re: [PATCH v3] e2fsck: check for consistent encryption policies
Date: Mon, 9 Sep 2019 10:34:20 -0700 [thread overview]
Message-ID: <20190909173418.GA12329@gmail.com> (raw)
In-Reply-To: <20190907100640.GA6778@mit.edu>
On Sat, Sep 07, 2019 at 06:06:40AM -0400, Theodore Y. Ts'o wrote:
> On Fri, Sep 06, 2019 at 10:23:03PM -0600, Andreas Dilger wrote:
> > If the number of files in the array get very large, then doubling the
> > array size at the end may consume a *lot* of memory. It would be
> > somewhat better to cap new_capacity by the number of inodes in the
> > filesystem, and better yet scale the array size by a fraction of the
> > total number of inodes that have already been processed, but this array
> > might still be several GB of RAM.
> >
> > What about using run-length encoding for this? It is unlikely that many
> > different encryption policies are in a filesystem, and inodes tend to be
> > allocated in groups by users, so it is likely that you will get large runs
> > of inodes with the same policy_id, and this could save considerable space.
>
> One approach that we could use is to allocate a separate bitmap for
> each policy. EXT2FS_BMAP_RBTREE effectively will use RLE. The
> downside is that if the inodes are not sparse, it will be quite
> heavyweight; each extent costs 40 bytes.
>
> So for file system with a very large number of policies (as opposed
> less than two or three, which will be the case with the vast majority
> of Android devices) this could be quite expensive.
>
> Of course, we don't have to use an rbtree; the bitarray will be
> created sequentially, so in theory we could create a new bitmap
> backend which uses a sorted list, which is O(1) for ordered insert and
> o(log n) for lookups. That could be about 12 bytes per extent. And
> of course, we don't have to implement the sorted list back end right
> away, switching it is just a matter of changing a parameter to
> ext2fs_alloc_generic_bitmap().
>
I don't think a bitmap per policy is a good idea, even if it was actually
represented as an rbtree or a sorted list. The problem is that to look up an
inode's encryption policy ID that way, you'd have to iterate through every
encryption policy, of which there could be a huge number.
Instead I'll try just changing:
struct encrypted_file {
ext2_ino_t ino;
__u32 policy_id;
};
to the following:
struct encrypted_file_range {
ext2_ino_t first_ino;
ext2_ino_t last_ino;
__u32 policy_id;
};
- Eric
prev parent reply other threads:[~2019-09-09 17:34 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-08-23 16:23 [PATCH v3] e2fsck: check for consistent encryption policies Eric Biggers
2019-09-04 15:55 ` Eric Biggers
2019-09-07 4:23 ` Andreas Dilger
2019-09-07 10:06 ` Theodore Y. Ts'o
2019-09-09 17:34 ` Eric Biggers [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190909173418.GA12329@gmail.com \
--to=ebiggers@kernel.org \
--cc=adilger@dilger.ca \
--cc=linux-ext4@vger.kernel.org \
--cc=linux-fscrypt@vger.kernel.org \
--cc=tytso@mit.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).