ukallocbbuddy

内存 评论

bbuddy.c （伙伴算法）

源码解读

基础数据结构

chunk_head_st

1
2
3
4
5
struct chunk_head_st {
	chunk_head_t *next;  /* 指向下一个链表节点 */
	chunk_head_t **pprev;  /* 指向当前空闲内存链表的链表头 */
	unsigned int level;  /* 当前链表的等级，即存储的每个内存块大小为2^level个页 */
};

chunk_tail_st

1
2
3
struct chunk_tail_st {
	unsigned int level;
};

uk_bbpalloc_memr

1
2
3
4
5
6
7
8
9
10
/* 为每个内存区域分别保留位图 
   memr：memory region
	*/
struct uk_bbpalloc_memr {
	struct uk_bbpalloc_memr *next;
	unsigned long first_page;  /*区块所对应的第一个页面的地址*/
	unsigned long nr_pages;   /*该内存区块中管理的页面数量*/
	unsigned long mm_alloc_bitmap_size;  /* 该内存区块的位图所占的地址区域大小 */
	unsigned long *mm_alloc_bitmap;  //伙伴位图
};

uk_bbpalloc

1
2
3
4
5
6
7
8
struct uk_bbpalloc {
	unsigned long nr_free_pages;
    /* 伙伴算法中空闲内存链表组成的数组，下标为i的链表存储的每个内存块大小为2^i个页 */
	chunk_head_t *free_head[FREELIST_SIZE];  
    /* 上述链表的链表头指针初始指向的区域，因为不是指针变量，所以一开始就有分配内存，起到链表的第一个节点的作用 */
	chunk_head_t free_tail[FREELIST_SIZE];  
	struct uk_bbpalloc_memr *memr_head;
};

函数解析

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
/* 给定当前页面的虚拟地址page_va，查找该页面在那一块内存块中，查找成功返回该内存块，否则返回NULL */
static inline struct uk_bbpalloc_memr *map_get_memr(struct uk_bbpalloc *b,
						    unsigned long page_va)  
    /* page_va: 页面虚拟地址(va virtual address) */
{							
	struct uk_bbpalloc_memr *memr = NULL;

	/*
	 * Find bitmap of according memory region  查找相应内存区域的位图
	 * This is a linear search but it is expected that we have only a few
	 * of them. It should be just one region in most cases
	 * 线性搜索。在大多数情况下，它应该只是一个区域
	 */
	for (memr = b->memr_head; memr != NULL; memr = memr->next) {
		if ((page_va >= memr->first_page)
		    && (page_va < (memr->first_page +
		    (memr->nr_pages << __PAGE_SHIFT))))
			return memr;
	}

	/*
	 * No region found
	 */
	return NULL;
}

虚拟内存分页

