当前位置: > Linux服务器 > nginx >

nginx中slab实现

时间:2016-06-06 12:08来源:linux.it.net.cn 作者:IT

slab的一些结构体:

typedef struct {  
    ngx_atomic_t      lock; // 锁,因为slab在nginx中一般配合共享内存使用  
  
    size_t            min_size; // 分配空间的最小值  
    size_t            min_shift;    // 该最小值对应的移位数  
  
    ngx_slab_page_t  *pages; // 页数组  
    ngx_slab_page_t   free; // 空闲的页  
  
    u_char           *start;    // 分配地址开始地址  
    u_char           *end;    
  
    ngx_shmtx_t       mutex;  
  
    u_char           *log_ctx;  
    u_char            zero;  
  
    void             *data;  
    void             *addr;  
} ngx_slab_pool_t;  
  
// 页结构体  
struct ngx_slab_page_s {  
    uintptr_t         slab;     // 保存当前页的一些信息  
    ngx_slab_page_t  *next;// 下一个  
    uintptr_t         prev;// 上一个  
};  

slab的函数调用:

// 初始化slab池  
void ngx_slab_init(ngx_slab_pool_t *pool);  
// 未加锁的  
void *ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size);  
// 在调用前已加锁,分配指定大小空间  
void *ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size);  
void ngx_slab_free(ngx_slab_pool_t *pool, void *p);  
// 释放空间  
void ngx_slab_free_locked(ngx_slab_pool_t *pool, void *p);  

关于slab的使用,我们在介绍nginx中共享内存的时候再去介绍吧,我们只需要知道在进程初始化时,ngx_init_cycle函数会调用ngx_init_zone_pool来初始化共享内存,然后在ngx_init_zone_pool函数中会调用ngx_slab_init来初始化slab内存池。随后,在进程中,我们就可以调用alloc与free来对共享内存进行操作了。

对于64位与32位系统,nginx里面默认的值是不一样的,我们看到数字可能会更好理解一点,所以我们就以32位来看,用实际的数字来说话!

 

// 页大小
ngx_pagesize: 4096
// 页大小对应的移位数
ngx_pagesize_shift: 12
// slab的一次最大分配空间,默认为pagesize/2
ngx_slab_max_size: 2048
// slab精确分配大小,这个是一个分界点,通常是4096/32,为什么会这样,我们后面会有介绍
ngx_slab_exact_size: 128
// slab精确分配大小对应的移位数
ngx_slab_exact_shift: 7

