Race in memcg kmem?

DISCUSSION Vladimir Davydov 3 participants 6 messages Dec 10, 2013 – Dec 18, 2013 cgroup

Share & tools

Vladimir Davydov

author

2013-12-10 13:59 UTC #0 lore raw

Hi,

Looking through the per-memcg kmem_cache initialization code, I have a bad feeling that it is prone to a race. Before getting to fixing it, I'd like to ensure this race is not only in my imagination. Here it goes.

We keep per-memcg kmem caches in the memcg_params field of each root cache. The memcg_params array is grown dynamically by memcg_update_cache_size(). I guess that if this function is executed concurrently with memcg_create_kmem_cache() we can get a race resulting in a memory leak.

-- memcg_create_kmem_cache(memcg, cachep) --
creates a new kmem_cache corresponding to a memcg and assigns it to the root cache; called in the background - it is OK to have several such functions trying to create a cache for the same memcg concurrently, but only one of them should succeed.
@cachep is the root cache
@memcg is the memcg we want to create a cache for.

The function:

A1) assures there is no cache corresponding to the memcg (if it is we have nothing to do):

    idx = memcg_cache_id(memcg);
    if (cachep->memcg_params[idx])
        goto out;

A2) creates and assigns a new cache:

    new_cachep = kmem_cache_dup(memcg, cachep);
    // init new_cachep
    cachep->memcg_params->memcg_caches[idx] = new_cachep;

-- memcg_update_cache_size(s, num_groups) --
grows s->memcg_params to accomodate data for num_groups memcg's @s is the root cache whose memcg_params we want to grow @num_groups is the new number of kmem-active cgroups (defines the new size of memcg_params array).

The function:

B1) allocates and assigns a new cache:

    cur_params = s->memcg_params;
    s->memcg_params = kzalloc(size, GFP_KERNEL);

B2) copies per-memcg cache ptrs from the old memcg_params array to the new one:

    for (i = 0; i < memcg_limited_groups_array_size; i++) {
        if (!cur_params->memcg_caches[i])
            continue;
        s->memcg_params->memcg_caches[i] =
                    cur_params->memcg_caches[i];
    }

B3) frees the old array:

    kfree(cur_params);

Since these two functions do not share any mutexes, we can get the following race:

Assume, by the time Cpu0 gets to memcg_create_kmem_cache(), the memcg cache has already been created by another thread, so this function should do nothing.

Cpu0 Cpu1
---- ----

B1

A1 we haven't initialized memcg_params yet so Cpu0 will
proceed to A2 to alloc and assign a new cache
A2
B2 Cpu1 rewrites the memcg cache ptr set by Cpu0 at A2
- a memory leak?
B3

I'd like to add that even if I'm right about the race, this is rather not critical, because memcg_update_cache_sizes() is called very rarely.

BTW, it seems to me that the way we update memcg_params in memcg_update_cache_size() make cache_from_memcg_idx() prone to use-after-free:

Quoted 7 lines

static inline struct kmem_cache * cache_from_memcg_idx(struct kmem_cache *s, int idx)
{
    if (!s->memcg_params)
        return NULL;
    return s->memcg_params->memcg_caches[idx];
}

This is equivalent to

1) struct memcg_cache_params *params = s->memcg_params;
2) return params->memcg_caches[idx];

If memcg_update_cache_size() is executed between steps 1 and 2 on another CPU, at step 2 we will dereference memcg_params that has already been freed. This is very unlikely, but still possible. Perhaps, we should free old memcg params only after a sync_rcu()?

Thanks.

Glauber Costa

2013-12-10 23:13 UTC #1 lore raw

Quoted 6 lines · Vladimir Davydov

Hi,
Looking through the per-memcg kmem_cache initialization code, I have a bad feeling that it is prone to a race. Before getting to fixing it, I'd like to ensure this race is not only in my imagination. Here it goes.

Quoted 6 lines

We keep per-memcg kmem caches in the memcg_params field of each root cache. The memcg_params array is grown dynamically by memcg_update_cache_size(). I guess that if this function is executed concurrently with memcg_create_kmem_cache() we can get a race resulting in a memory leak.

Ok, let's see.

Quoted 5 lines

