Skip to contentSkip to conversation

Ways to mitigate limitations of percpu memory allocator

LSF/MM/BPF TOPIC Harry Yoo 5 participants 8 messages Feb 27 – Mar 6 Memory management

lore
Share & tools
lore

Harry Yoo

author
#0 lore raw

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

Global lock contention
=======================

Percpu allocator has a global lock when allocating or freeing memory. Of course, caching percpu memory is not always worth it, because it would meaningfully increase memory usage.

However, some users (e.g., fork+exec, tc filter) suffer from the lock contention when many CPUs allocate / free percpu memory concurrently.

That said, we need a way to cache percpu memory per cpu, in a selective way. As an opt-in approach, Mateusz Guzik proposed [1] keeping percpu memory in slab objects and letting slab cache them per cpu, with slab ctor+dtor pair: allocate percpu memory and associate it with slab object in constructor, and free it when deallocating slabs (with resurrecting slab destructor feature).

This only works when percpu memory is associated with slab objects. I would like to hear if anybody thinks it's still worth redesigning percpu memory allocator for better scalability.

Initialization of percpu data has high overhead
===============================================

Initializing percpu data has non-negligible overhead on systems with many CPUs. There's been a few approaches proposed to mitigate this. I'd like to discuss the status of ideas proposed, and potentially whether there are other approaches worth exploring.

Slab constructor + destructor Pair
----------------------------------

Percpu allocator doesn't distinguish types of objects
unlike slab and it doesn't support constructors that could avoid re-initializing them on every allocation.
One solution to this is using slab ctor+dtor pair; as long as a certain state is preserved on free (e.g. sum of percpu counter is zero), initialization needs to be done only once on construction.

Dual-mode percpu counters
-------------------------

Gabriel Krisman Bertazi proposed [2] introducing dual-mode percpu counters; single-threaded tasks use a simple counter, which is cheaper to initialize. Later when a new task is spawned, upgrade it to a more expensive, full-fledged counter.

On-demand initialization of mm_cid counters
-------------------------------------------

Mathieu Desnoyers proposed [3] initializing mm_cid counters on-demand on clone instead of initializing for all CPUs on every allocation.

[1] https://lore.kernel.org/linux-mm/[email protected]
[2] https://lore.kernel.org/linux-mm/[email protected]
[3] https://lore.kernel.org/linux-mm/[email protected]

Signature · 2 lines
Cheers,
Harry / Hyeonggon
#1 lore raw
Quoted 7 lines · Harry Yoo

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

I won't be going to LSF this year. But Jan was the proponent of my dual-mode pcpu initialization work and he'll be around. I'm not sure this requires a full session either, as it might not grasp broader interest. Are Mathieu and Mateusz attending?

Quoted 58 lines

Global lock contention
=======================

Percpu allocator has a global lock when allocating or freeing memory. Of course, caching percpu memory is not always worth it, because it would meaningfully increase memory usage.

However, some users (e.g., fork+exec, tc filter) suffer from the lock contention when many CPUs allocate / free percpu memory concurrently.

That said, we need a way to cache percpu memory per cpu, in a selective way. As an opt-in approach, Mateusz Guzik proposed [1] keeping percpu memory in slab objects and letting slab cache them per cpu, with slab ctor+dtor pair: allocate percpu memory and associate it with slab object in constructor, and free it when deallocating slabs (with resurrecting slab destructor feature).

This only works when percpu memory is associated with slab objects. I would like to hear if anybody thinks it's still worth redesigning percpu memory allocator for better scalability.

Initialization of percpu data has high overhead
===============================================

Initializing percpu data has non-negligible overhead on systems with many CPUs. There's been a few approaches proposed to mitigate this. I'd like to discuss the status of ideas proposed, and potentially whether there are other approaches worth exploring.

Slab constructor + destructor Pair
----------------------------------