ngx_slab_exact_size这个时依赖slab的分配算法.它的值是这样来的.4096/32,2048是slab页大小,而32是一个int的位数,最后的值是128。
why? 我们在分配时,在一页中,我们可以将这一页分成多个块,而某个块需要标记是否被分配,而一页空间正好被分成32个128字节大小的块,于是我们可以用一个int的32位表示这块的使用情况,而此时,我们是使用ngx_slab_page_s结构体中的slab成员来表示块的使用情况的。另外,在分配大于128与小于128时,表示块的占用情况有所有同
// 初始化  
void  
ngx_slab_init(ngx_slab_pool_t *pool)  
{  
    u_char           *p;  
    size_t            size;  
    ngx_int_t         m;  
    ngx_uint_t        i, n, pages;  
    ngx_slab_page_t  *slots;  
  
    /* STUB */  
    if (ngx_slab_max_size == 0) {  
        // 最大分配空间为页大小的一半  
        ngx_slab_max_size = ngx_pagesize / 2;  
        // 精确分配大小,8为一个字节的位数,sizeof(uintptr_t)为一个uintptr_t的字节,我们后面会根据这个size来判断使用不同的分配算法  
        ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));  
        // 计算出此精确分配的移位数  
        for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {  
            /* void */  
        }  
    }  
    /**/  
  
    pool->min_size = 1 << pool->min_shift;  
  
    // p 指向slot数组  
    p = (u_char *) pool + sizeof(ngx_slab_pool_t);  
    size = pool->end - p;  
  
    // 将开始的size个字节设置为0  
    ngx_slab_junk(p, size);  
  
    // 某一个大小范围内的页,放到一起,具有相同的移位数  
    slots = (ngx_slab_page_t *) p;  
    // 最大移位数,减去最小移位数,得到需要的slot数量  
    // 默认为8  
    n = ngx_pagesize_shift - pool->min_shift;  
  
    // 初始化各个slot  
    for (i = 0; i < n; i++) {  
        slots[i].slab = 0;  
        slots[i].next = &slots[i];  
        slots[i].prev = 0;  
    }  
  
    // 指向页数组  
    p += n * sizeof(ngx_slab_page_t);  
  
    // 计算出当前内存空间可以放下多少个页,此时的计算没有进行对齐,在后面会进行调整  
    pages = (ngx_uint_t) (size / (ngx_pagesize + sizeof(ngx_slab_page_t)));  
  
    ngx_memzero(p, pages * sizeof(ngx_slab_page_t));  
  
    pool->pages = (ngx_slab_page_t *) p;  
  
    pool->free.prev = 0;  
    pool->free.next = (ngx_slab_page_t *) p;  
  
    pool->pages->slab = pages;  
    pool->pages->next = &pool->free;  
    pool->pages->prev = (uintptr_t) &pool->free;  
  
    // 计算出对齐后的返回内存的地址  
    pool->start = (u_char *)  
                  ngx_align_ptr((uintptr_t) p + pages * sizeof(ngx_slab_page_t),  
                                 ngx_pagesize);  
  
    // 用于判断我们对齐后的空间,是否需要进行调整  
    m = pages - (pool->end - pool->start) / ngx_pagesize;  
    // 说明之前是没有对齐过的,由于对齐之后,最后那一页,有可能不够一页,所以要去掉那一块  
    if (m > 0) {  
        pages -= m;  
        pool->pages->slab = pages;  
    }  
  
    pool->log_ctx = &pool->zero;  
    pool->zero = '\0';
}  
void *  
ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size)  
{  
    size_t            s;  
    uintptr_t         p, n, m, mask, *bitmap;  
    ngx_uint_t        i, slot, shift, map;  
    ngx_slab_page_t  *page, *prev, *slots;  
  
    // 如果超出slab最大可分配大小,即大于2048,则我们需要计算出需要的page数,  
    // 然后从空闲页中分配出连续的几个可用页  
    if (size >= ngx_slab_max_size) {  
  
        // 计算需要的页数,然后分配指针页数  
        page = ngx_slab_alloc_pages(pool, (size + ngx_pagesize - 1)  
                                          >> ngx_pagesize_shift);  
        if (page) {  
            // 由返回page在页数组中的偏移量,计算出实际数组地址的偏移量  
            p = (page - pool->pages) << ngx_pagesize_shift;  
            // 计算出实际的数据地址  
            p += (uintptr_t) pool->start;  
  
        } else {  
            p = 0;  
        }  
  
        goto done;  
    }  
  
    // 如果小于2048,则启用slab分配算法进行分配  
  
    // 计算出此size的移位数以及此size对应的slot以及移位数  
    if (size > pool->min_size) {  
        shift = 1;  
        // 计算移位数  
        for (s = size - 1; s >>= 1; shift++) { /* void */ }  
        // 由移位数得到slot  
        slot = shift - pool->min_shift;  
  
    } else {  
        // 小于最小可分配大小的都放到一个slot里面  
        size = pool->min_size;  
        shift = pool->min_shift;  
        // 因为小于最小分配的,所以就放在第一个slot里面  
        slot = 0;  
    }  
  
    slots = (ngx_slab_page_t *) ((u_char *) pool + sizeof(ngx_slab_pool_t));  
    // 得到当前slot所占用的页  
    page = slots[slot].next;  
  
    // 找到一个可用空间  
    if (page->next != page) {  
  
        // 分配大小小于128字节时的算法,看不懂的童鞋可以先看等于128字节的情况  
        // 当分配空间小于128字节时,我们不可能用一个int来表示这些块的占用情况  
        // 此时,我们就需要几个int了,即一个bitmap数组  
        // 我们此时没有使用page->slab,而是使用页数据空间的开始几个int空间来表示了  
        // 看代码  
  
        if (shift < ngx_slab_exact_shift) {  
  
            do {  
                // 得到页数据部分  
                p = (page - pool->pages) << ngx_pagesize_shift;  
                // 页的开始几个int大小的空间来存放位图数据  
                bitmap = (uintptr_t *) (pool->start + p);  
  
                // 当前页,在当前size下可分成map*32个块  
                // 我们需要map个int来表示这些块空间  
                map = (1 << (ngx_pagesize_shift - shift))  
                          / (sizeof(uintptr_t) * 8);  
  
                for (n = 0; n < map; n++) {  
  
                    if (bitmap[n] != NGX_SLAB_BUSY) {  
  
                        for (m = 1, i = 0; m; m <<= 1, i++) {  
                            if ((bitmap[n] & m)) {  
                                // 当前位表示的块已被使用了  
                                continue;  
                            }  
  
                            // 设置已占用  
                            bitmap[n] |= m;  
  
                            i = ((n * sizeof(uintptr_t) * 8 ) << shift)  
                                + (i << shift);  
  
                            // 如果当前bitmap所表示的空间已都被占用,就查找下一个bitmap  
                            if (bitmap[n] == NGX_SLAB_BUSY) {  
                                for (n = n + 1; n < map; n++) {  
                                    // 找到下一个还剩下空间的bitmap  
                                     if (bitmap[n] != NGX_SLAB_BUSY) {  
                                         p = (uintptr_t) bitmap + i;  
  
                                         goto done;  
                                     }  
                                }  
  
                                // 剩下所有的bitmap都被占用了,表明当前的页已完全被使用了,把当前页从链表中删除  
                                prev = (ngx_slab_page_t *)  
                                            (page->prev & ~NGX_SLAB_PAGE_MASK);  
                                prev->next = page->next;  
                                page->next->prev = page->prev;  
  
                                page->next = NULL;  
                                // 小内存分配  
                                page->prev = NGX_SLAB_SMALL;  
                            }  
  
                            p = (uintptr_t) bitmap + i;  
  
                            goto done;  
                        }  
                    }  
                }  
  
                page = page->next;  
  
            } while (page);  
  
        } else if (shift == ngx_slab_exact_shift) {  
            // 如果分配大小正好是128字节,则一页可以分成32个块,我们可以用一个int来表示这些个块的使用情况  
            // 这里我们使用page->slab来表示这些块的使用情况,当所有块被占用后,该值就变成了0xffffffff,即NGX_SLAB_BUSY  
            // 表示该块都被占用了  
  
            do {  
                // 当前页可用  
                if (page->slab != NGX_SLAB_BUSY) {  
  
                    for (m = 1, i = 0; m; m <<= 1, i++) {  
                        // 如果当前位被使用了,就继续查找下一块  
                        if ((page->slab & m)) {  
                            continue;  
                        }  
  
                        // 设置当前为已被使用  
                        page->slab |= m;  
  
                        // 最后一块也被使用了,就表示此页已使用完  
                        if (page->slab == NGX_SLAB_BUSY) {  
                            // 将当前页从链表中移除  
                            prev = (ngx_slab_page_t *)  
                                            (page->prev & ~NGX_SLAB_PAGE_MASK);  
                            prev->next = page->next;  
                            page->next->prev = page->prev;  
  
                            page->next = NULL;  
                            // 标识使用类型,精确  
                            page->prev = NGX_SLAB_EXACT;  
                        }  
  
                        p = (page - pool->pages) << ngx_pagesize_shift;  
                        p += i << shift;  
                        p += (uintptr_t) pool->start;  
  
                        goto done;  
                    }  
                }  
  
                // 查找下一页  
                page = page->next;  
  
            } while (page);  
  
        } else { /* shift > ngx_slab_exact_shift */  
            // 当需要分配的空间大于128时,我们可以用一个int的位来表示这些空间  
            //所以我们依然采用跟等于128时类似的情况,用page->slab来表示  
            // 但由于 大于128的情况比较多,移位数分别为8、9、10、11这些情况  
            // 对于一个页,我们如何来知道这个页的分配大小呢?  
            // 而我们知道,最小我们只需要使用16位即可表示这些空间了,即分配大小为256~512时  
            // 那么我们采用高16位来表示这些空间的占用情况  
            // 而最低位,我们也利用起来,表示此页的分配大小,即保存移位数  
            // 比如我们分配256,当分配第一个空间时,此时的page->slab位图情况是:0x0001008  
            // 那分配下一空间就是0x0003008了,当为0xffff008时,就分配完了  
            // 看代码  
  
            // page->slab & NGX_SLAB_SHIFT_MASK 即得到最低一位的值,其实就是当前页的分配大小的移位数  
            // ngx_pagesize_shift减掉后,就是在一页中标记这些块所需要的移位数,也就是块数对应的移位数  
            n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK);  
            // 得到一个页面所能放下的块数  
            n = 1 << n;  
            // 得到表示这些块数都用完的bitmap,用现在是低16位的  
            n = ((uintptr_t) 1 << n) - 1;  
            // 将低16位转换成高16位,因为我们是用高16位来表示空间地址的占用情况的  
            mask = n << NGX_SLAB_MAP_SHIFT;  
  
            do {  
                // 判断高16位是否全被占用了  
                if ((page->slab & NGX_SLAB_MAP_MASK) != mask) {  
  
                    // NGX_SLAB_MAP_SHIFT 为移位偏移, 得到0x10000  
                    for (m = (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT, i = 0;  
                         m & mask;  
                         m <<= 1, i++)  
                    {  
                        // 当前块是否被占用  
                        if ((page->slab & m)) {  
                            continue;  
                        }  
  
                        // 将当前位设置成1  
                        page->slab |= m;  
  
                        // 当前页是否完全被占用完  
                        if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {  
                            prev = (ngx_slab_page_t *)  
                                            (page->prev & ~NGX_SLAB_PAGE_MASK);  
                            prev->next = page->next;  
                            page->next->prev = page->prev;  
  
                            page->next = NULL;  
                            page->prev = NGX_SLAB_BIG;  
                        }  
  
                        p = (page - pool->pages) << ngx_pagesize_shift;  
                        p += i << shift;  
                        p += (uintptr_t) pool->start;  
  
                        goto done;  
                    }  
                }  
  
                page = page->next;  
  
            } while (page);  
        }  
    }  
  
    // 如果当前slab对应的page中没有空间可分配了,则重新从空闲page中分配一个页  
    page = ngx_slab_alloc_pages(pool, 1);  
  
    if (page) {  
        if (shift < ngx_slab_exact_shift) {  
            // 小于128时  
            p = (page - pool->pages) << ngx_pagesize_shift;  
            bitmap = (uintptr_t *) (pool->start + p);  
  
            // 需要的空间大小  
            s = 1 << shift;  
            n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;  
  
            if (n == 0) {  
                n = 1;  
            }  
  
            bitmap[0] = (2 << n) - 1;  
  
            // 需要使用的  
            map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);  
  
            for (i = 1; i < map; i++) {  
                bitmap[i] = 0;  
            }  
  
            page->slab = shift;  
            page->next = &slots[slot];  
            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;  
  
            slots[slot].next = page;  
  
            p = ((page - pool->pages) << ngx_pagesize_shift) + s * n;  
            p += (uintptr_t) pool->start;  
  
            goto done;  
  
        } else if (shift == ngx_slab_exact_shift) {  
  
            // 第一块空间被占用  
            page->slab = 1;  
            page->next = &slots[slot];  
            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;  
  
            slots[slot].next = page;  
  
            p = (page - pool->pages) << ngx_pagesize_shift;  
            p += (uintptr_t) pool->start;  
  
            goto done;  
  
        } else { /* shift > ngx_slab_exact_shift */  
  
            // 低位表示存放数据的大小  
            page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) | shift;  
            page->next = &slots[slot];  
            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;  
  
            slots[slot].next = page;  
  
            p = (page - pool->pages) << ngx_pagesize_shift;  
            p += (uintptr_t) pool->start;  
  
            goto done;  
        }  
    }  
  
    p = 0;  
  
