内容简介：相关数据结构
Linux 内存管理是一个非常复杂的子系统，要完全说清的话估计要一本书的篇幅。但 Linux 内存管理可以划分成多个部分来阐述，这篇文章主要介绍 slab 算法。
Linux 有个叫伙伴系统的分配算法，这个算法主要解决分配连续个内存页的问题。伙伴分配算法主要以内存页（ 4KB ）作为分配单位，就是说伙伴分配算法每次可以分配 2 order 个内存页（ order 为 0 、 1 、 2...9 ）。但有时候我们只需要申请一个很小的内存区（如 32 字节），这时候使用伙伴分配算法就显得浪费了。为了解决小内存分配问题， Linux 使用了 slab 分配算法。
相关数据结构
slab 算法有两个重要的数据结构，一个是 kmem_cache_t ，另外一个是 slab_t 。下面我们先来看看 kmem_cache_t 结构：
1. struct kmem_cache_s {
2. struct list_head slabs_full;
3. struct list_head slabs_partial;
4. struct list_head slabs_free;
5. unsigned int objsize;
6. unsigned int flags;
7. unsigned int num;
8. spinlock_t spinlock;
9.
10. /* 2) slab additions /removals */
11. /* order of pgs per slab (2^n) */
12. unsigned int gfporder;
13.
14. /* force GFP flags, e.g. GFP_DMA */
15. unsigned int gfpflags;
16.
17. size_t colour;
18. unsigned int colour_off;
19. unsigned int colour_next;
20. kmem_cache_t *slabp_cache;
21. ...
22. struct list_head next;
23. ...
24. };
下面介绍一下 kmem_cache_t 结构中比较重要的字段：
-
slab_full ：完全分配的 slab
-
slab_partial ：部分分配的 slab
-
slab_free ：没有被分配过的 slab
-
objsize ：存储的对象大小
-
num ：一个 slab 能够存储的对象个数
-
gfporder ：一个 slab 由 2 gfporder 个内存页组成
-
colour/colour_off/colour_next ：着色区大小（后面会讲到）
slab_t 结构定义如下：
1. typedef struct slab_s {
2. struct list_head list;
3. unsigned long colouroff;
4. void *s_mem;
5. unsigned int inuse;
6. kmem_bufctl_t free;
7. } slab_t;
slab_t 结构各个字段的用途如下：
-
list ：连接（全满 / 部分 / 全空）链
-
colouroff ：着色补偿
-
s_mem ：存储对象的起始内存地址
-
inuse ：已经分配多少个对象
-
free ：用于连接空闲的对象
用图来表示它们之间的关系，如下：
这里需要解释一下，一个 slab 会被划分为多个对象（可以理解为结构体），这些对象是 slab 算法分配的最小单元，而一个 slab 一般有一个或者多个内存页（但不能超过 2 4 个页面）组成。
在 kmem_cache_t 结构中的 slab_free 链表的 slab 是内存回收的主要备选对象。由于对象是从 slab 中分配和释放，所以单个 slab 可以在 slab 列表中进行一定。例如，当一个 slab 中所有对象被分配完时，就从 slab_partial 列表中移动到 slab_full 列表中。而当一个在 slab_free 列表中的 slab 被分配对象时，就会从 slab_free 列表中移动到 slab_partial 列表中。当一个 slab 中所有对象被释放时，就会从 slab_partial 列表中移动到 slab_free 列表中。
slab分配器初始化
slab 分配器的初始化由 kmem_cache_init() 函数完成，如下：
1. void __init kmem_cache_init( void )
2. {
3. size_t left_over;
4.
5. init_MUTEX(&cache_chain_sem);
6. INIT_LIST_HEAD(&cache_chain);
7.
8. kmem_cache_estimate( 0 , cache_cache.objsize, 0 ,
9. &left_over, &cache_cache.num);
10. if (!cache_cache.num)
11. BUG();
12.
13. cache_cache.colour = left_over/cache_cache.colour_off;
14. cache_cache.colour_next = 0 ;
15. }
这个函数主要用来初始化 cache_cache 这个变量， cache_cache 是一个类型为 kmem_cache_t 的结构体变量，定义如下：
1. static kmem_cache_t cache_cache = {
2. slabs_full: LIST_HEAD_INIT(cache_cache.slabs_full),
3. slabs_partial: LIST_HEAD_INIT(cache_cache.slabs_partial),
4. slabs_free: LIST_HEAD_INIT(cache_cache.slabs_free),
5. objsize: sizeof(kmem_cache_t),
6. flags: SLAB_NO_REAP,
7. spinlock: SPIN_LOCK_UNLOCKED,
8. colour_off: L1_CACHE_BYTES,
9. name: "kmem_cache" ,
10. };
为什么需要一个这样的对象呢？因为本身 kmem_cache_t 结构体也是小内存对象，所以也应该有 slab 分配器来分配的，但这样就出现 “ 鸡蛋和鸡谁先出现 ” 的问题。在系统初始化的时候， slab 分配器还没有初始化，所以并不能使用 slab 分配器来分配一个 kmem_cache_t 对象，这时候只能通过定义一个 kmem_cache_t 类型的静态变量来来管理 slab 分配器了，所以 cache_cache 静态变量就是用来管理 slab 分配器的。
从上面的代码可知， cache_cache 的 objsize 字段被设置为 sizeof(kmem_cache_t) 的大小，所以这个对象主要是用来分配不同类型的 kmem_cache_t 对象的。
kmem_cache_init() 函数调用了 kmem_cache_estimate() 函数来计算一个 slab 能够保存多少个大小为 cache_cache.objsize 的对象，并保存到 cache_cache.num 字段中。一个 slab 中不可能全部都用来分配对象的，举个例子：一个 4096 字节大小的 slab 用来分配大小为 22 字节的对象，可以划分为 186 个，但还剩余 4 字节不能使用的，所以这部分内存用来作为着色区。着色区的作用是为了错开不同的 slab ，让 CPU 更有效的缓存 slab 。当然这属于优化部分，对 slab 分配算法没有多大的影响。就是说就算不对 slab 进行着色操作， slab 分配算法还是可以工作起来的。
kmem_cache_t对象申请
kmem_cache_t 是用来管理和分配对象的，所以要使用 slab 分配器时，必须先申请一个 kmem_cache_t 对象，申请 kmem_cache_t 对象由 kmem_cache_create() 函数进行：
1. kmem_cache_t *kmem_cache_create (
2. const char *name,
3. size_t size,
4. size_t offset,
5. unsigned long flags,
6. void (*ctor)( void *, kmem_cache_t *, unsigned long ),
7. void (*dtor)( void *, kmem_cache_t *, unsigned long )
8. ) {
9. ...
10. cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
11. if (!cachep)
12. goto opps;
13. memset(cachep, 0 , sizeof(kmem_cache_t));
14. ...
15. do {
16. unsigned int break_flag = 0 ;
17. cal_wastage:
18. kmem_cache_estimate(cachep->gfporder, size, flags,
19. &left_over, &cachep->num);
20. if (break_flag)
21. break ;
22. if (cachep->gfporder >= MAX_GFP_ORDER)
23. break ;
24. if (!cachep->num)
25. goto next;
26. if (flags & CFLGS_OFF_SLAB && cachep->num > offslab_limit) {
27. /* Oops, this num of objs will cause problems. */
28. cachep->gfporder--;
29. break_flag++;
30. goto cal_wastage;
31. }
32.
33. if (cachep->gfporder >= slab_break_gfp_order)
34. break ;
35.
36. if ((left_over* 8 ) <= (PAGE_SIZE<<cachep->gfporder))
37. break ; /* Acceptable internal fragmentation. */
38. next:
39. cachep->gfporder++;
40. } while ( 1 );
41.
42. if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
43. flags &= ~CFLGS_OFF_SLAB;
44. left_over -= slab_size;
45. }
46.
47. /* Offset must be a multiple of the alignment. */
48. offset += (align- 1 );
49. offset &= ~(align- 1 );
50. if (!offset)
51. offset = L1_CACHE_BYTES;
52. cachep->colour_off = offset;
53. cachep->colour = left_over/offset;
54.
55. cachep->flags = flags;
56. cachep->gfpflags = 0 ;
57. if (flags & SLAB_CACHE_DMA)
58. cachep->gfpflags |= GFP_DMA;
59. spin_lock_init(&cachep->spinlock);
60. cachep->objsize = size;
61. INIT_LIST_HEAD(&cachep->slabs_full);
62. INIT_LIST_HEAD(&cachep->slabs_partial);
63. INIT_LIST_HEAD(&cachep->slabs_free);
64.
65. if (flags & CFLGS_OFF_SLAB)
66. cachep->slabp_cache = kmem_find_general_cachep(slab_size, 0 );
67. cachep->ctor = ctor;
68. cachep->dtor = dtor;
69. strcpy(cachep->name, name);
70.
71. down(&cache_chain_sem);
72. {
73. struct list_head *p;
74.
75. list_for_each(p, &cache_chain) {
76. kmem_cache_t *pc = list_entry(p, kmem_cache_t, next);
77. }
78. }
79.
80. list_add(&cachep->next, &cache_chain);
81. up(&cache_chain_sem);
82. opps:
83. return cachep;
84. }
kmem_cache_create() 函数比较长，所以上面代码去掉了一些不那么重要的地方，使代码更清晰的体现其原理。
在 kmem_cache_create() 函数中，首先调用 kmem_cache_alloc() 函数申请一个 kmem_cache_t 对象，我们看到调用 kmem_cache_alloc() 时，传入的就是 cache_cache 变量。申请完 kmem_cache_t 对象后需要对其进行初始化操作，主要是对 kmem_cache_t 对象的所有字段进行初始化： 1) 计算需要多少个页面来作为 slab 的大小。 2) 计算一个 slab 能够分配多少个对象。 3) 计算着色区信息。 4) 初始化 slab_full / slab_partial / slab_free 链表。 5) 把申请的 kmem_cache_t 对象保存到 cache_chain 链表中。
对象分配
申请完 kmem_cache_t 对象后，就使用通过调用 kmem_cache_alloc() 函数来申请指定的对象。 kmem_cache_alloc() 函数代码如下：
1. static inline void *
2. kmem_cache_alloc_one_tail (kmem_cache_t *cachep, slab_t *slabp)
3. {
4. void *objp;
5.
6. slabp->inuse++;
7. objp = slabp->s_mem + slabp->free*cachep->objsize;
8. slabp->free = slab_bufctl(slabp)[slabp->free];
9.
10. if (unlikely(slabp->free == BUFCTL_END)) {
11. list_del(&slabp->list);
12. list_add(&slabp->list, &cachep->slabs_full);
13. }
14. return objp;
15. }
16.
17. static inline void *
18. __kmem_cache_alloc(kmem_cache_t *cachep, int flags)
19. {
20. unsigned long save_flags;
21. void * objp;
22. struct list_head * slabs_partial, * entry;
23. slab_t *slabp;
24.
25. kmem_cache_alloc_head(cachep, flags);
26. try_again:
27. local_irq_save(save_flags);
28.
29. slabs_partial = &(cachep)->slabs_partial;
30. entry = slabs_partial->next;
31.
32. if (unlikely(entry == slabs_partial)) {
33. struct list_head * slabs_free;
34. slabs_free = &(cachep)->slabs_free;
35. entry = slabs_free->next;
36. if (unlikely(entry == slabs_free))
37. goto alloc_new_slab;
38. list_del(entry);
39. list_add(entry, slabs_partial);
40. }
41.
42. slabp = list_entry(entry, slab_t, list);
43. objp = kmem_cache_alloc_one_tail(cachep, slabp);
44.
45. local_irq_restore(save_flags);
46. return objp;
47.
48. alloc_new_slab:
49. local_irq_restore(save_flags);
50. if (kmem_cache_grow(cachep, flags))
51. goto try_again;
52. return NULL;
53. }
kmem_cache_alloc() 函数被我展开之后如上代码， kmem_cache_alloc() 函数的主要步骤是： 1) 从 kmem_cache_t 对象的 slab_partial 列表中查找是否有 slab 可用，如果有就直接从 slab 中分配一个对象。 2) 如果 slab_partial 列表中没有可用的 slab ，那么就从 slab_free 列表中查找可用的 slab ，如果有可用 slab ，就从 slab 分配一个对象，并且把此 slab 放置到 slab_partial 列表中。 3) 如果 slab_free 列表中没有可用的 slab ，那么就调用 kmem_cache_grow() 函数申请新的 slab 来进行对象的分配。
一个 slab 的结构如下图：
灰色部分是着色区，绿色部分是 slab 管理结构，黄色部分是空闲对象链表的索引，红色部分是对象的实体。我们可以看到 slab 结构的 s_mem 字段指向了对象实体列表的起始地址。
分配对象的时候就是先通过 slab 结构的 free 字段查看是否有空闲的对象可用， free 字段保存了空闲对象链表的首节点索引。
对象释放
对象的释放比较简单，主要通过调用 kmem_cache_free() 函数完成，而 kmem_cache_free() 函数最终会调用 kmem_cache_free_one() 函数，代码如下：
1. static inline void
2. kmem_cache_free_one(kmem_cache_t *cachep, void *objp)
3. {
4. slab_t* slabp;
5.
6. {
7. unsigned int objnr = (objp-slabp->s_mem)/cachep->objsize;
8. slab_bufctl(slabp)[objnr] = slabp->free;
9. slabp->free = objnr;
10. }
11.
12. /* fixup slab chains */
13. {
14. int inuse = slabp->inuse;
15. if (unlikely(!--slabp->inuse)) {
16. /* Was partial or full, now empty. */
17. list_del(&slabp->list);
18. list_add(&slabp->list, &cachep->slabs_free);
19. } else if (unlikely(inuse == cachep->num)) {
20. /* Was full. */
21. list_del(&slabp->list);
22. list_add(&slabp->list, &cachep->slabs_partial);
23. }
24. }
25. }
对象释放的时候首先会把对象的索引添加到 slab 的空闲对象链表中，然后根据 slab 的使用情况移动 slab 到合适的列表中。 1) 如果 slab 所有对象都被释放完时，把 slab 放置到 slab_free 列表中。 2) 如果对象所在的 slab 原来在 slab_full 中，那么就把 slab 移动到 slab_partial 中。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
人人都是产品经理
苏杰 / 电子工业出版社 / 2010年4月 / 45.00元
这是写给“-1到3岁的产品经理”的书，适合刚入门的产品经理、产品规划师、需求分析师，以及对做产品感兴趣的学生，用户体验、市场运营、技术部门的朋友们，特别是互联网、软件行业。作为一名“4岁的产品经理”，作者讲述了过去3年的经历与体会，与前辈们的书不同，本书就像你走到作者身边，说“嗨哥们！晚上有空吃个饭么，随便聊聊做产品的事吧”，然后作者说“好啊”。 书名叫“人人都是产品经理”，是因为作者觉得过......一起来看看 《人人都是产品经理》 这本书的介绍吧!
