[PATCH] KVM: Simplify backwards dirty ring batch check

[PATCH] KVM: Simplify backwards dirty ring batch check

[Peng Hao]

The backwards coalescing path shifts mask left and back right to check
whether moving the batch base would discard set bits.  The shift fits if
the distance is no greater than the number of leading zeroes in mask.

Use that directly.  Convert delta to u64 before negating it so that a
positive delta, including one that wrapped to S64_MIN, is rejected by the
unsigned comparison without invoking signed overflow.  Use __builtin_clzl()
to match the unsigned long type of mask on both 32-bit and 64-bit builds.

Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Peng Hao <flyingpeng@tencent.com>
---
 virt/kvm/dirty_ring.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/virt/kvm/dirty_ring.c b/virt/kvm/dirty_ring.c
index 572b854edf74..8f39047ae7ab 100644
--- a/virt/kvm/dirty_ring.c
+++ b/virt/kvm/dirty_ring.c
@@ -170,9 +170,8 @@ int kvm_dirty_ring_reset(struct kvm *kvm, struct kvm_dirty_ring *ring,
 					continue;
 				}
 
-				/* Backwards visit, careful about overflows! */
-				if (delta > -BITS_PER_LONG && delta < 0 &&
-				(mask << -delta >> -delta) == mask) {
+				/* Backwards visit, but do not discard set bits. */
+				if (-(u64)delta <= __builtin_clzl(mask)) {
 					cur_offset = next_offset;
 					mask = (mask << -delta) | 1;
 					continue;
-- 
2.43.7

Re: [PATCH] KVM: Simplify backwards dirty ring batch check

[Sean Christopherson]

On Thu, Sep 10, 2026, Peng Hao wrote:
> The backwards coalescing path shifts mask left and back right to check
> whether moving the batch base would discard set bits.  The shift fits if
> the distance is no greater than the number of leading zeroes in mask.
> 
> Use that directly.  Convert delta to u64 before negating it so that a
> positive delta, including one that wrapped to S64_MIN, is rejected by the
> unsigned comparison without invoking signed overflow.  Use __builtin_clzl()
> to match the unsigned long type of mask on both 32-bit and 64-bit builds.
> 
> Suggested-by: Paolo Bonzini <pbonzini@redhat.com>

LOL, Paolo definitely has a different sense of "simple" when it comes to bitwise
math.

> Signed-off-by: Peng Hao <flyingpeng@tencent.com>
> ---
>  virt/kvm/dirty_ring.c | 5 ++---
>  1 file changed, 2 insertions(+), 3 deletions(-)
> 
> diff --git a/virt/kvm/dirty_ring.c b/virt/kvm/dirty_ring.c
> index 572b854edf74..8f39047ae7ab 100644
> --- a/virt/kvm/dirty_ring.c
> +++ b/virt/kvm/dirty_ring.c
> @@ -170,9 +170,8 @@ int kvm_dirty_ring_reset(struct kvm *kvm, struct kvm_dirty_ring *ring,
>  					continue;
>  				}
>  
> -				/* Backwards visit, careful about overflows! */
> -				if (delta > -BITS_PER_LONG && delta < 0 &&
> -				(mask << -delta >> -delta) == mask) {
> +				/* Backwards visit, but do not discard set bits. */

IMO, this really needs a more verbose comment.  

> +				if (-(u64)delta <= __builtin_clzl(mask)) {

Rather than the s64 => u64 => negated logic, which just makes my head hurt even
with the verbose changelog, what if we gate the entire outer if-statement on the
absolute delta, i.e. the shift, being within range?

And probably in a separate patch, but I think we should also replace BITS_PER_LONG
with BITS_PER_TYPE(mask) to communicate that the logic is all about not overflowing
"mask".  

>  					cur_offset = next_offset;
>  					mask = (mask << -delta) | 1;

Maybe also opportunistically use BIT_ULL() instead of open coding the bit shifts?
The literal '1' is especially annoying, as it unnecessarily obfuscates that the
code is setting bit 0, i.e. that '1' isn't some magic number.

Untested, but I think this would work?

			s64 delta = next_offset - cur_offset;

			/*
			 * While the size of each ring is fixed, it's possible
			 * for the ring to be constantly re-dirtied/harvested
			 * while the reset is in-progress (the hard limit exists
			 * only to guard against the count becoming negative).
			 */
			cond_resched();

			/*
			 * Try to coalesce the reset operations when the guest
			 * is scanning pages in the same slot.
			 */
			if (next_slot == cur_slot &&
			    abs(delta) < BITS_PER_TYPE(mask)) {
				if (delta >= 0) {
					mask |= BIT_ULL(delta);
					continue;
				}

				/*
				 * The next offset is backwards relative to the
				 * current base of the mask of bits.  Shift the
				 * mask "backwards" as well so that the next
				 * offset becomes bit 0, unless doing so would
				 * drop bits from the mask.  If the number of
				 * leading zeros is greater than or equal to
				 * the shift, then no set bits will be dropped.
				 */
				if (-delta <= __builtin_clzl(mask)) {
					cur_offset = next_offset;
					mask = (mask << -delta) | BIT_ULL(0);
					continue;
				}
			}

			/*
			 * Reset the slot for all the harvested entries that
			 * have been gathered, but not yet fully processed.
			 */
			kvm_reset_dirty_gfn(kvm, cur_slot, cur_offset, mask);

Or maybe capture the shift as a u64 early on?

			s64 delta = next_offset - cur_offset;
			u64 shift = abs(delta);

			/*
			 * While the size of each ring is fixed, it's possible
			 * for the ring to be constantly re-dirtied/harvested
			 * while the reset is in-progress (the hard limit exists
			 * only to guard against the count becoming negative).
			 */
			cond_resched();

			/*
			 * Try to coalesce the reset operations when the guest
			 * is scanning pages in the same slot.
			 */
			if (next_slot == cur_slot && shift < BITS_PER_TYPE(mask)) {
				if (delta >= 0) {
					mask |= BIT_ULL(shift);
					continue;
				}

				/*
				 * The next offset is backwards relative to the
				 * current base of the mask of bits.  Shift the
				 * mask "backwards" as well so that the next
				 * offset becomes bit 0, unless doing so would
				 * drop bits from the mask.  If the number of
				 * leading zeros is greater than or equal to
				 * the shift, then no set bits will be dropped.
				 */
				if (shift <= __builtin_clzl(mask)) {
					cur_offset = next_offset;
					mask = (mask << shift) | BIT_ULL(0);
					continue;
				}
			}

			/*
			 * Reset the slot for all the harvested entries that
			 * have been gathered, but not yet fully processed.
			 */
			kvm_reset_dirty_gfn(kvm, cur_slot, cur_offset, mask);

Actually, I think I like option 3 the most: capture only the unsigned shift, and
then explicitly check "next_offset >= cur_offset" instead of checking the delta?

			u64 shift = abs(next_offset - cur_offset);

			/*
			 * While the size of each ring is fixed, it's possible
			 * for the ring to be constantly re-dirtied/harvested
			 * while the reset is in-progress (the hard limit exists
			 * only to guard against the count becoming negative).
			 */
			cond_resched();

			/*
			 * Try to coalesce the reset operations when the guest
			 * is scanning pages in the same slot.
			 */
			if (next_slot == cur_slot && shift < BITS_PER_TYPE(mask)) {
				if (next_offset >= cur_offset) {
					mask |= BIT_ULL(shift);
					continue;
				}

				/*
				 * The next offset is backwards relative to the
				 * current base of the mask of bits.  Shift the
				 * mask "backwards" as well so that the next
				 * offset becomes bit 0, unless doing so would
				 * drop bits from the mask.  If the number of
				 * leading zeros is greater than or equal to
				 * the shift, then no set bits will be dropped.
				 */
				if (shift <= __builtin_clzl(mask)) {
					cur_offset = next_offset;
					mask = (mask << shift) | BIT_ULL(0);
					continue;
				}
			}

			/*
			 * Reset the slot for all the harvested entries that
			 * have been gathered, but not yet fully processed.
			 */
			kvm_reset_dirty_gfn(kvm, cur_slot, cur_offset, mask);

>  					continue;
> -- 
> 2.43.7
> 

Re: [PATCH] KVM: Simplify backwards dirty ring batch check

[Paolo Bonzini]

On Thu, Sep 10, 2026 at 4:40 PM Sean Christopherson <seanjc@google.com> wrote:
>
> On Thu, Sep 10, 2026, Peng Hao wrote:
> > The backwards coalescing path shifts mask left and back right to check
> > whether moving the batch base would discard set bits.  The shift fits if
> > the distance is no greater than the number of leading zeroes in mask.
> >
> > Use that directly.  Convert delta to u64 before negating it so that a
> > positive delta, including one that wrapped to S64_MIN, is rejected by the
> > unsigned comparison without invoking signed overflow.  Use __builtin_clzl()
> > to match the unsigned long type of mask on both 32-bit and 64-bit builds.
> >
> > Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
>
> LOL, Paolo definitely has a different sense of "simple" when it comes to bitwise
> math.

I am not sure *when* I suggested that. I cannot honestly exclude it,
for the reason you express, :) but it probably was before
include/linux/overflow.h.  Because...

> > -                             /* Backwards visit, careful about overflows! */
> > -                             if (delta > -BITS_PER_LONG && delta < 0 &&
> > -                             (mask << -delta >> -delta) == mask) {
> > +                             /* Backwards visit, but do not discard set bits. */
>
> IMO, this really needs a more verbose comment.
>
> > +                             if (-(u64)delta <= __builtin_clzl(mask)) {

... I love it, but it's unreadable. The "mask << -delta >> -delta"
basically means no overflow on shift left. So just write

if (!check_shl_overflow(mask, -delta, shifted_mask)) {
    cur_offset = next_offset;
    mask = shifted_mask | 1;
}

and the clz magic, if desired, goes in include/linux/overflow.h. A lot
more complicated now:

i#define __check_shl_choose(_int, _ll)                                  \
        __builtin_choose_expr(sizeof(_a) <= sizeof(unsigned int) &&     \
                              sizeof(*_d) <= sizeof(unsigned int),      \
                              (_int), (_ll))

  #define check_shl_overflow(a, s, d) __must_check_overflow(({          \
        typeof(a) _a = (a);                                             \
        typeof(s) _s = (s);                                             \
        typeof(d) _d = (d);                                             \
        unsigned int _width = __check_shl_choose(32, 64);               \
        unsigned int _bits = 8 * sizeof(*_d);                           \
        unsigned int _dst_bits = _bits -                                \
                                 is_signed_type(typeof(*_d));           \
        unsigned int _adj = _width - _dst_bits;                         \
        unsigned int _clz = __check_shl_choose(                         \
                _a ? __builtin_clz((unsigned int)_a) : 32,              \
                _a ? __builtin_clzll((unsigned long long)_a) : 64);     \
        bool _overflow;                                                 \
                                                                        \
        BUILD_BUG_ON(is_signed_type(typeof(_a)));                       \
        BUILD_BUG_ON(is_signed_type(typeof(*_d)) &&                     \
                     sizeof(*_d) <= sizeof(_a));                        \
                                                                        \
        _overflow = (sizeof(_a) > sizeof(*_d) && _clz < _adj) ||        \
                (u64)_s >= min_t(u64, _bits, _clz - _adj + 1);          \
        if (!_overflow)                                                 \
                *_d = (typeof(*_d))_a << _s;                            \
        _overflow;                                                      \
  }))

(The BUILD_BUG_ON would be more restrictive than the current
implementation, but IMO would be a good idea anyway to avoid having to
think about sign extensions).

So yeah, I think I must pass on the opportunity and leave the current code...

Paolo