mm/list_lru: Optimize memcg_reparent_list_lru_node()
Subsystems (2)
PATCH v3 1/1 mm/list_lru: Optimize memcg_reparent_list_lru_node()
Since commit 2c80cd57c743 ("mm/list_lru.c: fix list_lru_count_node() to be race free"), we are tracking the total number of lru entries in a list_lru_node in its nr_items field. In the case of memcg_reparent_list_lru_node(), there is nothing to be done if nr_items is 0. We don't even need to take the nlru->lock as no new lru entry could be added by a racing list_lru_add() to the draining src_idx memcg at this point.
On systems that serve a lot of containers, it is possible that there can be thousands of list_lru's present due to the fact that each container may mount its own container specific filesystems. As a typical container uses only a few cpus, it is likely that only the list_lru_node that contains those cpus will be utilized while the rests may be empty. In other words, there can be a lot of list_lru_node with 0 nr_items. By skipping a lock/unlock operation and loading a cacheline from memcg_lrus, a sizeable number of cpu cycles can be saved. That can be substantial if we are talking about thousands of list_lru_node's with 0 nr_items.
--- mm/list_lru.c | 6 ++++++ 1 file changed, 6 insertions(+)
mm/list_lru.c +6 -0
@@ -394,6 +394,12 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid,int dst_idx = dst_memcg->kmemcg_id;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 · 1 line
2.27.0
Quoted 8 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.
Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight list_lru_add()? How about the following race?
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++IIUC, we use nlru->lock to serialise this scenario.
Thanks.
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.
I guess this race is theoretically possible but very unlikely since it means a very long pause between list_lru_from_kmem() and the increment of nr_items.
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0 -0
@@ -395,9 +395,10 @@ 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. + * If there is no lru entry in this nlru and the nlru->lock is free, + * we can skip it immediately.
*/
- if (!READ_ONCE(nlru->nr_items))
+ if (!READ_ONCE(nlru->nr_items) && !spin_is_locked(&nlru->lock)) return;
Cheers,
Longman
Quoted 31 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++
Quoted 5 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.
It is more possible in a VM.
Quoted 14 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-1@@ -395,9 +395,10 @@ 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.
mm/list_lru.c
Quoted 5 lines
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))
I think we also should insert a smp_rmb() between those two loads.
Thanks.
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;
Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.
Thinking about this some more, I believe that adding spin_is_locked() check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0 nr_items case. I will send out a patch to correct that. Thanks for bring this possible race to my attention.
Cheers,
Longman
Roman Gushchin
reviewerQuoted 58 lines · Waiman Long
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.
Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.
Yes, I think it's not enough:
CPU0 CPU1READ_ONCE(&nlru->nr_items) -> 0
spin_lock(&nlru->lock);
nlru->nr_items++;
spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
Getting back to the original patch, I wonder if instead we can batch reparenting of lrus so we don't have to grab and release nlru->lock for each reparenting lru.
Thanks!
Quoted 65 lines · Roman Gushchin
Quoted 57 lines · Waiman Long
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.
Quoted 7 lines
Yes, I think it's not enough:
CPU0 CPU1READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++; spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
I have actually thought of that. I am even thinking about reading nr_items again after spin_is_locked(). Still for arches with relaxed memory semantics, when will a memory write by one cpu be propagated to another cpu can be highly variable. It is very hard to prove that it is completely safe.
x86 has a more strict memory semantics and it is the only architecture that I have enough confidence that doing the check without taking a lock can be safe. Perhaps we could use this optimization just for x86 and do it inside locks for the rests.
Quoted 2 lines
Getting back to the original patch, I wonder if instead we can batch reparenting of lrus so we don't have to grab and release
nlru->lockfor each reparenting lru.
nlru is actually a sub-structure within a lru. So if there are m lrus and n nodes, we will have m*n nlrus. I don't believe there is anymore batching that can be done.
Cheers,
Longman
Roman Gushchin
reviewerQuoted 78 lines · Waiman Long
Quoted 65 lines · Roman Gushchin
Quoted 57 lines · Waiman Long
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.Quoted 7 lines
Yes, I think it's not enough:
CPU0 CPU1READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++; spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
I have actually thought of that. I am even thinking about reading
nr_itemsagain afterspin_is_locked(). Still for arches with relaxed memory semantics, when will a memory write by one cpu be propagated to another cpu can be highly variable. It is very hard to prove that it is completely safe.
Quoted 4 lines
x86 has a more strict memory semantics and it is the only architecture that I have enough confidence that doing the check without taking a lock can be safe. Perhaps we could use this optimization just for x86 and do it inside locks for the rests.
Hm, is this such a big problem in the real life? Can you describe the setup? I'm somewhat resistant to an idea of having arch-specific optimizations here without a HUGE reason.
Quoted 7 lines
Quoted 3 lines
Getting back to the original patch, I wonder if instead we can batch reparenting of lrus so we don't have to grab and release
nlru->lockfor each reparenting lru.nlru is actually a sub-structure within a lru. So if there are m lrus and n nodes, we will have m*n nlrus. I don't believe there is anymore batching that can be done.
I need to think, I'll share any ideas/patches if there will be any.
Thanks!
Quoted 79 lines · Roman Gushchin
Quoted 78 lines · Waiman Long
Quoted 65 lines · Roman Gushchin
Quoted 57 lines · Waiman Long
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.Quoted 7 lines
Yes, I think it's not enough:
CPU0 CPU1READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++; spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
I have actually thought of that. I am even thinking about reading
nr_itemsagain afterspin_is_locked(). Still for arches with relaxed memory semantics, when will a memory write by one cpu be propagated to another cpu can be highly variable. It is very hard to prove that it is completely safe.
Quoted 7 lines
Quoted 4 lines
x86 has a more strict memory semantics and it is the only architecture that I have enough confidence that doing the check without taking a lock can be safe. Perhaps we could use this optimization just for x86 and do it inside locks for the rests.
Hm, is this such a big problem in the real life? Can you describe the setup? I'm somewhat resistant to an idea of having arch-specific optimizations here without a HUGE reason.
I am just throwing this idea out for discussion. It does not mean that I want to do an arch specific patch unless there is performance data to indicate a substantial gain in performance in some use cases.
Cheers,
Longman
Roman Gushchin
reviewerQuoted 84 lines · Waiman Long
Quoted 83 lines · Roman Gushchin
Quoted 82 lines · Waiman Long
Quoted 65 lines · Roman Gushchin
Quoted 57 lines · Waiman Long
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.Quoted 7 lines
Yes, I think it's not enough:
CPU0 CPU1READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++; spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
I have actually thought of that. I am even thinking about reading
nr_itemsagain afterspin_is_locked(). Still for arches with relaxed memory semantics, when will a memory write by one cpu be propagated to another cpu can be highly variable. It is very hard to prove that it is completely safe.x86 has a more strict memory semantics and it is the only architecture that I have enough confidence that doing the check without taking a lock can be safe. Perhaps we could use this optimization just for x86 and do it inside locks for the rests.
Quoted 7 lines
Quoted 3 lines
Hm, is this such a big problem in the real life? Can you describe the setup? I'm somewhat resistant to an idea of having arch-specific optimizations here without a HUGE reason.
I am just throwing this idea out for discussion. It does not mean that I want to do an arch specific patch unless there is performance data to indicate a substantial gain in performance in some use cases.
Got it!
I mean it's not obvious from the original commit message if it's just a nice optimization or there was a real life problem. In the first case the best thing is probably to leave everything as it is now, in the latter we need to do something. I'm trying to understand which case it is.
Thanks!
Quoted 68 lines · Roman Gushchin
Quoted 58 lines · Waiman Long
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.
Quoted 1 line
Yes, I think it's not enough:
I think it may be enough if we insert a smp_rmb() between those two loads.
Quoted 4 lines
CPU0 CPU1
READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++;
^^^
|||
The nlr here is not thesame as the one in CPU0,
since CPU0 have done the
memcg reparting. Then
CPU0 will not miss nlru
reparting. If I am wrong, please
correct me. Thanks.
Quoted 2 lines
spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
Roman Gushchin
reviewerQuoted 80 lines · Muchun Song
Quoted 68 lines · Roman Gushchin
Quoted 58 lines · Waiman Long
Quoted 47 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 10 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-0@@ -395,9 +395,10 @@ static void memcg_reparent_list_lru_node(struct list_lru *lru, int nid, struct list_lru_one *src, *dst;Quoted 9 lines
mm/list_lru.c
Quoted 8 lines
mm/list_lru.c +0
-1/* -* If there is no lru entry in this nlru, we can skip it immediately.
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.Quoted 1 line
Yes, I think it's not enough:
I think it may be enough if we insert a
smp_rmb()between those two loads.Quoted 4 lines
CPU0 CPU1
READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++;^^^ ||| The nlr here is not the
Quoted 8 lines
same as the one in CPU0,
since CPU0 have done the
memcg reparting. Then
CPU0 will not miss nlru
reparting. If I am wrong, please
correct me. Thanks.Quoted 2 lines
spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
Indeed, you're right.
Thanks!
Quoted 76 lines · Muchun Song
Quoted 58 lines · Roman Gushchin
Quoted 57 lines · Waiman Long
Quoted 56 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 13 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-1@@ -395,9 +395,10 @@ 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.
mm/list_lru.c
Quoted 5 lines
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 8 lines
Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.Yes, I think it's not enough:
I think it may be enough if we insert a
smp_rmb()between those two loads.Quoted 4 lines
CPU0 CPU1
READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++;^^^ ||| The nlr here is not the
Quoted 8 lines
same as the one in CPU0,
since CPU0 have done the
memcg reparting. Then
CPU0 will not miss nlru
reparting. If I am wrong, please
correct me. Thanks.Quoted 2 lines
spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
I just realize that there is another lock/unlock pair in memcg_reparent_objcgs():
memcg_reparent_objcgs()
spin_lock_irq()
memcg reparenting
spin_unlock_irq()
percpu_ref_kill()
spin_lock_irqsave()
...
spin_unlock_irqrestore()
This lock/unlock pair in percpu_ref_kill() will stop the reordering of read/write before the memcg reparenting. Now I think just adding a spin_is_locked() check with smp_rmb() should be enough. However, I would like to change the ordering like that:
if (!spin_is_locked(&nlru->lock)) {
smp_rmb();
if (!READ_ONCE(nlru->nr_items))
return;
}
Otherwise, we will have the problem
list_lru_add()
spin_lock(&nlru->lock)
l = list_lru_from_kmem(memcg) READ_ONCE(nlru->nr_items);
// Assume 0->1
l->nr_items++
// Assume 0->1
nlru->nr_items++ spin_unlock(&nlru->lock) spin_is_locked()
If spin_is_locked() is before spin_lock() in list_lru_add(), list_lru_from_kmem() is guarantee to get the reparented memcg and so won't added to the reparented lru.
Thanks,
Longman
Quoted 104 lines · Waiman Long
Quoted 76 lines · Muchun Song
Quoted 58 lines · Roman Gushchin
Quoted 57 lines · Waiman Long
Quoted 56 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 13 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-1@@ -395,9 +395,10 @@ 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.
mm/list_lru.c
Quoted 5 lines
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 8 lines
Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.Yes, I think it's not enough:
I think it may be enough if we insert a
smp_rmb()between those two loads.Quoted 4 lines
CPU0 CPU1
READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++;^^^ ||| The nlr here is not theQuoted 8 lines
same as the one in CPU0,
since CPU0 have done the
memcg reparting. Then
CPU0 will not miss nlru
reparting. If I am wrong, please
correct me. Thanks.Quoted 2 lines
spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
I just realize that there is another lock/unlock pair in
memcg_reparent_objcgs():
memcg_reparent_objcgs()spin_lock_irq() memcg reparenting spin_unlock_irq() percpu_ref_kill() spin_lock_irqsave() ... spin_unlock_irqrestore()This lock/unlock pair in
percpu_ref_kill()will stop the reordering of read/write before the memcg reparenting. Now I think just adding aspin_is_locked()check withsmp_rmb()should be enough. However, I would like to change the ordering like that:
Quoted 5 lines
if (!spin_is_locked(&nlru->lock)) {
smp_rmb();
if (!READ_ONCE(nlru->nr_items))
return;
}Does the following race still exist?
CPU0: CPU1:
spin_is_locked(&nlru->lock)
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++Quoted 6 lines
Otherwise, we will have the problem
list_lru_add()
spin_lock(&nlru->lock)
l =list_lru_from_kmem(memcg)
Quoted 7 lines
READ_ONCE(nlru->nr_items);
// Assume 0->1
l->nr_items++
// Assume 0->1
nlru->nr_items++
spin_unlock(&nlru->lock)
spin_is_locked()You are right.
Quoted 5 lines
If
spin_is_locked()is beforespin_lock()inlist_lru_add(),list_lru_from_kmem()is guarantee to get the reparented memcg and so won't added to the reparented lru.
Quoted 106 lines · Muchun Song
Quoted 104 lines · Waiman Long
Quoted 76 lines · Muchun Song
Quoted 58 lines · Roman Gushchin
Quoted 57 lines · Waiman Long
Quoted 56 lines · Muchun Song
Quoted 30 lines · Waiman Long
Quoted 29 lines · Muchun Song
Quoted 7 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++Quoted 4 lines
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.I guess this race is theoretically possible but very unlikely since it means a very long pause between
list_lru_from_kmem()and the increment ofnr_items.It is more possible in a VM.
Quoted 13 lines
How about the following changes to make sure that this race can't happen?
mm/list_lru.c +0
-1@@ -395,9 +395,10 @@ 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.
mm/list_lru.c
Quoted 5 lines
mm/list_lru.c +3
-1+* If there is no lru entry in this nlru and the nlru->lock is free, +* we can skip it immediately. */ -if (!READ_ONCE (nlru->nr_items)) +if (!READ_ONCE (nlru->nr_items) && !spin_is_locked (&nlru->lock))I think we also should insert a
smp_rmb()between those two loads.Quoted 8 lines
Quoted 7 lines
Thinking about this some more, I believe that adding
spin_is_locked()check will be enough for x86. However, that will likely not be enough for arches with a more relaxed memory semantics. So the safest way to avoid this possible race is to move the check to within the lock critical section, though that comes with a slightly higher overhead for the 0nr_itemscase. I will send out a patch to correct that. Thanks for bring this possible race to my attention.Yes, I think it's not enough:
I think it may be enough if we insert a
smp_rmb()between those two loads.Quoted 4 lines
CPU0 CPU1
READ_ONCE(&nlru->nr_items)-> 0spin_lock(&nlru->lock); nlru->nr_items++;^^^ ||| The nlr here is not theQuoted 8 lines
same as the one in CPU0,
since CPU0 have done the
memcg reparting. Then
CPU0 will not miss nlru
reparting. If I am wrong, please
correct me. Thanks.Quoted 2 lines
spin_unlock(&nlru->lock);&& !spin_is_locked(&nlru->lock) -> 0
I just realize that there is another lock/unlock pair in
memcg_reparent_objcgs():
memcg_reparent_objcgs()spin_lock_irq() memcg reparenting spin_unlock_irq() percpu_ref_kill() spin_lock_irqsave() ... spin_unlock_irqrestore()This lock/unlock pair in
percpu_ref_kill()will stop the reordering of read/write before the memcg reparenting. Now I think just adding aspin_is_locked()check withsmp_rmb()should be enough. However, I would like to change the ordering like that:
Quoted 7 lines
Quoted 5 lines
if (!spin_is_locked(&nlru->lock)) { smp_rmb(); if (!READ_ONCE(nlru->nr_items)) return; }Does the following race still exist?
Ignore this. My bad. I think your approach could work.
Quoted 40 lines
CPU0: CPU1:
spin_is_locked(&nlru->lock)
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++Quoted 6 lines
Otherwise, we will have the problem
list_lru_add()
spin_lock(&nlru->lock)
l =list_lru_from_kmem(memcg)Quoted 7 lines
READ_ONCE(nlru->nr_items); // Assume 0->1 l->nr_items++ // Assume 0->1 nlru->nr_items++ spin_unlock(&nlru->lock) spin_is_locked()You are right.
Quoted 5 lines
If
spin_is_locked()is beforespin_lock()inlist_lru_add(),list_lru_from_kmem()is guarantee to get the reparented memcg and so won't added to the reparented lru.
Roman Gushchin
reviewerQuoted 31 lines · Muchun Song
Quoted 8 lines · Waiman Long
Since commit
2c80cd57c743("mm/list_lru.c: fixlist_lru_count_node()to be race free"), we are tracking the total number of lru entries in alist_lru_nodein itsnr_itemsfield. In the case ofmemcg_reparent_list_lru_node(), there is nothing to be done ifnr_itemsis 0. We don't even need to take thenlru->lockas no new lru entry could be added by a racinglist_lru_add()to the drainingsrc_idxmemcg at this point.Hi Waiman,
Sorry for the late reply. Quick question: what if there is an inflight
list_lru_add()? How about the following race?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++
Quoted 1 line
IIUC, we use
nlru->lockto serialise this scenario.
Thank you for bringing this up, really cool race!