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

[Viacheslav Dubeyko]

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:
> > > +
> > > +       switch (id) {
> > > +       case HFSPLUS_EXT_CNID:
> > > +               tree_name = "Extents";
> > > +               break;
> > > +       case HFSPLUS_CAT_CNID:
> > > +               tree_name = "Catalog";
> > > +               break;
> > > +       case HFSPLUS_ATTR_CNID:
> > > +               tree_name = "Attributes";
> > > +               break;
> > > +       default:
> > > +               tree_name = "Unknown";
> > > +               break;
> > > +       }
> > 
> > Frankly speaking, it could be enough to share only cnid. But if you
> > would like
> > to be really nice and to share the tree's name, then I prefer to see
> > an array of
> > constant strings where you can use cnid as an index. And macro or
> > static inline
> > method that can check cnid as a input argument. At minimum, simply
> > move this
> > code into the static inline method. But, array of constant strings
> > could be much
> > compact and elegant solution for my taste. Because, art of
> > programming is to
> > represent everything as arrays of something and to apply the
> > generalized loops.
> > :)
> > 
> 
> Hi Slava,
> 
> Sounds good. :) I will implement an array of constant strings indexed
> by cnid in v5.
> 
> > I prefer not to have the obligation of using this asynchronous
> > paradigm of
> > kmap_local()/kunmap_local(). It will be great to keep this inside of
> > hfs_bmap_get_map_<something>() method.
> > 
> > I prefer not to keep the whole page/folio for complete operation
> > locked. And,
> > frankly speaking, you don't need in the whole page because you need a
> > byte or
> > unsigned long portion of bitmap. So, we can consider likewise
> > interface:
> > 
> > u8 hfs_bmap_get_map_byte(struct hfs_bnode *node, u32 bit_index);
> > 
> > Here, you simply need to check the state of bit in byte (READ-ONLY
> > operation).
> > So, you can atomically copy the state of the byte in local variable
> > and to check
> > the bit state in local variable.
> > 
> 
> 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.

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.

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?

Thanks,
Slava.