memcg: fix and reimplement iterator

mm/memcontrol.c +3 -1

@@ -1218,9 +1218,18 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 			 * is alive.
 			 */
 			dead_count = atomic_read(&root->dead_count);
-			smp_rmb();
+
 			last_visited = iter->last_visited;
 			if (last_visited) {
+				/*
+				 * Paired with smp_wmb() below in this

mm/memcontrol.c +1 -0

@@ -1235,6 +1244,7 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 				css_put(&last_visited->css);
 
 			iter->last_visited = memcg;
+			/* paired with smp_rmb() above in this function */
 			smp_wmb();
 			iter->last_dead_count = dead_count;
 

Signature · 1 line

1.8.2.1

On Mon 03-06-13 17:44:37, Tejun Heo wrote:
[...]

Quoted 10 lines

(quoted diff) +3 -1

@@ -1218,9 +1218,18 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 			 * is alive.
 			 */
 			dead_count = atomic_read(&root->dead_count);
-			smp_rmb();
+
 			last_visited = iter->last_visited;
 			if (last_visited) {
+				/*
+				 * Paired with smp_wmb() below in this

Review struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root, · line 1235

Quoted 10 lines

(quoted diff) +7 -0

+				 * function.  The pair guarantee that
+				 * last_visited is more current than
+				 * last_dead_count, which may lead to
+				 * spurious iteration resets but guarantees
+				 * reliable detection of dead condition.
+				 */
+				smp_rmb();
 				if ((dead_count != iter->last_dead_count) ||
 					!css_tryget(&last_visited->css)) {
 					last_visited = NULL;

I originally had the barrier this way but Johannes pointed out it is not correct https://lkml.org/lkml/2013/2/11/411
"
!> + /*
!> + * last_visited might be invalid if some of the group
!> + * downwards was removed. As we do not know which one
!> + * disappeared we have to start all over again from the
!> + * root.
!> + * css ref count then makes sure that css won't
!> + * disappear while we iterate to the next memcg
!> + */
!> + last_visited = iter->last_visited;
!> + dead_count = atomic_read(&root->dead_count);
!> + smp_rmb();
!
!Confused about this barrier, see below.
!

!As per above, if you remove the iter lock, those lines are mixed up. !You need to read the dead count first because the writer updates the !dead count after it sets the new position. That way, if the dead !count gives the go-ahead, you KNOW that the position cache is valid, !because it has been updated first. If either the two reads or the two !writes get reordered, you risk seeing a matching dead count while the !position cache is stale.
"

Quoted 40 lines · Michal Hocko

On Mon 03-06-13 17:44:37, Tejun Heo wrote:
[...]

Quoted 10 lines

(quoted diff) +3 -1

@@ -1218,9 +1218,18 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 			 * is alive.
 			 */
 			dead_count = atomic_read(&root->dead_count);
-			smp_rmb();
+
 			last_visited = iter->last_visited;
 			if (last_visited) {
+				/*
+				 * Paired with smp_wmb() below in this

Review struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root, · line 1235

Quoted 10 lines

(quoted diff) +7 -0

+				 * function.  The pair guarantee that
+				 * last_visited is more current than
+				 * last_dead_count, which may lead to
+				 * spurious iteration resets but guarantees
+				 * reliable detection of dead condition.
+				 */
+				smp_rmb();
 				if ((dead_count != iter->last_dead_count) ||
 					!css_tryget(&last_visited->css)) {
 					last_visited = NULL;

I originally had the barrier this way but Johannes pointed out it is not correct https://lkml.org/lkml/2013/2/11/411
"
!> + /*
!> + * last_visited might be invalid if some of the group
!> + * downwards was removed. As we do not know which one
!> + * disappeared we have to start all over again from the
!> + * root.
!> + * css ref count then makes sure that css won't
!> + * disappear while we iterate to the next memcg
!> + */
!> + last_visited = iter->last_visited;
!> + dead_count = atomic_read(&root->dead_count);
!> + smp_rmb();
!
!Confused about this barrier, see below.
!

Quoted 8 lines

!As per above, if you remove the iter lock, those lines are mixed up. !You need to read the dead count first because the writer updates the !dead count after it sets the new position. That way, if the dead !count gives the go-ahead, you KNOW that the position cache is valid, !because it has been updated first. If either the two reads or the two !writes get reordered, you risk seeing a matching dead count while the !position cache is stale.
"

The original prototype code I sent looked like this:

mem_cgroup_iter:
rcu_read_lock()
if atomic_read(&root->dead_count) == iter->dead_count:
smp_rmb()
if tryget(iter->position):

    position = iter->position

memcg = find_next(postion)
css_put(position)
iter->position = memcg
smp_wmb() /* Write position cache BEFORE marking it uptodate */ iter->dead_count = atomic_read(&root->dead_count) rcu_read_unlock()

iter->last_position is written, THEN iter->last_dead_count is written.

So, yes, you "need to read the dead count" first to be sure iter->last_position is uptodate. But iter->last_dead_count, not root->dead_count. I should have caught this in the final submission of your patch :(

Tejun's patch is not correct, either. Something like this?

mm/memcontrol.c +12 -7

index 010d6c1..92830fa 100644
@@ -1199,7 +1199,6 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 
 			mz = mem_cgroup_zoneinfo(root, nid, zid);
 			iter = &mz->reclaim_iter[reclaim->priority];
-			last_visited = iter->last_visited;
 			if (prev && reclaim->generation != iter->generation) {
 				iter->last_visited = NULL;
 				goto out_unlock;

@@ -1217,14 +1216,20 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 			 * css_tryget() verifies the cgroup pointed to
 			 * is alive.
 			 */
+			last_visited = NULL;
 			dead_count = atomic_read(&root->dead_count);
-			smp_rmb();
-			last_visited = iter->last_visited;
-			if (last_visited) {
-				if ((dead_count != iter->last_dead_count) ||
-					!css_tryget(&last_visited->css)) {
+			if (dead_count == iter->last_dead_count) {
+				/*
+				 * The writer below sets the position
+				 * pointer, then the dead count.
+				 * Ensure we read the updated position
+				 * when the dead count matches.
+				 */
+				smp_rmb();
+				last_visited = iter->last_visited;
+				if (last_visited &&
+				    !css_tryget(&last_visited->css))
 					last_visited = NULL;
-				}
 			}
 		}
 

mem_cgroup_iter() implements two iteration modes - plain and reclaim. The former is normal pre-order tree walk. The latter tries to share iteration cursor per zone and priority pair among multiple reclaimers so that they all contribute to scanning forward rather than banging on the same cgroups simultaneously.

Implementing the two in the same function allows them to share code paths which is fine but the current structure is unnecessarily convoluted with conditionals on @reclaim spread across the function rather obscurely and with a somewhat strange control flow which checks for conditions which can't be and has duplicate tests for the same conditions in different forms.

This patch restructures the function such that there's single test on @reclaim and !reclaim path is contained in its block, which simplifies both !reclaim and reclaim paths. Also, the control flow in the reclaim path is restructured and commented so that it's easier to follow what's going on why.

Note that after the patch reclaim->generation is synchronized to the iter's on success whether @prev was specified or not. This doesn't cause any functional differences as the two generation numbers are guaranteed to be the same at that point if @prev and makes the code slightly easier to follow.

This patch is pure restructuring and shouldn't introduce any functional differences.

Signed-off-by Tejun Heo <[email protected]>

---
 mm/memcontrol.c | 131 ++++++++++++++++++++++++++++++--------------------------
 1 file changed, 71 insertions(+), 60 deletions(-)

mm/memcontrol.c +2 -16

index cb2f91c..99e7357 100644
@@ -1170,8 +1170,8 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 				   struct mem_cgroup_reclaim_cookie *reclaim)
 {
 	struct mem_cgroup *memcg = NULL;
-	struct mem_cgroup *last_visited = NULL;
-	unsigned long uninitialized_var(dead_count);
+	struct mem_cgroup_per_zone *mz;
+	struct mem_cgroup_reclaim_iter *iter;
 
 	if (mem_cgroup_disabled())
 		return NULL;

@@ -1179,9 +1179,6 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 	if (!root)
 		root = root_mem_cgroup;
 
-	if (prev && !reclaim)
-		last_visited = prev;
-
 	if (!root->use_hierarchy && root != root_mem_cgroup) {
 		if (prev)
 			goto out_css_put;

@@ -1189,73 +1186,87 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 	}
 
 	rcu_read_lock();
-	while (!memcg) {
-		struct mem_cgroup_reclaim_iter *uninitialized_var(iter);
-
-		if (reclaim) {
-			int nid = zone_to_nid(reclaim->zone);
-			int zid = zone_idx(reclaim->zone);
-			struct mem_cgroup_per_zone *mz;
-
-			mz = mem_cgroup_zoneinfo(root, nid, zid);
-			iter = &mz->reclaim_iter[reclaim->priority];
-			last_visited = iter->last_visited;

mm/memcontrol.c struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root, · line 1194

Quoted 5 lines

mm/memcontrol.c +5 -0

+	/* non reclaim case is simple - just iterate from @prev */
+	if (!reclaim) {
+		memcg = __mem_cgroup_iter_next(root, prev);
+		goto out_unlock;
+	}

I do not have objections for pulling !reclaim case like this, but could you base this on top of the patch which adds predicates into the operators, please?

mm/memcontrol.c +1 -0

@@ -1267,7 +1226,20 @@ struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root,
 			break;
 
 		iter->generation++;
+		last_visited = NULL;

mm/memcontrol.c +3 -0

+	last_visited = xchg(&iter->last_visited, memcg);
+	if (last_visited)
+		css_put(&last_visited->css);
 out_unlock:
 	rcu_read_unlock();
 out_css_put:

mm/memcontrol.c struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root, · line 1239

Quoted 2 lines

mm/memcontrol.c +2 -0

+	if (memcg)
+		css_get(&memcg->css);

This is all good and nice but it re-introduces the same problem which has been fixed by (5f578161: memcg: relax memcg iter caching). You are pinning memcg in memory for unbounded amount of time because css reference will not let object to leave and rest.

I understand your frustration about the complexity of the current synchronization but we didn't come up with anything easier. Originally I though that your tree walk updates which allow dropping rcu would help here but then I realized that not really because the iterator (resp. pos) has to be a valid pointer and there is only one possibility to do that AFAICS here and that is css pinning. And is no-go.

Hello, Michal.

Quoted 7 lines · Michal Hocko

mm/memcontrol.c struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root, · line 1239

Quoted 2 lines

mm/memcontrol.c +2 -0

+	if (memcg)
+		css_get(&memcg->css);

This is all good and nice but it re-introduces the same problem which has been fixed by (5f578161: memcg: relax memcg iter caching). You are pinning memcg in memory for unbounded amount of time because css reference will not let object to leave and rest.

I don't get why that is a problem. Can you please elaborate? css's now explicitly allow holding onto them. We now have clear separation of "destruction" and "release" and blkcg also depends on it. If memcg still doesn't distinguish the two properly, that's where the problem should be fixed.

Quoted 6 lines

I understand your frustration about the complexity of the current synchronization but we didn't come up with anything easier. Originally I though that your tree walk updates which allow dropping rcu would help here but then I realized that not really because the iterator (resp. pos) has to be a valid pointer and there is only one possibility to do that AFAICS here and that is css pinning. And is no-go.

I find the above really weird. If css can't be pinned for position caching, isn't it natural to ask why it can't be and then fix it?

Because that's what the whole refcnt thing is about and a usage which cgroup explicitly allows (e.g. blkcg also does it). Why do you go from there to "this batshit crazy barrier dancing is the only solution"?

Can you please explain why memcg css's can't be pinned?

Well, I do not mind pinning when I know that somebody releases the reference in a predictable future (ideally almost immediately). But the cached iter represents time unbounded pinning because nobody can guarantee that priority 3 at zone Normal at node 3 will be ever scanned again and the pointer in the last_visited node will be stuck there for

eternity. Can we free memcg with only css elevated and safely check that the cached pointer can be used without similar dances we have now? I am open to any suggestions.

Hello, Michal.

Quoted 5 lines · Michal Hocko

Well, I do not mind pinning when I know that somebody releases the reference in a predictable future (ideally almost immediately). But the cached iter represents time unbounded pinning because nobody can guarantee that priority 3 at zone Normal at node 3 will be ever scanned again and the pointer in the last_visited node will be stuck there for

I don't really get that. As long as the amount is bound and the overhead negligible / acceptable, why does it matter how long the pinning persists?

We aren't talking about something gigantic or can

leak continuously. It will only matter iff cgroups are continuously created and destroyed and each live memcg will be able to pin one memcg (BTW, I think I forgot to unpin on memcg destruction).

Quoted 3 lines

eternity. Can we free memcg with only css elevated and safely check that the cached pointer can be used without similar dances we have now? I am open to any suggestions.

I really think this is worrying too much about something which doesn't really matter and then coming up with an over-engineered solution for the imagined problem. This isn't a real problem. No solution is necessary.

In the off chance that this is a real problem, which I strongly doubt, as I wrote to Johannes, we can implement extremely dumb cleanup routine rather than this weak reference beast.

Quoted 3 lines

I don't really get that. As long as the amount is bound and the overhead negligible / acceptable, why does it matter how long the pinning persists?

Because the amount is not bound either. Just create a hierarchy and trigger the hard limit and if you are careful enough you can always keep some of the children in the cached pointer (with css reference, if you will) and then release the hierarchy. You can do that repeatedly and leak considerable amount of memory.

Quoted 1 line

We aren't talking about something gigantic or can

mem_cgroup is 888B now (depending on configuration). So I wouldn't call it negligible.

Quoted 3 lines

In the off chance that this is a real problem, which I strongly doubt, as I wrote to Johannes, we can implement extremely dumb cleanup routine rather than this weak reference beast.

That was my first version (https://lkml.org/lkml/2013/1/3/298) and Johannes didn't like. To be honest I do not care _much_ which way we go but we definitely cannot pin those objects for ever.

Hello, Michal.

Quoted 4 lines · Michal Hocko

Quoted 3 lines

I don't really get that. As long as the amount is bound and the overhead negligible / acceptable, why does it matter how long the pinning persists?

Quoted 5 lines

Because the amount is not bound either. Just create a hierarchy and trigger the hard limit and if you are careful enough you can always keep some of the children in the cached pointer (with css reference, if you will) and then release the hierarchy. You can do that repeatedly and leak considerable amount of memory.

It's still bound, no? Each live memcg can only keep limited number of cgroups cached, right?

Quoted 4 lines

Quoted 1 line

We aren't talking about something gigantic or can

mem_cgroup is 888B now (depending on configuration). So I wouldn't call it negligible.

Do you think that the number can actually grow harmful? Would you be kind enough to share some calculations with me?

Quoted 7 lines

Quoted 3 lines

In the off chance that this is a real problem, which I strongly doubt, as I wrote to Johannes, we can implement extremely dumb cleanup routine rather than this weak reference beast.

That was my first version (https://lkml.org/lkml/2013/1/3/298) and Johannes didn't like. To be honest I do not care _much_ which way we go but we definitely cannot pin those objects for ever.

I'll get to the barrier thread but really complex barrier dancing like that is only justifiable in extremely hot paths a lot of people pay attention to. It doesn't belong inside memcg proper. If the cached amount is an actual concern, let's please implement a simple clean up thing. All we need is a single delayed_work which scans the tree periodically.

Johannes, what do you think?

Thanks.

Signature · 1 line

tejun

Quoted 2 lines

It's still bound, no? Each live memcg can only keep limited number of cgroups cached, right?

Assuming that they are cleaned up when the memcg is offlined then yes.

Quoted 2 lines

Do you think that the number can actually grow harmful? Would you be kind enough to share some calculations with me?

Well, each intermediate node might pin up-to NR_NODES * NR_ZONES * NR_PRIORITY groups. You would need a big hierarchy to have chance to cache different groups so that it starts matter.

And do what? css_try_get to find out whether the cached memcg is still

alive. Sorry, I do not like it at all. I find it much better to clean up when the group is removed. Because doing things asynchronously just makes it more obscure. There is no reason to do such a thing on the background when we know _when_ to do the cleanup and that is definitely _not a hot path_.

Quoted 5 lines

alive. Sorry, I do not like it at all. I find it much better to clean up when the group is removed. Because doing things asynchronously just makes it more obscure. There is no reason to do such a thing on the background when we know _when_ to do the cleanup and that is definitely _not a hot path_.

Yeah, that's true. I just wanna avoid the barrier dancing. Only one of the ancestors can cache a memcg, right?

Walking up the tree scanning for cached ones and putting them should work? Is that what you were suggesting?

Quoted 2 lines

Yeah, that's true. I just wanna avoid the barrier dancing. Only one of the ancestors can cache a memcg, right?

No. All of them on the way up hierarchy. Basically each parent which ever triggered the reclaim caches reclaimers.

Quoted 2 lines

Walking up the tree scanning for cached ones and putting them should work? Is that what you were suggesting?

That was my first version of the patch I linked in the previous email.

Hello, Michal.

Quoted 4 lines · Michal Hocko

Quoted 3 lines

I don't really get that. As long as the amount is bound and the overhead negligible / acceptable, why does it matter how long the pinning persists?

Quoted 5 lines

Because the amount is not bound either. Just create a hierarchy and trigger the hard limit and if you are careful enough you can always keep some of the children in the cached pointer (with css reference, if you will) and then release the hierarchy. You can do that repeatedly and leak considerable amount of memory.

It's still bound, no? Each live memcg can only keep limited number of cgroups cached, right?

Quoted 4 lines

Quoted 1 line

We aren't talking about something gigantic or can

mem_cgroup is 888B now (depending on configuration). So I wouldn't call it negligible.

Do you think that the number can actually grow harmful? Would you be kind enough to share some calculations with me?

Quoted 7 lines

Quoted 3 lines

In the off chance that this is a real problem, which I strongly doubt, as I wrote to Johannes, we can implement extremely dumb cleanup routine rather than this weak reference beast.

That was my first version (https://lkml.org/lkml/2013/1/3/298) and Johannes didn't like. To be honest I do not care _much_ which way we go but we definitely cannot pin those objects for ever.

I'll get to the barrier thread but really complex barrier dancing like that is only justifiable in extremely hot paths a lot of people pay attention to. It doesn't belong inside memcg proper. If the cached amount is an actual concern, let's please implement a simple clean up thing. All we need is a single delayed_work which scans the tree periodically.

Johannes, what do you think?

Quoted 5 lines · Tejun Heo

Hello, Michal.

Quoted 2 lines · Michal Hocko

Quoted 1 line

We aren't talking about something gigantic or can

Quoted 5 lines

Quoted 2 lines

mem_cgroup is 888B now (depending on configuration). So I wouldn't call it negligible.

Do you think that the number can actually grow harmful? Would you be kind enough to share some calculations with me?

5k cgroups * say 10 priority levels * 1k struct mem_cgroup may pin 51M of dead struct mem_cgroup, plus whatever else the css pins.

You hate the barriers, so let's add a lock to access the iterator. That path is not too hot in most cases.

On the other hand, the weak pointer is not too esoteric of a pattern and we can neatly abstract it into two functions: one that takes an iterator and returns a verified css reference or NULL, and one to invalidate pointers when called from the memcg destruction code.

These two things should greatly simplify mem_cgroup_iter() while not completely abandoning all our optimizations.

What do you think?

5k cgroups * say 10 priority levels * 1k struct mem_cgroup may pin 51M of dead struct mem_cgroup, plus whatever else the css pins.

Quoted 8 lines

I'll get to the barrier thread but really complex barrier dancing like that is only justifiable in extremely hot paths a lot of people pay attention to. It doesn't belong inside memcg proper. If the cached amount is an actual concern, let's please implement a simple clean up thing. All we need is a single delayed_work which scans the tree periodically.

Johannes, what do you think?

While I see your concerns about complexity (and this certainly is not the most straight-forward code), I really can't get too excited about asynchroneous garbage collection, even worse when it's time-based. It would probably start out with less code but two releases later we would have added all this stuff that's required to get the interaction right and fix unpredictable reclaim disruption that hits when the reaper coincides just right with heavy reclaim once a week etc. I just don't think that asynchroneous models are simpler than state machines. Harder to reason about, harder to debug.

Now, there are separate things that add complexity to our current
code: the weak pointers, the lockless iterator, and the fact that all of it is jam-packed into one monolithic iterator function. I can see why you are not happy. But that does not mean we have to get rid of everything wholesale.

You hate the barriers, so let's add a lock to access the iterator. That path is not too hot in most cases.

On the other hand, the weak pointer is not too esoteric of a pattern and we can neatly abstract it into two functions: one that takes an iterator and returns a verified css reference or NULL, and one to invalidate pointers when called from the memcg destruction code.

These two things should greatly simplify mem_cgroup_iter() while not completely abandoning all our optimizations.

What do you think?

Hey, Johannes.

Quoted 2 lines · Johannes Weiner

5k cgroups * say 10 priority levels * 1k struct mem_cgroup may pin 51M of dead struct mem_cgroup, plus whatever else the css pins.

Yeah, it seems like it can grow quite a bit.

Quoted 9 lines

Quoted 8 lines

I'll get to the barrier thread but really complex barrier dancing like that is only justifiable in extremely hot paths a lot of people pay attention to. It doesn't belong inside memcg proper. If the cached amount is an actual concern, let's please implement a simple clean up thing. All we need is a single delayed_work which scans the tree periodically.

Johannes, what do you think?

Quoted 9 lines

While I see your concerns about complexity (and this certainly is not the most straight-forward code), I really can't get too excited about asynchroneous garbage collection, even worse when it's time-based. It would probably start out with less code but two releases later we would have added all this stuff that's required to get the interaction right and fix unpredictable reclaim disruption that hits when the reaper coincides just right with heavy reclaim once a week etc. I just don't think that asynchroneous models are simpler than state machines. Harder to reason about, harder to debug.

Agreed, but we can do the cleanup from ->css_offline() as Michal suggested. Naively implemented, this will lose the nice property of keeping the iteration point even when the cursor cgroup is removed, which can be an issue if we're actually worrying about cases with 5k cgroups continuously being created and destroyed. Maybe we can make it point to the next cgroup to visit rather than the last visited one and update it from ->css_offline().

Quoted 17 lines

Now, there are separate things that add complexity to our current
code: the weak pointers, the lockless iterator, and the fact that all of it is jam-packed into one monolithic iterator function. I can see why you are not happy. But that does not mean we have to get rid of everything wholesale.

You hate the barriers, so let's add a lock to access the iterator. That path is not too hot in most cases.

On the other hand, the weak pointer is not too esoteric of a pattern and we can neatly abstract it into two functions: one that takes an iterator and returns a verified css reference or NULL, and one to invalidate pointers when called from the memcg destruction code.

These two things should greatly simplify mem_cgroup_iter() while not completely abandoning all our optimizations.

Quoted 1 line

What do you think?

I really think the weak pointers should go especially as we can achieve about the same thing with normal RCU dereference. Also, I'm a bit confused about what you're suggesting. If we have invalidation from offline, why do we need weak pointers?

I'm not sure what you are suggesting. Synchroneously invalidate every individual iterator upwards the hierarchy every time a cgroup is destroyed?

The invalidation I am talking about is what we do by increasing the dead counts. This lazily invalidates all the weak pointers in the iterators of the hierarchy root.

Of course if you do a synchroneous invalidation of individual iterators, we don't need weak pointers anymore and RCU is enough, but that would mean nr_levels * nr_nodes * nr_zones * nr_priority_levels invalidation operations per destruction, whereas the weak pointers are invalidated with one atomic_inc() per nesting level.

As I said, the weak pointers are only a few lines of code that can be neatly self-contained (see the invalidate, load, store functions below). Please convince me that your alternative solution will save complexity to such an extent that either the memory waste of indefinite css pinning, or the computational overhead of non-lazy iterator cleanup, is justifiable.

Quoted 3 lines · Johannes Weiner

I'm not sure what you are suggesting. Synchroneously invalidate every individual iterator upwards the hierarchy every time a cgroup is destroyed?

Yeap.

Quoted 6 lines

As I said, the weak pointers are only a few lines of code that can be neatly self-contained (see the invalidate, load, store functions below). Please convince me that your alternative solution will save complexity to such an extent that either the memory waste of indefinite css pinning, or the computational overhead of non-lazy iterator cleanup, is justifiable.

The biggest issue I see with the weak pointer is that it's special and tricky. If this is something which is absolutely necessary, it should be somewhere more generic. Also, if we can use the usual RCU deref with O(depth) cleanup in the cold path, I don't see how this deviation is justifiable.

For people who've been looking at it for long enough, it probably isn't that different from using plain RCU but that's just because that person has spent the time to build that pattern into his/her brain. We now have a lot of people accustomed to plain RCU usages which in itself is tricky already and introducing new constructs is actively deterimental to maintainability. We sure can do that when there's no alternative but I don't think avoiding synchronous cleanup on cgroup destruction path is a good enough reason. It feels like an over-engineering to me.

Another thing is that this matters the most when there are continuous creation and destruction of cgroups and the weak pointer implementation would keep resetting the iteration to the beginning. Depending on timing, it'd be able to live-lock reclaim cursor to the beginning of iteration even with fairly low rate of destruction, right? It can be pretty bad high up the tree. With synchronous cleanup, depending on how it's implemented, it can be made to keep the iteration position.

That could be an advantage, yes. But keep in mind that every destruction has to perform this invalidation operation against the global root_mem_cgroup's nr_node * nr_zone * nr_priority_levels iterators, so you can't muck around forever, while possibly holding a lock at this level. It's not a hot path, but you don't want to turn it into one, either.

The upshot for me is this: whether you do long-term pinning or greedy iterator invalidation, the cost of cgroup destruction increases. Either in terms of memory usage or in terms of compute time. I would have loved to see something as simple as the long-term pinning work out in practice, because it truly would have been simpler. But at this point, I don't really care much because the projected margins of reduction in complexity and increase of cost from your proposal are too small for me to feel strongly about one solution or the other, or go ahead and write the code. I'll look at your patches, though ;-)

Either way, I'll prepare the patch set that includes the barrier fix and a small cleanup to make the weak pointer management more palatable. I'm still open to code proposals, so don't let it distract you, but we might as well make it a bit more readable in the meantime.

Yo,

Quoted 6 lines · Johannes Weiner

That could be an advantage, yes. But keep in mind that every destruction has to perform this invalidation operation against the global root_mem_cgroup's nr_node * nr_zone * nr_priority_levels iterators, so you can't muck around forever, while possibly holding a lock at this level. It's not a hot path, but you don't want to turn it into one, either.

nr_node tends to be pretty low in most cases, so it shouldn't be a problem there but yeah with high enough nodes and high enough rate of

Quoted 10 lines · Tejun Heo

Yo,

Quoted 6 lines · Johannes Weiner

That could be an advantage, yes. But keep in mind that every destruction has to perform this invalidation operation against the global root_mem_cgroup's nr_node * nr_zone * nr_priority_levels iterators, so you can't muck around forever, while possibly holding a lock at this level. It's not a hot path, but you don't want to turn it into one, either.

Quoted 2 lines

nr_node tends to be pretty low in most cases, so it shouldn't be a problem there but yeah with high enough nodes and high enough rate of

Also, do we need to hold a lock? It doesn't have to be completely strict, so we might as well get away with something like,

	for_each_cached_pos() {
		if (hint == me) {
			/* simple clearing implementation, we prolly wanna push it forward */
			cached = xchg(hint, NULL);
			if (cached)
				css_put(cached);
		}
	}

It still scans the memory but wouldn't create any contention.

Thanks.

Signature · 1 line

tejun

Quoted 11 lines

Also, do we need to hold a lock? It doesn't have to be completely strict, so we might as well get away with something like,

	for_each_cached_pos() {
		if (hint == me) {
			/* simple clearing implementation, we prolly wanna push it forward */
			cached = xchg(hint, NULL);
			if (cached)
				css_put(cached);
		}
	}

This would be racy:
mem_cgroup_iter
rcu_read_lock
__mem_cgroup_iter_next cgroup_destroy_locked
css_tryget(memcg)
atomic_add(CSS_DEACT_BIAS) offline_css(memcg)
xchg(memcg, NULL)
mem_cgroup_iter_update

    iter->last_visited = memcg

rcy_read_unlock

But if it was called from call_rcu the we should be safe AFAICS.

Hello,

Quoted 24 lines · Michal Hocko

Quoted 11 lines

Also, do we need to hold a lock? It doesn't have to be completely strict, so we might as well get away with something like,

	for_each_cached_pos() {
		if (hint == me) {
			/* simple clearing implementation, we prolly wanna push it forward */
			cached = xchg(hint, NULL);
			if (cached)
				css_put(cached);
		}
	}

This would be racy:
mem_cgroup_iter
rcu_read_lock
__mem_cgroup_iter_next cgroup_destroy_locked
css_tryget(memcg)
atomic_add(CSS_DEACT_BIAS) offline_css(memcg)
xchg(memcg, NULL)
mem_cgroup_iter_update

    iter->last_visited = memcg

rcy_read_unlock

Quoted 1 line

But if it was called from call_rcu the we should be safe AFAICS.

Oh yeah, it is racy. That's what I meant by "not having to be completely strict". The race window is small enough and it's not like we're messing up refcnt or may end up with use-after-free.

Doing it from RCU would make the race go away but I'm not sure whether the extra RCU bouncing is worthwhile. I don't know. Maybe.

Thanks.

Signature · 1 line

tejun

Quoted 3 lines

Oh yeah, it is racy. That's what I meant by "not having to be completely strict". The race window is small enough and it's not like we're messing up refcnt or may end up with use-after-free.

But it would potentially pin (aka leak) the memcg for ever.

Hello, Michal.

Quoted 4 lines · Michal Hocko

Quoted 3 lines

Oh yeah, it is racy. That's what I meant by "not having to be completely strict". The race window is small enough and it's not like we're messing up refcnt or may end up with use-after-free.

Quoted 1 line

But it would potentially pin (aka leak) the memcg for ever.

It wouldn't be anything systemetic tho - race condition's likliness is low and increases with the frequency of reclaim iteration, which at the same time means that it's likely to remedy itself pretty soon.

I'm doubtful it'd matter. If it's still bothering, we sure can do it from RCU callback.

Sure a next visit on the same root subtree (same node, zone and prio) would css_put it but what if that root goes away itself. Still fixable, if every group checks its own cached iters and css_put everybody but that is even uglier. So doing the up-the-hierarchy cleanup in RCU callback is much easier.

Hello, Michal.

Quoted 5 lines · Michal Hocko

Sure a next visit on the same root subtree (same node, zone and prio) would css_put it but what if that root goes away itself. Still fixable, if every group checks its own cached iters and css_put everybody but that is even uglier. So doing the up-the-hierarchy cleanup in RCU callback is much easier.

Ooh, right, we don't need cleanup of the cached cursors on destruction if we get this correct - especially if we make cursors point to the next cgroup to visit as self is always the first one to visit.

Yeah, if we can do away with that, doing that way is definitely better.

Quoted 3 lines

Ooh, right, we don't need cleanup of the cached cursors on destruction if we get this correct - especially if we make cursors point to the next cgroup to visit as self is always the first one to visit.

You would need to pin the next-to-visit memcg as well, so you need a cleanup on the removal.

Hey,

Quoted 4 lines · Michal Hocko

Quoted 3 lines

Ooh, right, we don't need cleanup of the cached cursors on destruction if we get this correct - especially if we make cursors point to the next cgroup to visit as self is always the first one to visit.

Quoted 2 lines

You would need to pin the next-to-visit memcg as well, so you need a cleanup on the removal.

But that'd be one of the descendants of the said cgroup and there can no descendant left when the cgroup is being removed. What am I missing?

          .
          .
          .
          A (cached=E)
         /|\____________
        / |             \
	 B  D (cached=E)   F<
	/   |               \
     C<   E                G
          ^
	 removed

* D level cache - nobody left for either approach approach
* A level is
- F for next-to-visit
- C for last_visited

You have to get up the hierarchy and handle root cgroup as a special case for !root->use_hierarchy. Once you have non-NULL new cache the it can be propagated without a new search (which I haven't realized when working on this approach the last time - not that it would safe some code in the end).

Makes sense?

Quoted 23 lines · Michal Hocko

          .
          .
          .
          A (cached=E)
         /|\____________
        / |             \
	 B  D (cached=E)   F<
	/   |               \
     C<   E                G
          ^
	 removed

* D level cache - nobody left for either approach approach
* A level is
- F for next-to-visit
- C for last_visited

You have to get up the hierarchy and handle root cgroup as a special case for !root->use_hierarchy. Once you have non-NULL new cache the it can be propagated without a new search (which I haven't realized when working on this approach the last time - not that it would safe some code in the end).

Quoted 1 line

Makes sense?

I don't think we're talking about the same thing. I wasn't talking about skipping walking up the hierarchy (differently depending on use_hierarchy of course) when E is removed. I was talking about skipped cleaning E's cache when removing E as it's guaranteed to be empty by then.

The difference between caching the last and next one is that if we put the last one in the cache, E's cache could be pointing to itself and needs to be scanned.

Not a big difference either way but if you combine that with the need for special rewinding which will basically come down to traversing the sibling list again, pointing to the next entry is just easier.

Anyways, I think we're getting too deep into details but one more thing, what do you mean by "non-NULL new cache"?

Quoted 2 lines

Anyways, I think we're getting too deep into details but one more thing, what do you mean by "non-NULL new cache"?

If you replace cached memcg by a new (non-NULL) one then all the parents up the hierarchy can reuse the same replacement and do not have to search again.

Hello, Michal.

Quoted 7 lines · Michal Hocko

mm/memcontrol.c struct mem_cgroup *mem_cgroup_iter(struct mem_cgroup *root, · line 1239

Quoted 2 lines

mm/memcontrol.c +2 -0

+	if (memcg)
+		css_get(&memcg->css);

This is all good and nice but it re-introduces the same problem which has been fixed by (5f578161: memcg: relax memcg iter caching). You are pinning memcg in memory for unbounded amount of time because css reference will not let object to leave and rest.

I don't get why that is a problem. Can you please elaborate? css's now explicitly allow holding onto them. We now have clear separation of "destruction" and "release" and blkcg also depends on it. If memcg still doesn't distinguish the two properly, that's where the problem should be fixed.

Quoted 6 lines

I understand your frustration about the complexity of the current synchronization but we didn't come up with anything easier. Originally I though that your tree walk updates which allow dropping rcu would help here but then I realized that not really because the iterator (resp. pos) has to be a valid pointer and there is only one possibility to do that AFAICS here and that is css pinning. And is no-go.

I find the above really weird. If css can't be pinned for position caching, isn't it natural to ask why it can't be and then fix it? Because that's what the whole refcnt thing is about and a usage which cgroup explicitly allows (e.g. blkcg also does it). Why do you go from there to "this batshit crazy barrier dancing is the only solution"?

Can you please explain why memcg css's can't be pinned?

We might pin them indefinitely. In a hierarchy with hundreds of groups that is short by 10M of memory, we only reclaim from a couple of groups before we stop and leave the iterator pointing somewhere in the hierarchy. Until the next reclaimer comes along, which might be a split second later or three days later.

There is a reclaim iterator for every memcg (since every memcg represents a hierarchy), so we could pin a lot of csss for an indefinite amount of time.