linux-fscrypt.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: "Theodore Y. Ts'o" <tytso@mit.edu>
To: Andreas Dilger <adilger@dilger.ca>
Cc: Eric Biggers <ebiggers@kernel.org>,
	linux-ext4@vger.kernel.org, linux-fscrypt@vger.kernel.org
Subject: Re: [PATCH v3] e2fsck: check for consistent encryption policies
Date: Sat, 7 Sep 2019 06:06:40 -0400	[thread overview]
Message-ID: <20190907100640.GA6778@mit.edu> (raw)
In-Reply-To: <28D1848F-B84A-4D2A-880E-F0C8E8FD36C7@dilger.ca>

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

      	     	       	    	     	      - Ted

  reply	other threads:[~2019-09-07 10:06 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 [this message]
2019-09-09 17:34       ` Eric Biggers

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=20190907100640.GA6778@mit.edu \
    --to=tytso@mit.edu \
    --cc=adilger@dilger.ca \
    --cc=ebiggers@kernel.org \
    --cc=linux-ext4@vger.kernel.org \
    --cc=linux-fscrypt@vger.kernel.org \
    /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).