注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

FY

Johnson 's Blog

 
 
 

日志

 
 

转: nginx中slab分配器的实现  

2011-12-28 15:24:50|  分类: Web 技术 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
链接出处

原创文章,转载请注明: 转载自pagefault

本文链接地址: nginx中slab分配器的实现

nginx的slab分配器主要用于共享内存部分的内存分配,代码包含在core/slab.c和core/slab.h中。slab是针对小于1 页的内存的fenpei 它的大体思想和jeff的那篇paper中描述的一致,因此可以先看看jeff的那篇关于slab的论文。有关于slab的优点也可以去看jeff的 paper,这里就不描述了。

下面就是nginx的slab的内存图.
slab in nginx

下面就是管理slab的核心的数据结构ngx_slab_pool_t,这里我只是简单的注释,紧接着我会详细的介绍实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct {
    ngx_atomic_t      lock;
 
    size_t            min_size;
    size_t            min_shift;
//管理页数组
    ngx_slab_page_t  *pages;
//管理free的页数组
    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;

然后描述下nginx中的slab是怎么实现的,一个slab管理了很多个相似大小的块,而nginx会通过两种方式来管理内存,它是根据所请求的 大小进行划分,小于ngx_slab_max_size的都会通过一个slots数组来进行管理(可以看我上面的内存图),然后每次进来的size都会根 据它的shift来划分到对应的数组的位置,下面就是数组的位置,size以及shift的对应关系,可以看到这里分配的大小都是向上对其的,也就是说你 申请35字节那么会返还给你64字节。

slot size shift
0 <= 8 3
1 9 ~ 16 4
2 17 ~ 32 5
3 33 ~ 64 6
4 65 ~ 128 7
5 129 ~ 256 8
6 257 ~ 512 9
7 513 ~ 1024 10
8 1025 ~ 2047 11

然后就是大于ngx_slab_max_size的情况,如果大于它则会从page数组分配,因为这个值是页大小的一半,大于它则说明我们需要直接 返回一个页或者几个页,此时就不需要象小的块那样需要一个复杂的管理块的东西,因此此时直接通过一个pages数组来进行管理,而数组元素的位置是紧跟着 slot部分。

下面就是相关的代码,下面的代码都是在slab_init中,首先是第一部分下面这段主要是设置一些限定值,比如ngx_slab_max_size和ngx_slab_exact_size。

1
2
3
4
5
6
7
8
9
10
    if (ngx_slab_max_size == 0) {
//可以看到这里ngx_slab_max_size的大小是半页,也就是1页以上我们就用pages来管理
        ngx_slab_max_size = ngx_pagesize / 2;
//这里计算一页用uintptr_t类型来表示所有块,那么每块是多大
        ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(uintptr_t));
//计算shift
        for (n = ngx_slab_exact_size; n >>= 1; ngx_slab_exact_shift++) {
            /* void */
        }
    }

然后是初始化ngx_slab_pool_t部分,主要是初始化slot数组和pages数组。
默认是每个slot数组的next指向自己,这个表明当前的slot数组还没有管理对应的页。具体的结构可以看我一开始的内存图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    pool->min_size = 1 << pool->min_shift;
//这个时候p指向pool_t的末尾
    p = (u_char *) pool + sizeof(ngx_slab_pool_t);
//计算大小,可以看到是除了ngx_slab_pool_t的大小
    size = pool->end - p;
 
    ngx_slab_junk(p, size);
 
    slots = (ngx_slab_page_t *) p;
//计算需要多大的数组
    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;
    }
//此时指向pages数组
    p += n * sizeof(ngx_slab_page_t);
//计算一共能够保存多少个页,加上ngx_slab_page_t,是因为每一个页都会有一个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));
//设置pages指针
    pool->pages = (ngx_slab_page_t *) p;
//free的next初始值指向第一个没有被使用page。
    pool->free.prev = 0;
    pool->free.next = (ngx_slab_page_t *) p;
//设置pages的属性
    pool->pages->slab = pages;
    pool->pages->next = &pool->free;
    pool->pages->prev = (uintptr_t) &pool->free;
//设置起始值,这里刚好是跳过slot和page部分。
    pool->start = (u_char *)
                  ngx_align_ptr((uintptr_t) p + pages * sizeof(ngx_slab_page_t),
                                 ngx_pagesize);

而小于ngx_slab_max_size又分为3种情况,这里也是按照请求的大小来进行划分,分界线是 ngx_slab_exact_shift,由于一个slab将会管理很多个块,此时就需要一个东西来表示每个块的具体情况,这里这个数值就是用来控制使 用什么样的方式来表示每个块的使用情况,当等于ngx_slab_exact_shift的话,nginx会直接使用一个域叫做 slab(uintptr_t类型 ),它的每一位表示每一个块的使用情况,这里会提前算好slab域最多能表示多少个块的使用情况,这个值就成为我们这里的exact。当小于 ngx_slab_exact_shift,则说明slab域无法表示完全所有的块,这个时候会在数据区域的head加上一个bitmap的数组,这个数 组就保存了当前slab的所有块的使用情况,而当大于ngx_slab_exact_shift,此时slab保存信息绰绰有余,并且我们必须知道当前的 shift在一页能够分配多少个块,因此我们还需要存储当前的shift,于是nginx在slab的低16位或者32位(64位平台),来保存当前页的 shift。

紧接着就是free域,这个域一直指向第一个没有被使用的页面。因此每次分配页面都会从free开始,而free页面则会将页面返还给free。

