[RFC] Per-file compression

[RFC] Per-file compression

[Tom Marshall]

I'd like to get some thoughts on whether having transparent per-file 
compression implemented in the kernel would be desirable.

Details:

We are running into space issues when upgrading Android devices to the 
latest version.  This issue is particularly troublesome for 64-bit 
devices that initially shipped without 64-bit support, as the multi-lib 
files nearly double the space requirements.  As it happens, many system 
files are quite compressible -- namely shared libs and apk files.  So 
implementing filesystem compression is a natural solution.

After investigating several well known compression solutions, we did not 
find any that met our goals:

* Compression should be transparent to user space.  It would be possible 
to identify subsets of the filesystem that compress well and handle 
compression in user space.  However, doing this involves repeating 
similar work in different areas of code, and can never fully utilize 
compression across the entire filesystem.

* Compression must work with existing Android filesystems.  There are 
filesystems that have native compression.  However, switching to a new 
filesystem on a released device is not really desirable.

* Compression should be implemented as transparently as possible. cloop 
is filesystem independent, but it makes the underlying device 
read-only.  This could be mitigated somewhat with overlayfs, but that 
would be a rather complex solution.

* Compression should be independent of the filesystem.  e2compr may work 
for ext2, but it seems abandoned and does not address other filesystem 
types.

So, I wrote a thing called 'zfile' that hooks into the VFS layer and 
intercepts file_operations to do file (de)compression on the fly. When a 
file is opened, it reads and decompresses the data into memory.  The 
file may be read, written, and mmaped in the usual way.  If the contents 
are changed, the data is compressed and written back.  A working patch 
for an older kernel version may be found at: 
http://review.cyanogenmod.org/#/c/95220/

Note this is mostly just a prototype at the moment.  I'm fully aware 
that it has some bugs and limitations.  Pretty major ones, I'm sure.  
However, if this is something that is generally desirable, I would look 
forward to working with the VFS maintainers to make it merge worthy.

Thanks!

Re: [RFC] Per-file compression

[Richard Weinberger]

On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
> I'd like to get some thoughts on whether having transparent per-file
> compression implemented in the kernel would be desirable.
>
> Details:
>
> We are running into space issues when upgrading Android devices to the
> latest version.  This issue is particularly troublesome for 64-bit devices
> that initially shipped without 64-bit support, as the multi-lib files nearly
> double the space requirements.  As it happens, many system files are quite
> compressible -- namely shared libs and apk files.  So implementing
> filesystem compression is a natural solution.
>
> After investigating several well known compression solutions, we did not
> find any that met our goals:
>
> * Compression should be transparent to user space.  It would be possible to
> identify subsets of the filesystem that compress well and handle compression
> in user space.  However, doing this involves repeating similar work in
> different areas of code, and can never fully utilize compression across the
> entire filesystem.
>
> * Compression must work with existing Android filesystems.  There are
> filesystems that have native compression.  However, switching to a new
> filesystem on a released device is not really desirable.
>
> * Compression should be implemented as transparently as possible. cloop is
> filesystem independent, but it makes the underlying device read-only.  This
> could be mitigated somewhat with overlayfs, but that would be a rather
> complex solution.
>
> * Compression should be independent of the filesystem.  e2compr may work for
> ext2, but it seems abandoned and does not address other filesystem types.
>
> So, I wrote a thing called 'zfile' that hooks into the VFS layer and
> intercepts file_operations to do file (de)compression on the fly. When a
> file is opened, it reads and decompresses the data into memory.  The file
> may be read, written, and mmaped in the usual way.  If the contents are
> changed, the data is compressed and written back.  A working patch for an
> older kernel version may be found at:
> http://review.cyanogenmod.org/#/c/95220/

Can you please share the patch as plain patch in your mail?

> Note this is mostly just a prototype at the moment.  I'm fully aware that it
> has some bugs and limitations.  Pretty major ones, I'm sure.  However, if
> this is something that is generally desirable, I would look forward to
> working with the VFS maintainers to make it merge worthy.

The first question which comes to my mind is, why can't use just
create a FUSE overlay
filesystem for that?

-- 
Thanks,
//richard

Re: [RFC] Per-file compression

