Skip to contentSkip to conversation

mm/list_lru: Fix possible race in memcg_reparent_list_lru_node()

PATCH In review Waiman Long 6 participants 10 messages Mar 30, 2022 – Apr 1, 2022

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 mm/list_lru: Fix possible race in memcg_reparent_list_lru_node()

Muchun Song found out there could be a race between list_lru_add() and memcg_reparent_list_lru_node() causing the later function to miss reparenting of a lru entry as shown below:

CPU0: CPU1:
list_lru_add()

    spin_lock(&nlru->lock)
    l = list_lru_from_kmem(memcg)
                                memcg_reparent_objcgs(memcg)
                                memcg_reparent_list_lrus(memcg)
                                    memcg_reparent_list_lru()
                                        memcg_reparent_list_lru_node()
                                            if (!READ_ONCE(nlru->nr_items))
                                                // Miss reparenting
                                                return
    // Assume 0->1
    l->nr_items++
    // Assume 0->1
    nlru->nr_items++

Though it is not likely that a list_lru_node that has 0 item suddenly has a newly added lru entry at the end of its life. The race is still theoretically possible.

With the lock/unlock pair used within the percpu_ref_kill() which is the last function call of memcg_reparent_objcgs(), any read issued in memcg_reparent_list_lru_node() will not be reordered before the reparenting of objcgs.

Adding a !spin_is_locked()/smp_rmb()/!READ_ONCE(nlru->nr_items) check to ensure that either the reading of nr_items is valid or the racing list_lru_add() will see the reparented objcg.

Fixes 405cc51fc104 ("mm/list_lru: optimize memcg_reparent_list_lru_node()")
---
 mm/list_lru.c | 31 +++++++++++++++++++++++++++----
 1 file changed, 27 insertions(+), 4 deletions(-)
mm/list_lru.c +27 -4
index c669d87001a6..08ff54ffabd6 100644
@@ -395,10 +395,33 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid,
 	struct list_lru_one *src, *dst;
 
 	/*
-	 * If there is no lru entry in this nlru, we can skip it immediately.
+	 * With the lock/unlock pair used within the percpu_ref_kill()
+	 * which is the last function call of memcg_reparent_objcgs(), any
+	 * read issued here will not be reordered before the reparenting
+	 * of objcgs.
+	 *
+	 * Assuming a racing list_lru_add():
+	 * list_lru_add()
+	 *				<- memcg_reparent_list_lru_node()
+	 *   spin_lock(&nlru->lock)
+	 *   l = list_lru_from_kmem(memcg)
+	 *   nlru->nr_items++
+	 *   spin_unlock(&nlru->lock)
+	 *				<- memcg_reparent_list_lru_node()
+	 *
+	 * The !spin_is_locked(&nlru->lock) check is true means it is
+	 * either before the spin_lock() or after the spin_unlock(). In the
+	 * former case, list_lru_add() will see the reparented objcg and so
+	 * won't touch the lru to be reparented. In the later case, it will
+	 * see the updated nr_items. So we can use the optimization that if
+	 * there is no lru entry in this nlru, skip it immediately.
 	 */
