mihirluthra/shm_alloc

fast lock free shared memory allocator

shm_alloc

Shared memory allocation for cache data

• What is it?
• When to use?
• Tested on
• Important Notes For Optimisation
• Use case
• Quick and short example
• How to use?
• Manpage
• Source code explanation

What is it?

A shared memory allocation library that mainly provides shm_malloc(), shm_calloc() and shm_free().

1. They are to be used just like malloc(2), calloc(2) and free(2) except that they allocate space in shared memory and return offset from the start of shared memory instead.
2. The shared memory is just a regular file which is mmap(2)'d into the processes' address space. This is done in shm_init().
3. The shared memory is divided into small blocks and allocation of each block is managed by a buddy system in form of a bitmap. Bitmaps for every block lie in the initial region of file and corresponding to them are the allocatable regions just after the bitmaps region ends.

When to use?

1. It uses C11's atomic library. It has been ensured that this branch works with (_POSIX_C_SOURCE >= 200809L). It uses gcc/clang extensions if available. The Makefile used to build the code in NOT posix compatible. The user will will have to rely on their own build system if needed. The current Makefile has only been tested on macOS Catalina and ubuntu 18.04. As far as I remember, current Makefile failed on FreeBSD.
2. If you are ok with allocating memory in a certain range. e.g., our use case would let us allocate memory in range 32 bytes - 1024 bytes (which is default). Main point here is how big can the range be? Max and min sizes need to be power of 2 and difference of these powers should be <= 5 if 64 bit compiler and <= 4 if 32 bit compiler.
   32 = 2⁵ and 1024 = 2¹⁰. The requirement is satisified as 10 - 5 = 5. It could have been 2¹⁵ to 2²⁰. (See changing defaults section).
   
3. The memory allocated on request of n bytes will be next closest power of 2 after n within range. e.g., If 158 bytes are requested, 256 bytes are allocated.
   If 9 bytes are requested, 32 bytes are allocated (not 16 because range is 32 to 1024).
   If more than 1024 bytes are requested, SHM_NULL is returned.

Tested on

1. macOS Catalina
2. Ubuntu 18.04(with and without -m32)

Important Notes For Optimisation

1. It is a good idea to have shared memory file in file system made by tmpfs. There are many alternatives for macOS which you can find by googling.
2. malloc(2) has the privilege of using huge pages which makes it faster because of TLB. But in case of shm_malloc() that uses mmap(2) with MAP_SHARED doesn't have huge page support.
   The starting point of shared memory is page aligned. Afterwards, there are blocks whose size can be altered by you(see changing defaults section). By default max size is 1024 bytes. So if page size is 4096, 4 blocks of memory constitute a single page.

Use case

1. It is meant to be used alongside a ctrie data structure into which multiple processes may insert path names. Memory requests are generally not more than 1024(as they are paths) in our case and even if they are, it's ok to ignore such requests as its just for caching.
2. This library needs to be injected into anonymous processes where it would intercept various system calls & library functions and perform operations with shared memory. So using locks is not a good idea as the process may get interrupted by a signal or maybe even called inside a signal handler or any such similar situation may cause a deadlock. As it may even be called inside a signal handler, its essential to use asyc-signal-safe functions. That's one more reason why shared memory initialisation that requires mmap(2) is done with __attribute__((constructor)) in our use case (as it is not considered asyc safe at the present time).

Quick and short example

Find examples in example directory.

How to use?

Find the instructions to use the library in how_to_use.md

Manpage

Find the documentation of all library functions in man.md

Source code explanation

Find the source code explanation in source_code_explanation.md.