All right, so when I get started, so next up, we've got Material NWA, who's going to be talking
to us about waste-free PLCPU, users-based memory allocation.
All right, thank you, Stefan.
So just as a segue from the previous talk, so the comment topic there is trying not to waste
memory, right, but here my focus is more on user space.
So I'm Mattie Dinoye, I'm a CEO at EPCS, and I'm maintaining the restortable sequence
and memory or system calls, as well as the LTTNG Tracer and in this context, Lebarsec.
It's not, there's no release yet of that project, it's a master branch, but it's a project
that aims at improving per CPU that has structured access in user space.
So, and for that, I need to allocate per CPU data structures, and we'll see how we can do things
better with the Lebarsec project.
All right, so the goal of this presentation, first it's to discuss scaling of data structures
by partitioning, just give a bit of context, discuss the challenges associated with the
use of per CPU data in user space, memory use, file sharing, cache line waste, present
the Lebarsec sample, or CPU allocator, discuss the current M map, M advice, MFDO, pen limitation
with respect shared mappings, meant to be local to a process, because when something is shared,
it's shared with the children after a fork or clone.
So scaling data structures, I'm going to go quickly there because I think there are quite
a few kernel developers in the room, so I'm not going to learn, nobody's going to learn
anything new.
So scope and partitioning of that structure, scope you have stack data, heap partitioning,
you have global variables, tread local storage, in the kernel, that would be adding stuff
into the task, which one though, thread task, well, the Per CPU data, task struct, yes.
So Per CPU data is actually very good, so each CPU access its own data, however, on larger
machines today, that pos some challenges as we will see for user space.
So tread local storage, TLS, so when the workload has much more threads than the system
as CPUs, then it becomes, it leads to inefficient views of the CPU cache, because things
that could be shared between threads end up having those per thread copy.
The access for tread are really, really fast, but if you're bouncing between threads,
then you're invalidating the cache from the other threads.
It's only static definition.
So initialization of large TLS areas, slow down tread creation, still I'm talking about
user space here, right?
So we're in the kernel trap, but I'm talking about how the kernel can help improve user
space, and we'll get to that.
So global dynamic TLS model for shared object is lower than initial exec, and I have additional
side effects.
So Per CPU data is an alternative to TLS, so it's a partitioning strategy that is widely
used within the Linux kernel, but it's not used so much in user space as far as I know.
And when it's used, there's actually this entire pattern that we observe.
People just declare arrays of Per CPU items.
They basically calculate, what's my worst possible case for the number of CPUs?
I just create an array of Per CPU items, and I indexed by the current CPU number.
What can go wrong there?
Well, we'll see.
So in the index, either with the result of schedule CPU, or the RSEC CPU ID field.
Actually, since Linux 6.3, RSEC added a new concurrency ID field, which basically gives
you an index into a first view data structure, but which is indexed by a current index
value that you have within the process that is, as close to zero as possible, allocated
by the scheduler based on the number of concurrently running threads.
So here, we have this entire pattern back to this entity pattern.
So at the left side, we can see fall sharing.
So if you don't align the elements, and they are smaller than a cache line, then you
end up having cache line bouncing across your CPUs that do access to different indexes
in your data structure.
So one solution for that, you'll say, well, okay, let's align each of those data structure,
cache line align.
Well, the problem there is, if you do that for a lot of data in your program, you're
actually wasting hot cache lines with padding.
So you're not, so your functional density of the cache line becomes really bad.
So yeah, just as I said, elements not cache line align, it hurts performance due to fall
sharing if they are a cache line align with padding, you waste cache lines.
So if we look at how the Linux kernel get away with that is by implementing its own
CPU allocator.
It basically maps a memory range on each CPU, and the memory allocator allocates ranges
at the same offset on semantically on each CPU.
So when you get some CPU data pointer that you've allocated, you then use it by indexing
it with a stride.
That will give you the, well, not necessarily as stride, they can do tricks with segments
and select on some architectures, but the idea is, you actually offset in your own
pursuit data.
So I've implemented the similar track for user space in the LIDAR-SEC MENPOL
Per CPU allocator.
So it's a port of those Per CPU kernel allocator concepts, two user space.
It's implemented as a user space API with the LIDAR-SEC, and it basically, so I have an API
to allow user space to create memory pool.
Polls, sorry, each pool maps a memory range, and it's actually a array of Per CPU areas.
So the user can define the size of those areas, for instance, it can be 64 kilobyte per
CPU, and then the allocation against the pool reserved memory at the same offset for each
CPU when it's reserved.
So here's the layout of the MENPOL range.
So we've allocated memory for each of those CPUs, each have their own Per CPU area,
and it's all a contegress.
Then we have the allocation for our stride A, I've reserved the first slot, let's say,
and stride B, the second slot, and then the rest is unallocated.
So the memory access pattern, so we replace a memory of Per CPU variables, so that was
the anti-pattern, anti-pattern that I told you about earlier, where you have the base pointer,
and then you offset by multiplying the CPU times size of your item, that would be the anti-pattern.
We replace that by just flipping over the calculation.
So rather than having an item to the array base pointer, we have pointer, and I'm going back
one's line, so you'd have a pointer to struck B in CPU zero.
Then we add CPU number times pull stride.
So if the pull stride is 64K by default, that gets you to struck B on the right CPU on which
you are.
So that's how you get to your Per CPU data.
So as you'll see, it's a base plus multiplication, so it's the same thing as it was before,
but we're gaining something.
What we're gaining is we're placing all the memory for a given CPU together, so we don't
have to add this padding between the members by having all the items separately for
a CPU.
Okay.
So allocating from a pull, so it returns a pointer to the array of CPU zero, combines
information about the base of the pull range and offset of the item.
So that's the mempool range layout with metadata, so we can see the same per CPU memory
array as that I showed you before.
Now we can see additional things added there.
So I have a header page.
I have a cannery page, initial values, and if configured in robust mode, there's a
free list as well there.
So the header page I'm going to come back to this, but this is to end all freeing memory.
The cannery page is to end all fork, and I'm going to tell you why then later.
The in-ed values, I'm coming back to this, so I'll come back a lot to that slide.
So the in-ed value is to, it's meant to populate the initialization values of newly
allocated memory array without requiring the system to allocate physical memory for each
possible CPU.
And that's a big part of the challenge of doing a CPU allocator in user space.
So you end up in continuous scenario where the CPU set, to restrict you to a subset of CPUs,
but then as soon as you start walking over all your CPU indexes to initialize data,
you've actually done copy on right or required allocation of actual memory, and then, well,
that hurts memory consumption.
So freeing items from pool.
So I wanted to support multiple pools to provide isolation between users, so it's not
a single pool per process.
It's really multiple pools.
But I wanted to do so without requiring the API of free to take a next-door argument besides
the pointer to free.
So here's how I did it.
So I need to reach the pool free list from a pointer to be free.
So how I do it is by aligning the pool range at specific addresses and applying a mask on
the pointer to figure out where that base starts.
So here, I have a pointer that in the range of CPUs, I apply a mask, I find the header
page, the header page, ask everything I need.
That's basically how I do it.
So it's a line, so there's no aligning map exposed by the kernel, so the trick I do is
I align larger than I need, and then I cut away the pieces I don't need.
Memory initialization.
Yeah, so touching every CPU on lower system is an issue.
If you have think a bit with 500 and 12 or more hardware threads, and then you have a
container that restrict your CPU sets or skip affinity, you don't want to touch the
Per CPU area that is not used in that container.
You may want, so in my case, I reserve virtual memory, but I don't want to reserve physical
memory for this.
So that's why I introduced a R-Squec-memical Per CPU malachinette.
So in order to allow the application to stop using this pattern of let's allocate memory
and touch every thing for every possible CPU, I include the initialization in the allocator.
So you pass the initialization pointer and length to the allocator saying, well, that's
what I want, to that memory to be initialized to.
Then I allocate a additional in a range mapping, that's at the end of those mapping, the
in-advalues after the last CPU.
This additional range, so it's a memfd, which has a copy on right mapping for each.
So initially, so we create a memfd, we have this memfd, we have this in-advalue, which
is a memfd, and it's shared mapping, and it has a private mapping of that same range, of
that same backing file, a RIA, into each of the CPU.
Those are private though.
So they observe the change to the in-advalues, but as soon as you write into one of those
CPU, a RIA, they trigger a copy on right, and then they get their own copy of the page.
So it's not for the entire thing, it's page per page that this is done using a copy on right mechanism.
All right, this is, yeah, on-store.
So the idea is we write the initial content of the newly allocated RIA, so let's say you
malach in it something.
We write the initial content in the in-adrange for that small block of data.
We iterate on all possible CPU, and read the content visible from each CPU mapping,
compare it with the in-adrange.
If it matches, there's no need to store, it means there was no copy on right.
We still have this shared backing page.
If it does not match, it means a copy on right has happened to the page due to store from that
CPU.
So then we need to store the initial contents on that CPU mapping as well.
So it ensures that memory is only reserved when it is actively used, stored to by active CPUs.
So the link of four can clone is tricky as well.
So the problem is, with memory of the open, the in-adrange that we create are shared,
and there's no kind of memory of the private flag.
So the one thing I would like to see happening eventually, and I'd like your feedback on that,
is to add a new flag to memory of the open, saying, well, this backing file is private,
to the process.
So there could be multiple shared mappings of that backing file within the process.
And that's all fine, and then you can do map private and everything.
But backing file, if you clone or fork in the child process, it would not be the same backing file.
It would be a copy of that backing file with the exact same MMVMA's layout and everything on that new backing file.
So that's something that would be interesting to, and I'd like to have your feedback on that.
That would be, so currently, I need to use a workaround using M advice.
So I have this cannery page where I do a don't fork M advice to basically,
and I use wipe on fork.
So I don't fork the rest of the mappings of this cannery page with wipe on fork.
That clears a bit in that page to allow me to detect that I'm actually in a child in a fork.
So I don't allow users to use those memory area across fork.
So that's documented.
So but with the MMV private or equivalent, that would solve all this.
So there's a bunch of additional features as well.
So they put auto-expans to add additional ranges when arranges fully allocated.
The MMV can be configured to either do the copy on right from in a range that I showed or from a zero page.
There's a corruption checks as well.
There's a notion of MMV set.
That's a collection of power of two allocation size pools.
So future work, adding support for allocation of variable sized element within a pool,
that would be interesting.
Add a guard page between perceived data to eliminate a cash line bouncing caused by hardware
prefetch in sequential pattern access.
So I actually noticed that in when benchmarking.
So when you have access pattern, that really reads sequentially up to the end of the page.
If you don't put a guard page in there, it's actually going to bleed on intel.
It's going to bleed the read on the next perceived data.
And you're actually causing false cash line bouncing because of that.
So other in depth, future work.
So as I said, figuring out a way to have an enemy move file that is prior to a process that would help a lot.
Meanwhile, I could also work around that for the single shredded case with the copy in a
picture that's workender, that's not done yet.
And then there's other work I intend to work on on the C Group CPU controller to allow
expressing concurrency limits without CPU sets.
I presented that yesterday in the container's rack.
So and that's a small slide on MMV create, MMV private.
So for can clone can be handled more robustly by adding a MMV private flag to
MMV create.
I explained that earlier, the use case.
So it's not just the main rule per CPU allocator.
There's a mesh allocator that exists that would require this as well.
The same physical page at different addresses to reduce internal allocator
fragmentation.
And there's also some Google dynamic analysis tools that require
map shared mappings of a given page within a process.
And they would like to be able to map private on fork.
So that's all I have.
And we have time for questions.
So this is per CPU variables for a user space.
Right?
Yes.
So what's conceptually?
What's the difference between TLS like Burr threat and per CPU?
I mean, from user space point of view that it should be interchangeable.
So for TLS, you define a global variable or static variable.
For per CPU, you can allocate dynamically instead.
So he think you're really dynamic allocation of memory, which you don't have with TLS.
And the TLS, you have one copy of the variable per threat.
Per CPU, you have one copy of the variable per physical hardware threat.
So if you have a system where you have tons and tons and tons and tons of
worker threads, then they are much more than the number of physical hardware
resources, then you misuse your memory because you're allocating
which much and you actually can start having, well, you don't use your CPU
cache as well, also in those cases.
But those are for different use cases, I would say.
Not all algorithm that can be done in TLS are suitable for
per CPU.
You really need to think about it.
Thank you.
Other questions?
Yeah, exactly.
You said it's for different use cases.
I totally get that.
But what I still fail to see is a use case that really makes
per CPU data interesting in user space because how do I
how do I deal with atomicity?
So my flat can be scheduled to a different core and a different
flat can be scheduled to the same CPU.
So how do I deal with concurrency with consistency?
Consistency.
Yes, I was looking forward.
Yeah, I'm glad you asked that question.
So I maintain the restortable sequence system call RSEC.
And it's meant to handle just that problem.
So you can create small critical sections in assembly.
And you let the kernel know if that if it preamps you.
So preemption, signal delivery, and migration,
it's going to move your instruction pointer to an abortender.
So that allow, so if you complete that critical section,
it meant it all ran on the same CPU.
So you are guaranteed that nobody has played on that
that structure while you were running.
Yeah.
Thank you very much for our interest in presentation.
Could it please shortly describe the main difference
between TCMALAQ, HP, CPU, cache, and year approach?
So the TCMALAQ perceived you caches.
So as I understand TCMALAQ, so those are caches for allocation
of memory that is meant to be used across the entire system.
In my case, this is per CPU memory areas.
So the difference is, so the TCMALAQ perceived you caches.
They want to quickly be able to reuse a memory area
that they've allocated, and then it's reclaimed,
and then they want to reuse it quickly.
So it's a fast path that bypasses lower allocator.
So in my case, I'm not allocating memory
meant to be handed over.
So it's not a single area of memory.
What I'm allocating is let's say I have 512 CPU.
So similarly, you do one allocation, you get 512
smaller areas of memory, and depending on which CPU you are,
you're using the current area that belong to your CPU.
So it's a allocator of per CPU data,
and not a cache that is per CPU for a generic allocator.
It's a specialized allocator that I do.
May I ask one more short question.
So as I understand, it can be used by TCMALAQ
to implement their base BPSPU caches.
You are correct.
Thank you so much.
Welcome.
Any questions?
If not, thank you very much.