On Wed, Dec 14, 2022 at 10:47:37PM -0800, Eric Biggers wrote: > On Thu, Dec 15, 2022 at 10:06:32AM +1100, Dave Chinner wrote: > > > Well, my proposal at > > > https://lore.kernel.org/r/20221028224539.171818-2-ebiggers@xxxxxxxxxx is to keep > > > tracking the "verified" status at the individual Merkle tree block level, by > > > adding a bitmap fsverity_info::hash_block_verified. That is part of the > > > fs/verity/ infrastructure, and all filesystems would be able to use it. > > > > Yeah, i had a look at that rewrite of the verification code last > > night - I get the gist of what it is doing, but a single patch of > > that complexity is largely impossible to sanely review... > > Thanks for taking a look at it. It doesn't really lend itself to being split > up, unfortunately, but I'll see what I can do. > > > Correct me if I'm wrong, but won't using a bitmap with 1 bit per > > verified block cause problems with contiguous memory allocation > > pretty quickly? i.e. a 64kB bitmap only tracks 512k blocks, which is > > only 2GB of merkle tree data. Hence at file sizes of 100+GB, the > > bitmap would have to be kvmalloc()d to guarantee allocation will > > succeed. > > > > I'm not really worried about the bitmap memory usage, just that it > > handles large contiguous allocations sanely. I suspect we may > > eventually need a sparse bitmap (e.g. the old btrfs bit-radix > > implementation) to track verification in really large files > > efficiently. > > Well, that's why my patch uses kvmalloc() to allocate the bitmap. > > I did originally think it was going to have to be a sparse bitmap that ties into > the shrinker so that pages of it can be evicted. But if you do the math, the > required bitmap size is only 1 / 2^22 the size of the file, assuming the Merkle > tree uses SHA-256 and 4K blocks. So a 100MB file only needs a 24-byte bitmap, > and the bitmap for any file under 17GB fits in a 4K page. > > My patch puts an arbitrary limit at a 1 MiB bitmap, which would be a 4.4TB file. > > It's not ideal to say "4 TB Ought To Be Enough For Anybody". But it does feel > that it's not currently worth the extra complexity and runtime overhead of > implementing a full-blown sparse bitmap with cache eviction support, when no one > currently has a use case for fsverity on files anywhere near that large. I think we can live with that for the moment, but I suspect that 4TB filesize limit will become an issue sooner rather than later. What will happen if someone tries to measure a file larger than this limit? What's the failure mode? Cheers, Dave. -- Dave Chinner david@xxxxxxxxxxxxx