[Theodore Ts'o]

On Sat, Apr 18, 2015 at 10:06:14AM +0200, Richard Weinberger wrote:
> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
> > We are running into space issues when upgrading Android devices to the
> > latest version.  This issue is particularly troublesome for 64-bit devices
> > that initially shipped without 64-bit support, as the multi-lib files nearly
> > double the space requirements.  As it happens, many system files are quite
> > compressible -- namely shared libs and apk files.  So implementing
> > filesystem compression is a natural solution.

Tom, have you verified whether or not this approach actually is
sufficient to address the problem you are trying to solve?
Specifically, (a) can you get enough space compression that it will
make things fit?  Given that apk files are already compressed using
zip, I'm a bit surprised you would get enough of a compression savings
that it's going to allow to make things fit.  And secondly (b) after
you decompress the shared libraries, is there enough memory that the
resulting system functions well.  Often times these older Android
devices don't have a huge amount of memory, and so either with or
without the overhead of needing to decompress the entire file (which
can be solved with chunking, although this tends to reduce the
compression efficiency), is the system going to function well using
64-bit binaries that take up a lot more room than the older 32-bit
binaries?

> > So, I wrote a thing called 'zfile' that hooks into the VFS layer and
> > intercepts file_operations to do file (de)compression on the fly. When a
> > file is opened, it reads and decompresses the data into memory.  The file
> > may be read, written, and mmaped in the usual way.  If the contents are
> > changed, the data is compressed and written back.

Do you really need to be able to rewrite the files?  Life gets much
easier if you can assume that the compressed files are read-only;
especially once you start trying to use chunking, it *definitely*
becomes easier if you don't need to support modifying the compressed
files.  And in the case of the system partition, this might be a safe
assumption,yes?

					- Ted

Re: [RFC] Per-file compression

[Alex Elsayed]

Theodore Ts'o wrote:

> On Sat, Apr 18, 2015 at 10:06:14AM +0200, Richard Weinberger wrote:
>> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
>> > We are running into space issues when upgrading Android devices to the
>> > latest version.  This issue is particularly troublesome for 64-bit
>> > devices that initially shipped without 64-bit support, as the multi-lib
>> > files nearly
>> > double the space requirements.  As it happens, many system files are
>> > quite
>> > compressible -- namely shared libs and apk files.  So implementing
>> > filesystem compression is a natural solution.
> 
> Tom, have you verified whether or not this approach actually is
> sufficient to address the problem you are trying to solve?
> Specifically, (a) can you get enough space compression that it will
> make things fit?  Given that apk files are already compressed using
> zip, I'm a bit surprised you would get enough of a compression savings
> that it's going to allow to make things fit.  And secondly (b) after
> you decompress the shared libraries, is there enough memory that the
> resulting system functions well.  Often times these older Android
> devices don't have a huge amount of memory, and so either with or
> without the overhead of needing to decompress the entire file (which
> can be solved with chunking, although this tends to reduce the
> compression efficiency), is the system going to function well using
> 64-bit binaries that take up a lot more room than the older 32-bit
> binaries?

APK files may be using the zip _format_, but it's not uncommon for the 
compression level to be zero. Honestly, _that_ sounds like a saner way of 
addressing the issue to me, especially if files are compressed whole rather 
than chunked for random access - set the compression level to 9 or 
something, since whichever level you add the compression at you've already 
lost the (IMO of dubious importance) speed benefit zero-compression zip 
gives.

>> > So, I wrote a thing called 'zfile' that hooks into the VFS layer and
>> > intercepts file_operations to do file (de)compression on the fly. When
>> > a
>> > file is opened, it reads and decompresses the data into memory.  The
>> > file
>> > may be read, written, and mmaped in the usual way.  If the contents are
>> > changed, the data is compressed and written back.
> 
> Do you really need to be able to rewrite the files?  Life gets much
> easier if you can assume that the compressed files are read-only;
> especially once you start trying to use chunking, it *definitely*
> becomes easier if you don't need to support modifying the compressed
> files.  And in the case of the system partition, this might be a safe
> assumption,yes?
> 
> - Ted
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel"
> in the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] Per-file compression

[Richard Weinberger]

On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
> So, I wrote a thing called 'zfile' that hooks into the VFS layer and
> intercepts file_operations to do file (de)compression on the fly. When a
> file is opened, it reads and decompresses the data into memory.  The file
> may be read, written, and mmaped in the usual way.  If the contents are
> changed, the data is compressed and written back.  A working patch for an
> older kernel version may be found at:
> http://review.cyanogenmod.org/#/c/95220/

So, I've extracted the patch from that website and gave a quick review.

I'm pretty sure VFS folks will hate the VFS layering you do.

Beside of that you decompress the *whole* file into memory at open() time.
This will explode as soon you deal with bigger files. Also you seem to trust the
user.compression.realsize xattr provided by userspace.
That looks exploitable.

Back to my original question, why not FUSE?
Or add compression support to ecryptfs...

-- 
Thanks,
//richard

Re: [RFC] Per-file compression

[Tom Marshall]

Thanks for taking the time to reply.

