Re: [PATCH RFC 2/8] xarray: add xas_prev_canonical()

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential
issues to consider:
- [Medium] xarray: xas_prev_canonical() corrupts xa_index on
  XA_RETRY_ENTRY
- [Medium] xarray: xas_prev_canonical() steps off non-leaf canonical
  slot on split
--

commit b768624f5f5a261ca8a1796cf3f8c4a5e5deca0d
Author: Kairui Song <kasong@tencent.com>

xarray: add xas_prev_canonical()

This commit adds xas_prev_canonical() to step backwards over multi-index
XArray entries onto the canonical slot and first index covered by the
entry, along with test cases in the XArray test suite.

> diff --git a/include/linux/xarray.h b/include/linux/xarray.h
> index be850174e802e..b76d24e7a46b3 100644
> --- a/include/linux/xarray.h
> +++ b/include/linux/xarray.h
[ ... ]
> @@ -1883,6 +1892,46 @@ static inline void *xas_prev(struct xa_state *xas)
>  	return xa_entry(xas->xa, node, xas->xa_offset);
>  }
>  
> +/**
> + * xas_prev_canonical() - Move iterator to the previous entry, onto the slot
> + * which stores it.
> + * @xas: XArray operation state.
> + *
> + * Same as xas_prev(), but it steps back over a multi-index entry as a
> + * whole: the state is left on the slot which stores the entry and on its
> + * first index, so xas_get_order() reports its order.  A cursor already
> + * inside an entry reports that entry instead of stepping off it.
> + *
> + * Context: Any context.  Hold the xa_lock or the RCU lock across the
> + * whole walk; xas_pause() is forward-only.
> + * Return: The entry at the new position, or %NULL (empty slot, error
> + * state, or the end of the walk).  The result may be an internal entry,
> + * which needs xas_retry().
> + */
> +static inline void *xas_prev_canonical(struct xa_state *xas)
> +{
> +	void *entry = NULL;
> +
> +	/* step back unless @xas is already inside an entry */
> +	if (!xas_is_node(xas) ||
> +	    xas->xa_offset >= XA_CHUNK_SIZE ||
> +	    xas->xa_offset == ((xas->xa_index >> xas->xa_node->shift) &
> +			       XA_CHUNK_MASK))
> +		entry = xas_prev(xas);

[Severity: Medium]
Does shifting xas->xa_index right by xas->xa_node->shift step off an entry
when the cursor is at a non-initial index inside the canonical slot of an
internal node?

When an entry has order >= XA_CHUNK_SHIFT (xas->xa_node->shift > 0), the
canonical slot itself covers (1UL << xas->xa_node->shift) indices.
Discarding the lower shift bits makes xas->xa_offset equal
((xas->xa_index >> xas->xa_node->shift) & XA_CHUNK_MASK) for every index
within that canonical slot, so xas_prev_canonical() calls xas_prev(xas)
even when xas->xa_index is past the first index of the entry:

CPU0                              CPU1
xas_load(&xas)
  /* order-6 entry at [128, 191],
     xas_index = 150, shift = 6,
     xa_offset = 2 */
                                  xas_split()
                                    /* splits slot 2 into child node */
xas_prev_canonical(&xas)
  /* (150 >> 6) & 63 == 2 */
  xas_prev(&xas)
    __xas_prev(&xas)
      xas->xa_index--; /* 149 */
      /* descends into child node
         at 149 instead of retrying
         at 150 */                <-- skips entry at 150

Preserving the lower shift bits the way xas_sibling() does (comparing
xas->xa_index & ((XA_CHUNK_SIZE << node->shift) - 1) against
(unsigned long)xas->xa_offset << node->shift) would avoid calling
xas_prev() when the cursor is already inside the canonical slot.

> +	if (!xas_is_node(xas))
> +		return entry;
> +	if (xa_is_sibling(entry))
> +		xas->xa_offset = xa_to_sibling(entry);
> +
> +	entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
> +	/* a concurrent store or split can leave a sibling or a node here */
> +	if (xa_is_sibling(entry) ||
> +	    (xas->xa_node->shift && xa_is_node(entry)))
> +		return XA_RETRY_ENTRY;
> +	xas_move_index(xas, xas->xa_offset);
> +	return entry;
> +}

[Severity: Medium]
Can xas_prev_canonical() move xas->xa_index backwards before returning
XA_RETRY_ENTRY, or lose an XA_RETRY_ENTRY returned by xas_prev()?

During a lockless RCU walk, xas_retry() calls xas_reset(), which sets
xas->xa_node = XAS_RESTART and relies on xas->xa_index remaining at the
index that needs to be retried so the next __xas_prev() call reloads that
same index.  Here, if xas_prev() returns a sibling entry and the canonical
slot at xas->xa_offset has been overwritten with XA_RETRY_ENTRY by a
concurrent xas_free_nodes() or xas_shrink(), XA_RETRY_ENTRY is neither a
sibling nor a node, so execution calls xas_move_index(xas, xas->xa_offset)
before returning XA_RETRY_ENTRY:

CPU0                              CPU1
xas_prev_canonical(&xas)
  entry = xas_prev(&xas)
    /* lands on sibling slot,
       returns xa_mk_sibling(off) */
  xas->xa_offset = off;
                                  xas_free_nodes()
                                    /* overwrites slot[off] with
                                       XA_RETRY_ENTRY */
  entry = xa_entry(..., off);
    /* entry is XA_RETRY_ENTRY */
  xas_move_index(&xas, off);      <-- lowers xas->xa_index
  return XA_RETRY_ENTRY;
xas_retry(&xas, entry)
  xas_reset(&xas);
xas_prev_canonical(&xas)
  __xas_prev(&xas)
    xas_load(&xas)                <-- reloads at lowered xa_index,
                                      skipping intermediate entries

In addition, if xas_prev() itself returns XA_RETRY_ENTRY (for example via
__xas_prev() -> xas_load() -> xas_descend() when a sibling in an internal
node was concurrently split into a child node), xas_prev_canonical()
unconditionally overwrites entry with xa_entry() and loses the retry if
that canonical slot was concurrently replaced with a normal entry.

Checking xa_is_retry(entry) after xas_prev() and before xas_move_index()
would preserve both the retry entry and xas->xa_index.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261114-swap-thp-split-v1-0-dfa8d4fa448d@tencent.com?part=2