-- memcg_create_kmem_cache(memcg, cachep) --
creates a new kmem_cache corresponding to a memcg and assigns it to the root cache; called in the background - it is OK to have several such functions trying to create a cache for the same memcg concurrently, but only one of them should succeed.

Yes.

Quoted 5 lines

@cachep is the root cache
@memcg is the memcg we want to create a cache for.
The function:

Quoted 8 lines

A1) assures there is no cache corresponding to the memcg (if it is we have nothing to do):
    idx = memcg_cache_id(memcg);
    if (cachep->memcg_params[idx])
        goto out;
A2) creates and assigns a new cache:
    new_cachep = kmem_cache_dup(memcg, cachep);

Please note this cannot proceed in parallel with memcg_update_cache_size(), because they both take the slab mutex.

Quoted 25 lines

    // init new_cachep
    cachep->memcg_params->memcg_caches[idx] = new_cachep;
-- memcg_update_cache_size(s, num_groups) --
grows s->memcg_params to accomodate data for num_groups memcg's @s is the root cache whose memcg_params we want to grow @num_groups is the new number of kmem-active cgroups (defines the new size of memcg_params array).
The function:
B1) allocates and assigns a new cache:
    cur_params = s->memcg_params;
    s->memcg_params = kzalloc(size, GFP_KERNEL);
B2) copies per-memcg cache ptrs from the old memcg_params array to the new one:
    for (i = 0; i < memcg_limited_groups_array_size; i++) {
        if (!cur_params->memcg_caches[i])
            continue;
        s->memcg_params->memcg_caches[i] =
                    cur_params->memcg_caches[i];
    }

Quoted 5 lines

B3) frees the old array:
    kfree(cur_params);
Since these two functions do not share any mutexes, we can get the

They do share a mutex, the slab mutex.

Quoted 16 lines

following race:
Assume, by the time Cpu0 gets to memcg_create_kmem_cache(), the memcg cache has already been created by another thread, so this function should do nothing.
Cpu0 Cpu1
---- ----
        B1
A1 we haven't initialized memcg_params yet so Cpu0 will
proceed to A2 to alloc and assign a new cache
A2
B2 Cpu1 rewrites the memcg cache ptr set by Cpu0 at A2
- a memory leak?
B3

Quoted 3 lines

I'd like to add that even if I'm right about the race, this is rather not critical, because memcg_update_cache_sizes() is called very rarely.

Every race is critical.

So, I am a bit lost by your description. Get back to me if I got anything wrong, but I am think that the point that you're missing is that all heavy slab operations
take the slab_mutex underneath, and that includes cache creation and update.

Quoted 15 lines

BTW, it seems to me that the way we update memcg_params in memcg_update_cache_size() make cache_from_memcg_idx() prone to use-after-free:
Quoted 7 lines
static inline struct kmem_cache * cache_from_memcg_idx(struct kmem_cache *s, int idx)
{
    if (!s->memcg_params)
        return NULL;
    return s->memcg_params->memcg_caches[idx];
}
This is equivalent to

Quoted 8 lines

1) struct memcg_cache_params *params = s->memcg_params;
2) return params->memcg_caches[idx];
If memcg_update_cache_size() is executed between steps 1 and 2 on another CPU, at step 2 we will dereference memcg_params that has already been freed. This is very unlikely, but still possible. Perhaps, we should free old memcg params only after a sync_rcu()?

You seem to be right in this one. Indeed, if my mind does not betray me, That is how I freed
the LRUs. (with synchronize_rcus).

Vladimir Davydov

author

2013-12-11 06:22 UTC #2 lore raw

Quoted 34 lines · Glauber Costa

Quoted 6 lines · Vladimir Davydov
Hi,
Looking through the per-memcg kmem_cache initialization code, I have a bad feeling that it is prone to a race. Before getting to fixing it, I'd like to ensure this race is not only in my imagination. Here it goes.
Quoted 6 lines
We keep per-memcg kmem caches in the memcg_params field of each root cache. The memcg_params array is grown dynamically by memcg_update_cache_size(). I guess that if this function is executed concurrently with memcg_create_kmem_cache() we can get a race resulting in a memory leak.
Ok, let's see.
Quoted 5 lines
-- memcg_create_kmem_cache(memcg, cachep) --
creates a new kmem_cache corresponding to a memcg and assigns it to the root cache; called in the background - it is OK to have several such functions trying to create a cache for the same memcg concurrently, but only one of them should succeed.
Yes.
Quoted 11 lines
@cachep is the root cache
@memcg is the memcg we want to create a cache for.
The function:
A1) assures there is no cache corresponding to the memcg (if it is we have nothing to do):
    idx = memcg_cache_id(memcg);
    if (cachep->memcg_params[idx])
        goto out;

