memcg/slab: reintroduce dead cache self-destruction

Currently, we count the number of pages allocated to a per memcg cache in memcg_cache_params->nr_pages. We only use this counter to find out if the cache is empty and can be destroyed. So let's rename it to refcnt and make it count not pages, but slabs so that we can use atomic_inc/dec instead of atomic_add/sub in memcg_charge/uncharge_slab.

When the memcg_cache_params->refcnt goes to 0, schedule the worker that will unregister the cache. To prevent this from happening when the owner memcg is alive, keep the refcnt incremented during memcg lifetime.

This will be used by the next patches.

SLUB's kmem_cache_shrink not only removes empty slabs from the cache, but also sorts slabs by the number of objects in-use to cope with fragmentation. To achieve that, it tries to allocate a temporary array. If it fails, it will abort the whole procedure.

This is unacceptable for kmemcg, where we want to be sure that all empty slabs are removed from the cache on memcg offline, so let's just skip the de-fragmentation step if the allocation fails, but still get rid of empty slabs.

Quoted 4 lines · Vladimir Davydov

SLUB's kmem_cache_shrink not only removes empty slabs from the cache, but also sorts slabs by the number of objects in-use to cope with fragmentation. To achieve that, it tries to allocate a temporary array. If it fails, it will abort the whole procedure.

If we cannot allocate a kernel structure that is mostly less than a page size then we have much more important things to worry about.

Quoted 4 lines

This is unacceptable for kmemcg, where we want to be sure that all empty slabs are removed from the cache on memcg offline, so let's just skip the de-fragmentation step if the allocation fails, but still get rid of empty slabs.

Lets just try the shrink and log the fact that it failed? Try again later?