-	if (!READ_ONCE(nlru->nr_items))
-		return;
+	if (!spin_is_locked(&nlru->lock)) {
+		/* nr_items read must be ordered after nlru->lock */
+		smp_rmb();
+		if (!READ_ONCE(nlru->nr_items))
+			return;
+	}
 
 	/*
 	 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
@@ -407,7 +430,7 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid,
 	spin_lock_irq(&nlru->lock);
 
 	src = list_lru_from_memcg_idx(lru, nid, src_idx);
-	if (!src)
+	if (!src || !src->nr_items)
 		goto out;
 	dst = list_lru_from_memcg_idx(lru, nid, dst_idx);
 
Signature · 1 line
2.27.0
reviewer Acked-by on v2 1/1
#1 lore raw
Quoted 29 lines · Waiman Long

Muchun Song found out there could be a race between list_lru_add() and memcg_reparent_list_lru_node() causing the later function to miss reparenting of a lru entry as shown below:

CPU0: CPU1:
list_lru_add()

    spin_lock(&nlru->lock)
    l = list_lru_from_kmem(memcg)
                                memcg_reparent_objcgs(memcg)
                                memcg_reparent_list_lrus(memcg)
                                    memcg_reparent_list_lru()
                                        memcg_reparent_list_lru_node()
                                            if (!READ_ONCE(nlru->nr_items))
                                                // Miss reparenting
                                                return
    // Assume 0->1
    l->nr_items++
    // Assume 0->1
    nlru->nr_items++

Though it is not likely that a list_lru_node that has 0 item suddenly has a newly added lru entry at the end of its life. The race is still theoretically possible.

With the lock/unlock pair used within the percpu_ref_kill() which is the last function call of memcg_reparent_objcgs(), any read issued in memcg_reparent_list_lru_node() will not be reordered before the reparenting of objcgs.

Quoted 7 lines

Adding a !spin_is_locked()/smp_rmb()/!READ_ONCE(nlru->nr_items) check to ensure that either the reading of nr_items is valid or the racing list_lru_add() will see the reparented objcg.

Fixes 405cc51fc104 ("mm/list_lru: optimize memcg_reparent_list_lru_node()")
maintainer
#2 lore raw
In reply to Waiman Long
Quoted 56 lines · On Wed, 30 Mar 2022 13:26:46 -0400 Waiman Long <[email protected]> wrote:

Muchun Song found out there could be a race between list_lru_add() and memcg_reparent_list_lru_node() causing the later function to miss reparenting of a lru entry as shown below:

CPU0: CPU1:
list_lru_add()

    spin_lock(&nlru->lock)
    l = list_lru_from_kmem(memcg)
                                memcg_reparent_objcgs(memcg)
                                memcg_reparent_list_lrus(memcg)
                                    memcg_reparent_list_lru()
                                        memcg_reparent_list_lru_node()
                                            if (!READ_ONCE(nlru->nr_items))
                                                // Miss reparenting
                                                return
    // Assume 0->1
    l->nr_items++
    // Assume 0->1
    nlru->nr_items++

Though it is not likely that a list_lru_node that has 0 item suddenly has a newly added lru entry at the end of its life. The race is still theoretically possible.

With the lock/unlock pair used within the percpu_ref_kill() which is the last function call of memcg_reparent_objcgs(), any read issued in memcg_reparent_list_lru_node() will not be reordered before the reparenting of objcgs.

Adding a !spin_is_locked()/smp_rmb()/!READ_ONCE(nlru->nr_items) check to ensure that either the reading of nr_items is valid or the racing list_lru_add() will see the reparented objcg.

...

mm/list_lru.c +14 -1
@@ -395,10 +395,33 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid,
 	struct list_lru_one *src, *dst;
 
 	/*
-	 * If there is no lru entry in this nlru, we can skip it immediately.
+	 * With the lock/unlock pair used within the percpu_ref_kill()
+	 * which is the last function call of memcg_reparent_objcgs(), any
+	 * read issued here will not be reordered before the reparenting
+	 * of objcgs.
+	 *
+	 * Assuming a racing list_lru_add():
+	 * list_lru_add()
+	 *				<- memcg_reparent_list_lru_node()
+	 *   spin_lock(&nlru->lock)
+	 *   l = list_lru_from_kmem(memcg)
+	 *   nlru->nr_items++
+	 *   spin_unlock(&nlru->lock)
+	 *				<- memcg_reparent_list_lru_node()
+	 *

mm/list_lru.c static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, · line 419

Quoted 10 lines
mm/list_lru.c +7 -2
+	 * The !spin_is_locked(&nlru->lock) check is true means it is
+	 * either before the spin_lock() or after the spin_unlock(). In the
+	 * former case, list_lru_add() will see the reparented objcg and so
+	 * won't touch the lru to be reparented. In the later case, it will
+	 * see the updated nr_items. So we can use the optimization that if
+	 * there is no lru entry in this nlru, skip it immediately.
 	 */
-	if (!READ_ONCE(nlru->nr_items))
-		return;
+	if (!spin_is_locked(&nlru->lock)) {

ick.

mm/list_lru.c static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, · line 424

Quoted 5 lines
mm/list_lru.c +5 -0
+		/* nr_items read must be ordered after nlru->lock */
+		smp_rmb();
+		if (!READ_ONCE(nlru->nr_items))
+			return;
+	}

