Ayende @ Rahien

Oren Eini aka Ayende Rahien CEO of Hibernating Rhinos LTD, which develops RavenDB, a NoSQL Open Source Document Database.

You can reach me by:

oren@ravendb.net

+972 52-548-6969

Posts: 6,916 | Comments: 49,398

filter by tags archive
time to read 4 min | 753 words

In my last post, I looked into the infrastructure of mimalloc, to be frank. A few details on how it is actually hooking the system allocator when used, mostly. I’m still using what is effectively a random scatter/gather approach to the codebase. Mostly because it is small. I’m trying to… grok it would be the best term, I guess. I’m going over the code because it also give me a good idea about practices in what seems to be a damn good C codebase.

I should mention that I drove right into the code, there is also the tech report, which I intend to read, but only after I got through enough of the code to get a good feeling for it.

I run into the code in the options.c file, for instance:

image

This is a really nice way to get configuration values from the user. What I find really interesting, to be frank, is not the actual options, which would be interesting later on, but the fact that this is such a nice way to represent things in a readable manner.

I’m doing similar things in C# (a much higher level language) to create readable options (typically using dictionary & dictionary initializer). I like how the code is able to express things so succinctly in a language with far fewer features.

However, the order of parameters is critical (is should match the mi_option_t enum values), and there is no way to express this in the code.

I also liked this code, which is part of reading configuration values from env variables:

image

I like that this is using strstr() in reverse in this manner. It is really elegant.

Going over the OS abstraction layer, on the other hand, show some granliness, take a look here:

image

I actually simplified the code abit, because it also had #if there for BSD, Linux, etc. I find it harder to follow this style, maybe adding indentation would help, but I have had to read this function multiple times, filtering for specific OSes to get it right.

I did find this tidbit, which is interesting:

image

This is attempting to do allocation with exclusive access. I wonder how this is actually used for. It looks like mimalloc is attempting to allocate in specific addresses, so that should be interesting.

Indeed, in _mi_os_reset() they will explicitly ask the OS to throw the memory away by calling MADV_FREE or MEM_RESET. I find this interesting, because this let the OS know that the memory can be thrown away, but the allocation still persists. I’m currently looking into some fragmentation issues in 32bits, which won’t be helped by this scenario. Then again, I don’t think that mimalloc is primarily intended for 32 bits systems (I can see code handling 32 bits, but I don’t think this is the primary use case or that 32 bits had a lot of attention).

The mi_os_alloc_aligned_ensured() method call is doing some interesting things. If I need a 16MB buffer, but aligned on 1MB boundary, I have no real way to ask this from the OS. So this is implemented directly by over-allocating. To be fair, I can’t think of a good reason why you’ll want to do something like that (you have no guarantees about what the actual physical memory layout would be after all, and that is the only scenario I can think this would be useful. Given that page aligned memory (which is what you get anyway from the OS) is usually sufficient, I wonder what is the use case for that here.

I get why mimalloc have to struggle with this, given that it is limited to just returning a pointer back (malloc interface), and doesn’t have a good way to tell that it played games with the alignment when you pass a value to free(). There seems to be a lot of code around here to deal with memory alignment requirements.  I think that I’ll need to go up the stack to figure out what kind of alignment requirements it has.

That is enough for now, I think. I’m going to get to the core of mimalloc in the next post.

time to read 4 min | 673 words

mimalloc is a memory allocator that is small and efficient, at least so the docs say. Which was interesting enough for me to take a look. We have had to do a lot of work in memory allocation inside RavenDB, and looking into how other people are doing that is always interesting. What was really attractive for me here was the fact that this is a small codebase, so I can go over that fairly quickly, and the amount of complexity involved is going to be limited.

As usual, I’m just going over the code, recording my impressions.

I started by looking at the API in mimalloc.h, and while it seems threatening, pretty much all of details here are around making it clear to the compiler what this code is doing, to enable additional optimizations.

image

If you ignore all of these, this is just a pretty normal function declaration with the usual malloc signature.

The code is very well commented, but it looks like it is going to take a serious inspection to actually figure out what is going on. I started by going over the header files, and they show some tantalizing details, but I’m missing context that I assume that I’ll get when I’ll go over the actual code.

The code talks about segments and blocks. I think that a segment is a chunk of memory that we allocated from the OS, and a block is a chunk of memory that we allocate to users of mimalloc. I like that there is an explicit model here of multi threading. There is a heap per thread, it seems, but you can free memory from another thread as well. This match very closely what we have done with RavenDB’s internal memory management.

I started to read the OS specific parts of the code, and I hit gold (as in, stuff that is really interesting to read) almost immediately:

image

There is a long discussion that details a lot of really fascinating details here, including certain level of “are you really going to go there?! OMG, you went there!”. For example, in order to patch malloc(), mimalloc need to patch atexit() to ensure that the process can shutdown normally.

I started reading the init.c file, and it isn’t about memory management at all, it is all about integrating mimalloc into the system, and that is quite fascinating on its own.

Here is how the memory is patched on ARM (similar code exists for X86 and X64):

image

What you see here is building of raw assembly instructions to do a task. I do wonder how this works, given that I would expect usual executable memory to be non writable, but I’ll look at that in a bit.

Then we have the actual list of functions to patch:

image

The last lines are scary, I have to admit.

And I found how the code deals with the memory protection:

image

I’m currently doing what is effectively random reads throughout the codebase, mostly because this is close to midnight and I’m not going to really be able to grok anything. I run into this function:

image

Nothing “special”, but it did lead me to some interesting articles about hashing, and what they are good for, how to build them, etc.

One of the reasons that I love doing these code reviews is that I learn so much more than what I expected to.

For example, the way mimalloc initialize its random is really quite interesting (see: _mi_random_init()) and elegant.

FUTURE POSTS

  1. Researching a disk based hash table - 3 hours from now

There are posts all the way to Nov 14, 2019

RECENT SERIES

  1. re (24):
    12 Nov 2019 - Document-Level Optimistic Concurrency in MongoDB
  2. Voron’s Roaring Set (2):
    11 Nov 2019 - Part II–Implementation
  3. Searching through text (3):
    17 Oct 2019 - Part III, Managing posting lists
  4. Design exercise (6):
    01 Aug 2019 - Complex data aggregation with RavenDB
  5. Reviewing mimalloc (2):
    22 Jul 2019 - Part II
View all series

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats