Skip to contentSkip to conversation

__futex_pivot_hash() race

RFC PATCH New Chris Mason 3 participants 8 messages Aug 18 – Oct 1 Futex

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 __futex_pivot_hash() race

This is really just AI questioning how we synchronize mmph->batches and mmph->hash. It looks real to me, and the repro with printks does fire, so hopefully I've got things right.

The patch and description were also AI, meaning this is more bug report in patch form. Testing was only done against the one repro.

(I may or may not have successfully switched over my git config to [email protected], lets see...)

#1 lore raw

PATCH 1/1 futex: sample poll cookie after publishing new hash

futex_ref_drop() may only skip its grace period when one has already elapsed since the current private hash was published:

    kernel/futex/core.c:futex_ref_drop
        if (poll_state_synchronize_rcu(mm->futex.phash.batches)) {
                /*
                 * There was a grace-period, we can begin now.
                 */
                __futex_ref_atomic_begin(fph);
                return;
        }

The cookie it polls is sampled one statement before that publication:

    kernel/futex/core.c:__futex_pivot_hash
        new->state = FR_PERCPU;
        scoped_guard(rcu) {
                mmph->batches = get_state_synchronize_rcu();
                rcu_assign_pointer(mmph->hash, new);
        }
        kvfree_rcu(fph, rcu);

get_state_synchronize_rcu() anchors its guarantee at the snapshot, so the cookie is cleared by the first grace period that starts from there on, including one starting between the two stores which never waited for a reader that loaded the old hash after it began.

    CPU 0 (resize)                    CPU 1 (futex_hash)
    ==============                    ==================
    __futex_pivot_hash()
      batches = get_state_...()
                                      grace period starts
                                      guard(rcu)
                                      fph = old hash
      rcu_assign_pointer(hash, new)
      kvfree_rcu(old hash)
    futex_hash_allocate()
      futex_ref_drop(new hash)
        poll_state_...() -> true
        __futex_ref_atomic_begin()
          atomic = LONG_MAX
                                      futex_ref_get(old hash) -> true
                                      spin_lock(&fph->queues[i].lock)

The reference count lives in the mm and has just been biased for the new generation, so the stalled reader pins and then locks the retired hash that is already queued for free, and its later put is charged against the live generation.

Fix by sampling the cookie after rcu_assign_pointer() publishes the new hash. Drop the surrounding scoped_guard(rcu) while at it: it only delayed completion of the prematurely anchored grace-period and serves no purpose once the cookie is sampled after publication. The writer side is serialized by mm->futex.phash.lock and neither rcu_assign_pointer() nor kvfree_rcu() requires a read-side section.

Fixes 56180dd20c19 ("futex: Use RCU-based per-CPU reference counting instead of rcuref_t")
Assisted-by kres:claude-opus-5
---
 kernel/futex/core.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)
kernel/futex/core.c +8 -4
index 128c5752f225..05619eb8329c 100644
@@ -209,10 +209,14 @@ static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *
 		futex_rehash_private(fph, new);
 	}
 	new->state = FR_PERCPU;
-	scoped_guard(rcu) {
-		mmph->batches = get_state_synchronize_rcu();
-		rcu_assign_pointer(mmph->hash, new);
-	}
+	rcu_assign_pointer(mmph->hash, new);
+	/*
+	 * Pairs with futex_ref_drop(): ->batches must be sampled at or after
+	 * the rcu_assign_pointer() above, so any grace-period satisfying
+	 * poll_state_synchronize_rcu() provably started once no reader could
+	 * still load the retired fph. Both stores are done under mmph->lock.
+	 */
+	mmph->batches = get_state_synchronize_rcu();
 	kvfree_rcu(fph, rcu);
 	return true;
 }
Signature · 1 line
2.53.0-Meta
#2 lore raw

Re: [PATCH] futex: sample poll cookie after publishing new hash

Quoted 49 lines · Chris Mason

futex_ref_drop() may only skip its grace period when one has already elapsed since the current private hash was published:

    kernel/futex/core.c:futex_ref_drop
        if (poll_state_synchronize_rcu(mm->futex.phash.batches)) {
                /*
                 * There was a grace-period, we can begin now.
                 */
                __futex_ref_atomic_begin(fph);
                return;
        }