include/linux/spinlock_up.h has

#define arch_spin_is_locked(lock) ((void)(lock), 0)

so this `if' will always be true on CONFIG_SMP=n. Will the kernel still work?

At the very least let's have changelogging and commenting explaining that we've actually thought about this.

Preferably, can we fix this hole properly and avoid this hack? There is a reason for this:

hp2:/usr/src/25> grep spin_is_locked mm/*.c
hp2:/usr/src/25>

#3 lore raw
Quoted 81 lines · Andrew Morton
Quoted 56 lines · On Wed, 30 Mar 2022 13:26:46 -0400 Waiman Long <[email protected]> wrote:

Muchun Song found out there could be a race between list_lru_add() and memcg_reparent_list_lru_node() causing the later function to miss reparenting of a lru entry as shown below:

CPU0: CPU1:
list_lru_add()
spin_lock(&nlru->lock)
l = list_lru_from_kmem(memcg)

                               memcg_reparent_objcgs(memcg)
                               memcg_reparent_list_lrus(memcg)
                                   memcg_reparent_list_lru()
                                       memcg_reparent_list_lru_node()
                                           if (!READ_ONCE(nlru->nr_items))
                                               // Miss reparenting
                                               return

// Assume 0->1
l->nr_items++
// Assume 0->1
nlru->nr_items++

Though it is not likely that a list_lru_node that has 0 item suddenly has a newly added lru entry at the end of its life. The race is still theoretically possible.

With the lock/unlock pair used within the percpu_ref_kill() which is the last function call of memcg_reparent_objcgs(), any read issued in memcg_reparent_list_lru_node() will not be reordered before the reparenting of objcgs.

Adding a !spin_is_locked()/smp_rmb()/!READ_ONCE(nlru->nr_items) check to ensure that either the reading of nr_items is valid or the racing list_lru_add() will see the reparented objcg.

...

mm/list_lru.c +14 -1
@@ -395,10 +395,33 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid,
   struct list_lru_one *src, *dst;
 
   /*
-     * If there is no lru entry in this nlru, we can skip it immediately.
+     * With the lock/unlock pair used within the percpu_ref_kill()
+     * which is the last function call of memcg_reparent_objcgs(), any
+     * read issued here will not be reordered before the reparenting
+     * of objcgs.
+     *
+     * Assuming a racing list_lru_add():
+     * list_lru_add()
+     *                <- memcg_reparent_list_lru_node()
+     *   spin_lock(&nlru->lock)
+     *   l = list_lru_from_kmem(memcg)
+     *   nlru->nr_items++
+     *   spin_unlock(&nlru->lock)
+     *                <- memcg_reparent_list_lru_node()
+     *

mm/list_lru.c static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, · line 419

Quoted 10 lines
mm/list_lru.c +7 -2
+     * The !spin_is_locked(&nlru->lock) check is true means it is
+     * either before the spin_lock() or after the spin_unlock(). In the
+     * former case, list_lru_add() will see the reparented objcg and so
+     * won't touch the lru to be reparented. In the later case, it will
+     * see the updated nr_items. So we can use the optimization that if
+     * there is no lru entry in this nlru, skip it immediately.
    */
-    if (!READ_ONCE(nlru->nr_items))
-        return;
+    if (!spin_is_locked(&nlru->lock)) {

ick.

mm/list_lru.c static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, · line 424

Quoted 5 lines
mm/list_lru.c +5 -0
+        /* nr_items read must be ordered after nlru->lock */
+        smp_rmb();
+        if (!READ_ONCE(nlru->nr_items))
+            return;
+    }
Quoted 6 lines

include/linux/spinlock_up.h has

#define arch_spin_is_locked(lock) ((void)(lock), 0)

so this `if' will always be true on CONFIG_SMP=n. Will the kernel still work?

I guess yes, because this race is not possible on a !smp machine.

Quoted 9 lines

At the very least let's have changelogging and commenting explaining that we've actually thought about this.

Preferably, can we fix this hole properly and avoid this hack? There is a reason for this:

