source_code_explanation.md

Abstract

The basic working of code goes as follows:

1. File at path given by env variable SHM_FILE or as an argument is mmap(2)'d into process' address space. If the file doesn't exist it is created. As the file is given its size by ftruncate(2), it is initialised with all 0.
2. When shm_malloc() is asked for memory, it is rounded up to the next power of 2. Then management blocks are checked for free bits as per the requirement. The bits are set and offset corresponding to them in the allocatable region is returned.
3. To access the allocated shared memory, user needs to get the base of allocatable region by get_shm_user_base(). Then offset needs to be added to the base, while typecasting base to uint8_t *.
4. To free the memory, shm_free() is called and it unsets the bits corresponding to the offset supplied.

Explanation

If shm_init() is called in multiple threads, all call mmap(2) and set the mapping values in a temporary struct shm_manager type. In the end they try atomic CAS on a global struct shm_manager type.

struct shm_manager {
    struct mmap_data shm_mapping;
    struct file_data shm_file;
};

To start with, consider a file. The file's size is obtained by a SHM_MAPPING_SIZE defined in shm_constants.h. The file contains 4 regions just as shown in the image above.

• Shm Allocatable Region
• Shm Management Region
• Shm Null
• Shm Data Table

Shm Allocatable Region

In the file, the area that is for actual data storage is called the shm allocatable region. Its size is defined by the macro MAX_ALLOCATABLE_SHM_SIZE. By default it is 512 MB. This region is thought as a collection of blocks of size MAX_ALLOCATABLE_SIZE. By default it is 1024 bytes. So there are 262144 blocks in the allocatable region by default.

Shm Management Region

For every block in allocatable region, there exists a management block in shm management region. These management blocks contain a bitmap and a variable that counts the memory used in that block. The management block is a variable of type struct shm_block_mgmt which is defined as follows:

struct shm_block_mgmt {
    _Atomic(shm_bitmap) mgmt_bmp;
    _Atomic(size_t)     mem_used;
};

• mgmt_bmp

  1. Bits in mgmt_bmp manage memory allocation in the corresponding block in allocatable region. The bitmap looks like:

     0000000000000000000000000000000000000000000000000000000000000000
     

     Well but you need not look it like that. Think of it like:

     0 --> unused bit
     0 --> 1024 
     00 --> 512 
     0000 --> 256 
     00000000 --> 128 
     0000000000000000 --> 64 
     00000000000000000000000000000000 --> 32 
     

  2. This bitmap is used as the buddy system.
  3. Here mgmt_bmp has 64 bits although only 63 bits are needed. Number of bits being used are defined in BITS. shm_bitmap is set to unsigned long if ATOMIC_LONG_LOCK_FREE is 2 i.e. always lock free. Otherwise it checks the same for unsigned int. If unsigned int is also not always lock free, the program terminates.
  4. To allocate memory in the block, the corresponding bit along with all its children need to be set.
     As its just a single 64 bits bitmap, its pretty simple to do bit setting. First of all, create a mask for the bit range for that particular memory level. e.g., For memory level 128, mask would look like:

     0 --> 1024 
     00 --> 512 
     0000 --> 256 
     11111111 --> 128 
     0000000000000000 --> 64 
     00000000000000000000000000000000 --> 32
     

     In this mask, we unset the bits that are already set in mgmt_bmp and then we find the posn of first set bit in the mask. Let's say first set bit is 8, then we make another mask called the set mask, that has bit no. 8 and all its children set like:

     0 --> 1024 
     00 --> 512 
     0000 --> 256 
     10000000 --> 128 
     1100000000000000 --> 64 
     11110000000000000000000000000000 --> 32
     

     Above is the set mask. We ensure none of these bits are set in mgmt_bmp and then we set all these bits via atomic CAS.
  5. To free the memory, the set mask is obtained for that particular bit. Then we unset all the set mask bits in mgmt_bmp via atomic CAS.

• mem_used

  mem_used holds the amount of memory used in block. This variable is only for optimising the code. If the memory needed + mem_used > max allocatable size, then we skip this block.

Shm Null

This is a part of shm allocatable region and is located in the start of it i.e. offset is 0. It's a single page mapped with PROT_READ. When mapping the file into the process, this region is made readonly. Management blocks for shm null exists as well, as it is a part of allocatable region. They are changed to mark shm null blocks as allocated while initialising shared memory.

Shm Data Table

This is placed at the very starting of mapping(which doesn't really make a difference). Its purpose is to make memory search faster. It is accessed by a variable of type struct shm_data_table which is defined as follows:

struct shm_data_table {
    _Atomic(shm_offt) start_blk_mgr_offt;
};

• start_blk_mgr_offt

  For a fresh shared memory i.e. all memory is unused, It stores offset to the first management block that is not full. Just think for once that no memory is being freed and blocks keep getting filled one by one. To allocate memory when n blocks are full, it would take n iterations to reach n+1^th. So to avoid that, whenever a block gets full, this stores the offset to the next block. When next request for memory comes, search starts from the management block at offset start_blk_mgr_offt. Although, as memory keeps getting allocated, start_blk_mgr_offt eventually points to the last management block which is full as well. So if memory is not found in the scan from start_blk_mgr_offt to the end, second scan is from start of the management area upto start_blk_mgr_offt to search for memory, if any was freed by shm_free().
  To optimize the second scan, we need to implement a freelist as well(#TODO).