The cookie it polls is sampled one statement before that publication:

    kernel/futex/core.c:__futex_pivot_hash
        new->state = FR_PERCPU;
        scoped_guard(rcu) {
                mmph->batches = get_state_synchronize_rcu();
                rcu_assign_pointer(mmph->hash, new);
        }
        kvfree_rcu(fph, rcu);

get_state_synchronize_rcu() anchors its guarantee at the snapshot, so the cookie is cleared by the first grace period that starts from there on, including one starting between the two stores which never waited for a reader that loaded the old hash after it began.

    CPU 0 (resize)                    CPU 1 (futex_hash)
    ==============                    ==================
    __futex_pivot_hash()
      batches = get_state_...()
                                      grace period starts
                                      guard(rcu)
                                      fph = old hash
      rcu_assign_pointer(hash, new)
      kvfree_rcu(old hash)
    futex_hash_allocate()
      futex_ref_drop(new hash)
        poll_state_...() -> true
        __futex_ref_atomic_begin()
          atomic = LONG_MAX
                                      futex_ref_get(old hash) -> true
                                      spin_lock(&fph->queues[i].lock)

The reference count lives in the mm and has just been biased for the new generation, so the stalled reader pins and then locks the retired hash that is already queued for free, and its later put is charged against the live generation.

Quoted 6 lines

Fix by sampling the cookie after rcu_assign_pointer() publishes the new hash. Drop the surrounding scoped_guard(rcu) while at it: it only delayed completion of the prematurely anchored grace-period and serves no purpose once the cookie is sampled after publication. The writer side is serialized by mm->futex.phash.lock and neither rcu_assign_pointer() nor kvfree_rcu() requires a read-side section.

God, how I hate reading AI output :-(

Anyway, the thinking was that by holding rcu_read_lock(), the current RCU-GP cannot change and the cookie and assignment are effectively 'atomic'.

Paul?

Quoted 33 lines
Fixes 56180dd20c19 ("futex: Use RCU-based per-CPU reference counting instead of rcuref_t")
Assisted-by kres:claude-opus-5
---
 kernel/futex/core.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)
kernel/futex/core.c +8 -4
index 128c5752f225..05619eb8329c 100644
@@ -209,10 +209,14 @@ static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *
 		futex_rehash_private(fph, new);
 	}
 	new->state = FR_PERCPU;
-	scoped_guard(rcu) {
-		mmph->batches = get_state_synchronize_rcu();
-		rcu_assign_pointer(mmph->hash, new);
-	}
+	rcu_assign_pointer(mmph->hash, new);
+	/*
+	 * Pairs with futex_ref_drop(): ->batches must be sampled at or after
+	 * the rcu_assign_pointer() above, so any grace-period satisfying
+	 * poll_state_synchronize_rcu() provably started once no reader could
+	 * still load the retired fph. Both stores are done under mmph->lock.
+	 */
+	mmph->batches = get_state_synchronize_rcu();
 	kvfree_rcu(fph, rcu);
 	return true;
 }
Signature · 1 line
2.53.0-Meta
#3 lore raw

Re: [PATCH] futex: sample poll cookie after publishing new hash

Quoted 57 lines · Peter Zijlstra
Quoted 49 lines · Chris Mason

futex_ref_drop() may only skip its grace period when one has already elapsed since the current private hash was published:

    kernel/futex/core.c:futex_ref_drop
        if (poll_state_synchronize_rcu(mm->futex.phash.batches)) {
                /*
                 * There was a grace-period, we can begin now.
                 */
                __futex_ref_atomic_begin(fph);
                return;
        }

The cookie it polls is sampled one statement before that publication:

    kernel/futex/core.c:__futex_pivot_hash
        new->state = FR_PERCPU;
        scoped_guard(rcu) {
                mmph->batches = get_state_synchronize_rcu();
                rcu_assign_pointer(mmph->hash, new);
        }
        kvfree_rcu(fph, rcu);

