Re: [PATCH 2/6] xfs: invert the realtime summary cache

["Darrick J. Wong" <djwong@kernel.org>]

On Mon, Jul 17, 2023 at 12:54:24PM -0700, Omar Sandoval wrote:
> On Wed, Jul 12, 2023 at 03:40:01PM -0700, Darrick J. Wong wrote:
> > On Tue, Jun 20, 2023 at 02:32:12PM -0700, Omar Sandoval wrote:
> > > From: Omar Sandoval <osandov@fb.com>
> > > 
> > > In commit 355e3532132b ("xfs: cache minimum realtime summary level"), I
> > > added a cache of the minimum level of the realtime summary that has any
> > > free extents. However, it turns out that the _maximum_ level is more
> > > useful for upcoming optimizations, and basically equivalent for the
> > > existing usage. So, let's change the meaning of the cache to be the
> > > maximum level + 1, or 0 if there are no free extents.
> > 
> > Hmm.  If I'm reading xfs_rtmodify_summary_int right, m_rsum_cache[b] now
> > tells us the maximum log2(length) of the free extents starting in
> > rtbitmap block b?
> > 
> > IOWs, let's say the cache contents are:
> > 
> > {2, 3, 2, 15, 8}
> > 
> > Someone asks for a 400rtx (realtime extent) allocation, so we want to
> > find a free space of at least magnitude floor(log2(400)) == 8.
> > 
> > The cache tells us that there aren't any free extents longer than 2^1
> > blocks in rtbitmap blocks 0 and 2; longer than 2^2 blocks in rtbmp block
> > 1; longer than 2^7 blocks in rtbmp block 4; nor longer than 2^14 blocks
> > in rtbmp block 3?
> 
> There's a potential for an off-by-one bug here, so just to make sure
> we're saying the same thing: the realtime summary for level n contains
> the number of free extents starting in a bitmap block such that
> floor(log2(size_in_realtime_extents)) == n. The maximum size of a free
> extent in level n is therefore 2^(n + 1) - 1 realtime extents.
> 
> So in your example, the cache is telling us that realtime bitmap blocks
> 0 and 2 don't have anything free in levels 2 or above, and therefore
> don't have any free extents longer than _or equal to_ 2^2.

D'oh.  I forgot that subtlety that the maximum size of a free
extent in level n is therefore 2^(n + 1) - 1 realtime extents.

> I'll try to reword the commit message and comments to make this
> unambiguous.

Ok, thanks.  A couple of quick examples (feel free to use mine) would be
helpful for descrambling my brain. :)

--D