... which means more async workers, more complication to kmemcg code :-(

Sorry, but I just don't get why we can't make kmem_cache_shrink never fail? Is failing de-fragmentation, which is even not implied by the function declaration, so critical that should be noted? If so, we can return an error while still shrinking empty slabs...

If you just don't like the code after the patch, here is another, less intrusive version doing practically the same. Would it be better?

First, nobody uses it. Second, it differs across the implementations:
for SLUB it always returns 0, for SLAB it returns 0 if the cache appears to be empty. So let's get rid of it.

Quoted 3 lines · Vladimir Davydov

First, nobody uses it. Second, it differs across the implementations:
for SLUB it always returns 0, for SLAB it returns 0 if the cache appears to be empty. So let's get rid of it.

Well slub returns an error code if it fails

I am all in favor of making it consistent. The indication in SLAB that the slab is empty may be useful. May return error code or the number of slab pages in use?

Some of the code that is shared by the allocators here could be moved into mm/slab_common.c. Put kmem_cache_shrink there and then have __kmem_cache_shrink to the allocator specific things?

Quoted 1 line

Well slub returns an error code if it fails

... to sort slabs by the nubmer of objects in use, which is not even implied by the function declaration. Why can *shrinking*, which is what kmem_cache_shrink must do at first place, ever fail?

Quoted 5 lines · Vladimir Davydov

Quoted 1 line

Well slub returns an error code if it fails

... to sort slabs by the nubmer of objects in use, which is not even implied by the function declaration. Why can *shrinking*, which is what kmem_cache_shrink must do at first place, ever fail?

Because there is a memory allocation failure. Or there may be other processes going on that prevent shrinking. F.e. We may want to merge a patchset that does defragmentation of slabs at some point.

Still, I really want to evict all empty slabs from cache on memcg offline for sure. Handling failures there means introducing a worker that will retry shrinking, but that seems to me as an unnecessary complication, because there's nothing that can prevent us from shrinking empty slabs from the cache, even if we merge slab defragmentation, isn't it?

May be, it's worth introducing a special function, say kmem_cache_zap(), that will only evict empty slabs from the cache, plus disable empty slabs caching? This function would be called only from memcg offline for dead memcg caches.

Quoted 7 lines · Vladimir Davydov

Still, I really want to evict all empty slabs from cache on memcg offline for sure. Handling failures there means introducing a worker that will retry shrinking, but that seems to me as an unnecessary complication, because there's nothing that can prevent us from shrinking empty slabs from the cache, even if we merge slab defragmentation, isn't it?

Quoted 4 lines

May be, it's worth introducing a special function, say kmem_cache_zap(), that will only evict empty slabs from the cache, plus disable empty slabs caching? This function would be called only from memcg offline for dead memcg caches.

I am fine with the lower impact version that you came up with later.

(3) is a bit more difficult, because slabs are added to per-cpu partial lists lock-less. Fortunately, we only have to handle the __slab_free case, because, as there shouldn't be any allocation requests dispatched to a dead memcg cache, get_partial_node() should never be called. In __slab_free we use cmpxchg to modify kmem_cache_cpu->partial (see put_cpu_partial) so that setting ->partial to a special value, which will make put_cpu_partial bail out, will do the trick.

Note, this shouldn't affect performance, because keeping empty slabs on per node lists as well as using per cpu partials are only worthwhile if the cache is used for allocations, which isn't the case for dead caches.

Quoted 11 lines · Vladimir Davydov

(3) is a bit more difficult, because slabs are added to per-cpu partial lists lock-less. Fortunately, we only have to handle the __slab_free case, because, as there shouldn't be any allocation requests dispatched to a dead memcg cache, get_partial_node() should never be called. In __slab_free we use cmpxchg to modify kmem_cache_cpu->partial (see put_cpu_partial) so that setting ->partial to a special value, which will make put_cpu_partial bail out, will do the trick.

Note, this shouldn't affect performance, because keeping empty slabs on per node lists as well as using per cpu partials are only worthwhile if the cache is used for allocations, which isn't the case for dead caches.

This all sounds pretty good to me but we still have some pretty extensive modifications that I would rather avoid.

In put_cpu_partial you can simply check that the memcg is dead right? This would avoid all the other modifications I would think and will not require a special value for the per cpu partial pointer.

Quoted 17 lines · Christoph Lameter

Quoted 11 lines · Vladimir Davydov

(3) is a bit more difficult, because slabs are added to per-cpu partial lists lock-less. Fortunately, we only have to handle the __slab_free case, because, as there shouldn't be any allocation requests dispatched to a dead memcg cache, get_partial_node() should never be called. In __slab_free we use cmpxchg to modify kmem_cache_cpu->partial (see put_cpu_partial) so that setting ->partial to a special value, which will make put_cpu_partial bail out, will do the trick.

Note, this shouldn't affect performance, because keeping empty slabs on per node lists as well as using per cpu partials are only worthwhile if the cache is used for allocations, which isn't the case for dead caches.

This all sounds pretty good to me but we still have some pretty extensive modifications that I would rather avoid.

Quoted 3 lines

In put_cpu_partial you can simply check that the memcg is dead right? This would avoid all the other modifications I would think and will not require a special value for the per cpu partial pointer.

That would be racy. The check if memcg is dead and the write to per cpu partial ptr wouldn't proceed as one atomic operation. If we set the dead flag from another thread between these two operations, put_cpu_partial will add a slab to a per cpu partial list *after* the cache was zapped.

Quoted 10 lines · Vladimir Davydov

Quoted 9 lines · Christoph Lameter

Quoted 7 lines · Vladimir Davydov

(3) is a bit more difficult, because slabs are added to per-cpu partial lists lock-less. Fortunately, we only have to handle the __slab_free case, because, as there shouldn't be any allocation requests dispatched to a dead memcg cache, get_partial_node() should never be called. In __slab_free we use cmpxchg to modify kmem_cache_cpu->partial (see put_cpu_partial) so that setting ->partial to a special value, which will make put_cpu_partial bail out, will do the trick.

I think that we can do (3) easily.
If we check memcg_cache_dead() in the end of put_cpu_partial() rather than in the begin of put_cpu_partial(), we can avoid the race you mentioned. If someone do put_cpu_partial() before dead flag is set, it can be zapped by who set dead flag. And if someone do put_cpu_partial() after dead flag is set, it can be zapped by who do put_cpu_partial().

Hi Joonsoo,

Quoted 11 lines · Joonsoo Kim

Quoted 10 lines · Vladimir Davydov

Quoted 9 lines · Christoph Lameter

Quoted 7 lines · Vladimir Davydov

(3) is a bit more difficult, because slabs are added to per-cpu partial lists lock-less. Fortunately, we only have to handle the __slab_free case, because, as there shouldn't be any allocation requests dispatched to a dead memcg cache, get_partial_node() should never be called. In __slab_free we use cmpxchg to modify kmem_cache_cpu->partial (see put_cpu_partial) so that setting ->partial to a special value, which will make put_cpu_partial bail out, will do the trick.

[...]

Quoted 7 lines

I think that we can do (3) easily.
If we check memcg_cache_dead() in the end of put_cpu_partial() rather than in the begin of put_cpu_partial(), we can avoid the race you mentioned. If someone do put_cpu_partial() before dead flag is set, it can be zapped by who set dead flag. And if someone do put_cpu_partial() after dead flag is set, it can be zapped by who do put_cpu_partial().

After put_cpu_partial() adds a frozen slab to a per cpu partial list, the slab becomes visible to other threads, which means it can be unfrozen and freed. The latter can trigger cache destruction. Hence we shouldn't touch the cache, in particular call memcg_cache_dead() on it, after calling put_cpu_partial(), otherwise we can get use-after-free.

However, what you propose makes sense if we disable irqs before adding a slab to a partial list and enable them only after checking if the cache is dead and unfreezing all partials if so, i.e.

mm/slub.c +15 -0

index d96faa2464c3..14b9e9a8677c 100644
@@ -2030,8 +2030,15 @@ static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
        struct page *oldpage;
        int pages;
        int pobjects;
+       unsigned long flags;
+       int irq_saved = 0;
 
        do {
+               if (irq_saved) {
+                       local_irq_restore(flags);
+                       irq_saved = 0;
+               }
+
                pages = 0;
                pobjects = 0;
                oldpage = this_cpu_read(s->cpu_slab->partial);

@@ -2062,8 +2069,16 @@ static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
                page->pobjects = pobjects;
                page->next = oldpage;
 
+               local_irq_save(flags);
+               irq_saved = 1;
+
        } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page)
                                                                != oldpage);
