Feature request: Align compressed output of files on squashfs to device block size

[meeuw]

I have multiple large (8GB) squashfs images which are mostly similar and I would like to use reflinks (on XFS) to deduplicate the data.

Deduplication using reflinks is done using FICLONERANGE and "Disk filesystems generally require the offset and length arguments to be aligned to the fundamental block size".

To check this, I wrote the following Python script to calculate MD5 checksums of 4 kB blocks in two SquashFS images:

import hashlib
import sys
with open(sys.argv[1], 'rb') as f:
    while 1:
        buf = f.read(4096)
        if not buf: break
        print(hashlib.md5(buf).hexdigest())

I then compared the results (using sort | uniq -c | sort) to see how many blocks were identical between the two SquashFS images.

Unfortunately, I found that only a few blocks were duplicates, even though the contents of the images are mostly the same (as confirmed with a tool like rdiff).

My assumption is that mksquashfs does not align the compressed output of files to the device block size. As a result, duplicate data gets shifted relative to the block boundary, making the blocks slightly - or completely - different.

In my research, I came across a 4k-align.patch
(though I haven’t found an up-to-date version). I also noticed that gensquashfs supports an [align] option in its sort file.

What I wish mksquashfs had is an option to align files to a configurable block size, with the ability to set a minimum file size threshold. Something like:

-align MIN_SIZE,BLOCK_SIZE

-align 131072,4096
-align 0,4096

Would it be possible to add such an option to mksquashfs?

I’d be happy to create a pull request or patch for this - any hints or guidance would be greatly appreciated!

[meeuw]

I'm trying to understand the codebase and found the following:

The write position is managed through set_dpos, get_dpos and get_and_inc_dpos (in virt_disk_pos.h)

The dpos for data blocks seems to be handled in the orderer, which already does block alignment using SQUASHFS_COMPRESSED_SIZE_BLOCK with a SQUASHFS_COMPRESSED_BIT_BLOCK(SIZE) of 1<<24, a multiple of 4096 bytes.

Could it be that the start of the "data blocks & fragments" part is simply not aligned the same for different squashfs filesystems?

[plougher]

The write position is managed by the orderer in 4.7 and later, but, it doesn't do block alignment. The SQUASHFS_COMPRESSED_BIT (bit 24) indicates whether the block is compressed or not.

Rather than you puzzling this out over many hours and reimplemernting the wheel, I can implement what you want (to the extent it is supported by the filesystem layout) in a couple of hours using the existing functionality in Mksquashfs to do the specifying. In that way it will do what you want and more because it is using existing functionality rather than reimplementing the wheel.

There will be caveats because the Squashfs filesystem layout doesn't support full block alignment, and only in specific cases. So once I do the implementation, it will be up to you to specify things in a way that avoids the filesystem limitations if it is possible.

The alternative of explaining what you can do, and can't do with the filesystem layout, and how to leverage existing functionality to do it properly will take much more of my time than doing it myself.

So essentially time (that is my time) is the critical issue here. I have things which I'd rather be doing than this, and so I have to prioritize or rearrange priorities here.

[meeuw]

Thanks for your reply, very much appreciated!

It's good to know that this won't be an easy fix (for a beginner like me) and isn't a stupid bug which can be fixed.

I'm also glad to read that there's already some functionality for adding some support for this.

Don't worry too much about adding this feature, I already learned a lot about squashfs and reflinks. It's nice reading the source code of a pretty clean, highly optimized tool.

I hope it will be implemented once, for now I'll throw some more storage at it and see what I can do with a sort file (to prioritize files that are the same to the start of the squashfs).

What's still puzzling me is that even with a block size that is a multiple of 4096 (like the default of 131072 bytes), not more 4096-byte blocks match. I can imagine that the first and last block might mismatch (from misalignment), but the 30 in between should still match.

[plougher]

Thanks for your reply, very much appreciated!

It's good to know that this won't be an easy fix (for a beginner like me) and isn't a stupid bug which can be fixed.

I'm glad you didn't take my comments as a slight, because they were not meant in that way! I have now done the work, and it did require a fair amount of knowledge about the parallel threads and the action code.

I'm also glad to read that there's already some functionality for adding some support for this.

Yes, almost all the functionality was already there, and the additional code is very small.

Don't worry too much about adding this feature, I already learned a lot about squashfs and reflinks. It's nice reading the source code of a pretty clean, highly optimized tool.

Thank you for your compliment. It is unfortunately rare that people are that nice. In fact it is that which made me do the work, and curiosity.

I hope it will be implemented once, for now I'll throw some more storage at it and see what I can do with a sort file (to prioritize files that are the same to the start of the squashfs).

FYI the two commits that implement it are:

d6ab894

The perhaps difficult (or obscure) implementation aspect of that commit is that is is the responsibility of the reader thread to pass the alignment value through the pipeline of parallel threads via thefile buffer until it gets passed to the orderer thread which then uses the value. The reason for that is because the parallel threads deliberately only use the information passed to them via the file buffer, and don't look at external sources of information, because that would require locking/synchronisation of the external sources if they could be being modified by another thread in parallel. Putting all the information necessary in the file buffer eliminates that.

e4f8ca8

That commit adds an align() action to the Action language/subsystem in Mksquashfs.

The Actions language/subsystem has been there and documented since 2021 (Squashfs tools v4.5) but not a lot of people seem to know about it. This is is a pity because it is a fairly powerful language (modelled on the find command) which allows you to use a large amount of test operators on files and if the tests match perform an action.

In this case the new action is to align the matching file to the specified alignment. I gave a couple of examples in the commit message:

% mksquashfs dir dir.sqfs -action "align(4096)@true

This will align all files to a 4096 byte boundary. Here the test operator is true which is always true for any file.

% mksquashfs dir dir.sqfs -action "align(4K)@filesize(>=32K)"

This will align all files which are 32K or larger to a 4K boundary. Here the test operator is filesize(>=32K) which returns true for any file which is 32k or larger.

% mksquashfs dir dir.sqfs -action "align(4K)@perm(/a=x) && user(root)"

This is an example which shows the test operators operate on far more than just file sizes and test operators can be combined using the usual && (and) and || (or). In this case the test operator perm(/a=x) matches on any file which has the executable bit set and user(root) matches on files owned by root.

There has actually long been a use-case for this. In embedded systems for performance reasons they may want executables to be aligned and uncompressed. There has been an action to make the matching file uncompressed (not surprisingly called uncompressed()), but not one to make it aligned until now.

The link to the current Actions documentation is FYI here https://github.com/plougher/squashfs-tools/blob/master/Documentation/latest/ACTIONS-README

What's still puzzling me is that even with a block size that is a multiple of 4096 (like the default of 131072 bytes), not more 4096-byte blocks match. I can imagine that the first and last block might mismatch (from misalignment), but the 30 in between should still match.

I think I know the issue here. It is due to the default action of Mksquashfs to pack files into fragment blocks. Tomorrow (it is late here) I'll explain more.

If you use the new alignment functionality I believe you will get much better results. Any request to add an alignment to a file automatically disables fragment packing for that file.

[meeuw]

I'm speechless, I don't know how thank you! Especially for the explanation of your changes, this is gold!

The action subsystem is new for me and it does exactly what I want, can't wait to do some experiments with it to see what works best. I will report my findings here.

[meeuw]

I had to make some fixes to my scripts because mksquashfs got a lot more strict (which is nice!)

Some quick/first findings:

align(4K)@filesize(>=32K) only gives a 1.5% increase in file size for my 9GB squashfs file, but I now can deduplicate 7GB (!) of two squashfs files.