get_state_synchronize_rcu() anchors its guarantee at the snapshot, so the cookie is cleared by the first grace period that starts from there on, including one starting between the two stores which never waited for a reader that loaded the old hash after it began.

    CPU 0 (resize)                    CPU 1 (futex_hash)
    ==============                    ==================
    __futex_pivot_hash()
      batches = get_state_...()
                                      grace period starts
                                      guard(rcu)
                                      fph = old hash
      rcu_assign_pointer(hash, new)
      kvfree_rcu(old hash)
    futex_hash_allocate()
      futex_ref_drop(new hash)
        poll_state_...() -> true
        __futex_ref_atomic_begin()
          atomic = LONG_MAX
                                      futex_ref_get(old hash) -> true
                                      spin_lock(&fph->queues[i].lock)

The reference count lives in the mm and has just been biased for the new generation, so the stalled reader pins and then locks the retired hash that is already queued for free, and its later put is charged against the live generation.

Quoted 6 lines

Fix by sampling the cookie after rcu_assign_pointer() publishes the new hash. Drop the surrounding scoped_guard(rcu) while at it: it only delayed completion of the prematurely anchored grace-period and serves no purpose once the cookie is sampled after publication. The writer side is serialized by mm->futex.phash.lock and neither rcu_assign_pointer() nor kvfree_rcu() requires a read-side section.

Quoted 5 lines