+
+       if (memcg_cache_dead(s))
+               unfreeze_partials(s, this_cpu_ptr(s->cpu_slab));
+
+       local_irq_restore(flags);
 #endif
 }
 

That would be safe against possible cache destruction, because to remove a slab from a per cpu partial list we have to run on the cpu it was frozen on. Disabling irqs makes it impossible.

Hmm... this is also a bit ugly.
How about following change?

2014-06-02 20:47 GMT+09:00 Vladimir Davydov <[email protected]>:

Quoted 71 lines

Hi Joonsoo,

Quoted 11 lines · Joonsoo Kim

Quoted 10 lines · Vladimir Davydov

Quoted 9 lines · Christoph Lameter

Quoted 7 lines · Vladimir Davydov

(3) is a bit more difficult, because slabs are added to per-cpu partial lists lock-less. Fortunately, we only have to handle the __slab_free case, because, as there shouldn't be any allocation requests dispatched to a dead memcg cache, get_partial_node() should never be called. In __slab_free we use cmpxchg to modify kmem_cache_cpu->partial (see put_cpu_partial) so that setting ->partial to a special value, which will make put_cpu_partial bail out, will do the trick.

[...]

Quoted 7 lines

I think that we can do (3) easily.
If we check memcg_cache_dead() in the end of put_cpu_partial() rather than in the begin of put_cpu_partial(), we can avoid the race you mentioned. If someone do put_cpu_partial() before dead flag is set, it can be zapped by who set dead flag. And if someone do put_cpu_partial() after dead flag is set, it can be zapped by who do put_cpu_partial().

