Hello and welcome. We had just some technical issues presenting with the laptop, but now
it's working with a picture, right? Okay, so let's welcome Neil Scuroil, welcome at
for them and we'll hear his talk, a memory allocator with only 6,000 percent, 30,000
percent fixed overhead written from the scratch, something with big storage you want to
allocate small things. Thank you, let's go.
Hello everyone, so before we start for real, I need to fix something, because we need
to do something about this click baity title or in your case, your appearance baity title.
So what are the actual numbers that I was referring to there?
It's for a given page size that the memory allocator can out at the minimum to bits.
So if you go through the numbers that gives you 4,000 by pages, these 0.006 percent
from the first title. So just to illustrate and give you a bit of a feeling, if you want to manage
one petabyte at 4 kilobit pages, that's 65 gigabytes, just the feeling for that.
And obviously if you choose smaller pages, this overhead will increase.
So at 256 byte pages, the overhead is one order of, so it goes from mega to kilo from
giga to kilo, two giga to mega is a price.
So welcome to a memory allocator with a fixed overhead of 2 to the power of s minus p minus 2
for an arena size of 2 to the power of s and the minimal page size of 2 to the power of p written from scratch.
So my name is Niels. I'm an old guy. I know Linux since I was a teen. I have a degree.
I run an ISP and then another one and another one.
I learned everything from fos. So to all the people who came before me, I owe you a lot.
I feel like I learned nothing at university and everything from staring at other people's code.
For quite some time now, I'm an independent consultant and developer who runs a small company.
Also, for a couple of years now, I'm one of three maintainers of a beautiful piece of software called Warnish Cash, which also this project is about.
It's called slash slash with this slash.
It's licensed LGPA, comparably small, so WC tells me it's 36,000 lines of code including comments,
so something in that ballpark.
What it implements are two storage engines for Warnish Cash, so Warnish Cash has a module concept to extend the build in language, which is called WCL,
but also since quite actually since this project, also to extend core fundamental core functionality.
And one of the relevant components in Warnish Cash is where it's responsible for actually storing the object somewhere.
So if Warnish Cash later asks for it, it gets it back a bit like a file system in metadata.
So this project comprises two storage engines, one is called body, and we will see in just a moment why.
For in memory, cash only, so a cash that you lose when the process restarts or the machine restarts.
And one is called fellow, which is implements here, disc memory storage.
This storage is eventually persistent, which means depending on which compromise you're willing to take, you might lose a couple of seconds or more before you can reload your objects.
It's always consistent, so whatever you do, as long as you deliberately program your hardware to miss behave.
It should always come up consistently with something usable.
It implements ASNGIO, or uses ASNGIO as implemented in IO during, but we also have two other implementations.
And for the even broader context, the first sponsor who made this all possible, they run a video CD and so you can, that's probably illustrative of where the numbers are coming from.
So when I was, when I agreed with the sponsor that I would actually be doing this,
I went through some kind of requirements design phase, and besides the huge storage that it's obviously need to support to be useful.
I also wanted to solve some other issues along the way, so I had my own little requirements in design list on top of that.
First, there is an LIEU fairness problem with the built-in storage implementations.
So for this implementation, I really wanted to make sure that a request which has already been waiting, and is now at the top of the queue, which actually turned out to be the implementation.
So, anyway, first come first served for allocation requests.
I absolutely wanted to have a fixed size, both in memory and in on disk.
So the advantage cache in the built-in storage engine, it's quite an issue that they will take more memory than you configure.
I mean, that's obviously documented, but you never quite know how much more.
So for this implementation, I absolutely wanted to fix size, and ensure I wanted efficiency in managed cache, where we have this efficiency fetish, nothing beats it.
So the little more detail, what comes out of these requirements, or came out of these requirements for me was,
I absolutely did not want to manage free maps, so meta information about free space on disk.
I did not want to do any disk I owe just to manage space.
And upon that this question, can I somehow really be doable to support multiple petabytes of storage with reasonable amounts of RAM?
I mean, it doesn't need to support a petabyte in my laptop, but maybe in a data center server.
Then there was a kind of coincidence that I carried in my, in my thoughts, this idea of the body allocator, which I at one point had read about.
And really, yeah, I thought it was really a cool idea.
Invented as per Wikipedia in 1963 by Harry Markovitz, it's advisable to use in kernels, and I guess in many other places.
And the base idea is that the allocator manages a hierarchy of power of two page sizes.
We'll see that illustrated in a moment.
And with this hierarchy of pages that adjacent pages can merge into the next power of two, or be split into two powers of two lower.
So let's look at an example.
This is super simplified.
In this case, me, the example only has three different page sizes, but really for this idea, it doesn't matter at all if you draw eight or 20 or three.
And if we started with our empty arena, all our page, excuse me, all our free memory will be in just one page.
Actually, through in in in practice, if if I run a one terabyte arena, because it's a power of two initially, I will have one free page off size one terabyte.
Now in this example, that's suppose we want to allocate one of these middle sized pages.
So we split. First of all, we take the top page split it.
When we end up with one allocated here shown blue and one free page shown in white.
Now, if we want to allocate another page this time, a small size, we do that split again, have one page which we can use and another page which is free.
Now, let's do this stuff in reverse, but different order. So we free the bigger page first.
That's then super simple. We do nothing but just marking it free.
But now if we free the little blue page again, also, all these merge into just one page again.
So that's really, I think, this auto coalescing of free space is really what I think is wonderful about the body allocator idea.
So what is the memory allocator about on a very fundamental level?
It's maybe for other things like detecting out of bounds access for, yeah, depending on the API, it might need to also track allocated space.
But fundamentally, it's really not concerned that this space you have already allocated, it's concerned with the space that is free.
That is this way of thinking about it, help me get into the topic.
If free space is actual memory. So if the allocator, it would be talking about was actually only for memory like RAM.
It's what I'm what easy to manage free space because we have plenty of free space as long as we have free space, right?
Because that's RAM. We can put metadata in there.
But if you want to manage free space on disk, there is no RAM that comes with it.
And if we don't want to do I owe to manage free space, well, there will be nice if the metadata fit into RAM.
For traditional approaches, also the management of the free space scales with the fragmentation.
So the more little blocks you have that you need to track, obviously the more metadata you need.
Which is bad for this predictability thing that I talked about a moment ago.
So what was this fundamental idea? Take a body allocator and for all these boxes, just use single bits.
So many, many, many, many, I get allocator. I've looked at they use linked list, trees, whatever.
But in this implementation, I thought okay, but yeah, but they could be bits, right?
So what we end up with this implementation is just one huge bit field for each of these levels.
So in this case, the top bit would be one bit field, the middle and the low bit would all be one bit field.
Excuse me.
And yeah, I just chose to set bits to mark free pages.
It could probably be the other way around that the free pages are zero and one, it probably doesn't matter.
So to jump ahead a little bit, I would like to show you what one nice thing which we can do.
If we use these bit fields, because we can map these bit fields into shit.
Okay, my fondest small excuse me, at the fondest too big.
Right.
So we should see at the top, that there are 13 terabytes of memory managed here.
This is my burn and machine.
So at the top right you see 1429 yada yada bytes total, that's 13 terabytes.
And we are looking at the memory management live.
This is not a mockup or anything you can download the software anyway.
So each character on the screen at this level, at the zoom level represents 8 gigabytes.
And we see that stuff happening there at the left.
Changing between fully taken, which is the star and partly taken, which is the slash.
Yeah, it's because we can zoom in, we can scroll down, we can scroll up.
So yeah, it's a nice gimmick, but trust me, this has helped me keep finding my nasty bugs.
Being able to visualize something is super important and what really amazes me is that it gives you exactly what the memory
memory calculator is using in a safe manner, because the memory map file, which is used to keep the information that is used to keep the bit fields,
is map read only into another process, while the main process here, one is the does its actual thing.
And the other process, this one slash map, it cannot do any harm because it only sees read only mapings.
They come slide, okay.
So now I want to go dive a little deeper with you into the implementation and some of the things I came across.
What do we need to implement for to get a memory allocator?
First of all, a bit of a weird name, I call the free implement, sorry, what you usually, you're in all known malloc and free.
So what you know is free, I call return, because the memories return to the allocator.
I don't know what struck me for some reason, I thought free was already confusing me, so it's called return.
The allocation and the return, what do we need to get them?
We need to be able to free a single page to take a single page.
We need to be able to split the page into merge pages.
Also we need to find space.
And the following examples contain pseudo C, just for readability.
But it's close to what I actually have.
So let's think back at the body allocator and using bit fields.
So if we want to free a page, I said I'm using the set bits to mark the free pages.
So what is freeing a page then is just setting a bit super simple.
The only thing is that the bit fields might be gigabytes in size, but it's just finding the right bird and setting the right bit.
Conversely, the take is just to clear, but if you know that a page is free and you want to take it, clear the bit.
For the split, it's also super, super simple.
And this is the first of all we take one page which we know is free.
Then we go one level down, mark the right page is free because we're not going to need it.
Go one level down.
By the way, the right page is always the uneven one.
So the left end page is always even, the right end page is always uneven.
If you number the page is starting at the zero.
Then we do that again, and we do that again, and then we have the small allocation that we want out of the split.
We need to reverse that.
I don't have a full animation for the merge, but it's pretty clear if you think about it.
So we know that the body page, the one we potentially merge with is the same page number is our page number with just the last bit flipped.
This is our always our body.
So we look at this body and check, okay, while it's in bounds.
So while it's not beyond the end of the bit field.
And it's free so we can take it.
We do that.
And just continue at the next level.
I think this is just, yeah, I mean, I didn't come up with the body idea.
I just found it super nice that I can have the two main functions of the locator in something like 10 lines.
Finding space is finding set bits.
So for 64 bits, we have a compiler built in, which we can, which we can use.
But now the problem is if we have more than 64 bits, if we have more than 64 pages, what do we do?
Yeah, okay, what do you always do?
You turn a linear search into a logarithmic time search.
And in this case, use an index, which is also a bit field, using the same code.
So here's an example.
64 bits are not a good idea to fit onto a slide.
So this example is just with four bit words, but it's the same principle.
So at the bottom is our actual bit field that we, that managers are free pages.
And now what we can very simply do is just maintain another layer of another bit field layer, which has one bits,
whenever the word is non-zero, not just the individual bit, and then do that again, and again, and again.
Yeah, we end up with an index.
Then finding space is just consulting the index until there is one, as long as there is one.
And if the index already says, okay, I don't have any space.
Then we know we're done, and otherwise we have found a hidden, unroll the recursion.
Probably would need to be read on in a closed form, but I didn't bother so far.
So that is what I've just been talking about is finding a page of a certain size where you know that there should be one in the bit field, just find a bit in the bit field.
But we also need to find the right page size to use for an allocation request.
So if the right allocation size is not available, what the body allocator you normally does is it looks upwards.
It looks for larger pages to be for larger free pages and splits them as explained before.
But in this case, for my application, there's also another thing we can do, because if you watch your video on your smartphone,
and one of the sketch needs to fetch that video from some back in somewhere, it's totally happy with storing that in this size.
In this, this chunk size or another chunk size, it doesn't matter so much, it matters a bit for performance, but it doesn't really matter that much.
So that we can make the deliberate decision to fetch the data in smaller sizes, then we would ideally want.
And thus the scram parameter which are introduced to the allocator, which just tells that there is a negative and a positive form, which is slightly different, but in principle, the absolute value matters which just the allocator.
Okay, I'm also fine with a allocation, which is that many orders of magnitude smaller, that many powers of two smaller powers of two smaller.
If you read about body allocators, or at least when I did, I always found this statement, or the body allocator will always return whatever size you requested, rounded up to the next power of two, and sure.
First thing that it does is just that, it knows only powers of two, so in the first place, it gives you that.
But we can do something, we can trim the allocation to the size that the request wanted, and then return the leftover to the allocator.
So that way, okay, you get all these little trim, trimings, as free space, but many of your applications just happens to make use of them.
And the grand stuff that I just talked about is one way to make one way to make it possible to use these trimings.
Something about a look, fragmentation.
All memory allocators fragment. I mean, if you think about it, your memory allocator and people can come to you and allocate all kinds of different countries, sizes, ultimately there will be, and return them and then allocate something else.
There will always be fragmentation, there will always be small parts, which cannot be merged again into bigger parts.
So can we have the Windows 95 defragment tool, and for this application as a web cache, you actually can, because when the cache is full, that's when it's fragmented.
It's not fragmented, usually not fragmented when the cache is only partially used.
So we always need to do, we need to have some cache eviction algorithm, anyway.
And in one cache, this happens to L-I-U, and also in my implementation, this happens to L-I-U, the L-I-U. You could use other eviction algorithms. I'm always talking about L-I-U on these slides, doesn't mean I wasn't aware that there were alternatives.
So how can we combat or counteract fragmentation issues? Well, we can just have a thread, making room, and at the same time trying to allocate larger pages.
That way, we will remove objects as long as they happen eventually to coalesce into the larger size that we want to see.
Now we can put this large size onto a reserve, and whenever some other thread comes along and needs memory, we can return what we have in the reserve and make the other thread happy to get a nice big chunk of memory.
So last part, I want to show you a bit of the API side. Yes, I'm one of these C guys, and I've heard about memory safety.
So there were a couple of things which I thought, or found out actually during the process that I have for, first of all, some separate data types, then batching, waiting allocations, and also asynchronous allocations, allocation requests, I should say.
Coming back to the Lipsy Mallorque API, which is quite common, you all know that you basically get a single pointer back when you make an allocation. So you say, okay, I want 1540 bytes, and you get back a single pointer and you basically the implicit contract is that this will be enough to store 1540 bytes.
And when you free the chunk of memory and you return it to the allocator, the allocator now must somehow know that those were 1540 bytes, or at least, I mean whatever it does, it needs to internally make it so that it makes the right amount of memory available again.
It could be a slab allocator, yada, yada, okay. But here, in this allocator, we actually need to know the original size, if it was a power of 2, we need to know which bit field, we need to clear a bit and excuse me, set a bit.
If it was a different size, which is not a power of 2, we also need to know the exact size because we need to, we then have all these little or increasingly big partial allocations that we also need to clear and potentially merge.
So yeah, and then I told you, okay, one of the main motivations was to have an allocator which doesn't work on memory, but works on disk offsets. So now we have four different things.
We have these arbitrary sized allocations, which I call extends, as pointers or as offsets, and also the power of 2 allocations, as pointers and offsets.
The reason that the letter to exist is just that they are internally a bit more efficient, so I thought, okay, better expose the efficiency.
And yeah, then for each of these four, we have an allocation function and a return function, which ultimately all net onto the same code, but but anyway.
One other thing which I believe is relevant for performance is that entering the allocator is expensive and especially in slash fellow, the disk storage.
Sometimes there is like thousands of segments that need to be returned or allocated at the same time. So why would we want to enter the allocator for one thing and then return and enter it again return.
Also, for mergers to happen, it's really advantageous if we have all the returns at once. Before we make any new allocations, because this way has this chance that returns coalesce.
Before we hand out, before we potentially split something which could more usefully be used as a as a larger page.
So this interface uses a structure on the stack, which is basically a this body Rex stack is basically a.
It's a macro basically creating a compound literal and that then is the argument to a excuse me, then we fill this compound literal with that helper functions make the actual allocation.
And then we get multiple things back get end things back and for all of these end things we can then you take them out of the compound literal structure and and use them individually.
Same idea for returns this was for requests.
So, what do we do as a web cache? If we if we can't get the memory immediately, yeah, we run LIU and I've already talked about this.
So there are two ends to this with this problem one and is is requests which need memory and the other end is LIU which makes room.
And I actually pondered quite a bit how to tackle this best. So is it really a good idea to do this above the memory allocator in the code calling it or should it be something the allocator itself supports.
And I came to the conclusion that really the best way is that the allocator itself supports it.
Which is why we have waiting requests with prior task use. So there's a fixed set of priorities.
There's each priority is basically a take you.
And as long as there's waiting requests, everyone gets onto the onto the queues.
And then something somewhere will make room.
And when it's done making room, it will check, okay, are there any waiting allocations will try to run them.
So that way those should eventually return.
Now this opened an interesting opportunity. I think which is because which is that we do not need to synchronously wait for allocations.
At some point make a request. Oh, I know in this quite soon I'm going to need some memory, but I have stuff to do in the meantime.
So submit the allocation request. Go away do something or I mean react, probably, possibly react to it immediately if it comes back, but if it doesn't.
Go away do something else. And then.
Yeah, you can still judge your mind and synchronously wait or your lucky in comes back and you work with it.
At the moment, this uses the code that that's out there. It uses condition variables.
So it's really based on this model that you either reject asynchronously or that you synchronously wait, but that's not enough for another project.
I need some kind of callback, which is more like in the A8 design pattern.
More following this A8 design pattern.
So regarding performance, I mentioned this initially, so at the end I also wanted to talk about it at least briefly.
The actual project delivers the performance that you expect from it, which is just the bare metal performance. So what if you have 400 gigabit nix, you want to saturate them.
There's also TLS, which is unrelated to this, but the LOK that should not be the bottleneck.
Excuse me, the storage engine should not be the bottleneck and as far as I know it is not.
And then taking one level down, in my own work on this, I've never seen the LOK to be the bottleneck, but I must say, I had this one purpose, I had this one application for it.
So I never, never actually benchmark the whole thing like you would benchmark the email or whatever.
What I can say is that it can easily scale, because you can easily have multiple of these buddies and we actually do.
So why am I here today? And now what?
Yeah, first of all, I wanted to share these ideas in case they might help anyone.
I'm always very fond of seeing people just doing the project's pick and small starting from scratch.
And I just think that the body allocator is an idea, which is so simple that you could basically do it over a weekend.
But I have a big question.
I can hardly believe that no one else before me came up with this bitfield idea.
So if anyone is out there who's done it before, please get in touch.
And let me know, I haven't found you so far if you exist.
But please let me know if you do, at least, so I can give you credit for having the idea, having had the idea before me.
And then, yeah, OK, obviously this is for them.
So another question I have is, is this of general interest, my own case that I wrote this for is I guess special.
A web cache is definitely not the same as a desktop application from the perspective of a memory allocator.
And a normal desktop application cannot just allow you stuff.
So yeah, I know, but still, I have this question.
If if this should for for now and ever remain part of this less project or if if anyone saw any potential in in taking it elsewhere.
Yeah, and that's it. Thank you.
We have some minutes for question and maybe answers.
Anyone here, please wave a bit.
What?
Yeah, sorry.
So I was wondering if you took the bits you needed for the least reason to use policy into account in memory overhead as well.
And if you do something smart like pseudo LRU or if you do some more fully least reason to use policy.
There's a bit of a question I didn't understand something that the bits and LRU.
So you can make a true least recently used where you keep track of which is the actual least recently used thing, but also for least recently used you can actually do your whole body system idea of making it.
The hierarchy of radic steel trees of saying which of the two was the least recently used.
Ah, okay.
And that's called pseudo you.
Yeah, so I wanted this.
I mean, if I understand you correctly, your question is about if we can't kind of track where things are such that we can merge better, right?
Yeah, that just takes a lot of memory if you want to do that.
And that comes back to this, okay, we only use these two bits at the moment for one page, which is great if if you manage a petabyte.
And as soon as we even start to think about having a single pointer eight bytes is already eight times six, I can't I can't think at the moment.
So already way way way out of all of budget.
And regarding the LRU strictness, we do multiple compromises first of all.
We we have a cut of time for one implementation, which doesn't always reinsert.
It just rates a bit until sometimes passed.
And the other compromises, just multiple LRUs, which are also a big big compromise because then the least recently is the least recently on that particular list.
But not globally.
So, but that has to form it because then you have other metrics and stuff that you have multiple of them.
Okay.
And any other question?
Yes, hi, thank you for the talk. So, I don't know if I understand something correctly.
And it's like you can not prevent fermentation for the searching.
But I think I understood that through a preferred eviction size, you do have a effort to find that kind of size the next time that you search.
I know what I said about fermentation is that we can, because in a cash, we can evict stuff.
And we can evict stuff until we have a nice big page.
So, that's the whole idea I was talking about. Does that make sense?
So, you don't have a target for that, like a preferred target for that big space. You just try the maximum.
You just try to evict as much as possible every time.
So, as long as you have free pages, you make this match.
And you can have this grant parameter to say, okay, I'm also okay with a smaller allocation.
But eventually, you will need bigger allocations, right, for some things.
And the point is, they do two things. First of all, we do them in advance.
So, before the fact, before you need to wait for them, we already have them.
That's one thing. And the other thing is, we don't just allow you for some size.
We allow you for a reasonably large size such that we basically express objects until they happen to coalesce into this larger size.
So, and again, that's something you can do on a cash, which you cannot do in, like in Firefox, you cannot just close tabs until you're happy with the fragmentation, right?
Okay, thank you.
Thank you.
But, please.
Camera.
The camera.
Thanks. When I hear LAU, I think ring buffers, essentially, especially for a logging purpose.
Can I basically, but low overhead, abuse this to just allocate a page to put my log message in?
And then let LAU take care of keeping this as a ring buffer.
And somehow, still be able to recover the order of things that I inserted into.
Yeah, I guess.
I mean, it's something you do on top of the LOKTA.
So, what this body implementation gives you is just this whole concept of one side, making room and the other side,
doing allocations with the weights, which connect the two.
The LAU, yeah, okay, I was talking about the LAU again, and again, maybe that was not the best idea in the context of the body LOKTA.
The body LOKTA itself, because it has nothing to do with it, right?
It's something in my implementation which uses it, but it's not like you had to have an LAU to use the body LOKTA, and not even this implementation.
So, yeah, you would probably have some list of your stuff that you know the tail off and the head off and in one end, you insert the other end, you would just take the stuff out and and free it.
And yeah, that's essentially what's happening here.
Just in your case, it would not be like HTTP body segments, but your log stuff or whatever.
Yeah.
Thanks.
Okay, I think I must say this is the last question to get in time here again.
Thank you for your talk.
Thank you for attending, for us them.
Yeah, maybe a warmer applause.
Always we're here.
And, and a big thank you for my side to you as a volunteer and all the other volunteers and everyone making for the possible.
It's absolutely amazing.
Thank you so much for your great work and keep it up.