hp2:/usr/src/25> grep spin_is_locked mm/*.c
hp2:/usr/src/25>

But honestly, I’d drop the original optimization together with the fix, if only there is no _real world_ data on the problem and the improvement. It seems like it has started as a nice simple improvement, but the race makes it complex and probably not worth the added complexity and fragility.

Thanks!

#4 lore raw
Quoted 2 lines · Roman Gushchin

[...]

Quoted 3 lines

But honestly, I’d drop the original optimization together with the fix, if only there is no _real world_ data on the problem and the improvement. It seems like it has started as a nice simple improvement, but the race makes it complex and probably not worth the added complexity and fragility.

I agree with dropping the original optimization as it is not really fixing an observed issue which may justify adding some complexity.

thanks,
Shakeel

#5 lore raw
Quoted 6 lines · Shakeel Butt
Quoted 2 lines · Roman Gushchin

[...]

Quoted 2 lines
Quoted 8 lines
Quoted 5 lines

But honestly, I’d drop the original optimization together with the fix, if only there is no _real world_ data on the problem and the improvement. It seems like it has started as a nice simple improvement, but the race makes it complex and probably not worth the added complexity and fragility.

I agree with dropping the original optimization as it is not really fixing an observed issue which may justify adding some complexity.

Completely agreed. The patch as it is proposed is not really acceptable IMHO and I have to say I am worried that this is not the first time we are in a situation when a follow up fixes or unrelated patches are growing in complexity to fit on top of a performance optimizations which do not refer to any actual numbers.

Signature · 2 lines
Michal Hocko
SUSE Labs
maintainer
#6 lore raw
Quoted 13 lines · On Thu, 31 Mar 2022 09:46:52 +0200 Michal Hocko <[email protected]> wrote:
Quoted 12 lines · Shakeel Butt
Quoted 2 lines · Roman Gushchin

[...]

Quoted 7 lines

But honestly, I’d drop the original optimization together with the fix, if only there is no _real world_ data on the problem and the improvement. It seems like it has started as a nice simple improvement, but the race makes it complex and probably not worth the added complexity and fragility.

Quoted 8 lines
Quoted 2 lines

I agree with dropping the original optimization as it is not really fixing an observed issue which may justify adding some complexity.

Completely agreed. The patch as it is proposed is not really acceptable IMHO and I have to say I am worried that this is not the first time we are in a situation when a follow up fixes or unrelated patches are growing in complexity to fit on top of a performance optimizations which do not refer to any actual numbers.

Yup. I did this:

From: Andrew Morton <[email protected]>
Subject: mm/list_lru.c: revert "mm/list_lru: optimize memcg_reparent_list_lru_node()"

405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()") has subtle races which are proving ugly to fix. Revert the original optimization. If quantitative testing indicates that we have a significant problem here then other implementations can be looked at.

Fixes 405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()")
Cc Waiman Long <[email protected]>
Cc Roman Gushchin <[email protected]>
Cc Muchun Song <[email protected]>
Cc Michal Hocko <[email protected]>
Cc Johannes Weiner <[email protected]>
Cc Shakeel Butt <[email protected]>

---

 mm/list_lru.c |    6 ------
 1 file changed, 6 deletions(-)
mm/list_lru.c renamed from mm/list_lru.c~revert-1 +0 -6
@@ -395,12 +395,6 @@ static void memcg_reparent_list_lru_node
 	struct list_lru_one *src, *dst;
 
 	/*
-	 * If there is no lru entry in this nlru, we can skip it immediately.
-	 */
-	if (!READ_ONCE(nlru->nr_items))
-		return;
-
-	/*
 	 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
 	 * we have to use IRQ-safe primitives here to avoid deadlock.
 	 */

_

Acked-by
#7 lore raw
Quoted 35 lines · Andrew Morton
Quoted 13 lines · On Thu, 31 Mar 2022 09:46:52 +0200 Michal Hocko <[email protected]> wrote:
Quoted 12 lines · Shakeel Butt
Quoted 2 lines · Roman Gushchin

[...]

Quoted 7 lines

But honestly, I’d drop the original optimization together with the fix, if only there is no _real world_ data on the problem and the improvement. It seems like it has started as a nice simple improvement, but the race makes it complex and probably not worth the added complexity and fragility.

Quoted 8 lines
Quoted 2 lines

I agree with dropping the original optimization as it is not really fixing an observed issue which may justify adding some complexity.