来看对应的代码,这部分的代码都在ngx_slab_alloc_locked中,这个是slab的分配函数,首先它会判断请求的大小是否大于 ngx_slab_max_size,如果大于它则说明需要从pages数组进行分配,因此会先计算需要分配的页数量,然后从page数组汇总返回对应的 page slab位置,最终从start计算偏移然后返回给用户。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    if (size >= ngx_slab_max_size) {
 
        ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
                       "slab alloc: %uz", size);
//得到对应的page,也就是page数组的对应元素。
        page = ngx_slab_alloc_pages(pool, (size + ngx_pagesize - 1)
                                          >> ngx_pagesize_shift);
        if (page) {
//得到想对于start的偏移。
            p = (page - pool->pages) << ngx_pagesize_shift;
            p += (uintptr_t) pool->start;
 
        } else {
            p = 0;
        }
 
        goto done;
    }

接下来主要来看当第一次分配内存的情况,也就是当前的slot为空,并没有对应的页面。此时需要alloc一个页面,然后根据大小来对块进行管理。
首先是请求大小小于ngx_slab_exact_shift的情况,这时候需要内存前放一个header来保存位图,而位图数组的个数计算是这样的,首 先计算需要多少字节((1 << (ngx_pagesize_shift - shift)),然后再来计算需要多少数量(除上sizeof(uintptr_t) * 8).

这里要注意prev指针,这里prev指针的后2位会被用来保存当前的page对应的类型(也就是对应ngx_slab_exact_shift的分割).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
        if (shift < ngx_slab_exact_shift) {
//得到对应的偏移
            p = (page - pool->pages) << ngx_pagesize_shift;
//得到位图位置
            bitmap = (uintptr_t *) (pool->start + p);
//计算当前shift对应的位
            s = 1 << shift;
            n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;
 
            if (n == 0) {
                n = 1;
            }
//设置位
            bitmap[0] = (2 << n) - 1;
//得到bitmap的大小
            map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);
//其他的位设置为0.
            for (i = 1; i < map; i++) {
                bitmap[i] = 0;
            }
//slab设置为偏移
            page->slab = shift;
//page和slots连接起来的。
            page->next = &slots[slot];
//prev设置为slots的指针,这里可以看到成为了一个环,然后后3位设置类型
            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;
 
        }

然后是请求等于ngx_slab_exact_shift的情况,这种情况是最简单的,它就用slab来保存对应的块的信息。而prev指针和上面一样,保存块的类型信息。这里要注意,slab最后一位是1主要是为了计算方便。

1
2
3
4
5
6
7
8
9
10
11
12
//这里slab设置
            page->slab = 1;
            page->next = &slots[slot];
//设置prev
            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;

最后是大于ngx_slab_exact_shift的情况,这个时候,也是用slab来保存块的信息,不过由于此时只有高16或者32位用来保存块的信息,然后低位用来保存对应的偏移。

1
2
3
4
5
6
7
8
9
10
11
12
//可以看到先左移16或者32位表示第一个块被使用,然后再或上shift来保存偏移值。
            page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) | shift;
            page->next = &slots[slot];
//设置prev
            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;

这里如果请求时当前的slot已经挂载好page的情况的代码就不分析了,因为原理和上面一样,只不过是一个反向的操作,就是取出对应的块的信息,然后找到第一个没有被使用的块然后返回。

这里还有一种情况要处理,那就是当分配完某个块之后,当前的页面的所有块都被分配完毕了,此时处理其实很简单,将当前的page从 slot->next去除掉,然后将next指针重新指向slot自己,然后下次进来就会重新分配page了。下面是请求等于 ngx_slab_exact_shift的处理:

1
2
3
4
5
6
7
8
9
10
                        if (page->slab == NGX_SLAB_BUSY) {
//取出prev指针,这里要清除尾部保存的shift
                            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;
                        }

然后就是上面很重要的一个函数,ngx_slab_alloc_pages,这个函数主要是用来分配一定数量page,然后返回。它的实现是这样 的,遍历free,找到适合的page,然后返回对应的page。这里要注意每一个free掉的page最终都会挂载到free上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
static ngx_slab_page_t *
ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
{
    ngx_slab_page_t  *page, *p;
//开始遍历free指针。
    for (page = pool->free.next; page != &pool->free; page = page->next) {
//判断slab值,也就是看还能分配多少page。
        if (page->slab >= pages) {
//如果是远远大于pages,则直接分配对应的page,然后将当前的要分配的page从free中去除。
            if (page->slab > pages) {
//更新page的属性。
                page[pages].slab = page->slab - pages;
                page[pages].next = page->next;
                page[pages].prev = page->prev;
//从free中去除
                p = (ngx_slab_page_t *) page->prev;
                p->next = &page[pages];
                page->next->prev = (uintptr_t) &page[pages];
 
            } else {
                p = (ngx_slab_page_t *) page->prev;
                p->next = page->next;
                page->next->prev = page->prev;
            }
//设置slab
            page->slab = pages | NGX_SLAB_PAGE_START;
            page->next = NULL;
            page->prev = NGX_SLAB_PAGE;
//如果只是分配一个page,则直接返回
            if (--pages == 0) {
                return page;
            }
//否则需要将已经分配的页的slab全部设置为busy。
            for (p = page + 1; pages; pages--) {
                p->slab = NGX_SLAB_PAGE_BUSY;
                p->next = NULL;
                p->prev = NGX_SLAB_PAGE;
                p++;
            }
 
            return page;
        }
    }
 
    ngx_slab_error(pool, NGX_LOG_CRIT, "ngx_slab_alloc() failed: no memory");
 
    return NULL;
  评论这张
 
阅读(489)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018