Quoted 4 lines

Quoted 2 lines
A2) creates and assigns a new cache:
    new_cachep = kmem_cache_dup(memcg, cachep);
Please note this cannot proceed in parallel with memcg_update_cache_size(), because they both take the slab mutex.

Oh, I see. memcg_create_kmem_cache() takes and releases the slab mutex in kmem_cache_create_memcg(), which is called by kmem_cache_dup(). This effectively works as a barrier that does not allow A2 to proceed until memcg_update_cache_sizes() finishes, which makes the race implausible. Did not notice that at first. Thanks for clarification!

Quoted 76 lines

Quoted 26 lines
    // init new_cachep
    cachep->memcg_params->memcg_caches[idx] = new_cachep;
-- memcg_update_cache_size(s, num_groups) --
grows s->memcg_params to accomodate data for num_groups memcg's @s is the root cache whose memcg_params we want to grow @num_groups is the new number of kmem-active cgroups (defines the new size of memcg_params array).
The function:
B1) allocates and assigns a new cache:
    cur_params = s->memcg_params;
    s->memcg_params = kzalloc(size, GFP_KERNEL);
B2) copies per-memcg cache ptrs from the old memcg_params array to the new one:
    for (i = 0; i < memcg_limited_groups_array_size; i++) {
        if (!cur_params->memcg_caches[i])
            continue;
        s->memcg_params->memcg_caches[i] =
                    cur_params->memcg_caches[i];
    }
Quoted 5 lines
B3) frees the old array:
    kfree(cur_params);
Since these two functions do not share any mutexes, we can get the
They do share a mutex, the slab mutex.
Quoted 16 lines
following race:
Assume, by the time Cpu0 gets to memcg_create_kmem_cache(), the memcg cache has already been created by another thread, so this function should do nothing.
Cpu0 Cpu1
---- ----
        B1
A1 we haven't initialized memcg_params yet so Cpu0 will
proceed to A2 to alloc and assign a new cache
A2
B2 Cpu1 rewrites the memcg cache ptr set by Cpu0 at A2
- a memory leak?
B3
Quoted 3 lines
I'd like to add that even if I'm right about the race, this is rather not critical, because memcg_update_cache_sizes() is called very rarely.
Every race is critical.
So, I am a bit lost by your description. Get back to me if I got anything wrong, but I am think that the point that you're missing is that all heavy slab operations
take the slab_mutex underneath, and that includes cache creation and update.
Quoted 16 lines
BTW, it seems to me that the way we update memcg_params in memcg_update_cache_size() make cache_from_memcg_idx() prone to use-after-free:
Quoted 7 lines
static inline struct kmem_cache * cache_from_memcg_idx(struct kmem_cache *s, int idx)
{
    if (!s->memcg_params)
        return NULL;
    return s->memcg_params->memcg_caches[idx];
}
This is equivalent to
1) struct memcg_cache_params *params = s->memcg_params;
2) return params->memcg_caches[idx];

Quoted 8 lines

Quoted 5 lines
If memcg_update_cache_size() is executed between steps 1 and 2 on another CPU, at step 2 we will dereference memcg_params that has already been freed. This is very unlikely, but still possible. Perhaps, we should free old memcg params only after a sync_rcu()?
You seem to be right in this one. Indeed, if my mind does not betray me, That is how I freed
the LRUs. (with synchronize_rcus).

Yes, you freed LRUs only after a sync_rcu, that's why the way memcg_params is updated looks suspicious to me. I'll try to fix it then.

Thanks.

Michal Hocko

2013-12-12 13:21 UTC #3 lore raw

Quoted 2 lines · Vladimir Davydov

Quoted 1 line · Glauber Costa
On Tue, Dec 10, 2013 at 5:59 PM, Vladimir Davydov

[...]

Quoted 21 lines