Percpu allocator doesn't distinguish types of objects
unlike slab and it doesn't support constructors that could avoid re-initializing them on every allocation.
One solution to this is using slab ctor+dtor pair; as long as a certain state is preserved on free (e.g. sum of percpu counter is zero), initialization needs to be done only once on construction.

Dual-mode percpu counters
-------------------------

Gabriel Krisman Bertazi proposed [2] introducing dual-mode percpu counters; single-threaded tasks use a simple counter, which is cheaper to initialize. Later when a new task is spawned, upgrade it to a more expensive, full-fledged counter.

On-demand initialization of mm_cid counters
-------------------------------------------

Mathieu Desnoyers proposed [3] initializing mm_cid counters on-demand on clone instead of initializing for all CPUs on every allocation.

[1] https://lore.kernel.org/linux-mm/[email protected]
[2] https://lore.kernel.org/linux-mm/[email protected]
[3] https://lore.kernel.org/linux-mm/[email protected]

Signature · 1 line
Gabriel Krisman Bertazi
#2 lore raw
Quoted 10 lines · Gabriel Krisman Bertazi
Quoted 7 lines · Harry Yoo

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

Quoted 5 lines

I won't be going to LSF this year. But Jan was the proponent of my dual-mode pcpu initialization work and he'll be around. I'm not sure this requires a full session either, as it might not grasp broader interest. Are Mathieu and Mateusz attending?

No sorry, I was not planning to attend in person this year. Is it possible to attend remotely ?

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#3 lore raw
Quoted 11 lines · Mathieu Desnoyers
Quoted 10 lines · Gabriel Krisman Bertazi
Quoted 7 lines · Harry Yoo

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

Quoted 7 lines
Quoted 4 lines

I won't be going to LSF this year. But Jan was the proponent of my dual-mode pcpu initialization work and he'll be around. I'm not sure this requires a full session either, as it might not grasp broader interest. Are Mathieu and Mateusz attending?

No sorry, I was not planning to attend in person this year. Is it possible to attend remotely ?

We don't offer general remote attendance option but we will have two meeting owls available on site so we can set up something on case-by-case basis. If you're interested in remotely participating in this session, please talk to MM track leaders how / whether they can accommodate this.

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#4 lore raw
In reply to Harry Yoo
Quoted 25 lines · Harry Yoo

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

Global lock contention
=======================

Percpu allocator has a global lock when allocating or freeing memory. Of course, caching percpu memory is not always worth it, because it would meaningfully increase memory usage.

However, some users (e.g., fork+exec, tc filter) suffer from the lock contention when many CPUs allocate / free percpu memory concurrently.

That said, we need a way to cache percpu memory per cpu, in a selective way. As an opt-in approach, Mateusz Guzik proposed [1] keeping percpu memory in slab objects and letting slab cache them per cpu, with slab ctor+dtor pair: allocate percpu memory and associate it with slab object in constructor, and free it when deallocating slabs (with resurrecting slab destructor feature).

Quoted 3 lines

This only works when percpu memory is associated with slab objects. I would like to hear if anybody thinks it's still worth redesigning percpu memory allocator for better scalability.

I think this (make alloc_percpu actually scale) is the obvious suggestion. Everything else is just papering over the cracks.

Quoted 9 lines

Slab constructor + destructor Pair
----------------------------------

Percpu allocator doesn't distinguish types of objects
unlike slab and it doesn't support constructors that could avoid re-initializing them on every allocation.
One solution to this is using slab ctor+dtor pair; as long as a certain state is preserved on free (e.g. sum of percpu counter is zero), initialization needs to be done only once on construction.

As I said way back when, making an object permanently accessible a-la TYPESAFE_BY_RCU) is screwey and messes with the object lifetime too much. Not to mention the locking problems that we discussed back-and-forth.

Signature · 1 line
Pedro
#5 lore raw
Quoted 26 lines · Pedro Falcato
Quoted 25 lines · Harry Yoo

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

Global lock contention
=======================

Percpu allocator has a global lock when allocating or freeing memory. Of course, caching percpu memory is not always worth it, because it would meaningfully increase memory usage.