如图所示，每个页的大小为2^12，所以每隔一个页的开头实际地址就是当前编号向左移12位，而当前页向后数nr_pages所计算出的地址则为page_first + nr_pages << __PAGE_SHIFT（也就是12）。该内存块的起始地址为first_page，终止地址为page_first + nr_pages << __PAGE_SHIFT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 查看page_va在bitmap中的状态 */
static inline unsigned long allocated_in_map(struct uk_bbpalloc *b,
				   unsigned long page_va)
{
	struct uk_bbpalloc_memr *memr = map_get_memr(b, page_va);
	unsigned long page_idx;
	unsigned long bm_idx, bm_off;

	/* treat pages outside of region as allocated */
	if (!memr)
		return 1;

	page_idx = (page_va - memr->first_page) >> __PAGE_SHIFT;
    /* 取该页在bitmap中的下标 */
	bm_idx = page_idx / PAGES_PER_MAPWORD;  
    /* idx & 11111，只取低5位，也就是求偏移量 */
	bm_off = page_idx & (PAGES_PER_MAPWORD - 1);  

	return ((memr)->mm_alloc_bitmap[bm_idx] & (1UL << bm_off)); 
    /* 查询bitmap中下标为bm_idx的第bm_off位的状态 */
}
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
/* 将从first_page开始到first_page + nr_pages - 1的所有页映射进bitmap中 */
static void map_alloc(struct uk_bbpalloc *b, uintptr_t first_page,
		      unsigned long nr_pages)
{
	struct uk_bbpalloc_memr *memr;
	unsigned long first_page_idx, end_page_idx;
	unsigned long start_off, end_off, curr_idx, end_idx;

	/*
	 * In case there was no memory region found, the allocator
	 * is in a really bad state. It means that the specified page
	 * region is not covered by our allocator.
	 */
	memr = map_get_memr(b, first_page);
	UK_ASSERT(memr != NULL);
	UK_ASSERT((first_page + (nr_pages << __PAGE_SHIFT))
		  <= (memr->first_page + (memr->nr_pages << __PAGE_SHIFT)));
	
    /* 计算起始page在bitmap中的idx与偏移量以及终止page在bitmap中的idx以及偏移量 */
	first_page -= memr->first_page;
	first_page_idx = first_page >> __PAGE_SHIFT;
	curr_idx = first_page_idx / PAGES_PER_MAPWORD;
	start_off = first_page_idx & (PAGES_PER_MAPWORD - 1);
	end_page_idx = first_page_idx + nr_pages;
	end_idx = end_page_idx / PAGES_PER_MAPWORD;
	end_off = end_page_idx & (PAGES_PER_MAPWORD - 1);
	
    /* 分类讨论，讨论该次分配的所有页是否在一个mapword中 */
	if (curr_idx == end_idx) {
        /* 如果在同一个mapword中，则将该mapword的[start_off, end_off)位 置1 */
		memr->mm_alloc_bitmap[curr_idx] |=
		    ((1UL << end_off) - 1) & -(1UL << start_off);
	} else {
    /* 如果不在同一个mapword中，则先将curr_idx所在的mapword从start_off开始到最高位填充完毕，再将curr_idx到end_idx中所有的mapword填充完毕，最后将end_idx所在的低end_off位填充完毕 */
		memr->mm_alloc_bitmap[curr_idx] |= -(1UL << start_off);
		while (++curr_idx < end_idx)
			memr->mm_alloc_bitmap[curr_idx] = ~0UL;
		memr->mm_alloc_bitmap[curr_idx] |= (1UL << end_off) - 1;
	}

	b->nr_free_pages -= nr_pages; /* 更新可分配的页面数 */
}

map_alloc_1

map_alloc_2

