Re: [PATCH v4 2/2] hfsplus: validate b-tree node 0 bitmap at mount time

[Shardul Bankar <shardul.b@mpiricsoftware.com>]

On Fri, 2026-02-27 at 20:11 +0000, Viacheslav Dubeyko wrote:
> On Fri, 2026-02-27 at 22:34 +0530, Shardul Bankar wrote:
> > On Thu, 2026-02-26 at 23:29 +0000, Viacheslav Dubeyko wrote:
> > > On Thu, 2026-02-26 at 14:42 +0530, Shardul Bankar wrote:
> > > 
> > > 
> > 
> > While this byte-level interface is perfect for the mount-time
> > validation in hfs_btree_open() where we only need to check a single
> > bit, using it inside hfs_bmap_alloc() introduces a significant
> > performance regression.
> > 
> > Because hfs_bmap_alloc() performs a linear scan to find a free
> > node,
> > using hfs_bmap_get_map_byte() inside the while (len) loop would
> > force
> > the kernel to execute kmap_local_page() and kunmap_local() for
> > every
> > single byte evaluated (potentially thousands of times per page).
> > The
> > current logic maps the page once, scans memory linearly, and only
> > unmaps when crossing a PAGE_SIZE boundary.
> > 
> > To address your request for a generalized map access method without
> > sacrificing the allocator's O(N) scanning performance, how about
> > this
> > for v5?
> > 
> >     -We introduce the hfs_bmap_get_map_byte() specifically for
> > single-
> > bit reads (like the mount-time check). This can internally call
> > hfs_bmap_get_map_page() from Patch 1/2 to avoid duplicating the
> > offset
> > math.
> > 
> >     -We retain the page-level helper (hfs_bmap_get_map_page) for
> > hfs_bmap_alloc() to preserve its fast linear scanning.
> > 
> > Let me know if this dual-helper approach sounds acceptable, and I
> > will
> > prepare v5.
> > 
> > 
> 
> I think your point makes sense. I missed this. However, we need to
> keep the
> methods simple and understandable. First of all, if we need to return
> multiple
> items from the method, then we definitely need some structure
> declarations that
> can be used.
> 

Agreed. To clean up the method signature for hfs_bmap_get_map_page(), I
will introduce a small structure (e.g., struct hfs_bmap_loc) to hold
the off, len, and page_idx variables instead of passing multiple
pointers.

> As far as I can see, we never had method for bit state check in the
> b-tree map
> before. However, we have hfs_bmap_free() method that is one bit
> change
> operation. So, we could have one bit check (hfs_bmap_test_bit()) and
> one bit
> change (hfs_bmap_set_bit()) pair of methods that could hide all of
> these memory
> pages operations.

This sounds like a good API improvement. I will introduce
hfs_bmap_test_bit() for the mount-time Node 0 check in v5. It can
internally call hfs_bmap_get_map_page() to avoid duplicating the offset
math, while safely encapsulating the kmap_local/kunmap_local for
single-bit reads.

> 
> However, hfs_bmap_alloc() is slightly special one. Probably, we could
> not make
> significant changes in core logic of this method. However, your
> vision of
> auxiliary method can be useful here. Yes, we need to execute
> kmap_local_page()
> for the page, then do the search/allocation, and execute
> kunmap_local(). You are
> right here. But, for my taste, the whole logic of linear search looks
> like not
> very efficient. Do you see any ways of optimizations here? Could we
> employ tree-
> > node_count? Or, maybe, introduce some in-core variable(s) that will
> > keep
> knowledge about last allocation/free? And we can use this knowledge
> to start
> from the most beneficial region of search?
> 

I like the idea of introducing an in-core allocation hint (a roving
pointer) to struct hfs_btree to convert this into a next-fit allocator,
and reusing the map-chain seek logic currently in hfs_bmap_free() to
jump directly to the beneficial region. Bounding the inner scan loop
with tree->node_count also seems like a good correctness optimization
to avoid scanning padding bytes.

However, the current patch series is targeted at the mount-time bitmap
corruption vulnerability. To keep the scope aligned, would it be
acceptable to finalize this current 2-patch series (the map access
refactoring + the Node 0 mount-time validation) in v5, and I will open
a separate thread/patchset afterward to pursue this alloc_hint and
node_count optimization?

Thanks,
Shardul