However, some users (e.g., fork+exec, tc filter) suffer from the lock contention when many CPUs allocate / free percpu memory concurrently.

That said, we need a way to cache percpu memory per cpu, in a selective way. As an opt-in approach, Mateusz Guzik proposed [1] keeping percpu memory in slab objects and letting slab cache them per cpu, with slab ctor+dtor pair: allocate percpu memory and associate it with slab object in constructor, and free it when deallocating slabs (with resurrecting slab destructor feature).

Quoted 6 lines
Quoted 3 lines

This only works when percpu memory is associated with slab objects. I would like to hear if anybody thinks it's still worth redesigning percpu memory allocator for better scalability.

I think this (make alloc_percpu actually scale) is the obvious suggestion. Everything else is just papering over the cracks.

I disagree. There are two separate (although related) issues that need solving. One issue is certainly scalability of the percpu allocator. Another issue (which is also visible in singlethreaded workloads) is that a percpu counter creation has a rather large cost even if the allocator is totally uncontended - this is because of the initialization (and final summarization) cost. And this is very visible e.g. in the fork() intensive loads such as shell scripts where we currently allocate several percpu arrays for each fork() and significant part of the fork() cost is currently the initialization of percpu arrays on larger machines. Reducing this overhead is a separate goal.

Quoted 10 lines
Quoted 9 lines

Slab constructor + destructor Pair
----------------------------------

Percpu allocator doesn't distinguish types of objects
unlike slab and it doesn't support constructors that could avoid re-initializing them on every allocation.
One solution to this is using slab ctor+dtor pair; as long as a certain state is preserved on free (e.g. sum of percpu counter is zero), initialization needs to be done only once on construction.

Quoted 3 lines

As I said way back when, making an object permanently accessible a-la TYPESAFE_BY_RCU) is screwey and messes with the object lifetime too much. Not to mention the locking problems that we discussed back-and-forth.

Yeah, I was not enthusiastic about this solution either.

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#6 lore raw
Quoted 34 lines · Jan Kara
Quoted 26 lines · Pedro Falcato
Quoted 25 lines · Harry Yoo

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

Global lock contention
=======================

Percpu allocator has a global lock when allocating or freeing memory. Of course, caching percpu memory is not always worth it, because it would meaningfully increase memory usage.

However, some users (e.g., fork+exec, tc filter) suffer from the lock contention when many CPUs allocate / free percpu memory concurrently.

That said, we need a way to cache percpu memory per cpu, in a selective way. As an opt-in approach, Mateusz Guzik proposed [1] keeping percpu memory in slab objects and letting slab cache them per cpu, with slab ctor+dtor pair: allocate percpu memory and associate it with slab object in constructor, and free it when deallocating slabs (with resurrecting slab destructor feature).

Quoted 6 lines
Quoted 3 lines

This only works when percpu memory is associated with slab objects. I would like to hear if anybody thinks it's still worth redesigning percpu memory allocator for better scalability.

I think this (make alloc_percpu actually scale) is the obvious suggestion. Everything else is just papering over the cracks.

Quoted 10 lines

I disagree. There are two separate (although related) issues that need solving. One issue is certainly scalability of the percpu allocator. Another issue (which is also visible in singlethreaded workloads) is that a percpu counter creation has a rather large cost even if the allocator is totally uncontended - this is because of the initialization (and final summarization) cost. And this is very visible e.g. in the fork() intensive loads such as shell scripts where we currently allocate several percpu arrays for each fork() and significant part of the fork() cost is currently the initialization of percpu arrays on larger machines. Reducing this overhead is a separate goal.