On Sat, Apr 18, 2015 at 01:41:09PM +0200, Richard Weinberger wrote:
> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
> > So, I wrote a thing called 'zfile' that hooks into the VFS layer and
> > intercepts file_operations to do file (de)compression on the fly. When a
> > file is opened, it reads and decompresses the data into memory.  The file
> > may be read, written, and mmaped in the usual way.  If the contents are
> > changed, the data is compressed and written back.  A working patch for an
> > older kernel version may be found at:
> > http://review.cyanogenmod.org/#/c/95220/
> 
> So, I've extracted the patch from that website and gave a quick review.
> 
> I'm pretty sure VFS folks will hate the VFS layering you do.

This, I'm afraid, is the biggest obstacle to such a solution.  I know that
OverlayFS has been merged, so filesystem stacking is acceptable.  Perhaps
there would be a way to design a filesystem that stacks compression?

> Beside of that you decompress the *whole* file into memory at open() time.
> This will explode as soon you deal with bigger files.

I was thinking that a header with compressed offsets might be an option.  Or
in the case of lz4 it's not terribly inefficient to scan the blocks.

> Also you seem to trust the user.compression.realsize xattr provided by
> userspace.  That looks exploitable.

This is only used to provide a fast stat().  It could be put into a header
or even removed entirely in favor of scanning the blocks.

> Back to my original question, why not FUSE?

Mostly because I'm not very familiar with FUSE.  But I suppose it could be
an option.  I have some immediate concerns though:

* How would it affect performance?  FUSE passes all operations through user
  space, correct?

* How big might a reasonably complete implementation be for ARM?  The
  implementation would need to be stored in the initrd.

> Or add compression support to ecryptfs...

Several filesystems have native compression support.  But this would violate
the goal of not switching filesystems.

Re: [RFC] Per-file compression

[Richard Weinberger]

Hi!

Am 18.04.2015 um 16:58 schrieb Tom Marshall:
> On Sat, Apr 18, 2015 at 01:41:09PM +0200, Richard Weinberger wrote:
>> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
>>> So, I wrote a thing called 'zfile' that hooks into the VFS layer and
>>> intercepts file_operations to do file (de)compression on the fly. When a
>>> file is opened, it reads and decompresses the data into memory.  The file
>>> may be read, written, and mmaped in the usual way.  If the contents are
>>> changed, the data is compressed and written back.  A working patch for an
>>> older kernel version may be found at:
>>> http://review.cyanogenmod.org/#/c/95220/
>>
>> So, I've extracted the patch from that website and gave a quick review.
>>
>> I'm pretty sure VFS folks will hate the VFS layering you do.
> 
> This, I'm afraid, is the biggest obstacle to such a solution.  I know that
> OverlayFS has been merged, so filesystem stacking is acceptable.  Perhaps
> there would be a way to design a filesystem that stacks compression?

That's why I said think of adding compression support to ecryptfs.

>> Beside of that you decompress the *whole* file into memory at open() time.
>> This will explode as soon you deal with bigger files.
> 
> I was thinking that a header with compressed offsets might be an option.  Or
> in the case of lz4 it's not terribly inefficient to scan the blocks.
> 
>> Also you seem to trust the user.compression.realsize xattr provided by
>> userspace.  That looks exploitable.
> 
> This is only used to provide a fast stat().  It could be put into a header
> or even removed entirely in favor of scanning the blocks.
> 
>> Back to my original question, why not FUSE?
> 
> Mostly because I'm not very familiar with FUSE.  But I suppose it could be
> an option.  I have some immediate concerns though:
> 
> * How would it affect performance?  FUSE passes all operations through user
>   space, correct?

Yeah, but you'll have to do benchmarks to find out the real trade off.
I'd give it a tray. Your targets are smartphones not HPC clusters.

> * How big might a reasonably complete implementation be for ARM?  The
>   implementation would need to be stored in the initrd.

I bet you can do it in less than 1000 lines of C...

>> Or add compression support to ecryptfs...
> 
> Several filesystems have native compression support.  But this would violate
> the goal of not switching filesystems.

...your goals. Be flexible. ;)
BTW: ecryptfs is an overlay filesystem.

Thanks,
//richard

Re: [RFC] Per-file compression

[Tom Marshall]