After put_cpu_partial() adds a frozen slab to a per cpu partial list, the slab becomes visible to other threads, which means it can be unfrozen and freed. The latter can trigger cache destruction. Hence we shouldn't touch the cache, in particular call memcg_cache_dead() on it, after calling put_cpu_partial(), otherwise we can get use-after-free.

However, what you propose makes sense if we disable irqs before adding a slab to a partial list and enable them only after checking if the cache is dead and unfreezing all partials if so, i.e.

mm/slub.c +15 -0

index d96faa2464c3..14b9e9a8677c 100644
@@ -2030,8 +2030,15 @@ static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
        struct page *oldpage;
        int pages;
        int pobjects;
+       unsigned long flags;
+       int irq_saved = 0;
 
        do {
+               if (irq_saved) {
+                       local_irq_restore(flags);
+                       irq_saved = 0;
+               }
+
                pages = 0;
                pobjects = 0;
                oldpage = this_cpu_read(s->cpu_slab->partial);

@@ -2062,8 +2069,16 @@ static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
                page->pobjects = pobjects;
                page->next = oldpage;
 
+               local_irq_save(flags);
+               irq_saved = 1;
+
        } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page)
                                                                != oldpage);
+
+       if (memcg_cache_dead(s))
+               unfreeze_partials(s, this_cpu_ptr(s->cpu_slab));
+
+       local_irq_restore(flags);
 #endif
 }
 

Quoted 3 lines

That would be safe against possible cache destruction, because to remove a slab from a per cpu partial list we have to run on the cpu it was frozen on. Disabling irqs makes it impossible.

Hmm... this is also a bit ugly.
How about following change?

Thanks.

mm/slub.c +0 -0

index 2b1ce69..6adab87 100644

Quoted 86 lines

2014-06-02 20:47 GMT+09:00 Vladimir Davydov <[email protected]>:

Quoted 71 lines

Hi Joonsoo,

Quoted 11 lines · Joonsoo Kim

Quoted 10 lines · Vladimir Davydov

Quoted 9 lines · Christoph Lameter

Quoted 7 lines · Vladimir Davydov

(3) is a bit more difficult, because slabs are added to per-cpu partial lists lock-less. Fortunately, we only have to handle the __slab_free case, because, as there shouldn't be any allocation requests dispatched to a dead memcg cache, get_partial_node() should never be called. In __slab_free we use cmpxchg to modify kmem_cache_cpu->partial (see put_cpu_partial) so that setting ->partial to a special value, which will make put_cpu_partial bail out, will do the trick.

[...]

Quoted 7 lines

I think that we can do (3) easily.
If we check memcg_cache_dead() in the end of put_cpu_partial() rather than in the begin of put_cpu_partial(), we can avoid the race you mentioned. If someone do put_cpu_partial() before dead flag is set, it can be zapped by who set dead flag. And if someone do put_cpu_partial() after dead flag is set, it can be zapped by who do put_cpu_partial().

After put_cpu_partial() adds a frozen slab to a per cpu partial list, the slab becomes visible to other threads, which means it can be unfrozen and freed. The latter can trigger cache destruction. Hence we shouldn't touch the cache, in particular call memcg_cache_dead() on it, after calling put_cpu_partial(), otherwise we can get use-after-free.

However, what you propose makes sense if we disable irqs before adding a slab to a partial list and enable them only after checking if the cache is dead and unfreezing all partials if so, i.e.

mm/slub.c +15 -0

index d96faa2464c3..14b9e9a8677c 100644
@@ -2030,8 +2030,15 @@ static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
        struct page *oldpage;
        int pages;
        int pobjects;