God, how I hate reading AI output :-(

Anyway, the thinking was that by holding rcu_read_lock(), the current RCU-GP cannot change and the cookie and assignment are effectively 'atomic'.

From what I can tell there are a few ways for new grace periods to start while we're holding rcu_read_lock(), synchronize_rcu_expedited() if no GP is currently in flight being the easiest?

Anyway, this BUG_ON() fires for me:

kernel/futex/core.c +8 -0
index a061f54b6..18d51c145 100644
@@ -215,6 +215,14 @@ static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *
 	new->state = FR_PERCPU;
 	scoped_guard(rcu) {
 		mmph->batches = get_state_synchronize_rcu();
+		/*
+		 * Fires only if a grace period started after the cookie
+		 * above was taken, although rcu_read_lock() is held. That
+		 * grace period then satisfies the stored cookie, yet it began
+		 * before the new hash is published below.
+		 */
+		BUG_ON(!same_state_synchronize_rcu(mmph->batches,
+						   get_state_synchronize_rcu()));
 		rcu_assign_pointer(mmph->hash, new);
 	}
 	kvfree_rcu(fph, rcu);

-chris

#4 lore raw

Re: [PATCH] futex: sample poll cookie after publishing new hash

Quoted 81 lines · Chris Mason
Quoted 57 lines · Peter Zijlstra
Quoted 49 lines · Chris Mason

futex_ref_drop() may only skip its grace period when one has already elapsed since the current private hash was published:

    kernel/futex/core.c:futex_ref_drop
        if (poll_state_synchronize_rcu(mm->futex.phash.batches)) {
                /*
                 * There was a grace-period, we can begin now.
                 */
                __futex_ref_atomic_begin(fph);
                return;
        }

The cookie it polls is sampled one statement before that publication:

    kernel/futex/core.c:__futex_pivot_hash
        new->state = FR_PERCPU;
        scoped_guard(rcu) {
                mmph->batches = get_state_synchronize_rcu();
                rcu_assign_pointer(mmph->hash, new);
        }
        kvfree_rcu(fph, rcu);

get_state_synchronize_rcu() anchors its guarantee at the snapshot, so the cookie is cleared by the first grace period that starts from there on, including one starting between the two stores which never waited for a reader that loaded the old hash after it began.

    CPU 0 (resize)                    CPU 1 (futex_hash)
    ==============                    ==================
    __futex_pivot_hash()
      batches = get_state_...()
                                      grace period starts
                                      guard(rcu)
                                      fph = old hash
      rcu_assign_pointer(hash, new)
      kvfree_rcu(old hash)
    futex_hash_allocate()
      futex_ref_drop(new hash)
        poll_state_...() -> true
        __futex_ref_atomic_begin()
          atomic = LONG_MAX
                                      futex_ref_get(old hash) -> true
                                      spin_lock(&fph->queues[i].lock)

The reference count lives in the mm and has just been biased for the new generation, so the stalled reader pins and then locks the retired hash that is already queued for free, and its later put is charged against the live generation.

Quoted 6 lines

Fix by sampling the cookie after rcu_assign_pointer() publishes the new hash. Drop the surrounding scoped_guard(rcu) while at it: it only delayed completion of the prematurely anchored grace-period and serves no purpose once the cookie is sampled after publication. The writer side is serialized by mm->futex.phash.lock and neither rcu_assign_pointer() nor kvfree_rcu() requires a read-side section.

Quoted 7 lines

God, how I hate reading AI output :-(

Anyway, the thinking was that by holding rcu_read_lock(), the current RCU-GP cannot change and the cookie and assignment are effectively 'atomic'.

From what I can tell there are a few ways for new grace periods to start

while we're holding rcu_read_lock(), synchronize_rcu_expedited() if no GP is currently in flight being the easiest?

Anyway, this BUG_ON() fires for me:

kernel/futex/core.c +3 -0
index a061f54b6..18d51c145 100644
@@ -215,6 +215,14 @@ static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *
 	new->state = FR_PERCPU;
 	scoped_guard(rcu) {
 		mmph->batches = get_state_synchronize_rcu();
+		/*
+		 * Fires only if a grace period started after the cookie
+		 * above was taken, although rcu_read_lock() is held. That

kernel/futex/core.c static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *

Quoted 10 lines
kernel/futex/core.c +5 -1
+		 * grace period then satisfies the stored cookie, yet it began
+		 * before the new hash is published below.
+		 */
+		BUG_ON(!same_state_synchronize_rcu(mmph->batches,
+						   get_state_synchronize_rcu()));
 		rcu_assign_pointer(mmph->hash, new);
 	}
 	kvfree_rcu(fph, rcu);
 
-chris

This matches my understanding of RCU. Although rcu_read_lock() will prevent a *new* RCU grace period from ending, it will not prevent an *old* one from ending or a new one from starting.

Thanx, Paul

#5 lore raw

Re: [PATCH] futex: sample poll cookie after publishing new hash

Quoted 91 lines · Paul E. McKenney
Quoted 90 lines · Chris Mason
Quoted 57 lines · Peter Zijlstra
Quoted 49 lines · Chris Mason

futex_ref_drop() may only skip its grace period when one has already elapsed since the current private hash was published:

    kernel/futex/core.c:futex_ref_drop
        if (poll_state_synchronize_rcu(mm->futex.phash.batches)) {
                /*
                 * There was a grace-period, we can begin now.
                 */
                __futex_ref_atomic_begin(fph);
                return;
        }

The cookie it polls is sampled one statement before that publication:

    kernel/futex/core.c:__futex_pivot_hash
        new->state = FR_PERCPU;
        scoped_guard(rcu) {
                mmph->batches = get_state_synchronize_rcu();
                rcu_assign_pointer(mmph->hash, new);
        }
        kvfree_rcu(fph, rcu);

get_state_synchronize_rcu() anchors its guarantee at the snapshot, so the cookie is cleared by the first grace period that starts from there on, including one starting between the two stores which never waited for a reader that loaded the old hash after it began.

    CPU 0 (resize)                    CPU 1 (futex_hash)
    ==============                    ==================
    __futex_pivot_hash()
      batches = get_state_...()
                                      grace period starts
                                      guard(rcu)
                                      fph = old hash
      rcu_assign_pointer(hash, new)
      kvfree_rcu(old hash)
    futex_hash_allocate()
      futex_ref_drop(new hash)
        poll_state_...() -> true
        __futex_ref_atomic_begin()
          atomic = LONG_MAX
                                      futex_ref_get(old hash) -> true
                                      spin_lock(&fph->queues[i].lock)

The reference count lives in the mm and has just been biased for the new generation, so the stalled reader pins and then locks the retired hash that is already queued for free, and its later put is charged against the live generation.

Quoted 6 lines

Fix by sampling the cookie after rcu_assign_pointer() publishes the new hash. Drop the surrounding scoped_guard(rcu) while at it: it only delayed completion of the prematurely anchored grace-period and serves no purpose once the cookie is sampled after publication. The writer side is serialized by mm->futex.phash.lock and neither rcu_assign_pointer() nor kvfree_rcu() requires a read-side section.

Quoted 7 lines

God, how I hate reading AI output :-(

Anyway, the thinking was that by holding rcu_read_lock(), the current RCU-GP cannot change and the cookie and assignment are effectively 'atomic'.

From what I can tell there are a few ways for new grace periods to start

while we're holding rcu_read_lock(), synchronize_rcu_expedited() if no GP is currently in flight being the easiest?

Anyway, this BUG_ON() fires for me:

kernel/futex/core.c +8 -0
index a061f54b6..18d51c145 100644
@@ -215,6 +215,14 @@ static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *
 	new->state = FR_PERCPU;
 	scoped_guard(rcu) {
 		mmph->batches = get_state_synchronize_rcu();
+		/*
+		 * Fires only if a grace period started after the cookie
+		 * above was taken, although rcu_read_lock() is held. That
+		 * grace period then satisfies the stored cookie, yet it began
+		 * before the new hash is published below.
+		 */
+		BUG_ON(!same_state_synchronize_rcu(mmph->batches,
+						   get_state_synchronize_rcu()));
 		rcu_assign_pointer(mmph->hash, new);
 	}
 	kvfree_rcu(fph, rcu);
Quoted 5 lines
Quoted 1 line

-chris

This matches my understanding of RCU. Although rcu_read_lock() will prevent a *new* RCU grace period from ending, it will not prevent an *old* one from ending or a new one from starting.

So, let us consider the dual counter RCU.

The RCU state is:

  counter[2];
  index;

rcu_read_lock() would increment counter[index & 1], rcu_read_unlock() would decrement whatever counter it incremented (say rcu_read_lock() returns the index, like SRCU does).

GP progression can either be sample or rcu_read_unlock() driven. Either way, when 'counter[!(index & 1)] == 0' is observed, there are no more observers of the old state (and callbacks can be ran).

At this point we can flip the counter and start anew: index++;

So index changes while counter[index & 1] != 0, which is somewhat fundamental to how the whole thing works.

Now, suppose get_state_synchronize_rcu() is simply returning a snapshot of 'index', then same_state_synchronize_rcu() can indeed trigger. The index can get advanced.

But that does not mean poll_state_synchronize_rcu() would return true; in the above scheme poll_state_synchronize_rcu() would be something like:

  if (index - snapshot < 2)
    return counter[snapshot & 1] == 0;

return true;

That is, not only does index need to advance, but also the counter needs to drain in order for it to report the GP is complete.

And this is where I went wrong, when we hold rcu_read_lock() we pin the counter and thus the GP cannot complete. But as I now see, that is not sufficient, because there can be observers of the old state in the next GP too.

So yes, the code is wrong and the patch is correct.

#6 lore raw

Re: [PATCH] futex: sample poll cookie after publishing new hash

Quoted 134 lines · Peter Zijlstra
Quoted 91 lines · Paul E. McKenney
Quoted 90 lines · Chris Mason
Quoted 57 lines · Peter Zijlstra
Quoted 49 lines · Chris Mason

futex_ref_drop() may only skip its grace period when one has already elapsed since the current private hash was published:

    kernel/futex/core.c:futex_ref_drop
        if (poll_state_synchronize_rcu(mm->futex.phash.batches)) {
                /*
                 * There was a grace-period, we can begin now.
                 */
                __futex_ref_atomic_begin(fph);
                return;
        }

The cookie it polls is sampled one statement before that publication:

    kernel/futex/core.c:__futex_pivot_hash
        new->state = FR_PERCPU;
        scoped_guard(rcu) {
                mmph->batches = get_state_synchronize_rcu();
                rcu_assign_pointer(mmph->hash, new);
        }
        kvfree_rcu(fph, rcu);

get_state_synchronize_rcu() anchors its guarantee at the snapshot, so the cookie is cleared by the first grace period that starts from there on, including one starting between the two stores which never waited for a reader that loaded the old hash after it began.

    CPU 0 (resize)                    CPU 1 (futex_hash)
    ==============                    ==================
    __futex_pivot_hash()
      batches = get_state_...()
                                      grace period starts
                                      guard(rcu)
                                      fph = old hash
      rcu_assign_pointer(hash, new)
      kvfree_rcu(old hash)
    futex_hash_allocate()
      futex_ref_drop(new hash)
        poll_state_...() -> true
        __futex_ref_atomic_begin()
          atomic = LONG_MAX
                                      futex_ref_get(old hash) -> true
                                      spin_lock(&fph->queues[i].lock)

The reference count lives in the mm and has just been biased for the new generation, so the stalled reader pins and then locks the retired hash that is already queued for free, and its later put is charged against the live generation.

Quoted 6 lines

Fix by sampling the cookie after rcu_assign_pointer() publishes the new hash. Drop the surrounding scoped_guard(rcu) while at it: it only delayed completion of the prematurely anchored grace-period and serves no purpose once the cookie is sampled after publication. The writer side is serialized by mm->futex.phash.lock and neither rcu_assign_pointer() nor kvfree_rcu() requires a read-side section.

Quoted 7 lines

God, how I hate reading AI output :-(

Anyway, the thinking was that by holding rcu_read_lock(), the current RCU-GP cannot change and the cookie and assignment are effectively 'atomic'.

From what I can tell there are a few ways for new grace periods to start

while we're holding rcu_read_lock(), synchronize_rcu_expedited() if no GP is currently in flight being the easiest?

Anyway, this BUG_ON() fires for me:

kernel/futex/core.c +8 -0
index a061f54b6..18d51c145 100644
@@ -215,6 +215,14 @@ static bool __futex_pivot_hash(struct mm_struct *mm, struct futex_private_hash *
 	new->state = FR_PERCPU;
 	scoped_guard(rcu) {
 		mmph->batches = get_state_synchronize_rcu();
+		/*
+		 * Fires only if a grace period started after the cookie
+		 * above was taken, although rcu_read_lock() is held. That
+		 * grace period then satisfies the stored cookie, yet it began
+		 * before the new hash is published below.
+		 */
+		BUG_ON(!same_state_synchronize_rcu(mmph->batches,
+						   get_state_synchronize_rcu()));
 		rcu_assign_pointer(mmph->hash, new);
 	}
 	kvfree_rcu(fph, rcu);
Quoted 5 lines
Quoted 1 line

-chris

This matches my understanding of RCU. Although rcu_read_lock() will prevent a *new* RCU grace period from ending, it will not prevent an *old* one from ending or a new one from starting.

So, let us consider the dual counter RCU.

The RCU state is:

  counter[2];
  index;

rcu_read_lock() would increment counter[index & 1], rcu_read_unlock() would decrement whatever counter it incremented (say rcu_read_lock() returns the index, like SRCU does).

GP progression can either be sample or rcu_read_unlock() driven. Either way, when 'counter[!(index & 1)] == 0' is observed, there are no more observers of the old state (and callbacks can be ran).

At this point we can flip the counter and start anew: index++;

So index changes while counter[index & 1] != 0, which is somewhat fundamental to how the whole thing works.

Now, suppose get_state_synchronize_rcu() is simply returning a snapshot of 'index', then same_state_synchronize_rcu() can indeed trigger. The index can get advanced.

But that does not mean poll_state_synchronize_rcu() would return true; in the above scheme poll_state_synchronize_rcu() would be something like:

  if (index - snapshot < 2)
    return counter[snapshot & 1] == 0;

return true;

That is, not only does index need to advance, but also the counter needs to drain in order for it to report the GP is complete.

Quoted 6 lines

And this is where I went wrong, when we hold rcu_read_lock() we pin the counter and thus the GP cannot complete. But as I now see, that is not sufficient, because there can be observers of the old state in the next GP too.

So yes, the code is wrong and the patch is correct.

Ok, I'll resend against recent git with a better commit message, unless you've already queued up something better suited?

-chris

#7 lore raw

Re: [PATCH] futex: sample poll cookie after publishing new hash

Quoted 2 lines · Chris Mason

Ok, I'll resend against recent git with a better commit message, unless you've already queued up something better suited?

If you would, that'd be great!