On Sat, Apr 18, 2015 at 05:07:16PM +0200, Richard Weinberger wrote:
> Hi!
> 
> Am 18.04.2015 um 16:58 schrieb Tom Marshall:
> > On Sat, Apr 18, 2015 at 01:41:09PM +0200, Richard Weinberger wrote:
> >> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
> >>> So, I wrote a thing called 'zfile' that hooks into the VFS layer and
> >>> intercepts file_operations to do file (de)compression on the fly. When a
> >>> file is opened, it reads and decompresses the data into memory.  The file
> >>> may be read, written, and mmaped in the usual way.  If the contents are
> >>> changed, the data is compressed and written back.  A working patch for an
> >>> older kernel version may be found at:
> >>> http://review.cyanogenmod.org/#/c/95220/
> >>
> >> So, I've extracted the patch from that website and gave a quick review.
> >>
> >> I'm pretty sure VFS folks will hate the VFS layering you do.
> > 
> > This, I'm afraid, is the biggest obstacle to such a solution.  I know that
> > OverlayFS has been merged, so filesystem stacking is acceptable.  Perhaps
> > there would be a way to design a filesystem that stacks compression?
> 
> That's why I said think of adding compression support to ecryptfs.
> 
> >> Beside of that you decompress the *whole* file into memory at open() time.
> >> This will explode as soon you deal with bigger files.
> > 
> > I was thinking that a header with compressed offsets might be an option.  Or
> > in the case of lz4 it's not terribly inefficient to scan the blocks.
> > 
> >> Also you seem to trust the user.compression.realsize xattr provided by
> >> userspace.  That looks exploitable.
> > 
> > This is only used to provide a fast stat().  It could be put into a header
> > or even removed entirely in favor of scanning the blocks.
> > 
> >> Back to my original question, why not FUSE?
> > 
> > Mostly because I'm not very familiar with FUSE.  But I suppose it could be
> > an option.  I have some immediate concerns though:
> > 
> > * How would it affect performance?  FUSE passes all operations through user
> >   space, correct?
> 
> Yeah, but you'll have to do benchmarks to find out the real trade off.
> I'd give it a tray. Your targets are smartphones not HPC clusters.

I'll certainly keep that in mind as an option.  If nothing else, it would
provide a way to iterate on development much more quickly than I'm doing
now.  :)

> 
> > * How big might a reasonably complete implementation be for ARM?  The
> >   implementation would need to be stored in the initrd.
> 
> I bet you can do it in less than 1000 lines of C...
> 
> >> Or add compression support to ecryptfs...
> > 
> > Several filesystems have native compression support.  But this would violate
> > the goal of not switching filesystems.
> 
> ...your goals. Be flexible. ;)
> BTW: ecryptfs is an overlay filesystem.

Given the choice of adding compression support to ecryptfs and making a new
similar filesystem (ecompressfs?), which would you recommend?

Re: [RFC] Per-file compression

[Richard Weinberger]

Am 18.04.2015 um 17:48 schrieb Tom Marshall:
>> ...your goals. Be flexible. ;)
>> BTW: ecryptfs is an overlay filesystem.
> 
> Given the choice of adding compression support to ecryptfs and making a new
> similar filesystem (ecompressfs?), which would you recommend?

I'd give ecryptfs a try to re-use as much existing code as possible.

Thanks,
//richard

Re: [RFC] Per-file compression

[Tyler Hicks]

[-- Attachment #1: Type: text/plain, Size: 3922 bytes --]

On 2015-04-18 17:07:16, Richard Weinberger wrote:
> Hi!
> 
> Am 18.04.2015 um 16:58 schrieb Tom Marshall:
> > On Sat, Apr 18, 2015 at 01:41:09PM +0200, Richard Weinberger wrote:
> >> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
> >>> So, I wrote a thing called 'zfile' that hooks into the VFS layer and
> >>> intercepts file_operations to do file (de)compression on the fly. When a
> >>> file is opened, it reads and decompresses the data into memory.  The file
> >>> may be read, written, and mmaped in the usual way.  If the contents are
> >>> changed, the data is compressed and written back.  A working patch for an
> >>> older kernel version may be found at:
> >>> http://review.cyanogenmod.org/#/c/95220/
> >>
> >> So, I've extracted the patch from that website and gave a quick review.
> >>
> >> I'm pretty sure VFS folks will hate the VFS layering you do.
> > 
> > This, I'm afraid, is the biggest obstacle to such a solution.  I know that
> > OverlayFS has been merged, so filesystem stacking is acceptable.  Perhaps
> > there would be a way to design a filesystem that stacks compression?
> 
> That's why I said think of adding compression support to ecryptfs.

I think adding compression support to eCryptfs is the wrong approach.
The "X is already a stacked filesystem so look into adding compression
support to it" logic also works when X=overlayfs. I doubt that Miklos
would be willing to accept such a feature. :)

A stacked filesystem that implements compression should be fairly
simple. If it is not simple, it is too complicated to try to wedge into
an unrelated stacked filesystem.

While it may be the quickest route to your end goal, it will overly
complicate eCryptfs. eCryptfs already has plenty of complexity around
the file offset since metadata may be stored in the first 8192 bytes of
the lower file, which offsets the entire file, and the end of the file
has to be padded. Mixing in compression would make things much worse.

Also, eCryptfs has lots of cruft that is definitely not needed for
compression.

Please consider a small, standalone stacked fs to handle compression.

Tyler