Quoted 21 lines
Quoted 21 lines
-- memcg_update_cache_size(s, num_groups) --
grows s->memcg_params to accomodate data for num_groups memcg's @s is the root cache whose memcg_params we want to grow @num_groups is the new number of kmem-active cgroups (defines the new size of memcg_params array).
The function:
B1) allocates and assigns a new cache:
    cur_params = s->memcg_params;
    s->memcg_params = kzalloc(size, GFP_KERNEL);
B2) copies per-memcg cache ptrs from the old memcg_params array to the new one:
    for (i = 0; i < memcg_limited_groups_array_size; i++) {
        if (!cur_params->memcg_caches[i])
            continue;
        s->memcg_params->memcg_caches[i] =
                    cur_params->memcg_caches[i];
    }

Quoted 6 lines

Quoted 6 lines
Quoted 5 lines
B3) frees the old array:
    kfree(cur_params);
Since these two functions do not share any mutexes, we can get the
They do share a mutex, the slab mutex.

Worth sticking in a lock_dep_assert?

Quoted 49 lines

Quoted 49 lines
Quoted 17 lines
following race:
Assume, by the time Cpu0 gets to memcg_create_kmem_cache(), the memcg cache has already been created by another thread, so this function should do nothing.
Cpu0 Cpu1
---- ----
        B1
A1 we haven't initialized memcg_params yet so Cpu0 will
proceed to A2 to alloc and assign a new cache
A2
B2 Cpu1 rewrites the memcg cache ptr set by Cpu0 at A2
- a memory leak?
B3
Quoted 3 lines
I'd like to add that even if I'm right about the race, this is rather not critical, because memcg_update_cache_sizes() is called very rarely.
Every race is critical.
So, I am a bit lost by your description. Get back to me if I got anything wrong, but I am think that the point that you're missing is that all heavy slab operations
take the slab_mutex underneath, and that includes cache creation and update.
Quoted 21 lines
BTW, it seems to me that the way we update memcg_params in memcg_update_cache_size() make cache_from_memcg_idx() prone to use-after-free:
Quoted 7 lines
static inline struct kmem_cache * cache_from_memcg_idx(struct kmem_cache *s, int idx)
{
    if (!s->memcg_params)
        return NULL;
    return s->memcg_params->memcg_caches[idx];
}
This is equivalent to
1) struct memcg_cache_params *params = s->memcg_params;
2) return params->memcg_caches[idx];
If memcg_update_cache_size() is executed between steps 1 and 2 on another CPU, at step 2 we will dereference memcg_params that has already been freed. This is very unlikely, but still possible. Perhaps, we should free old memcg params only after a sync_rcu()?

Quoted 6 lines

Quoted 3 lines
You seem to be right in this one. Indeed, if my mind does not betray me, That is how I freed
the LRUs. (with synchronize_rcus).
Yes, you freed LRUs only after a sync_rcu, that's why the way memcg_params is updated looks suspicious to me. I'll try to fix it then.

I have quickly glanced through cache_from_memcg_idx users and the locking is quite inconsistent.
* mem_cgroup_slabinfo_read - memcg->slab_caches_mutex
* memcg_create_kmem_cache - memcg_cache_mutex
* kmem_cache_destroy_memcg_children - set_limit_mutex
* __memcg_kmem_get_cache - RCU read lock

I was afraid to go further...

memcg_update_cache_size and kmem_cache_create_memcg seem to be the only who touch memcg_params and they rely on slab_mutex. The later one is touching a cache which is not visible yet so it should be safe.

I didn't look closer at all the callers of cache_from_memcg_idx but I guess we want to use RCU here.

Signature · 2 lines

Michal Hocko
SUSE Labs

Vladimir Davydov

author

2013-12-12 13:39 UTC #4 lore raw

Quoted 25 lines · Michal Hocko

Quoted 2 lines · Vladimir Davydov
Quoted 1 line · Glauber Costa
On Tue, Dec 10, 2013 at 5:59 PM, Vladimir Davydov
[...]
Quoted 21 lines
Quoted 21 lines
Quoted 21 lines
-- memcg_update_cache_size(s, num_groups) --
grows s->memcg_params to accomodate data for num_groups memcg's @s is the root cache whose memcg_params we want to grow @num_groups is the new number of kmem-active cgroups (defines the new size of memcg_params array).
The function:
B1) allocates and assigns a new cache:
    cur_params = s->memcg_params;
    s->memcg_params = kzalloc(size, GFP_KERNEL);
