Hi there!
I am posting this series early in its development phase to solicit some
feedback.
We are implementing transparent decompression with a focus on ext4. One
of the main usecases is that of Firefox on Android. Currently libxul.so
is compressed and it is loaded into memory by a custom linker on
demand. With the use of transparent decompression, we can make do
without the custom linker. More details (i.e. code) about the linker can
be found at https://github.com/glandium/faulty.lib
Patch 1 introduces the seekable zip format to the kernel. The tool to
create the szip file can be found in the git repository mentioned
earlier. Patch 2 introduces transparent decompression to ext4. This
patch is really ugly, but it gives an idea of what I am upto right now.
Now let's move on the interesting bits.
There are a few flaws with the current approach (though most are easily
fixable)
1. The decompression takes place very late. We probably want to be
decompressing soon after get the data off disk.
2. No seek support. This is for simplicity as I was experimenting with
filesystems for the first time. I have a patch that does it, but it is
too ugly to see the world. I will fix it up in time for the next set.
3. No mmap support. For a similar reason as 1. There is no reason it
cannot be done, it just has not been done correctly.
4. stat still returns the compressed size. We need to modify
compressed files to return uncompressed size.
5. Implementation is tied to the szip format. However it is quite easy
to decouple the compression scheme from the filesystem. I will probably
get to that in another 2 rounds (first goal is to get seek support
working fine, and mmap in place)
6. Introduction of an additional file_operation to decompress the
buffer. This will be *removed* in the next posting once I have seek
support implemented properly.
7. The compressed file is read only. In order to write to the file, it
shall have to be replaced.
8. The kernel learns that the file is compressed with the use of the
chattr tool. For now I am abusing the +c flag. Please let me know if
that should not be used.
In order to try this patch out, please create an szip file using the
szip tool. Then, read the file. Just ensure that the buffer you provide
to the kernel is big enough to fit the uncompressed file (and that you
read the whole file in one go.)
Thanks!
Dhaval
--
Dhaval Giani (2):
szip: Add seekable zip format
Add rudimentary transparent decompression support to ext4
fs/ext4/file.c | 66 ++++++++++++++++
fs/read_write.c | 3 +
include/linux/fs.h | 1 +
include/linux/szip.h | 32 ++++++++
lib/Kconfig | 8 ++
lib/Makefile | 1 +
lib/szip.c | 217 +++++++++++++++++++++++++++++++++++++++++++++++++++
7 files changed, 328 insertions(+)
create mode 100644 include/linux/szip.h
create mode 100644 lib/szip.c
--
1.8.1.4
On Wed, 24 July 2013 17:03:53 -0400, Dhaval Giani wrote:
>
> I am posting this series early in its development phase to solicit some
> feedback.
At this state, a good description of the format would be nice.
> We are implementing transparent decompression with a focus on ext4. One
> of the main usecases is that of Firefox on Android. Currently libxul.so
> is compressed and it is loaded into memory by a custom linker on
> demand. With the use of transparent decompression, we can make do
> without the custom linker. More details (i.e. code) about the linker can
> be found at https://github.com/glandium/faulty.lib
It is not quite clear what you want to achieve here. One approach is
to create an empty file, chattr it to enable compression, then write
uncompressed data to it. Nothing in userspace will ever know the file
is compressed, unless you explicitly call lsattr.
If you want to follow some other approach where userspace has one
interface to write the compressed data to a file and some other
interface to read the file uncompressed, you are likely in a world of
pain.
Assuming you use the chattr approach, that pretty much comes down to
adding compression support to ext4. There have been old patches for
ext2 around that never got merged. Reading up on the problems
encountered by those patches might be instructive.
Jörn
--
I've never met a human being who would want to read 17,000 pages of
documentation, and if there was, I'd kill him to get him out of the
gene pool.
-- Joseph Costello
On 07/24/2013 07:36 PM, Jörn Engel wrote:
> On Wed, 24 July 2013 17:03:53 -0400, Dhaval Giani wrote:
>> I am posting this series early in its development phase to solicit some
>> feedback.
> At this state, a good description of the format would be nice.
Sure. The format is quite simple. There is a 20 byte header followed by
an offset table giving us the offsets of 16k compressed zlib chunks (The
16k is the default number, it can be changed with the use of szip tool,
the kernel should still decompress it as that data is in the header). I
am not tied to the format. I used it as that is what being used here. My
final goal is the have the filesystem agnostic of the compression format
as long as it is seekable.
>
>> We are implementing transparent decompression with a focus on ext4. One
>> of the main usecases is that of Firefox on Android. Currently libxul.so
>> is compressed and it is loaded into memory by a custom linker on
>> demand. With the use of transparent decompression, we can make do
>> without the custom linker. More details (i.e. code) about the linker can
>> be found at https://github.com/glandium/faulty.lib
> It is not quite clear what you want to achieve here.
To introduce transparent decompression. Let someone else do the
compression for us, and supply decompressed data on demand (in this
case a read call). Reduces the complexity which would otherwise have to
be brought into the filesystem.
> One approach is
> to create an empty file, chattr it to enable compression, then write
> uncompressed data to it. Nothing in userspace will ever know the file
> is compressed, unless you explicitly call lsattr.
>
> If you want to follow some other approach where userspace has one
> interface to write the compressed data to a file and some other
> interface to read the file uncompressed, you are likely in a world of
> pain.
Why? If it is going to only be a few applications who know the file is
compressed, and read it to get decompressed data, why would it be
painful? What about introducing a new flag, O_COMPR which tells the
kernel, btw, we want this file to be decompressed if it can be. It can
fallback to O_RDONLY or something like that? That gets rid of the chattr
ugliness.
> Assuming you use the chattr approach, that pretty much comes down to
> adding compression support to ext4. There have been old patches for
> ext2 around that never got merged. Reading up on the problems
> encountered by those patches might be instructive.
Do you have subjects for these? When I googled for ext4 compression, I
found http://code.google.com/p/e4z/ which doesn't seem to exist, and
checking in my LKML archives gives too many false positives.
Thanks!
Dhaval
On 25 July 2013 16:16, Dhaval Giani <[email protected]> wrote:
> On 07/24/2013 07:36 PM, J?rn Engel wrote:
>
>> Assuming you use the chattr approach, that pretty much comes down to
>> adding compression support to ext4. There have been old patches for
>> ext2 around that never got merged. Reading up on the problems
>> encountered by those patches might be instructive.
>
>
> Do you have subjects for these? When I googled for ext4 compression, I found
> http://code.google.com/p/e4z/ which doesn't seem to exist, and checking in
> my LKML archives gives too many false positives.
>
The ext2 compression project was called e2compr, http://e2compr.sourceforge.net/
Also just google for "e2compr".
Phillip
> Thanks!
> Dhaval
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
>
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
Dhaval Giani wrote:
> On 07/24/2013 07:36 PM, Jörn Engel wrote:
>> On Wed, 24 July 2013 17:03:53 -0400, Dhaval Giani wrote:
>>> I am posting this series early in its development phase to solicit some
>>> feedback.
>> At this state, a good description of the format would be nice.
>
> Sure. The format is quite simple. There is a 20 byte header followed
> by an offset table giving us the offsets of 16k compressed zlib chunks
> (The 16k is the default number, it can be changed with the use of szip
> tool, the kernel should still decompress it as that data is in the
> header). I am not tied to the format. I used it as that is what being
> used here. My final goal is the have the filesystem agnostic of the
> compression format as long as it is seekable.
>
>>
>>> We are implementing transparent decompression with a focus on ext4. One
>>> of the main usecases is that of Firefox on Android. Currently libxul.so
>>> is compressed and it is loaded into memory by a custom linker on
>>> demand. With the use of transparent decompression, we can make do
>>> without the custom linker. More details (i.e. code) about the linker
>>> can
>>> be found at https://github.com/glandium/faulty.lib
>> It is not quite clear what you want to achieve here.
>
> To introduce transparent decompression. Let someone else do the
> compression for us, and supply decompressed data on demand (in this
> case a read call). Reduces the complexity which would otherwise have
> to be brought into the filesystem.
The main use for file compression for Firefox(it's useful on Linux
desktop too) is to improve IO-throughput and reduce startup latency. In
order for compression to be a net win an application should be aware of
what is being compressed and what isn't. For example patterns for IO on
large libraries (eg 30mb libxul.so) are well suited to compression, but
SQLite databases are not. Similarly for our disk cache: images should
not be compressed, but javascript should be. Footprint wins are useful
on android, but it's the increased IO throughput on crappy storage
devices that makes this most attractive.
In addition of being aware of which files should be compressed, Firefox
is aware of patterns of usage of various files it could schedule
compression at the most optimal time.
Above needs tie in nicely with the simplification of not implementing
compression at fs-level.
>
>> One approach is
>> to create an empty file, chattr it to enable compression, then write
>> uncompressed data to it. Nothing in userspace will ever know the file
>> is compressed, unless you explicitly call lsattr.
>>
>> If you want to follow some other approach where userspace has one
>> interface to write the compressed data to a file and some other
>> interface to read the file uncompressed, you are likely in a world of
>> pain.
> Why? If it is going to only be a few applications who know the file is
> compressed, and read it to get decompressed data, why would it be
> painful? What about introducing a new flag, O_COMPR which tells the
> kernel, btw, we want this file to be decompressed if it can be. It can
> fallback to O_RDONLY or something like that? That gets rid of the
> chattr ugliness.
This transparent decompression idea is based on our experience with
HFS+. Apple uses the fs-attribute approach. OSX is able to compress
application libraries at installation-time, apps remain blissfully
unaware but get an extra boost in startup perf.
So in Linux, the package manager could compress .so files, textual data
files, etc.
>
>> Assuming you use the chattr approach, that pretty much comes down to
>> adding compression support to ext4. There have been old patches for
>> ext2 around that never got merged. Reading up on the problems
>> encountered by those patches might be instructive.
>
> Do you have subjects for these? When I googled for ext4 compression, I
> found http://code.google.com/p/e4z/ which doesn't seem to exist, and
> checking in my LKML archives gives too many false positives.
>
> Thanks!
> Dhaval
On Jul 25, 2013, at 8:42 PM, Taras Glek wrote:
[snip]
>>>
>>
>> To introduce transparent decompression. Let someone else do the compression for us, and supply decompressed data on demand (in this case a read call). Reduces the complexity which would otherwise have to be brought into the filesystem.
> The main use for file compression for Firefox(it's useful on Linux desktop too) is to improve IO-throughput and reduce startup latency. In order for compression to be a net win an application should be aware of what is being compressed and what isn't. For example patterns for IO on large libraries (eg 30mb libxul.so) are well suited to compression, but SQLite databases are not. Similarly for our disk cache: images should not be compressed, but javascript should be. Footprint wins are useful on android, but it's the increased IO throughput on crappy storage devices that makes this most attractive.
>
> In addition of being aware of which files should be compressed, Firefox is aware of patterns of usage of various files it could schedule compression at the most optimal time.
>
> Above needs tie in nicely with the simplification of not implementing compression at fs-level.
There are many filesystems that uses compression as internal technique. And, as I understand, implementation
of compression in different Linux kernel filesystem drivers has similar code patterns. So, from my point of view,
it makes sense to generalize compression/decompression code in the form of library. The API of such generalized
compression kernel library can be used in drivers of different file systems. Also such generalized compression
library will simplify support of compression in file system drivers that don't support compression feature currently.
Moreover, I think that it is possible to implement compression support on VFS level. Such feature gives
opportunity to have compression support for filesystems that don't support compression feature as
internal technique.
[snip]
>>
> This transparent decompression idea is based on our experience with HFS+. Apple uses the fs-attribute approach. OSX is able to compress application libraries at installation-time, apps remain blissfully unaware but get an extra boost in startup perf.
>
HFS+ supports compression as internal filesystem technique. It means that HFS+ volume layout has
metadata structures for compression support (compressed xattrs or compressed resource forks).
So, compression is supported on FS level. As I know, Mac OS X has native decompression support
for compressed files but you need to use special tool for compression of files on HFS+. Maybe
Mac OS X has internal library that give opportunity to compress application libraries at installation
time. But I suppose that it is simply user-space tool or library that uses HFS+ compression support
on kernel-space and volume layout levels.
With the best regards,
Vyacheslav Dubeyko.
On 2013-07-25 2:15 PM, Vyacheslav Dubeyko wrote:
> On Jul 25, 2013, at 8:42 PM, Taras Glek wrote:
>
> [snip]
>>> To introduce transparent decompression. Let someone else do the compression for us, and supply decompressed data on demand (in this case a read call). Reduces the complexity which would otherwise have to be brought into the filesystem.
>> The main use for file compression for Firefox(it's useful on Linux desktop too) is to improve IO-throughput and reduce startup latency. In order for compression to be a net win an application should be aware of what is being compressed and what isn't. For example patterns for IO on large libraries (eg 30mb libxul.so) are well suited to compression, but SQLite databases are not. Similarly for our disk cache: images should not be compressed, but javascript should be. Footprint wins are useful on android, but it's the increased IO throughput on crappy storage devices that makes this most attractive.
>>
>> In addition of being aware of which files should be compressed, Firefox is aware of patterns of usage of various files it could schedule compression at the most optimal time.
>>
>> Above needs tie in nicely with the simplification of not implementing compression at fs-level.
> There are many filesystems that uses compression as internal technique. And, as I understand, implementation
> of compression in different Linux kernel filesystem drivers has similar code patterns. So, from my point of view,
> it makes sense to generalize compression/decompression code in the form of library. The API of such generalized
> compression kernel library can be used in drivers of different file systems. Also such generalized compression
> library will simplify support of compression in file system drivers that don't support compression feature currently.
>
> Moreover, I think that it is possible to implement compression support on VFS level. Such feature gives
> opportunity to have compression support for filesystems that don't support compression feature as
> internal technique.
I am not sure it is a very good idea at this stage.
> [snip]
>> This transparent decompression idea is based on our experience with HFS+. Apple uses the fs-attribute approach. OSX is able to compress application libraries at installation-time, apps remain blissfully unaware but get an extra boost in startup perf.
>>
> HFS+ supports compression as internal filesystem technique. It means that HFS+ volume layout has
> metadata structures for compression support (compressed xattrs or compressed resource forks).
> So, compression is supported on FS level. As I know, Mac OS X has native decompression support
> for compressed files but you need to use special tool for compression of files on HFS+. Maybe
> Mac OS X has internal library that give opportunity to compress application libraries at installation
> time. But I suppose that it is simply user-space tool or library that uses HFS+ compression support
> on kernel-space and volume layout levels.
In addition to what Taras mentioned, there is a similar approach being
followed here. There is a compression tool to compress files at
https://github.com/glandium/faulty.lib/blob/master/linker/szip.cpp .
On Thu, 25 July 2013 09:42:18 -0700, Taras Glek wrote:
> Footprint wins are useful on android, but it's the
> increased IO throughput on crappy storage devices that makes this
> most attractive.
All the world used to be a PC. Seems to be Android these days.
The biggest problem with compression support in the past was the
physical properties of hard drives (the spinning type, if you can
still remember those). A random seek is surprisingly expensive, of a
similar cost to 1MB or more of linear read. So anything that
introduces more random seeks will kill the preciously little
performance you had to begin with.
As long as files are write-once and read-only from that point on, you
can just append a bunch of compressed chunks on the disk and nothing
bad happens. But if you have a read-write file with random overwrites
somewhere in the middle, those overwrites will change the size of the
compressed data. You have to free the old physical blocks on disk and
allocate new ones. In effect, you have auto-fragmentation.
So if you want any kind of support for your approach, I suspect you
should either limit it to write-once files or prepare for a mob of
gray-haired oldtimers with rainbow suspenders complaining about
performance on their antiquated hardware. And the mob may be larger
than you think.
Jörn
--
Don't worry about people stealing your ideas. If your ideas are any good,
you'll have to ram them down people's throats.
-- Howard Aiken quoted by Ken Iverson quoted by Jim Horning quoted by
Raph Levien, 1979
On 2013-07-25 1:53 PM, Jörn Engel wrote:
> On Thu, 25 July 2013 09:42:18 -0700, Taras Glek wrote:
>> Footprint wins are useful on android, but it's the
>> increased IO throughput on crappy storage devices that makes this
>> most attractive.
> All the world used to be a PC. Seems to be Android these days.
>
> The biggest problem with compression support in the past was the
> physical properties of hard drives (the spinning type, if you can
> still remember those). A random seek is surprisingly expensive, of a
> similar cost to 1MB or more of linear read. So anything that
> introduces more random seeks will kill the preciously little
> performance you had to begin with.
>
> As long as files are write-once and read-only from that point on, you
> can just append a bunch of compressed chunks on the disk and nothing
> bad happens. But if you have a read-write file with random overwrites
> somewhere in the middle, those overwrites will change the size of the
> compressed data. You have to free the old physical blocks on disk and
> allocate new ones. In effect, you have auto-fragmentation.
>
> So if you want any kind of support for your approach, I suspect you
> should either limit it to write-once files or prepare for a mob of
> gray-haired oldtimers with rainbow suspenders complaining about
> performance on their antiquated hardware. And the mob may be larger
> than you think.
Yes, we plan to limit it to write-once. In order to write, you have to
replace the file.
Dhaval
On Thu, 25 July 2013 11:16:06 -0400, Dhaval Giani wrote:
> >
> >If you want to follow some other approach where userspace has one
> >interface to write the compressed data to a file and some other
> >interface to read the file uncompressed, you are likely in a world of
> >pain.
> Why? If it is going to only be a few applications who know the file
> is compressed, and read it to get decompressed data, why would it be
> painful?
It would likely require an ABI extention. Your immediate pain would
be to get past a wall of NAK when you propose the extention. You have
to make a rather convincing case that the ABI extention cannot cause
VFS or filesystem maintainers future pain in some dark cornercase.
Just because the one application you care about only wants to use
compression on write-once files doesn't prevent the next person from
abusing the new ABI. Such abuse should be strictly limited,
preferrably impossible.
I am not saying that I object. Just warning you to brace yourself for
impact.
> What about introducing a new flag, O_COMPR which tells the
> kernel, btw, we want this file to be decompressed if it can be. It
> can fallback to O_RDONLY or something like that? That gets rid of
> the chattr ugliness.
How is that different from chattr ugliness, which also comes down to a
single flag? ;)
Jörn
--
/* Keep these two variables together */
int bar;
> > What about introducing a new flag, O_COMPR which tells the
> > kernel, btw, we want this file to be decompressed if it can be. It
> > can fallback to O_RDONLY or something like that? That gets rid of
> > the chattr ugliness.
>
> How is that different from chattr ugliness, which also comes down to a
> single flag? ;)
It's much worse because it's per fd instead of per inode.
The page cache, where the undisclosed complexity of this proposal lurks,
where compressed and uncompressed cached copies of the data need to be
managed somehow, is per inode.
- z
(Hi Taras! :))
On Thu, 25 July 2013 13:09:39 -0700, Zach Brown wrote:
>
> > > What about introducing a new flag, O_COMPR which tells the
> > > kernel, btw, we want this file to be decompressed if it can be. It
> > > can fallback to O_RDONLY or something like that? That gets rid of
> > > the chattr ugliness.
> >
> > How is that different from chattr ugliness, which also comes down to a
> > single flag? ;)
>
> It's much worse because it's per fd instead of per inode.
>
> The page cache, where the undisclosed complexity of this proposal lurks,
> where compressed and uncompressed cached copies of the data need to be
> managed somehow, is per inode.
You've been giving it away! Bad Zach, no cookies tonight.
Jörn
--
With a PC, I always felt limited by the software available. On Unix,
I am limited only by my knowledge.
-- Peter J. Schoenster
On Thu, 2013-07-25 at 11:16 -0700, Taras Glek wrote:
>
>
> Vyacheslav Dubeyko wrote:
> > On Jul 25, 2013, at 8:42 PM, Taras Glek wrote:
> >
> > [snip]
> > > > To introduce transparent decompression. Let someone else do the compression for us, and supply decompressed data on demand (in this case a read call). Reduces the complexity which would otherwise have to be brought into the filesystem.
> > > The main use for file compression for Firefox(it's useful on Linux desktop too) is to improve IO-throughput and reduce startup latency. In order for compression to be a net win an application should be aware of what is being compressed and what isn't. For example patterns for IO on large libraries (eg 30mb libxul.so) are well suited to compression, but SQLite databases are not. Similarly for our disk cache: images should not be compressed, but javascript should be. Footprint wins are useful on android, but it's the increased IO throughput on crappy storage devices that makes this most attractive.
> > >
> > > In addition of being aware of which files should be compressed, Firefox is aware of patterns of usage of various files it could schedule compression at the most optimal time.
> > >
> > > Above needs tie in nicely with the simplification of not implementing compression at fs-level.
> >
> > There are many filesystems that uses compression as internal technique. And, as I understand, implementation
> > of compression in different Linux kernel filesystem drivers has similar code patterns. So, from my point of view,
> > it makes sense to generalize compression/decompression code in the form of library. The API of such generalized
> > compression kernel library can be used in drivers of different file systems. Also such generalized compression
> > library will simplify support of compression in file system drivers that don't support compression feature currently.
> >
> > Moreover, I think that it is possible to implement compression support on VFS level. Such feature gives
> > opportunity to have compression support for filesystems that don't support compression feature as
> > internal technique.
> >From my conversations with Ted, it sounded like it was easier to
> accomplish changes like this at fs level than vfs. Maybe things are
> different now
If I understand the idea correctly, you want to have file-oriented
compression. I mean that you want to have one type of files are
compressed but another type of ones should be not compressed. So, from
my understanding, a file is not ext4 specific concept. Every filesystem
contains files. So, if you intend to implement compression support in
ext4 then you need to use e2compr as basis for full-featured compression
in ext4. But if you want to have something like file-oriented
compression then it is not feature of concrete filesystem. Do you mean
that Firefox will work only on ext4? So, it means for me that feature
likewise file-oriented compression should be on VFS level or over VFS.
And I am not fully confident that it should be a feature in
kernel-space.
> >
> > [snip]
> > > This transparent decompression idea is based on our experience with HFS+. Apple uses the fs-attribute approach. OSX is able to compress application libraries at installation-time, apps remain blissfully unaware but get an extra boost in startup perf.
> > >
> >
> > HFS+ supports compression as internal filesystem technique. It means that HFS+ volume layout has
> > metadata structures for compression support (compressed xattrs or compressed resource forks).
> > So, compression is supported on FS level. As I know, Mac OS X has native decompression support
> > for compressed files but you need to use special tool for compression of files on HFS+. Maybe
> > Mac OS X has internal library that give opportunity to compress application libraries at installation
> > time. But I suppose that it is simply user-space tool or library that uses HFS+ compression support
> > on kernel-space and volume layout levels.
> OSX compression is done in userspace, all heuristics are done in
> userspace. https://github.com/jrk/afsctool/blob/master/afsctool.c#L87
> Rest of the details are there too.
Anyway, HFS+ keeps compressed files' content in com.apple.decmpfs xattr
or in resource fork. It means for me that HFS+ volume layout has special
metadata structures for compression support. Because if you will try to
work with HFS+ compressed file under Linux then you will see file with
zero byte in size. And, moreover, Mac OS X filesystem driver should know
about these metadata structures. Otherwise, it cannot process HFS+
compressed files. We can discuss about HFS+ compression in more details
but I think that it is not key topic for this patch set.
With the best regards,
Vyacheslav Dubeyko.
> Taras
> >
> > With the best regards,
> > Vyacheslav Dubeyko.
> >
On Thu, 2013-07-25 at 14:35 -0400, Dhaval Giani wrote:
> On 2013-07-25 2:15 PM, Vyacheslav Dubeyko wrote:
> > On Jul 25, 2013, at 8:42 PM, Taras Glek wrote:
> >
> > [snip]
> >>> To introduce transparent decompression. Let someone else do the compression for us, and supply decompressed data on demand (in this case a read call). Reduces the complexity which would otherwise have to be brought into the filesystem.
> >> The main use for file compression for Firefox(it's useful on Linux desktop too) is to improve IO-throughput and reduce startup latency. In order for compression to be a net win an application should be aware of what is being compressed and what isn't. For example patterns for IO on large libraries (eg 30mb libxul.so) are well suited to compression, but SQLite databases are not. Similarly for our disk cache: images should not be compressed, but javascript should be. Footprint wins are useful on android, but it's the increased IO throughput on crappy storage devices that makes this most attractive.
> >>
> >> In addition of being aware of which files should be compressed, Firefox is aware of patterns of usage of various files it could schedule compression at the most optimal time.
> >>
> >> Above needs tie in nicely with the simplification of not implementing compression at fs-level.
> > There are many filesystems that uses compression as internal technique. And, as I understand, implementation
> > of compression in different Linux kernel filesystem drivers has similar code patterns. So, from my point of view,
> > it makes sense to generalize compression/decompression code in the form of library. The API of such generalized
> > compression kernel library can be used in drivers of different file systems. Also such generalized compression
> > library will simplify support of compression in file system drivers that don't support compression feature currently.
> >
> > Moreover, I think that it is possible to implement compression support on VFS level. Such feature gives
> > opportunity to have compression support for filesystems that don't support compression feature as
> > internal technique.
>
> I am not sure it is a very good idea at this stage.
We are discussing not about good or bad idea. We need to elaborate a
right solution. I think that suggested idea is not clear. Do you want to
support compression in ext4? Or do you want to add some new compression
feature (likewise file-oriented compression)? If we are talking about
compression in ext4 then it needs to use e2compr patch set. Otherwise,
if we are talking about file compression then it is not question of
concrete filesystem. And we need to make implementation on VFS level. It
is only architectural point of view.
> > [snip]
> >> This transparent decompression idea is based on our experience with HFS+. Apple uses the fs-attribute approach. OSX is able to compress application libraries at installation-time, apps remain blissfully unaware but get an extra boost in startup perf.
> >>
> > HFS+ supports compression as internal filesystem technique. It means that HFS+ volume layout has
> > metadata structures for compression support (compressed xattrs or compressed resource forks).
> > So, compression is supported on FS level. As I know, Mac OS X has native decompression support
> > for compressed files but you need to use special tool for compression of files on HFS+. Maybe
> > Mac OS X has internal library that give opportunity to compress application libraries at installation
> > time. But I suppose that it is simply user-space tool or library that uses HFS+ compression support
> > on kernel-space and volume layout levels.
> In addition to what Taras mentioned, there is a similar approach being
> followed here. There is a compression tool to compress files at
> https://github.com/glandium/faulty.lib/blob/master/linker/szip.cpp .
>
Why do you try to implement likewise concept on kernel level? It looks
like you try to move some user-space concept in kernel-space.
With the best regards,
Vyacheslav Dubeyko.
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, 26 July 2013 12:01:23 +0400, Vyacheslav Dubeyko wrote:
>
> We are discussing not about good or bad idea. We need to elaborate a
> right solution. I think that suggested idea is not clear. Do you want to
> support compression in ext4? Or do you want to add some new compression
> feature (likewise file-oriented compression)? If we are talking about
> compression in ext4 then it needs to use e2compr patch set. Otherwise,
> if we are talking about file compression then it is not question of
> concrete filesystem. And we need to make implementation on VFS level. It
> is only architectural point of view.
I don't think the e2compr patches are strictly necessary. They are a
good option, but not the only one.
One trick to simplify the problem is to make Dhaval's compressed files
strictly read-only. It will require some dance to load the compressed
content, flip the switch, then uncompress data on the fly and disallow
writes. Not the most pleasing of interfaces, but yet another option.
> Why do you try to implement likewise concept on kernel level? It looks
> like you try to move some user-space concept in kernel-space.
The kernel controls the page cache. Once the page cache is filled
with uncompressed file content, you can do mmap, regular file io, etc.
Putting uncompression code into the kernel makes sense to me. Whether
a solution different from e2compr makes sense is yet to be seen.
Whatever you do, it will require support from the on-disk format and
the userspace ABI. Setting the compression bit on a file has the
clear advantage that it is an established interface and also supported
by other filesystems. Introducing yet another interface requires a
fairly strong case to be made. But who knows, maybe Dhaval can pull
it off.
Jörn
--
Measuring programming progress by lines of code is like measuring aircraft
building progress by weight.
-- Bill Gates
On Fri, Jul 26, 2013 at 09:20:34AM -0400, J?rn Engel wrote:
> On Fri, 26 July 2013 12:01:23 +0400, Vyacheslav Dubeyko wrote:
> >
> > We are discussing not about good or bad idea. We need to elaborate a
> > right solution. I think that suggested idea is not clear. Do you
> > want to support compression in ext4? Or do you want to add some new
> > compression feature (likewise file-oriented compression)? If we are
> > talking about compression in ext4 then it needs to use e2compr patch
> > set. Otherwise, if we are talking about file compression then it is
> > not question of concrete filesystem. And we need to make
> > implementation on VFS level. It is only architectural point of view.
>
> I don't think the e2compr patches are strictly necessary. They are a
> good option, but not the only one.
>
> One trick to simplify the problem is to make Dhaval's compressed files
> strictly read-only. It will require some dance to load the compressed
> content, flip the switch, then uncompress data on the fly and disallow
> writes. Not the most pleasing of interfaces, but yet another option.
>
> > Why do you try to implement likewise concept on kernel level? It
> > looks like you try to move some user-space concept in kernel-space.
>
> The kernel controls the page cache. Once the page cache is filled
> with uncompressed file content, you can do mmap, regular file io, etc.
> Putting uncompression code into the kernel makes sense to me. Whether
> a solution different from e2compr makes sense is yet to be seen.
>
> Whatever you do, it will require support from the on-disk format and
> the userspace ABI. Setting the compression bit on a file has the
> clear advantage that it is an established interface and also supported
> by other filesystems. Introducing yet another interface requires a
> fairly strong case to be made. But who knows, maybe Dhaval can pull
> it off.
Come to think of it, the whole thing could be handled entirely in user
space through fuse. While this is probably a workable solution on
desktop/server environments, it doesn't pan out on Android: /dev/fuse is
rarely available, and even if it were, fusermount needs to be there and
be a setuid program (or have the right capabilities). So, another angle
could be to allow some things to happen without privileges, such as
mounting filesystems in a private namespace. That wouldn't solve the
lack of /dev/fuse, though.
Mike
On Fri, Jul 26, 2013 at 09:20:34AM -0400, J?rn Engel wrote:
>
> I don't think the e2compr patches are strictly necessary. They are a
> good option, but not the only one.
Sorry for not chiming in earlier; I've been travelling this past week,
and between that and a bunch of other things I've fallen a bit earlier
on my e-mail.
> One trick to simplify the problem is to make Dhaval's compressed files
> strictly read-only. It will require some dance to load the compressed
> content, flip the switch, then uncompress data on the fly and disallow
> writes. Not the most pleasing of interfaces, but yet another option.
Yeah, this is something that I've wanted for a while. (In fact a few
years ago I shopped around this design to some folks who were
associated with Firefox.) MacOS has something rather similar to this.
I haven't had a chance to look at Dhaval's patches yet, but the way
I've been thinking about this is that the compression and building the
table mapping compressed clusters to byte offsets in the file would be
done in userspace. Once the compressed file plus the table is written
to the disk, the userspace program would then close the file
descriptor, and then set the "compressed" bit.
When the bit is set, we flush all of its pages from the page cache,
and the file becomes immutable. At that point, the kernel will handle
the decompression, by implementing readpages() by reading the pages
into the buffer cache, and then decompressing the compressed cluster
of pages into the page cache. This gives us transparent compression,
with a fraction of the complexity of supporting read/write
compression. In addition, since we don't have to worry rewriting a
cluster (and having the modified compressed cluster taking up more
space), the on-disk representation can be a lot more efficient, since
you don't have to use a stacker-style design.
One of the cool things about this design is that the vast majority of
files on a typical distribution are write-once, and better yet, they
are written by the package manager. So once you teach dpkg, rpm, and
the Android package installer how to write the file in this compressed
format and set the compressed bit, we can the vast majority of the
benefits of using compressed file with minimal effort.
- Ted
P.S. This is interesting not just for systems with slow HDD's, but
also for cheap, single-channel MMC flash, the kind found in low-end
handset and embedded systems.
P.P.S. At least in theory, nothing of what I've described here has to
be ext4 specific. We could implement this in the VFS layer, at which
point not only ext4 would benefit, but also btrfs, xfs, f2fs, etc.
On Sat, 3 August 2013 20:33:16 -0400, Theodore Ts'o wrote:
>
> P.P.S. At least in theory, nothing of what I've described here has to
> be ext4 specific. We could implement this in the VFS layer, at which
> point not only ext4 would benefit, but also btrfs, xfs, f2fs, etc.
Except for an inode bit that needs to be stored in the filesystem,
agreed. The ugliness I see is in detecting how to treat the
filesystem at hand.
Filesystems with mandatory compression (jffs2, ubifs,...):
- Just write the file, nothing to do.
Filesystems with optional compression (logfs, ext2compr,...):
- You may or may not want to chattr between file creation and writing
the payload.
Filesystems without compression (ext[234], xfs,...):
- Just write the file, nothing can be done.
- Alternatively fall back to a userspace version.
Filesystems with optional uncompression (what is being proposed):
- Write the file in compressed form, close, chattr.
I would like to see the compression side done in the kernel as well.
Then we can chattr right after creat() and, if that fails, either
proceed anyway or go to a userspace fallback. All decisions can be
made early on and we don't have to share the format with lots of
userspace.
Sure, we still have to share the format with fsck and similar
filesystem tools. But not with installers.
Jörn
--
Man darf nicht das, was uns unwahrscheinlich und unnatürlich erscheint,
mit dem verwechseln, was absolut unmöglich ist.
-- Carl Friedrich Gauß
On Sat, Aug 03, 2013 at 10:21:14PM -0400, J?rn Engel wrote:
> On Sat, 3 August 2013 20:33:16 -0400, Theodore Ts'o wrote:
> >
> > P.P.S. At least in theory, nothing of what I've described here has to
> > be ext4 specific. We could implement this in the VFS layer, at which
> > point not only ext4 would benefit, but also btrfs, xfs, f2fs, etc.
>
> Except for an inode bit that needs to be stored in the filesystem,
> agreed. The ugliness I see is in detecting how to treat the
> filesystem at hand.
>
> Filesystems with mandatory compression (jffs2, ubifs,...):
> - Just write the file, nothing to do.
> Filesystems with optional compression (logfs, ext2compr,...):
> - You may or may not want to chattr between file creation and writing
> the payload.
> Filesystems without compression (ext[234], xfs,...):
> - Just write the file, nothing can be done.
> - Alternatively fall back to a userspace version.
> Filesystems with optional uncompression (what is being proposed):
> - Write the file in compressed form, close, chattr.
There's way more than that on the filesystem specific side. For
example, if we have to store a special flag to say it's a compressed
file, then we have to be able to validate that flag is correctly set
when doing filesystem checks (i.e. e2fsck, xfs_repair, etc), and
probably also validate that the *data is in a decodable format*.
That is, if the data is not in a compressed state and the flag is
set, then that's a filesystem corruption. It might be metadata
corruption, it might be data corruption, but either way it is
something that we need to be able verify as being correctly set.
So, we need support for this new format in all the filesystem
userspace tools as well.
> I would like to see the compression side done in the kernel as well.
> Then we can chattr right after creat() and, if that fails, either
> proceed anyway or go to a userspace fallback. All decisions can be
> made early on and we don't have to share the format with lots of
> userspace.
>
> Sure, we still have to share the format with fsck and similar
> filesystem tools. But not with installers.
Yup, you are effectively saying that the compression format becomes
a fixed on-disk format defined by the VFS and that all filesystems
have to be able to support in their userspace tools. That's *lots*
of code that will need to share with, and so now you're talking
about needing a library to match the kernel implementation. How do
you propose shipping that so that userspace tools can keep up with
the kernels that ship?
Indeed, how are we going to test it? This is absolutely going to
require xfstests support, which means we'll need an independent
method of doing compression and decompression so we can validate
that the kernel code is doing the right thing (e.g. xfs_io support).
We'll need data validation tests, tests that validate mmap and
direct IO behaviour, data corruption and fsck tests, seek tests,
etc.
Then we'll need man pages, documentation in the kernel code about
the compression format, etc.
The kernel compression/decompression code is the *easy bit*, and
only about 10% of the work needed to bring this functionality in
robust manner to the VFS....
And, like all compression formats in the kernel, they last about 3
months before someone comes up with some fancy new one that is 1%
faster or smaller at something, and we end up with a proliferation
of different supported compression formats. What's the plan to stop
this insanity from occurring for such a VFS provided compression
format?
Cheers,
Dave.
--
Dave Chinner
[email protected]
On 2013-08-04, at 5:48 PM, Dave Chinner wrote:
> On Sat, Aug 03, 2013 at 10:21:14PM -0400, J?rn Engel wrote:
>> On Sat, 3 August 2013 20:33:16 -0400, Theodore Ts'o wrote:
>>>
>>> P.P.S. At least in theory, nothing of what I've described here has to be ext4 specific. We could implement this in the VFS
>>> layer, at which point not only ext4 would benefit, but also btrfs, xfs, f2fs, etc.
>>
>> Except for an inode bit that needs to be stored in the filesystem,
>> agreed. The ugliness I see is in detecting how to treat the
>> filesystem at hand.
>>
>> Filesystems with mandatory compression (jffs2, ubifs,...):
>> - Just write the file, nothing to do.
>> Filesystems with optional compression (logfs, ext2compr,...):
>> - You may or may not want to chattr between file creation and writing
>> the payload.
>> Filesystems without compression (ext[234], xfs,...):
>> - Just write the file, nothing can be done.
>> - Alternatively fall back to a userspace version.
>> Filesystems with optional uncompression (what is being proposed):
>> - Write the file in compressed form, close, chattr.
>
> There's way more than that on the filesystem specific side. For
> example, if we have to store a special flag to say it's a compressed
> file, then we have to be able to validate that flag is correctly set
> when doing filesystem checks (i.e. e2fsck, xfs_repair, etc), and
> probably also validate that the *data is in a decodable format*.
>
> That is, if the data is not in a compressed state and the flag is
> set, then that's a filesystem corruption. It might be metadata
> corruption, it might be data corruption, but either way it is
> something that we need to be able verify as being correctly set.
I don't see how this _has_ to exist for any of the userspace tools.
If the file is corrupt (i.e. cannot be decompressed), then that is
no different than if the file is corrupt and it is a regular file.
e2fsck doesn't detect file content corruption, and AFAIK neither
does xfs_repair. Why is the bar raised just because there is a
flag that reports the file is in compressed format?
> So, we need support for this new format in all the filesystem
> userspace tools as well.
I'm not saying that a tool to check this would be a bad thing, but
if the compression support is a generic feature of the VFS, then it
makes sense that the checker can also be generic and unrelated to
the filesystem metadata checking as well. It may be "gunzip -t"
or LZO equivalent is enough to determine if the file is/isn't in a
valid state, and if not then the flag can be cleared from userspace
in the same way it was set (presumably chattr is enough).
Possibly a per-file hook could be added to the fsck tools to run an
arbitrary data verification command? That would be generically
useful for all kinds of things and not just this compression code.
>> I would like to see the compression side done in the kernel as well.
>> Then we can chattr right after creat() and, if that fails, either
>> proceed anyway or go to a userspace fallback. All decisions can be
>> made early on and we don't have to share the format with lots of
>> userspace.
>>
>> Sure, we still have to share the format with fsck and similar
>> filesystem tools. But not with installers.
>
> Yup, you are effectively saying that the compression format becomes
> a fixed on-disk format defined by the VFS and that all filesystems
> have to be able to support in their userspace tools. That's *lots*
> of code that will need to share with, and so now you're talking
> about needing a library to match the kernel implementation. How do
> you propose shipping that so that userspace tools can keep up with
> the kernels that ship?
Presumably if the userspace checking is independent of the fsck tool
this would be much less of a burden. As you write below, we'd also
want to avoid flavour-of-the-month for compression formats, to keep
the ongoing burden down.
> Indeed, how are we going to test it? This is absolutely going to
> require xfstests support, which means we'll need an independent
> method of doing compression and decompression so we can validate
> that the kernel code is doing the right thing (e.g. xfs_io support).
> We'll need data validation tests, tests that validate mmap and
> direct IO behaviour, data corruption and fsck tests, seek tests,
> etc.
The testing is definitely needed in order for this to become robust.
I'm not sure if any of this is filesystem-specific. It might even
be possible to change things minimally to generate all files in
compressed mode when running some other test (e.g. LD_PRELOAD hook
on close() that compresses the file and sets the flag if it isn't
already set)?
> Then we'll need man pages, documentation in the kernel code about
> the compression format, etc.
>
> The kernel compression/decompression code is the *easy bit*, and
> only about 10% of the work needed to bring this functionality in
> robust manner to the VFS....
Sure, but it all has to start somewhere...
> And, like all compression formats in the kernel, they last about 3
> months before someone comes up with some fancy new one that is 1%
> faster or smaller at something, and we end up with a proliferation
> of different supported compression formats. What's the plan to stop
> this insanity from occurring for such a VFS provided compression
> format?
Definitely agree with this part.
Cheers, Andreas
On Wed, 7 August 2013 03:21:47 -0600, Andreas Dilger wrote:
>
> I'm not saying that a tool to check this would be a bad thing, but
> if the compression support is a generic feature of the VFS, then it
> makes sense that the checker can also be generic and unrelated to
> the filesystem metadata checking as well. It may be "gunzip -t"
> or LZO equivalent is enough to determine if the file is/isn't in a
Careful! If you have a 1GB file in gzip format and want to
demand-page the last page from it, you have to gunzip the _entire_
file before you can uncompress that page. There is no alternative to
splitting the file into chunks of some reasonable size and therefore
"gunzip -t" will never be enough.
That also means that data corruption has more impact here than it
would have for an uncompressed file. Instead of handing the corrupted
data to userspace and let it deal with the results, the kernel has to
interpret some header, some list of chunks and finally the compression
format. Any bugs here will lead to crashes or privilege escalations
that we are responsible for. We cannot just say "garbage in, garbage
out, let userspace handle it".
Do we return zero-filled pages in case of data corruption? Or should
we return -EIO on reads and segfault on access of mmap'ed pages? Or
does the filesystem really own the metadata, which in this case
includes the header and chunk list and potentially some bits of the
compression format, and adds checksums, etc. to said metadata?
Jörn
--
Somewhere around the year 2000 there was this turningpoint when it
became cheaper to collect information than to understand it.
-- Freeman Dyson