linux-kernel - Re: [PATCH v3] btrfs: index buffer

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20250705122605.GA4453@twin.jikos.cz>
Date: Sat, 5 Jul 2025 14:26:05 +0200
From: David Sterba <dsterba@...e.cz>
To: Daniel Vacek <neelx@...e.com>
Cc: Chris Mason <clm@...com>, Josef Bacik <josef@...icpanda.com>,
	David Sterba <dsterba@...e.com>, Qu Wenruo <wqu@...e.com>,
	linux-btrfs@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3] btrfs: index buffer_tree using node size

On Fri, Jul 04, 2025 at 06:07:02PM +0200, Daniel Vacek wrote:
> So far we are deriving the buffer tree index using the sector size. But each
> extent buffer covers multiple sectors. This makes the buffer tree rather sparse.
> 
> For example the typical and quite common configuration uses sector size of 4KiB
> and node size of 16KiB. In this case it means the buffer tree is using up to
> the maximum of 25% of it's slots. Or in other words at least 75% of the tree
> slots are wasted as never used.
> 
> We can score significant memory savings on the required tree nodes by indexing
> the tree using the node size instead. As a result far less slots are wasted
> and the tree can now use up to all 100% of it's slots this way.
> 
> Note: This works even with unaligned tree blocks as we can still get unique
>       index by doing eb->start >> nodesize_shift.
> 
> Getting some stats from running fio write test, there is a bit of variance.
> The values presented in the table below are medians from 5 test runs.
> The numbers are (# of allocated ebs in the tree / # of leaf tree nodes /
> / highest index in the tree (radix tree width)):
> 
> ebs / leaves / Index |   bare for-next    |      with fix
> ---------------------+--------------------+-------------------
> 	post mount   |   16 /  11 / 10e5c |   16 /  10 / 4240
> 	post test    | 5810 / 891 / 11cfc | 4420 / 252 / 473a
> 	post rm	     |  574 / 300 / 10ef0 |  540 / 163 / 46e9
> 
> In this case (10 gig FS) the height of the tree is still 3 levels but the
> 4x width reduction is clearly visible as expected. But since the tree is
> more dense we can see the 54-72% reduction of leaf nodes. That's very
> close to ideal with this test. It means the tree is getting really dense
> with this kind of workload.
> 
> Also, the fio results show no performance change.
> 
> Signed-off-by: Daniel Vacek <neelx@...e.com>
> Reviewed-by: Qu Wenruo <wqu@...e.com>
> ---
> V3 changes: Mentioned stats diff in the commit message and rebased.

Added to for-next, thanks. Please also format the changelog lines to 72
or 74 chars.