nginx_shared_memory_slab

Overview

In previous post shared memory tracking, it shows how shared memory is tracked and allocated, but it does not show how to manage allocated shared memory, then provide API for user to use memory from it, say you have a big shared memory, later on you may want to allocate blocks from the shared memory, how does nginx manage the shared memory and allocate block to user quickly? this is the post aims to tell you.

Slab

Actually nginx uses slab to manage the shared memory, same as kernel does for its slab. it provides several size of slabs like 8, 16, 2^x, that means you can only get 2^x bytes from the shared memory, for each slab, there is a slab header, each entry in the slab list is the slab page control part which has the metadata for that page(like which block is used etc), when user requests size bytes, round(size) to 2^x, then check the proper slab, find a free page in that slab, allocate block from that page, mark that block as used.

Data structure and API

Data Structure

/* slab page control part OR slab header which no real slab page related*/
struct ngx_slab_page_s {
    uintptr_t         slab;
    ngx_slab_page_t  *next;
    uintptr_t         prev;
};

typedef struct {
    ngx_uint_t        total; /* all available chunks(used and unused) except bitmap used if has */
    ngx_uint_t        used;  /* used chunks count, NOT count bitmap used */

    ngx_uint_t        reqs;
    ngx_uint_t        fails;
} ngx_slab_stat_t;

typedef struct {
    size_t            min_size; /* 8 bytes */
    size_t            min_shift; /* 3, 2^3 = 8 */

    /* as for each slab(2^x), first we need a page
     * below fields are used for manges shared memory as pages.
     * inside that page, use bitmap to track small block (2^x size)
     */
    ngx_slab_page_t  *pages; /* page control, each page has one ngx_slab_page_t */
    ngx_slab_page_t  *last;  /* last control page structure */
    ngx_slab_page_t   free;  /* header of free page structure */

    ngx_slab_stat_t  *stats; /* stats for each slot */
    ngx_uint_t        pfree; /* free pages */

    u_char           *start; /* page data area(aligned) */
    u_char           *end;   /* original addr + size */

    void             *data; /* context of shared memory */
    void             *addr; /* original shared memory addr */
} ngx_slab_pool_t;

API

static ngx_int_t ngx_init_zone_pool(ngx_cycle_t *cycle, ngx_shm_zone_t *zn);
void ngx_slab_init(ngx_slab_pool_t *pool);
void * ngx_slab_calloc(ngx_slab_pool_t *pool, size_t size);
void * ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size);

Slab layout

As you can see slab management sits at the beginning of the shared memory, like slab pool, slab header, stats header, ngx_slab_page_t(for each page), that means the available memory for user is less than the size passed to mmap().

Page movement during free and allocate

At first, all pages are linked to free list, but after allocation and free, the control part ngx_slab_page_t may be at different slots.

Bitmap for block(inside one page) management

Bitmap is used to track the block status(used or not) in a page, each bit in the map represents a block in the page, it also needs memory for the bitmap, as different blocks need different bitmap size, nginx saves bitmap in two different places, if block size >=64 bytes, bitmap saves at ngx_slab_page_t->slab, otherwise, bitmap saves at page in place(beginning of the page).

How to get the chunk index from chunk address
page offset are least 12 bits for each bytes in the page, then we group bytes as chunk, the chunk shift are offset inside each chunk, the least chunk_shift bit is offset inside each chunk, the high bit is same for a chunk（which takes 2^chunk_offset bytes).

high---------bit 0  1  0  0  0  0 0 0 0 0 0  1
|--page index----|<---page offset----------->|
                 |chunk index  | chunk offset|

nginx first needs to know which page the block belongs, then the page control part, knows the chunk offset, then gets chunk index(set bitmap or clear it when free the block).