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;  
4.   
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.     }  
16.   
17.     if (c->ctor)//如果定義了構造函數則調用構造函數   
18.         c->ctor(b);  
19.   
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;  
8.   
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;  
16.   
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;  
31.   
32.         /* Attempt to alloc */  
33.         prev = sp->list.prev;  
34.         b = slob_page_alloc(sp, size, align);//分配對象   
35.         if (!b)  
36.             continue;  
37.   
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);  
48.   
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);  
56.   
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);  
5.   
6.     for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {  
7.         slobidx_t avail = slob_units(cur);//計算獲取的空閒塊的容量   
8.   
9.         /*如果設置了對齊值則先將塊進行對齊*/  
10.         if (align) {  
11.             aligned = (slob_t *)ALIGN((unsigned long)cur, align);  
12.             delta = aligned - cur;//計算對齊後的對象增加了多少字節的內存   
13.         }  
14.   
15.         /*空閒塊內存不小於要求分配的 units+對齊增量*/  
16.         if (avail >= units + delta) { /* room enough? */  
17.             slob_t *next;  
18.   
19.             /*確實進行了對齊操作*/  
20.             if (delta) { /* need to fragment head to align? */  
21.                 next = slob_next(cur);//獲取下一個空閒塊   
22.   
23.                 /*這裡將原本的一個塊分裂成了兩個塊*/  
24.                 set_slob(aligned, avail - delta, next);//設置空閒對象偏移aligned-->next   
25.                 set_slob(cur, delta, aligned);//設置空閒對象偏移cur--->aligned   
26.   
27.                 /*調整prev指針以及cur指針，都向後移動一個塊*/  
28.                 prev = cur;  
29.                 cur = aligned;  
30.                 avail = slob_units(cur);//重新獲取單元數   
31.             }  
32.   
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.             }  
46.   
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. }