Completely agreed. The patch as it is proposed is not really acceptable IMHO and I have to say I am worried that this is not the first time we are in a situation when a follow up fixes or unrelated patches are growing in complexity to fit on top of a performance optimizations which do not refer to any actual numbers.

Yup. I did this:

From: Andrew Morton <[email protected]>
Subject: mm/list_lru.c: revert "mm/list_lru: optimize memcg_reparent_list_lru_node()"

405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()") has subtle races which are proving ugly to fix. Revert the original optimization. If quantitative testing indicates that we have a significant problem here then other implementations can be looked at.

Quoted 8 lines
Fixes 405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()")
Cc Waiman Long <[email protected]>
Cc Roman Gushchin <[email protected]>
Cc Muchun Song <[email protected]>
Cc Michal Hocko <[email protected]>
Cc Johannes Weiner <[email protected]>
Cc Shakeel Butt <[email protected]>
Reviewed-by
#8 lore raw
In reply to Andrew Morton
Quoted 35 lines · Andrew Morton
Quoted 13 lines · On Thu, 31 Mar 2022 09:46:52 +0200 Michal Hocko <[email protected]> wrote:
Quoted 12 lines · Shakeel Butt
Quoted 2 lines · Roman Gushchin

[...]

Quoted 7 lines

But honestly, I’d drop the original optimization together with the fix, if only there is no _real world_ data on the problem and the improvement. It seems like it has started as a nice simple improvement, but the race makes it complex and probably not worth the added complexity and fragility.

Quoted 8 lines
Quoted 2 lines

I agree with dropping the original optimization as it is not really fixing an observed issue which may justify adding some complexity.

Completely agreed. The patch as it is proposed is not really acceptable IMHO and I have to say I am worried that this is not the first time we are in a situation when a follow up fixes or unrelated patches are growing in complexity to fit on top of a performance optimizations which do not refer to any actual numbers.

Yup. I did this:

From: Andrew Morton <[email protected]>
Subject: mm/list_lru.c: revert "mm/list_lru: optimize memcg_reparent_list_lru_node()"

405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()") has subtle races which are proving ugly to fix. Revert the original optimization. If quantitative testing indicates that we have a significant problem here then other implementations can be looked at.

Quoted 8 lines
Fixes 405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()")
Cc Waiman Long <[email protected]>
Cc Roman Gushchin <[email protected]>
Cc Muchun Song <[email protected]>
Cc Michal Hocko <[email protected]>
Cc Johannes Weiner <[email protected]>
Cc Shakeel Butt <[email protected]>
Acked-by
#9 lore raw
In reply to Andrew Morton

On Thu 31-03-22 18:11:26, Andrew Morton wrote:
[...]

Quoted 10 lines

Yup. I did this:

From: Andrew Morton <[email protected]>
Subject: mm/list_lru.c: revert "mm/list_lru: optimize memcg_reparent_list_lru_node()"

405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()") has subtle races which are proving ugly to fix. Revert the original optimization. If quantitative testing indicates that we have a significant problem here then other implementations can be looked at.

Quoted 8 lines
Fixes 405cc51fc1049c73 ("mm/list_lru: optimize memcg_reparent_list_lru_node()")
Cc Waiman Long <[email protected]>
Cc Roman Gushchin <[email protected]>
Cc Muchun Song <[email protected]>
Cc Michal Hocko <[email protected]>
Cc Johannes Weiner <[email protected]>
Cc Shakeel Butt <[email protected]>

Thanks!

Quoted 21 lines

---

 mm/list_lru.c |    6 ------
 1 file changed, 6 deletions(-)
mm/list_lru.c renamed from mm/list_lru.c~revert-1 +0 -6
@@ -395,12 +395,6 @@ static void memcg_reparent_list_lru_node
 	struct list_lru_one *src, *dst;
 
 	/*
-	 * If there is no lru entry in this nlru, we can skip it immediately.
-	 */
-	if (!READ_ONCE(nlru->nr_items))
-		return;
-
-	/*
 	 * Since list_lru_{add,del} may be called under an IRQ-safe lock,
 	 * we have to use IRQ-safe primitives here to avoid deadlock.
 	 */

_

Signature · 2 lines
Michal Hocko
SUSE Labs