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

[Viacheslav Dubeyko]

On Sat, 2026-02-28 at 03:32 +0530, Shardul Bankar wrote:
> 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?
> 

This is my point too. Let's finish this patch at first. Then, we can optimize
hfs_bmap_alloc(). Potentially, we can even consider of caching some portion of
b-tree's map for search and synchronization with map in memory pages.

Thanks,
Slava.