+       unsigned long flags;
+       int irq_saved = 0;
 
        do {
+               if (irq_saved) {
+                       local_irq_restore(flags);
+                       irq_saved = 0;
+               }
+
                pages = 0;
                pobjects = 0;
                oldpage = this_cpu_read(s->cpu_slab->partial);

@@ -2062,8 +2069,16 @@ static void put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
                page->pobjects = pobjects;
                page->next = oldpage;
 
+               local_irq_save(flags);
+               irq_saved = 1;
+
        } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page)
                                                                != oldpage);
+
+       if (memcg_cache_dead(s))
+               unfreeze_partials(s, this_cpu_ptr(s->cpu_slab));
+
+       local_irq_restore(flags);
 #endif
 }
 

Quoted 3 lines

That would be safe against possible cache destruction, because to remove a slab from a per cpu partial list we have to run on the cpu it was frozen on. Disabling irqs makes it impossible.

Hmm... this is also a bit ugly.
How about following change?

Thanks.

mm/slub.c +0 -0

index 2b1ce69..6adab87 100644

mm/slub.c static void put_cpu_partial(struct kmem_cache · line 2065

Quoted 8 lines

mm/slub.c +4 -0

@@ -2058,6 +2058,21 @@ static void put_cpu_partial(struct kmem_cache
 *s, struct page *page, int drain)
 
        } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page)
                                                                != oldpage);
+
+       if (memcg_cache_dead(s)) {
+               bool done = false;
+               unsigned long flags;

Suppose we are preempted here. In the meanwhile all objects are freed to the cache, all frozen pages are unfrozen and also freed. The cache destruction is then scheduled (patch 2 of this set). Then when this thread continues execution it will operate on the cache that was destroyed - use-after-free.

I admit, this is very unlikely, but can we ignore this possibility?

From your comment, now, I realize that your cache destruction solution

Consider __slab_free(). After put_cpu_partial() in __slab_free() is called, we attempt to update stat. There is possibility that this operation could be use-after-free with your solution. Until now, we have just stat operation, but it could be more. I don't like to impose this constraint to the slab free path.

So IMHO, it is better that we should defer to destroy kmem_cache until last kfree() caller returns. Is it fair enough? :)

There is no use in keeping free objects/slabs on dead memcg caches, because they will never be allocated. So let's make cache_reap() shrink as many free objects from such caches as possible.

Note the difference between SLAB and SLUB handling of dead memcg caches. For SLUB, dead cache destruction is scheduled as soon as the last object is freed, because dead caches do not cache free objects. For SLAB, dead caches can keep some free objects on per cpu arrays, so that an empty dead cache will be hanging around until cache_reap() drains it.

We don't disable free objects caching for SLAB, because it would force kfree to always take a spin lock, which would degrade performance significantly.

Quoted 3 lines · Vladimir Davydov

We don't disable free objects caching for SLAB, because it would force kfree to always take a spin lock, which would degrade performance significantly.

You can use a similar approach than in SLUB. Reduce the size of the per cpu array objects to zero. Then SLAB will always fall back to its slow path in cache_flusharray() where you may be able to do something with less of an impact on performace.

Quoted 4 lines

You can use a similar approach than in SLUB. Reduce the size of the per cpu array objects to zero. Then SLAB will always fall back to its slow path in cache_flusharray() where you may be able to do something with less of an impact on performace.

In contrast to SLUB, for SLAB this will slow down kfree significantly.

Fast path for SLAB is just putting an object to a per cpu array, while the slow path requires taking a per node lock, which is much slower even with no contention. There still can be lots of objects in a dead memcg cache (e.g. hundreds of megabytes of dcache), so such performance degradation is not acceptable, IMO.

Quoted 6 lines · Vladimir Davydov

Quoted 4 lines

You can use a similar approach than in SLUB. Reduce the size of the per cpu array objects to zero. Then SLAB will always fall back to its slow path in cache_flusharray() where you may be able to do something with less of an impact on performace.