done:  
  
    return (void *) p;  
}  
/ 分配指针个数的页  
static ngx_slab_page_t *  
ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)  
{  
    ngx_slab_page_t  *page, *p;  
  
    for (page = pool->free.next; page != &pool->free; page = page->next) {  
  
        if (page->slab >= pages) {  
  
            // 当前可以分配  
            if (page->slab > pages) {  
                // 空闲的pages大于需要分配的pages  
  
                // 减少  
                page[pages].slab = page->slab - pages;  
                // 这几个页就分配出去了哦!  
                page[pages].next = page->next;  
                page[pages].prev = page->prev;  
  
                p = (ngx_slab_page_t *) page->prev;  
                p->next = &page[pages];  
                page->next->prev = (uintptr_t) &page[pages];  
  
            } else {  
                // slab == pages  
                // 正好分配完  
  
                // 设置free链表  
                p = (ngx_slab_page_t *) page->prev;  
                p->next = page->next;  
                page->next->prev = page->prev;  
            }  
  
            page->slab = pages | NGX_SLAB_PAGE_START;  
            page->next = NULL;  
            page->prev = NGX_SLAB_PAGE;  
  
            if (--pages == 0) {  
                return page;  
            }  
  
            for (p = page + 1; pages; pages--) {  
                p->slab = NGX_SLAB_PAGE_BUSY;  
                p->next = NULL;  
                p->prev = NGX_SLAB_PAGE;  
                p++;  
            }  
  
            return page;  
        }  
    }  
  
    return NULL;  
}  

 

 




(责任编辑:IT)
------分隔线----------------------------
栏目列表
推荐内容