> 
> >> Beside of that you decompress the *whole* file into memory at open() time.
> >> This will explode as soon you deal with bigger files.
> > 
> > I was thinking that a header with compressed offsets might be an option.  Or
> > in the case of lz4 it's not terribly inefficient to scan the blocks.
> > 
> >> Also you seem to trust the user.compression.realsize xattr provided by
> >> userspace.  That looks exploitable.
> > 
> > This is only used to provide a fast stat().  It could be put into a header
> > or even removed entirely in favor of scanning the blocks.
> > 
> >> Back to my original question, why not FUSE?
> > 
> > Mostly because I'm not very familiar with FUSE.  But I suppose it could be
> > an option.  I have some immediate concerns though:
> > 
> > * How would it affect performance?  FUSE passes all operations through user
> >   space, correct?
> 
> Yeah, but you'll have to do benchmarks to find out the real trade off.
> I'd give it a tray. Your targets are smartphones not HPC clusters.
> 
> > * How big might a reasonably complete implementation be for ARM?  The
> >   implementation would need to be stored in the initrd.
> 
> I bet you can do it in less than 1000 lines of C...
> 
> >> Or add compression support to ecryptfs...
> > 
> > Several filesystems have native compression support.  But this would violate
> > the goal of not switching filesystems.
> 
> ...your goals. Be flexible. ;)
> BTW: ecryptfs is an overlay filesystem.
> 
> Thanks,
> //richard
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [RFC] Per-file compression

[Richard Weinberger]

Am 20.04.2015 um 16:53 schrieb Tyler Hicks:
> On 2015-04-18 17:07:16, Richard Weinberger wrote:
>> Hi!
>>
>> Am 18.04.2015 um 16:58 schrieb Tom Marshall:
>>> On Sat, Apr 18, 2015 at 01:41:09PM +0200, Richard Weinberger wrote:
>>>> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote:
>>>>> So, I wrote a thing called 'zfile' that hooks into the VFS layer and
>>>>> intercepts file_operations to do file (de)compression on the fly. When a
>>>>> file is opened, it reads and decompresses the data into memory.  The file
>>>>> may be read, written, and mmaped in the usual way.  If the contents are
>>>>> changed, the data is compressed and written back.  A working patch for an
>>>>> older kernel version may be found at:
>>>>> http://review.cyanogenmod.org/#/c/95220/
>>>>
>>>> So, I've extracted the patch from that website and gave a quick review.
>>>>
>>>> I'm pretty sure VFS folks will hate the VFS layering you do.
>>>
>>> This, I'm afraid, is the biggest obstacle to such a solution.  I know that
>>> OverlayFS has been merged, so filesystem stacking is acceptable.  Perhaps
>>> there would be a way to design a filesystem that stacks compression?
>>
>> That's why I said think of adding compression support to ecryptfs.
> 
> I think adding compression support to eCryptfs is the wrong approach.
> The "X is already a stacked filesystem so look into adding compression
> support to it" logic also works when X=overlayfs. I doubt that Miklos
> would be willing to accept such a feature. :)

My thought was that compression is not far away from crypto an hence
a lot of ecryptfs could be reused.

> A stacked filesystem that implements compression should be fairly
> simple. If it is not simple, it is too complicated to try to wedge into
> an unrelated stacked filesystem.
> 
> While it may be the quickest route to your end goal, it will overly
> complicate eCryptfs. eCryptfs already has plenty of complexity around
> the file offset since metadata may be stored in the first 8192 bytes of
> the lower file, which offsets the entire file, and the end of the file
> has to be padded. Mixing in compression would make things much worse.

I assumed that you need also some meta data for compression.
At least if you do it in a non-trivial way.

> Also, eCryptfs has lots of cruft that is definitely not needed for
> compression.

As you're the maintainer of ecryptfs you know obviously better than I do. :)
Tom, to make the story short, you'll have to experiment a bit.

Thanks,
//richard

Re: [RFC] Per-file compression