I agree that it's a separate issue. But it's as much of an issue for single-threaded processes as much as multi-threaded. Say you have a 64 core CPU. Why should you pay for 64 separate cores when you only spawned 2 threads? (and, yes, this is a not-so-rare situation, like lld which spawns up to 16 threads (https://reviews.llvm.org/D147493), even if you have hundreds of CPUs)

So perhaps the best way to go about this problem would be to go back to per-task RSS accounting. This one had problems with many-task RSS accuracy, but the current one has problems for many-cpu RSS accuracy. A single-threaded optimization could patch over the problem for the vast majority of programs, but exceptions exist.

Or another possible idea: lazily initialize these cpu counters somehow, on task switch.

I'm afraid that while the solution presented by Mathieu fixes a problem with the current scheme (insane inaccuracy on large-cpu-count), it might also add to the percpu allocation + init problem (this might not be true, I have not paid too much attention).

Signature · 1 line
Pedro
#7 lore raw
Quoted 47 lines · Pedro Falcato
Quoted 34 lines · Jan Kara
Quoted 26 lines · Pedro Falcato
Quoted 25 lines · Harry Yoo

Hi folks, I'd like to discuss ways to mitigate limitations of percpu memory allocator.

While the percpu memory allocator has served its role well, it has a few problems: 1) its global lock contention, and
2) lack of features to avoid high initialization cost of percpu memory.

Global lock contention
=======================

Percpu allocator has a global lock when allocating or freeing memory. Of course, caching percpu memory is not always worth it, because it would meaningfully increase memory usage.

However, some users (e.g., fork+exec, tc filter) suffer from the lock contention when many CPUs allocate / free percpu memory concurrently.

That said, we need a way to cache percpu memory per cpu, in a selective way. As an opt-in approach, Mateusz Guzik proposed [1] keeping percpu memory in slab objects and letting slab cache them per cpu, with slab ctor+dtor pair: allocate percpu memory and associate it with slab object in constructor, and free it when deallocating slabs (with resurrecting slab destructor feature).

Quoted 6 lines
Quoted 3 lines

This only works when percpu memory is associated with slab objects. I would like to hear if anybody thinks it's still worth redesigning percpu memory allocator for better scalability.

I think this (make alloc_percpu actually scale) is the obvious suggestion. Everything else is just papering over the cracks.

Quoted 10 lines

I disagree. There are two separate (although related) issues that need solving. One issue is certainly scalability of the percpu allocator. Another issue (which is also visible in singlethreaded workloads) is that a percpu counter creation has a rather large cost even if the allocator is totally uncontended - this is because of the initialization (and final summarization) cost. And this is very visible e.g. in the fork() intensive loads such as shell scripts where we currently allocate several percpu arrays for each fork() and significant part of the fork() cost is currently the initialization of percpu arrays on larger machines. Reducing this overhead is a separate goal.

Quoted 6 lines

I agree that it's a separate issue. But it's as much of an issue for single-threaded processes as much as multi-threaded. Say you have a 64 core CPU. Why should you pay for 64 separate cores when you only spawned 2 threads? (and, yes, this is a not-so-rare situation, like lld which spawns up to 16 threads (https://reviews.llvm.org/D147493), even if you have hundreds of CPUs)

True. Still, being an up-front initialization cost, it is the most relevant the shortest the task lives. I'd imagine that even for something as lld doing 16 clone syscalls, the overhead of a single percpu counter initialization is a very small blip in the profile, not worth special-casing for. The single-threaded case is the obvious optimizable-case in this sense.

Quoted 3 lines

So perhaps the best way to go about this problem would be to go back to per-task RSS accounting. This one had problems with many-task RSS accuracy, but the current one has problems for many-cpu RSS accuracy.

The current pcpu one has a much smaller accuracy error than per-task, which justified its inclusion in the first place, no? IIRC, there was a real use case where the worse accuracy mattered for process selection during OOM.

Quoted 13 lines

A single-threaded
optimization could patch over the problem for the vast majority of programs, but exceptions exist.

Or another possible idea: lazily initialize these cpu counters somehow, on task switch.

I'm afraid that while the solution presented by Mathieu fixes a problem with the current scheme (insane inaccuracy on large-cpu-count), it might also add to the percpu allocation + init problem (this might not be true, I have not paid too much attention).

Signature · 1 line
Gabriel Krisman Bertazi