In contrast to SLUB, for SLAB this will slow down kfree significantly.

But that is only when you want to destroy a cache. This is similar.

Quoted 6 lines

Fast path for SLAB is just putting an object to a per cpu array, while the slow path requires taking a per node lock, which is much slower even with no contention. There still can be lots of objects in a dead memcg cache (e.g. hundreds of megabytes of dcache), so such performance degradation is not acceptable, IMO.

I am not sure that there is such a stark difference to SLUB. SLUB also takes the per node lock if necessary to handle freeing especially if you zap the per cpu partial slab pages.

There is no use in keeping free objects/slabs on dead memcg caches, because they will never be allocated. So let's make cache_reap() shrink as many free objects from such caches as possible.

Note the difference between SLAB and SLUB handling of dead memcg caches. For SLUB, dead cache destruction is scheduled as soon as the last object is freed, because dead caches do not cache free objects. For SLAB, dead caches can keep some free objects on per cpu arrays, so that an empty dead cache will be hanging around until cache_reap() drains it.

We don't disable free objects caching for SLAB, because it would force kfree to always take a spin lock, which would degrade performance significantly.

Since cache_reap() drains all caches once ~4 secs on each CPU, empty dead caches will die quickly.

Signed-off-by Vladimir Davydov <[email protected]>

---
 mm/slab.c |   17 ++++++++++++-----
 1 file changed, 12 insertions(+), 5 deletions(-)

mm/slab.c +6 -2

index cecc01bba389..d81e46316c99 100644
@@ -3985,6 +3985,11 @@ static void cache_reap(struct work_struct *w)
 		goto out;
 
 	list_for_each_entry(searchp, &slab_caches, list) {
+		int force = 0;
+
+		if (memcg_cache_dead(searchp))
+			force = 1;
+
 		check_irq_on();
 
 		/*

@@ -3996,7 +4001,7 @@ static void cache_reap(struct work_struct *w)
 
 		reap_alien(searchp, n);
 
-		drain_array(searchp, n, cpu_cache_get(searchp), 0, node);
+		drain_array(searchp, n, cpu_cache_get(searchp), force, node);
 
 		/*
 		 * These are racy checks but it does not matter

@@ -4007,15 +4012,17 @@ static void cache_reap(struct work_struct *w)
 
 		n->next_reap = jiffies + REAPTIMEOUT_NODE;
 
-		drain_array(searchp, n, n->shared, 0, node);

According to my code reading, slabs_to_free() doesn't return number of free slabs. This bug is introduced by 0fa8103b. I think that it is better to fix it before applyting this patch. Otherwise, use n->free_objects instead of slabs_tofree() to achieve your purpose correctly.

Quoted 4 lines

According to my code reading, slabs_to_free() doesn't return number of free slabs. This bug is introduced by 0fa8103b. I think that it is better to fix it before applyting this patch. Otherwise, use n->free_objects instead of slabs_tofree() to achieve your purpose correctly.

Hmm, I don't think slab_tofree() computes the number of free slabs wrong. If we have N free objects, there may be DIV_ROUND_UP(N,objs_per_slab) empty slabs at max, and that's exactly what slab_tofree() does, no?

2014-06-02 21:10 GMT+09:00 Vladimir Davydov <[email protected]>:

Quoted 10 lines · Joonsoo Kim

Quoted 4 lines

According to my code reading, slabs_to_free() doesn't return number of free slabs. This bug is introduced by 0fa8103b. I think that it is better to fix it before applyting this patch. Otherwise, use n->free_objects instead of slabs_tofree() to achieve your purpose correctly.

Hmm, I don't think slab_tofree() computes the number of free slabs wrong. If we have N free objects, there may be DIV_ROUND_UP(N,objs_per_slab) empty slabs at max, and that's exactly what slab_tofree() does, no?

BTW, we don't need DIV_ROUND_UP. I think that just N / objs_per_slab is sufficient to get number of empty slabs at max. Am I missing too?