Linux Slob分配器(二)--分配對象

上節介紹了Slob分配器的相關概念和思想，這節來看Slob分配器是如何分配對象的。kmem_cache_alloc_node()函數用來分配一個專用緩存的對象：

相關閱讀：
Linux Slob分配器(一)--概述 http://www.linuxidc.com/Linux/2012-07/64107.htm
Linux Slob分配器(三)--釋放對象 http://www.linuxidc.com/Linux/2012-07/64109.htm

1. void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)
2. {
3. void *b;
5. if (c->size < PAGE_SIZE) {//對象小於PAGE_SIZE，由Slob分配器進行分配
6. b = slob_alloc(c->size, flags, c->align, node);
7. trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
8. SLOB_UNITS(c->size) * SLOB_UNIT,
9. flags, node);
10. } else {//否則通過伙伴系統分配
11. b = slob_new_pages(flags, get_order(c->size), node);
12. trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
13. PAGE_SIZE << get_order(c->size),
14. flags, node);
15. }
17. if (c->ctor)//如果定義了構造函數則調用構造函數
18. c->ctor(b);
20. kmemleak_alloc_recursive(b, c->size, 1, c->flags, flags);
21. return b;
22. }

由於slob為PAGE_SIZE大小，因此首先要判斷要求分配的對象的大小是否在這個范圍內，如果是，則通過Slob分配器來分配，否則的話通過伙伴系統分配。

來看Slob分配對象的具體過程

1. static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
2. {
3. struct slob_page *sp;
4. struct list_head *prev;
5. struct list_head *slob_list;
6. slob_t *b = NULL;
7. unsigned long flags;
9. /*根據分配對象的大小選擇從哪個鏈表的slob中進行分配*/
10. if (size < SLOB_BREAK1)
11. slob_list = &free_slob_small;
12. else if (size < SLOB_BREAK2)
13. slob_list = &free_slob_medium;
14. else
15. slob_list = &free_slob_large;
17. spin_lock_irqsave(&slob_lock, flags);
18. /* Iterate through each partially free page, try to find room */
19. list_for_each_entry(sp, slob_list, list) {//遍歷slob鏈表
20. #ifdef CONFIG_NUMA
21. /*
22. * If there's a node specification, search for a partial
23. * page with a matching node id in the freelist.
24. */
25. if (node != -1 && page_to_nid(&sp->page) != node)//節點不匹配
26. continue;
27. #endif
28. /* Enough room on this page? */
29. if (sp->units < SLOB_UNITS(size))//slob中的空間不夠
30. continue;
32. /* Attempt to alloc */
33. prev = sp->list.prev;
34. b = slob_page_alloc(sp, size, align);//分配對象
35. if (!b)
36. continue;
38. /* Improve fragment distribution and reduce our average
39. * search time by starting our next search here. (see
40. * Knuth vol 1, sec 2.5, pg 449) */
41. /*這裡將slob_list鏈表頭移動到prev->next前面，以便下次遍歷時能夠從prev->next開始遍歷*/
42. if (prev != slob_list->prev &&
43. slob_list->next != prev->next)
44. list_move_tail(slob_list, prev->next);
45. break;
46. }
47. spin_unlock_irqrestore(&slob_lock, flags);
49. /* Not enough space: must allocate a new page */
50. if (!b) {//沒有分配到對象，也就是說slob_list中沒有可以滿足分配要求的slob了
51. b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node);//創建新的slob
52. if (!b)
53. return NULL;
54. sp = slob_page(b);//獲取slob的地址
55. set_slob_page(sp);
57. spin_lock_irqsave(&slob_lock, flags);
58. sp->units = SLOB_UNITS(PAGE_SIZE);//計算單元數
59. sp->free = b; //設置首個空閒塊的地址
60. INIT_LIST_HEAD(&sp->list);
61. set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
62. set_slob_page_free(sp, slob_list); //將sp鏈入slob_list
63. b = slob_page_alloc(sp, size, align);//從新的slob中分配塊
64. BUG_ON(!b);
65. spin_unlock_irqrestore(&slob_lock, flags);
66. }
67. if (unlikely((gfp & __GFP_ZERO) && b))
68. memset(b, 0, size);
69. return b;
70. }

• 首先要根據對象的大小來決定從哪個全局鏈表中尋找slob進行分配
• 遍歷選取的鏈表，找到一個空間足夠滿足分配要求的slob
• 從選取的slob中分配對象塊(slob_page_alloc())
• 如果遍歷完整個鏈表都沒能分配到對象，則創建一個新的slob(slob_new_page()),然後設置slob的屬性，再進行分配，可以看到一個新的slob中只有一個塊，並且下一個空閒對象的指針指向了下一頁的起始處，也就是頁對齊的

來看分配的細節操作slab_page_alloc()

1. static void *slob_page_alloc(struct slob_page *sp, size_t size, int align)
2. {
3. slob_t *prev, *cur, *aligned = NULL;
4. int delta = 0, units = SLOB_UNITS(size);
6. for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {
7. slobidx_t avail = slob_units(cur);//計算獲取的空閒塊的容量
9. /*如果設置了對齊值則先將塊進行對齊*/
10. if (align) {
11. aligned = (slob_t *)ALIGN((unsigned long)cur, align);
12. delta = aligned - cur;//計算對齊後的對象增加了多少字節的內存
13. }
15. /*空閒塊內存不小於要求分配的 units+對齊增量*/
16. if (avail >= units + delta) { /* room enough? */
17. slob_t *next;
19. /*確實進行了對齊操作*/
20. if (delta) { /* need to fragment head to align? */
21. next = slob_next(cur);//獲取下一個空閒塊
23. /*這裡將原本的一個塊分裂成了兩個塊*/
24. set_slob(aligned, avail - delta, next);//設置空閒對象偏移aligned-->next
25. set_slob(cur, delta, aligned);//設置空閒對象偏移cur--->aligned
27. /*調整prev指針以及cur指針，都向後移動一個塊*/
28. prev = cur;
29. cur = aligned;
30. avail = slob_units(cur);//重新獲取單元數
31. }
33. next = slob_next(cur);//獲取下一個空閒塊
34. if (avail == units) { /* 空閒塊的大小和要求的大小完全相符 */
35. if (prev)//存在先驅塊，則將先驅塊的指針指向next塊
36. set_slob(prev, slob_units(prev), next);
37. else//不存在先驅塊說明為第一個塊，則將free直接指向next
38. sp->free = next;
39. } else { /* 大小不相符，則要將塊分裂*/
40. if (prev)
41. set_slob(prev, slob_units(prev), cur + units);
42. else
43. sp->free = cur + units;
44. set_slob(cur + units, avail - units, next);
45. }
47. sp->units -= units;//減少slob的單元數
48. if (!sp->units)//單元數為0表明slob沒有空閒單元，則從鏈表中刪除
49. clear_slob_page_free(sp);
50. return cur;
51. }
52. if (slob_last(cur))
53. return NULL;
54. }
55. }