如图所示，两个图分别演示了分类讨论中的两种情况，分别为curr_idx与end_idx在同一mapword中与curr_idex与end_idx在不同mapword中的位填充示意图。

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
/* 同上map_alloc，map_alloc为置1操作，而map_free为置零操作 */
static void map_free(struct uk_bbpalloc *b, uintptr_t first_page,
		     unsigned long nr_pages)
{
	struct uk_bbpalloc_memr *memr;
	unsigned long first_page_idx, end_page_idx;
	unsigned long start_off, end_off, curr_idx, end_idx;

	/*
	 * In case there was no memory region found, the allocator
	 * is in a really bad state. It means that the specified page
	 * region is not covered by our allocator.
	 */
	memr = map_get_memr(b, first_page);
	UK_ASSERT(memr != NULL);
	UK_ASSERT((first_page + (nr_pages << __PAGE_SHIFT))
		  <= (memr->first_page + (memr->nr_pages << __PAGE_SHIFT)));

	first_page -= memr->first_page;
	first_page_idx = first_page >> __PAGE_SHIFT;
	curr_idx = first_page_idx / PAGES_PER_MAPWORD;
	start_off = first_page_idx & (PAGES_PER_MAPWORD - 1);
	end_page_idx = first_page_idx + nr_pages;
	end_idx = end_page_idx / PAGES_PER_MAPWORD;
	end_off = end_page_idx & (PAGES_PER_MAPWORD - 1);

	if (curr_idx == end_idx) {
		memr->mm_alloc_bitmap[curr_idx] &=
		    -(1UL << end_off) | ((1UL << start_off) - 1);
	} else {
		memr->mm_alloc_bitmap[curr_idx] &= (1UL << start_off) - 1;
		while (++curr_idx != end_idx)
			memr->mm_alloc_bitmap[curr_idx] = 0;
		memr->mm_alloc_bitmap[curr_idx] &= -(1UL << end_off);
	}

	b->nr_free_pages += nr_pages;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 计算特定值的函数， 返回传入数的下一个2次幂的对数，如6的下一个2次幂就是8，8的对数为3 */
/* return log of the next power of two of passed number */
static inline unsigned long num_pages_to_order(unsigned long num_pages)
{
	UK_ASSERT(num_pages != 0);

	/* ukarch_flsl has undefined behavior when called with zero */
	if (num_pages == 1)
		return 0;

	/* ukarch_flsl(num_pages - 1) returns log of the previous power of two
	 * of num_pages. ukarch_flsl is called with `num_pages - 1` and not
	 * `num_pages` to handle the case where num_pages is already a power
	 * of two.
	 */
	return ukarch_flsl(num_pages - 1) + 1;
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*  伙伴算法分配内存页 */
static void *bbuddy_palloc(struct uk_alloc *a, unsigned long num_pages)
{
	struct uk_bbpalloc *b;
	size_t i;
	chunk_head_t *alloc_ch, *spare_ch;
	chunk_tail_t *spare_ct;
	
    
    /*
    	alloc_ch: 需要分配的空间的chunk_head
    	spare_ch: 空闲空间的chunk_head
    	spare_ct: 空间空间的chunk_tail
    */
    
	UK_ASSERT(a != NULL);
    
    /* 将a的priv数组转化为uk_bbpalloc(因为priv数组的作用就是用来存放已经被初始化好的uk_bbpalloc，所以每次从priv中转化出来就相当于一直在操作同一个内存分配器) */
	b = (struct uk_bbpalloc *)&a->priv;  
	
    /* 找到要分配的页面数的下一个2次幂的对数 */
	size_t order = (size_t)num_pages_to_order(num_pages);  

	/* Find smallest order which can satisfy the request. 即找到最小的可用块*/
	for (i = order; i < FREELIST_SIZE; i++) {
		if (!FREELIST_EMPTY(b->free_head[i]))
			break;
	}
	if (i == FREELIST_SIZE)
		goto no_memory;

	/* Unlink a chunk. 
		将该块从链表中摘下
	*/
	alloc_ch = b->free_head[i];
	b->free_head[i] = alloc_ch->next;
	alloc_ch->next->pprev = alloc_ch->pprev;

	/* We may have to break the chunk a number of times. */
    /* 折半查找合适的可分配地址空间，并将空闲块重新挂回链表上 */
	while (i != order) {
		/* Split into two equal parts. */
        /*  将当前的i，也就是次幂减一，以便后续操作 */
		i--;
        
        
		spare_ch = (chunk_head_t *)((char *)alloc_ch
					    + (1UL << (i + __PAGE_SHIFT)));
		spare_ct = (chunk_tail_t *)((char *)spare_ch
					    + (1UL << (i + __PAGE_SHIFT))) - 1;
		
        /*
        
   spare_ch = (chunk_head_t *)((char *)alloc_ch + (1UL << (i + __PAGE_SHIFT)));
   tips: 
      int a[] = {1,2,3,4,5};
      int *p = a;
      printf("%d\n", *p); 此时*p的值为1，也就是p[0]
      p += 1;
      printf("%d\n", *p); 此时*p的值为2，也就是p[1]
      这说明了一件事，当在给指针做加减操作的时候移动的字节数与指针所指向的类型相关
      如果是p指向的是char类型，那么p+1只会向后移动一个字节
        		
        	-------------------------------------------------
           |                      2^i个page                  |
        	-------------------------------------------------
        	^                       ^
        	alloc_ch   (char *)alloc_ch + (1UL << (i + __PAGE_SHIFT)) (也就是2^(i-1)个page位置处)
        	
      对于该行代码，(char *)强转操作是为了将alloc_ch暂时指向char类型，所以后面加上2^i页个字节的大小
      由于之前i已经减一了，所以加上2^i之后相当于跳到了原本地址块的一半位置，即伙伴算法中折半找适配块的流程
        	
        	-------------------------------------------------
           |                        |                        |
        	-------------------------------------------------
        	           ^						 ^
        	    前2^(i-1)继续查找	   后2^(i-1)作为空闲区挂载回链表
        
      下一轮：先执行i--，然后流程同上，直到找到合适的内存区域位置(按buddy算法的描述，即alloc_occupy >= 1/2*memr)
        	-------------------------
           |            |            | 
        	-------------------------
        	^           ^
        	alloc_ch   (char *)alloc_ch + (1UL << (i + __PAGE_SHIFT))
        */												
		/* Create new header for spare chunk. */
		spare_ch->level = i;
		spare_ch->next = b->free_head[i];
		spare_ch->pprev = &b->free_head[i];
		spare_ct->level = i;

		/* Link in the spare chunk. */
		spare_ch->next->pprev = &spare_ch->next;
		b->free_head[i] = spare_ch;
        /* 将地址块的后半段作为空闲区域挂载在free_head[i]链表上 */
	}
	map_alloc(b, (uintptr_t)alloc_ch, 1UL << order); /* 将分配出去的所有页在bitmap中置1 */

	uk_alloc_stats_count_palloc(a, (void *) alloc_ch, num_pages);  /* 统计分配的页面数量 */
	return ((void *)alloc_ch);

    /* 报错处理，打印报错信息，并记录错误 */
no_memory:
	uk_pr_warn("%"__PRIuptr": Cannot handle palloc request of order %"__PRIsz": Out of memory\n",
		   (uintptr_t)a, order);

	uk_alloc_stats_count_penomem(a, num_pages);
	errno = ENOMEM;
	return NULL;
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/* 伙伴算法释放内存页 */
static void bbuddy_pfree(struct uk_alloc *a, void *obj, unsigned long num_pages)
{
	struct uk_bbpalloc *b;
	chunk_head_t *freed_ch, *to_merge_ch;
	chunk_tail_t *freed_ct;
	unsigned long mask;

	UK_ASSERT(a != NULL);

	uk_alloc_stats_count_pfree(a, obj, num_pages);
	b = (struct uk_bbpalloc *)&a->priv;
	
    /* 获取需要释放的最小内存的页数的对数 */
	size_t order = (size_t)num_pages_to_order(num_pages);  

	/* if the object is not page aligned it was clearly not from us */
	UK_ASSERT((((uintptr_t)obj) & (__PAGE_SIZE - 1)) == 0);

	/* First free the chunk  将这些内存页在bitmap中置零*/
	map_free(b, (uintptr_t)obj, 1UL << order);

	/* Create free chunk   创建空闲内存块*/
	freed_ch = (chunk_head_t *)obj;
	freed_ct = (chunk_tail_t *)((char *)obj
				    + (1UL << (order + __PAGE_SHIFT))) - 1;

	/* Now, possibly we can conseal chunks together   合并内存块操作*/
    /* while循环的作用是从低到高查询是否有可以合并的内存块 */
	while (order < FREELIST_SIZE) {
		mask = 1UL << (order + __PAGE_SHIFT);
		if ((unsigned long)freed_ch & mask) {
			to_merge_ch = (chunk_head_t *)((char *)freed_ch - mask);
            /* 如果该块已经被分配了或者该块和当前内存块不是一个大小(level)，说明该块不满足伙伴块的定义，直接退出循环 */
			if (allocated_in_map(b, (uintptr_t)to_merge_ch)
			    || to_merge_ch->level != order)
				break;

			/* Merge with predecessor */
			freed_ch = to_merge_ch;
            
            /*
            伙伴块
            
            -----------------------------------------------------
           |                        |                            |
            -----------------------------------------------------
           ^                        ^                            ^
           to_merge_ch           freed_ch                     freed_ct
           
    如果当前块的首地址(unsigned long)freed_ch的第(order + __PAGE_SHIFT)位存在，则说明当前块的伙伴块中地址较大的那一个，被合并的伙伴块则是伙伴块中地址较小的那一个(即to_merge_ch = (chunk_head_t *)((char *)freed_ch - mask);)，所以块合并的时候是将地址较大的伙伴块的首地址指针(freed_ch)移动到地址较小的伙伴块的首地址(to_merge_ch)，且尾地址指针(freed_ct)不变
            */
		} else {
			to_merge_ch = (chunk_head_t *)((char *)freed_ch + mask);
            /* 如果该块已经被分配了或者该块和当前内存块不是一个大小(level)，说明该块不满足伙伴块的定义，直接退出循环 */
			if (allocated_in_map(b, (uintptr_t)to_merge_ch)
			    || to_merge_ch->level != order)
				break;

			/* Merge with successor */
			freed_ct =
			    (chunk_tail_t *)((char *)to_merge_ch + mask) - 1;
            
            /* 
                               to_merge_ch       
                                    ^
                                    |
            -----------------------------------------------------
           |                        |                            |
            -----------------------------------------------------
           ^                       ^                            ^
         freed_ch              freed_ct          (chunk_tail_t *)((char *)to_merge_ch + mask) - 1
            
     如果当前块的首地址(unsigned long)freed_ch的第(order + __PAGE_SHIFT)位不存在，则说明当前块的伙伴块中地址较小的那一个，被合并的伙伴块则是伙伴块中地址较大的那一个(即to_merge_ch = (chunk_head_t *)((char *)freed_ch + mask);)，所以块合并的时候是将地址较小的伙伴块的尾指针(freed_ct)移动到地址较大的伙伴块的尾地址((chunk_tail_t *)((char *)to_merge_ch + mask) - 1)，且首地址指针不变
            
            */
		}

		/* We are commited to merging, unlink the chunk  为了方便下一步的合并操作，所以需要将该块从原链表摘下 */
		*(to_merge_ch->pprev) = to_merge_ch->next;
		to_merge_ch->next->pprev = to_merge_ch->pprev;

		order++;
	}

	/* Link the new chunk   将我们合并好的大的内存块重新放回空闲内存块链表*/
	freed_ch->level = order;
	freed_ch->next = b->free_head[order];
	freed_ch->pprev = &b->free_head[order];
	freed_ct->level = order;

	freed_ch->next->pprev = &freed_ch->next;
	b->free_head[order] = freed_ch;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 很简单的功能，查找并返回最大可用页的数量 */
static long bbuddy_pmaxalloc(struct uk_alloc *a)
{
	struct uk_bbpalloc *b;
	size_t i, order;

	UK_ASSERT(a != NULL);
	b = (struct uk_bbpalloc *)&a->priv;

	/* Find biggest order that has still elements available */
	order = FREELIST_SIZE;
	for (i = 0; i < FREELIST_SIZE; i++) {
		if (!FREELIST_EMPTY(b->free_head[i]))
			order = i;
	}
	if (order == FREELIST_SIZE)
		return 0; /* no memory left */

	return (long) (1 << order);
}
1
2
3
4
5
6
7
8
9
10
11
/* 返回当前伙伴算法可用内存页的总数 */
static long bbuddy_pavailmem(struct uk_alloc *a)
{
	struct uk_bbpalloc *b;

	UK_ASSERT(a != NULL);
	b = (struct uk_bbpalloc *)&a->priv;

	return (long) b->nr_free_pages;
}

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/* 其实就是一个对内存区域初始化的操作 */
static int bbuddy_addmem(struct uk_alloc *a, void *base, size_t len)
{
	struct uk_bbpalloc *b;
	struct uk_bbpalloc_memr *memr;
	size_t memr_size;
	unsigned long count, i;
	chunk_head_t *ch;
	chunk_tail_t *ct;
	uintptr_t min, max, range;

	UK_ASSERT(a != NULL);
	UK_ASSERT(base != NULL);
	b = (struct uk_bbpalloc *)&a->priv;

	min = round_pgup((uintptr_t)base);  /* 将基址与页地址向上对齐 */
	max = round_pgdown((uintptr_t)base + (uintptr_t)len); /* 将要分配的地址末尾与页地址向下对齐 */
	if (max < min) {
		uk_pr_err("%"__PRIuptr": Failed to add memory region %"__PRIuptr"-%"__PRIuptr": Invalid range after applying page alignments\n",
			  (uintptr_t) a, (uintptr_t) base,
			  (uintptr_t) base + (uintptr_t) len);
		return -EINVAL;
	}

	range = max - min;  
    /* 
    
    能分配的地址范围，range被分为了三个部分，一个是memr内存区块管理占用空间，一个是bitmap位图占用空间，以及实际要分配出去的内存页的占用空间 
	
	min <--------------------------range------------------------->max
	 ---------------------------------------------------------------
	|        |           |                                          |
	 ---------------------------------------------------------------
	    ^          ^                         ^
	   memr   bitmap位图实际存储            实际可分配内存页
	
	*/

	/* We should have at least one page for bitmap tracking
	 * and one page for data.
	 * 如果除了memr内存区域和一个mapword以外，一个内存页的空间都没有的话，说明内存不够，无法分配
	 */
	if (range < round_pgup(sizeof(*memr) + BYTES_PER_MAPWORD) +
			__PAGE_SIZE) {
		uk_pr_err("%"__PRIuptr": Failed to add memory region %"__PRIuptr"-%"__PRIuptr": Not enough space after applying page alignments\n",
			  (uintptr_t) a, (uintptr_t) base,
			  (uintptr_t) base + (uintptr_t) len);
		return -EINVAL;
	}

	memr = (struct uk_bbpalloc_memr *)min;

	/*
	 * The number of pages is found by solving the inequality:
	 *
	 * sizeof(*memr) + bitmap_size + page_num * page_size <= range
	 *
	 * where: bitmap_size = page_num / BITS_PER_BYTE
	 
	 memr->nr_pages: 用于存储实际的可分配页数。计算公式为：总比特数/一个内存页所占的比特数+1
	 后面的+1是为了为bitmap让出空间，因为一个页需要一个位用来记录分配情况
	 	
	 memr->mm_alloc_bitmap: 用于指向bitmap实际占用的地址的首地址，具体地址为min(基址) + sizeof(*memr)(内存管理块的大小)
	 memr_size: 用于计算memr和bitmap占用的总地址空间(同时与内存页地址向上对齐)	 
		
	 memr->mm_alloc_bitmap_size: bitmap实际占用的地址大小，用memr_size减去memr占用的空间即可
	 
	 *
	 */
	memr->nr_pages =
		BITS_PER_BYTE * (range - sizeof(*memr)) /
		(BITS_PER_BYTE * __PAGE_SIZE + 1);
	memr->mm_alloc_bitmap = (unsigned long *) (min + sizeof(*memr));
	memr_size = round_pgup(sizeof(*memr) +
		DIV_ROUND_UP(memr->nr_pages, BITS_PER_BYTE));
	memr->mm_alloc_bitmap_size = memr_size - sizeof(*memr);

	min += memr_size;  /* 基址移动到可分配页的首地址 */
	range -= memr_size; /* 更新可分配页的总地址空间 */

	/*
	 * Initialize region's bitmap
	 */
	memr->first_page = min;
	/* add to list */
	memr->next = b->memr_head;
	b->memr_head = memr;

	/* All allocated by default. */
	memset(memr->mm_alloc_bitmap, (unsigned char) ~0,
			memr->mm_alloc_bitmap_size);

	/* free up the memory we've been given to play with */
	map_free(b, min, memr->nr_pages);

	count = 0;
    
    /*
     下面的这个while循环有点类似于一个数分解成各个二次幂数的过程
     例如 100 = 64 + 32 +4，先找100的最高位次幂，即64，然后剩下100-64 = 36
     再从36里头找最高位次幂，即32，然后剩下36-32 = 4，4正好是最高位次幂，所以将100划分成了64 + 32 + 4三个数字
        
     下面的循环内依次找到了当前可分配内存大小的最高位次幂，并将其创建一个新的空闲内存块，加入链表对应的位置中。
    */
	while (range != 0) {
		/*
		 * Next chunk is limited by alignment of min, but also
		 * must not be bigger than remaining range.
		 */
		for (i = __PAGE_SHIFT; (1UL << (i + 1)) <= range; i++)
			if (min & (1UL << i))
				break;

		uk_pr_debug("%"__PRIuptr": Add allocate unit %"__PRIuptr" - %"__PRIuptr" (order %lu)\n",
			    (uintptr_t)a, min, (uintptr_t)(min + (1UL << i)),
			    (i - __PAGE_SHIFT));

		ch = (chunk_head_t *)min;
		min += 1UL << i;
		range -= 1UL << i;
		ct = (chunk_tail_t *)min - 1;
		i -= __PAGE_SHIFT;
		ch->level = i;
		ch->next = b->free_head[i];
		ch->pprev = &b->free_head[i];
		ch->next->pprev = &ch->next;
		b->free_head[i] = ch;
		ct->level = i;
		count++;
	}

	return 0;
}
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
49
50
51
52
53
54
55
/* 整个伙伴算法数据结构+内存空间的初始化 */
struct uk_alloc *uk_allocbbuddy_init(void *base, size_t len)
{
	struct uk_alloc *a;
	struct uk_bbpalloc *b;
	size_t metalen;
	uintptr_t min, max;
	unsigned long i;

	min = round_pgup((uintptr_t)base);  /* 内存区域的基址 */
	max = round_pgdown((uintptr_t)base + (uintptr_t)len);  /* 内存区域的末尾地址 */
	UK_ASSERT(max > min);

	/* Allocate space for allocator descriptor  为内存分配器分配地址 */
	metalen = round_pgup(sizeof(*a) + sizeof(*b));

	/* enough space for allocator available?  判断是否足够为内存分配器分配空间*/
	if (min + metalen > max) {
		uk_pr_err("Not enough space for allocator: %"__PRIsz" B required but only %"__PRIuptr" B usable\n",
			  metalen, (max - min));
		return NULL;
	}

	a = (struct uk_alloc *)min;  /* 将内存分配器指向基址 */
	uk_pr_info("Initialize binary buddy allocator %"__PRIuptr"\n",
		   (uintptr_t)a);
	min += metalen;  /* 基址跳过内存分配器的占用空间 */
	memset(a, 0, metalen);    /* 内存分配器初始化 */
	b = (struct uk_bbpalloc *)&a->priv;
	
    /* 初始化伙伴算法空闲内存数组，将每个链表的free_head[i]指向free_tail[i] */
	for (i = 0; i < FREELIST_SIZE; i++) {
		b->free_head[i] = &b->free_tail[i];
		b->free_tail[i].pprev = &b->free_head[i];
		b->free_tail[i].next = NULL;
	}
	b->memr_head = NULL;

	/* initialize and register allocator interface   
	   将伙伴算法的各个函数注册到uk_alloc中的接口中去
	*/
	uk_alloc_init_palloc(a, bbuddy_palloc, bbuddy_pfree,
			     bbuddy_pmaxalloc, bbuddy_pavailmem,
			     bbuddy_addmem);

	if (max > min + metalen) {
		/* add left memory - ignore return value */
        /* 除去内存分配器以外的剩下的区域用来初始化内存分配 */
		bbuddy_addmem(a, (void *)(min + metalen),
				 (size_t)(max - min - metalen));
	}

	return a;
}

结合分析上述函数流程，内存区域分布图如图所示：

image-20221015123303381

TenonOSunikraft-learning

个人简介。