makefs: Calculate indirect block count properly for large files on ffs

[lytboris_gmail.com]

Summary

When building an ffs image with large image in it, space requirements are calculated incorrectly yielding a bigger image than it could be.
The reason is that amount of indirect blocks estimation is done wrong:

• a single indirect block is treated as it can hold just 12 data blocks
• nested indirect blocks are not taken into account at all

Patch attached introduces support for indirect blocks and fixes another tiny bug with underestimated space requirement for files with size between (UFS_NDADDR-1)*blksz+fragsz ... (UFS_NDADDR)*blksz requesting a N>1 fragments instead of a whole block.

Test Plan

makefs -d 0xffff -B little -o minfree=0,optimization=space,bsize=65536,fsize=8192 imgfile /path/to/dir/with/large/files
makefs -d 0xffff -B little -o minfree=0,optimization=space imgfile /path/to/dir/with/large/files

It should yield something similar to:

ADDDIRENT: was: rtr.zfs-dump.xz (41) this 52 cur 24
ADDDIRENT: now: rtr.zfs-dump.xz (41) this 52 cur 76
ffs_size_dir: `rtr.zfs-dump.xz' size 525676312
ffs_size_dir: size 525676312, using 2 levels of indirect blocks, overhead 64 blocks
ADDDIRENT: was: rtr.zfs-dump.xz.sha256 (48) this 60 cur 76
ADDDIRENT: now: rtr.zfs-dump.xz.sha256 (48) this 60 cur 136
ffs_size_dir: `rtr.zfs-dump.xz.sha256' size 65
ADDDIRENT: was: boot (4) this 16 cur 136
ADDDIRENT: now: boot (4) this 16 cur 152
ffs_size_dir: `boot' size 512
ffs_size_dir: entry: bytes 527732736 inodes 3
...
ADDDIRENT: was: kernel.gz (9) this 20 cur 48
ADDDIRENT: now: kernel.gz (9) this 20 cur 68
ffs_size_dir: `kernel.gz' size 11349916
ffs_size_dir: size 11349916, using 2 levels of indirect blocks, overhead 3 blocks
...
ADDDIRENT: was: loader (6) this 16 cur 96
ADDDIRENT: now: loader (6) this 16 cur 112
ffs_size_dir: `loader' size 475136
ffs_size_dir: size 475136, using 1 levels of indirect blocks, overhead 1 blocks
ADDDIRENT: was: loader.conf (11) this 20 cur 112
ADDDIRENT: now: loader.conf (11) this 20 cur 132
ffs_size_dir: `loader.conf' size 1347
ffs_size_dir: exit: size 540651520 inodes 40
ADDDIRENT: was: boot.config (11) this 20 cur 152
ADDDIRENT: now: boot.config (11) this 20 cur 172
ffs_size_dir: `boot.config' size 3
ADDDIRENT: was: mfsroot.gz (10) this 20 cur 172
ADDDIRENT: now: mfsroot.gz (10) this 20 cur 192
ffs_size_dir: `mfsroot.gz' size 35043879
ffs_size_dir: size 35043879, using 2 levels of indirect blocks, overhead 6 blocks
ffs_size_dir: exit: size 575852544 inodes 42

[kib]

usr.sbin/makefs/ffs.c

693–694

Can this become a proper function, with proper types for arguments?

[kib]

usr.sbin/makefs/ffs.c

608

This does not need 'else'. Then formatting of the previous block and the herald comment could be cleaned up.

613

615

Should it be full file_len? I do not think direct blocks needs to participate in indirect blocks allocations.

618

I do not understand this at all. What the size of the on-disk inode have with the number of block pointers in indirect blocks?

632

[lytboris_gmail.com]

usr.sbin/makefs/ffs.c

618

That was a mistakenly-taken copypaste, replaced with fs_inopb now

[kib]

usr.sbin/makefs/ffs.c

616

Similarly no, this is wrong. The number of pointers in the indirect block has nothing to do with inode size.

Each indirect block is a plain array of addresses of the next level blocks (then the target is either next level indirect block or data block). The type of the pointer is ufs2_daddr_t or ufs1_daddr_t depending on the version.

621

Definitely not fs_inopb

630

Instead of %lld and long long cast, we normally use %jd and uintmax_t cast for printing integers with arch-dependent sizeof.

[lytboris_gmail.com]

usr.sbin/makefs/ffs.c

616

No idea why I took it :)

fs_nindir should be fine.

[kib]

usr.sbin/makefs/ffs.c

632

I would not bother and always reserve the full block. I suspect this might be easier or even more correct due to some alignment issues.

637

641

At this moment we already accounted that blocks do not need to keep the block count for the direct blocks.

But first, second, and third indirect levels work similarly:

• first, we allocate single-level indirect block and use it to record pointers for file blocks at corresponding offsets;
• second, we need to not count file blocks already in first indirect block, and the second indirect level is only for file offsets after the first level;
• similarly, for third level, both the first and second level blocks should be not accounted for.

[lytboris_gmail.com]

usr.sbin/makefs/ffs.c

632

That's true, but normally these issues will be covered by non-zero minfree. For my test makefs runs I can build a 500Mb image with just 200k of free space with these more "presize" fragment calculations. See roundup at line 660, this helps with alignment issues for me.

641

This is exactly how this while loop works.
On the first round it calculates the number of indirect blocks to hold links to data blocks. If we got 1 from howmany(), we store that particular block in di_ib[] and break the loop (blocks == 0 now). In case we end up with blocks > 0 - we need the next round of while loop to know the number of second indirect blocks to hold links to first indirect blocks left.

[kib]

usr.sbin/makefs/ffs.c

614

632

Ok.

See other places how the switch should be formatted. Basically, the 'case' lines are not indented.

641

I see. Thank you for correcting me.

[kib]

usr.sbin/makefs/ffs.c

651

656

Per style, there should be a blank line before the multi-line comment.

[emaste]

LGTM assuming the two remaining style(9) nits @kib pointed out are fixed. @kib will you handle the push to main?

[kib]

In D52120#1192335, @emaste wrote:

LGTM assuming the two remaining style(9) nits @kib pointed out are fixed. @kib will you handle the push to main?

I prefer that you or Mark do this. I never touched makefs.

[emaste]

Ok, I can commit. @lytboris_gmail.com please confirm Boris Lytochkin <[e-mail]> as the git --author.

[lytboris_gmail.com]

In D52120#1192351, @emaste wrote:

Ok, I can commit. @lytboris_gmail.com please confirm Boris Lytochkin <[e-mail]> as the git --author.

Yep, LGTM