[Theodore Ts'o]

On Mon, Apr 20, 2015 at 06:51:03PM +0200, Richard Weinberger wrote:
> My thought was that compression is not far away from crypto an hence
> a lot of ecryptfs could be reused.

The problem with using eCryptfs as a base is that it assumes that the
encryption is constant-sized --- i.e., that a 4096 plaintext block
encrypts to a 4096 ciphertext block.  This is *not* true for compression.

The other problem with eCryptfs is that since the underlying file
system doesn't know it's being stacked, you end up burning memory for
both the plaintext and ciphertext versions of the file.  This is one
of the reasons why eCryptfs wasn't considered for future versions of
Android; instead we've added encryption into the ext4 file system
layer instead.  (With most of the interesting bits in separate files,
and where I've been communicating with the f2fs maintainer so that
f2fs can add the same encryption feature into f2fs).

For compression, what I'd recommend doing is something similar; do it
at the file system level, but structure it such that it's relatively
easy for other file systems to reuse "library code" for the core data
transforms.  However, allow the underlying file system to use its own
specialized storage for things like flags, xattrs, etc., since it can
be made more efficient.

What I'd also suggest is that you support read-only compression (which
is what MacOS did as well), and do it by using a chunksize of say, 32k
or 64k, and at the very end of the file, store a pointer to the
compressed chunk directory which is simply a header which describes
the chunk size (and other useful bits, such as the compression
algorith, *possibly* a space for a preset compression dictionary that
would be shared across all of the chunks, if that makes sense, and
then a list of offsets into the files which gives the starting offset
for chunk #0, chunk #1, chunk #2, etc.

This file would be created with some help from a userspace
application; said userspace application would do the compression and
write out the compressed file, and then call an ioctl which sets an
attribute which (a) flushes the page cache from containing the
compressed version of the file, and (b) marks the inode as read-only
and containing compressed data.

When the kernel reads from the file, it reads the compression header
and directory, and then pages into the page cache a chunk at a time
--- that is, if userspace requests a single 4k page, the kernel will
read in whatever blocks are needed to decompress the 64k chunk
containing that page, and populate the page cache with that 64k chunk.

I've sketched this design out a few times, hoping to interest someone
into implementing it for ext4, but this is the sort of thing that
could be implemented as a library, and then easily spliced into
mulitple file systems.

Cheers,

					- Ted

P.S.  Note that one of the things about this design is that although
it requires userspace support, it's *perfect* for files which are
installed via a package, whether that be an RPM, dpkg, or apk.  You
just need to create a userspace library which takes the incoming file
stream from the package file, and then writes out the compressed
version of the file and marks the file as containing compressed data.
It shouldn't be hard, once the userspace library is created, to modify
rpm, dpkg, etc., to take advantage of this feature.  And these package
files are the ones which are *perfect* candidates for compression;
they tend to be written once, and read many times, and in general they
are read-only.  (Yes, there are exceptions for config files, but rpm
and dpkg already have a way of specifying which files are config
files, which is important if you want to verify that the unpacked
pacakge is consistent with what was installed originally.)

Re: [RFC] Per-file compression

[Jeff Moyer]

"Theodore Ts'o" <tytso@mit.edu> writes:

> I've sketched this design out a few times, hoping to interest someone
> into implementing it for ext4, but this is the sort of thing that
> could be implemented as a library, and then easily spliced into
> mulitple file systems.

For those not aware, this was discussed previously on lkml:
  http://thread.gmane.org/gmane.linux.kernel/1531567

Cheers,
Jeff

Re: [RFC] Per-file compression

[Theodore Ts'o]

On Tue, Apr 21, 2015 at 11:37:53AM -0400, Jeff Moyer wrote:
> "Theodore Ts'o" <tytso@mit.edu> writes:
> 
> > I've sketched this design out a few times, hoping to interest someone
> > into implementing it for ext4, but this is the sort of thing that
> > could be implemented as a library, and then easily spliced into
> > mulitple file systems.
> 
> For those not aware, this was discussed previously on lkml:
>   http://thread.gmane.org/gmane.linux.kernel/1531567

Thanks for reminding me about this; I had forgotten the Mozzila folks
had been working on this.  I'm not sure what happened to that effort,
since as I recall they never came back with a revised patch set.

My apologies if that was because they were waiting for something from
me, but I maybe Dhaval can let us know if they took this work any
further?

						- Ted

Re: [RFC] Per-file compression

[Tom Marshall]

I've done some investigation into stacking compression on top of an 
existing filesystem with the ideas you suggested.  I'm not really much 
of a filesystem guy, so maybe I'm off base.  But here's what I've come 
up with so far:

Provide a function that the underlying filesystem can call to wrap the 
inode.  This allows a new inode to be created and passed back to the VFS 
layer.  Since this won't be a stacking filesystem, I was thinking of 
using new_inode_pseudo for this purpose, as is done in pipe.c.  The 
underlying inode is stored and referenced in inode.i_private.

The compressed inode implements all necessary operations for eg. read, 
write, mmap using generic_* functions where appropriate. This mostly 
leaves inode_operations.getattr and address_space_operations.readpage to 
be implemented.

getattr is implemented by calling the underlying getattr and then 
substituting in the uncompressed file size.

readpage is implemented by finding the compressed offset for the 
requested chunk of data and reading the underlying pages, decompressing 
the chunk, and copying out the desired data.  I'm looking at the 
squashfs implementation for clues as to how this should be done.

Does that sound like a reasonable plan, or am I off base?

On 04/21/2015 08:18 AM, Theodore Ts'o wrote:
> On Mon, Apr 20, 2015 at 06:51:03PM +0200, Richard Weinberger wrote:
>> My thought was that compression is not far away from crypto an hence
>> a lot of ecryptfs could be reused.
> The problem with using eCryptfs as a base is that it assumes that the
> encryption is constant-sized --- i.e., that a 4096 plaintext block
> encrypts to a 4096 ciphertext block.  This is *not* true for compression.
>
> The other problem with eCryptfs is that since the underlying file
> system doesn't know it's being stacked, you end up burning memory for
> both the plaintext and ciphertext versions of the file.  This is one
> of the reasons why eCryptfs wasn't considered for future versions of
> Android; instead we've added encryption into the ext4 file system
> layer instead.  (With most of the interesting bits in separate files,
> and where I've been communicating with the f2fs maintainer so that
> f2fs can add the same encryption feature into f2fs).
>
> For compression, what I'd recommend doing is something similar; do it
> at the file system level, but structure it such that it's relatively
> easy for other file systems to reuse "library code" for the core data
> transforms.  However, allow the underlying file system to use its own
> specialized storage for things like flags, xattrs, etc., since it can
> be made more efficient.
>
> What I'd also suggest is that you support read-only compression (which
> is what MacOS did as well), and do it by using a chunksize of say, 32k
> or 64k, and at the very end of the file, store a pointer to the
> compressed chunk directory which is simply a header which describes
> the chunk size (and other useful bits, such as the compression
> algorith, *possibly* a space for a preset compression dictionary that
> would be shared across all of the chunks, if that makes sense, and
> then a list of offsets into the files which gives the starting offset
> for chunk #0, chunk #1, chunk #2, etc.
>
> This file would be created with some help from a userspace
> application; said userspace application would do the compression and
> write out the compressed file, and then call an ioctl which sets an
> attribute which (a) flushes the page cache from containing the
> compressed version of the file, and (b) marks the inode as read-only
> and containing compressed data.
>
> When the kernel reads from the file, it reads the compression header
> and directory, and then pages into the page cache a chunk at a time
> --- that is, if userspace requests a single 4k page, the kernel will
> read in whatever blocks are needed to decompress the 64k chunk
> containing that page, and populate the page cache with that 64k chunk.
>
> I've sketched this design out a few times, hoping to interest someone
> into implementing it for ext4, but this is the sort of thing that
> could be implemented as a library, and then easily spliced into
> mulitple file systems.
>
> Cheers,
>
> 					- Ted
>
> P.S.  Note that one of the things about this design is that although
> it requires userspace support, it's *perfect* for files which are
> installed via a package, whether that be an RPM, dpkg, or apk.  You
> just need to create a userspace library which takes the incoming file
> stream from the package file, and then writes out the compressed
> version of the file and marks the file as containing compressed data.
> It shouldn't be hard, once the userspace library is created, to modify
> rpm, dpkg, etc., to take advantage of this feature.  And these package
> files are the ones which are *perfect* candidates for compression;
> they tend to be written once, and read many times, and in general they
> are read-only.  (Yes, there are exceptions for config files, but rpm
> and dpkg already have a way of specifying which files are config
> files, which is important if you want to verify that the unpacked
> pacakge is consistent with what was installed originally.)
>

Re: [RFC] Per-file compression

[Steve French]

On Fri, Apr 17, 2015 at 5:20 PM, Tom Marshall <tom@cyngn.com> wrote:
> I'd like to get some thoughts on whether having transparent per-file
> compression implemented in the kernel would be desirable.

For Samba this is very desirable.  Virtualization (HyperV in
particular over SMB3) will try to mark image files as compressed (and
sparse) which Samba typically can only do over btrfs.   As long as set
compression flag on the file is a 'hint' (in otherwords setting the
flag doesn't cause a blocking ioctl for 15 minutes to hang while it
compresses the file) it should be helpful to Samba in common
Windows/Mac workloads.

-- 
Thanks,

Steve

Re: [RFC] Per-file compression

[Tom Marshall]

On Apr 18, 2015 4:09 PM, Theodore Ts'o <tytso@mit.edu> wrote:
>
> On Sat, Apr 18, 2015 at 10:06:14AM +0200, Richard Weinberger wrote: 
> > On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote: 
> > > We are running into space issues when upgrading Android devices to the 
> > > latest version.  This issue is particularly troublesome for 64-bit devices 
> > > that initially shipped without 64-bit support, as the multi-lib files nearly 
> > > double the space requirements.  As it happens, many system files are quite 
> > > compressible -- namely shared libs and apk files.  So implementing 
> > > filesystem compression is a natural solution. 
>
> Tom, have you verified whether or not this approach actually is 
> sufficient to address the problem you are trying to solve? 
> Specifically, (a) can you get enough space compression that it will 
> make things fit?  Given that apk files are already compressed using 
> zip, I'm a bit surprised you would get enough of a compression savings 
> that it's going to allow to make things fit.

Yes it works surprisingly well. Both .so files and .apk files compress by roughly 40%. I'm also a bit surprised at the .apk results, but it works great.

>  And secondly (b) after 
> you decompress the shared libraries, is there enough memory that the 
> resulting system functions well.

Yes, on our particular device, it actually performs at least as well as before, possibly better. I haven't done an extensive survey of memory usage though.

The majority of compression comes from .so and .apk files. Shared libs are typically mmap'd and most of the contents accessed. apk files are not referenced much after initial dexopt.

> Often times these older Android 
> devices don't have a huge amount of memory, and so either with or 
> without the overhead of needing to decompress the entire file (which 
> can be solved with chunking, although this tends to reduce the 
> compression efficiency), is the system going to function well using 
> 64-bit binaries that take up a lot more room than the older 32-bit 
> binaries? 

Our test device is not so much an older device, just a mid-range device (msm8916). It has mediocre emmc speed and decent CPU (though thermal throttling is pretty aggressive).

>
> > > So, I wrote a thing called 'zfile' that hooks into the VFS layer and 
> > > intercepts file_operations to do file (de)compression on the fly. When a 
> > > file is opened, it reads and decompresses the data into memory.  The file 
> > > may be read, written, and mmaped in the usual way.  If the contents are 
> > > changed, the data is compressed and written back. 
>
> Do you really need to be able to rewrite the files?  Life gets much 
> easier if you can assume that the compressed files are read-only; 
> especially once you start trying to use chunking, it *definitely* 
> becomes easier if you don't need to support modifying the compressed 
> files.  And in the case of the system partition, this might be a safe 
> assumption,yes? 

You are correct. Writing is not really a requirement for us, just nice to have.

Re: [RFC] Per-file compression

[Tom Marshall]

I'll try my hand at ecompressfs shortly, thanks!On Apr 20, 2015 9:51 AM, Richard Weinberger <richard@nod.at> wrote:
>
> Am 20.04.2015 um 16:53 schrieb Tyler Hicks: 
> > On 2015-04-18 17:07:16, Richard Weinberger wrote: 
> >> Hi! 
> >> 
> >> Am 18.04.2015 um 16:58 schrieb Tom Marshall: 
> >>> On Sat, Apr 18, 2015 at 01:41:09PM +0200, Richard Weinberger wrote: 
> >>>> On Sat, Apr 18, 2015 at 12:20 AM, Tom Marshall <tom@cyngn.com> wrote: 
> >>>>> So, I wrote a thing called 'zfile' that hooks into the VFS layer and 
> >>>>> intercepts file_operations to do file (de)compression on the fly. When a 
> >>>>> file is opened, it reads and decompresses the data into memory.  The file 
> >>>>> may be read, written, and mmaped in the usual way.  If the contents are 
> >>>>> changed, the data is compressed and written back.  A working patch for an 
> >>>>> older kernel version may be found at: 
> >>>>> http://review.cyanogenmod.org/#/c/95220/ 
> >>>> 
> >>>> So, I've extracted the patch from that website and gave a quick review. 
> >>>> 
> >>>> I'm pretty sure VFS folks will hate the VFS layering you do. 
> >>> 
> >>> This, I'm afraid, is the biggest obstacle to such a solution.  I know that 
> >>> OverlayFS has been merged, so filesystem stacking is acceptable.  Perhaps 
> >>> there would be a way to design a filesystem that stacks compression? 
> >> 
> >> That's why I said think of adding compression support to ecryptfs. 
> > 
> > I think adding compression support to eCryptfs is the wrong approach. 
> > The "X is already a stacked filesystem so look into adding compression 
> > support to it" logic also works when X=overlayfs. I doubt that Miklos 
> > would be willing to accept such a feature. :) 
>
> My thought was that compression is not far away from crypto an hence 
> a lot of ecryptfs could be reused. 
>
> > A stacked filesystem that implements compression should be fairly 
> > simple. If it is not simple, it is too complicated to try to wedge into 
> > an unrelated stacked filesystem. 
> > 
> > While it may be the quickest route to your end goal, it will overly 
> > complicate eCryptfs. eCryptfs already has plenty of complexity around 
> > the file offset since metadata may be stored in the first 8192 bytes of 
> > the lower file, which offsets the entire file, and the end of the file 
> > has to be padded. Mixing in compression would make things much worse. 
>
> I assumed that you need also some meta data for compression. 
> At least if you do it in a non-trivial way. 
>
> > Also, eCryptfs has lots of cruft that is definitely not needed for 
> > compression. 
>
> As you're the maintainer of ecryptfs you know obviously better than I do. :) 
> Tom, to make the story short, you'll have to experiment a bit. 
>
> Thanks, 
> //richard