B2) copies per-memcg cache ptrs from the old memcg_params array to the new one:
    for (i = 0; i < memcg_limited_groups_array_size; i++) {
        if (!cur_params->memcg_caches[i])
            continue;
        s->memcg_params->memcg_caches[i] =
                    cur_params->memcg_caches[i];
    }

Quoted 7 lines

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
B3) frees the old array:
    kfree(cur_params);
Since these two functions do not share any mutexes, we can get the
They do share a mutex, the slab mutex.
Worth sticking in a lock_dep_assert?

AFAIU, lockdep_assert_held() is not applicable here:
memcg_create_kmem_cache() is called w/o the slab_mutex held, but it calls kmem_cache_create_kmemcg(), which takes and releases this mutex, working as a barrier. Placing lockdep_assert_held() into the latter won't make things any clearer. IMO, we need a big good comment in memcg_create_kmem_cache() proving its correctness.

Thanks.

Vladimir Davydov

author

2013-12-18 07:51 UTC #5 lore raw

Quoted 31 lines · Vladimir Davydov

Quoted 30 lines · Michal Hocko
Quoted 2 lines · Vladimir Davydov
Quoted 1 line · Glauber Costa
On Tue, Dec 10, 2013 at 5:59 PM, Vladimir Davydov
[...]
Quoted 26 lines
Quoted 26 lines
Quoted 26 lines
-- memcg_update_cache_size(s, num_groups) --
grows s->memcg_params to accomodate data for num_groups memcg's @s is the root cache whose memcg_params we want to grow @num_groups is the new number of kmem-active cgroups (defines the new size of memcg_params array).
The function:
B1) allocates and assigns a new cache:
    cur_params = s->memcg_params;
    s->memcg_params = kzalloc(size, GFP_KERNEL);
B2) copies per-memcg cache ptrs from the old memcg_params array to the new one:
    for (i = 0; i < memcg_limited_groups_array_size; i++) {
        if (!cur_params->memcg_caches[i])
            continue;
        s->memcg_params->memcg_caches[i] =
                    cur_params->memcg_caches[i];
    }
B3) frees the old array:
    kfree(cur_params);
Since these two functions do not share any mutexes, we can get the

Quoted 8 lines

Quoted 2 lines
Quoted 1 line
Quoted 1 line
They do share a mutex, the slab mutex.
Worth sticking in a lock_dep_assert?
AFAIU, lockdep_assert_held() is not applicable here:
memcg_create_kmem_cache() is called w/o the slab_mutex held, but it calls kmem_cache_create_kmemcg(), which takes and releases this mutex, working as a barrier. Placing lockdep_assert_held() into the latter won't make things any clearer. IMO, we need a big good comment in memcg_create_kmem_cache() proving its correctness.

After a bit of thinking on the comment explaining why the race is impossible I seem to have found another one in these two functions.

Assume two threads schedule kmem_cache creation works for the same kmem_cache of the same memcg from __memcg_kmem_get_cache(). One of the works successfully creates it. Another work should fail then, but if it interleaves with memcg_update_cache_size() as follows, it does not:

memcg_create_kmem_cache() memcg_update_cache_size()
(called w/o mutexes held) (called with slab_mutex
held)
------------------------- -------------------------
mutex_lock(&memcg_cache_mutex)

                                                s->memcg_params=kzalloc(...)
new_cachep=cache_from_memcg_idx(cachep,idx)
// new_cachep==NULL => proceed to creation
                                                // initialize
s->memcg_params;
                                                // sets s->memcg_params
                                                //

->memcg_caches[idx]
new_cachep = kmem_cache_dup(memcg, cachep) // nothing prevents kmem_cache_dup from
// succeeding so ... cachep->memcg_params->memcg_caches[idx]=new_cachep // we've overwritten an existing cache ptr!

slab_mutex won't help here...

Anyway, I'm going to move check and initialization of memcg_caches[idx] from memcg_create_kmem_cache() to kmem_cache_create_memcg() under the slab_mutex eliminating every possibility of race there. Will send the patch soon.

Thanks.